Problems with realloc()

L

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 = (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 = rand() % MAX;
printf("%d ", x);
}
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,0,length-1);

printf("Sorted:\n");
for(i = 0 ; i < size ; i++)
{
for (j = 0 ; j < length ; j++)
printf("%d ", a[j]);
}
printf("\n");

for (i = 0 ; i < length ; i++)
free(a);
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
 
B

Barry

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 = (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 = rand() % MAX;
printf("%d ", x);
}
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];
Click to expand...


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,0,length-1);

printf("Sorted:\n");
for(i = 0 ; i < size ; i++)
{
for (j = 0 ; j < length ; j++)
printf("%d ", a[j]);
}
printf("\n");

for (i = 0 ; i < length ; i++)
free(a);
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
Click to expand...
 
D

DingDong

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 = (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 = rand() % MAX;
printf("%d ", x);
}
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,0,length-1);

printf("Sorted:\n");
for(i = 0 ; i < size ; i++)
{
for (j = 0 ; j < length ; j++)
printf("%d ", a[j]);
}
printf("\n");

for (i = 0 ; i < length ; i++)
free(a);
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
Click to expand...


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

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

pete

length[] is the number of each row in matrix a.
Click to expand...
I meant to say length[] is the number of integers in each row of
matrix a.
Click to expand...

/* 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 = NULL;
length = 0;
}
puts("Original: ");
for (i = 0 ; i < N ; i++) {
x = rand() % MAX;
printf("%2d ", x);
}
puts("\n");
for (j = 0 ; j < N ; j++) {
i = SIZE;
while (i-- > 0) {
if (x[j] / (double)MAX >= i / (double)SIZE) {
++length;
temp = realloc(a, length * sizeof *temp);
if (temp == NULL) {
puts("ERROR: realloc failed");
exit(EXIT_FAILURE);
}
a = temp;
a[length - 1] = x[j];
break;
}
}
}
for (i = 0 ; i < SIZE ; i++) {
quicksort(a, 0, length - 1);
}
puts("Sorted:");
for (i = 0 ; i < SIZE ; i++) {
printf("a[%d] ", i);
for (j = 0 ; j < length ; j++) {
printf("%2d ", a[j]);
}
putchar('\n');
}
free_int_2d(a, length);
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);
}
free(a);
}

/* END new.c */
 
P

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 */
Click to expand...
int main(void)
{
int i, j, *length, x[N], **a, *temp;
Click to expand...
for (i = 0 ; i < SIZE ; i++) {
printf("a[%d] ", i);
for (j = 0 ; j < length ; j++) {
printf("%2d ", a[j]);
}
putchar('\n');
}
free_int_2d(a, length);
Click to expand...


Oops!
The above line of code should be

free_int_2d(a, SIZE);

instead.
free(length);
return 0;
}
Click to expand...
void free_int_2d(int **a, int i)
{
while (i-- > 0) {
free(a);
}
free(a);
}
Click to expand...
 
B

Barry Schwarz

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)
Click to expand...

snip unrelated function
}

int main()
{
int i, j, *length, x[N], **a, *temp;
srand(time(NULL));

a = (int **)malloc(size * sizeof(int*));
Click to expand...

Don't cast the return from malloc. It only serves to hide undefined
behavior.
for (i = 0 ; i < size ; i++)
a = (int*)malloc((N/size + 1) * sizeof(int));
Click to expand...


Are you sure that all groups will have the same number of elements?
length = (int *)malloc(size * sizeof(int));
Click to expand...

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 = rand() % MAX;
printf("%d ", x);
}
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)
Click to expand...


You only need one cast in each division expression.
{
a[i-1][length[i-1]] = x[j];
Click to expand...

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)
Click to expand...

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,0,length-1);

printf("Sorted:\n");
for(i = 0 ; i < size ; i++)
{
for (j = 0 ; j < length ; j++)
printf("%d ", a[j]);
}
printf("\n");

for (i = 0 ; i < length ; i++)
Click to expand...


This is wrong. i should run from 0 to size. Each a does point to
length int but you only free the a, 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);
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.
Click to expand...




Remove del for email
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Fibonacci 0
Could you fix my code please? (i get no output after inputing the number) 1
strange behaviour of realloc() 3
C program: memory leak/ segmentation fault/ memory limit exceeded 0
Segmentation fault using realloc() 5
Need Help: Program to Accept 2 Matrices and Show their Sum 0
SENTINEL CONTROL LOOP WHEN DEALING WITH TWO ARRAYS 1
A process take input from /proc/<pid>/fd/0, but won't process it 0

Members online

Total: 42 (members: 1, guests: 41)
Robots: 358

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,058
Latest member
QQXCharlot

Latest Threads

Top