aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r--src/util/container_heap.c533
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 */
36struct 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 */
48struct 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
62struct 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
76void
77internal_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
92void
93printTree (struct GNUNET_CONTAINER_Heap *root)
94{
95 internal_print (root->root);
96}
97
98struct GNUNET_CONTAINER_Heap *
99GNUNET_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
112void
113GNUNET_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
125struct GNUNET_CONTAINER_heap_node *
126find_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
148static struct GNUNET_CONTAINER_heap_node *
149getNextPos (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
191static struct GNUNET_CONTAINER_heap_node *
192getPos (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
221void
222swapNodes (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
254void
255percolateHeap (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
274void
275percolateDownHeap (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
320void *
321GNUNET_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
372int
373GNUNET_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
402void *
403GNUNET_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
432static int
433updatedCost (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
458int
459GNUNET_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
474void
475internal_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
486int
487GNUNET_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
495void *
496GNUNET_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
527unsigned int
528GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
529{
530 return heap->size;
531}
532
533/* end of heap.c */