2 This file is part of GNUnet.
3 (C) 2008, 2009 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 * @file util/container_heap.c
23 * @brief Implementation of a heap
24 * @author Nathan Evans
25 * @author Christian Grothoff
29 #include "gnunet_util_lib.h"
37 struct GNUNET_CONTAINER_HeapNode
40 * Heap this node belongs to.
42 struct GNUNET_CONTAINER_Heap *heap;
47 struct GNUNET_CONTAINER_HeapNode *parent;
52 struct GNUNET_CONTAINER_HeapNode *left_child;
57 struct GNUNET_CONTAINER_HeapNode *right_child;
65 * Cost for this element.
67 GNUNET_CONTAINER_HeapCostType cost;
70 * Number of elements below this node in the heap
71 * (excluding this node itself).
73 unsigned int tree_size;
78 * Handle to a node in a heap.
80 struct GNUNET_CONTAINER_Heap
86 struct GNUNET_CONTAINER_HeapNode *root;
89 * Current position of our random walk.
91 struct GNUNET_CONTAINER_HeapNode *walk_pos;
94 * Number of elements in the heap.
99 * How is the heap sorted?
101 enum GNUNET_CONTAINER_HeapOrder order;
108 * Check if internal invariants hold for the given node.
110 * @param node subtree to check
113 check (const struct GNUNET_CONTAINER_HeapNode *node)
117 GNUNET_assert (node->tree_size ==
118 ((node->left_child ==
119 NULL) ? 0 : 1 + node->left_child->tree_size) +
120 ((node->right_child ==
121 NULL) ? 0 : 1 + node->right_child->tree_size));
122 check (node->left_child);
123 check (node->right_child);
127 #define CHECK(n) check(n)
129 #define CHECK(n) do {} while (0)
136 * @param order how should the heap be sorted?
137 * @return handle to the heap
139 struct GNUNET_CONTAINER_Heap *
140 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
142 struct GNUNET_CONTAINER_Heap *heap;
144 heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
151 * Destroys the heap. Only call on a heap that
154 * @param heap heap to destroy
157 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
159 GNUNET_break (heap->size == 0);
165 * Get element stored at root of heap.
167 * @param heap heap to inspect
168 * @return NULL if heap is empty
171 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
173 if (heap->root == NULL)
175 return heap->root->element;
180 * Get the current size of the heap
182 * @param heap the heap to get the size of
183 * @return number of elements stored
186 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
193 * Get the current cost of the node
195 * @param node the node to get the cost of
196 * @return cost of the node
198 GNUNET_CONTAINER_HeapCostType
199 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
206 * Iterate over the children of the given node.
208 * @param heap argument to give to iterator
209 * @param node node to iterate over
210 * @param iterator function to call on each node
211 * @param iterator_cls closure for iterator
212 * @return GNUNET_YES to continue to iterate
215 node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
216 struct GNUNET_CONTAINER_HeapNode *node,
217 GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
221 if (GNUNET_YES != node_iterator (heap,
222 node->left_child, iterator, iterator_cls))
224 if (GNUNET_YES != node_iterator (heap,
225 node->right_child, iterator, iterator_cls))
227 return iterator (iterator_cls, node, node->element, node->cost);
232 * Iterate over all entries in the heap.
234 * @param heap the heap
235 * @param iterator function to call on each entry
236 * @param iterator_cls closure for iterator
239 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
240 GNUNET_CONTAINER_HeapIterator iterator,
243 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
248 * Perform a random walk of the tree. The walk is biased
249 * towards elements closer to the root of the tree (since
250 * each walk starts at the root and ends at a random leaf).
251 * The heap internally tracks the current position of the
254 * @param heap heap to walk
255 * @return data stored at the next random node in the walk;
256 * NULL if the tree is empty.
259 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
261 struct GNUNET_CONTAINER_HeapNode *pos;
264 if (heap->root == NULL)
266 pos = heap->walk_pos;
269 element = pos->element;
271 = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2))
272 ? pos->right_child : pos->left_child;
278 * Insert the given node 'node' into the subtree starting
279 * at 'pos' (while keeping the tree somewhat balanced).
281 * @param heap heap to modify
282 * @param pos existing tree
283 * @param node node to insert (which may be a subtree itself)
286 insert_node (struct GNUNET_CONTAINER_Heap *heap,
287 struct GNUNET_CONTAINER_HeapNode *pos,
288 struct GNUNET_CONTAINER_HeapNode *node)
290 struct GNUNET_CONTAINER_HeapNode *parent;
292 GNUNET_assert (node->parent == NULL);
293 while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX)
294 ? (pos->cost >= node->cost) : (pos->cost <= node->cost))
296 /* node is descendent of pos */
297 pos->tree_size += (1 + node->tree_size);
298 if (pos->left_child == NULL)
300 pos->left_child = node;
304 if (pos->right_child == NULL)
306 pos->right_child = node;
310 /* keep it balanced by descending into smaller subtree */
311 if (pos->left_child->tree_size < pos->right_child->tree_size)
312 pos = pos->left_child;
314 pos = pos->right_child;
316 /* make 'node' parent of 'pos' */
317 parent = pos->parent;
319 node->parent = parent;
326 if (parent->left_child == pos)
327 parent->left_child = node;
329 parent->right_child = node;
331 /* insert 'pos' below 'node' */
332 insert_node (heap, node, pos);
338 * Inserts a new element into the heap.
340 * @param heap heap to modify
341 * @param element element to insert
342 * @param cost cost for the element
343 * @return node for the new element
345 struct GNUNET_CONTAINER_HeapNode *
346 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
347 void *element, GNUNET_CONTAINER_HeapCostType cost)
349 struct GNUNET_CONTAINER_HeapNode *node;
351 node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode));
353 node->element = element;
356 if (NULL == heap->root)
359 insert_node (heap, heap->root, node);
360 GNUNET_assert (heap->size == heap->root->tree_size + 1);
367 * Remove root of the heap.
369 * @param heap heap to modify
370 * @return element data stored at the root node, NULL if heap is empty
373 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
376 struct GNUNET_CONTAINER_HeapNode *root;
378 if (NULL == (root = heap->root))
382 if (root->left_child == NULL)
384 heap->root = root->right_child;
385 if (root->right_child != NULL)
386 root->right_child->parent = NULL;
388 else if (root->right_child == NULL)
390 heap->root = root->left_child;
391 root->left_child->parent = NULL;
395 root->left_child->parent = NULL;
396 root->right_child->parent = NULL;
397 heap->root = root->left_child;
398 insert_node (heap, heap->root, root->right_child);
402 GNUNET_assert (((heap->size == 0) &&
403 (heap->root == NULL)) ||
404 (heap->size == heap->root->tree_size + 1));
412 * Remove the given node 'node' from the tree and update
413 * the 'tree_size' fields accordingly. Preserves the
414 * children of 'node' and does NOT change the overall
415 * 'size' field of the tree.
418 remove_node (struct GNUNET_CONTAINER_HeapNode *node)
420 struct GNUNET_CONTAINER_HeapNode *ancestor;
421 struct GNUNET_CONTAINER_Heap *heap = node->heap;
423 /* update 'size' of the ancestors */
425 while (NULL != (ancestor = ancestor->parent))
426 ancestor->tree_size--;
428 /* update 'size' of node itself */
429 if (node->left_child != NULL)
430 node->tree_size -= (1 + node->left_child->tree_size);
431 if (node->right_child != NULL)
432 node->tree_size -= (1 + node->right_child->tree_size);
434 /* unlink 'node' itself and insert children in its place */
435 if (node->parent == NULL)
437 if (node->left_child != NULL)
439 heap->root = node->left_child;
440 node->left_child->parent = NULL;
441 if (node->right_child != NULL)
443 node->right_child->parent = NULL;
444 insert_node (heap, heap->root, node->right_child);
449 heap->root = node->right_child;
450 if (node->right_child != NULL)
451 node->right_child->parent = NULL;
456 if (node->parent->left_child == node)
457 node->parent->left_child = NULL;
459 node->parent->right_child = NULL;
460 if (node->left_child != NULL)
462 node->left_child->parent = NULL;
463 node->parent->tree_size -= (1 + node->left_child->tree_size);
464 insert_node (heap, node->parent, node->left_child);
466 if (node->right_child != NULL)
468 node->right_child->parent = NULL;
469 node->parent->tree_size -= (1 + node->right_child->tree_size);
470 insert_node (heap, node->parent, node->right_child);
474 node->left_child = NULL;
475 node->right_child = NULL;
476 GNUNET_assert (node->tree_size == 0);
482 * Removes a node from the heap.
484 * @param node node to remove
485 * @return element data stored at the node
488 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
491 struct GNUNET_CONTAINER_Heap *heap;
495 if (heap->walk_pos == node)
496 (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
500 if (heap->walk_pos == node)
501 heap->walk_pos = NULL;
505 GNUNET_assert (((heap->size == 0) &&
506 (heap->root == NULL)) ||
507 (heap->size == heap->root->tree_size + 1));
514 * Updates the cost of any node in the tree
516 * @param heap heap to modify
517 * @param node node for which the cost is to be changed
518 * @param new_cost new cost for the node
521 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
522 struct GNUNET_CONTAINER_HeapNode *node,
523 GNUNET_CONTAINER_HeapCostType new_cost)
526 GNUNET_assert (((heap->size == 0) &&
527 (heap->root == NULL)) ||
528 (heap->size == heap->root->tree_size + 1));
534 GNUNET_assert (((heap->size == 1) &&
535 (heap->root == NULL)) ||
536 (heap->size == heap->root->tree_size + 2));
538 node->cost = new_cost;
539 if (heap->root == NULL)
542 insert_node (heap, heap->root, node);
545 GNUNET_assert (((heap->size == 0) &&
546 (heap->root == NULL)) ||
547 (heap->size == heap->root->tree_size + 1));