3
\$\begingroup\$

I've written an implementation of a dynamic array in C, but I'm not sure if my implementation is correct... This is what I'm worried about: if I add an element, will it remain in the collection? This problem has arisen from my (apparently) limited knowledge on void pointers. I haven't found any answers to my question online...

The List struct is defined like this:

typedef struct list
{
    /**
     * C-style array containing the data in this list.
     */
    void** data;
    /**
     * Amount of elements currently present in this list.
     */
    unsigned int size;
    /**
     * Amount of elements that could be present in this list (i.e. size + number of empty spots).
     */
    unsigned int capacity;
} List;

So far so good?

Now, when I want to add an element to a list l, I call List_Add(&l, &element)...

void List_Add(List* list, void* element)
{
    if (list->data == NULL)
    {
        return;
    }

    if (list->size == list->capacity)
    {
        // Double the data array of list.
        list->data = realloc(list->data, 2 * list->capacity * sizeof(void*));
        list->capacity *= 2;
    }

    if (list->data != NULL)
    {
        list->data[list->size] = element;
        ++(list->size);
    }
}

By the way: yes, list->data is malloced before calling this function.

I've done some testing with adding elements, but I'm not sure if it's entirely correct. If I were to call this function with an element created on the stack (example below), would it continue to work for the entirety of the program's lifetime?

Example

List l;
List_Init(&l);
int i = 1;
List_Add(&l, &i);
\$\endgroup\$
4
\$\begingroup\$

If I were to call this function with an element created on the stack (example below), would it continue to work for the entirety of the program's lifetime?

No, it wouldn't:

  • i is created on the stack
  • pointer to i is saved in the list
  • i disappears and stack is reused when caller goes out of scope (now list is pointing to garbage)

Your List can be used to store:

  • Objects created on the heap (using malloc)
  • Global/static objects
  • Local stack objects, but only if they are removed again before they go out of scope.

For example:

List l;
List_Init(&l);
int i = 1;
int* ptr_i = (int*)malloc(sizof(int));
*ptr_i = i;
List_Add(&l, ptr_i);
// *ptr_i will remain until someone calls free(ptr_i)
\$\endgroup\$
  • \$\begingroup\$ Lesson learned: whenever you are writing any form of ADT, make it work with hard copies of the data, rather than with pointers to data outside the ADT. \$\endgroup\$ – Lundin Feb 6 '14 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.