Problems with realloc()

[lancer6238]

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

[Barry]

<la********@yahoo.comwrote in message
news:11*********************@g12g2000prg.googlegro ups.com...

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]?

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

[DingDong]

On Jul 22, 2:38 pm, "[e-mail]" <[e-mail]>
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 <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 [].

[lancer6238]

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.

[lancer6238]

On Jul 22, 11:10 pm, "[e-mail]" <[e-mail]>
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.

[pete]

la********@yahoo.com wrote:

>
On Jul 22, 11:10 pm, "[e-mail]" <[e-mail]>
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 <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

[pete]

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

[Barry Schwarz]

On Sun, 22 Jul 2007 02:38:02 -0700, "la********@yahoo.com"
<la********@yahoo.comwrote:

>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

>}

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[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.

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