Segmentation fault by realloc, while creating dynamic generic array

Question

I tried to implement a dynamic generic array. However, when I tested my code, the result I got was "segmentation fault". I know that this error happens by realloc in a function ArrayListResize, but why?

Here is my implementation of a few methods:

typedef struct ArrayList {
  void** arr;
  size_t allocated, len;
} ArrayList;

int ArrayListInit(ArrayList *list) {
  list = (ArrayList *)malloc(sizeof(ArrayList));
  if (list == NULL) {
    fprintf(stderr, FAILED_ALLOCATION_MSG);
    return -1;
  }
  list->allocated = 0;
  list->len = 0;
  list->arr = (void **)NULL;
  return 0;
}

int ArrayListAppend(ArrayList *list, void *item) {
  if (item == NULL) {
    fprintf(stderr, INVALID_ARG_MSG);
    return -1;
  }
  if (ArrayListResize(list, list->len + 1) == -1) {
    return -1;
  }
  list->arr[list->len] = item;
  return 0;
}

int ArrayListResize(ArrayList *list, size_t len) {
  void **arr;
  size_t allocated = list->allocated, new_allocated;
  if (allocated >= len && len >= (allocated >> 1)) {
    assert(list->arr != NULL || len == 0);
    list->len = len;
    return 0;
  }
  if (len == 0)
    new_allocated = 0;
  else
    new_allocated = len + (len >> 3) + (len < 9 ? 3 : 6);
  arr = (void**)realloc(list->arr, sizeof(void *) * new_allocated); // Here I get the segmentation fault
  if (arr == NULL) {
    fprintf(stderr, FAILED_REALLOCATION_MSG);
    return -1;
  }
  list->arr = arr;
  list->allocated = new_allocated;
  list->len = len;
  return 0;
}

And this is the test code:

int* GenerateIntPointer(int n) {
  int* ptr_int = (int*)malloc(sizeof(int));
  *ptr_int = n;
  return ptr_int;
}

int main() {
  ArrayList list;
  ArrayListInit(&list);
  for (size_t i = 0; i < 10; i++) {
    ArrayListAppend(&list, (void*)GenerateIntPointer((int)i));
  }
  ArrayListDelete(&list, free);
  return 0;
}

Answer 1

A significant problem is that your ArrayListInit function is not actually initializing the list object you have declared on the stack in your main function! You have the line

  ArrayList list;

which sets aside memory for an ArrayList object on the stack. However, since it's a struct, then for efficiency & smaller code size purposes, the values are likely not initialized. Actually, since you've tagged this with c, then there are no even implicit constructors and C compilers won't initialize it. Even with a CPP compiler on a .c file, or with a .cpp file since there is no explicit constructor, no initialization will very likely occur even then.

Your code is then passing a pointer to this object in the line

  ArrayListInit(&list);

where the ArrayListInit code reassigns its parameter, i.e., also called list, to a new memory location, i.e., with

  list = (ArrayList *)malloc(sizeof(ArrayList));
  if (list == NULL) {
    fprintf(stderr, FAILED_ALLOCATION_MSG);
    return -1;
  }

Thus, the remaining initialization lines there, i.e.,

  list->allocated = 0;
  list->len = 0;
  list->arr = (void **)NULL;

update the newly allocated object, not the original list object in main. Thus, in ArrayListResize, the values passed to realloc are not valid, just whatever the stack bytes had initially, thus causing the segmentation fault.

The easiest way to fix this is to remove the lines in ArrayListInit which change the passed in list pointer value to a new memory location. Alternatively, especially if you will only be using one ArrayList object, you can get rid of the ArrayListInit method and just initialize the object values directly, e.g., as suggested in Neil's comment, i.e.,

You definitely want to initialize it; for example, ArrayList list = {0} or ArrayList list = {0,0,0} (C90).

In either case, you may also need to make an appropriate corresponding change to your ArrayListDelete function.

Alternatively, if you wish to have and use a dynamically allocated ArrayList object, then you would need to make several other changes. First, in main, have your declaration line be something like

ArrayList* list;

Then change your ArrayListInit function to have a parameter of ArrayList** list. In the rest of that function, change list to be *list. In the main function, change the ArrayListAppend call to pass in just list. Finally, you will need to make the corresponding changes in your ArrayListDelete function.