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)
89 internal_print (struct GNUNET_CONTAINER_heap_node *root)
91 fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
92 if (root->left_child != NULL)
94 fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
95 internal_print (root->left_child);
97 if (root->right_child != NULL)
99 fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
100 internal_print (root->right_child);
105 printTree (struct GNUNET_CONTAINER_Heap *root)
107 internal_print (root->root);
110 struct GNUNET_CONTAINER_Heap *
111 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
113 struct GNUNET_CONTAINER_Heap *heap;
114 heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
118 heap->traversal_pos = NULL;
125 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
128 while (heap->size > 0)
130 unused = GNUNET_CONTAINER_heap_remove_root (heap);
137 struct GNUNET_CONTAINER_heap_node *
138 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
140 struct GNUNET_CONTAINER_heap_node *ret;
142 if ((node != NULL) && (node->element == element))
147 if ((ret == NULL) && (node->left_child != NULL))
149 ret = find_element (node->left_child, element);
152 if ((ret == NULL) && (node->right_child != NULL))
154 ret = find_element (node->right_child, element);
160 static struct GNUNET_CONTAINER_heap_node *
161 getNextPos (struct GNUNET_CONTAINER_Heap *root)
163 struct GNUNET_CONTAINER_heap_node *ret;
164 struct GNUNET_CONTAINER_heap_node *parent;
169 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
170 pos = root->size + 1;
171 depth = (int) log2 (pos);
172 ret->left_child = NULL;
173 ret->right_child = NULL;
183 for (i = depth; i > 1; i--)
185 if (((pos / (1 << (i - 1))) % 2) == 0)
186 parent = parent->left_child;
188 parent = parent->right_child;
191 ret->parent = parent;
193 parent->left_child = ret;
195 parent->right_child = ret;
203 static struct GNUNET_CONTAINER_heap_node *
204 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
206 struct GNUNET_CONTAINER_heap_node *ret;
211 depth = (int) log2 (pos);
213 if (pos > root->size)
220 for (i = depth; i > 0; i--)
222 if (((pos / (1 << (i - 1))) % 2) == 0)
223 ret = ret->left_child;
225 ret = ret->right_child;
234 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
235 struct GNUNET_CONTAINER_heap_node *second,
236 struct GNUNET_CONTAINER_Heap *root)
239 GNUNET_CONTAINER_HeapCost temp_cost;
241 temp_element = first->element;
242 temp_cost = first->cost;
243 first->element = second->element;
244 first->cost = second->cost;
245 second->element = temp_element;
246 second->cost = temp_cost;
249 * I still worry that there is some good reason for
250 * elements being location aware... but it eludes me
252 if ((root->type == GNUNET_DV_MAX_HEAP))
254 first->neighbor->max_loc = first;
255 second->neighbor->max_loc = second;
257 else if ((root->type == GNUNET_DV_MIN_HEAP))
259 first->neighbor->min_loc = first;
260 second->neighbor->min_loc = second;
267 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
268 struct GNUNET_CONTAINER_Heap *root)
271 while ((pos->parent != NULL) &&
272 (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
273 && (pos->parent->cost < pos->cost))
274 || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
275 && (pos->parent->cost > pos->cost))))
277 swapNodes (pos, pos->parent, root);
287 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
288 struct GNUNET_CONTAINER_Heap *root)
290 struct GNUNET_CONTAINER_heap_node *switchNeighbor;
292 switchNeighbor = pos;
294 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
296 if ((pos->left_child != NULL)
297 && (pos->left_child->cost > switchNeighbor->cost))
299 switchNeighbor = pos->left_child;
302 if ((pos->right_child != NULL)
303 && (pos->right_child->cost > switchNeighbor->cost))
305 switchNeighbor = pos->right_child;
308 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
310 if ((pos->left_child != NULL)
311 && (pos->left_child->cost < switchNeighbor->cost))
313 switchNeighbor = pos->left_child;
316 if ((pos->right_child != NULL)
317 && (pos->right_child->cost < switchNeighbor->cost))
319 switchNeighbor = pos->right_child;
323 if (switchNeighbor != pos)
325 swapNodes (switchNeighbor, pos, root);
326 percolateDownHeap (switchNeighbor, root);
333 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
337 struct GNUNET_CONTAINER_heap_node *del_node;
338 struct GNUNET_CONTAINER_heap_node *last;
339 GNUNET_CONTAINER_HeapCost old_cost;
342 del_node = find_element (root->root, element);
344 if (del_node == NULL)
346 else if (del_node == root->root)
347 return GNUNET_CONTAINER_heap_remove_root (root);
349 ret = del_node->element;
350 last = getPos (root, root->size);
352 old_cost = del_node->cost;
353 del_node->element = last->element;
354 del_node->cost = last->cost;
356 if (last->parent->left_child == last)
357 last->parent->left_child = NULL;
358 if (last->parent->right_child == last)
359 last->parent->right_child = NULL;
361 if (root->traversal_pos == last)
363 root->traversal_pos = root->root;
368 if (del_node->cost > old_cost)
370 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
371 percolateHeap (del_node, root);
372 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
373 percolateDownHeap (del_node, root);
375 else if (del_node->cost < old_cost)
377 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
378 percolateDownHeap (del_node, root);
379 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
380 percolateHeap (del_node, root);
387 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
388 void *element, GNUNET_CONTAINER_HeapCost cost)
390 struct GNUNET_CONTAINER_heap_node *new_pos;
394 if (root->max_size > root->size)
396 new_pos = getNextPos (root);
397 new_pos->element = element;
398 new_pos->cost = cost;
400 /*We no longer can tolerate pointers between heaps :( */
401 /*if (root->type == GNUNET_DV_MIN_HEAP)
402 new_pos->neighbor->min_loc = new_pos;
403 else if (root->type == GNUNET_DV_MAX_HEAP)
404 new_pos->neighbor->max_loc = new_pos; */
406 percolateHeap (new_pos, root);
417 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
420 struct GNUNET_CONTAINER_heap_node *root_node;
421 struct GNUNET_CONTAINER_heap_node *last;
423 root_node = root->root;
424 ret = root_node->element;
425 last = getPos (root, root->size);
427 if ((root_node == last) && (root->size == 1))
429 /* We are removing the last node in the heap! */
431 root->traversal_pos = NULL;
436 if (last->parent->left_child == last)
437 last->parent->left_child = NULL;
438 else if (last->parent->right_child == last)
439 last->parent->right_child = NULL;
441 root_node->element = last->element;
442 root_node->cost = last->cost;
444 if (root->traversal_pos == last)
446 root->traversal_pos = root->root;
451 percolateDownHeap (root->root, root);
456 updatedCost (struct GNUNET_CONTAINER_Heap *root,
457 struct GNUNET_CONTAINER_heap_node *node)
459 struct GNUNET_CONTAINER_heap_node *parent;
462 return GNUNET_SYSERR;
464 parent = node->parent;
466 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
467 && (node->cost > parent->cost))
468 percolateHeap (node, root);
469 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
470 && (node->cost < parent->cost))
471 percolateHeap (node, root);
472 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
473 percolateDownHeap (node, root);
474 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
475 percolateDownHeap (node, root);
482 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
484 GNUNET_CONTAINER_HeapCost new_cost)
486 struct GNUNET_CONTAINER_heap_node *node;
487 int ret = GNUNET_YES;
488 node = find_element (root->root, element);
492 node->cost = new_cost;
493 ret = updatedCost (root, node);
498 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
499 struct GNUNET_CONTAINER_heap_node *node,
500 GNUNET_CONTAINER_HeapIterator iterator, void *cls)
504 internal_iterator (root, node->left_child, iterator, cls);
505 internal_iterator (root, node->right_child, iterator, cls);
506 iterator (cls, node->element, node->cost);
510 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
511 GNUNET_CONTAINER_HeapIterator iterator,
514 internal_iterator (heap, heap->root, iterator, cls);
519 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
524 if ((root->traversal_pos == NULL) && (root->root != NULL))
526 root->traversal_pos = root->root;
529 if (root->traversal_pos == NULL)
532 element = root->traversal_pos->element;
534 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
539 root->traversal_pos = root->traversal_pos->right_child;
542 root->traversal_pos = root->traversal_pos->left_child;
551 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)