GNUnet  0.10.x
Data Structures | Macros | Functions
container_heap.c File Reference

Implementation of a heap. More...

#include "platform.h"
#include "gnunet_container_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, ...)   GNUNET_log_from(kind, "util-container-heap", __VA_ARGS__)
 
#define EXTRA_CHECKS   0
 
#define CHECK(n)   do {} while (0)
 

Functions

struct GNUNET_CONTAINER_HeapGNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order)
 Create a new heap. More...
 
void GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
 Destroys the heap. More...
 
void * GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap)
 Get element stored at the root of heap. More...
 
int 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. More...
 
unsigned int GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
 Get the current size of the heap. More...
 
GNUNET_CONTAINER_HeapCostType GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node)
 Get the current cost of the node. More...
 
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. More...
 
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. More...
 
void * GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
 Perform a random walk of the tree. More...
 
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). More...
 
struct GNUNET_CONTAINER_HeapNodeGNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, GNUNET_CONTAINER_HeapCostType cost)
 Inserts a new element into the heap. More...
 
void * GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
 Remove root of the heap. More...
 
static void remove_node (struct GNUNET_CONTAINER_HeapNode *node)
 Remove the given node 'node' from the tree and update the 'tree_size' fields accordingly. More...
 
void * GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
 Removes a node from the heap. More...
 
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. More...
 

Detailed Description

Implementation of a heap.

Author
Nathan Evans
Christian Grothoff

Definition in file container_heap.c.

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)    GNUNET_log_from(kind, "util-container-heap", __VA_ARGS__)

Definition at line 31 of file container_heap.c.

◆ EXTRA_CHECKS

#define EXTRA_CHECKS   0

Definition at line 33 of file container_heap.c.

◆ CHECK

#define CHECK (   n)    do {} while (0)

Function Documentation

◆ GNUNET_CONTAINER_heap_peek2()

int 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.

Parameters
[in]heapHeap to inspect.
[out]elementRoot element is returned here.
[out]costCost of element is returned here.
Returns
GNUNET_YES if an element is returned, GNUNET_NO if the heap is empty.

Definition at line 185 of file container_heap.c.

References GNUNET_CONTAINER_HeapNode::cost, GNUNET_CONTAINER_HeapNode::element, GNUNET_NO, GNUNET_YES, and GNUNET_CONTAINER_Heap::root.

Referenced by GCP_attach_path().

188 {
189  if (NULL == heap->root)
190  return GNUNET_NO;
191  if (NULL != element)
192  *element = heap->root->element;
193  if (NULL != cost)
194  *cost = heap->root->cost;
195  return GNUNET_YES;
196 }
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.
#define GNUNET_NO
Definition: gnunet_common.h:78
void * element
Our element.
#define GNUNET_YES
Definition: gnunet_common.h:77
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
Here is the caller graph for this function:

◆ 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
heapargument to give to iterator
nodenode to iterate over
iteratorfunction to call on each node
iterator_clsclosure for iterator
Returns
GNUNET_YES to continue to iterate

Definition at line 236 of file container_heap.c.

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

Referenced by GNUNET_CONTAINER_heap_iterate().

239 {
240  if (node == NULL)
241  return GNUNET_YES;
242  if (GNUNET_YES !=
243  node_iterator(heap, node->left_child, iterator, iterator_cls))
244  return GNUNET_NO;
245  if (GNUNET_YES !=
246  node_iterator(heap, node->right_child, iterator, iterator_cls))
247  return GNUNET_NO;
248  return iterator(iterator_cls, node, node->element, node->cost);
249 }
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.
#define GNUNET_NO
Definition: gnunet_common.h:78
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 * element
Our element.
#define GNUNET_YES
Definition: gnunet_common.h:77
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
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
heapheap to modify
posexisting tree
nodenode to insert (which may be a subtree itself)

Definition at line 308 of file container_heap.c.

References CHECK, GNUNET_CONTAINER_HeapNode::cost, GNUNET_assert, GNUNET_CONTAINER_HEAP_ORDER_MAX, 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(), and remove_node().

311 {
313 
314  GNUNET_assert(node->parent == NULL);
315  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
316  node->cost)
317  : (pos->cost <= node->cost))
318  {
319  /* node is descendent of pos */
320  pos->tree_size += (1 + node->tree_size);
321  if (pos->left_child == NULL)
322  {
323  pos->left_child = node;
324  node->parent = pos;
325  return;
326  }
327  if (pos->right_child == NULL)
328  {
329  pos->right_child = node;
330  node->parent = pos;
331  return;
332  }
333  /* keep it balanced by descending into smaller subtree */
334  if (pos->left_child->tree_size < pos->right_child->tree_size)
335  pos = pos->left_child;
336  else
337  pos = pos->right_child;
338  }
339  /* make 'node' parent of 'pos' */
340  parent = pos->parent;
341  pos->parent = NULL;
342  node->parent = parent;
343  if (NULL == parent)
344  {
345  heap->root = node;
346  }
347  else
348  {
349  if (parent->left_child == pos)
350  parent->left_child = node;
351  else
352  parent->right_child = node;
353  }
354  /* insert 'pos' below 'node' */
355  insert_node(heap, node, pos);
356  CHECK(pos);
357 }
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
#define CHECK(n)
static void insert_node(struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *pos, struct GNUNET_CONTAINER_HeapNode *node)
Insert the given node &#39;node&#39; into the subtree starting at &#39;pos&#39; (while keeping the tree somewhat bala...
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.
unsigned int tree_size
Number of elements below this node in the heap (excluding this node itself).
Node in the heap.
enum GNUNET_CONTAINER_HeapOrder order
How is the heap sorted?
struct GNUNET_CONTAINER_HeapNode * parent
Parent node.
Heap with the maximum cost at the root.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
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 442 of file container_heap.c.

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().

443 {
444  struct GNUNET_CONTAINER_HeapNode *ancestor;
445  struct GNUNET_CONTAINER_Heap *heap = node->heap;
446 
447  /* update 'size' of the ancestors */
448  ancestor = node;
449  while (NULL != (ancestor = ancestor->parent))
450  ancestor->tree_size--;
451 
452  /* update 'size' of node itself */
453  if (node->left_child != NULL)
454  node->tree_size -= (1 + node->left_child->tree_size);
455  if (node->right_child != NULL)
456  node->tree_size -= (1 + node->right_child->tree_size);
457 
458  /* unlink 'node' itself and insert children in its place */
459  if (node->parent == NULL)
460  {
461  if (node->left_child != NULL)
462  {
463  heap->root = node->left_child;
464  node->left_child->parent = NULL;
465  if (node->right_child != NULL)
466  {
467  node->right_child->parent = NULL;
468  insert_node(heap, heap->root, node->right_child);
469  }
470  }
471  else
472  {
473  heap->root = node->right_child;
474  if (node->right_child != NULL)
475  node->right_child->parent = NULL;
476  }
477  }
478  else
479  {
480  if (node->parent->left_child == node)
481  node->parent->left_child = NULL;
482  else
483  node->parent->right_child = NULL;
484  if (node->left_child != NULL)
485  {
486  node->left_child->parent = NULL;
487  node->parent->tree_size -= (1 + node->left_child->tree_size);
488  insert_node(heap, node->parent, node->left_child);
489  }
490  if (node->right_child != NULL)
491  {
492  node->right_child->parent = NULL;
493  node->parent->tree_size -= (1 + node->right_child->tree_size);
494  insert_node(heap, node->parent, node->right_child);
495  }
496  }
497  node->parent = NULL;
498  node->left_child = NULL;
499  node->right_child = NULL;
500  GNUNET_assert(node->tree_size == 0);
501  CHECK(heap->root);
502 }
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
#define CHECK(n)
static void insert_node(struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *pos, struct GNUNET_CONTAINER_HeapNode *node)
Insert the given node &#39;node&#39; into the subtree starting at &#39;pos&#39; (while keeping the tree somewhat bala...
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
Handle to a node in a heap.
unsigned int tree_size
Number of elements below this node in the heap (excluding this node itself).
Node in the heap.
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
struct GNUNET_CONTAINER_HeapNode * parent
Parent node.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
Here is the call graph for this function:
Here is the caller graph for this function: