title: How may I implement a generic, dynamically growing array in C?
body: <p>My requirements:</p>
  
  <ul>
  <li>The data structure must be able to hold an arbitrary number of elements (on the order of hundreds of thousands).</li>
  <li>The data structure must use memory efficiently. In this case, that means adding on an extra hundred thousand items whenever they are needed.</li>
  <li>The data structure must hold items of an unknown but uniform type.</li>
  </ul>
  
  <p>The way I expected to be able to build one was to define a struct which represented the array. The struct contained the length of the array and the number of elements in the array. It also contained a pointer to an array of void pointers, which led to the actual data.</p>
  
  <p><a href="https://i.stack.imgur.com/FdK2Y.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/FdK2Y.png" alt="Diagram showing conceptual layout of the data structure"></a></p>
  
  <p>The pointer was used because the memory was malloc()'d and realloc()'d as the array grew. The array was of void pointers because the type of the elements was unknown. It was the responsibility of the user to create and initialize elements, to pass them to the array implementation, and to keep track what type was being used.</p>
  
  <p>In memory, the struct would exist either on the stack or in the heap (user's choice), the elements themselves would be scattered throughout the heap, and the array of pointers to the elements would exist in the heap.</p>
  
  <p>The problem is that when I went to implement this, I needed to be able to assign a void pointer to a spot in the array of pointers (e.g. when appending an element), and I could not do this because void pointers cannot be assigned (compiler says "incomplete type 'void' is not assignable").</p>
  
  <p>Is there a different approach I should be using?</p>
  
  <hr>
  
  <p>Nguai's code helped me get it right! His is below in his answer, and here is the implementation I wrote based on his code:</p>
  
  <pre><code>typedef struct {
      void **head;
      size_t used_size;
      size_t free_size;
      size_t current_size;
      size_t size_increment;
  } GrowingArray;
  
  GrowingArray createEmptyGrowingArray(int initial_size, int size_increment) {
      GrowingArray empty_growing_array;
      empty_growing_array.head = malloc(initial_size * sizeof(void *));
      empty_growing_array.used_size = 0;
      empty_growing_array.free_size = initial_size;
      empty_growing_array.current_size = initial_size;
      empty_growing_array.size_increment = size_increment;
  
      return empty_growing_array;
  }
  
  GrowingArray appendToGrowingArray(GrowingArray growing_array, void *new_element) {
  
      void *new_head_of_array;
  
      if (growing_array.free_size == 0) {
          new_head_of_array = realloc(growing_array.head, (growing_array.current_size + growing_array.size_increment) * sizeof(void*));
          if (new_head_of_array == NULL) {
              printf("Reallocation failure.\n");
          }
  
          growing_array.free_size = growing_array.size_increment;
          growing_array.current_size += growing_array.size_increment;
          growing_array.head = new_head_of_array;
      }
  
      growing_array.head[growing_array.used_size++] = new_element;
      growing_array.free_size--;
  
      return growing_array;
  }
  
  void finalizeGrowingArrayMemory(GrowingArray growing_array) {
      growing_array.head = realloc(growing_array.head, growing_array.current_size * sizeof(void *));
  }
  
  void freeGrowingArray(GrowingArray growing_array) {
      free(growing_array.head);
  }
  
  int main(int argc, char* argv[]) {
      GrowingArray test_array = createEmptyGrowingArray(5, 1);
  
      int *test_integer = (int *)malloc(1 * sizeof(int));
      *test_integer = 4;
  
      int *another_integer = (int *)malloc(1 * sizeof(int));
      *another_integer = 6;
  
      int *yet_another_integer = (int *)malloc(sizeof(int));
      *yet_another_integer = 9;
  
      test_array = appendToGrowingArray(test_array, test_integer);
      test_array = appendToGrowingArray(test_array, another_integer);
      test_array = appendToGrowingArray(test_array, yet_another_integer);
      finalizeGrowingArrayMemory(test_array);
  
      printf("%x,", *(int *)test_array.head[0]);
      printf("%x,", *(int *)test_array.head[1]);
      printf("%x\n", *(int *)test_array.head[2]);
  
      freeGrowingArray(test_array);
  
      printf("Going to free %llx\n", (long long int)test_integer);
      free(test_integer);
  
      printf("Going to free %llx\n", (long long int)another_integer);
      free(another_integer);
  
      printf("Going to free %llx\n", (long long int)yet_another_integer);
      free(yet_another_integer);
  
      return 0;
  }
  </code></pre>