Function sort_buckets

src/simplicity/rsort.c:87–111

Sort the subarray a[begin:end) by their ix-th character, * where begin = bucketEdge[0] and end = bucketEdge[UMAX_CHAR] + bucketSize[UMAX_CHAR]. * * We expect that the ix-length prefix of every entry in a[being:end) to be identical * so that the result is that the a[begin:end) subarray ends up sorted by their first 'ix + 1' characters. * * Precondition: For all begin <= i < end, NULL != a[i];

 * Postcondition: The contents of bucketSize is not preserved!
 */
static void sort_buckets(const sha256_midstate** a, uint32_t* restrict bucketSize, const uint32_t* restrict bucketEdge, unsigned int ix) {
  /* The implementation works by finding the first non-empty bucket and then swapping the first element of that bucket into its position
     at the far end of the bucket where it belongs.

     After moving the element into that position the size of the target bucket is decreased by one,
     and thus the next element that will be swapped into that bucket will be placed behind it.

     This process continues until the first element of the first non-empty bucket gets swapped with itself
     and its own bucket is decremented from size 1 to size 0.

     At that point we search again for the next non-empty bucket and repeat this process until there are no more non-empty buckets.
   */
  for (unsigned int i = 0; i < CHAR_COUNT; ++i) {
    size_t start = bucketEdge[i];
    while (bucketSize[i]) {
      /* Each time through this while loop some bucketSize is decremented.
         Therefore this body is executed 'sum(i < CHAR_COUNT, bucketSize[i]) = end - begin' many times.
       */
      size_t bucket = readIndex(a[start], ix);
      simplicity_assert(bucketSize[bucket]);
      bucketSize[bucket]--;
      swap(a + start, a + bucketEdge[bucket] + bucketSize[bucket]);
    }
  }
}

/* Attempts to (partially) sort an array of pointers to 'sha256_midstate's in place in memcmp order.
 * If NULL == hasDuplicates then sorting is always run to completion.