git subrepo pull (merge) --force deps/libchdr

[pcsx_rearmed.git] / deps / libchdr / deps / lzma-22.01 / src / Sort.c

/* Sort.c -- Sort functions\r
2014-04-05 : Igor Pavlov : Public domain */\r
\r
#include "Precomp.h"\r
\r
#include "Sort.h"\r
\r
#define HeapSortDown(p, k, size, temp) \\r
  { for (;;) { \\r
    size_t s = (k << 1); \\r
    if (s > size) break; \\r
    if (s < size && p[s + 1] > p[s]) s++; \\r
    if (temp >= p[s]) break; \\r
    p[k] = p[s]; k = s; \\r
  } p[k] = temp; }\r
\r
void HeapSort(UInt32 *p, size_t size)\r
{\r
  if (size <= 1)\r
    return;\r
  p--;\r
  {\r
    size_t i = size / 2;\r
    do\r
    {\r
      UInt32 temp = p[i];\r
      size_t k = i;\r
      HeapSortDown(p, k, size, temp)\r
    }\r
    while (--i != 0);\r
  }\r
  /*\r
  do\r
  {\r
    size_t k = 1;\r
    UInt32 temp = p[size];\r
    p[size--] = p[1];\r
    HeapSortDown(p, k, size, temp)\r
  }\r
  while (size > 1);\r
  */\r
  while (size > 3)\r
  {\r
    UInt32 temp = p[size];\r
    size_t k = (p[3] > p[2]) ? 3 : 2;\r
    p[size--] = p[1];\r
    p[1] = p[k];\r
    HeapSortDown(p, k, size, temp)\r
  }\r
  {\r
    UInt32 temp = p[size];\r
    p[size] = p[1];\r
    if (size > 2 && p[2] < temp)\r
    {\r
      p[1] = p[2];\r
      p[2] = temp;\r
    }\r
    else\r
      p[1] = temp;\r
  }\r
}\r
\r
void HeapSort64(UInt64 *p, size_t size)\r
{\r
  if (size <= 1)\r
    return;\r
  p--;\r
  {\r
    size_t i = size / 2;\r
    do\r
    {\r
      UInt64 temp = p[i];\r
      size_t k = i;\r
      HeapSortDown(p, k, size, temp)\r
    }\r
    while (--i != 0);\r
  }\r
  /*\r
  do\r
  {\r
    size_t k = 1;\r
    UInt64 temp = p[size];\r
    p[size--] = p[1];\r
    HeapSortDown(p, k, size, temp)\r
  }\r
  while (size > 1);\r
  */\r
  while (size > 3)\r
  {\r
    UInt64 temp = p[size];\r
    size_t k = (p[3] > p[2]) ? 3 : 2;\r
    p[size--] = p[1];\r
    p[1] = p[k];\r
    HeapSortDown(p, k, size, temp)\r
  }\r
  {\r
    UInt64 temp = p[size];\r
    p[size] = p[1];\r
    if (size > 2 && p[2] < temp)\r
    {\r
      p[1] = p[2];\r
      p[2] = temp;\r
    }\r
    else\r
      p[1] = temp;\r
  }\r
}\r
\r
/*\r
#define HeapSortRefDown(p, vals, n, size, temp) \\r
  { size_t k = n; UInt32 val = vals[temp]; for (;;) { \\r
    size_t s = (k << 1); \\r
    if (s > size) break; \\r
    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \\r
    if (val >= vals[p[s]]) break; \\r
    p[k] = p[s]; k = s; \\r
  } p[k] = temp; }\r
\r
void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)\r
{\r
  if (size <= 1)\r
    return;\r
  p--;\r
  {\r
    size_t i = size / 2;\r
    do\r
    {\r
      UInt32 temp = p[i];\r
      HeapSortRefDown(p, vals, i, size, temp);\r
    }\r
    while (--i != 0);\r
  }\r
  do\r
  {\r
    UInt32 temp = p[size];\r
    p[size--] = p[1];\r
    HeapSortRefDown(p, vals, 1, size, temp);\r
  }\r
  while (size > 1);\r
}\r
*/\r