2 This file is part of GNUnet.
3 Copyright (C) 2008, 2009 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your 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 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
22 * @file util/container_heap.c
23 * @brief Implementation of a heap
24 * @author Nathan Evans
25 * @author Christian Grothoff
29 #include "gnunet_container_lib.h"
31 #define LOG(kind, ...) GNUNET_log_from (kind, "util-container-heap", \
34 #define EXTRA_CHECKS 0
39 struct GNUNET_CONTAINER_HeapNode
42 * Heap this node belongs to.
44 struct GNUNET_CONTAINER_Heap *heap;
49 struct GNUNET_CONTAINER_HeapNode *parent;
54 struct GNUNET_CONTAINER_HeapNode *left_child;
59 struct GNUNET_CONTAINER_HeapNode *right_child;
67 * Cost for this element.
69 GNUNET_CONTAINER_HeapCostType cost;
72 * Number of elements below this node in the heap
73 * (excluding this node itself).
75 unsigned int tree_size;
79 * Handle to a node in a heap.
81 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;
107 * Check if internal invariants hold for the given node.
109 * @param node subtree to check
112 check (const struct GNUNET_CONTAINER_HeapNode *node)
116 GNUNET_assert (node->tree_size ==
117 ((node->left_child ==
118 NULL) ? 0 : 1 + node->left_child->tree_size)
119 + ((node->right_child ==
120 NULL) ? 0 : 1 + node->right_child->tree_size));
121 check (node->left_child);
122 check (node->right_child);
126 #define CHECK(n) check (n)
128 #define CHECK(n) do {} while (0)
135 * @param order how should the heap be sorted?
136 * @return handle to the heap
138 struct GNUNET_CONTAINER_Heap *
139 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
141 struct GNUNET_CONTAINER_Heap *heap;
143 heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
150 * Destroys the heap. Only call on a heap that
153 * @param heap heap to destroy
156 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
158 GNUNET_break (heap->size == 0);
164 * Get element stored at the root of @a heap.
166 * @param heap Heap to inspect.
167 * @return Element at the root, or NULL if heap is empty.
170 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
172 if (heap->root == NULL)
174 return heap->root->element;
179 * Get @a element and @a cost stored at the root of @a heap.
181 * @param[in] heap Heap to inspect.
182 * @param[out] element Root element is returned here.
183 * @param[out] cost Cost of @a element is returned here.
184 * @return #GNUNET_YES if an element is returned,
185 * #GNUNET_NO if the heap is empty.
188 GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
190 GNUNET_CONTAINER_HeapCostType *cost)
192 if (NULL == heap->root)
195 *element = heap->root->element;
197 *cost = heap->root->cost;
203 * Get the current size of the heap
205 * @param heap the heap to get the size of
206 * @return number of elements stored
209 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
216 * Get the current cost of the node
218 * @param node the node to get the cost of
219 * @return cost of the node
221 GNUNET_CONTAINER_HeapCostType
222 GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
230 * Iterate over the children of the given node.
232 * @param heap argument to give to iterator
233 * @param node node to iterate over
234 * @param iterator function to call on each node
235 * @param iterator_cls closure for iterator
236 * @return GNUNET_YES to continue to iterate
239 node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
240 struct GNUNET_CONTAINER_HeapNode *node,
241 GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
246 node_iterator (heap, node->left_child, iterator, iterator_cls))
249 node_iterator (heap, node->right_child, iterator, iterator_cls))
251 return iterator (iterator_cls, node, node->element, node->cost);
256 * Iterate over all entries in the heap.
258 * @param heap the heap
259 * @param iterator function to call on each entry
260 * @param iterator_cls closure for iterator
263 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
264 GNUNET_CONTAINER_HeapIterator iterator,
267 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
272 * Perform a random walk of the tree. The walk is biased
273 * towards elements closer to the root of the tree (since
274 * each walk starts at the root and ends at a random leaf).
275 * The heap internally tracks the current position of the
278 * @param heap heap to walk
279 * @return data stored at the next random node in the walk;
280 * NULL if the tree is empty.
283 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
285 struct GNUNET_CONTAINER_HeapNode *pos;
288 if (heap->root == NULL)
290 pos = heap->walk_pos;
293 element = pos->element;
296 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
297 2)) ? pos->right_child : pos->left_child;
303 * Insert the given node 'node' into the subtree starting
304 * at 'pos' (while keeping the tree somewhat balanced).
306 * @param heap heap to modify
307 * @param pos existing tree
308 * @param node node to insert (which may be a subtree itself)
311 insert_node (struct GNUNET_CONTAINER_Heap *heap,
312 struct GNUNET_CONTAINER_HeapNode *pos,
313 struct GNUNET_CONTAINER_HeapNode *node)
315 struct GNUNET_CONTAINER_HeapNode *parent;
317 GNUNET_assert (node->parent == NULL);
318 while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
320 : (pos->cost <= node->cost))
322 /* node is descendent of pos */
323 pos->tree_size += (1 + node->tree_size);
324 if (pos->left_child == NULL)
326 pos->left_child = node;
330 if (pos->right_child == NULL)
332 pos->right_child = node;
336 /* keep it balanced by descending into smaller subtree */
337 if (pos->left_child->tree_size < pos->right_child->tree_size)
338 pos = pos->left_child;
340 pos = pos->right_child;
342 /* make 'node' parent of 'pos' */
343 parent = pos->parent;
345 node->parent = parent;
352 if (parent->left_child == pos)
353 parent->left_child = node;
355 parent->right_child = node;
357 /* insert 'pos' below 'node' */
358 insert_node (heap, node, pos);
364 * Inserts a new element into the heap.
366 * @param heap heap to modify
367 * @param element element to insert
368 * @param cost cost for the element
369 * @return node for the new element
371 struct GNUNET_CONTAINER_HeapNode *
372 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
373 GNUNET_CONTAINER_HeapCostType cost)
375 struct GNUNET_CONTAINER_HeapNode *node;
377 node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
379 node->element = element;
382 if (NULL == heap->root)
385 insert_node (heap, heap->root, node);
386 GNUNET_assert (heap->size == heap->root->tree_size + 1);
393 * Remove root of the heap.
395 * @param heap heap to modify
396 * @return element data stored at the root node, NULL if heap is empty
399 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
402 struct GNUNET_CONTAINER_HeapNode *root;
404 if (NULL == (root = heap->root))
408 if (root->left_child == NULL)
410 heap->root = root->right_child;
411 if (root->right_child != NULL)
412 root->right_child->parent = NULL;
414 else if (root->right_child == NULL)
416 heap->root = root->left_child;
417 root->left_child->parent = NULL;
421 root->left_child->parent = NULL;
422 root->right_child->parent = NULL;
423 heap->root = root->left_child;
424 insert_node (heap, heap->root, root->right_child);
426 if (heap->walk_pos == root)
427 heap->walk_pos = heap->root;
430 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
431 (heap->size == heap->root->tree_size + 1));
439 * Remove the given node 'node' from the tree and update
440 * the 'tree_size' fields accordingly. Preserves the
441 * children of 'node' and does NOT change the overall
442 * 'size' field of the tree.
445 remove_node (struct GNUNET_CONTAINER_HeapNode *node)
447 struct GNUNET_CONTAINER_HeapNode *ancestor;
448 struct GNUNET_CONTAINER_Heap *heap = node->heap;
450 /* update 'size' of the ancestors */
452 while (NULL != (ancestor = ancestor->parent))
453 ancestor->tree_size--;
455 /* update 'size' of node itself */
456 if (node->left_child != NULL)
457 node->tree_size -= (1 + node->left_child->tree_size);
458 if (node->right_child != NULL)
459 node->tree_size -= (1 + node->right_child->tree_size);
461 /* unlink 'node' itself and insert children in its place */
462 if (node->parent == NULL)
464 if (node->left_child != NULL)
466 heap->root = node->left_child;
467 node->left_child->parent = NULL;
468 if (node->right_child != NULL)
470 node->right_child->parent = NULL;
471 insert_node (heap, heap->root, node->right_child);
476 heap->root = node->right_child;
477 if (node->right_child != NULL)
478 node->right_child->parent = NULL;
483 if (node->parent->left_child == node)
484 node->parent->left_child = NULL;
486 node->parent->right_child = NULL;
487 if (node->left_child != NULL)
489 node->left_child->parent = NULL;
490 node->parent->tree_size -= (1 + node->left_child->tree_size);
491 insert_node (heap, node->parent, node->left_child);
493 if (node->right_child != NULL)
495 node->right_child->parent = NULL;
496 node->parent->tree_size -= (1 + node->right_child->tree_size);
497 insert_node (heap, node->parent, node->right_child);
501 node->left_child = NULL;
502 node->right_child = NULL;
503 GNUNET_assert (node->tree_size == 0);
509 * Removes a node from the heap.
511 * @param node node to remove
512 * @return element data stored at the node
515 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
518 struct GNUNET_CONTAINER_Heap *heap;
522 if (heap->walk_pos == node)
523 (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
527 if (heap->walk_pos == node)
528 heap->walk_pos = NULL;
532 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
533 (heap->size == heap->root->tree_size + 1));
540 * Updates the cost of any node in the tree
542 * @param node node for which the cost is to be changed
543 * @param new_cost new cost for the node
546 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
547 GNUNET_CONTAINER_HeapCostType new_cost)
549 struct GNUNET_CONTAINER_Heap *heap = node->heap;
552 node->cost = new_cost;
553 if (NULL == heap->root)