2 This file is part of GNUnet.
3 (C) 2008 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @author Nathan Evans
23 * @file util/container_heap.c
24 * @brief Implementation of heap operations
28 #include "gnunet_protocols.h"
29 #include "gnunet_util_lib.h"
32 * Struct that is stored in hashmap, pointers to
33 * locations in min_heap and max_heap.
35 struct GNUNET_CONTAINER_heap_info
37 struct GNUNET_CONTAINER_heap_node *min_loc;
39 struct GNUNET_CONTAINER_heap_node *max_loc;
44 * Generic heap node structure, contains pointer to parent
45 * left child, right child, and actual neighbor.
47 struct GNUNET_CONTAINER_heap_node
49 struct GNUNET_CONTAINER_heap_node *parent;
51 struct GNUNET_CONTAINER_heap_node *left_child;
53 struct GNUNET_CONTAINER_heap_node *right_child;
55 GNUNET_CONTAINER_HeapCost cost;
61 struct GNUNET_CONTAINER_Heap
65 unsigned int max_size;
67 enum GNUNET_CONTAINER_HeapOrder type;
69 struct GNUNET_CONTAINER_heap_node *root;
71 struct GNUNET_CONTAINER_heap_node *traversal_pos;
77 * Returns element stored at root of tree, doesn't effect anything
79 * @param heap the heap
80 * @return NULL if the heap is empty
82 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
84 if ((heap == NULL) || (heap->root == NULL))
87 return heap->root->element;
91 next_power_of_2(int v)
103 internal_print (struct GNUNET_CONTAINER_heap_node *root)
105 fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
106 if (root->left_child != NULL)
108 fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
109 internal_print (root->left_child);
111 if (root->right_child != NULL)
113 fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
114 internal_print (root->right_child);
119 printTree (struct GNUNET_CONTAINER_Heap *root)
121 internal_print (root->root);
124 struct GNUNET_CONTAINER_Heap *
125 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
127 struct GNUNET_CONTAINER_Heap *heap;
128 heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
132 heap->traversal_pos = NULL;
139 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
141 while (heap->size > 0)
142 GNUNET_CONTAINER_heap_remove_root (heap);
147 struct GNUNET_CONTAINER_heap_node *
148 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
150 struct GNUNET_CONTAINER_heap_node *ret;
155 if (node->element == element)
158 if (node->left_child != NULL)
159 ret = find_element (node->left_child, element);
161 if ((ret == NULL) && (node->right_child != NULL))
162 ret = find_element (node->right_child, element);
167 static struct GNUNET_CONTAINER_heap_node *
168 getNextPos (struct GNUNET_CONTAINER_Heap *root)
170 struct GNUNET_CONTAINER_heap_node *ret;
171 struct GNUNET_CONTAINER_heap_node *parent;
175 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
176 pos = root->size + 1;
177 ret->left_child = NULL;
178 ret->right_child = NULL;
188 for (i = next_power_of_2(pos) >> 2; i > 1; i >>= 1)
190 if (((pos / i) % 2) == 0)
191 parent = parent->left_child;
193 parent = parent->right_child;
196 ret->parent = parent;
198 parent->left_child = ret;
200 parent->right_child = ret;
208 static struct GNUNET_CONTAINER_heap_node *
209 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
211 struct GNUNET_CONTAINER_heap_node *ret;
215 if (pos > root->size)
222 for (i = next_power_of_2(pos) >> 2; i > 0; i >>= 1)
224 if (((pos / i) % 2) == 0)
225 ret = ret->left_child;
227 ret = ret->right_child;
236 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
237 struct GNUNET_CONTAINER_heap_node *second,
238 struct GNUNET_CONTAINER_Heap *root)
241 GNUNET_CONTAINER_HeapCost temp_cost;
243 temp_element = first->element;
244 temp_cost = first->cost;
245 first->element = second->element;
246 first->cost = second->cost;
247 second->element = temp_element;
248 second->cost = temp_cost;
254 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
255 struct GNUNET_CONTAINER_Heap *root)
258 while ((pos->parent != NULL) &&
259 (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
260 && (pos->parent->cost < pos->cost))
261 || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
262 && (pos->parent->cost > pos->cost))))
264 swapNodes (pos, pos->parent, root);
274 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
275 struct GNUNET_CONTAINER_Heap *root)
277 struct GNUNET_CONTAINER_heap_node *switchNeighbor;
279 switchNeighbor = pos;
281 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
283 if ((pos->left_child != NULL)
284 && (pos->left_child->cost > switchNeighbor->cost))
286 switchNeighbor = pos->left_child;
289 if ((pos->right_child != NULL)
290 && (pos->right_child->cost > switchNeighbor->cost))
292 switchNeighbor = pos->right_child;
295 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
297 if ((pos->left_child != NULL)
298 && (pos->left_child->cost < switchNeighbor->cost))
300 switchNeighbor = pos->left_child;
303 if ((pos->right_child != NULL)
304 && (pos->right_child->cost < switchNeighbor->cost))
306 switchNeighbor = pos->right_child;
310 if (switchNeighbor != pos)
312 swapNodes (switchNeighbor, pos, root);
313 percolateDownHeap (switchNeighbor, root);
320 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
324 struct GNUNET_CONTAINER_heap_node *del_node;
325 struct GNUNET_CONTAINER_heap_node *last;
326 GNUNET_CONTAINER_HeapCost old_cost;
329 del_node = find_element (root->root, element);
331 if (del_node == NULL)
333 else if (del_node == root->root)
334 return GNUNET_CONTAINER_heap_remove_root (root);
336 ret = del_node->element;
337 last = getPos (root, root->size);
339 old_cost = del_node->cost;
340 del_node->element = last->element;
341 del_node->cost = last->cost;
343 if (last->parent->left_child == last)
344 last->parent->left_child = NULL;
345 if (last->parent->right_child == last)
346 last->parent->right_child = NULL;
348 if (root->traversal_pos == last)
350 root->traversal_pos = root->root;
355 if (del_node->cost > old_cost)
357 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
358 percolateHeap (del_node, root);
359 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
360 percolateDownHeap (del_node, root);
362 else if (del_node->cost < old_cost)
364 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
365 percolateDownHeap (del_node, root);
366 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
367 percolateHeap (del_node, root);
374 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
375 void *element, GNUNET_CONTAINER_HeapCost cost)
377 struct GNUNET_CONTAINER_heap_node *new_pos;
381 if (root->max_size > root->size)
383 new_pos = getNextPos (root);
384 new_pos->element = element;
385 new_pos->cost = cost;
388 percolateHeap (new_pos, root);
399 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
402 struct GNUNET_CONTAINER_heap_node *root_node;
403 struct GNUNET_CONTAINER_heap_node *last;
405 if ((root == NULL) || (root->size == 0) || (root->root == NULL))
408 root_node = root->root;
409 ret = root_node->element;
410 last = getPos (root, root->size);
412 if ((root_node == last) && (root->size == 1))
414 /* We are removing the last node in the heap! */
416 root->traversal_pos = NULL;
421 if (last->parent->left_child == last)
422 last->parent->left_child = NULL;
423 else if (last->parent->right_child == last)
424 last->parent->right_child = NULL;
426 root_node->element = last->element;
427 root_node->cost = last->cost;
429 if (root->traversal_pos == last)
431 root->traversal_pos = root->root;
436 percolateDownHeap (root->root, root);
441 updatedCost (struct GNUNET_CONTAINER_Heap *root,
442 struct GNUNET_CONTAINER_heap_node *node)
444 struct GNUNET_CONTAINER_heap_node *parent;
447 return GNUNET_SYSERR;
449 parent = node->parent;
451 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
452 && (node->cost > parent->cost))
453 percolateHeap (node, root);
454 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
455 && (node->cost < parent->cost))
456 percolateHeap (node, root);
457 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
458 percolateDownHeap (node, root);
459 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
460 percolateDownHeap (node, root);
467 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
469 GNUNET_CONTAINER_HeapCost new_cost)
471 struct GNUNET_CONTAINER_heap_node *node;
472 int ret = GNUNET_YES;
473 node = find_element (root->root, element);
477 node->cost = new_cost;
478 ret = updatedCost (root, node);
483 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
484 struct GNUNET_CONTAINER_heap_node *node,
485 GNUNET_CONTAINER_HeapIterator iterator, void *cls)
489 internal_iterator (root, node->left_child, iterator, cls);
490 internal_iterator (root, node->right_child, iterator, cls);
491 iterator (cls, node->element, node->cost);
495 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
496 GNUNET_CONTAINER_HeapIterator iterator,
499 internal_iterator (heap, heap->root, iterator, cls);
504 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
509 if ((root->traversal_pos == NULL) && (root->root != NULL))
511 root->traversal_pos = root->root;
514 if (root->traversal_pos == NULL)
517 element = root->traversal_pos->element;
519 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
524 root->traversal_pos = root->traversal_pos->right_child;
527 root->traversal_pos = root->traversal_pos->left_child;
536 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)