Sorting a dynamic array in c

Question

I am trying to create a function to create an ascending list using malloc and realloc.

Here is the structure:

struct sorted_dyn_array { int *array; int length; int capacity; }; 

returns a pointer to the sorted_dyn_array structure allocated on the heap

 const int BUFFER_INIT_SIZE = 5; const int KEY_NOT_FOUND = -1; struct sorted_dyn_array *arr_create(void) { struct sorted_dyn_array *new_arr = malloc(sizeof (struct sorted_dyn_array)); new_arr->array = malloc(sizeof (int) * BUFFER_INIT_SIZE); new_arr->length = 0; new_arr->capacity = 5; return new_arr; } 

free memory:

 void free_arr(struct sorted_dyn_array *arr) { free(arr->buffer); free(arr); } int arr_length(struct sorted_dyn_array * arr) { return arr->length; } int arr_capacity(struct sorted_dyn_array *arr) { return arr->capacity; } 

using binary search, find the position for the following number:

 int find_pos(int item, int arr[], int len) { int low = 0; int high = len-1; if (arr[0] >= item) { return 0; } if(arr[0] < item) { return KEY_NOT_FOUND; } while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == item) { return mid; } else if (arr[mid] < item) { low = mid + 1; } else { high = mid - 1; } if(arr[high] < item) { return high; } } return KEY_NOT_FOUND; } int arr_find_successor(struct sorted_dyn_array *arr, int k) { int len = arr_length(arr); return find_pos(k,arr->buffer,len); } 

enter a number, if it is already in the list, return false. Otherwise, paste the number in the list, and then return true

 bool arr_insert(struct sorted_dyn_array *arr, int k) { int pos = arr_find_successor(arr,k); if(arr_length(arr) == arr_capacity(arr)) { arr->capacity *= 2; arr->array = realloc(arr->buffer, sizeof(int) * arr->capacity);// realloc if the length exceed the capacity } if (pos == KEY_NOT_FOUND) {// If the number is greater than all the number in array,put it at the end int l = arr->length; arr->array[l] = k; arr->length++; } if (pos != KEY_NOT_FOUND){ for (int c = arr->length - 1; c >= pos; c--) arr->array[c+1] = array->array[c]; arr->array[pos] = k; arr->length++; } return true; } 

The main function:

 int main () { struct sorted_dyn_array *myarray = arr_create(); int next = 0; while (scanf("%d",&next) == 1) { int next_item = next; arr_insert(myarray, next_item); printf("%d\n",next_item); free_arr(myarray); } } 

However, when I try to scan the second number, it says

  int arr_length(struct sorted_dyn_array * arr) { return arr->length; } 

Invalid access memory. Can someone help me? I spend all day and still can't find where it goes wrong. Thanks in advance.

Answer 1

Calling free_arr at the end of the loop in main means that the second iteration works in free memory when calling arr_length .

This leads to undefined behavior, but you are very lucky to crash so quickly. Are you using a Windows debug build? (This will free up memory to a known "bad" value - 0xFEEEFEEE - to help you identify such problems.)

The fix here is simple: just move the call to free_arr(myarray) outside the loop.

 int main () { struct sorted_dyn_array *myarray = arr_create(); int next = 0; while (scanf("%d",&next) == 1) { int next_item = next; arr_insert(myarray, next_item); printf("%d\n",next_item); } free_arr(myarray); }