1. 23 Aug, 2019 1 commit
    • util: do not perform allocations in insertsort · 8cbef12d
      Our hand-rolled fallback sorting function `git__insertsort_r` does an
      in-place sort of the given array. As elements may not necessarily be
      pointers, it needs a way of swapping two values of arbitrary size, which
      is currently implemented by allocating a temporary buffer of the
      element's size. This is problematic, though, as the emulated `qsort`
      interface doesn't provide any return values and thus cannot signal an
      error if allocation of that temporary buffer has failed.
      
      Convert the function to swap via a temporary buffer allocated on the
      stack. Like this, it can `memcpy` contents of both elements in small
      batches without requiring a heap allocation. The buffer size has been
      chosen such that in most cases, a single iteration of copying will
      suffice. Most importantly, it can fully contain `git_oid` structures and
      pointers.
      
      Add a bunch of tests for the `git__qsort_r` interface to verify nothing
      breaks. Furthermore, this removes the declaration of `git__insertsort_r`
      and makes it static as it is not used anywhere else.
      Patrick Steinhardt committed