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