CODEWITHSUNDEEP
csyntaxqsort
Corry Chapman
Corry Chapman

Reputation: 167

Explain line of C code in qsort

I've been looking at different implementations of qsort, and there's a line in the source found here (https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html) that I don't understand. It looks like a function pointer declaration. I'd appreciate any help. I've included as much code as necessary (with the line noted) to I think answer the question. Please let me know if not, thanks.

typedef struct
{
    char *lo;
    char *hi;

} stack_node;


void _quicksort (void *const pbase, size_t total_elems, size_t size, cmp_t cmp, void *arg)
{

    char *base_ptr = (char *) pbase;

    const size_t max_thresh = 4 * size;

    if (total_elems == 0)

        return;

    if (total_elems > 4)
    {
        char *lo = base_ptr;
        char *hi = &lo[size * (total_elems - 1)];
        stack_node stack[(8 * sizeof(size_t))];
        stack_node *top = stack;

        /* Line below is a function pointer declaration?  Initializes struct? */

        ((void) ((top->lo = (((void*)0))), (top->hi = (((void*)0))), ++top));

        while ((stack < top))
        {
            char *left_ptr;
            char *right_ptr;

            char *mid = lo + size * ((hi - lo) / size >> 1);

... code goes on

Upvotes: 4

Views: 185

Answers (2)

Ahmed Masud
Ahmed Masud

Reputation: 22402

Looking at the URL we discover that the line is actually a macro definition in particular 

/* The next 4 #defines implement a very fast in-line stack abstraction. */
/* The stack needs log (total_elements) entries (we could even subtract
   log(MAX_THRESH)).  Since total_elements has type size_t, we get as
   upper bound for log (total_elements):
   bits per byte (CHAR_BIT) * sizeof(size_t).  */

#define STACK_SIZE        (CHAR_BIT * sizeof(size_t))
#define PUSH(low, high)   ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
#define POP(low, high)    ((void) (--top, (low = top->lo), (high = top->hi)))
#define STACK_NOT_EMPTY   (stack < top)

and the code actually appears in the definition of PUSH and its compendium appears in POP. The use of extra ()s is to ensure that ++top and --top happen inline and in the correct sequence.

The reason it's implemented this way is clearer when we see the Copyright (C) 1991 - 2017 message at the top of the qsort.c ... Compilers in 1991 were probably really sucky at inlining functions.

Upvotes: 2

AnT stands with Russia
AnT stands with Russia

Reputation: 320671

No, it is not a function pointer declaration. It is just a convoluted way to say

top->lo = 0;
top->hi = 0;
++top;

You can rewrite the above as a single expression statement using , operator

top->lo = 0, top->hi = 0, ++top;

then add unnecessary casts

top->lo = (void *) 0, top->hi = (void *) 0, ++top;

and a bunch of redundant ()s

(top->lo = (((void *) 0))), (top->hi = (((void *) 0))), ++top;

and then cast the whole thing to (void) (say, to suppress any potential compiler warnings about expression result's being "unused")

((void) ((top->lo = (((void *) 0))), (top->hi = (((void *) 0))), ++top));

and now you have your original version.

Why someone decided to use that strange syntax with , operator and massive amount of redundant () is not clear to me. Looks like a macro expansion. Maybe it is a piece of already-preprocessed code? The ((void *) 0) parts might easily be preprocessor replacements for standard NULL macro.

Upvotes: 7

Related Questions