In plain C, pointers to void are useful as arguments to generic functions, such as a generic quicksort, or a generic swap, etc., as seen here:

Implementation of generic quicksort, etc.

However, as the example of the generic partition function at that link shows:

size_t generic_partition(void *v, size_t nelems, size_t size, compare_function comp)
{
    // for brevity we'll be using the right-most 'element' for the 
    //  location of the pivot storage. a better choice would use
    //  a median-of-three or median-of-five for pivot selection,
    //  then swap it to that location before the partitioning loop.
    
    void *ploc = (unsigned char*)v   (nelems-1) * size;
    size_t pvt = 0;

    for (size_t i=0; i<nelems;   i)
    {
        if (comp((unsigned char*)v   (i*size), ploc) < 0)
            generic_swap((unsigned char*)v   (pvt  *size), (unsigned char*)v   (i*size), size);
    }

    generic_swap((unsigned char*)v   (pvt*size), ploc, size);

    return pvt;
}

it can be quite heavy on the pointer arithmetic and type casting, inside a loop. The reason seems to be that we must frequently cast between void* and char*, because char* supports pointer arithmetic, while void* does not (because the element size is unknown).

So why don't we use char* instead of void*, to implement generic arguments to generic functions ? It seems to have the advantages of void* (generality, since doesn't every type occupy some integer multiple of one byte ?) with the additional advantage of supporting pointer arithmetic.

Using pointers to char only, without pointers to void, wouldn't the loop in the above code require fewer additions, no multiplications, and no type casts ? If so, then wouldn't that be more efficient ?

Perhaps I am missing something to do with functions like "comp" automatically converting the arguments passed to them into the expected type ?

Perhaps I am missing the point generally.

EDIT (To include code for generic_swap):

void generic_swap(void *a, void *b, size_t size)
{
    if (a == b)
        return;

    unsigned char *p1 = a, *p2 = b;
    while (size-- > 0)
    {
        unsigned char c = *p1;
        *p1   = *p2;
        *p2   = c;
    }
}

EDIT - This is what I meant by avoiding multiplications (for what it's worth). I've written it as a modification of dbush's nice answer:

size_t generic_partition(void *v, size_t nelems, size_t size, compare_function comp)
{
    // for brevity we'll be using the right-most 'element' for the 
    //  location of the pivot storage. a better choice would use
    //  a median-of-three or median-of-five for pivot selection,
    //  then swap it to that location before the partitioning loop.
    
    unsigned char *pboundary = v;
    unsigned char *ploc = pboundary   (nelems-1) * size;
    size_t pvt = 0;

    unsigned char *pcurrent = pboundary   size;

    while (pcurrent < ploc)
    {
        if (comp(pcurrent, ploc) < 0)
        {
            generic_swap(pboundary, pcurrent, size);
            pboundary = pboundary   size;
            pvt  ;
        }
        pcurrent = pcurrent   size;
    }

    generic_swap(pboundary, ploc, size);

    return pvt;
}

CodePudding user response：

Conversions to and from void * can occur without a cast and are guaranteed to work for any object type.

You can actually eliminate the casting by assigning the void * argument to a unsigned char * once, then using that in the rest of the function:

size_t generic_partition(void *v, size_t nelems, size_t size, compare_function comp)
{
    // for brevity we'll be using the right-most 'element' for the 
    //  location of the pivot storage. a better choice would use
    //  a median-of-three or median-of-five for pivot selection,
    //  then swap it to that location before the partitioning loop.
    
    unsigned char *pstart = v;
    unsigned char *ploc = pstart   (nelems-1) * size;
    size_t pvt = 0;

    for (size_t i=0; i<nelems;   i)
    {
        if (comp(pstart    (i*size), ploc) < 0)
            generic_swap(pstart   (pvt  *size), pstart   (i*size), size);
    }

    generic_swap(pstart   (pvt*size), ploc, size);

    return pvt;
}

Note that you still have to multiply by the element size when constructing the pointers.