Managing an array of indeterminate type with void pointers

Question

I'm trying to write my own Mergesort function in the same fashion as C's qsort function. If I were writing MergeSort for an array of known items, I wouldn't have a problem, but since I don't know what they'll be it's throwing me for a loop.

The specification given by my professor didn't want me to use a separate function for merging, so I'm writing that implementation inside the Mergesort function itself. That means I'll have the same information qsort() would have:

• void* base - a pointer to the first element of the array to be sorted
• size_t nel - the number of elements in the array
• size_t width - the size of each element
• int (*compar)( const void*, const void* ) - a function that tells you how to compare each element

The problem I'm having is with the Merge part. Every implementation I've seen has used a temporary array to store items while they're sorted. I'm not that used to working with void pointers, and the biggest obstacle I've found is moving through and assigning values into arrays. How would I find the value at the second index in the array pointed to by base? How could I assign a value from that array into a temporary array? How would I create that temporary array?

Would it work if I casted the void pointers to char, and just incremented them by the width? I'm not sure how assignment would work, though.

Answer 1

How would I find the value at the second index in the array pointed to by base? Would it work if I casted the void pointers to char, and just incremented them by the width?

Yes, that's right. The size of a char is defined by the standard to be 1, so the "width" you're given is, by definition, the size of each element in chars. So you can find the address as follows:

void *second_element_ptr = ((char*)base) + width;

You can't find the value, because you don't know its type and so you can't make sense of the memory it occupies. But that's OK, to sort objects in C with this interface you don't need to know their values: you need pointers to them, which you can pass to the comparator function, and you need to be able to copy objects around.

How could I assign a value from that array into a temporary array?

char temporary_array[width]; // this is a C99 VLA, you might want to 
                             // allocate the array differently
memcpy(temporary_array, second_element_ptr, width);

How would I create that temporary array?

Oh, I guess I took these questions in the wrong order. For a small array containing a single element, you could take a chance on a VLA. Or you could use malloc as follows:

// an array half the size of the input
// using char*, since unlike void* we can do arithmetic on it
char *big_temp_array = malloc(width * (nel + 1)/2);

Btw, gcc supports arithmetic on void* as a compiler extension, treating it like arithmetic on char*. Up to you to decide whether you can/will use this.

Answer 2

How would I find the value at the second index in the array pointed to by base?

Use (char *)base + (width*i). This will give you the address of the i-th element.

How could I assign a value from that array into a temporary array?

You just copy the data. for (int n=0;n<width;n++) { //copy one byte from }

How would I create the temporary array?

Something like:

c - void* tempArray = malloc(width*elementsNeeded);

c++ - void* tempArray = (void*) (new char[width*elementsNeeded]);

EDIT:

To explain copying data a little further, you need to do:

for (int n=0;n<width;n++) {
  adressTo[n] = addressFrom[n];
}
// This will copy the contents of pointer addressFrom to addressTo.