[solved] qsort() returns garbage

[Caitlin]

I'm trying to use qsort() to sort a table with 5 entries in it (room for 100) in a program. I've verified that the data in the table is valid when I call qsort(), but afterwards, there is nothing but trash there.

I'm programming in C using gcc. I've used qsort() successfully many times before under Turbo C, but this is the first time for gcc.

One difference is that Turbo C uses 2-byte short ints, but gcc uses 4-byte short ints. I thought gcc might be inserting slack bytes in the ELEMEN structure, but I added the ((packed)) attribute and this did not fix the problem.

Perhaps my call to the qsort() function is wrong. This particular problem is not mentioned on the internet. I checked the syntax of the call to qsort() there and it seems to be correct. There's nothing else to check there.

I'm including (what I believe to be) the relevant portions of my program. Let me know if you need anything else.

Code: Select all

#include <stdlib.h>                                                           /* 5 */


#define NOSLACK __attribute__((packed))
                                   /* don't insert slack bytes (comp without sync) */
                                                                             /* 10 */
#define TABWIDTH 200
                    /* width of table of tasks, prereqs, and postreqs (task table) */
                                                                             /* 41 */

#define TABSIZE 100
                                                /* number of entries in task table */

#define FIXED 3 * sizeof(short int) + 2 * sizeof(char)
                                     /* size of fixed-length portion of task table */

struct ELEMEN                                                                /* 59 */
   {short int tasknum;     /* task number of THIS task (excluding any step number) */
    char stepnum;                               /* step number (first = 'a', etc.) */
    char flags;                                   /* flags pertaining to this task */
    short int numpre;                           /* number of prereqs this task has */
    short int numpost;                         /* number of postreqs this task has */
    short int prereqs[0];        /* table of prerequisites (omitted if numpre = 0) */
    short int postreqs[0];     /* table of postrequisites (omitted if numpost = 0) */
    char fragment[TABWIDTH                /* fragment of the description; the max- */
     - FIXED];};                          /* imum that will fit (with zero byte)   */
                   /* the lengths of all the above fields should total to TABWIDTH */
                                                                             /* 70 */
struct GLOBALS                                    /* some global variables follow: */
   {NOSLACK struct ELEMEN cactus[TABSIZE];
    . . .
    char workarea[600];} g;                                        /* input buffer */

    int e35(const void*, const void*);
    
    qsort(&g.cactus, g.numelem, TABWIDTH, e35);         /* sort cactus using e35() */

int e35(const void* elem1, const void* elem2)
   {return (((const struct ELEMEN*)elem1)-> tasknum
     > ((const struct ELEMEN*)elem2)-> tasknum)                             /* 395 */
     - (((const struct ELEMEN*)elem1)-> tasknum
     < ((const struct ELEMEN*)elem2)-> tasknum);};

[LE_746F6D617A7A69]

A trivial bug: You're passing incorrect size of element to qsort(): it should be sizeof(struct ELEMEN), not TABWIDTH

[Caitlin]

I'll try it but struct ELEMEN was designed to be TABWIDTH bytes long.

Caitlin

[LE_746F6D617A7A69]

I'll try it but struct ELEMEN was designed to be TABWIDTH bytes long.

If this was Your intention, then take a look at the formula for symbol "FIXED": it's definitely incorrect.

EDIT: OK, now I have some more time to explain what have happened:
The formula (3 * sizeof(short int) + 2 * sizeof(char)) is incorrect, because it does not take into account the data alignment, and it gives an offset of 8 bytes, while for the default 4-byte alignment the offset is 20 bytes. In the effect, the total struct size is 200-8+20=212 bytes, not 200 -> so qsort() will work with sizeof(struct), but not with TABWIDTH=200.

However, the root cause of the problem is in incorrect usage of the packed attribute (NOSLACK symbol): attributes are working with declarations of structures/functions, not with implementation.

Nevertheless, You should avoid using 'packed' attribute if it's only possible - it can cause dramatic performance loss and generates sub-optimal code if the structure is not manually optimized for packing. In Your case, this is easy:

Code: Select all

#define TABWIDTH 200
typedef struct {
    short int tasknum;   
    char stepnum;                          
    char flags;                                
    short int numpre;                        
    short int numpost;                      
    short int prereqs[0];      
    short int postreqs[0];
} header_struct;

struct ELEMEN {
    header_s hdr;
    char fragment[TABWIDTH - sizeof(header_struct)];
};

[Caitlin]

Right you were, LE_746F6D617A7A69, the problem was in FIXED. I Added a pair of parentheses and now it works.

From: #define FIXED 3 * sizeof(short int) + 2 * sizeof(char)

To: #define FIXED (3 * sizeof(short int) + 2 * sizeof(char))

I effectively changed the sign of the last part. Here's how the calculation goes:

Tasknum, stepnum, flags, numpre, and numpost: 14 bytes (with 4-byte short ints), equal to the value of FIXED.
Prereqs[0] and postreqs[0]: 0 bytes.
Fragment: TABWIDTH (200) - FIXED (14) = 186 bytes.
Total size: TABWIDTH.

But that's not the whole story. Prereqs[0] is a table that can contain one or more entries, which "occurs depending on numpre". (Bonus points if you know what language the quoted part is.) Same for postreqs[0]. While the structure declaration shows no room in the prereqs/postreqs tables, they grow as needed. The extra needed is taken away from fragment, so the full structure size is always TABWIDTH.

Also, I figured I might have alignment problems. Turbo C, with its two-byte short ints, does line up because stepnum and flags together take up two bytes -- keeping everything following two-byte aligned. (I tried ((packed)) but it doesn't seem to be necessary.) If it does become a problem, I can move stepnum and flags to the end of the structure and make sure TABWIDTH is a multiple of 8.

Anyway, thanks for your help!

Caitlin

[LE_746F6D617A7A69]

#define FIXED (3 * sizeof(short int) + 2 * sizeof(char))

There's one problem: the above formula gives 8, not 14, and the explanation is rather different:
I've just checked, that gcc v8.3 is not using the default 4-byte alignment for this structure, (so it behaves a little bit different than some older versions), and the code works only thanks to this fact.
I.e. this is just a matter of luck, compiler version/flags used

Obviously, in this situation, the (packed) attribute does nothing, but it should be used to avoid surprises in the future.
Alternatively, You could use a separate header structure to reliably calculate the size.