9c6005bebc8010750f37014594f1beb1f843dd7f
[oweals/gnunet.git] / src / util / container_heap.c
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_lib.h"
30
31 /**
32  * Generic heap node structure, contains pointer to parent
33  * left child, right child, and actual neighbor.
34  */
35 struct GNUNET_CONTAINER_heap_node
36 {
37   struct GNUNET_CONTAINER_heap_node *parent;
38
39   struct GNUNET_CONTAINER_heap_node *left_child;
40
41   struct GNUNET_CONTAINER_heap_node *right_child;
42
43   GNUNET_CONTAINER_HeapCost cost;
44
45   void *element;
46
47 };
48
49 struct GNUNET_CONTAINER_Heap
50 {
51   unsigned int size;
52
53   unsigned int max_size;
54
55   enum GNUNET_CONTAINER_HeapOrder type;
56
57   struct GNUNET_CONTAINER_heap_node *root;
58
59   struct GNUNET_CONTAINER_heap_node *traversal_pos;
60
61 };
62
63
64 /**
65  * Returns element stored at root of tree, doesn't effect anything
66  *
67  * @param heap the heap
68  * @return NULL if the heap is empty
69  */
70 void *
71 GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
72 {
73   if ((heap == NULL) || (heap->root == NULL))
74     return NULL;
75
76   return heap->root->element;
77 }
78
79 static int
80 next_power_of_2 (int v)
81 {
82   v |= v >> 1;
83   v |= v >> 2;
84   v |= v >> 4;
85   v |= v >> 8;
86   v |= v >> 16;
87   v++;
88   return v;
89 }
90
91 #if 0
92 static void
93 internal_print (struct GNUNET_CONTAINER_heap_node *root)
94 {
95   fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
96   if (root->left_child != NULL)
97     {
98       fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
99       internal_print (root->left_child);
100     }
101   if (root->right_child != NULL)
102     {
103       fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
104       internal_print (root->right_child);
105     }
106 }
107
108 static void
109 printTree (struct GNUNET_CONTAINER_Heap *root)
110 {
111   internal_print (root->root);
112 }
113 #endif
114
115 struct GNUNET_CONTAINER_Heap *
116 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
117 {
118   struct GNUNET_CONTAINER_Heap *heap;
119   heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
120   heap->max_size = -1;
121   heap->type = type;
122   heap->root = NULL;
123   heap->traversal_pos = NULL;
124   heap->size = 0;
125
126   return heap;
127 }
128
129 void
130 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
131 {
132   while (heap->size > 0)
133     GNUNET_CONTAINER_heap_remove_root (heap);
134   GNUNET_free (heap);
135 }
136
137 static struct GNUNET_CONTAINER_heap_node *
138 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
139 {
140   struct GNUNET_CONTAINER_heap_node *ret;
141   ret = NULL;
142   if (node == NULL)
143     return NULL;
144
145   if (node->element == element)
146     return node;
147
148   if (node->left_child != NULL)
149     ret = find_element (node->left_child, element);
150
151   if ((ret == NULL) && (node->right_child != NULL))
152     ret = find_element (node->right_child, element);
153
154   return ret;
155 }
156
157 static struct GNUNET_CONTAINER_heap_node *
158 getNextPos (struct GNUNET_CONTAINER_Heap *root)
159 {
160   struct GNUNET_CONTAINER_heap_node *ret;
161   struct GNUNET_CONTAINER_heap_node *parent;
162   int pos;
163   int i;
164
165   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
166   pos = root->size + 1;
167   ret->left_child = NULL;
168   ret->right_child = NULL;
169
170   if (0 == root->size)
171     {
172       ret->parent = NULL;
173       root->root = ret;
174     }
175   else
176     {
177       parent = root->root;
178       for (i = next_power_of_2 (pos) >> 2; i > 1; i >>= 1)
179         {
180           if (((pos / i) % 2) == 0)
181             parent = parent->left_child;
182           else
183             parent = parent->right_child;
184         }
185
186       ret->parent = parent;
187       if ((pos % 2) == 0)
188         parent->left_child = ret;
189       else
190         parent->right_child = ret;
191
192     }
193
194   return ret;
195
196 }
197
198 static struct GNUNET_CONTAINER_heap_node *
199 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
200 {
201   struct GNUNET_CONTAINER_heap_node *ret;
202   unsigned int i;
203
204   ret = NULL;
205   if (pos > root->size)
206     {
207       return ret;
208     }
209   else
210     {
211       ret = root->root;
212       for (i = next_power_of_2 (pos) >> 2; i > 0; i >>= 1)
213         {
214           if (((pos / i) % 2) == 0)
215             ret = ret->left_child;
216           else
217             ret = ret->right_child;
218         }
219     }
220
221   return ret;
222
223 }
224
225 void
226 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
227            struct GNUNET_CONTAINER_heap_node *second,
228            struct GNUNET_CONTAINER_Heap *root)
229 {
230   void *temp_element;
231   GNUNET_CONTAINER_HeapCost temp_cost;
232
233   temp_element = first->element;
234   temp_cost = first->cost;
235   first->element = second->element;
236   first->cost = second->cost;
237   second->element = temp_element;
238   second->cost = temp_cost;
239
240   return;
241 }
242
243 void
244 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
245                struct GNUNET_CONTAINER_Heap *root)
246 {
247
248   while ((pos->parent != NULL) &&
249          (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
250            && (pos->parent->cost < pos->cost))
251           || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
252               && (pos->parent->cost > pos->cost))))
253     {
254       swapNodes (pos, pos->parent, root);
255       pos = pos->parent;
256     }
257
258   return;
259 }
260
261
262
263 void
264 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
265                    struct GNUNET_CONTAINER_Heap *root)
266 {
267   struct GNUNET_CONTAINER_heap_node *switchNeighbor;
268
269   switchNeighbor = pos;
270
271   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
272     {
273       if ((pos->left_child != NULL)
274           && (pos->left_child->cost > switchNeighbor->cost))
275         {
276           switchNeighbor = pos->left_child;
277         }
278
279       if ((pos->right_child != NULL)
280           && (pos->right_child->cost > switchNeighbor->cost))
281         {
282           switchNeighbor = pos->right_child;
283         }
284     }
285   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
286     {
287       if ((pos->left_child != NULL)
288           && (pos->left_child->cost < switchNeighbor->cost))
289         {
290           switchNeighbor = pos->left_child;
291         }
292
293       if ((pos->right_child != NULL)
294           && (pos->right_child->cost < switchNeighbor->cost))
295         {
296           switchNeighbor = pos->right_child;
297         }
298     }
299
300   if (switchNeighbor != pos)
301     {
302       swapNodes (switchNeighbor, pos, root);
303       percolateDownHeap (switchNeighbor, root);
304     }
305
306   return;
307 }
308
309 void *
310 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
311                                    void *element)
312 {
313   void *ret;
314   struct GNUNET_CONTAINER_heap_node *del_node;
315   struct GNUNET_CONTAINER_heap_node *last;
316   GNUNET_CONTAINER_HeapCost old_cost;
317
318   del_node = NULL;
319   del_node = find_element (root->root, element);
320
321   if (del_node == NULL)
322     return NULL;
323   else if (del_node == root->root)
324     return GNUNET_CONTAINER_heap_remove_root (root);
325
326   ret = del_node->element;
327   last = getPos (root, root->size);
328
329   root->size--;
330
331   old_cost = del_node->cost;
332   del_node->element = last->element;
333   del_node->cost = last->cost;
334
335   if (last->parent->left_child == last)
336     last->parent->left_child = NULL;
337   if (last->parent->right_child == last)
338     last->parent->right_child = NULL;
339
340   if (root->traversal_pos == last)
341     {
342       root->traversal_pos = root->root;
343     }
344
345   if (last == del_node)
346   {
347     GNUNET_free (last);
348     return ret;
349   }
350   GNUNET_free (last);
351
352
353   if (del_node->cost > old_cost)
354     {
355       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
356         percolateHeap (del_node, root);
357       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
358         percolateDownHeap (del_node, root);
359     }
360   else if (del_node->cost < old_cost)
361     {
362       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
363         percolateDownHeap (del_node, root);
364       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
365         percolateHeap (del_node, root);
366     }
367
368   return ret;
369 }
370
371 int
372 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
373                               void *element, GNUNET_CONTAINER_HeapCost cost)
374 {
375   struct GNUNET_CONTAINER_heap_node *new_pos;
376   int ret;
377   ret = GNUNET_YES;
378
379   if (root->max_size > root->size)
380     {
381       new_pos = getNextPos (root);
382       new_pos->element = element;
383       new_pos->cost = cost;
384       root->size++;
385
386       percolateHeap (new_pos, root);
387     }
388   else
389     {
390       ret = GNUNET_NO;
391     }
392
393   return ret;
394 }
395
396 void *
397 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
398 {
399   void *ret;
400   struct GNUNET_CONTAINER_heap_node *root_node;
401   struct GNUNET_CONTAINER_heap_node *last;
402
403   if ((root == NULL) || (root->size == 0) || (root->root == NULL))
404     {
405       GNUNET_break (0);
406       return NULL;
407     }
408
409   root_node = root->root;
410   ret = root_node->element;
411   last = getPos (root, root->size);
412
413   if ((root_node == last) && (root->size == 1))
414     {
415       /* We are removing the last node in the heap! */
416       GNUNET_free (last);
417       root->root = NULL;
418       root->traversal_pos = NULL;
419       GNUNET_assert (0 == --root->size);
420       return ret;
421     }
422
423   if (last->parent->left_child == last)
424     last->parent->left_child = NULL;
425   else if (last->parent->right_child == last)
426     last->parent->right_child = NULL;
427
428   root_node->element = last->element;
429   root_node->cost = last->cost;
430
431   if (root->traversal_pos == last)
432     root->traversal_pos = root->root;
433   GNUNET_free (last);
434   root->size--;
435   percolateDownHeap (root->root, root);
436   return ret;
437 }
438
439 static int
440 updatedCost (struct GNUNET_CONTAINER_Heap *root,
441              struct GNUNET_CONTAINER_heap_node *node)
442 {
443   struct GNUNET_CONTAINER_heap_node *parent;
444
445   if (node == NULL)
446     return GNUNET_SYSERR;
447
448   parent = node->parent;
449
450   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
451       && (node->cost > parent->cost))
452     percolateHeap (node, root);
453   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
454            && (node->cost < parent->cost))
455     percolateHeap (node, root);
456   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
457     percolateDownHeap (node, root);
458   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
459     percolateDownHeap (node, root);
460
461   return GNUNET_YES;
462 }
463
464
465 int
466 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
467                                    void *element,
468                                    GNUNET_CONTAINER_HeapCost new_cost)
469 {
470   struct GNUNET_CONTAINER_heap_node *node;
471   int ret = GNUNET_YES;
472   node = find_element (root->root, element);
473   if (node == NULL)
474     return GNUNET_NO;
475
476   node->cost = new_cost;
477   ret = updatedCost (root, node);
478   return ret;
479 }
480
481 void
482 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
483                    struct GNUNET_CONTAINER_heap_node *node,
484                    GNUNET_CONTAINER_HeapIterator iterator, void *cls)
485 {
486   if (node == NULL)
487     return;
488   internal_iterator (root, node->left_child, iterator, cls);
489   internal_iterator (root, node->right_child, iterator, cls);
490   iterator (cls, node->element, node->cost);
491 }
492
493 int
494 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
495                                GNUNET_CONTAINER_HeapIterator iterator,
496                                void *cls)
497 {
498   internal_iterator (heap, heap->root, iterator, cls);
499   return GNUNET_OK;
500 }
501
502 void *
503 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
504 {
505   unsigned int choice;
506   void *element;
507
508   if ((root->traversal_pos == NULL) && (root->root != NULL))
509     {
510       root->traversal_pos = root->root;
511     }
512
513   if (root->traversal_pos == NULL)
514     return NULL;
515
516   element = root->traversal_pos->element;
517
518   choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
519
520   switch (choice)
521     {
522     case 1:
523       root->traversal_pos = root->traversal_pos->right_child;
524       break;
525     case 0:
526       root->traversal_pos = root->traversal_pos->left_child;
527       break;
528     }
529
530   return element;
531
532 }
533
534 unsigned int
535 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
536 {
537   return heap->size;
538 }
539
540 /* end of heap.c */