]>
Commit | Line | Data |
---|---|---|
95974447 | 1 | /* |
e0edde6f | 2 | * Copyright (c) 2012 Nicira, Inc. |
95974447 BP |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | ||
17 | /* A test for for functions and macros declared in heap.h. */ | |
18 | ||
19 | #include <config.h> | |
20 | #include "heap.h" | |
21 | #include <inttypes.h> | |
22 | #include <limits.h> | |
23 | #include <stdlib.h> | |
24 | #include "command-line.h" | |
25 | #include "random.h" | |
26 | #include "util.h" | |
27 | ||
28 | #undef NDEBUG | |
29 | #include <assert.h> | |
30 | ||
31 | /* Sample heap element. */ | |
32 | struct element { | |
33 | uint32_t full_pri; | |
34 | struct heap_node heap_node; | |
35 | }; | |
36 | ||
37 | static struct element * | |
38 | element_from_heap_node(const struct heap_node *node) | |
39 | { | |
40 | return CONTAINER_OF(node, struct element, heap_node); | |
41 | } | |
42 | ||
43 | static int | |
44 | compare_uint32s(const void *a_, const void *b_) | |
45 | { | |
46 | const uint32_t *a = a_; | |
47 | const uint32_t *b = b_; | |
48 | return *a < *b ? -1 : *a > *b; | |
49 | } | |
50 | ||
51 | /* Verifies that 'heap' is internally consistent and contains all 'n' of the | |
52 | * 'priorities'. */ | |
53 | static void | |
54 | check_heap(const struct heap *heap, const uint32_t priorities[], size_t n) | |
55 | { | |
56 | uint32_t *priorities_copy; | |
57 | uint32_t *elements_copy; | |
58 | struct element *element; | |
59 | size_t i; | |
60 | ||
61 | assert(heap_count(heap) == n); | |
62 | assert(heap_is_empty(heap) == !n); | |
63 | if (n > 0) { | |
64 | assert(heap_max(heap) == heap->array[1]); | |
65 | } | |
66 | ||
67 | /* Check indexes. */ | |
68 | for (i = 1; i <= n; i++) { | |
69 | assert(heap->array[i]->idx == i); | |
70 | } | |
71 | ||
72 | /* Check that priority values are internally consistent. */ | |
73 | for (i = 1; i <= n; i++) { | |
74 | element = element_from_heap_node(heap->array[i]); | |
75 | assert(element->heap_node.priority == (element->full_pri >> 16)); | |
76 | } | |
77 | ||
78 | /* Check the heap property. */ | |
79 | for (i = 1; i <= n; i++) { | |
80 | size_t parent = heap_parent__(i); | |
81 | size_t left = heap_left__(i); | |
82 | size_t right = heap_right__(i); | |
83 | ||
84 | if (parent >= 1) { | |
85 | assert(heap->array[parent]->priority >= heap->array[i]->priority); | |
86 | } | |
87 | if (left <= n) { | |
88 | assert(heap->array[left]->priority <= heap->array[i]->priority); | |
89 | } | |
90 | if (right <= n) { | |
91 | assert(heap->array[right]->priority <= heap->array[i]->priority); | |
92 | } | |
93 | } | |
94 | ||
95 | /* Check that HEAP_FOR_EACH iterates all the nodes in order. */ | |
96 | i = 0; | |
97 | HEAP_FOR_EACH (element, heap_node, heap) { | |
98 | assert(i < n); | |
99 | assert(&element->heap_node == heap->array[i + 1]); | |
100 | i++; | |
101 | } | |
102 | assert(i == n); | |
103 | ||
104 | priorities_copy = xmemdup(priorities, n * sizeof *priorities); | |
105 | elements_copy = xmalloc(n * sizeof *priorities); | |
106 | i = 0; | |
107 | HEAP_FOR_EACH (element, heap_node, heap) { | |
108 | elements_copy[i++] = element->heap_node.priority; | |
109 | } | |
110 | ||
111 | qsort(priorities_copy, n, sizeof *priorities_copy, compare_uint32s); | |
112 | qsort(elements_copy, n, sizeof *elements_copy, compare_uint32s); | |
113 | for (i = 0; i < n; i++) { | |
114 | assert((priorities_copy[i] >> 16) == elements_copy[i]); | |
115 | } | |
116 | ||
117 | free(priorities_copy); | |
118 | free(elements_copy); | |
119 | } | |
120 | ||
121 | static void | |
122 | shuffle(uint32_t *p, size_t n) | |
123 | { | |
124 | for (; n > 1; n--, p++) { | |
125 | uint32_t *q = &p[random_range(n)]; | |
126 | uint32_t tmp = *p; | |
127 | *p = *q; | |
128 | *q = tmp; | |
129 | } | |
130 | } | |
131 | ||
132 | /* Prints the values in 'heap', plus 'name' as a title. */ | |
133 | static void OVS_UNUSED | |
134 | print_heap(const char *name, struct heap *heap) | |
135 | { | |
136 | struct element *e; | |
137 | ||
138 | printf("%s:", name); | |
139 | HEAP_FOR_EACH (e, heap_node, heap) { | |
140 | printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & 0xffff); | |
141 | } | |
142 | printf("\n"); | |
143 | } | |
144 | ||
145 | static int | |
146 | factorial(int n_items) | |
147 | { | |
148 | int n, i; | |
149 | ||
150 | n = 1; | |
151 | for (i = 2; i <= n_items; i++) { | |
152 | n *= i; | |
153 | } | |
154 | return n; | |
155 | } | |
156 | ||
157 | static void | |
158 | swap(uint32_t *a, uint32_t *b) | |
159 | { | |
160 | uint32_t tmp = *a; | |
161 | *a = *b; | |
162 | *b = tmp; | |
163 | } | |
164 | ||
165 | static void | |
166 | reverse(uint32_t *a, int n) | |
167 | { | |
168 | int i; | |
169 | ||
170 | for (i = 0; i < n / 2; i++) { | |
171 | int j = n - (i + 1); | |
172 | swap(&a[i], &a[j]); | |
173 | } | |
174 | } | |
175 | ||
176 | static bool | |
177 | next_permutation(uint32_t *a, int n) | |
178 | { | |
179 | int k; | |
180 | ||
181 | for (k = n - 2; k >= 0; k--) { | |
182 | if ((a[k] >> 16) < (a[k + 1] >> 16)) { | |
183 | int l; | |
184 | ||
185 | for (l = n - 1; ; l--) { | |
186 | if ((a[l] >> 16) > (a[k] >> 16)) { | |
187 | swap(&a[k], &a[l]); | |
188 | reverse(a + (k + 1), n - (k + 1)); | |
189 | return true; | |
190 | } | |
191 | } | |
192 | } | |
193 | } | |
194 | return false; | |
195 | } | |
196 | ||
197 | static void | |
198 | test_insert_delete__(struct element *elements, | |
199 | const uint32_t *insert, | |
200 | const uint32_t *delete, | |
201 | size_t n) | |
202 | { | |
203 | struct heap heap; | |
204 | size_t i; | |
205 | ||
206 | heap_init(&heap); | |
207 | check_heap(&heap, NULL, 0); | |
208 | for (i = 0; i < n; i++) { | |
209 | uint32_t priority = insert[i]; | |
210 | ||
211 | elements[i].full_pri = priority; | |
212 | heap_insert(&heap, &elements[i].heap_node, priority >> 16); | |
213 | check_heap(&heap, insert, i + 1); | |
214 | } | |
215 | ||
216 | for (i = 0; i < n; i++) { | |
217 | struct element *element; | |
218 | ||
219 | HEAP_FOR_EACH (element, heap_node, &heap) { | |
220 | if (element->full_pri == delete[i]) { | |
221 | goto found; | |
222 | } | |
223 | } | |
428b2edd | 224 | OVS_NOT_REACHED(); |
95974447 BP |
225 | |
226 | found: | |
227 | heap_remove(&heap, &element->heap_node); | |
228 | check_heap(&heap, delete + i + 1, n - (i + 1)); | |
229 | } | |
230 | heap_destroy(&heap); | |
231 | } | |
232 | ||
233 | static void | |
234 | test_insert_delete_raw__(struct element *elements, | |
235 | const uint32_t *insert, unsigned int insert_pattern, | |
236 | const uint32_t *delete, unsigned int delete_pattern, | |
237 | size_t n) | |
238 | { | |
239 | struct heap heap; | |
240 | size_t i; | |
241 | ||
242 | heap_init(&heap); | |
243 | check_heap(&heap, NULL, 0); | |
244 | for (i = 0; i < n; i++) { | |
245 | uint32_t priority = insert[i]; | |
246 | ||
247 | elements[i].full_pri = priority; | |
248 | heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16); | |
249 | if (insert_pattern & (1u << i)) { | |
250 | heap_rebuild(&heap); | |
251 | check_heap(&heap, insert, i + 1); | |
252 | } | |
253 | } | |
254 | ||
255 | for (i = 0; i < n; i++) { | |
256 | struct element *element; | |
257 | ||
258 | HEAP_FOR_EACH (element, heap_node, &heap) { | |
259 | if (element->full_pri == delete[i]) { | |
260 | goto found; | |
261 | } | |
262 | } | |
428b2edd | 263 | OVS_NOT_REACHED(); |
95974447 BP |
264 | |
265 | found: | |
266 | heap_raw_remove(&heap, &element->heap_node); | |
267 | if (delete_pattern & (1u << i)) { | |
268 | heap_rebuild(&heap); | |
269 | check_heap(&heap, delete + i + 1, n - (i + 1)); | |
270 | } | |
271 | } | |
272 | heap_destroy(&heap); | |
273 | } | |
274 | ||
275 | static void | |
276 | test_heap_insert_delete_same_order(int argc OVS_UNUSED, | |
277 | char *argv[] OVS_UNUSED) | |
278 | { | |
279 | enum { N_ELEMS = 7 }; | |
280 | ||
281 | uint32_t insert[N_ELEMS]; | |
282 | int n_permutations; | |
283 | size_t i; | |
284 | ||
285 | for (i = 0; i < N_ELEMS; i++) { | |
286 | insert[i] = i << 16; | |
287 | } | |
288 | ||
289 | n_permutations = 0; | |
290 | do { | |
291 | struct element elements[N_ELEMS]; | |
292 | ||
293 | n_permutations++; | |
294 | test_insert_delete__(elements, insert, insert, N_ELEMS); | |
295 | } while (next_permutation(insert, N_ELEMS)); | |
296 | assert(n_permutations == factorial(N_ELEMS)); | |
297 | } | |
298 | ||
299 | static void | |
300 | test_heap_insert_delete_reverse_order(int argc OVS_UNUSED, | |
301 | char *argv[] OVS_UNUSED) | |
302 | { | |
303 | enum { N_ELEMS = 7 }; | |
304 | ||
305 | uint32_t insert[N_ELEMS]; | |
306 | int n_permutations; | |
307 | size_t i; | |
308 | ||
309 | for (i = 0; i < N_ELEMS; i++) { | |
310 | insert[i] = i << 16; | |
311 | } | |
312 | ||
313 | n_permutations = 0; | |
314 | do { | |
315 | struct element elements[N_ELEMS]; | |
316 | uint32_t delete[N_ELEMS]; | |
317 | ||
318 | n_permutations++; | |
319 | ||
320 | for (i = 0; i < N_ELEMS; i++) { | |
321 | delete[N_ELEMS - i - 1] = insert[i]; | |
322 | } | |
323 | ||
324 | test_insert_delete__(elements, insert, delete, N_ELEMS); | |
325 | } while (next_permutation(insert, N_ELEMS)); | |
326 | assert(n_permutations == factorial(N_ELEMS)); | |
327 | } | |
328 | ||
329 | static void | |
330 | test_heap_insert_delete_every_order(int argc OVS_UNUSED, | |
331 | char *argv[] OVS_UNUSED) | |
332 | { | |
333 | enum { N_ELEMS = 5 }; | |
334 | ||
335 | uint32_t insert[N_ELEMS]; | |
336 | int outer_permutations; | |
337 | size_t i; | |
338 | ||
339 | for (i = 0; i < N_ELEMS; i++) { | |
340 | insert[i] = i << 16; | |
341 | } | |
342 | ||
343 | outer_permutations = 0; | |
344 | do { | |
345 | struct element elements[N_ELEMS]; | |
346 | uint32_t delete[N_ELEMS]; | |
347 | int inner_permutations; | |
348 | ||
349 | outer_permutations++; | |
350 | ||
351 | for (i = 0; i < N_ELEMS; i++) { | |
352 | delete[i] = i << 16; | |
353 | } | |
354 | ||
355 | inner_permutations = 0; | |
356 | do { | |
357 | inner_permutations++; | |
358 | test_insert_delete__(elements, insert, delete, N_ELEMS); | |
359 | } while (next_permutation(delete, N_ELEMS)); | |
360 | assert(inner_permutations == factorial(N_ELEMS)); | |
361 | } while (next_permutation(insert, N_ELEMS)); | |
362 | assert(outer_permutations == factorial(N_ELEMS)); | |
363 | } | |
364 | ||
365 | static void | |
366 | test_heap_insert_delete_same_order_with_dups(int argc OVS_UNUSED, | |
367 | char *argv[] OVS_UNUSED) | |
368 | { | |
369 | enum { N_ELEMS = 7 }; | |
370 | ||
371 | unsigned int pattern; | |
372 | size_t i; | |
373 | ||
374 | for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) { | |
375 | int n_permutations, expected_permutations; | |
376 | uint32_t insert[N_ELEMS]; | |
377 | int j; | |
378 | ||
379 | j = 0; | |
380 | for (i = 0; i < N_ELEMS; i++) { | |
381 | if (i && !(pattern & (1u << i))) { | |
382 | j++; | |
383 | } | |
384 | insert[i] = (j << 16) | i; | |
385 | } | |
386 | ||
387 | expected_permutations = factorial(N_ELEMS); | |
388 | for (i = 0; i < N_ELEMS; ) { | |
389 | j = i + 1; | |
390 | if (pattern & (1u << i)) { | |
391 | for (; j < N_ELEMS; j++) { | |
392 | if (!(pattern & (1u << j))) { | |
393 | break; | |
394 | } | |
395 | } | |
396 | expected_permutations /= factorial(j - i + 1); | |
397 | } | |
398 | i = j; | |
399 | } | |
400 | ||
401 | n_permutations = 0; | |
402 | do { | |
403 | struct element elements[N_ELEMS]; | |
404 | ||
405 | n_permutations++; | |
406 | test_insert_delete__(elements, insert, insert, N_ELEMS); | |
407 | } while (next_permutation(insert, N_ELEMS)); | |
408 | assert(n_permutations == expected_permutations); | |
409 | } | |
410 | } | |
411 | ||
412 | static void | |
413 | test_heap_raw_insert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
414 | { | |
415 | enum { N_ELEMS = 7 }; | |
416 | ||
417 | uint32_t insert[N_ELEMS]; | |
418 | int n_permutations; | |
419 | size_t i; | |
420 | ||
421 | for (i = 0; i < N_ELEMS; i++) { | |
422 | insert[i] = i << 16; | |
423 | } | |
424 | ||
425 | n_permutations = 0; | |
426 | do { | |
427 | struct element elements[N_ELEMS]; | |
428 | ||
429 | n_permutations++; | |
430 | test_insert_delete_raw__(elements, | |
431 | insert, 1u << (N_ELEMS - 1), | |
432 | insert, UINT_MAX, | |
433 | N_ELEMS); | |
434 | } while (next_permutation(insert, N_ELEMS)); | |
435 | assert(n_permutations == factorial(N_ELEMS)); | |
436 | } | |
437 | ||
438 | static void | |
439 | test_heap_raw_delete(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
440 | { | |
441 | enum { N_ELEMS = 16 }; | |
442 | ||
443 | uint32_t insert[N_ELEMS]; | |
444 | uint32_t delete[N_ELEMS]; | |
445 | size_t i; | |
446 | ||
447 | for (i = 0; i < N_ELEMS; i++) { | |
448 | insert[i] = i << 16; | |
449 | delete[i] = i << 16; | |
450 | } | |
451 | ||
452 | for (i = 0; i < 1000; i++) { | |
453 | struct element elements[N_ELEMS]; | |
454 | ||
455 | shuffle(insert, N_ELEMS); | |
456 | shuffle(delete, N_ELEMS); | |
457 | ||
458 | test_insert_delete_raw__(elements, | |
459 | insert, 0, | |
460 | delete, | |
461 | (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / 2)), | |
462 | N_ELEMS); | |
463 | } | |
464 | } | |
465 | ||
466 | static const struct command commands[] = { | |
467 | { "insert-delete-same-order", 0, 0, test_heap_insert_delete_same_order, }, | |
468 | { "insert-delete-reverse-order", 0, 0, | |
469 | test_heap_insert_delete_reverse_order, }, | |
470 | { "insert-delete-every-order", 0, 0, | |
471 | test_heap_insert_delete_every_order, }, | |
472 | { "insert-delete-same-order-with-dups", 0, 0, | |
473 | test_heap_insert_delete_same_order_with_dups, }, | |
474 | { "raw-insert", 0, 0, test_heap_raw_insert, }, | |
475 | { "raw-delete", 0, 0, test_heap_raw_delete, }, | |
476 | }; | |
477 | ||
478 | int | |
479 | main(int argc, char *argv[]) | |
480 | { | |
481 | set_program_name(argv[0]); | |
482 | ||
483 | run_command(argc - 1, argv + 1, commands); | |
484 | ||
485 | return 0; | |
486 | } |