4

I'm trying to create a function in order to create a ascending order list by using "malloc" and "realloc".

Here is the structure:

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

returns a pointer to a 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 next 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);  
}

insert a number, if it is already in the list, return false. Otherwise, insert a number into the list 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;
}

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 scanf the second number it says

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

invalid access memory. Can somebody help me out? I spend like a whole afternoon and still cant find where goes wrong. Thanks in advance.

6
  • 1
    +1 for showing thorough attempt. Commented Jul 23, 2013 at 0:16
  • 1
    have you considered using Valgrind? Commented Jul 23, 2013 at 0:16
  • The 5 in arr_create() should be BUFFER_INIT_SIZE. Commented Jul 23, 2013 at 0:20
  • Reading the value of arr[0] in find_pos is undefined behavior when the array is empty. Commented Jul 23, 2013 at 0:27
  • Looking at the actual comparisons in find_pos: it's a fundamental property of integers that either arr[0] >= item or arr[0] < item is true. The while loop is never reached. Commented Jul 23, 2013 at 0:30

1 Answer 1

1

The call to free_arr at the end of the loop in main means that the second iteration is operating on freed memory when it calls arr_length.

This results in undefined behaviour but you've been quite lucky to crash so quickly. Are you running a Windows debug build? (This will set freed memory to a known 'bad' value - 0xFEEEFEEE - to help you spot problems like this.)

The fix is simple here - just move the free_arr(myarray) call 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);
}
Sign up to request clarification or add additional context in comments.

1 Comment

I got a sdl(21291) malloc: *** error for object 0x7fb14bc03a50: pointer being freed was not allocated *** set a breakpoint in malloc_error_break to debug message. Your fix does fix the problems once the code compiles.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.