memcmp sort

Question

I have a single buffer, and several pointers into it. I want to sort the pointers based upon the bytes in the buffer they point at.

qsort() and stl::sort() can be given custom comparision functions. For example, if the buffer was zero-terminated I could use strcmp:

int my_strcmp(const void* a,const void* b) {
  const char* const one = *(const char**)a,
  const two = *(const char**)b;
  return ::strcmp(one,two);
}

however, if the buffer is not zero-terminated, I have to use memcmp() which requires a length parameter.

Is there a tidy, efficient way to get the length of the buffer into my comparision function without a global variable?

Answer 1

Can you pack your buffer pointer + length into a structure and pass a pointer of that structure as void *?

Answer 2

Is there a reason you can't null-terminate your buffers?

If not, since you're using C++ you can write your own function object:

 struct MyStrCmp {
    MyStrCmp (int n): length(n) { }
    inline bool operator< (char *lhs, char *rhs) {
       return ::strcmp (lhs, rhs, length);
    }
    int length;
 };
 // ...
 std::sort (myList.begin (), myList.end (), MyStrCmp (STR_LENGTH));

Answer 3

With std::sort, you can use a Functor like this:

struct CompString {
    CompString(int len) : m_Len(len) {}
    bool operator<(const char *a, const char *b) const {
        return std::memcmp(a, b, m_Len);
    }
private:
    int m_Len;
};

Then you can do this:

std::sort(begin(), end(), CompString(4)); // all strings are 4 chars long

EDIT: from the comment suggestions (i guess both strings are in a common buffer?):

struct CompString {
    CompString (const unsigned char* e) : end(e) {}
    bool operator()(const unsigned char *a, const unsigned char *b) const {
        return std::memcmp(a, b, std::min(end - a, end - b)) < 0;
    }
private:
    const unsigned char* const end;
};

Answer 4

You could functors (give the length to the functor's constructor) or Boost.Lambda (use the length in-place).

Answer 5

I'm not clear on what you're asking. But I'll try, assuming that

• You have a single buffer
• You have an array of pointers of some kind which has been processed in some way so that some or all of its contents point into the buffer

That is code equivalent to:

char *buf = (char*)malloc(sizeof(char)*bufsize);
for (int i=0; i<bufsize; ++i){
    buf[i] = some_cleverly_chosen_value(i);
}

char *ary[arraysize] = {0};
for(int i=0; i<arraysize; ++i){
   ary[i] = buf + some_clever_function(i);
}

/* ...do the sort here */

Now if you control the allocation of the buffer, you could substitute

char *buf = (char*)malloc(sizeof(char)*(bufsize+1));
buf[bufsize]='\0';

and go ahead using strcmp. This may be possible even if you don't control the filling of the buffer.

If you have to live with a buffer handed you by someone else you can

1. Use some global storage (which you asked to avoid and good thinking).
2. Hand the sort function something more complicated than a raw pointer (the address of a struct or class that supports the extra data). For this you need to control the deffinition of ary in the above code.
3. Use a sort function which supports an extra input. Either sort_r as suggested by Adam, or a home-rolled solution (which I do recommend as an exercise for the student, and don't recommend in real life). In either case the extra data is probably a pointer to the end of the buffer.

Answer 6

memcmp should stop on the first byte that is unequal, so the length should be large, i.e. to-the-end-of-the-buffer. Then the only way it can return zero is if it does go to the end of the buffer.

(BTW, I lean toward merge sort myself. It's stable and well-behaved.)

Answer 7

With the C function qsort(), no, there is no way to pass the length to your comparison function without using a global variable, which means it can't be done in a thread-safe manner. Some systems have a qsort_r() function (r stands for reentrant) which allows you to pass an extra context parameter, which then gets passed on to your comparison function:

int my_comparison_func(void *context, const void *a, const void *b)
{
    return memcmp(*(const void **)a, *(const void **)b, (size_t)context);
}

qsort_r(data, n, sizeof(void*), (void*)number_of_bytes_to_compare, &my_comparison_func);