CODEWITHSUNDEEP
void-pointers
user2883993
user2883993

Reputation:

How can I merge two arrays declared as void pointers?

I currently have I program I am writing where I am implementing a Mergesort of an array. The array is of unknown variables--it is a void pointer, so I don't actually know what sort of objects I'm sorting (there is a comparison function passed in for the actual comparisons).

How can I traverse the array when it is a void pointer? I've learned that I can't just use typical array format (i.e. arr[3]) since it is a void pointer. There IS a parameter passed into my functions that holds the size of the mystery elements, so I suppose I would need that. Is there a way I could cast it depending on the provided size so I COULD use that typical array format, or do I have to use pointer arithmetic (again, having to somehow cast it to something of the provided size)?

Thanks to anyone who provides some input! :)

Upvotes: 4

Views: 627

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

There IS a parameter passed into my functions that holds the size of the mystery elements

Good - that is precisely what you need to do the pointer arithmetic right. This is the same approach that qsort library function is using.

void merge_sort(void *array, size_t N, size_t size, int (*compare)(const void *, const void *));

Once you cast the void* pointer to a char*, you would be able to compute the location of the mystery element i as follows:

size_t size; // Element size
void *array; // The address of the array
size_t N;    // Count of elements in the array
char *base = array;
for (int i = 0 ; i != N ; i++) {
    void *elementAtPositionI = &base[i * size];
    ...
}

To find the point at which you split the array for sorting separately you can use the same technique:

void *secondHalf = &base[N * size / 2];

I can't quite get it to work though... it seems as if I'm skipping values and going into memory past the array!

A couple of major issues remain in your code:

  • Your code skips values because you calculate the sizes of the left and the right parts incorrectly: you assume that they both are num_elem/2, when in fact one of them is num_elem/2+1 when num_elem is odd. Use num_elem/2 for the left side and num_elem-num_elem/2 for the right side. Find all places where your assumption is made, and fix them (there's more than one place).
  • Your code goes into wrong memory because you calculate the position of the middle incorrectly. You need to make a fix on this line: merge(carr, carr + (num_elem/2) /* <<== HERE */, num_elem/2, num_elem/2, elem_size, cmp);
  • You are copying elements into helper incorrectly. Instead of helper[helper_place * elem_size] = *a_temp; you need to call memcpy and use elem_size for the number of bytes to copy. There are several spots where you need to make this fix.

This should bring you a lot closer to a working solution.

Upvotes: 2

R Sahu
R Sahu

Reputation: 206567

In mergesort, you need to treat the pointers as char*, You will need to pass the size of the objects so you would know how to perform pointer arithmetic correctly.

void mergesort(void* a, void* b, size_t objectSize, size_t objectCount)
{
   char* ac = (char*)a;
   char* bc = (char*)b;

   //.....

   mergesort(ac, ac+objectSize*objectCount/2);
}

Upvotes: 1

Related Questions