1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/win32/7zip/7z/C/Sort.c	Sat Mar 03 10:31:27 2012 -0600
     1.3 @@ -0,0 +1,95 @@
     1.4 +/* Sort.c -- Sort functions
     1.5 +2008-08-17
     1.6 +Igor Pavlov
     1.7 +Public domain */
     1.8 +
     1.9 +#include "Sort.h"
    1.10 +
    1.11 +#define HeapSortDown(p, k, size, temp) \
    1.12 +  { for (;;) { \
    1.13 +    UInt32 s = (k << 1); \
    1.14 +    if (s > size) break; \
    1.15 +    if (s < size && p[s + 1] > p[s]) s++; \
    1.16 +    if (temp >= p[s]) break; \
    1.17 +    p[k] = p[s]; k = s; \
    1.18 +  } p[k] = temp; }
    1.19 +
    1.20 +void HeapSort(UInt32 *p, UInt32 size)
    1.21 +{
    1.22 +  if (size <= 1)
    1.23 +    return;
    1.24 +  p--;
    1.25 +  {
    1.26 +    UInt32 i = size / 2;
    1.27 +    do
    1.28 +    {
    1.29 +      UInt32 temp = p[i];
    1.30 +      UInt32 k = i;
    1.31 +      HeapSortDown(p, k, size, temp)
    1.32 +    }
    1.33 +    while (--i != 0);
    1.34 +  }
    1.35 +  /*
    1.36 +  do
    1.37 +  {
    1.38 +    UInt32 k = 1;
    1.39 +    UInt32 temp = p[size];
    1.40 +    p[size--] = p[1];
    1.41 +    HeapSortDown(p, k, size, temp)
    1.42 +  }
    1.43 +  while (size > 1);
    1.44 +  */
    1.45 +  while (size > 3)
    1.46 +  {
    1.47 +    UInt32 temp = p[size];
    1.48 +    UInt32 k = (p[3] > p[2]) ? 3 : 2;
    1.49 +    p[size--] = p[1];
    1.50 +    p[1] = p[k];
    1.51 +    HeapSortDown(p, k, size, temp)
    1.52 +  }
    1.53 +  {
    1.54 +    UInt32 temp = p[size];
    1.55 +    p[size] = p[1];
    1.56 +    if (size > 2 && p[2] < temp)
    1.57 +    {
    1.58 +      p[1] = p[2];
    1.59 +      p[2] = temp;
    1.60 +    }
    1.61 +    else
    1.62 +      p[1] = temp;
    1.63 +  }
    1.64 +}
    1.65 +
    1.66 +/*
    1.67 +#define HeapSortRefDown(p, vals, n, size, temp) \
    1.68 +  { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \
    1.69 +    UInt32 s = (k << 1); \
    1.70 +    if (s > size) break; \
    1.71 +    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
    1.72 +    if (val >= vals[p[s]]) break; \
    1.73 +    p[k] = p[s]; k = s; \
    1.74 +  } p[k] = temp; }
    1.75 +
    1.76 +void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size)
    1.77 +{
    1.78 +  if (size <= 1)
    1.79 +    return;
    1.80 +  p--;
    1.81 +  {
    1.82 +    UInt32 i = size / 2;
    1.83 +    do
    1.84 +    {
    1.85 +      UInt32 temp = p[i];
    1.86 +      HeapSortRefDown(p, vals, i, size, temp);
    1.87 +    }
    1.88 +    while (--i != 0);
    1.89 +  }
    1.90 +  do
    1.91 +  {
    1.92 +    UInt32 temp = p[size];
    1.93 +    p[size--] = p[1];
    1.94 +    HeapSortRefDown(p, vals, 1, size, temp);
    1.95 +  }
    1.96 +  while (size > 1);
    1.97 +}
    1.98 +*/
    1.99 \ No newline at end of file