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"
31 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
38 struct GNUNET_CONTAINER_HeapNode
41 * Heap this node belongs to.
43 struct GNUNET_CONTAINER_Heap *heap;
48 struct GNUNET_CONTAINER_HeapNode *parent;
53 struct GNUNET_CONTAINER_HeapNode *left_child;
58 struct GNUNET_CONTAINER_HeapNode *right_child;
66 * Cost for this element.
68 GNUNET_CONTAINER_HeapCostType cost;
71 * Number of elements below this node in the heap
72 * (excluding this node itself).
74 unsigned int tree_size;
79 * Handle to a node in a heap.
81 struct GNUNET_CONTAINER_Heap
87 struct GNUNET_CONTAINER_HeapNode *root;
90 * Current position of our random walk.
92 struct GNUNET_CONTAINER_HeapNode *walk_pos;
95 * Number of elements in the heap.
100 * How is the heap sorted?
102 enum GNUNET_CONTAINER_HeapOrder order;
109 * Check if internal invariants hold for the given node.
111 * @param node subtree to check
114 check (const struct GNUNET_CONTAINER_HeapNode *node)
118 GNUNET_assert (node->tree_size ==
119 ((node->left_child ==
120 NULL) ? 0 : 1 + node->left_child->tree_size) +
121 ((node->right_child ==
122 NULL) ? 0 : 1 + node->right_child->tree_size));
123 check (node->left_child);
124 check (node->right_child);
128 #define CHECK(n) check(n)
130 #define CHECK(n) do {} while (0)
137 * @param order how should the heap be sorted?
138 * @return handle to the heap
140 struct GNUNET_CONTAINER_Heap *
141 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
143 struct GNUNET_CONTAINER_Heap *heap;
145 heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
152 * Destroys the heap. Only call on a heap that
155 * @param heap heap to destroy
158 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
160 GNUNET_break (heap->size == 0);
166 * Get element stored at root of heap.
168 * @param heap heap to inspect
169 * @return NULL if heap is empty
172 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
174 if (heap->root == NULL)
176 return heap->root->element;
181 * Get the current size of the heap
183 * @param heap the heap to get the size of
184 * @return number of elements stored
187 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
194 * Get the current cost of the node
196 * @param node the node to get the cost of
197 * @return cost of the node
199 GNUNET_CONTAINER_HeapCostType
200 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
207 * Iterate over the children of the given node.
209 * @param heap argument to give to iterator
210 * @param node node to iterate over
211 * @param iterator function to call on each node
212 * @param iterator_cls closure for iterator
213 * @return GNUNET_YES to continue to iterate
216 node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
217 struct GNUNET_CONTAINER_HeapNode *node,
218 GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
223 node_iterator (heap, node->left_child, iterator, iterator_cls))
226 node_iterator (heap, node->right_child, iterator, iterator_cls))
228 return iterator (iterator_cls, node, node->element, node->cost);
233 * Iterate over all entries in the heap.
235 * @param heap the heap
236 * @param iterator function to call on each entry
237 * @param iterator_cls closure for iterator
240 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
241 GNUNET_CONTAINER_HeapIterator iterator,
244 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
249 * Perform a random walk of the tree. The walk is biased
250 * towards elements closer to the root of the tree (since
251 * each walk starts at the root and ends at a random leaf).
252 * The heap internally tracks the current position of the
255 * @param heap heap to walk
256 * @return data stored at the next random node in the walk;
257 * NULL if the tree is empty.
260 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
262 struct GNUNET_CONTAINER_HeapNode *pos;
265 if (heap->root == NULL)
267 pos = heap->walk_pos;
270 element = pos->element;
273 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
274 2)) ? pos->right_child : pos->left_child;
280 * Insert the given node 'node' into the subtree starting
281 * at 'pos' (while keeping the tree somewhat balanced).
283 * @param heap heap to modify
284 * @param pos existing tree
285 * @param node node to insert (which may be a subtree itself)
288 insert_node (struct GNUNET_CONTAINER_Heap *heap,
289 struct GNUNET_CONTAINER_HeapNode *pos,
290 struct GNUNET_CONTAINER_HeapNode *node)
292 struct GNUNET_CONTAINER_HeapNode *parent;
294 GNUNET_assert (node->parent == NULL);
295 while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
297 : (pos->cost <= node->cost))
299 /* node is descendent of pos */
300 pos->tree_size += (1 + node->tree_size);
301 if (pos->left_child == NULL)
303 pos->left_child = node;
307 if (pos->right_child == NULL)
309 pos->right_child = node;
313 /* keep it balanced by descending into smaller subtree */
314 if (pos->left_child->tree_size < pos->right_child->tree_size)
315 pos = pos->left_child;
317 pos = pos->right_child;
319 /* make 'node' parent of 'pos' */
320 parent = pos->parent;
322 node->parent = parent;
329 if (parent->left_child == pos)
330 parent->left_child = node;
332 parent->right_child = node;
334 /* insert 'pos' below 'node' */
335 insert_node (heap, node, pos);
341 * Inserts a new element into the heap.
343 * @param heap heap to modify
344 * @param element element to insert
345 * @param cost cost for the element
346 * @return node for the new element
348 struct GNUNET_CONTAINER_HeapNode *
349 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
350 GNUNET_CONTAINER_HeapCostType cost)
352 struct GNUNET_CONTAINER_HeapNode *node;
354 node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode));
356 node->element = element;
359 if (NULL == heap->root)
362 insert_node (heap, heap->root, node);
363 GNUNET_assert (heap->size == heap->root->tree_size + 1);
370 * Remove root of the heap.
372 * @param heap heap to modify
373 * @return element data stored at the root node, NULL if heap is empty
376 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
379 struct GNUNET_CONTAINER_HeapNode *root;
381 if (NULL == (root = heap->root))
385 if (root->left_child == NULL)
387 heap->root = root->right_child;
388 if (root->right_child != NULL)
389 root->right_child->parent = NULL;
391 else if (root->right_child == NULL)
393 heap->root = root->left_child;
394 root->left_child->parent = NULL;
398 root->left_child->parent = NULL;
399 root->right_child->parent = NULL;
400 heap->root = root->left_child;
401 insert_node (heap, heap->root, root->right_child);
405 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
406 (heap->size == heap->root->tree_size + 1));
414 * Remove the given node 'node' from the tree and update
415 * the 'tree_size' fields accordingly. Preserves the
416 * children of 'node' and does NOT change the overall
417 * 'size' field of the tree.
420 remove_node (struct GNUNET_CONTAINER_HeapNode *node)
422 struct GNUNET_CONTAINER_HeapNode *ancestor;
423 struct GNUNET_CONTAINER_Heap *heap = node->heap;
425 /* update 'size' of the ancestors */
427 while (NULL != (ancestor = ancestor->parent))
428 ancestor->tree_size--;
430 /* update 'size' of node itself */
431 if (node->left_child != NULL)
432 node->tree_size -= (1 + node->left_child->tree_size);
433 if (node->right_child != NULL)
434 node->tree_size -= (1 + node->right_child->tree_size);
436 /* unlink 'node' itself and insert children in its place */
437 if (node->parent == NULL)
439 if (node->left_child != NULL)
441 heap->root = node->left_child;
442 node->left_child->parent = NULL;
443 if (node->right_child != NULL)
445 node->right_child->parent = NULL;
446 insert_node (heap, heap->root, node->right_child);
451 heap->root = node->right_child;
452 if (node->right_child != NULL)
453 node->right_child->parent = NULL;
458 if (node->parent->left_child == node)
459 node->parent->left_child = NULL;
461 node->parent->right_child = NULL;
462 if (node->left_child != NULL)
464 node->left_child->parent = NULL;
465 node->parent->tree_size -= (1 + node->left_child->tree_size);
466 insert_node (heap, node->parent, node->left_child);
468 if (node->right_child != NULL)
470 node->right_child->parent = NULL;
471 node->parent->tree_size -= (1 + node->right_child->tree_size);
472 insert_node (heap, node->parent, node->right_child);
476 node->left_child = NULL;
477 node->right_child = NULL;
478 GNUNET_assert (node->tree_size == 0);
484 * Removes a node from the heap.
486 * @param node node to remove
487 * @return element data stored at the node
490 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
493 struct GNUNET_CONTAINER_Heap *heap;
497 if (heap->walk_pos == node)
498 (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
502 if (heap->walk_pos == node)
503 heap->walk_pos = NULL;
507 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
508 (heap->size == heap->root->tree_size + 1));
515 * Updates the cost of any node in the tree
517 * @param heap heap to modify
518 * @param node node for which the cost is to be changed
519 * @param new_cost new cost for the node
522 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
523 struct GNUNET_CONTAINER_HeapNode *node,
524 GNUNET_CONTAINER_HeapCostType new_cost)
527 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
528 (heap->size == heap->root->tree_size + 1));
534 GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) ||
535 (heap->size == heap->root->tree_size + 2));
537 node->cost = new_cost;
538 if (heap->root == NULL)
541 insert_node (heap, heap->root, node);
544 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
545 (heap->size == heap->root->tree_size + 1));