In C, using qsort for dynamically allocated array

ntmsz · 08-22-2005, 12:05 PM

Hello. I am having some problems using qsort on arrays that I allocated dynamically in C.

I have a method which dynamically creates an array from a file strings cointained from a file that looks like this:

Code:

void readinput(){
  int i;
  char buf[80];
  char **input;
  input = (char **)malloc(sizeof(char *) * count);

  for(i=0; i<count; i++){
    input[i] = (char *)malloc(sizeof(char)*80);
    fgets(buf,80,file);
    sscanf(buf,"%s",input[i]);
    printf("input i: %s\n",input[i]);
  }

  qsort(input,count,sizeof(char *),mysortcmp);
}

First it creates input, an array of strings. Next I get the input and assign them all to input. I removed some pieces of code but that's more or less it.

The mysortcmp method looks like this:

Code:

int mysortcmp(a,b)
  char *a, *b;{
  char alow[strlen(a)];
  char blow[strlen(b)];

  strcpy(alow,a);
  strcpy(blow,b);

  strcpy(alow,strlower(alow));
  strcpy(blow,strlower(blow));

  return strcmp(alow,blow);
}

The strlower(char *) function just converts the string to lowercase. Anyway, the problem is, when I put printf("%s\n", a) anywhere in the mysortcmp method, I get garbage data full of symbols instead of the string I want to be compared.

However, if I did not dynamically allocate input, such that the readinput method is like this:

Code:

void readinput(){
  int i;
  char buf[80];
  char input[10][80]

  for(i=0; i<count; i++){
    fgets(buf,80,file);
    sscanf(buf,"%s",input[i]);
    printf("input i: %s\n",input[i]);
  }

  qsort(input,count,(sizeof(char) * 80),mysortcmp);
}

it would work great and there aren't any problems. But I don't think that would really be the solution for me. I was wondering what I should be doing.

Should I
A) Create my own sort algorithm?
B) Use qsort properly for dynamically allocated arrays, if you could please show me how?
C) Do something else?

(And btw, on my

Code:

fgets(buf,80,file);
// sscanf(buf,"%s",input[i]);

I was wondering if there is a better way of doing something similar to fgets without taking along the \n character, but still getting whitespaces.)

Thanks a lot.

itsme86 · 08-22-2005, 12:40 PM

I didn't read all the code, but this is wrong:

Code:

  char alow[strlen(a)];
  char blow[strlen(b)];

  strcpy(alow,a);
  strcpy(blow,b);

To store a string, say "hello", you need 6 elements. One for each character plus the '\0'. However, strlen("hello") only returns 5. So you're not allocating enough memory and your strcpy()'s are overflowing the buffers.

deiussum · 08-22-2005, 01:06 PM

I'm actually kind of surprised that this even compiles:

Code:

  char alow[strlen(a)];
  char blow[strlen(b)];

Creating an array on the stack like this generally requires a constant value for the size. (e.g. a value known at compile time so that the compiler knows the proper amount of memory to allocate on the stack..)

jim mcnamara · 08-22-2005, 03:07 PM

The C99 standard allows for dynamically sized arays in functions other than main() when the size of the array is dictated by an argument.

They are called variable-length arrays. That said, I'm not sure if they work in the context of using strlen().

deiussum · 08-22-2005, 04:48 PM

Quote:

Originally posted by jim mcnamara
The C99 standard allows for dynamically sized arays in functions other than main() when the size of the array is dictated by an argument.

They are called variable-length arrays. That said, I'm not sure if they work in the context of using strlen().

Cool. I learn something new all the time. Has gcc just recently implemented this standard? I don't know that I've ever actually tried to do this in gcc because I knew that you usually need a constant array size on the stack, but I could swear I have seen posts here in the past of people complaining because they got errors from similar code.

As a side note, I just tested it out in gcc/g++ and it seemed to work fine. However, it appears that VC++ .Net 2003 still reports a compiler error. I know that MS has made huge strides in improving ANSI compliance since VC++ 6.0, but evidently this is one area where it still is lacking.

lowpro2k3 · 08-22-2005, 05:04 PM

Quote:

Originally posted by deiussum
As a side note, I just tested it out in gcc/g++ and it seemed to work fine. However, it appears that VC++ .Net 2003 still reports a compiler error. I know that MS has made huge strides in improving ANSI compliance since VC++ 6.0, but evidently this is one area where it still is lacking.

I'm working on a string class in VS.NET and came across the same 'problem'. I am using C++, not C, but I can't use variable length arrays in any of my class methods. Its not really an issue, but I did notice I can't do this:

Code:

char tmp[strlen(class_member)+1];

I have to do this instead:

Code:

char * tmp = new char[strlen(class_member)+1];

Just thought I'd point it out. I didn't really take a look at the main question for the thread, but I wonder if finding the buffer problems helped find the answer?

EDIT: BTW I'm using VS.NET 2002, not 2003 or the newer 2005 beta. They might have fixed it in these versions.

ntmsz · 08-22-2005, 09:50 PM

Let's say I fixed that using char * and then malloc on it, putting printf for a and b (and that is also before using alow and blow) still give me garbage strings. I was wondering if everything else is correct such that the only real problem is that the compiler I'm using does not support dynamically allocated arrays for qsort, or the arguments I used for qsort are incorrect?

deiussum · 08-23-2005, 11:33 AM

I took a brief look at this for you, and after printing out memory addresses it appears that when you use the dynamic array method, qsort is actually sending you a char** to the sorting method. Try the following:

Code:

int mysortcmp(a,b)
  char *a, *b;{
  char alow[strlen(a)];
  char blow[strlen(b)];
  char **pa = (char**)a;
  char **pb = (char**)b;
  
  strcpy(alow,*pa);
  strcpy(blow,*pb);

  strcpy(alow,strlower(alow));
  strcpy(blow,strlower(blow));

  return strcmp(alow,blow);
}

So basically when you call:

Code:

qsort(input,count,x,mysortcmp);

Your mysortcmp gets parameters whose addresses are
input, input + x, input + x*2, .. input + x*(count-1)

Those addresses themselves are just the address locations for another char* in the case where you are using dynamically allocated arrays.

It looks like you probably already understand the fundamental difference between a char** and a char[][], but just in case... The char[][] is all going to be one contiguous block of memory, where as the char** is going to be a pointer to an array of pointers, and thus, the memory for all the underlying char data is not contiguous...