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
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With