tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

Sort.c (2589B)

      1 /* Sort.c -- Sort functions
      2 2014-04-05 : Igor Pavlov : Public domain */
      3 
      4 #include "Precomp.h"
      5 
      6 #include "Sort.h"
      7 
      8 #define HeapSortDown(p, k, size, temp) \
      9  { for (;;) { \
     10    size_t s = (k << 1); \
     11    if (s > size) break; \
     12    if (s < size && p[s + 1] > p[s]) s++; \
     13    if (temp >= p[s]) break; \
     14    p[k] = p[s]; k = s; \
     15  } p[k] = temp; }
     16 
     17 void HeapSort(UInt32 *p, size_t size)
     18 {
     19  if (size <= 1)
     20    return;
     21  p--;
     22  {
     23    size_t i = size / 2;
     24    do
     25    {
     26      UInt32 temp = p[i];
     27      size_t k = i;
     28      HeapSortDown(p, k, size, temp)
     29    }
     30    while (--i != 0);
     31  }
     32  /*
     33  do
     34  {
     35    size_t k = 1;
     36    UInt32 temp = p[size];
     37    p[size--] = p[1];
     38    HeapSortDown(p, k, size, temp)
     39  }
     40  while (size > 1);
     41  */
     42  while (size > 3)
     43  {
     44    UInt32 temp = p[size];
     45    size_t k = (p[3] > p[2]) ? 3 : 2;
     46    p[size--] = p[1];
     47    p[1] = p[k];
     48    HeapSortDown(p, k, size, temp)
     49  }
     50  {
     51    UInt32 temp = p[size];
     52    p[size] = p[1];
     53    if (size > 2 && p[2] < temp)
     54    {
     55      p[1] = p[2];
     56      p[2] = temp;
     57    }
     58    else
     59      p[1] = temp;
     60  }
     61 }
     62 
     63 void HeapSort64(UInt64 *p, size_t size)
     64 {
     65  if (size <= 1)
     66    return;
     67  p--;
     68  {
     69    size_t i = size / 2;
     70    do
     71    {
     72      UInt64 temp = p[i];
     73      size_t k = i;
     74      HeapSortDown(p, k, size, temp)
     75    }
     76    while (--i != 0);
     77  }
     78  /*
     79  do
     80  {
     81    size_t k = 1;
     82    UInt64 temp = p[size];
     83    p[size--] = p[1];
     84    HeapSortDown(p, k, size, temp)
     85  }
     86  while (size > 1);
     87  */
     88  while (size > 3)
     89  {
     90    UInt64 temp = p[size];
     91    size_t k = (p[3] > p[2]) ? 3 : 2;
     92    p[size--] = p[1];
     93    p[1] = p[k];
     94    HeapSortDown(p, k, size, temp)
     95  }
     96  {
     97    UInt64 temp = p[size];
     98    p[size] = p[1];
     99    if (size > 2 && p[2] < temp)
    100    {
    101      p[1] = p[2];
    102      p[2] = temp;
    103    }
    104    else
    105      p[1] = temp;
    106  }
    107 }
    108 
    109 /*
    110 #define HeapSortRefDown(p, vals, n, size, temp) \
    111  { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
    112    size_t s = (k << 1); \
    113    if (s > size) break; \
    114    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
    115    if (val >= vals[p[s]]) break; \
    116    p[k] = p[s]; k = s; \
    117  } p[k] = temp; }
    118 
    119 void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
    120 {
    121  if (size <= 1)
    122    return;
    123  p--;
    124  {
    125    size_t i = size / 2;
    126    do
    127    {
    128      UInt32 temp = p[i];
    129      HeapSortRefDown(p, vals, i, size, temp);
    130    }
    131    while (--i != 0);
    132  }
    133  do
    134  {
    135    UInt32 temp = p[size];
    136    p[size--] = p[1];
    137    HeapSortRefDown(p, vals, 1, size, temp);
    138  }
    139  while (size > 1);
    140 }
    141 */