qsort seems to change values

Question

I'm stuck with following problem:

int sort_compare(const void *x, const void *y) {
    const int *xi = *(const int **) x;
    const int *yi = *(const int **) y;

    for (int i = 0; i < block_size; i++) {
        comp_x[i] = block[(*xi + i) % block_size];
        comp_y[i] = block[(*yi + i) % block_size];
    }

    return memcmp(comp_x, comp_y, block_size);
}

void sort() {
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
    qsort(to_sort, block_size, sizeof (int), sort_compare);
    for (int i = 0; i < block_size; i++) {
        printf("%d,", to_sort[i]);
    }
    puts("");
}

values:
    block_size = 5;
    block = "jkldj";
    comp_x, compy_y and to_sort are well allocated

output:
    0,1,2,3,4,
    3,0,1785357420,1,1684826986,

to_sort contains the first letter from a (circular) string e.g.

qwer
werq
erqw
rqwe

, represented as (0,1,2,3) needs to be sorted to

erqw
rqwe
qwer
werq

, represented as (2,3,0,1). I seem to get very large numbers, why is that?

Thanks in advance!

Answer 1

qsort() sings by giving it a a linear list of N-items, where any given item(n) address is computable using the based address + size of each 'item'. So start with something simple, and by simple I mean a list of pointers.

First, the circular-ness of the buffer can be emulated by simply splicing a copy onto the original (ideally less-one-char, but I'm not going to quibble about one byte). I.e.

"qwer" ==> "qwerqwer"

This can be done by:

char *buff = malloc(2 * blocksize);
memcpy(buff, to_sort, blocksize);
memcpy(buff+blocksize, to_sort, blocksize);

Now you have offsets 0..(blocksize-1), each of which being a blocksize of chars, that can be compared against one another without any special pointer math.

Next, build the list of pointers to actually sort, in this case,

char** ptrs = malloc(sizeof(char*) * blocksize); 
for (i=0;i<blocksize;i++)
    ptrs[i] = buff+i;

Next, a function that compares two "items". Our items, passed to us by address, are pointers to character strings. Again, the addresses past as left and right are memory locations were we will find two char *. The addresses themselves are not char *:

int block_compare(const void *left, const void *right)
{
    // memcmp would work for most platforms, but not all, so...
    return strncmp(*(char **)left, *(char **)right, blocksize);
}

Finally, send this to qsort() as such:

qsort(ptrs, blocksize, sizeof(char*), block_compare);

The final output will be a blocksize-length list of pointers into the fabricated circular buffer, each of which is referencing a blocksize sized chunk. The full text of everything described above follows:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>

size_t blocksize = 0;

int block_compare(const void *left, const void *right)
{
    // memcmp would work for most platforms, but not all, so...
    return strncmp(*(char **)left, *(char **)right, blocksize);
}


int main(int argc, char* argv[])
{
    char to_sort[] = "qwer";
    size_t i = 0;

    // set blockize
    blocksize = strlen(to_sort);

    char *buff = malloc(2 * blocksize);
    memcpy(buff, to_sort, blocksize);
    memcpy(buff+blocksize, to_sort, blocksize);

    char ** ptrs = malloc(blocksize * sizeof(char*));
    for (i=0;i<blocksize;++i)
        ptrs[i] = buff+i;

    // now send the pointer list to qsort()
    qsort(ptrs, blocksize, sizeof(*ptrs), block_compare);

    // ptrs is sorted. do with it what you will.
    for (i=0;i<blocksize;i++)
    {
        fwrite(ptrs[i], sizeof(char), blocksize, stdout);
        fwrite("\n", sizeof(char), 1, stdout);
    }
    fflush(stdout);

    free(ptrs);
    free(buff);

    return EXIT_SUCCESS;
}

Using "qwer" produces:

erqw
qwer
rqwe
werq

Another sample, using "asubstantiallylongerstringtest"

allylongerstringtestasubstanti
antiallylongerstringtestasubst
asubstantiallylongerstringtest
bstantiallylongerstringtestasu
erstringtestasubstantiallylong
estasubstantiallylongerstringt
gerstringtestasubstantiallylon
gtestasubstantiallylongerstrin
iallylongerstringtestasubstant
ingtestasubstantiallylongerstr
llylongerstringtestasubstantia
longerstringtestasubstantially
lylongerstringtestasubstantial
ngerstringtestasubstantiallylo
ngtestasubstantiallylongerstri
ntiallylongerstringtestasubsta
ongerstringtestasubstantiallyl
ringtestasubstantiallylongerst
rstringtestasubstantiallylonge
stantiallylongerstringtestasub
stasubstantiallylongerstringte
stringtestasubstantiallylonger
substantiallylongerstringtesta
tantiallylongerstringtestasubs
tasubstantiallylongerstringtes
testasubstantiallylongerstring
tiallylongerstringtestasubstan
tringtestasubstantiallylongers
ubstantiallylongerstringtestas
ylongerstringtestasubstantiall

Man I hope that was what you were looking for. (whew).

Answer 2

When you initialise

const int *xi = *(const int **) x;
const int *yi = *(const int **) y;

the address of the element of to_sort is interpreted as a const int**, that is then dereferenced to give the values for xi and yi. That interprets the values in to_sort (and possibly beyond, if int*s are larger than ints) as pointers.

You should just cast the void*s:

const int *xi = (const int *) x;
const int *yi = (const int *) y;

Answer 3

The x and y passed into your comparator are pointers to your array elements. Your array elements are ints, so to get the int values, you need to cast the void pointers into int pointers and dereference. You have an extra layer of indirection in your code, it should really look like this:

int xi = *(const int *) x;
int yi = *(const int *) y;

Then just use xi and yi directly instead of *xi and *yi when doing the data comparison.

As an optimization, there's no need to copy the data into separate arrays and then memcmp them -- you can just compare them yourself in the loop:

for (int i = 0; i < block_size; i++) {
    char data_x = block[(xi + i) % block_size];
    char data_y = block[(yi + i) % block_size];
    if (data_x != data_y)
        return data_x - data_y;
}

return 0;

And as a further optimization, if you double the data in the block array (e.g. so that it has "qwerqwer" instead of just "qwer"), you can do the comparison in a single call to memcmp, since you no longer have to deal with the wraparound. memcmp is heavily optimized, so if you have a lot of data, it can be much faster to use memcmp then a hand-written for loop.