Comment by lamacase | Hacker News Reader

Comment by lamacase | Hacker News Reader

Bit of a tangent but, I don't know if a segfault should be considered a consequence of a "naive" implementation. Seems more like a consequence of a broken one.

A simple if (!A) goto err_free; would turn that segfault into a "Failed to parse file"

Also, it looks like qsort is implemented on his system as qsort_r:

  http://osxr.org/glibc/source/stdlib/msort.c

Qsort_r appears to allocate O(n) extra memory when the data fits into 1/4 of physical memory. The comments suggest that the regular qsort is slower.

I guess, you're right - for naive implementation it should fall with error, not a segfault. Maybe I just add a check for realloc result.

As for qsort implementation - I was confused by glibc sources ;-) What I've found was a slow but in-place implementation, and what you've shown me is an actual implementation that invokes an in-place variant when allocation was failed:

  tmp = malloc (size);
  __set_errno (save);
  if (tmp == NULL)
    {
      /* Couldn't get space, so use the slower algorithm
         that doesn't need a temporary array.  */
      _quicksort (b, n, s, cmp, arg);
      return;
    }

Thanks for feedback!

Reply on news.ycombinator.com