About qsort () in C, the difference between ** buf and buf [] []

Question

When I use qsort () in C on my Mac, this code works well, it can sort all the lines in one file.

int compare(const void *p, const void *q) { return strcmp(p,q); } void function_name(){ char buf[1024][1024]; int i=0; FILE * fp; if(!(fp=fopen(filename,"r"))){ perror("Open error!"); exit(0); } while(fgets(buf[i],1024,fp)){ //printf("%s",buf[i]); i++; } qsort(buf, i, sizeof(buf[0]), compare); } 

However, when I use malloc to assign space, it sucks. Why is this? In the code below, I use malloc to create one two-dimensional array. I print the contents of the buffer before and after. All information seems to be losing.

  int i=0; FILE * fp; char ** buf; buf = (char **)malloc(sizeof(char*)*1024); if(!(fp=fopen(filename,"r"))){ perror("Open error!"); exit(0); } buf[0]=(char *)malloc(sizeof(char)*1024); while(fgets(buf[i],1024,fp)){ i++; buf[i]=(char *)malloc(sizeof(char)*1024); } for(int j=0;j<i;j++){ printf("%s",buf[j]); } printf("hehe%ld\n",sizeof(char)*1024); qsort(buf, i, sizeof(char)*1024, compare); printf("hehe\n"); for(int j=0;j<i;j++){ printf("%s",buf[j]); } 

exit:

 a A b c d D C E e B d e f a hehe1024 hehe (null)(null)(null)(null)(null)(null)(null)(null)(null)(null)(null)(null)(null)(null)(null)(null) 

Most importantly, how to fix my version of malloc?

Answer 1

When you try qsort buf declared as char **buf , you are using the wrong compare function. As I noted in the comment, char buf[x][y] is an array of arrays of characters x characters y characters, for example. char (*)[y] when passed as a parameter. When you declare buf as char **buf; , you are pointing to a pointer to a type char. In any case, you have a pointer to a string, and you must dereference each value passed to qsort with one additional level of indirection. For example.

 int cmpstrings (const void *a, const void *b) { return strcmp (*(char * const *)a, *(char * const *)b); } 

A short example using char **buf; :

 #include <stdio.h> #include <stdlib.h> #include <string.h> /* qsort string comparison - for pointer to pointer to char */ int cmpstrings (const void *a, const void *b) { return strcmp (*(char * const *)a, *(char * const *)b); } int main (void) { char *ap[] = { "This is a tale", "of captian Jack Sparrow", "a pirate so brave", "on the seven seas." }, **buf = NULL; int n = sizeof ap/sizeof *ap; if (!(buf = malloc (n * sizeof *buf))) { /* allocate pointers */ fprintf (stderr, "error: virtual memory exhausted.\n"); return 1; } for (int i = 0; i < n; i++) buf[i] = strdup (ap[i]); /* allocate/copy strings */ qsort (buf, n, sizeof *buf, cmpstrings); for (int i = 0; i < n; i++) { /* print and free */ printf ("buf[%d] : %s\n", i, buf[i]); free (buf[i]); } free (buf); return 0; } 

Example

 $ ./bin/qsortptp buf[0] : This is a tale buf[1] : a pirate so brave buf[2] : of captian Jack Sparrow buf[3] : on the seven seas. 

Answer 2

qsort , memcpy and similar functions assume that the pointer passed points in the array. The definition of an array itself is the number of elements allocated contiguously in adjacent memory cells. For example char array [x][y]; .

There is widespread confusion about the use of pointers to pointers. There is an old trick that you can use to declare a lookup table, where each element points to a variable-length array that looks like this:

 char** ptr = malloc(x * sizeof(char*)); for(int i=0; i<x; i++) { ptr[i] = malloc(y * sizeof(char)); } 

This allows access to a lookup table with the syntax of an array type, ptr[i][j] . But this does not mean that it is an array, there is no relation to a pointer to a pointer and a 2D array! It is rather x number of segments where each segment is allocated anywhere on the heap.

The only reason you have ever used the aforementioned pointer pointer trick is when you must have a variable length for each element in the lookup table. If you do not need this, then the method described above is bad and always wrong - it is much slower than a real array, both in terms of cost allocation, heap fragmentation, and with a bad data cache. And as you discovered, it cannot even be used as an array ... because it is not alone.

Now, unfortunately, numerous incompetent potential gurus all over the world are incorrectly teaching the above as a way to distribute a multidimensional array dynamically. This is complete stupidity. It is not a multidimensional array and cannot be used as one. See this for an explanation of how you should actually distribute multidimensional arrays dynamically.