C++ qsort array of pointers not sorting

Question

Hi,

I am trying to sort a buffer full of variable-length records alphabetically in C++. I previously asked how to implement this, and was told to sort an array of pointers to the records. I set up an array of pointers, but realized that each pointer points to the beginning of a record, but there is no way of it knowing when the record stops. When I try to print out the record pointed to by each pointer in the array, therefore, for each pointer, I get the entire buffer of all records, starting from the one pointed to. (For example, if the buffer holds "Helloworld", and there is a pointer at each letter, printing the array of pointers would produce "Helloworldelloworldlloworldloworldoworldworldorldrldldd".) Obviously, this is not what I want; also, the qsort does not seem to be working on the array of pointers either. When I debug, the memory spaces pointed to by the pointers seem to hold very odd characters that are definitely not part of the ascii character set and were not included in my input file. I am very confused. Below is my code; how can I do this without getting the odd results I get now? Thank you so much, bsg.

int _tmain(int argc, _TCHAR* argv[])
{
    //allocate memory for the buffer
    buff = (unsigned char *) malloc(2048);
    realbuff = (unsigned char *) malloc(NUM_RECORDS * RECORD_SIZE);

fp = fopen("postings0.txt", "r");
        if(fp)
        {
            fread(buff, 1, 2048, fp);
            /*for(int i=0; i <30; i++)
                cout << buff[i] <<endl;*/

            int y=0;

 //create a pointer to an array of unsigned char pointers
    unsigned char *pointerarray[NUM_RECORDS];
    //point the first pointer in the pointer array to the first record in the buffer
            pointerarray[0] = &buff[0];
            int recordcounter = 1;  



        //iterate through each character in the buffer; 
    //if the character  is a line feed (denoting a new record),
// point the next pointer in the pointer array to the next 
//character in the buffer (that is, the start of the next record)
                for(int i=0;i <2048; i++)
            {
                if(buff[i] == char(10))
                {
                    pointerarray[recordcounter] = &buff[i+1];
                    recordcounter++;
                }


    }

//the actual qsort (NUM_RECORDS is a constant declared above; omitted here)
    qsort(pointerarray, NUM_RECORDS, sizeof(char*), comparator);

        }

        else 
            cout << "sorry";

        cout << sizeof(pointerarray)/sizeof(char*);
    for(int k=0; k < sizeof(pointerarray)/sizeof(char*);k++)
    {
        cout << pointerarray[k];
    }

int comparator(const void * elem1, const void * elem2)
{

    //iterate through the length of the first string
    while(*firstString != char(10))
    {
        return(strcmp(firstString, secondString));

                firstString++;
        secondString++;

        /       
    }
return 0;
    }

Answer 1

I'm guessing the problem is in your comparator function (which doesn't compile as posted). qsort gives a pointer to the array element to the comparator function. In your case that would be a pointer to the char* stored in the array.

The man page for qsort gives this example:

static int
cmpstringp(const void *p1, const void *p2)
{
    /* The actual arguments to this function are "pointers to
      pointers to char", but strcmp(3) arguments are "pointers
       to char", hence the following cast plus dereference */

    return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int
main(int argc, char *argv[])
{
    int j;

    assert(argc > 1);

    qsort(&argv[1], argc - 1, sizeof(char *), cmpstringp);

    for (j = 1; j < argc; j++)
        puts(argv[j]);
    exit(EXIT_SUCCESS);
}

Answer 2

This question basically comes down to 'how do you know the length of your variable-length record.' There needs to be some way to tell, either from the record itself, or from some other data.

One way is to use pointer/length pairs to refer to records -- a pointer to the beginning of the record and a length (int or size_t), which you store together in a struct. With C++ you can use std::pair, or with C define a litte struct. You can then use qsort on an array of these.

In your case, you can tell the length by looking for a char(10), as you always use them to terminate your strings. You need a custom comparison (strcmp won't work -- it expects NUL terminators) that is aware of this.