container_heap.c File Reference

Implementation of a heap. More...

#include "platform.h"
#include "gnunet_util_lib.h"

Include dependency graph for container_heap.c:

Go to the source code of this file.

Data Structures
struct	GNUNET_CONTAINER_HeapNode
	Node in the heap. More...
struct	GNUNET_CONTAINER_Heap
	Handle to a node in a heap. More...

Macros
#define	LOG(kind, ...)
#define	EXTRA_CHECKS   0
#define	CHECK(n)   do {} while (0)

Functions
struct GNUNET_CONTAINER_Heap *	GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
	Create a new heap.
void	GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
	Destroys the heap.
void *	GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
	Get element stored at the root of heap.
enum GNUNET_GenericReturnValue	GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap, void **element, GNUNET_CONTAINER_HeapCostType *cost)
	Get element and cost stored at the root of heap.
unsigned int	GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
	Get the current size of the heap.
GNUNET_CONTAINER_HeapCostType	GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node)
	Get the current cost of the node.
static int	node_iterator (const struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *node, GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
	Iterate over the children of the given node.
void	GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
	Iterate over all entries in the heap.
void *	GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
	Perform a random walk of the tree.
static void	insert_node (struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *pos, struct GNUNET_CONTAINER_HeapNode *node)
	Insert the given node 'node' into the subtree starting at 'pos' (while keeping the tree somewhat balanced).
struct GNUNET_CONTAINER_HeapNode *	GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, GNUNET_CONTAINER_HeapCostType cost)
	Inserts a new element into the heap.
void *	GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
	Remove root of the heap.
static void	remove_node (struct GNUNET_CONTAINER_HeapNode *node)
	Remove the given node 'node' from the tree and update the 'tree_size' fields accordingly.
void *	GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
	Removes a node from the heap.
void	GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node, GNUNET_CONTAINER_HeapCostType new_cost)
	Updates the cost of any node in the tree.

Detailed Description

Implementation of a heap.

Author

Nathan Evans

Christian Grothoff

Definition in file container_heap.c.

Macro Definition Documentation

LOG

#define LOG	(		kind,
			...
	)

Value:

                                        GNUNET_log_from (kind, "util-container-heap", \
                                        __VA_ARGS__)

Definition at line 32 of file container_heap.c.

{
  struct GNUNET_CONTAINER_Heap *heap;
 
  struct GNUNET_CONTAINER_HeapNode *parent;
 
  struct GNUNET_CONTAINER_HeapNode *left_child;
 
  struct GNUNET_CONTAINER_HeapNode *right_child;
 
  void *element;
 
  GNUNET_CONTAINER_HeapCostType cost;
 
  unsigned int tree_size;
};
 
struct GNUNET_CONTAINER_Heap
{
  struct GNUNET_CONTAINER_HeapNode *root;
 
  struct GNUNET_CONTAINER_HeapNode *walk_pos;
 
  unsigned int size;
 
  enum GNUNET_CONTAINER_HeapOrder order;
};
 
 
#if EXTRA_CHECKS
static void
check (const struct GNUNET_CONTAINER_HeapNode *node)
{
  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);
}
 
 
#define CHECK(n) check (n)
#else
#define CHECK(n) do {} while (0)
#endif
 
 
struct GNUNET_CONTAINER_Heap *
GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
{
  struct GNUNET_CONTAINER_Heap *heap;
 
  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
  heap->order = order;
  return heap;
}
 
 
void
GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
{
  GNUNET_break (heap->size == 0);
  GNUNET_free (heap);
}
 
 
void *
GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
{
  if (heap->root == NULL)
    return NULL;
  return heap->root->element;
}
 
 
enum GNUNET_GenericReturnValue
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;
}
 
 
unsigned int
GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
{
  return heap->size;
}
 
 
GNUNET_CONTAINER_HeapCostType
GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
                                     *node)
{
  return node->cost;
}
 
 
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);
}
 
 
void
GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
                               GNUNET_CONTAINER_HeapIterator iterator,
                               void *iterator_cls)
{
  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
}
 
 
void *
GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
{
  struct GNUNET_CONTAINER_HeapNode *pos;
  void *element;
 
  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;
}
 
 
static void
insert_node (struct GNUNET_CONTAINER_Heap *heap,
             struct GNUNET_CONTAINER_HeapNode *pos,
             struct GNUNET_CONTAINER_HeapNode *node)
{
  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)
    {
      pos->left_child = node;
      node->parent = pos;
      return;
    }
    if (pos->right_child == NULL)
    {
      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);
}
 
 
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;
}
 
 
void *
GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
{
  void *ret;
  struct GNUNET_CONTAINER_HeapNode *root;
 
  if (NULL == (root = heap->root))
    return NULL;
  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;
}
 
 
static void
remove_node (struct GNUNET_CONTAINER_HeapNode *node)
{
  struct GNUNET_CONTAINER_HeapNode *ancestor;
  struct GNUNET_CONTAINER_Heap *heap = node->heap;
 
  /* update 'size' of the ancestors */
  ancestor = node;
  while (NULL != (ancestor = ancestor->parent))
    ancestor->tree_size--;
 
  /* 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)
    {
      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
    {
      heap->root = node->right_child;
      if (node->right_child != NULL)
        node->right_child->parent = NULL;
    }
  }
  else
  {
    if (node->parent->left_child == node)
      node->parent->left_child = NULL;
    else
      node->parent->right_child = NULL;
    if (node->left_child != NULL)
    {
      node->left_child->parent = NULL;
      node->parent->tree_size -= (1 + node->left_child->tree_size);
      insert_node (heap, node->parent, node->left_child);
    }
    if (node->right_child != NULL)
    {
      node->right_child->parent = NULL;
      node->parent->tree_size -= (1 + node->right_child->tree_size);
      insert_node (heap, node->parent, node->right_child);
    }
  }
  node->parent = NULL;
  node->left_child = NULL;
  node->right_child = NULL;
  GNUNET_assert (node->tree_size == 0);
  CHECK (heap->root);
}
 
 
void *
GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
{
  void *ret;
  struct GNUNET_CONTAINER_Heap *heap;
 
  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;
}
 
 
void
GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node,
                                   GNUNET_CONTAINER_HeapCostType new_cost)
{
  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);
}
 
 
/* end of heap.c */

EXTRA_CHECKS

#define EXTRA_CHECKS   0

Definition at line 35 of file container_heap.c.

CHECK

#define CHECK

(

n

)

do {} while (0)

Definition at line 129 of file container_heap.c.

Function Documentation

node_iterator()

static int node_iterator ( const struct GNUNET_CONTAINER_Heap *  heap, struct GNUNET_CONTAINER_HeapNode *  node, GNUNET_CONTAINER_HeapIterator  iterator, void *  iterator_cls  )

static

Iterate over the children of the given node.

Parameters

heap	argument to give to iterator
node	node to iterate over
iterator	function to call on each node
iterator_cls	closure for iterator

Returns

GNUNET_YES to continue to iterate

Definition at line 210 of file container_heap.c.

{
  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);
}

References GNUNET_CONTAINER_HeapNode::cost, GNUNET_CONTAINER_HeapNode::element, GNUNET_NO, GNUNET_YES, GNUNET_CONTAINER_HeapNode::left_child, node_iterator(), and GNUNET_CONTAINER_HeapNode::right_child.

Referenced by GNUNET_CONTAINER_heap_iterate(), and node_iterator().

Here is the call graph for this function:

Here is the caller graph for this function:

insert_node()

static void insert_node ( struct GNUNET_CONTAINER_Heap *  heap, struct GNUNET_CONTAINER_HeapNode *  pos, struct GNUNET_CONTAINER_HeapNode *  node  )

static

Insert the given node 'node' into the subtree starting at 'pos' (while keeping the tree somewhat balanced).

Parameters

heap	heap to modify
pos	existing tree
node	node to insert (which may be a subtree itself)

Definition at line 264 of file container_heap.c.

{
  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)
    {
      pos->left_child = node;
      node->parent = pos;
      return;
    }
    if (pos->right_child == NULL)
    {
      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);
}

References CHECK, GNUNET_CONTAINER_HeapNode::cost, GNUNET_assert, GNUNET_CONTAINER_HEAP_ORDER_MAX, GNUNET_CONTAINER_HeapNode::heap, insert_node(), GNUNET_CONTAINER_HeapNode::left_child, GNUNET_CONTAINER_Heap::order, GNUNET_CONTAINER_HeapNode::parent, GNUNET_CONTAINER_HeapNode::right_child, GNUNET_CONTAINER_Heap::root, and GNUNET_CONTAINER_HeapNode::tree_size.

Referenced by GNUNET_CONTAINER_heap_insert(), GNUNET_CONTAINER_heap_remove_root(), GNUNET_CONTAINER_heap_update_cost(), insert_node(), and remove_node().

Here is the call graph for this function:

Here is the caller graph for this function:

remove_node()

static void remove_node ( struct GNUNET_CONTAINER_HeapNode *  node )

static

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.

Definition at line 390 of file container_heap.c.

{
  struct GNUNET_CONTAINER_HeapNode *ancestor;
  struct GNUNET_CONTAINER_Heap *heap = node->heap;
 
  /* update 'size' of the ancestors */
  ancestor = node;
  while (NULL != (ancestor = ancestor->parent))
    ancestor->tree_size--;
 
  /* 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)
    {
      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
    {
      heap->root = node->right_child;
      if (node->right_child != NULL)
        node->right_child->parent = NULL;
    }
  }
  else
  {
    if (node->parent->left_child == node)
      node->parent->left_child = NULL;
    else
      node->parent->right_child = NULL;
    if (node->left_child != NULL)
    {
      node->left_child->parent = NULL;
      node->parent->tree_size -= (1 + node->left_child->tree_size);
      insert_node (heap, node->parent, node->left_child);
    }
    if (node->right_child != NULL)
    {
      node->right_child->parent = NULL;
      node->parent->tree_size -= (1 + node->right_child->tree_size);
      insert_node (heap, node->parent, node->right_child);
    }
  }
  node->parent = NULL;
  node->left_child = NULL;
  node->right_child = NULL;
  GNUNET_assert (node->tree_size == 0);
  CHECK (heap->root);
}

References CHECK, GNUNET_assert, GNUNET_CONTAINER_HeapNode::heap, insert_node(), GNUNET_CONTAINER_HeapNode::left_child, GNUNET_CONTAINER_HeapNode::parent, GNUNET_CONTAINER_HeapNode::right_child, GNUNET_CONTAINER_Heap::root, and GNUNET_CONTAINER_HeapNode::tree_size.

Referenced by GNUNET_CONTAINER_heap_remove_node(), and GNUNET_CONTAINER_heap_update_cost().

Here is the call graph for this function:

Here is the caller graph for this function: