Function rsort_ex

src/simplicity/rsort.c:124–233

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. * Otherwise, if NULL != hasDuplicates and if duplicate entries are found, the sorting is aborted and * *hasDuplicates is set to one of pointers of a duplicate entry. * If NULL != hasDuplicates and no duplicate entries are found,

 *               uint32_t stack[(CHAR_COUNT - 1)*(sizeof(*a)->s) + 1];
 */
static void rsort_ex(const sha256_midstate** a, uint_fast32_t len, const sha256_midstate** hasDuplicates, uint32_t* stack) {
  unsigned int depth = 0;
  size_t bucketCount[sizeof((*a)->s) + 1];
  size_t totalBucketCount = 1;

  static_assert(sizeof((*a)->s) <= UINT_MAX, "UINT_MAX too small to hold depth.");
  stack[0]=0;
  bucketCount[depth] = 1;

  /* This implementation contains a 'stack' of 'totalBucketCount' many subarrays (called buckets)
     that have been partially sorted up to various prefix length.

     The buckets are disjoint and cover the entire array from 0 up to len.
     As sorting proceeds, the end of the array will be sorted first.
     We will decrease len as we go as we find out that items at the end of the array are in their proper, sorted position.

     The 'i'th bucket is the subarray a[stack[i]:stack[i+1]),
     except for the last bucket which is the subarray a[stack[totalBucketCount-1]:len).

     The depth to which various buckets are sorted increases the further down the stack you go.
     The 'bucketCount' stores how many buckets are sorted to various depths.

     * for all i <= depth, the subarray a[sum(j < i, bucketCount[i]):end) have their first i characters sorted.
     * for all i <= depth, the (sum(j < i, bucketCount[i]))th and later buckets have all the first i characters of their entries identical.

     So all buckets are sorted up to a prefix length of 0 many characters.
     Then, if 1 <= depth, all bucket except for the first bucketCount[0]-many buckets are sorted by their 1 character prefix
     And then, if 2 <= depth, all bucket except for the first (bucketCount[0] + bucket[1])-many buckets are sorted by their 2 character prefix
     And so on.

     It is always the case that 'totalBucketCount = sum(i <= depth, bucketCount[i])',
     and thus the last bucket in the stack is located at stack[totalBucketCount-1].
     'totalBucketCount' and 'bucketCount' items are always increased and decreased in tandum.

     The loop is initialized with a 'totalBucketCount' of 1 and this one bucket contains the whole array a[0:len).
     'depth' is initialized to 0, and all the entries are trivialy sorted by the first 0-many characters.

     As we go through the loop, the last bucket is "popped" off the stack and processed, which can go one of two ways.

     If the last bucket is size 2 or greater, we proceed to sort it by its 'depth' character and partition the bucket into 256 sub-buckets
     which are then pushed onto the stack (notice this causes a net increase of the stack size by 255 items, because one was popped off).

     If ever the depth is beyond the size of the data being sorted,
     we can immediately halt as we have found 2 or more item that are identical.

     Note: there is an added optimization where by if there is only one non-empty bucket found when attempting to sort,
     i.e. it happens that every bucket item already has identical 'depth' characters,
     we skip the subdivision and move onto the next depth immediately.
     (This is equivalent to pushing the one non-empty bucket onto the stack and immediately popping it back off.)

     If the last bucket is of size 0 or 1, it must be already be sorted.
     Since this bucket is at the end of the array we decrease 'len'.
   */
  while(totalBucketCount) {
    /* Find the correct "depth" of the last bucket. */
    while(0 == bucketCount[depth]) {
      simplicity_assert(depth);
      depth--;