/*
- This file is part of GNUnet.
- (C) 2008 Christian Grothoff (and other contributing authors)
-
- GNUnet is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published
- by the Free Software Foundation; either version 2, or (at your
- option) any later version.
-
- GNUnet is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
- */
+ This file is part of GNUnet.
+ Copyright (C) 2008, 2009 GNUnet e.V.
+
+ GNUnet is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; either version 3, or (at your
+ option) any later version.
+
+ GNUnet is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING. If not, write to the
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
+*/
/**
- * @author Nathan Evans
* @file util/container_heap.c
- * @brief Implementation of heap operations
+ * @brief Implementation of a heap
+ * @author Nathan Evans
+ * @author Christian Grothoff
*/
#include "platform.h"
-#include "gnunet_protocols.h"
-#include "gnunet_util_lib.h"
+#include "gnunet_container_lib.h"
-/*
- * Struct that is stored in hashmap, pointers to
- * locations in min_heap and max_heap.
- */
-struct GNUNET_CONTAINER_heap_info
-{
- struct GNUNET_CONTAINER_heap_node *min_loc;
-
- struct GNUNET_CONTAINER_heap_node *max_loc;
+#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
-};
+#define EXTRA_CHECKS 0
-/*
- * Generic heap node structure, contains pointer to parent
- * left child, right child, and actual neighbor.
+/**
+ * Node in the heap.
*/
-struct GNUNET_CONTAINER_heap_node
+struct GNUNET_CONTAINER_HeapNode
{
- struct GNUNET_CONTAINER_heap_node *parent;
+ /**
+ * Heap this node belongs to.
+ */
+ struct GNUNET_CONTAINER_Heap *heap;
- struct GNUNET_CONTAINER_heap_node *left_child;
+ /**
+ * Parent node.
+ */
+ struct GNUNET_CONTAINER_HeapNode *parent;
- struct GNUNET_CONTAINER_heap_node *right_child;
+ /**
+ * Left child.
+ */
+ struct GNUNET_CONTAINER_HeapNode *left_child;
- GNUNET_CONTAINER_HeapCost cost;
+ /**
+ * Right child.
+ */
+ struct GNUNET_CONTAINER_HeapNode *right_child;
+ /**
+ * Our element.
+ */
void *element;
+ /**
+ * Cost for this element.
+ */
+ GNUNET_CONTAINER_HeapCostType cost;
+
+ /**
+ * Number of elements below this node in the heap
+ * (excluding this node itself).
+ */
+ unsigned int tree_size;
+
};
+/**
+ * Handle to a node in a heap.
+ */
struct GNUNET_CONTAINER_Heap
{
- unsigned int size;
- unsigned int max_size;
+ /**
+ * Root of the heap.
+ */
+ struct GNUNET_CONTAINER_HeapNode *root;
- enum GNUNET_CONTAINER_HeapOrder type;
+ /**
+ * Current position of our random walk.
+ */
+ struct GNUNET_CONTAINER_HeapNode *walk_pos;
- struct GNUNET_CONTAINER_heap_node *root;
+ /**
+ * Number of elements in the heap.
+ */
+ unsigned int size;
- struct GNUNET_CONTAINER_heap_node *traversal_pos;
+ /**
+ * How is the heap sorted?
+ */
+ enum GNUNET_CONTAINER_HeapOrder order;
};
+#if EXTRA_CHECKS
/**
- * Returns element stored at root of tree, doesn't effect anything
+ * Check if internal invariants hold for the given node.
*
- * @param heap the heap
- * @return NULL if the heap is empty
+ * @param node subtree to check
*/
-void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
-{
- if ((heap == NULL) || (heap->root == NULL))
- return NULL;
-
- return heap->root->element;
-}
-
-static int
-next_power_of_2(int v)
-{
- v |= v >> 1;
- v |= v >> 2;
- v |= v >> 4;
- v |= v >> 8;
- v |= v >> 16;
- v++;
- return v;
-}
-
-#if 0
static void
-internal_print (struct GNUNET_CONTAINER_heap_node *root)
+check (const struct GNUNET_CONTAINER_HeapNode *node)
{
- fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
- if (root->left_child != NULL)
- {
- fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
- internal_print (root->left_child);
- }
- if (root->right_child != NULL)
- {
- fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
- internal_print (root->right_child);
- }
+ if (NULL == node)
+ return;
+ GNUNET_assert (node->tree_size ==
+ ((node->left_child ==
+ NULL) ? 0 : 1 + node->left_child->tree_size) +
+ ((node->right_child ==
+ NULL) ? 0 : 1 + node->right_child->tree_size));
+ check (node->left_child);
+ check (node->right_child);
}
-static void
-printTree (struct GNUNET_CONTAINER_Heap *root)
-{
- internal_print (root->root);
-}
+
+#define CHECK(n) check(n)
+#else
+#define CHECK(n) do {} while (0)
#endif
+
+/**
+ * Create a new heap.
+ *
+ * @param order how should the heap be sorted?
+ * @return handle to the heap
+ */
struct GNUNET_CONTAINER_Heap *
-GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
+GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
{
struct GNUNET_CONTAINER_Heap *heap;
- heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
- heap->max_size = -1;
- heap->type = type;
- heap->root = NULL;
- heap->traversal_pos = NULL;
- heap->size = 0;
+ heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
+ heap->order = order;
return heap;
}
+
+/**
+ * Destroys the heap. Only call on a heap that
+ * is already empty.
+ *
+ * @param heap heap to destroy
+ */
void
GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
{
- while (heap->size > 0)
- GNUNET_CONTAINER_heap_remove_root (heap);
+ GNUNET_break (heap->size == 0);
GNUNET_free (heap);
- return;
}
-static struct GNUNET_CONTAINER_heap_node *
-find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
+
+/**
+ * Get element stored at the root of @a heap.
+ *
+ * @param heap Heap to inspect.
+ * @return Element at the root, or NULL if heap is empty.
+ */
+void *
+GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
{
- struct GNUNET_CONTAINER_heap_node *ret;
- ret = NULL;
- if (node == NULL)
+ if (heap->root == NULL)
return NULL;
-
- if (node->element == element)
- return node;
-
- if (node->left_child != NULL)
- ret = find_element (node->left_child, element);
-
- if ((ret == NULL) && (node->right_child != NULL))
- ret = find_element (node->right_child, element);
-
- return ret;
+ return heap->root->element;
}
-static struct GNUNET_CONTAINER_heap_node *
-getNextPos (struct GNUNET_CONTAINER_Heap *root)
-{
- struct GNUNET_CONTAINER_heap_node *ret;
- struct GNUNET_CONTAINER_heap_node *parent;
- int pos;
- int i;
-
- ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
- pos = root->size + 1;
- ret->left_child = NULL;
- ret->right_child = NULL;
-
- if (0 == root->size)
- {
- ret->parent = NULL;
- root->root = ret;
- }
- else
- {
- parent = root->root;
- for (i = next_power_of_2(pos) >> 2; i > 1; i >>= 1)
- {
- if (((pos / i) % 2) == 0)
- parent = parent->left_child;
- else
- parent = parent->right_child;
- }
-
- ret->parent = parent;
- if ((pos % 2) == 0)
- parent->left_child = ret;
- else
- parent->right_child = ret;
- }
+/**
+ * Get @a element and @a cost stored at the root of @a heap.
+ *
+ * @param[in] heap Heap to inspect.
+ * @param[out] element Root element is returned here.
+ * @param[out] cost Cost of @a element is returned here.
+ * @return #GNUNET_YES if an element is returned,
+ * #GNUNET_NO if the heap is empty.
+ */
+int
+GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap,
+ void **element,
+ GNUNET_CONTAINER_HeapCostType *cost)
+{
+ if (NULL == heap->root)
+ return GNUNET_NO;
+ if (NULL != element)
+ *element = heap->root->element;
+ if (NULL != cost)
+ *cost = heap->root->cost;
+ return GNUNET_YES;
+}
- return ret;
+/**
+ * Get the current size of the heap
+ *
+ * @param heap the heap to get the size of
+ * @return number of elements stored
+ */
+unsigned int
+GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
+{
+ return heap->size;
}
-static struct GNUNET_CONTAINER_heap_node *
-getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
-{
- struct GNUNET_CONTAINER_heap_node *ret;
- int i;
- ret = NULL;
- if (pos > root->size)
- {
- return ret;
- }
- else
- {
- ret = root->root;
- for (i = next_power_of_2(pos) >> 2; i > 0; i >>= 1)
- {
- if (((pos / i) % 2) == 0)
- ret = ret->left_child;
- else
- ret = ret->right_child;
- }
- }
+/**
+ * Get the current cost of the node
+ *
+ * @param node the node to get the cost of
+ * @return cost of the node
+ */
+GNUNET_CONTAINER_HeapCostType
+GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
+ *node)
+{
+ return node->cost;
+}
- return ret;
+/**
+ * Iterate over the children of the given node.
+ *
+ * @param heap argument to give to iterator
+ * @param node node to iterate over
+ * @param iterator function to call on each node
+ * @param iterator_cls closure for iterator
+ * @return GNUNET_YES to continue to iterate
+ */
+static int
+node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
+{
+ if (node == NULL)
+ return GNUNET_YES;
+ if (GNUNET_YES !=
+ node_iterator (heap, node->left_child, iterator, iterator_cls))
+ return GNUNET_NO;
+ if (GNUNET_YES !=
+ node_iterator (heap, node->right_child, iterator, iterator_cls))
+ return GNUNET_NO;
+ return iterator (iterator_cls, node, node->element, node->cost);
}
+
+/**
+ * Iterate over all entries in the heap.
+ *
+ * @param heap the heap
+ * @param iterator function to call on each entry
+ * @param iterator_cls closure for iterator
+ */
void
-swapNodes (struct GNUNET_CONTAINER_heap_node *first,
- struct GNUNET_CONTAINER_heap_node *second,
- struct GNUNET_CONTAINER_Heap *root)
+GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
+ GNUNET_CONTAINER_HeapIterator iterator,
+ void *iterator_cls)
{
- void *temp_element;
- GNUNET_CONTAINER_HeapCost temp_cost;
-
- temp_element = first->element;
- temp_cost = first->cost;
- first->element = second->element;
- first->cost = second->cost;
- second->element = temp_element;
- second->cost = temp_cost;
-
- return;
+ (void) node_iterator (heap, heap->root, iterator, iterator_cls);
}
-void
-percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
- struct GNUNET_CONTAINER_Heap *root)
-{
- while ((pos->parent != NULL) &&
- (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
- && (pos->parent->cost < pos->cost))
- || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
- && (pos->parent->cost > pos->cost))))
- {
- swapNodes (pos, pos->parent, root);
- pos = pos->parent;
- }
+/**
+ * Perform a random walk of the tree. The walk is biased
+ * towards elements closer to the root of the tree (since
+ * each walk starts at the root and ends at a random leaf).
+ * The heap internally tracks the current position of the
+ * walk.
+ *
+ * @param heap heap to walk
+ * @return data stored at the next random node in the walk;
+ * NULL if the tree is empty.
+ */
+void *
+GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
+{
+ struct GNUNET_CONTAINER_HeapNode *pos;
+ void *element;
- return;
+ if (heap->root == NULL)
+ return NULL;
+ pos = heap->walk_pos;
+ if (pos == NULL)
+ pos = heap->root;
+ element = pos->element;
+ heap->walk_pos =
+ (0 ==
+ GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+ 2)) ? pos->right_child : pos->left_child;
+ return element;
}
-
-void
-percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
- struct GNUNET_CONTAINER_Heap *root)
+/**
+ * Insert the given node 'node' into the subtree starting
+ * at 'pos' (while keeping the tree somewhat balanced).
+ *
+ * @param heap heap to modify
+ * @param pos existing tree
+ * @param node node to insert (which may be a subtree itself)
+ */
+static void
+insert_node (struct GNUNET_CONTAINER_Heap *heap,
+ struct GNUNET_CONTAINER_HeapNode *pos,
+ struct GNUNET_CONTAINER_HeapNode *node)
{
- struct GNUNET_CONTAINER_heap_node *switchNeighbor;
-
- switchNeighbor = pos;
-
- if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
+ struct GNUNET_CONTAINER_HeapNode *parent;
+
+ GNUNET_assert (node->parent == NULL);
+ while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
+ node->cost)
+ : (pos->cost <= node->cost))
+ {
+ /* node is descendent of pos */
+ pos->tree_size += (1 + node->tree_size);
+ if (pos->left_child == NULL)
{
- if ((pos->left_child != NULL)
- && (pos->left_child->cost > switchNeighbor->cost))
- {
- switchNeighbor = pos->left_child;
- }
-
- if ((pos->right_child != NULL)
- && (pos->right_child->cost > switchNeighbor->cost))
- {
- switchNeighbor = pos->right_child;
- }
+ pos->left_child = node;
+ node->parent = pos;
+ return;
}
- else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
+ if (pos->right_child == NULL)
{
- if ((pos->left_child != NULL)
- && (pos->left_child->cost < switchNeighbor->cost))
- {
- switchNeighbor = pos->left_child;
- }
-
- if ((pos->right_child != NULL)
- && (pos->right_child->cost < switchNeighbor->cost))
- {
- switchNeighbor = pos->right_child;
- }
+ pos->right_child = node;
+ node->parent = pos;
+ return;
}
+ /* keep it balanced by descending into smaller subtree */
+ if (pos->left_child->tree_size < pos->right_child->tree_size)
+ pos = pos->left_child;
+ else
+ pos = pos->right_child;
+ }
+ /* make 'node' parent of 'pos' */
+ parent = pos->parent;
+ pos->parent = NULL;
+ node->parent = parent;
+ if (NULL == parent)
+ {
+ heap->root = node;
+ }
+ else
+ {
+ if (parent->left_child == pos)
+ parent->left_child = node;
+ else
+ parent->right_child = node;
+ }
+ /* insert 'pos' below 'node' */
+ insert_node (heap, node, pos);
+ CHECK (pos);
+}
- if (switchNeighbor != pos)
- {
- swapNodes (switchNeighbor, pos, root);
- percolateDownHeap (switchNeighbor, root);
- }
- return;
+/**
+ * Inserts a new element into the heap.
+ *
+ * @param heap heap to modify
+ * @param element element to insert
+ * @param cost cost for the element
+ * @return node for the new element
+ */
+struct GNUNET_CONTAINER_HeapNode *
+GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element,
+ GNUNET_CONTAINER_HeapCostType cost)
+{
+ struct GNUNET_CONTAINER_HeapNode *node;
+
+ node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
+ node->heap = heap;
+ node->element = element;
+ node->cost = cost;
+ heap->size++;
+ if (NULL == heap->root)
+ heap->root = node;
+ else
+ insert_node (heap, heap->root, node);
+ GNUNET_assert (heap->size == heap->root->tree_size + 1);
+ CHECK (heap->root);
+ return node;
}
+
+/**
+ * Remove root of the heap.
+ *
+ * @param heap heap to modify
+ * @return element data stored at the root node, NULL if heap is empty
+ */
void *
-GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
- void *element)
+GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
{
void *ret;
- struct GNUNET_CONTAINER_heap_node *del_node;
- struct GNUNET_CONTAINER_heap_node *last;
- GNUNET_CONTAINER_HeapCost old_cost;
+ struct GNUNET_CONTAINER_HeapNode *root;
- del_node = NULL;
- del_node = find_element (root->root, element);
-
- if (del_node == NULL)
+ if (NULL == (root = heap->root))
return NULL;
- else if (del_node == root->root)
- return GNUNET_CONTAINER_heap_remove_root (root);
-
- ret = del_node->element;
- last = getPos (root, root->size);
+ heap->size--;
+ ret = root->element;
+ if (root->left_child == NULL)
+ {
+ heap->root = root->right_child;
+ if (root->right_child != NULL)
+ root->right_child->parent = NULL;
+ }
+ else if (root->right_child == NULL)
+ {
+ heap->root = root->left_child;
+ root->left_child->parent = NULL;
+ }
+ else
+ {
+ root->left_child->parent = NULL;
+ root->right_child->parent = NULL;
+ heap->root = root->left_child;
+ insert_node (heap, heap->root, root->right_child);
+ }
+ if (heap->walk_pos == root)
+ heap->walk_pos = heap->root;
+ GNUNET_free (root);
+#if EXTRA_CHECKS
+ GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 1));
+ CHECK (heap->root);
+#endif
+ return ret;
+}
- old_cost = del_node->cost;
- del_node->element = last->element;
- del_node->cost = last->cost;
- if (last->parent->left_child == last)
- last->parent->left_child = NULL;
- if (last->parent->right_child == last)
- last->parent->right_child = NULL;
+/**
+ * Remove the given node 'node' from the tree and update
+ * the 'tree_size' fields accordingly. Preserves the
+ * children of 'node' and does NOT change the overall
+ * 'size' field of the tree.
+ */
+static void
+remove_node (struct GNUNET_CONTAINER_HeapNode *node)
+{
+ struct GNUNET_CONTAINER_HeapNode *ancestor;
+ struct GNUNET_CONTAINER_Heap *heap = node->heap;
- if (root->traversal_pos == last)
- {
- root->traversal_pos = root->root;
- }
- GNUNET_free (last);
- root->size--;
+ /* update 'size' of the ancestors */
+ ancestor = node;
+ while (NULL != (ancestor = ancestor->parent))
+ ancestor->tree_size--;
- if (del_node->cost > old_cost)
+ /* update 'size' of node itself */
+ if (node->left_child != NULL)
+ node->tree_size -= (1 + node->left_child->tree_size);
+ if (node->right_child != NULL)
+ node->tree_size -= (1 + node->right_child->tree_size);
+
+ /* unlink 'node' itself and insert children in its place */
+ if (node->parent == NULL)
+ {
+ if (node->left_child != NULL)
{
- if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
- percolateHeap (del_node, root);
- else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
- percolateDownHeap (del_node, root);
+ heap->root = node->left_child;
+ node->left_child->parent = NULL;
+ if (node->right_child != NULL)
+ {
+ node->right_child->parent = NULL;
+ insert_node (heap, heap->root, node->right_child);
+ }
}
- else if (del_node->cost < old_cost)
+ else
{
- if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
- percolateDownHeap (del_node, root);
- else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
- percolateHeap (del_node, root);
+ heap->root = node->right_child;
+ if (node->right_child != NULL)
+ node->right_child->parent = NULL;
}
-
- return ret;
-}
-
-int
-GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
- void *element, GNUNET_CONTAINER_HeapCost cost)
-{
- struct GNUNET_CONTAINER_heap_node *new_pos;
- int ret;
- ret = GNUNET_YES;
-
- if (root->max_size > root->size)
+ }
+ else
+ {
+ if (node->parent->left_child == node)
+ node->parent->left_child = NULL;
+ else
+ node->parent->right_child = NULL;
+ if (node->left_child != NULL)
{
- new_pos = getNextPos (root);
- new_pos->element = element;
- new_pos->cost = cost;
- root->size++;
-
- percolateHeap (new_pos, root);
+ node->left_child->parent = NULL;
+ node->parent->tree_size -= (1 + node->left_child->tree_size);
+ insert_node (heap, node->parent, node->left_child);
}
- else
+ if (node->right_child != NULL)
{
- ret = GNUNET_NO;
+ node->right_child->parent = NULL;
+ node->parent->tree_size -= (1 + node->right_child->tree_size);
+ insert_node (heap, node->parent, node->right_child);
}
-
- return ret;
+ }
+ node->parent = NULL;
+ node->left_child = NULL;
+ node->right_child = NULL;
+ GNUNET_assert (node->tree_size == 0);
+ CHECK (heap->root);
}
+
+/**
+ * Removes a node from the heap.
+ *
+ * @param node node to remove
+ * @return element data stored at the node
+ */
void *
-GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
+GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
{
void *ret;
- struct GNUNET_CONTAINER_heap_node *root_node;
- struct GNUNET_CONTAINER_heap_node *last;
-
- if ((root == NULL) || (root->size == 0) || (root->root == NULL))
- return NULL;
-
- root_node = root->root;
- ret = root_node->element;
- last = getPos (root, root->size);
-
- if ((root_node == last) && (root->size == 1))
- {
- /* We are removing the last node in the heap! */
- root->root = NULL;
- root->traversal_pos = NULL;
- GNUNET_assert (0 == --root->size);
- return ret;
- }
-
- if (last->parent->left_child == last)
- last->parent->left_child = NULL;
- else if (last->parent->right_child == last)
- last->parent->right_child = NULL;
-
- root_node->element = last->element;
- root_node->cost = last->cost;
-
- if (root->traversal_pos == last)
- {
- root->traversal_pos = root->root;
- }
+ struct GNUNET_CONTAINER_Heap *heap;
- GNUNET_free (last);
- root->size--;
- percolateDownHeap (root->root, root);
+ heap = node->heap;
+ CHECK (heap->root);
+ if (heap->walk_pos == node)
+ (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
+ remove_node (node);
+ heap->size--;
+ ret = node->element;
+ if (heap->walk_pos == node)
+ heap->walk_pos = NULL;
+ GNUNET_free (node);
+#if EXTRA_CHECKS
+ CHECK (heap->root);
+ GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
+ (heap->size == heap->root->tree_size + 1));
+#endif
return ret;
}
-static int
-updatedCost (struct GNUNET_CONTAINER_Heap *root,
- struct GNUNET_CONTAINER_heap_node *node)
-{
- struct GNUNET_CONTAINER_heap_node *parent;
-
- if (node == NULL)
- return GNUNET_SYSERR;
-
- parent = node->parent;
-
- if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
- && (node->cost > parent->cost))
- percolateHeap (node, root);
- else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
- && (node->cost < parent->cost))
- percolateHeap (node, root);
- else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
- percolateDownHeap (node, root);
- else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
- percolateDownHeap (node, root);
-
- return GNUNET_YES;
-}
-
-
-int
-GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
- void *element,
- GNUNET_CONTAINER_HeapCost new_cost)
-{
- struct GNUNET_CONTAINER_heap_node *node;
- int ret = GNUNET_YES;
- node = find_element (root->root, element);
- if (node == NULL)
- return GNUNET_NO;
-
- node->cost = new_cost;
- ret = updatedCost (root, node);
- return ret;
-}
+/**
+ * Updates the cost of any node in the tree
+ *
+ * @param node node for which the cost is to be changed
+ * @param new_cost new cost for the node
+ */
void
-internal_iterator (struct GNUNET_CONTAINER_Heap *root,
- struct GNUNET_CONTAINER_heap_node *node,
- GNUNET_CONTAINER_HeapIterator iterator, void *cls)
+GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
+ GNUNET_CONTAINER_HeapCostType new_cost)
{
- if (node == NULL)
- return;
- internal_iterator (root, node->left_child, iterator, cls);
- internal_iterator (root, node->right_child, iterator, cls);
- iterator (cls, node->element, node->cost);
-}
-
-int
-GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
- GNUNET_CONTAINER_HeapIterator iterator,
- void *cls)
-{
- internal_iterator (heap, heap->root, iterator, cls);
- return GNUNET_OK;
-}
-
-void *
-GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
-{
- unsigned int choice;
- void *element;
-
- if ((root->traversal_pos == NULL) && (root->root != NULL))
- {
- root->traversal_pos = root->root;
- }
-
- if (root->traversal_pos == NULL)
- return NULL;
-
- element = root->traversal_pos->element;
-
- choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
-
- switch (choice)
- {
- case 1:
- root->traversal_pos = root->traversal_pos->right_child;
- break;
- case 0:
- root->traversal_pos = root->traversal_pos->left_child;
- break;
- }
-
- return element;
+ struct GNUNET_CONTAINER_Heap *heap = node->heap;
+ remove_node (node);
+ node->cost = new_cost;
+ if (NULL == heap->root)
+ heap->root = node;
+ else
+ insert_node (heap,
+ heap->root,
+ node);
}
-unsigned int
-GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
-{
- return heap->size;
-}
/* end of heap.c */