Is qsort thread safe?

Question

I have some old code that uses qsort to sort an MFC CArray of structures but am seeing the occasional crash that may be down to multiple threads calling qsort at the same time. The code I am using looks something like this:

struct Foo
{
  CString str;
  time_t t;

  Foo(LPCTSTR lpsz, time_t ti) : str(lpsz), t(ti)
  {
  }
};

class Sorter()
{
public:
    static void DoSort();
    static int __cdecl SortProc(const void* elem1, const void* elem2);
};

...

void Sorter::DoSort()
{
  CArray<Foo*, Foo*> data;
  for (int i = 0; i < 100; i++)
  {
    Foo* foo = new Foo("some string", 12345678);
    data.Add(foo);
  }

  qsort(data.GetData(), data.GetCount(), sizeof(Foo*), SortProc);
  ...
}

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = (Foo*)elem1;
  Foo* foo2 = (Foo*)elem2;
  // 0xC0000005: Access violation reading location blah here
  return (int)(foo1->t - foo2->t);
}

...

Sorter::DoSort();

I am about to refactor this horrible code to use std::sort instead but wondered if the above is actually unsafe?

EDIT: Sorter::DoSort is actually a static function but uses no static variables itself.

EDIT2: The SortProc function has been changed to match the real code.

Answer 1

Your problem doesn't necessarily have anything to do with thread saftey.

The sort callback function takes in pointers to each item, not the item itself. Since you are sorting Foo* what you actually want to do is access the parameters as Foo**, like this:

int __cdecl SortProc(const void* elem1, const void* elem2)
{
  Foo* foo1 = *(Foo**)elem1;
  Foo* foo2 = *(Foo**)elem2;
  if(foo1->t < foo2->t) return -1;
  else if (foo1->t > foo2->t) return 1;
  else return 0;
}

Answer 2

Your SortProc isn't returning correct results, and this likely leads to memory corruption by something assuming that the data is, well, sorted after you get done sorting it. You could even be leading qsort into corruption as it tries to sort, but that of course varies by implementation.

The comparison function for qsort must return negative if the first object is less than the second, zero if they are equal, and positive otherwise. Your current code only ever returns 0 or 1, and returns 1 when you should be returning negative.

int __cdecl Sorter::SortProc(const void* ap, const void* bp) {
  Foo const& a = *(Foo const*)ap;
  Foo const& b = *(Foo const*)bp;
  if (a.t == b.t) return 0;
  return (a.t < b.t) ? -1 : 1;
}

Answer 3

C++ doesn't really make any guarantees about thread safety. About the most you can say is that either multiple readers OR a single writer to a data structure will be OK. Any combination of readers and writers, and you need to serialise the access somehow.

Answer 4

Since you tagged your question with MFC tag I suppose you should select Multi-threaded Runtime Library in Project Settings.

Answer 5

Right now, your code is thread-safe, but useless, as the DoSort-method only uses local variables, and doesn't even return anything. If the data you are sorting is a member of Sorter, then it is not safe to call the function from multiple threads. In gerenal, read up on reentrancy, this may give you an idea of what you need to look out for.

Answer 6

what make it thread safe is, whether your object are thread safe, for example to make qsort thread-safe you must ensure that anything that write or read to or from and to the object are thread safe.

Answer 7

The pthreads man page lists the standard functions which are not required to be thread-safe. qsort is not among them, so it is required to be thread-safe in POSIX.

http://www.kernel.org/doc/man-pages/online/pages/man7/pthreads.7.html

I can't find the equivalent list for Windows, though, so this isn't really an answer to your question. I'd be a bit surprised if it was different.

Be aware what "thread-safe" means in this context, though. It means you can call the same function concurrently on different arrays -- it doesn't mean that concurrent access to the same data via qsort is safe (it isn't).

Answer 8

As a word of warning, you may find std::sort is not as fast as qsort. If you do find that try std::stable_sort.

I once wrote a BWT compressor based on the code presented my Mark Nelson in Dr Dobbs and when I turned it into classes I found that regular sort was a lot slower. stable_sort fixed the speed problems.