By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
431,827 Members | 2,155 Online
Bytes IT Community
+ 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 <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

Jul 22 '07 #1
Share this Question
Share on Google+
7 Replies


P: n/a

<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

Jul 22 '07 #2

P: n/a
On Jul 22, 2:38 pm, "lancer6...@yahoo.com" <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 <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 [].

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

Jul 22 '07 #4

P: n/a
On Jul 22, 11:10 pm, "lancer6...@yahoo.com" <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" <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 <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
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"
<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
Jul 22 '07 #8

This discussion thread is closed

Replies have been disabled for this discussion.