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
42 struct GNUNET_CONTAINER_HeapNode *parent;
47 struct GNUNET_CONTAINER_HeapNode *left_child;
52 struct GNUNET_CONTAINER_HeapNode *right_child;
60 * Cost for this element.
62 GNUNET_CONTAINER_HeapCostType cost;
65 * Number of elements below this node in the heap
66 * (excluding this node itself).
68 unsigned int tree_size;
73 * Handle to a node in a heap.
75 struct GNUNET_CONTAINER_Heap
81 struct GNUNET_CONTAINER_HeapNode *root;
84 * Current position of our random walk.
86 struct GNUNET_CONTAINER_HeapNode *walk_pos;
89 * Number of elements in the heap.
94 * How is the heap sorted?
96 enum GNUNET_CONTAINER_HeapOrder order;
103 * Check if internal invariants hold for the given node.
105 * @param node subtree to check
108 check (const struct GNUNET_CONTAINER_HeapNode *node)
112 GNUNET_assert (node->tree_size ==
113 ( (node->left_child == NULL) ? 0 : 1 + node->left_child->tree_size) +
114 ( (node->right_child == NULL) ? 0 : 1 + node->right_child->tree_size) );
115 check (node->left_child);
116 check (node->right_child);
120 #define CHECK(n) check(n)
122 #define CHECK(n) do {} while (0)
129 * @param order how should the heap be sorted?
130 * @return handle to the heap
132 struct GNUNET_CONTAINER_Heap *
133 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
135 struct GNUNET_CONTAINER_Heap *heap;
137 heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap));
138 heap->walk_pos = NULL;
147 * Destroys the heap. Only call on a heap that
150 * @param heap heap to destroy
153 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
155 GNUNET_break (heap->size == 0);
161 * Get element stored at root of heap.
163 * @param heap heap to inspect
164 * @return NULL if heap is empty
167 GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
169 if (heap->root == NULL)
171 return heap->root->element;
176 * Get the current size of the heap
178 * @param heap the heap to get the size of
179 * @return number of elements stored
182 GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
189 * Iterate over the children of the given node.
191 * @param heap argument to give to iterator
192 * @param node node to iterate over
193 * @param iterator function to call on each node
194 * @param iterator_cls closure for iterator
195 * @return GNUNET_YES to continue to iterate
198 node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
199 struct GNUNET_CONTAINER_HeapNode *node,
200 GNUNET_CONTAINER_HeapIterator iterator,
205 if (GNUNET_YES != node_iterator (heap,
210 if (GNUNET_YES != node_iterator (heap,
215 return iterator (iterator_cls,
223 * Iterate over all entries in the heap.
225 * @param heap the heap
226 * @param iterator function to call on each entry
227 * @param iterator_cls closure for iterator
230 GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
231 GNUNET_CONTAINER_HeapIterator iterator,
234 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
239 * Perform a random walk of the tree. The walk is biased
240 * towards elements closer to the root of the tree (since
241 * each walk starts at the root and ends at a random leaf).
242 * The heap internally tracks the current position of the
245 * @param heap heap to walk
246 * @return data stored at the next random node in the walk;
247 * NULL if the tree is empty.
250 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
252 struct GNUNET_CONTAINER_HeapNode *pos;
255 if (heap->root == NULL)
257 pos = heap->walk_pos;
260 element = pos->element;
262 = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2))
270 * Insert the given node 'node' into the subtree starting
271 * at 'pos' (while keeping the tree somewhat balanced).
273 * @param heap heap to modify
274 * @param pos existing tree
275 * @param node node to insert (which may be a subtree itself)
278 insert_node (struct GNUNET_CONTAINER_Heap *heap,
279 struct GNUNET_CONTAINER_HeapNode *pos,
280 struct GNUNET_CONTAINER_HeapNode *node)
282 struct GNUNET_CONTAINER_HeapNode *parent;
284 GNUNET_assert (node->parent == NULL);
285 while ( (heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX)
286 ? (pos->cost >= node->cost)
287 : (pos->cost <= node->cost) )
289 /* node is descendent of pos */
290 pos->tree_size += (1 + node->tree_size);
291 if (pos->left_child == NULL)
293 pos->left_child = node;
297 if (pos->right_child == NULL)
299 pos->right_child = node;
303 /* keep it balanced by descending into smaller subtree */
304 if (pos->left_child->tree_size < pos->right_child->tree_size)
305 pos = pos->left_child;
307 pos = pos->right_child;
309 /* make 'node' parent of 'pos' */
310 parent = pos->parent;
312 node->parent = parent;
319 if (parent->left_child == pos)
320 parent->left_child = node;
322 parent->right_child = node;
324 /* insert 'pos' below 'node' */
325 insert_node (heap, node, pos);
331 * Inserts a new element into the heap.
333 * @param heap heap to modify
334 * @param element element to insert
335 * @param cost cost for the element
336 * @return node for the new element
338 struct GNUNET_CONTAINER_HeapNode *
339 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
341 GNUNET_CONTAINER_HeapCostType cost)
343 struct GNUNET_CONTAINER_HeapNode *node;
345 node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode));
346 node->element = element;
349 if (NULL == heap->root)
352 insert_node (heap, heap->root, node);
353 GNUNET_assert (heap->size == heap->root->tree_size + 1);
360 * Remove root of the heap.
362 * @param heap heap to modify
363 * @return element data stored at the root node, NULL if heap is empty
366 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
369 struct GNUNET_CONTAINER_HeapNode *root;
371 if (NULL == (root = heap->root))
375 if (root->left_child == NULL)
377 heap->root = root->right_child;
378 if (root->right_child != NULL)
379 root->right_child->parent = NULL;
381 else if (root->right_child == NULL)
383 heap->root = root->left_child;
384 if (root->left_child != NULL)
385 root->left_child->parent = NULL;
389 root->left_child->parent = NULL;
390 root->right_child->parent = NULL;
391 heap->root = root->left_child;
392 insert_node (heap, heap->root, root->right_child);
396 GNUNET_assert (( (heap->size == 0) &&
397 (heap->root == NULL) ) ||
398 (heap->size == heap->root->tree_size + 1) );
406 * Remove the given node 'node' from the tree and update
407 * the 'tree_size' fields accordingly. Preserves the
408 * children of 'node' and does NOT change the overall
409 * 'size' field of the tree.
412 remove_node (struct GNUNET_CONTAINER_Heap *heap,
413 struct GNUNET_CONTAINER_HeapNode *node)
415 struct GNUNET_CONTAINER_HeapNode *ancestor;
417 /* update 'size' of the ancestors */
419 while (NULL != (ancestor = ancestor->parent))
420 ancestor->tree_size--;
422 /* update 'size' of node itself */
423 if (node->left_child != NULL)
424 node->tree_size -= (1 + node->left_child->tree_size);
425 if (node->right_child != NULL)
426 node->tree_size -= (1 + node->right_child->tree_size);
428 /* unlink 'node' itself and insert children in its place */
429 if (node->parent == NULL)
431 if (node->left_child != NULL)
433 heap->root = node->left_child;
434 node->left_child->parent = NULL;
435 if (node->right_child != NULL)
437 node->right_child->parent = NULL;
438 insert_node (heap, heap->root, node->right_child);
443 heap->root = node->right_child;
444 if (node->right_child != NULL)
445 node->right_child->parent = NULL;
450 if (node->parent->left_child == node)
451 node->parent->left_child = NULL;
453 node->parent->right_child = NULL;
454 if (node->left_child != NULL)
456 node->left_child->parent = NULL;
457 node->parent->tree_size -= (1 + node->left_child->tree_size);
458 insert_node (heap, node->parent, node->left_child);
460 if (node->right_child != NULL)
462 node->right_child->parent = NULL;
463 node->parent->tree_size -= (1 + node->right_child->tree_size);
464 insert_node (heap, node->parent, node->right_child);
468 node->left_child = NULL;
469 node->right_child = NULL;
470 GNUNET_assert (node->tree_size == 0);
476 * Removes a node from the heap.
478 * @param heap heap to modify
479 * @param node node to remove
480 * @return element data stored at the node
483 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap,
484 struct GNUNET_CONTAINER_HeapNode *node)
489 if (heap->walk_pos == node)
490 (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
491 remove_node (heap, node);
494 if (heap->walk_pos == node)
495 heap->walk_pos = NULL;
499 GNUNET_assert (( (heap->size == 0) &&
500 (heap->root == NULL) ) ||
501 (heap->size == heap->root->tree_size + 1) );
508 * Updates the cost of any node in the tree
510 * @param heap heap to modify
511 * @param node node for which the cost is to be changed
512 * @param new_cost new cost for the node
515 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
516 struct GNUNET_CONTAINER_HeapNode *node,
517 GNUNET_CONTAINER_HeapCostType new_cost)
520 GNUNET_assert ( ( (heap->size == 0) &&
521 (heap->root == NULL) ) ||
522 (heap->size == heap->root->tree_size + 1) );
525 remove_node (heap, node);
528 GNUNET_assert ( ( (heap->size == 1) &&
529 (heap->root == NULL) ) ||
530 (heap->size == heap->root->tree_size + 2) );
532 node->cost = new_cost;
533 if (heap->root == NULL)
536 insert_node (heap, heap->root, node);
539 GNUNET_assert ( ( (heap->size == 0) &&
540 (heap->root == NULL) ) ||
541 (heap->size == heap->root->tree_size + 1) );