1. 23 Jan, 2017 1 commit
    • René Scharfe's avatar
      compat: add qsort_s() · 04ee8b87
      René Scharfe authored
      The function qsort_s() was introduced with C11 Annex K; it provides the
      ability to pass a context pointer to the comparison function, supports
      the convention of using a NULL pointer for an empty array and performs a
      few safety checks.
      
      Add an implementation based on compat/qsort.c for platforms that lack a
      native standards-compliant qsort_s() (i.e. basically everyone).  It
      doesn't perform the full range of possible checks: It uses size_t
      instead of rsize_t and doesn't check nmemb and size against RSIZE_MAX
      because we probably don't have the restricted size type defined.  For
      the same reason it returns int instead of errno_t.
      Signed-off-by: default avatarRene Scharfe <l.s.r@web.de>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      04ee8b87
  2. 22 Feb, 2016 1 commit
  3. 06 Oct, 2011 1 commit
    • Brandon Casey's avatar
      cleanup: use internal memory allocation wrapper functions everywhere · 040a6551
      Brandon Casey authored
      The "x"-prefixed versions of strdup, malloc, etc. will check whether the
      allocation was successful and terminate the process otherwise.
      
      A few uses of malloc were left alone since they already implemented a
      graceful path of failure or were in a quasi external library like xdiff.
      
      Additionally, the call to malloc in compat/win32/syslog.c was not modified
      since the syslog() implemented there is a die handler and a call to the
      x-wrappers within a die handler could result in recursion should memory
      allocation fail.  This will have to be addressed separately.
      Signed-off-by: default avatarBrandon Casey <drafnel@gmail.com>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      040a6551
  4. 07 Feb, 2008 1 commit
    • Brian Downing's avatar
      compat: Add simplified merge sort implementation from glibc · 43fe901b
      Brian Downing authored
      qsort in Windows 2000 (and various other C libraries) is a Quicksort
      with the usual O(n^2) worst case.  Unfortunately, sorting Git trees
      seems to get very close to that worst case quite often:
      
          $ /git/gitbad runstatus
          # On branch master
          qsort, nmemb = 30842
          done, 237838087 comparisons.
      
      This patch adds a simplified version of the merge sort that is glibc's
      qsort(3).  As a merge sort, this needs a temporary array equal in size
      to the array that is to be sorted, but has a worst-case performance of
      O(n log n).
      
      The complexity that was removed is:
      
      * Doing direct stores for word-size and -aligned data.
      * Falling back to quicksort if the allocation required to perform the
        merge sort would likely push the machine into swap.
      
      Even with these simplifications, this seems to outperform the Windows
      qsort(3) implementation, even in Windows XP (where it is "fixed" and
      doesn't trigger O(n^2) complexity on trees).
      
      [jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion]
      [bcd: removed gcc-ism, thanks to Edgar Toernig.  renamed make variable
            per Junio's comment.]
      Signed-off-by: Brian Downing's avatarBrian Downing <bdowning@lavos.net>
      Signed-off-by: default avatarSteffen Prohaska <prohaska@zib.de>
      Signed-off-by: Johannes Schindelin's avatarJohannes Schindelin <johannes.schindelin@gmx.de>
      Signed-off-by: default avatarJunio C Hamano <gitster@pobox.com>
      43fe901b