Memory allocation for qsort function

[diguana]

Hy NI
I have a strange problem. I'm a useer of CVI 8. I have problem with correctness of memory allocation. Take a look into this prog.

I read some rows from file FileTemp and sort it by use qsort in DataCheck function.

char **StringTemp;

const int row_length =100, rows =19;  

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

StringTemp = (char **) malloc(rows * row_length* sizeof(char));   //19*100*1

for(i=0;i<rows; i++)  {

*(StringTemp + i) = (char *) malloc(row_length * sizeof(char) );    //100*1

            ReadLine (FileTemp, *(StringTemp+i), row_length);
}

//qsort ( *StringTemp, rows, (row_length * sizeof(char)), DataCheck);  //incorrect

qsort ( *StringTemp, rows, 112, DataCheck);  //correct

return 0;}

First qsort takes to sort operation 100B. When I look into memory allocation I see that each block has 112B, except 100B . Where is a source of this extra 12B  ?

Help me please to figure out this problem.

diguana

[Alex D]

diguana:

I'm not entirely sure I understood your description of the problem you are having, but simply looking at your code, you are using qsort incorrectly.

qsort, by its very nature, sorts elements of an array that are stored contiguously in memory. In your case, you are passing the address of a single string to qsort, which is just wrong. If you were allocating the string storage as a single large memory block, you could do this, but that isn't the case.

The simplest way to change to code to work would be to sort an array of character pointers (which you are allocating, albeit incorrectly) and sort based on the contents of the pointed to memory. That would look something like this:

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

int main (int argc, char *argv[])
{
    int i;
    StringTemp = (char **) malloc(rows * sizeof(char *));
    for (i = 0; i < rows; ++i)
    {
        StringTemp[i] = (char *) malloc(row_length * sizeof(char));
        ReadLine (FileTemp, StringTemp[i], row_length);
    }

    qsort ( StringTemp, rows, sizeof(char *), DataCheck);

    // do something with sorted strings
    
    for (i = 0; i < rows; ++i)
        free(StringTemp[i]);
    free(StringTemp);

    return 0;
}

I should also point out that, since you are always allocating the strings to be the same size, there is no reason to dynamically allocate them. You could simplify this code significantly by changing to a static two-dimensional array.

Hope this helps,

-alex

[diguana@o2.pl]

Hi Alex
Thanks for your response and modyfication but.... a few explanation...and questions
I need to do it dynamically, because all the time the file I read has a different numbers of rows, but the same row's length.
So, static -will be a problem, only one static dimention is possible.
As I see that my program works, the qsort function take to sort all my table and made it correctly - I obtain sorted rows.
Not as you suggested only one row->logically one row can't be sorted...Happily, *Stringtemp and StringTemp at the beginning, point the same place in memory.
I've just asked why allocated blok has 112B expect 100B as I want to reserve. Is the answer: The block have to have multiple of 8bits value ??

The condition I use in sorting function DataCheck is a part of the row includes date and time, example 2007-04-02 12:30 126.192.12.3_12_70. Let me present it:

int DataCheck(const void *arg1, const void *arg2)
{
int  month1, month2, day1, day2, year1, year2, hour1, hour2, min1, min2;
char IPSP1[30],IPSP2[30];
char *Arg1 = (char *)arg1; char *Arg2 = (char *)arg2;
sscanf (Arg1, "%04d-%02d-%02d %02d:%02d %s", &year1, &month1, &day1, &hour1, &min1, IPSP1);
sscanf (Arg2, "%04d-%02d-%02d %02d:%02d %s", &year2, &month2, &day2, &hour2, &min2, IPSP2);
    if (year1 == year2)                        {
            if (month1 == month2)         {
                if (day1 == day2)              {
                    if (hour1 == hour2)       {
                        if (min1 == min2)    return 0;
                         else return (min2 > min1) ? -1 : 1;   }
                    else return (hour2 > hour1) ? -1 : 1;      }
                else return (day2 > day1) ? -1 : 1;             }
            else return (month2 > month1) ? -1 : 1;        }
    else return (year2 > year1) ? -1 : 1;
}
Looks OK.

And last thing, you mention that allocation is made incorrectly.
Your proposal: StringTemp = (char **) malloc(rows * sizeof(char *)) - I agree, like in books
My proposal: StringTemp = (char **) malloc(rows * row_length* sizeof(char));
If I know, what will be a size of a string pointed by char * why I can't to exchange it to this knowledge: row_length* sizeof(char)) ??

I don't know why, but your code doesn't sort my rows, just rearrange it.
Best regards
diguana

[diguana@o2.pl]

Additional thing.
You know Alex, when I change in your code the qsort function from
qsort ( StringTemp, rows, sizeof(char *), DataCheck); //made only row's rearrangement
to
qsort ( *StringTemp, rows, 112, DataCheck);
it works perfect.
Maybe this suggest you where the problem is.
diguana

[Alex D]

Ok. I'm not entirely sure what you mean by "your code doesn't sort my rows, just rearrange it". Do you mean that it rearranges the rows internally, or with respect to each other? If the latter, how does this differ from sorting? Do you just mean it's not sorting them like you want?

Just to see if we can find some common ground, let me tell you about my experience trying to run the code you posted (without modification).

The first error I got was on the ReadLine call:

"Array argument too small (100 bytes).  Argument must contain at least 101 bytes (101 elements)."

This was remedied by changing the second malloc from this:

    *(StringTemp + i) = (char *) malloc(row_length * sizeof(char) );    //100*1

to this:

    *(StringTemp + i) = (char *) malloc((row_length + 1) * sizeof(char) );    //101*1

The second error I received was:

"Array argument too small (101 bytes).  Argument must contain at least 2128 bytes (2128 elements)."

on the line:

    qsort ( *StringTemp, rows, 112, DataCheck);  //correct

I then tried commenting this line out and using the line:

    qsort ( *StringTemp, rows, (row_length * sizeof(char)), DataCheck);  //incorrect

and received the error:

"Array argument too small (101 bytes).  Argument must contain at least 1900 bytes (1900 elements)."

The changes I then made to solve this problem are what I described in my original post.

I changed the first malloc call from this:

    StringTemp = (char **) malloc(rows * row_length* sizeof(char));   //19*100*1

to this:

    StringTemp = (char **) malloc(rows * sizeof(char *));

I changed the qsort call from this:

    qsort ( *StringTemp, rows, 112, DataCheck);  //correct

to this:

    qsort (StringTemp, rows, sizeof(char *), DataCheck);

I changed the DataCheck function from taking (char *) parameters to taking (char **) parameters (because of the change to the qsort call). This changed this:

    char *Arg1 = (char *)arg1; char *Arg2 = (char *)arg2;

to this:

    const char *Arg1 = *(const char **)arg1;
    const char *Arg2 = *(const char **)arg2;

At this point, I created a dummy data file to read in to test the changes. In my tests, the rows are sorted without issue. I then changed your DataCheck function to the function I posted in my original post (just calling strcmp). The results were the same. The reason for this is that the date string is presented in order of decreasing significance (year, month, day, hour, minute, etc.). This means that a textual sort will do the same thing as the complicated comparison you were doing in DataCheck.

I am attaching a project which contains my code and yours so you can test it for yourself.

It is possible you have some other code that is causing the problem you originally posted about (the 100 vs 112 problem) but I could never reproduce that issue, and I can't think of any reason that it would happen. It is possible that the issue you are seeing is limited to a specific version of CVI; which version are you using?

At any rate, try the project I attached and let me know how it goes.

Regards,

-alex

[diguana]

Alex
You had got some errors because wrong first memory allocation.  I saw it a few versions before.
This is my code which works perfect. I was testing it in many cases.
I lost the same DataCheck function.

StringTemp = (char **) malloc(rows * sizeof(char *));
            for(i=0;i<rows; i++) {
                *(StringTemp + i) = (char *) malloc(row_length * sizeof(char) );                
                ReadLine (FileTemp, *(StringTemp+i), row_length);
                strcat( *(StringTemp+i), "\0" );
            }
            qsort ( *StringTemp, rows, 112, DataCheck);   

The question is still the same, why I have to put 112 except (row_lenght+1) ??

But leave it, your code is more professional and understandable, let me use it in my program.
You noticed the way how to simplify the DateCheck - very simple, very good idea.
I have started to use  CVI 8.01, so probably I’ll find new problems soon.
Thanks for you fruitful help.
diguana