c - generic linked list

Question

I'm trying to write simplest generic linked list in ansi c (c89).

Here's code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node {
  struct node *previous;
  struct node *next;
  void *value;
};

struct node*
allocate_node(void);

void
free_node(struct node *freeable_node);

void
init_node(struct node *initializable_node);

void
print_node(struct node *printable_node);

struct node*
allocate_node(void)
{
  struct node *allocatable_node =
    (struct node*) calloc(1, sizeof(struct node));

  allocatable_node -> previous = NULL;
  allocatable_node -> next = NULL;
  return allocatable_node;
}

void
free_node(struct node *freeable_node)
{
  free(freeable_node -> previous);
  free(freeable_node -> next);
  free(freeable_node -> value);
  free(freeable_node);
}

void
init_node(struct node *initializable_node)
{
  int *initializable_value = (int*) (initializable_node -> value);
  initializable_value = calloc(1, sizeof(int*));
  *initializable_value = rand() % 100;
}

void
print_node(struct node *printable_node)
{
  printf("%d\n", *((int*) (printable_node -> value)));
}

int
main(void)
{
  struct node *demo_list = NULL;

  srand((unsigned int) time(NULL));
  demo_list = allocate_node();
  init_node(demo_list);
  print_node(demo_list);
  free(demo_list);

  return 0;
}

Via clang it compiles successfully, but after running prints segfault.

And valgrind output:

$ valgrind ./build/app                                                                  
==23061== Memcheck, a memory error detector
==23061== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==23061== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==23061== Command: ./build/app
==23061==
==23061== Invalid read of size 4
==23061==    at 0x4007AE: print_node (app.c:56)
==23061==    by 0x400813: main (app.c:67)
==23061==  Address 0x0 is not stack'd, malloc'd or (recently) free'd
==23061==
==23061==
==23061== Process terminating with default action of signal 11 (SIGSEGV)
==23061==  Access not within mapped region at address 0x0
==23061==    at 0x4007AE: print_node (app.c:56)
==23061==    by 0x400813: main (app.c:67)
==23061==  If you believe this happened as a result of a stack
==23061==  overflow in your program's main thread (unlikely but
==23061==  possible), you can try to increase the size of the
==23061==  main thread stack using the --main-stacksize= flag.
==23061==  The main thread stack size used in this run was 8388608.
==23061==
==23061== HEAP SUMMARY:
==23061==     in use at exit: 32 bytes in 2 blocks
==23061==   total heap usage: 2 allocs, 0 frees, 32 bytes allocated
==23061==
==23061== LEAK SUMMARY:
==23061==    definitely lost: 8 bytes in 1 blocks
==23061==    indirectly lost: 0 bytes in 0 blocks
==23061==      possibly lost: 0 bytes in 0 blocks
==23061==    still reachable: 24 bytes in 1 blocks
==23061==         suppressed: 0 bytes in 0 blocks
==23061== Rerun with --leak-check=full to see details of leaked memory
==23061==
==23061== For counts of detected and suppressed errors, rerun with: -v
==23061== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault

Any ideas how to fix it?

If you want a better way, have a look https://stackoverflow.com/questions/1885408/linux-kernels-list-h. — Stargateur, Jun 03 '17 at 10:45
"simplest **generic** linked list" --> note that `void *value;` can handle pointers to objects, but nor certainly pointers to functions. For that, use a `union` of `void*` and `int (*)()`. — chux - Reinstate Monica, Jun 03 '17 at 12:49
@chux when function pointers should be stored in data structures? D.s. are designed to store data, isn't it? — Lex Ushakov, Jun 03 '17 at 15:55
@LexUshakov A function pointer is data. In essence a function pointer store in a structure is the underlying attribute of virtual pointers in C++. Similar needs arise in C. — chux - Reinstate Monica, Jun 03 '17 at 17:33
@chux From the hardware point of view regular data and processor instructions stored in the same device. But for us, programmers, it's different things, right? Where is use-cases here for storing function pointers in data structures in practice? I really don't understand. — Lex Ushakov, Jun 04 '17 at 08:26
"for us, programmers, it's different things, right?' --> No. It is not about "regular data and processor instructions" It is about "regular data and function addresses" Try searching on "how to use function pointer inside structure in c". Example [this](https://stackoverflow.com/q/19039014/2410359) and [this](https://stackoverflow.com/q/1350376/2410359): — chux - Reinstate Monica, Jun 04 '17 at 14:42

H. Figueiredo · Accepted Answer · 2017-06-03T10:44:19.843

2

The problem is simple, you are missing one line in the init_node function.

void
init_node(struct node *initializable_node)
{
  int *initializable_value = (int*) (initializable_node -> value);
  initializable_value = calloc(1, sizeof(int*));
  *initializable_value = rand() % 100;
  //This line puts the variable you just created in the structure
  initializable_node->value=initializable_value;
}

By the way in the main function I think you meant to use free_node(demo_list); instead of free(demo_list);

If you need anymore help, feel free to ask!

EDIT: Realized the first line of your init_node function is not needed as you are assigning to a int pointer a NULL value.

So instead, do this:

void
init_node(struct node *initializable_node)
{
  int *initializable_value = calloc(1, sizeof(int*));
  *initializable_value = rand() % 100;
  //This line puts the variable you just created in the structure
  initializable_node->value=initializable_value;
}

edited Jun 03 '17 at 10:44

answered Jun 03 '17 at 10:21

H. Figueiredo

888
9
18

thanks! I thought about it) But, as I uunderstand, `*initializable_value` stores address of value in heap, and it's points to the same address as `initializable_node -> value`, why it's not true? Why we should do extra assigning? – Lex Ushakov Jun 03 '17 at 10:47
See edit, it's not true because `initializable_node->value` is NULL and therefor his address is garbage. Only when you do the `calloc` function you have a real address. So only then you assign the address you have allocated to the structure. – H. Figueiredo Jun 03 '17 at 10:51
You are right, I had understood. I am ashamed for my stupid questions. – Lex Ushakov Jun 03 '17 at 12:07

score 1 · Answer 2 · answered Jun 03 '17 at 10:19

1

free(freeable_node -> value);
This void * value is never initialized. so value will have garbage value by default and you are trying to free that memory.

answered Jun 03 '17 at 10:19

LearningC

3,182
1
12
19

But `free_node` inserted after `init_node` in `main`. – Lex Ushakov Jun 03 '17 at 10:42
@LexUshakov init_node() was not initializing value as per your code. – LearningC Jun 03 '17 at 12:59

c - generic linked list

2 Answers2