GNUnet  0.20.0

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

Collaboration diagram for Heap:

Typedefs

typedef uint64_t GNUNET_CONTAINER_HeapCostType
 Cost by which elements in a heap can be ordered. More...
 
typedef enum GNUNET_GenericReturnValue(* 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 2136 of file gnunet_container_lib.h.

◆ GNUNET_CONTAINER_HeapIterator

typedef enum GNUNET_GenericReturnValue(* 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 2240 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 2143 of file gnunet_container_lib.h.

2144 {
2150 
2156 };
@ GNUNET_CONTAINER_HEAP_ORDER_MIN
Heap with the minimum cost at the root.
@ GNUNET_CONTAINER_HEAP_ORDER_MAX
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 135 of file container_heap.c.

136 {
137  struct GNUNET_CONTAINER_Heap *heap;
138 
139  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
140  heap->order = order;
141  return heap;
142 }
#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?

References GNUNET_new, 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().

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 146 of file container_heap.c.

147 {
148  GNUNET_break (heap->size == 0);
149  GNUNET_free (heap);
150 }
#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.
unsigned int size
Number of elements in the heap.

References GNUNET_break, GNUNET_free, and GNUNET_CONTAINER_Heap::size.

Referenced by cleanup(), destroy_peer(), do_shutdown(), free_virtual_link(), GCO_shutdown(), GCP_drop_owned_paths(), GNS_resolver_done(), GSF_plan_notify_peer_disconnect_(), libgnunet_plugin_datacache_heap_done(), and libgnunet_plugin_transport_udp_init().

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 154 of file container_heap.c.

155 {
156  if (heap->root == NULL)
157  return NULL;
158  return heap->root->element;
159 }
void * element
Our element.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.

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

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 187 of file container_heap.c.

188 {
189  return heap->size;
190 }

References GNUNET_CONTAINER_Heap::size.

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

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 194 of file container_heap.c.

196 {
197  return node->cost;
198 }
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.

References GNUNET_CONTAINER_HeapNode::cost.

◆ 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

Definition at line 228 of file container_heap.c.

231 {
232  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
233 }
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.
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.

References iterator(), node_iterator(), and GNUNET_CONTAINER_Heap::root.

Referenced by read_process_fragment(), and udp_disconnect_session().

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 237 of file container_heap.c.

238 {
239  struct GNUNET_CONTAINER_HeapNode *pos;
240  void *element;
241 
242  if (heap->root == NULL)
243  return NULL;
244  pos = heap->walk_pos;
245  if (pos == NULL)
246  pos = heap->root;
247  element = pos->element;
248  heap->walk_pos =
249  (0 ==
251  2)) ? pos->right_child : pos->left_child;
252  return element;
253 }
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_WEAK
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
struct GNUNET_CONTAINER_HeapNode * walk_pos
Current position of our random walk.

References GNUNET_CONTAINER_HeapNode::element, GNUNET_CRYPTO_QUALITY_WEAK, GNUNET_CRYPTO_random_u32(), GNUNET_CONTAINER_HeapNode::heap, 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().

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 318 of file container_heap.c.

320 {
321  struct GNUNET_CONTAINER_HeapNode *node;
322 
323  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
324  node->heap = heap;
325  node->element = element;
326  node->cost = cost;
327  heap->size++;
328  if (NULL == heap->root)
329  heap->root = node;
330  else
331  insert_node (heap, heap->root, node);
333  CHECK (heap->root);
334  return node;
335 }
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 CHECK(n)
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
unsigned int tree_size
Number of elements below this node in the heap (excluding this node itself).

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 check_dht_local_get_result_seen(), check_dht_local_put(), GCP_attach_path(), GDS_ROUTING_add(), get_cb(), GSF_pending_request_create_(), handle_client_redirect_to_ip(), handle_client_redirect_to_service(), handle_connection_create(), 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(), and update_next_challenge_time().

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 345 of file container_heap.c.

346 {
347  void *ret;
348  struct GNUNET_CONTAINER_HeapNode *root;
349 
350  if (NULL == (root = heap->root))
351  return NULL;
352  heap->size--;
353  ret = root->element;
354  if (root->left_child == NULL)
355  {
356  heap->root = root->right_child;
357  if (root->right_child != NULL)
358  root->right_child->parent = NULL;
359  }
360  else if (root->right_child == NULL)
361  {
362  heap->root = root->left_child;
363  root->left_child->parent = NULL;
364  }
365  else
366  {
367  root->left_child->parent = NULL;
368  root->right_child->parent = NULL;
369  heap->root = root->left_child;
370  insert_node (heap, heap->root, root->right_child);
371  }
372  if (heap->walk_pos == root)
373  heap->walk_pos = heap->root;
374  GNUNET_free (root);
375 #if EXTRA_CHECKS
376  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
377  (heap->size == heap->root->tree_size + 1));
378  CHECK (heap->root);
379 #endif
380  return ret;
381 }
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
struct GNUNET_CONTAINER_HeapNode * parent
Parent node.

References CHECK, GNUNET_CONTAINER_HeapNode::element, GNUNET_assert, GNUNET_free, GNUNET_CONTAINER_HeapNode::heap, 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 check_dht_local_put(), do_shutdown(), drop_paths(), GCP_drop_owned_paths(), GSF_plan_notify_peer_disconnect_(), heap_plugin_get_replication(), libgnunet_plugin_datacache_heap_done(), path_heap_cleanup(), process_queue(), read_process_fragment(), schedule_peer_transmission(), setup_state_record(), and start_dht_request().

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 461 of file container_heap.c.

462 {
463  void *ret;
464  struct GNUNET_CONTAINER_Heap *heap;
465 
466  heap = node->heap;
467  CHECK (heap->root);
468  if (heap->walk_pos == node)
470  remove_node (node);
471  heap->size--;
472  ret = node->element;
473  if (heap->walk_pos == node)
474  heap->walk_pos = NULL;
475  GNUNET_free (node);
476 #if EXTRA_CHECKS
477  CHECK (heap->root);
478  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
479  (heap->size == heap->root->tree_size + 1));
480 #endif
481  return ret;
482 }
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_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
Perform a random walk of the tree.

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_query_record(), sender_destroy(), and udp_disconnect_session().

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 486 of file container_heap.c.

488 {
489  struct GNUNET_CONTAINER_Heap *heap = node->heap;
490 
491  remove_node (node);
492  node->cost = new_cost;
493  if (NULL == heap->root)
494  heap->root = node;
495  else
496  insert_node (heap,
497  heap->root,
498  node);
499 }

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(), read_process_fragment(), reschedule_receiver_timeout(), reschedule_sender_timeout(), route_message(), route_packet(), update_iterator(), and update_next_challenge_time().

Here is the call graph for this function:
Here is the caller graph for this function: