GNUnet  0.11.x
Typedefs | Enumerations | Enumerator | Functions
Container library: Heap

Min- or max-heap with arbitrary element removal. More...

Typedefs

typedef uint64_t GNUNET_CONTAINER_HeapCostType
 Cost by which elements in a heap can be ordered. More...
 
typedef int(* GNUNET_CONTAINER_HeapIterator) (void *cls, struct GNUNET_CONTAINER_HeapNode *node, void *element, GNUNET_CONTAINER_HeapCostType cost)
 Iterator for heap. More...
 

Enumerations

enum  GNUNET_CONTAINER_HeapOrder { GNUNET_CONTAINER_HEAP_ORDER_MAX, GNUNET_CONTAINER_HEAP_ORDER_MIN }
 Heap type, either max or min. More...
 

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

Min- or max-heap with arbitrary element removal.

Typedef Documentation

◆ GNUNET_CONTAINER_HeapCostType

Cost by which elements in a heap can be ordered.

Definition at line 2491 of file gnunet_container_lib.h.

◆ GNUNET_CONTAINER_HeapIterator

typedef int(* GNUNET_CONTAINER_HeapIterator) (void *cls, struct GNUNET_CONTAINER_HeapNode *node, void *element, GNUNET_CONTAINER_HeapCostType cost)

Iterator for heap.

Parameters
clsclosure
nodeinternal node of the heap
elementvalue stored at the node
costcost associated with the node
Returns
GNUNET_YES if we should continue to iterate, GNUNET_NO if not.

Definition at line 2610 of file gnunet_container_lib.h.

Enumeration Type Documentation

◆ GNUNET_CONTAINER_HeapOrder

Heap type, either max or min.

Enumerator
GNUNET_CONTAINER_HEAP_ORDER_MAX 

Heap with the maximum cost at the root.

GNUNET_CONTAINER_HEAP_ORDER_MIN 

Heap with the minimum cost at the root.

Definition at line 2498 of file gnunet_container_lib.h.

2499 {
2505 
2511 };
Heap with the minimum cost at the root.
Heap with the maximum cost at the root.

Function Documentation

◆ GNUNET_CONTAINER_heap_create()

struct GNUNET_CONTAINER_Heap* GNUNET_CONTAINER_heap_create ( enum GNUNET_CONTAINER_HeapOrder  order)

Create a new heap.

Parameters
orderhow should the heap be sorted?
Returns
handle to the heap

Definition at line 139 of file container_heap.c.

References GNUNET_new, GNUNET_CONTAINER_HeapNode::heap, and GNUNET_CONTAINER_Heap::order.

Referenced by GCO_init(), GCP_get(), GDS_CLIENTS_init(), GDS_ROUTING_init(), GNS_resolver_init(), GSF_pending_request_init_(), GSF_plan_add_(), handle_fragment_box(), libgnunet_plugin_datacache_heap_init(), libgnunet_plugin_datastore_heap_init(), libgnunet_plugin_transport_udp_init(), and run().

140 {
141  struct GNUNET_CONTAINER_Heap *heap;
142 
143  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
144  heap->order = order;
145  return heap;
146 }
#define GNUNET_new(type)
Allocate a struct or union of the given type.
Handle to a node in a heap.
enum GNUNET_CONTAINER_HeapOrder order
How is the heap sorted?
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_destroy()

void GNUNET_CONTAINER_heap_destroy ( struct GNUNET_CONTAINER_Heap heap)

Destroys the heap.

Only call on a heap that is already empty.

Parameters
heapheap to destroy

Definition at line 156 of file container_heap.c.

References GNUNET_break, GNUNET_free, and GNUNET_CONTAINER_Heap::size.

Referenced by __attribute__(), cleanup(), destroy_peer(), do_shutdown(), free_neighbour(), GCO_shutdown(), GCP_drop_owned_paths(), GDS_ROUTING_done(), GNS_resolver_done(), GSF_pending_request_done_(), GSF_plan_notify_peer_disconnect_(), libgnunet_plugin_datacache_heap_done(), libgnunet_plugin_datastore_heap_done(), libgnunet_plugin_transport_udp_done(), and libgnunet_plugin_transport_udp_init().

157 {
158  GNUNET_break (heap->size == 0);
159  GNUNET_free (heap);
160 }
unsigned int size
Number of elements in the heap.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
#define GNUNET_free(ptr)
Wrapper around free.
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_peek()

void* GNUNET_CONTAINER_heap_peek ( const struct GNUNET_CONTAINER_Heap heap)

Get element stored at the root of heap.

Parameters
heapHeap to inspect.
Returns
Element at the root, or NULL if heap is empty.

Definition at line 170 of file container_heap.c.

References GNUNET_CONTAINER_HeapNode::element, and GNUNET_CONTAINER_Heap::root.

Referenced by check_timeouts(), expire_channel(), expire_destination(), expire_oldest_entry(), GSF_pending_request_create_(), heap_plugin_get_expiration(), insert_sorted(), path_heap_cleanup(), process_queue(), reassembly_cleanup_task(), schedule_peer_transmission(), timeout_cb(), update_next_challenge_time(), and validation_start_cb().

171 {
172  if (heap->root == NULL)
173  return NULL;
174  return heap->root->element;
175 }
void * element
Our element.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_get_size()

unsigned int GNUNET_CONTAINER_heap_get_size ( const struct GNUNET_CONTAINER_Heap heap)

Get the current size of the heap.

Parameters
heapthe heap to get the size of
Returns
number of elements stored

Definition at line 209 of file container_heap.c.

References GNUNET_CONTAINER_Heap::size.

Referenced by __attribute__(), consider_peer_destroy(), GCP_attach_path(), GDS_ROUTING_add(), GDS_ROUTING_done(), GSF_pending_request_create_(), path_heap_cleanup(), read_process_fragment(), schedule_peer_transmission(), setup_state_record(), and start_dht_request().

210 {
211  return heap->size;
212 }
unsigned int size
Number of elements in the heap.
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_node_get_cost()

GNUNET_CONTAINER_HeapCostType GNUNET_CONTAINER_heap_node_get_cost ( const struct GNUNET_CONTAINER_HeapNode node)

Get the current cost of the node.

Parameters
nodethe node to get the cost of
Returns
cost of the node

Definition at line 222 of file container_heap.c.

References GNUNET_CONTAINER_HeapNode::cost.

224 {
225  return node->cost;
226 }
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.

◆ GNUNET_CONTAINER_heap_iterate()

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.

Parameters
heapthe heap
iteratorfunction to call on each entry
iterator_clsclosure for iterator
heapthe heap
iteratorfunction to call on each entry
iterator_clsclosure for iterator

Definition at line 263 of file container_heap.c.

References node_iterator(), and GNUNET_CONTAINER_Heap::root.

Referenced by libgnunet_plugin_transport_udp_done(), read_process_fragment(), and udp_disconnect_session().

266 {
267  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
268 }
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
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.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_walk_get_next()

void* GNUNET_CONTAINER_heap_walk_get_next ( struct GNUNET_CONTAINER_Heap heap)

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.

Parameters
heapheap to walk
Returns
data stored at the next random node in the walk; NULL if the tree is empty.

Definition at line 283 of file container_heap.c.

References GNUNET_CONTAINER_HeapNode::element, GNUNET_CRYPTO_QUALITY_WEAK, GNUNET_CRYPTO_random_u32(), GNUNET_CONTAINER_HeapNode::left_child, GNUNET_CONTAINER_HeapNode::right_child, GNUNET_CONTAINER_Heap::root, and GNUNET_CONTAINER_Heap::walk_pos.

Referenced by GNUNET_CONTAINER_heap_remove_node(), and heap_plugin_get_replication().

284 {
285  struct GNUNET_CONTAINER_HeapNode *pos;
286  void *element;
287 
288  if (heap->root == NULL)
289  return NULL;
290  pos = heap->walk_pos;
291  if (pos == NULL)
292  pos = heap->root;
293  element = pos->element;
294  heap->walk_pos =
295  (0 ==
297  2)) ? pos->right_child : pos->left_child;
298  return element;
299 }
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
void * element
Our element.
struct GNUNET_CONTAINER_HeapNode * walk_pos
Current position of our random walk.
Node in the heap.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_insert()

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.

Parameters
heapheap to modify
elementelement to insert
costcost for the element
Returns
node for the new element

Definition at line 372 of file container_heap.c.

References CHECK, GNUNET_CONTAINER_HeapNode::cost, GNUNET_CONTAINER_HeapNode::element, GNUNET_assert, GNUNET_new, GNUNET_CONTAINER_HeapNode::heap, insert_node(), GNUNET_CONTAINER_Heap::root, GNUNET_CONTAINER_Heap::size, and GNUNET_CONTAINER_HeapNode::tree_size.

Referenced by GCP_attach_path(), GDS_ROUTING_add(), GSF_pending_request_create_(), handle_client_redirect_to_ip(), handle_client_redirect_to_service(), handle_connection_create(), handle_dht_local_get(), handle_fragment_box(), heap_plugin_get_replication(), heap_plugin_put(), insert_sorted(), mq_init(), plan(), read_process_fragment(), route_packet(), schedule_peer_transmission(), setup_sender(), setup_state_record(), start_dht_request(), transmit_next_request_task(), and update_next_challenge_time().

374 {
375  struct GNUNET_CONTAINER_HeapNode *node;
376 
377  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
378  node->heap = heap;
379  node->element = element;
380  node->cost = cost;
381  heap->size++;
382  if (NULL == heap->root)
383  heap->root = node;
384  else
385  insert_node (heap, heap->root, node);
386  GNUNET_assert (heap->size == heap->root->tree_size + 1);
387  CHECK (heap->root);
388  return node;
389 }
#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 'node' into the subtree starting at 'pos' (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.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
unsigned int size
Number of elements in the heap.
void * element
Our element.
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 * root
Root of the heap.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_remove_root()

void* GNUNET_CONTAINER_heap_remove_root ( struct GNUNET_CONTAINER_Heap heap)

Remove root of the heap.

Parameters
heapheap to modify
Returns
element data stored at the root node
Parameters
heapheap to modify
Returns
element data stored at the root node, NULL if heap is empty

Definition at line 399 of file container_heap.c.

References CHECK, GNUNET_CONTAINER_HeapNode::element, GNUNET_assert, GNUNET_free, insert_node(), GNUNET_CONTAINER_HeapNode::left_child, GNUNET_CONTAINER_HeapNode::parent, ret, GNUNET_CONTAINER_HeapNode::right_child, GNUNET_CONTAINER_Heap::root, GNUNET_CONTAINER_Heap::size, GNUNET_CONTAINER_HeapNode::tree_size, and GNUNET_CONTAINER_Heap::walk_pos.

Referenced by do_shutdown(), drop_paths(), GCP_drop_owned_paths(), GSF_plan_notify_peer_disconnect_(), heap_plugin_del(), heap_plugin_get_replication(), libgnunet_plugin_datacache_heap_done(), path_heap_cleanup(), process_queue(), read_process_fragment(), schedule_peer_transmission(), setup_state_record(), start_dht_request(), and transmit_next_request_task().

400 {
401  void *ret;
402  struct GNUNET_CONTAINER_HeapNode *root;
403 
404  if (NULL == (root = heap->root))
405  return NULL;
406  heap->size--;
407  ret = root->element;
408  if (root->left_child == NULL)
409  {
410  heap->root = root->right_child;
411  if (root->right_child != NULL)
412  root->right_child->parent = NULL;
413  }
414  else if (root->right_child == NULL)
415  {
416  heap->root = root->left_child;
417  root->left_child->parent = NULL;
418  }
419  else
420  {
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);
425  }
426  if (heap->walk_pos == root)
427  heap->walk_pos = heap->root;
428  GNUNET_free (root);
429 #if EXTRA_CHECKS
430  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
431  (heap->size == heap->root->tree_size + 1));
432  CHECK (heap->root);
433 #endif
434  return ret;
435 }
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 'node' into the subtree starting at 'pos' (while keeping the tree somewhat bala...
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
unsigned int size
Number of elements in the heap.
void * element
Our element.
struct GNUNET_CONTAINER_HeapNode * walk_pos
Current position of our random walk.
unsigned int tree_size
Number of elements below this node in the heap (excluding this node itself).
Node in the heap.
struct GNUNET_CONTAINER_HeapNode * parent
Parent node.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_remove_node()

void* GNUNET_CONTAINER_heap_remove_node ( struct GNUNET_CONTAINER_HeapNode node)

Removes a node from the heap.

Parameters
nodenode to remove
Returns
element data stored at the node, NULL if heap is empty
Parameters
nodenode to remove
Returns
element data stored at the node

Definition at line 515 of file container_heap.c.

References CHECK, GNUNET_CONTAINER_HeapNode::element, GNUNET_assert, GNUNET_CONTAINER_heap_walk_get_next(), GNUNET_free, GNUNET_CONTAINER_HeapNode::heap, remove_node(), ret, GNUNET_CONTAINER_Heap::root, GNUNET_CONTAINER_Heap::size, GNUNET_CONTAINER_HeapNode::tree_size, and GNUNET_CONTAINER_Heap::walk_pos.

Referenced by ack_proc(), clean_channel(), clean_request(), delete_value(), destroy_route(), expire_oldest_entry(), free_channel_state(), free_destination_entry(), free_reassembly_context(), free_validation_state(), GCP_detach_path(), GNS_resolver_lookup_cancel(), GSF_plan_notify_request_done_(), handle_dht_response(), heap_cleanup_iterator(), receiver_destroy(), remove_client_record(), sender_destroy(), and udp_disconnect_session().

516 {
517  void *ret;
518  struct GNUNET_CONTAINER_Heap *heap;
519 
520  heap = node->heap;
521  CHECK (heap->root);
522  if (heap->walk_pos == node)
524  remove_node (node);
525  heap->size--;
526  ret = node->element;
527  if (heap->walk_pos == node)
528  heap->walk_pos = NULL;
529  GNUNET_free (node);
530 #if EXTRA_CHECKS
531  CHECK (heap->root);
532  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
533  (heap->size == heap->root->tree_size + 1));
534 #endif
535  return ret;
536 }
#define CHECK(n)
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
unsigned int size
Number of elements in the heap.
void * element
Our element.
static void remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Remove the given node 'node' from the tree and update the 'tree_size' fields accordingly.
struct GNUNET_CONTAINER_HeapNode * walk_pos
Current position of our random walk.
Handle to a node in a heap.
unsigned int tree_size
Number of elements below this node in the heap (excluding this node itself).
void * GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
Perform a random walk of the tree.
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_heap_update_cost()

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.

Parameters
nodenode for which the cost is to be changed
new_costnew cost for the node

Definition at line 546 of file container_heap.c.

References GNUNET_CONTAINER_HeapNode::cost, GNUNET_CONTAINER_HeapNode::heap, insert_node(), remove_node(), and GNUNET_CONTAINER_Heap::root.

Referenced by get_redirect_state(), handle_icmp_back(), handle_tcp_back(), handle_udp_back(), put_cb(), read_process_fragment(), reschedule_receiver_timeout(), reschedule_sender_timeout(), route_message(), route_packet(), update_iterator(), and update_next_challenge_time().

548 {
549  struct GNUNET_CONTAINER_Heap *heap = node->heap;
550 
551  remove_node (node);
552  node->cost = new_cost;
553  if (NULL == heap->root)
554  heap->root = node;
555  else
556  insert_node (heap,
557  heap->root,
558  node);
559 }
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 bala...
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.
static void remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Remove the given node 'node' from the tree and update the 'tree_size' fields accordingly.
Handle to a node in a heap.
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
Here is the call graph for this function:
Here is the caller graph for this function: