How to push and pop a void pointer in C

Question

I have this working code:

#import <stdlib.h>
#import <stdio.h>

typedef struct myarray {
  int len;
  void* items[];
} MYARRAY;

MYARRAY *collection;

void
mypop(void** val) {
  puts(collection->items[collection->len]);
  *val = collection->items[collection->len--];
}

void
mypush(void* val) {
  int len = collection->len++;
  collection->items[len] = val;
  puts(collection->items[len]);
}

int
main() {
  puts("Start");
  collection = malloc( sizeof *collection + (sizeof collection->items[0] * 1000) );
  collection->len = 0;
  puts("Defined collection");
  mypush("foo");
  puts("Pushed foo");
  mypush("bar");
  puts("Pushed bar");
  char str1;
  mypop((void*)&str1);
  puts("Popped bar");
  puts(&str1);
  char str2;
  mypop((void*)&str2);
  puts("Popped foo");
  puts(&str2);
  puts("Done");
  return 0;
}

It outputs:

Start
Defined collection
foo
Pushed foo
bar
Pushed bar
(null)
Popped bar

bar
Popped foo
�ߍ
Done

It should output this instead:

Start
Defined collection
foo
Pushed foo
bar
Pushed bar
bar
Popped bar
bar
foo
Popped foo
foo
Done

Being new to C I am not really sure what's going on or why the output is "corrupted" like that. It seems though that the double pointer void** allows you to pass in a pointer and get out a value without knowing the type, so yay. But wondering if one could show how this code should be implemented so I can get a feel for how to do such a thing.

Compiled with clang:

clang -o example example.c

---

Update

I've updated my code to reflect the latest answers, but still not sure the malloc of the collection is correct.

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

typedef struct myarray {
  int len;
  void* items[];
} MYARRAY;

MYARRAY *collection;

void
mypop(void** val) {
  --collection->len;
  puts(collection->items[collection->len]);
  *val = collection->items[collection->len];
}

void
mypush(void* val) {
  int len = collection->len++;
  collection->items[len] = val;
  puts(collection->items[len]);
}

int
main() {
  puts("Start");
  collection = malloc( sizeof *collection + (sizeof collection->items[0] * 1000) );
  collection->len = 0;
  puts("Defined collection");
  mypush("foo");
  puts("Pushed foo");
  mypush("bar");
  puts("Pushed bar");
  char *str1;
  mypop((void**)&str1);
  puts("Popped bar");
  puts(str1);
  char *str2;
  mypop((void**)&str2);
  puts("Popped foo");
  puts(str2);
  free(collection);
  puts("Done");
  return 0;
}

Betel

*value - No. You cannot dereference a void pointer. You must cast to a valid type first. You are free to use void just as any other pointer, except you cannot dereference it (it has no type). – Falcongentle

Btw, can we keep array index empty in C like here void* items[]; ? I guess not. – Electronic

@Electronic It's a flexible array member. But one needs to dynamically allocate memory for such members, which isn't done here. – Anemophilous

There is a lot wrong with your code. Are you sure you want to try something this complicated right now? The major problem with your code is that it doesn't allocate memory for the items or even for the array of pointers to the items. If you have a limit on the number of items that can be stored in a collection, then you can just allocate the items member as void *items[YOUR_LIMIT]. That would take care of allocating memory for the array of pointers to items. As far as allocating memory for the items, your mypush function needs to know the size of the item to push, so it can allocate memory. – Miscarriage

I have looked through many examples of obscure uses of pointers, this is just my first time trying to apply it and I have a lot to learn. But doing it this way is most helpful for me, if I can see how something like this works. – Betel

the misconception of people is to think that void * is the "homogeneous" type of collection in C, it's not. You should use not use void * this way. It's a bad practice. – Wardrobe

Please show me how I can accomplish the same thing without void. If it were bad practice I don't understand why free(void*) uses it, and several other core lib functions. Explaining why it's bad practice would be helpful too. – Betel

@LancePollard because void * lose the information of the type, free() take a void * because it doesn't care about the type, malloc() return a void * because it doesn't know the type. Also, what you trying to do is never used in any production code in C. With your structure, If I want stock a int I would need to allocate each int with malloc(). This would be a performance killer. Your code is ok for a string but not for any scalar. In C, you can code a generic linked list with some trick, but you can't code a generic vector container. void * => char * or find a macro solution. – Wardrobe

Answer 1

There are a few things to fix, but for a beginner that is not bad.

1. pop

You need to decrement first len (your push does correctly post-increment). This is a stack.

void mypop(void** val) {
     puts(collection->items[--collection->len]);
     *val = collection->items[collection->len];
}

Arrays start at 0, so

len = 0;
items[len++] = elem1;  // len is 0 for the assignment then incremented
items[len++] = elem2;  // len is 1 for the assignment then incremented

then to pop values

elem2 = items[--len];  // len is first decremented to 1
elem1 = items[--len];  // len is first decremented to 0

2. str

What you want is a pointer to chars, a char *, for str1 and str2, since pop() will store a pointer, not a single char.

 char *str1;
 mypop((void **)&str1);
 puts("Popped bar");
 puts(str1);
 char *str2;
 mypop((void **)&str2);
 puts("Popped foo");
 puts(str2);
 puts("Done");
 return 0;

That should fix the visibly corrupted display. However there are a few more things of interest

3. Allocation

Your programs runs because your allocation is big, and items being inside the struct, its space is likely covered by the whole allocation. But that makes an assumption (quite likely, to be fair), which could lead to undefined behavior in some situations.

But to be cleaner, since you have two entities to allocate, that needs two allocations

collection = malloc( sizeof *collection );
collection->items = malloc( sizeof(collection->items[0]) * 1000 );

to be both freed later on.

In this case, the structure should be

typedef struct myarray {
  int len;
  void **;
} MYARRAY

Since MYARRAY itself is pretty small, you could also declare it statically

static MYARRAY collection;

4. import

#import is deprecated, please use #include instead.

Authoritarian

I get error: array type 'void *[]' is not assignable: collection->items = malloc( sizeof(collection->items[0]) * 1000 );. – Betel

#import is not standard C, FYI. – Telegonus

Answer 2

One problem is here:

void mypush(void* state) {
   DATA data = { state };
   int pos = collection.len++;
   collection.items[pos] = &data;
}

Note that the last line of this function stores a pointer to the local variable data into your items array. But as soon as the mypush() function returns, that local variable is destroyed, which means that the pointer you stored into the array is no longer valid! (it is now a dangling pointer) Most likely your segmentation fault occurs when you later on try to read from that now-invalid pointer (which invokes undefined behavior, and in this case, a crash)

To avoid that, simply store the state variable directly, without involving a local data variable at all. You can cast other pointer-types to (and from) void * as necessary (as long as you are careful to make sure that your casts match the actual type of the data the pointer points to -- with void-pointers, the compiler won't tell your if you're casting to an inappropriate type!)

Matrimony

"simply store the state variable directly" not sure what you mean, I am new to C. – Betel

I mean what you did in your original program: collection.items[pos] = state; – Matrimony

I'm not sure what is different from my first example. – Betel

Answer 3

There are two main issues with your modified code. The first is in the mypop function:

void
mypop(void** val) {
  puts(collection->items[collection->len]);
  *val = collection->items[collection->len--];
}

When the function is entered, there are a total of collection->len in the collection->items array, and the index of the last one is collection->len - 1. So collection->items[collection->len] is reading an array member that hasn't been written to yet, and allocated memory has indeterminate values before it is written. So when you call puts on this value, you're dereferencing an invalid pointer. This invokes undefined behavior. On your machine it prints "(null)" but on mine it crashes.

This can be fixed by decrementing len first:

void
mypop(void** val) {
  collection->len--;
  puts(collection->items[collection->len]);
  *val = collection->items[collection->len];
}

The second problem is in how you're saving the popped values:

  char str1;
  mypop((void*)&str1);
  puts("Popped bar");
  puts(&str1);
  char str2;
  mypop((void*)&str2);
  puts("Popped foo");
  puts(&str2);

The mypop function is expecting a void **, i.e. the address of a void *, but you're passing the address of a char. When the mypop then assigns to *val, it tries to write sizeof(void *) bytes (most likely either 4 or 8 bytes) to assign the value, but str1 and str2 are only sizeof(char) == 1 byte in size. So this means *val = ... is writing past str1 and str2 into adjacent memory that doesn't belong to it. This again invokes undefined behavior.

Since a char * is what was stored in your stack, it should be the address of a char * that you pass to mypop. So make str1 and str2 pointers to char:

  char *str1;
  mypop((void**)&str1);
  puts("Popped bar");
  puts(str1);
  char *str2;
  mypop((void**)&str2);
  puts("Popped foo");
  puts(str2);

This will get your program running properly.

Also, you haven't free'ed the memory you allocated, so be sure to free(collection) at the end of your program.

You should also use #include instead of #import to include header files, as the former is standardized while the latter is an extension.

Regarding your malloc:

collection = malloc( sizeof *collection + (sizeof collection->items[0] * 1000) );

This is fine. The size of a struct with a flexible array member doesn't include the size of that member. So when space for such a struct is allocated, you need the size of the struct plus size for some number of array elements. This is exactly what you've done: allocated space for the struct with a flexible array member capable of holding 1000 elements.

Handwriting

I've pasted my updated code above, still getting a segfault. I think it's because "So this means *val = ... is writing past str1 and str2", but not sure how to fix that. – Betel

@LancePollard The decrement in mypop is not what this or the other answer specified. You're decrementing the array element, not the counter. – Handwriting

@LancePollard Also, see my edit regarding the malloc. – Handwriting

Answer 4

Changed a few things, commented in the code below.

You need to note that you must allocate one collection structure, wich have a pointer to 1000 items that need to be allocated too, and later deallocate these. And in C arrays start at 0, so the last item pushed is collection->items[collection->len - 1].

I don't did it, but one common practice, when working with C strings, is to initialize all the elements in the array to zero right after allocation, so functions like puts() will never cause a segmentation fault, because 0 is interpreted as the end of the string.

#include <stdio.h>

typedef struct myarray {
  int len;
  void** items;
} MYARRAY;

MYARRAY *collection;

void
mypop(void** val) {
  --collection->len;
  puts(collection->items[collection->len]);
  *val = collection->items[collection->len];
}

void
mypush(void* val) {
  collection->len++;
  collection->items[collection->len - 1] = val;  // 0-based index
  puts((char *)collection->items[collection->len - 1]); // must cast to char*
}

int
main() {
  puts("Start");
  collection = malloc(sizeof(MYARRAY)); // alloc one structure
  collection->items = malloc(sizeof(void *) * 1000);    // that have 1000 items
  collection->len = 0;
  puts("Defined collection");
  mypush("foo");
  puts("Pushed foo");
  mypush("bar");
  puts("Pushed bar");
  char *str1;
  mypop((void**)&str1);
  puts("Popped bar");
  puts(str1);
  char *str2;
  mypop((void**)&str2);
  puts("Popped foo");
  puts(str2);
  free(collection->items);  // need to deallocate this too
  free(collection);
  puts("Done");
  return 0;
}

Monteith