diff options
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r-- | src/util/container_heap.c | 533 |
1 files changed, 533 insertions, 0 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c new file mode 100644 index 000000000..1e7077c80 --- /dev/null +++ b/src/util/container_heap.c | |||
@@ -0,0 +1,533 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2008 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 2, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @author Nathan Evans | ||
23 | * @file util/container_heap.c | ||
24 | * @brief Implementation of heap operations | ||
25 | */ | ||
26 | |||
27 | #include "platform.h" | ||
28 | #include "gnunet_protocols.h" | ||
29 | #include "gnunet_util.h" | ||
30 | #include "gnunet_util_containers.h" | ||
31 | |||
32 | /* | ||
33 | * Struct that is stored in hashmap, pointers to | ||
34 | * locations in min_heap and max_heap. | ||
35 | */ | ||
36 | struct GNUNET_CONTAINER_heap_info | ||
37 | { | ||
38 | struct GNUNET_CONTAINER_heap_node *min_loc; | ||
39 | |||
40 | struct GNUNET_CONTAINER_heap_node *max_loc; | ||
41 | |||
42 | }; | ||
43 | |||
44 | /* | ||
45 | * Generic heap node structure, contains pointer to parent | ||
46 | * left child, right child, and actual neighbor. | ||
47 | */ | ||
48 | struct GNUNET_CONTAINER_heap_node | ||
49 | { | ||
50 | struct GNUNET_CONTAINER_heap_node *parent; | ||
51 | |||
52 | struct GNUNET_CONTAINER_heap_node *left_child; | ||
53 | |||
54 | struct GNUNET_CONTAINER_heap_node *right_child; | ||
55 | |||
56 | GNUNET_CONTAINER_HeapCost cost; | ||
57 | |||
58 | void *element; | ||
59 | |||
60 | }; | ||
61 | |||
62 | struct GNUNET_CONTAINER_Heap | ||
63 | { | ||
64 | unsigned int size; | ||
65 | |||
66 | unsigned int max_size; | ||
67 | |||
68 | enum type; | ||
69 | |||
70 | struct GNUNET_CONTAINER_heap_node *root; | ||
71 | |||
72 | struct GNUNET_CONTAINER_heap_node *traversal_pos; | ||
73 | |||
74 | }; | ||
75 | |||
76 | void | ||
77 | internal_print (struct GNUNET_CONTAINER_heap_node *root) | ||
78 | { | ||
79 | fprintf (stdout, "%d\n", root->cost); | ||
80 | if (root->left_child != NULL) | ||
81 | { | ||
82 | fprintf (stdout, "LEFT of %d\n", root->cost); | ||
83 | internal_print (root->left_child); | ||
84 | } | ||
85 | if (root->right_child != NULL) | ||
86 | { | ||
87 | fprintf (stdout, "RIGHT of %d\n", root->cost); | ||
88 | internal_print (root->right_child); | ||
89 | } | ||
90 | } | ||
91 | |||
92 | void | ||
93 | printTree (struct GNUNET_CONTAINER_Heap *root) | ||
94 | { | ||
95 | internal_print (root->root); | ||
96 | } | ||
97 | |||
98 | struct GNUNET_CONTAINER_Heap * | ||
99 | GNUNET_CONTAINER_heap_create (enum type) | ||
100 | { | ||
101 | struct GNUNET_CONTAINER_Heap *heap; | ||
102 | heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap)); | ||
103 | heap->max_size = -1; | ||
104 | heap->type = type; | ||
105 | heap->root = NULL; | ||
106 | heap->traversal_pos = NULL; | ||
107 | heap->size = 0; | ||
108 | |||
109 | return heap; | ||
110 | } | ||
111 | |||
112 | void | ||
113 | GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) | ||
114 | { | ||
115 | void *unused; | ||
116 | while (heap->size > 0) | ||
117 | { | ||
118 | unused = GNUNET_CONTAINER_heap_remove_root (heap); | ||
119 | } | ||
120 | |||
121 | GNUNET_free (heap); | ||
122 | return; | ||
123 | } | ||
124 | |||
125 | struct GNUNET_CONTAINER_heap_node * | ||
126 | find_element (struct GNUNET_CONTAINER_heap_node *node, void *element) | ||
127 | { | ||
128 | struct GNUNET_CONTAINER_heap_node *ret; | ||
129 | ret = NULL; | ||
130 | if ((node != NULL) && (node->element == element)) | ||
131 | { | ||
132 | ret = node; | ||
133 | } | ||
134 | |||
135 | if ((ret == NULL) && (node->left_child != NULL)) | ||
136 | { | ||
137 | ret = find_element (node->left_child, element); | ||
138 | } | ||
139 | |||
140 | if ((ret == NULL) && (node->right_child != NULL)) | ||
141 | { | ||
142 | ret = find_element (node->right_child, element); | ||
143 | } | ||
144 | |||
145 | return ret; | ||
146 | } | ||
147 | |||
148 | static struct GNUNET_CONTAINER_heap_node * | ||
149 | getNextPos (struct GNUNET_CONTAINER_Heap *root) | ||
150 | { | ||
151 | struct GNUNET_CONTAINER_heap_node *ret; | ||
152 | struct GNUNET_CONTAINER_heap_node *parent; | ||
153 | int pos; | ||
154 | int depth; | ||
155 | int i; | ||
156 | |||
157 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node)); | ||
158 | pos = root->size + 1; | ||
159 | depth = (int) log2 (pos); | ||
160 | ret->left_child = NULL; | ||
161 | ret->right_child = NULL; | ||
162 | |||
163 | if (depth == 0) | ||
164 | { | ||
165 | ret->parent = NULL; | ||
166 | root->root = ret; | ||
167 | } | ||
168 | else | ||
169 | { | ||
170 | parent = root->root; | ||
171 | for (i = depth; i > 1; i--) | ||
172 | { | ||
173 | if (((pos / (1 << (i - 1))) % 2) == 0) | ||
174 | parent = parent->left_child; | ||
175 | else | ||
176 | parent = parent->right_child; | ||
177 | } | ||
178 | |||
179 | ret->parent = parent; | ||
180 | if ((pos % 2) == 0) | ||
181 | parent->left_child = ret; | ||
182 | else | ||
183 | parent->right_child = ret; | ||
184 | |||
185 | } | ||
186 | |||
187 | return ret; | ||
188 | |||
189 | } | ||
190 | |||
191 | static struct GNUNET_CONTAINER_heap_node * | ||
192 | getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos) | ||
193 | { | ||
194 | struct GNUNET_CONTAINER_heap_node *ret; | ||
195 | |||
196 | int depth; | ||
197 | int i; | ||
198 | |||
199 | depth = (int) log2 (pos); | ||
200 | ret = NULL; | ||
201 | if (pos > root->size) | ||
202 | { | ||
203 | return ret; | ||
204 | } | ||
205 | else | ||
206 | { | ||
207 | ret = root->root; | ||
208 | for (i = depth; i > 0; i--) | ||
209 | { | ||
210 | if (((pos / (1 << (i - 1))) % 2) == 0) | ||
211 | ret = ret->left_child; | ||
212 | else | ||
213 | ret = ret->right_child; | ||
214 | } | ||
215 | } | ||
216 | |||
217 | return ret; | ||
218 | |||
219 | } | ||
220 | |||
221 | void | ||
222 | swapNodes (struct GNUNET_CONTAINER_heap_node *first, | ||
223 | struct GNUNET_CONTAINER_heap_node *second, | ||
224 | struct GNUNET_CONTAINER_Heap *root) | ||
225 | { | ||
226 | void *temp_element; | ||
227 | GNUNET_CONTAINER_HeapCost temp_cost; | ||
228 | |||
229 | temp_element = first->element; | ||
230 | temp_cost = first->cost; | ||
231 | first->element = second->element; | ||
232 | first->cost = second->cost; | ||
233 | second->element = temp_element; | ||
234 | second->cost = temp_cost; | ||
235 | |||
236 | /* | ||
237 | * I still worry that there is some good reason for | ||
238 | * elements being location aware... but it eludes me | ||
239 | * for the moment... | ||
240 | if ((root->type == GNUNET_DV_MAX_HEAP)) | ||
241 | { | ||
242 | first->neighbor->max_loc = first; | ||
243 | second->neighbor->max_loc = second; | ||
244 | } | ||
245 | else if ((root->type == GNUNET_DV_MIN_HEAP)) | ||
246 | { | ||
247 | first->neighbor->min_loc = first; | ||
248 | second->neighbor->min_loc = second; | ||
249 | } | ||
250 | */ | ||
251 | return; | ||
252 | } | ||
253 | |||
254 | void | ||
255 | percolateHeap (struct GNUNET_CONTAINER_heap_node *pos, | ||
256 | struct GNUNET_CONTAINER_Heap *root) | ||
257 | { | ||
258 | |||
259 | while ((pos->parent != NULL) && | ||
260 | (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | ||
261 | && (pos->parent->cost < pos->cost)) | ||
262 | || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | ||
263 | && (pos->parent->cost > pos->cost)))) | ||
264 | { | ||
265 | swapNodes (pos, pos->parent, root); | ||
266 | pos = pos->parent; | ||
267 | } | ||
268 | |||
269 | return; | ||
270 | } | ||
271 | |||
272 | |||
273 | |||
274 | void | ||
275 | percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos, | ||
276 | struct GNUNET_CONTAINER_Heap *root) | ||
277 | { | ||
278 | struct GNUNET_CONTAINER_heap_node *switchNeighbor; | ||
279 | |||
280 | switchNeighbor = pos; | ||
281 | |||
282 | if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)) | ||
283 | { | ||
284 | if ((pos->left_child != NULL) | ||
285 | && (pos->left_child->cost > switchNeighbor->cost)) | ||
286 | { | ||
287 | switchNeighbor = pos->left_child; | ||
288 | } | ||
289 | |||
290 | if ((pos->right_child != NULL) | ||
291 | && (pos->right_child->cost > switchNeighbor->cost)) | ||
292 | { | ||
293 | switchNeighbor = pos->right_child; | ||
294 | } | ||
295 | } | ||
296 | else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)) | ||
297 | { | ||
298 | if ((pos->left_child != NULL) | ||
299 | && (pos->left_child->cost < switchNeighbor->cost)) | ||
300 | { | ||
301 | switchNeighbor = pos->left_child; | ||
302 | } | ||
303 | |||
304 | if ((pos->right_child != NULL) | ||
305 | && (pos->right_child->cost < switchNeighbor->cost)) | ||
306 | { | ||
307 | switchNeighbor = pos->right_child; | ||
308 | } | ||
309 | } | ||
310 | |||
311 | if (switchNeighbor != pos) | ||
312 | { | ||
313 | swapNodes (switchNeighbor, pos, root); | ||
314 | percolateDownHeap (switchNeighbor, root); | ||
315 | } | ||
316 | |||
317 | return; | ||
318 | } | ||
319 | |||
320 | void * | ||
321 | GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root, | ||
322 | void *element) | ||
323 | { | ||
324 | void *ret; | ||
325 | struct GNUNET_CONTAINER_heap_node *del_node; | ||
326 | struct GNUNET_CONTAINER_heap_node *last; | ||
327 | GNUNET_CONTAINER_HeapCost old_cost; | ||
328 | |||
329 | del_node = NULL; | ||
330 | del_node = find_element (root->root, element); | ||
331 | |||
332 | if (del_node == NULL) | ||
333 | return NULL; | ||
334 | |||
335 | ret = del_node->element; | ||
336 | last = getPos (root, root->size); | ||
337 | |||
338 | old_cost = del_node->cost; | ||
339 | del_node->element = last->element; | ||
340 | del_node->cost = last->cost; | ||
341 | |||
342 | if (last->parent->left_child == last) | ||
343 | last->parent->left_child = NULL; | ||
344 | if (last->parent->right_child == last) | ||
345 | last->parent->right_child = NULL; | ||
346 | |||
347 | if (root->traversal_pos == last) | ||
348 | { | ||
349 | root->traversal_pos = root->root; | ||
350 | } | ||
351 | GNUNET_free (last); | ||
352 | root->size--; | ||
353 | |||
354 | if (del_node->cost > old_cost) | ||
355 | { | ||
356 | if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | ||
357 | percolateHeap (del_node, root); | ||
358 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | ||
359 | percolateDownHeap (del_node, root); | ||
360 | } | ||
361 | else if (del_node->cost < old_cost) | ||
362 | { | ||
363 | if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | ||
364 | percolateDownHeap (del_node, root); | ||
365 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | ||
366 | percolateHeap (del_node, root); | ||
367 | } | ||
368 | |||
369 | return ret; | ||
370 | } | ||
371 | |||
372 | int | ||
373 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root, | ||
374 | void *element, GNUNET_CONTAINER_HeapCost cost) | ||
375 | { | ||
376 | struct GNUNET_CONTAINER_heap_node *new_pos; | ||
377 | int ret; | ||
378 | ret = GNUNET_YES; | ||
379 | |||
380 | if (root->max_size > root->size) | ||
381 | { | ||
382 | new_pos = getNextPos (root); | ||
383 | new_pos->element = element; | ||
384 | new_pos->cost = cost; | ||
385 | root->size++; | ||
386 | /*We no longer can tolerate pointers between heaps :( */ | ||
387 | /*if (root->type == GNUNET_DV_MIN_HEAP) | ||
388 | new_pos->neighbor->min_loc = new_pos; | ||
389 | else if (root->type == GNUNET_DV_MAX_HEAP) | ||
390 | new_pos->neighbor->max_loc = new_pos; */ | ||
391 | |||
392 | percolateHeap (new_pos, root); | ||
393 | } | ||
394 | else | ||
395 | { | ||
396 | ret = GNUNET_NO; | ||
397 | } | ||
398 | |||
399 | return ret; | ||
400 | } | ||
401 | |||
402 | void * | ||
403 | GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root) | ||
404 | { | ||
405 | void *ret; | ||
406 | struct GNUNET_CONTAINER_heap_node *root_node; | ||
407 | struct GNUNET_CONTAINER_heap_node *last; | ||
408 | |||
409 | root_node = root->root; | ||
410 | ret = root_node->element; | ||
411 | last = getPos (root, root->size); | ||
412 | |||
413 | if (last->parent->left_child == last) | ||
414 | last->parent->left_child = NULL; | ||
415 | else if (last->parent->right_child == last) | ||
416 | last->parent->right_child = NULL; | ||
417 | |||
418 | root_node->element = last->element; | ||
419 | root_node->cost = last->cost; | ||
420 | |||
421 | if (root->traversal_pos == last) | ||
422 | { | ||
423 | root->traversal_pos = root->root; | ||
424 | } | ||
425 | |||
426 | GNUNET_free (last); | ||
427 | root->size--; | ||
428 | percolateDownHeap (root->root, root); | ||
429 | return ret; | ||
430 | } | ||
431 | |||
432 | static int | ||
433 | updatedCost (struct GNUNET_CONTAINER_Heap *root, | ||
434 | struct GNUNET_CONTAINER_heap_node *node) | ||
435 | { | ||
436 | struct GNUNET_CONTAINER_heap_node *parent; | ||
437 | |||
438 | if (node == NULL) | ||
439 | return GNUNET_SYSERR; | ||
440 | |||
441 | parent = node->parent; | ||
442 | |||
443 | if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL) | ||
444 | && (node->cost > parent->cost)) | ||
445 | percolateHeap (node, root); | ||
446 | else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL) | ||
447 | && (node->cost < parent->cost)) | ||
448 | percolateHeap (node, root); | ||
449 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | ||
450 | percolateDownHeap (node, root); | ||
451 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | ||
452 | percolateDownHeap (node, root); | ||
453 | |||
454 | return GNUNET_YES; | ||
455 | } | ||
456 | |||
457 | |||
458 | int | ||
459 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root, | ||
460 | void *element, | ||
461 | GNUNET_CONTAINER_HeapCost new_cost) | ||
462 | { | ||
463 | struct GNUNET_CONTAINER_heap_node *node; | ||
464 | int ret = GNUNET_YES; | ||
465 | node = find_element (root->root, element); | ||
466 | if (node == NULL) | ||
467 | return GNUNET_NO; | ||
468 | |||
469 | node->cost = new_cost; | ||
470 | ret = updatedCost (root, node); | ||
471 | return ret; | ||
472 | } | ||
473 | |||
474 | void | ||
475 | internal_iterator (struct GNUNET_CONTAINER_Heap *root, | ||
476 | struct GNUNET_CONTAINER_heap_node *node, | ||
477 | GNUNET_CONTAINER_HeapIterator iterator, void *cls) | ||
478 | { | ||
479 | if (node == NULL) | ||
480 | return; | ||
481 | internal_iterator (root, node->left_child, iterator, cls); | ||
482 | internal_iterator (root, node->right_child, iterator, cls); | ||
483 | iterator (node->element, node->cost, root, cls); | ||
484 | } | ||
485 | |||
486 | int | ||
487 | GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap, | ||
488 | GNUNET_CONTAINER_HeapIterator iterator, | ||
489 | void *cls) | ||
490 | { | ||
491 | internal_iterator (heap, heap->root, iterator, cls); | ||
492 | return GNUNET_OK; | ||
493 | } | ||
494 | |||
495 | void * | ||
496 | GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root) | ||
497 | { | ||
498 | unsigned int choice; | ||
499 | void *element; | ||
500 | |||
501 | if ((root->traversal_pos == NULL) && (root->root != NULL)) | ||
502 | { | ||
503 | root->traversal_pos = root->root; | ||
504 | } | ||
505 | |||
506 | if (root->traversal_pos == NULL) | ||
507 | return NULL; | ||
508 | |||
509 | element = root->traversal_pos->element; | ||
510 | |||
511 | choice = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2); | ||
512 | |||
513 | switch (choice) | ||
514 | { | ||
515 | case 1: | ||
516 | root->traversal_pos = root->traversal_pos->right_child; | ||
517 | break; | ||
518 | case 0: | ||
519 | root->traversal_pos = root->traversal_pos->left_child; | ||
520 | break; | ||
521 | } | ||
522 | |||
523 | return element; | ||
524 | |||
525 | } | ||
526 | |||
527 | unsigned int | ||
528 | GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap) | ||
529 | { | ||
530 | return heap->size; | ||
531 | } | ||
532 | |||
533 | /* end of heap.c */ | ||