Can someone explain to me this code from K&R's 'The C Programming Language' book?

frankie_DJ · 11-07-2006, 02:28 PM

Hi everyone,

The following is a code from K&R 'The C Programming Language' and I
can't seem to figure out what is going on. The program is supposed to do a job similar to the unix command sort: it should sort the lines of the input text lexicographicaly or numericaly, based on user's choice.

Code:

#include <stdio.h>
#include <string.h>

#define MAXLINES 5000 /*max #lines to be sorted */
char *linesptr[MAXLINES]; /*pointers to text lines */


int readlines(char *linesptr[],int nlines);
void writelines(char *linesptr[], int nlines);

//these two functions are written elsewhere and I understand
//what they do: readlines stores all the input lines in one big
 //char array and put the pointer (member of linesptr array) at 
//beginning of each; writelines just prints out these lines

void qsort(void *linesptr[],int left, int right, 
int (*comp)(void *, void *));

//this is a sorting procedure which I also understand; the whole 
//point is to illustrate pointers to the functions - user can 
//pick either numerical or lexicographical comparision and use 
//that as a *comp function in the sorting algorithm

main(int argc, char *argv[])
{
int nlines; /* number of input lines read */
int numeric=0; //1 if numeric sort

if (argc>1 && strcmp(argv[1], "-n")==0)
numeric==1;

if ((nlines=readlines(linesptr,MAXLINES))>=0)
{

//THE FOLLOWING LINE IS WHAT I CANNOT UNDERSTAND!
qsort((void **) linesptr, 0,nlines-1,(int (*)(void*,void*))(numeric?numcmp:strcmp));
//WHAT IS (VOID **) DOING? IS IT CASTING LINESPTR? WHY TWO STARS?
//ALSO what is int (*)? WHY NOT int (*comp)?


writelines(linesptr,nlines);
return 0;
}
else
{
printf("input too big to sort\n");
return 1;
}
}

I have been looking at this code for couple of days now, and I just can't figure out what these constructs do. Any help would be appreciated. Ask if you need more clarification of what is the code supposed to do. Thanks

jim mcnamara · 11-07-2006, 03:40 PM

Code:

qsort((void **) linesptr, 0,nlines-1,(int (*)(void*,void*))(numeric?numcmp:strcmp));

linesptr is a pointer to a pointer so it is void**

soggycornflake · 11-07-2006, 03:44 PM

Quote:

//WHAT IS (VOID **) DOING? IS IT CASTING LINESPTR? WHY TWO STARS?

If a function takes a void*, then you can pass any pointer to it and it will be automatically cast to void (assuming an ANSI C compiler). However, casting is not recursive. A char** (which is what linesptr is) will not be automatically cast to a void**, hence the cast. See the C usenet FAQ for more details on this.

Quote:

//ALSO what is int (*)? WHY NOT int (*comp)?

This is a function type, the name of the function is not relevant here.

A typedef would make this clearer, e.g.

Code:

typedef int (*CmpFunc)(void *, void*);
CmdFunc comp;

qsort((void **) linesptr, 0,nlines-1, (CmpFunc)(numeric?numcmp:strcmp));

95se · 11-07-2006, 03:48 PM

OK,

int (*comp)(void *, void *));

This isn't actually a "function," but a pointer to a function. One that is apparently never set to anything, and never used ?

(int (*)(void*,void*))(numeric?numcmp:strcmp)
This is just casting either the function numcmp or strcmp (if numeric is true or false respectively) to one that has the signiture int (*)(void*,void*). This is needed, because if strcmp is defined like this, int strcmp(const char *, const char *), then the compiler will give, at least, a warning, and may be an error. And, for all I know, numcmp is defined like this, int numcmp(int *, int *).

frankie_DJ · 11-07-2006, 11:45 PM

thank you guys. but I still don't understand why two stars. Function would normaly be called with

qsort(linesptr,left,right, numcp)

If I want to cast linesptr, shouldn't I do

qsort((void *) linesptr,left,right,numcp)

?

Wim Sturkenboom · 11-08-2006, 02:47 AM

You are correct that you normally would pass lineptr. However. qsort wants an array of pointers to void, hence the casting.

When you cast, you must cast to the same 'type'; as lineptr is an array (the first pointer) of pointers (the second pointer) to character strings, you need to cast to array of pointers and hence the two stars in the cast.

frankie_DJ · 11-08-2006, 05:33 AM

OK, so does that mean that
qsort((void *) linesptr[],...)
would also be correct?

bigearsbilly · 11-08-2006, 11:08 AM

use ddd (debugger)
have a look, step through, examine, you may find it useful
in understanding.

Hko · 11-08-2006, 11:24 AM

Quote:

Originally Posted by frankie_DJ

OK, so does that mean that
qsort((void *) linesptr[],...)
would also be correct?

Though I remember there are subtle differences between "char *str[]" and "char **str", in this case it would probably be equivalent. (I just don't remember what those subtle differences really are).

soggycornflake · 11-09-2006, 09:44 AM

Quote:

Originally Posted by Hko

Though I remember there are subtle differences between "char *str[]" and "char **str", in this case it would probably be equivalent. (I just don't remember what those subtle differences really are).

Technically, they are different types, the former is a pointer to an array of characters, while the latter is a pointer to a pointer to a char. However, since a pointer to an array decays into a pointer to the first element, they are equivalent in practice. (Thus, one may use either e.g. 'int main(int argc, char *argv[])' or 'int main(int argc, char **argv)' without incident.)

Hko · 11-25-2006, 01:35 PM

Quote:

Originally Posted by soggycornflake

Technically, they are different types, the former is a pointer to an array of characters, while the latter is a pointer to a pointer to a char. However, since a pointer to an array decays into a pointer to the first element, they are equivalent in practice. (Thus, one may use either e.g. 'int main(int argc, char *argv[])' or 'int main(int argc, char **argv)' without incident.)

Thanks. Now I also remember one of the implications of this difference. Like it's not possible to initialize a pointer to a pointer to a char, but an array of pointers to a char (array of strings) can be initialized with constant strings:

This is OK:

Code:

char *str_arr[] = {"one", "two"};

But this is not:

Code:

 char **str_arr = {"one", "two"};