Print this page
11972 resync smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/sort.c
+++ new/usr/src/tools/smatch/src/sort.c
1 1 /*
2 2 * sort_list: a stable sort for lists.
3 3 *
4 4 * Time complexity: O(n*log n)
5 5 * [assuming limited zero-element fragments]
6 6 *
7 7 * Space complexity: O(1).
8 8 *
9 9 * Stable: yes.
10 10 */
11 11
12 12 #include <stdio.h>
13 13 #include <stdlib.h>
14 14 #include <string.h>
15 15
16 16 #include "lib.h"
17 17 #include "allocate.h"
18 18
19 19 #undef PARANOIA
20 20 #undef COVERAGE
21 21
22 22 #ifdef PARANOIA
23 23 #include <assert.h>
24 24 #else
25 25 #define assert(x)
26 26 #endif
27 27
28 28 #ifdef COVERAGE
29 29 static unsigned char been_there[256];
30 30 #define BEEN_THERE(_c) \
31 31 do { \
32 32 if (!been_there[_c]) { \
33 33 been_there[_c] = 1; \
34 34 printf ("Been there: %c\n", _c); \
35 35 } \
36 36 } while (0)
37 37 #else
38 38 #define BEEN_THERE(_c) do { } while (0)
39 39 #endif
40 40
41 41 // Sort one fragment. LIST_NODE_NR (==29) is a bit too high for my
42 42 // taste for something this simple. But, hey, it's O(1).
43 43 //
44 44 // I would use libc qsort for this, but its comparison function
45 45 // gets a pointer indirection extra.
46 46 static void array_sort(void **ptr, int nr, int (*cmp)(const void *, const void *))
47 47 {
48 48 int i;
49 49 for (i = 1; i < nr; i++) {
50 50 void *p = ptr[i];
51 51 if (cmp(ptr[i-1],p) > 0) {
52 52 int j = i;
53 53 do {
54 54 ptr[j] = ptr[j-1];
55 55 if (!--j)
56 56 break;
57 57 } while (cmp(ptr[j-1], p) > 0);
58 58 ptr[j] = p;
59 59 }
60 60 }
61 61 }
62 62
63 63 #ifdef PARANOIA
64 64 static void verify_seq_sorted (struct ptr_list *l, int n,
65 65 int (*cmp)(const void *, const void *))
66 66 {
67 67 int i = 0;
68 68 const void *a;
69 69 struct ptr_list *head = l;
70 70
71 71 while (l->nr == 0) {
72 72 l = l->next;
73 73 if (--n == 0)
74 74 return;
75 75 assert (l != head);
76 76 }
77 77
78 78 a = l->list[0];
79 79 while (n > 0) {
80 80 const void *b;
81 81 if (++i >= l->nr) {
82 82 i = 0;
83 83 l = l->next;
84 84 n--;
85 85 assert (l != head || n == 0);
86 86 continue;
87 87 }
88 88 b = l->list[i];
89 89 assert (cmp (a, b) <= 0);
90 90 a = b;
91 91 }
92 92 }
93 93 #endif
94 94
95 95
96 96 #define FLUSH_TO(b) \
97 97 do { \
98 98 int nr = (b)->nr; \
99 99 assert (nbuf >= nr); \
100 100 memcpy ((b)->list, buffer, nr * sizeof (void *)); \
101 101 nbuf -= nr; \
102 102 memmove (buffer, buffer + nr, nbuf * sizeof (void *)); \
103 103 } while (0)
104 104
105 105 #define DUMP_TO(b) \
106 106 do { \
107 107 assert (nbuf <= (b)->nr); \
108 108 memcpy ((b)->list, buffer, nbuf * sizeof (void *)); \
109 109 } while (0)
110 110
111 111
112 112 // Merge two already-sorted sequences of blocks:
113 113 // (b1_1, ..., b1_n) and (b2_1, ..., b2_m)
114 114 // Since we may be moving blocks around, we return the new head
115 115 // of the merged list.
116 116 static struct ptr_list *
117 117 merge_block_seqs (struct ptr_list *b1, int n,
118 118 struct ptr_list *b2, int m,
119 119 int (*cmp)(const void *, const void *))
120 120 {
121 121 int i1 = 0, i2 = 0;
122 122 const void *buffer[2 * LIST_NODE_NR];
123 123 int nbuf = 0;
124 124 struct ptr_list *newhead = b1;
125 125
126 126 // printf ("Merging %d blocks at %p with %d blocks at %p\n", n, b1, m, b2);
127 127
128 128 // Skip empty blocks in b2.
129 129 while (b2->nr == 0) {
130 130 BEEN_THERE('F');
|
↓ open down ↓ |
130 lines elided |
↑ open up ↑ |
131 131 b2 = b2->next;
132 132 if (--m == 0) {
133 133 BEEN_THERE('G');
134 134 return newhead;
135 135 }
136 136 }
137 137
138 138 // Do a quick skip in case entire blocks from b1 are
139 139 // already less than smallest element in b2.
140 140 while (b1->nr == 0 ||
141 - cmp (PTR_ENTRY(b1, b1->nr - 1), PTR_ENTRY(b2,0)) < 0) {
141 + cmp (PTR_ENTRY_NOTAG(b1, b1->nr - 1), PTR_ENTRY_NOTAG(b2,0)) < 0) {
142 142 // printf ("Skipping whole block.\n");
143 143 BEEN_THERE('H');
144 144 b1 = b1->next;
145 145 if (--n == 0) {
146 146 BEEN_THERE('I');
147 147 return newhead;
148 148 }
149 149 }
150 150
151 151 while (1) {
152 - const void *d1 = PTR_ENTRY(b1,i1);
153 - const void *d2 = PTR_ENTRY(b2,i2);
152 + const void *d1 = PTR_ENTRY_NOTAG(b1,i1);
153 + const void *d2 = PTR_ENTRY_NOTAG(b2,i2);
154 154
155 155 assert (i1 >= 0 && i1 < b1->nr);
156 156 assert (i2 >= 0 && i2 < b2->nr);
157 157 assert (b1 != b2);
158 158 assert (n > 0);
159 159 assert (m > 0);
160 160
161 161 if (cmp (d1, d2) <= 0) {
162 162 BEEN_THERE('J');
163 163 buffer[nbuf++] = d1;
164 164 // Element from b1 is smaller
165 165 if (++i1 >= b1->nr) {
166 166 BEEN_THERE('L');
167 167 FLUSH_TO(b1);
168 168 do {
169 169 b1 = b1->next;
170 170 if (--n == 0) {
171 171 BEEN_THERE('O');
172 172 while (b1 != b2) {
173 173 BEEN_THERE('P');
174 174 FLUSH_TO(b1);
175 175 b1 = b1->next;
176 176 }
177 177 assert (nbuf == i2);
178 178 DUMP_TO(b2);
179 179 return newhead;
180 180 }
181 181 } while (b1->nr == 0);
182 182 i1 = 0;
183 183 }
184 184 } else {
185 185 BEEN_THERE('K');
186 186 // Element from b2 is smaller
187 187 buffer[nbuf++] = d2;
188 188 if (++i2 >= b2->nr) {
189 189 struct ptr_list *l = b2;
190 190 BEEN_THERE('M');
191 191 // OK, we finished with b2. Pull it out
192 192 // and plug it in before b1.
193 193
194 194 b2 = b2->next;
195 195 b2->prev = l->prev;
196 196 b2->prev->next = b2;
197 197 l->next = b1;
198 198 l->prev = b1->prev;
199 199 l->next->prev = l;
200 200 l->prev->next = l;
201 201
202 202 if (b1 == newhead) {
203 203 BEEN_THERE('N');
204 204 newhead = l;
205 205 }
206 206
207 207 FLUSH_TO(l);
208 208 b2 = b2->prev;
209 209 do {
210 210 b2 = b2->next;
211 211 if (--m == 0) {
212 212 BEEN_THERE('Q');
213 213 assert (nbuf == i1);
214 214 DUMP_TO(b1);
215 215 return newhead;
216 216 }
217 217 } while (b2->nr == 0);
218 218 i2 = 0;
219 219 }
220 220 }
221 221 }
222 222 }
223 223
224 224
225 225 void sort_list(struct ptr_list **plist, int (*cmp)(const void *, const void *))
226 226 {
227 227 struct ptr_list *head = *plist, *list = head;
228 228 int blocks = 1;
229 229
230 230 if (!head)
231 231 return;
232 232
233 233 // Sort all the sub-lists
234 234 do {
235 235 array_sort(list->list, list->nr, cmp);
236 236 #ifdef PARANOIA
237 237 verify_seq_sorted (list, 1, cmp);
238 238 #endif
239 239 list = list->next;
240 240 } while (list != head);
241 241
242 242 // Merge the damn things together
243 243 while (1) {
244 244 struct ptr_list *block1 = head;
245 245
246 246 do {
247 247 struct ptr_list *block2 = block1;
248 248 struct ptr_list *next, *newhead;
249 249 int i;
250 250
251 251 for (i = 0; i < blocks; i++) {
252 252 block2 = block2->next;
253 253 if (block2 == head) {
254 254 if (block1 == head) {
255 255 BEEN_THERE('A');
256 256 *plist = head;
257 257 return;
258 258 }
259 259 BEEN_THERE('B');
260 260 goto next_pass;
261 261 }
262 262 }
263 263
264 264 next = block2;
265 265 for (i = 0; i < blocks; ) {
266 266 next = next->next;
267 267 i++;
268 268 if (next == head) {
269 269 BEEN_THERE('C');
270 270 break;
271 271 }
272 272 BEEN_THERE('D');
273 273 }
274 274
275 275 newhead = merge_block_seqs (block1, blocks,
276 276 block2, i,
277 277 cmp);
278 278 #ifdef PARANOIA
279 279 verify_seq_sorted (newhead, blocks + i, cmp);
280 280 #endif
281 281 if (block1 == head) {
282 282 BEEN_THERE('E');
283 283 head = newhead;
284 284 }
285 285 block1 = next;
286 286 } while (block1 != head);
287 287 next_pass:
288 288 blocks <<= 1;
289 289 }
290 290 }
|
↓ open down ↓ |
127 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX