deps/lzma-16.04/C/Sort.c

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