Problems with realloc() | | |
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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#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[0][6], becomes 0.
How do I fix this problem?
Thank you.
Regards,
Rayne
| | | | re: Problems with realloc()
<lancer6238@yahoo.comwrote in message
news:1185097082.039704.55520@g12g2000prg.googlegro ups.com... Quote:
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 <stdio.h>
#include <stdlib.h>
>
#include <time.h>
>
#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]? Quote:
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[0][6], becomes 0.
>
How do I fix this problem?
>
Thank you.
>
Regards,
Rayne
>
| | | | re: Problems with realloc()
On Jul 22, 2:38 pm, "lancer6...@yahoo.com" <lancer6...@yahoo.com>
wrote: Quote:
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 <stdio.h>
#include <stdlib.h>
>
#include <time.h>
>
#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[0][6], 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 []. | | | | re: Problems with realloc()
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[0][] has 3 integers and the other a[1][] has 7
integers. Then length[0] = 3 and length[1] = 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.
| | | | re: Problems with realloc()
On Jul 22, 11:10 pm, "lancer6...@yahoo.com" <lancer6...@yahoo.com>
wrote: Quote:
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. | | | | re: Problems with realloc()
lancer6238@yahoo.com wrote: Quote:
>
On Jul 22, 11:10 pm, "lancer6...@yahoo.com" <lancer6...@yahoo.com>
wrote: Quote:
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 <stdio.h>
#include <stdlib.h>
#include <time.h>
#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 | | | | re: Problems with realloc()
pete wrote: Quote:
#define N 10 /* number of integers to sort */
#define SIZE 2 /* number of groups */
#define MAX 100 /* maximum value of the integers */
Quote:
int main(void)
{
int i, j, *length, x[N], **a, *temp;
Quote:
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. Quote:
free(length);
return 0;
}
Quote:
void free_int_2d(int **a, int i)
{
while (i-- 0) {
free(a[i]);
}
free(a);
}
--
pete | | | | re: Problems with realloc()
On Sun, 22 Jul 2007 02:38:02 -0700, "lancer6238@yahoo.com"
<lancer6238@yahoo.comwrote: Quote:
>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 <stdio.h>
>#include <stdlib.h>
>
>#include <time.h>
>
>#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)
snip unrelated function Quote:
>}
>
>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. Quote:
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? Quote:
>
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. Quote:
>
/* 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. Quote:
{
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. Quote:
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. Quote:
{
> 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[1] could be 4. When i is
1, you free a[1] and increment i to 2. length[2] doesn't exist. More
undefined behavior. Quote:
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[0][6], becomes 0.
Remove del for email |  |
| | |  /bytes/about
We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights.
Get the best answers to your questions from over 226,392 network members.
|
