News for hackers. Stuff that matters.
Re:When memory is not enough by lamacase on Thursday April 02, 2015 @04:47PM (#9313109)
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.
Re:When memory is not enough by dzeban on Saturday April 04, 2015 @08:46AM (#9320684)
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!