431,827 Members | 2,155 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 431,827 IT Pros & Developers. It's quick & easy.

# Problems with realloc()

 P: n/a Hi, I'm writing a program that separates a set of integers into groups and then quicksort each group individually. However, I'm having problems with my realloc() function. (Pardon me if the indentation is weird. There's no preview button here and I can't tell if my indentation is correct.) #include #include #include #define N 10 // number of integers to sort #define size 2 // number of groups #define MAX 100 // maximum value of the integers void quicksort(int a[], int lo, int hi) { int h, l, p, t; if (lo < hi) { l = lo; h = hi; p = a[hi]; do { while ((l < h) && (a[l] <= p)) l = l+1; while ((h l) && (a[h] >= p)) h = h-1; if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; } } while (l < h); t = a[l]; a[l] = a[hi]; a[hi] = t; quicksort(a, lo, l-1); quicksort(a, l+1, hi); } } int main() { int i, j, *length, x[N], **a, *temp; srand(time(NULL)); a = (int **)malloc(size * sizeof(int*)); for (i = 0 ; i < size ; i++) a[i] = (int*)malloc((N/size + 1) * sizeof(int)); length = (int *)malloc(size * sizeof(int)); /* Generate random integers */ printf("Original: \n"); for (i = 0 ; i < N ; i++) { x[i] = rand() % MAX; printf("%d ", x[i]); } printf("\n\n"); for (j = 0 ; j < N ; j++) { for (i = size ; i >= 1 ; i--) { if ((double)x[j]/(double)MAX (double)(i-1)/ (double)size) { a[i-1][length[i-1]] = x[j]; length[i-1]++; if (length[i-1] N/size + 1) { if ((temp = realloc(a[i-1], sizeof(int) * 2 * (N/size + 1))) == NULL) { printf("ERROR: realloc failed"); exit(0); } a[i-1] = temp; } break; } } } for(i = 0 ; i < size ; i++) quicksort(a[i],0,length[i]-1); printf("Sorted:\n"); for(i = 0 ; i < size ; i++) { for (j = 0 ; j < length[i] ; j++) printf("%d ", a[i][j]); } printf("\n"); for (i = 0 ; i < length[i] ; i++) free(a[i]); free(a); free(length); return 0; } Everytime the realloc() function is needed, i.e. when the size of any of the 2 groups has to be increased to more than the original 6 integers, I'll either get the error "Segmentation Fault", "*** glibc detected *** realloc(): invalid next size: 0x00000000005020c0 ***", or the value that's supposed to go into the newly created memory, e.g. a, becomes 0. How do I fix this problem? Thank you. Regards, Rayne Jul 22 '07 #1
7 Replies

 P: n/a #include #include #define N 10 // number of integers to sort #define size 2 // number of groups #define MAX 100 // maximum value of the integers void quicksort(int a[], int lo, int hi) { int h, l, p, t; if (lo < hi) { l = lo; h = hi; p = a[hi]; do { while ((l < h) && (a[l] <= p)) l = l+1; while ((h l) && (a[h] >= p)) h = h-1; if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; } } while (l < h); t = a[l]; a[l] = a[hi]; a[hi] = t; quicksort(a, lo, l-1); quicksort(a, l+1, hi); } } int main() { int i, j, *length, x[N], **a, *temp; srand(time(NULL)); a = (int **)malloc(size * sizeof(int*)); for (i = 0 ; i < size ; i++) a[i] = (int*)malloc((N/size + 1) * sizeof(int)); length = (int *)malloc(size * sizeof(int)); /* Generate random integers */ printf("Original: \n"); for (i = 0 ; i < N ; i++) { x[i] = rand() % MAX; printf("%d ", x[i]); } printf("\n\n"); for (j = 0 ; j < N ; j++) { for (i = size ; i >= 1 ; i--) { if ((double)x[j]/(double)MAX (double)(i-1)/ (double)size) { a[i-1][length[i-1]] = x[j]; What is stored in length[i-1]? length[i-1]++; if (length[i-1] N/size + 1) { if ((temp = realloc(a[i-1], sizeof(int) * 2 * (N/size + 1))) == NULL) { printf("ERROR: realloc failed"); exit(0); } a[i-1] = temp; } break; } } } for(i = 0 ; i < size ; i++) quicksort(a[i],0,length[i]-1); printf("Sorted:\n"); for(i = 0 ; i < size ; i++) { for (j = 0 ; j < length[i] ; j++) printf("%d ", a[i][j]); } printf("\n"); for (i = 0 ; i < length[i] ; i++) free(a[i]); free(a); free(length); return 0; } Everytime the realloc() function is needed, i.e. when the size of any of the 2 groups has to be increased to more than the original 6 integers, I'll either get the error "Segmentation Fault", "*** glibc detected *** realloc(): invalid next size: 0x00000000005020c0 ***", or the value that's supposed to go into the newly created memory, e.g. a, becomes 0. How do I fix this problem? Thank you. Regards, Rayne Jul 22 '07 #2

 P: n/a On Jul 22, 2:38 pm, "lancer6...@yahoo.com" wrote: Hi, I'm writing a program that separates a set of integers into groups and then quicksort each group individually. However, I'm having problems with my realloc() function. (Pardon me if the indentation is weird. There's no preview button here and I can't tell if my indentation is correct.) #include #include #include #define N 10 // number of integers to sort #define size 2 // number of groups #define MAX 100 // maximum value of the integers void quicksort(int a[], int lo, int hi) { int h, l, p, t; if (lo < hi) { l = lo; h = hi; p = a[hi]; do { while ((l < h) && (a[l] <= p)) l = l+1; while ((h l) && (a[h] >= p)) h = h-1; if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; } } while (l < h); t = a[l]; a[l] = a[hi]; a[hi] = t; quicksort(a, lo, l-1); quicksort(a, l+1, hi); } } int main() { int i, j, *length, x[N], **a, *temp; srand(time(NULL)); a = (int **)malloc(size * sizeof(int*)); for (i = 0 ; i < size ; i++) a[i] = (int*)malloc((N/size + 1) * sizeof(int)); length = (int *)malloc(size * sizeof(int)); /* Generate random integers */ printf("Original: \n"); for (i = 0 ; i < N ; i++) { x[i] = rand() % MAX; printf("%d ", x[i]); } printf("\n\n"); for (j = 0 ; j < N ; j++) { for (i = size ; i >= 1 ; i--) { if ((double)x[j]/(double)MAX (double)(i-1)/ (double)size) { a[i-1][length[i-1]] = x[j]; length[i-1]++; if (length[i-1] N/size + 1) { if ((temp = realloc(a[i-1], sizeof(int) * 2 * (N/size + 1))) == NULL) { printf("ERROR: realloc failed"); exit(0); } a[i-1] = temp; } break; } } } for(i = 0 ; i < size ; i++) quicksort(a[i],0,length[i]-1); printf("Sorted:\n"); for(i = 0 ; i < size ; i++) { for (j = 0 ; j < length[i] ; j++) printf("%d ", a[i][j]); } printf("\n"); for (i = 0 ; i < length[i] ; i++) free(a[i]); free(a); free(length); return 0; } Everytime the realloc() function is needed, i.e. when the size of any of the 2 groups has to be increased to more than the original 6 integers, I'll either get the error "Segmentation Fault", "*** glibc detected *** realloc(): invalid next size: 0x00000000005020c0 ***", or the value that's supposed to go into the newly created memory, e.g. a, becomes 0. How do I fix this problem? Thank you. Regards, Rayne The program never initializes the length array. If the idea was to start with 0, may be you should have used a calloc instead of malloc for length []. Jul 22 '07 #3

 P: n/a length[] is the number of each row in matrix a. Initially, a is a rectangular "size-by-(N/size+1)" matrix. For example, if size is 2 and N is 10, then a is a 2-by-6 matrix. As I'm splitting the integers into the appropriate groups (if size = 2, then there are 2 groups), I may end up with a jagged array, i.e. one group/row a[] has 3 integers and the other a[] has 7 integers. Then length = 3 and length = 7. I've initialized length[] with calloc, but I still have the same problem. I also don't get why length is the problem here. Jul 22 '07 #4

 P: n/a On Jul 22, 11:10 pm, "lancer6...@yahoo.com" wrote: length[] is the number of each row in matrix a. I meant to say length[] is the number of integers in each row of matrix a. Jul 22 '07 #5

 P: n/a la********@yahoo.com wrote: > On Jul 22, 11:10 pm, "lancer6...@yahoo.com" wrote: length[] is the number of each row in matrix a. I meant to say length[] is the number of integers in each row of matrix a. /* BEGIN new.c */ #include #include #include #define N 10 /* number of integers to sort */ #define SIZE 2 /* number of groups */ #define MAX 100 /* maximum value of the integers */ void free_int_2d(int **a, int i); void quicksort(int a[], int lo, int hi); int main(void) { int i, j, *length, x[N], **a, *temp; srand(time(NULL)); a = malloc(SIZE * sizeof *a); if (a == NULL) { puts("a == NULL"); exit(EXIT_FAILURE); } length = malloc(SIZE * sizeof *length); if (length == NULL) { free_int_2d(a, SIZE); puts("length == NULL"); exit(EXIT_FAILURE); } for (i = 0 ; i < SIZE ; i++) { a[i] = NULL; length[i] = 0; } puts("Original: "); for (i = 0 ; i < N ; i++) { x[i] = rand() % MAX; printf("%2d ", x[i]); } puts("\n"); for (j = 0 ; j < N ; j++) { i = SIZE; while (i-- 0) { if (x[j] / (double)MAX >= i / (double)SIZE) { ++length[i]; temp = realloc(a[i], length[i] * sizeof *temp); if (temp == NULL) { puts("ERROR: realloc failed"); exit(EXIT_FAILURE); } a[i] = temp; a[i][length[i] - 1] = x[j]; break; } } } for (i = 0 ; i < SIZE ; i++) { quicksort(a[i], 0, length[i] - 1); } puts("Sorted:"); for (i = 0 ; i < SIZE ; i++) { printf("a[%d] ", i); for (j = 0 ; j < length[i] ; j++) { printf("%2d ", a[i][j]); } putchar('\n'); } free_int_2d(a, length[i]); free(length); return 0; } void quicksort(int a[], int lo, int hi) { int h, l, p, t; if (lo < hi) { l = lo; h = hi; p = a[hi]; do { while ((l < h) && (a[l] <= p)) { l = l+1; } while ((h l) && (a[h] >= p)) { h = h-1; } if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; } } while (l < h); t = a[l]; a[l] = a[hi]; a[hi] = t; quicksort(a, lo, l-1); quicksort(a, l+1, hi); } } void free_int_2d(int **a, int i) { while (i-- 0) { free(a[i]); } free(a); } /* END new.c */ -- pete Jul 22 '07 #6

 P: n/a pete wrote: #define N 10 /* number of integers to sort */ #define SIZE 2 /* number of groups */ #define MAX 100 /* maximum value of the integers */ int main(void) { int i, j, *length, x[N], **a, *temp; for (i = 0 ; i < SIZE ; i++) { printf("a[%d] ", i); for (j = 0 ; j < length[i] ; j++) { printf("%2d ", a[i][j]); } putchar('\n'); } free_int_2d(a, length[i]); Oops! The above line of code should be free_int_2d(a, SIZE); instead. free(length); return 0; } void free_int_2d(int **a, int i) { while (i-- 0) { free(a[i]); } free(a); } -- pete Jul 22 '07 #7

 P: n/a On Sun, 22 Jul 2007 02:38:02 -0700, "la********@yahoo.com" Hi,I'm writing a program that separates a set of integers into groups andthen quicksort each group individually. However, I'm having problemswith my realloc() function. (Pardon me if the indentation is weird.There's no preview button here and I can't tell if my indentation iscorrect.)#include #include #include #define N 10 // number of integers to sort#define size 2 // number of groups#define MAX 100 // maximum value of the integersvoid quicksort(int a[], int lo, int hi) snip unrelated function >}int main(){ int i, j, *length, x[N], **a, *temp; srand(time(NULL)); a = (int **)malloc(size * sizeof(int*)); Don't cast the return from malloc. It only serves to hide undefined behavior. for (i = 0 ; i < size ; i++) a[i] = (int*)malloc((N/size + 1) * sizeof(int)); Are you sure that all groups will have the same number of elements? > length = (int *)malloc(size * sizeof(int)); length now points to a space large enough to hold 2 int. However, neither int has been assigned a value. They are both indeterminate. You should always check malloc for success. > /* Generate random integers */ printf("Original: \n"); for (i = 0 ; i < N ; i++) { x[i] = rand() % MAX; printf("%d ", x[i]); } printf("\n\n"); for (j = 0 ; j < N ; j++) { for (i = size ; i >= 1 ; i--) { if ((double)x[j]/(double)MAX (double)(i-1)/(double)size) You only need one cast in each division expression. { a[i-1][length[i-1]] = x[j]; length[i-1] is still indeterminate. This statement invokes undefined behavior. From the standard point of view, everything that happens after this point unconstrained. From a practical point of view, length[i-1] probably evaluates to a value out of range for a[i-1] so you end up overflowing the allocated area. On many systems, this has the effect of stepping on data that the allocation routines use to keep track of dynamic allocations. length[i-1]++; if (length[i-1] N/size + 1) { if ((temp = realloc(a[i-1], sizeof(int) * 2 * (N/size+ 1))) == NULL) And when realloc tries to use this corrupted data, it gets very confused. { printf("ERROR: realloc failed"); exit(0); } a[i-1] = temp; } break; } } } for(i = 0 ; i < size ; i++) quicksort(a[i],0,length[i]-1); printf("Sorted:\n"); for(i = 0 ; i < size ; i++) { for (j = 0 ; j < length[i] ; j++) printf("%d ", a[i][j]); } printf("\n"); for (i = 0 ; i < length[i] ; i++) This is wrong. i should run from 0 to size. Each a[i] does point to length[i] int but you only free the a[i], not each int it points to. size is 2. length points to 2 int. length could be 4. When i is 1, you free a and increment i to 2. length doesn't exist. More undefined behavior. free(a[i]); free(a); free(length); return 0;}Everytime the realloc() function is needed, i.e. when the size of anyof the 2 groups has to be increased to more than the original 6integers, I'll either get the error "Segmentation Fault", "*** glibcdetected *** realloc(): invalid next size: 0x00000000005020c0 ***", orthe value that's supposed to go into the newly created memory, e.g.a, becomes 0. Remove del for email Jul 22 '07 #8

### This discussion thread is closed

Replies have been disabled for this discussion. 