GNUnet  0.10.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 2487 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 2605 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 2494 of file gnunet_container_lib.h.

2494  {
2500 
2506 };
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 136 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().

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

154 {
155  GNUNET_break(heap->size == 0);
156  GNUNET_free(heap);
157 }
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 167 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().

168 {
169  if (heap->root == NULL)
170  return NULL;
171  return heap->root->element;
172 }
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 206 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().

207 {
208  return heap->size;
209 }
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 219 of file container_heap.c.

References GNUNET_CONTAINER_HeapNode::cost.

221 {
222  return node->cost;
223 }
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 260 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().

263 {
264  (void)node_iterator(heap, heap->root, iterator, iterator_cls);
265 }
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 280 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().

281 {
282  struct GNUNET_CONTAINER_HeapNode *pos;
283  void *element;
284 
285  if (heap->root == NULL)
286  return NULL;
287  pos = heap->walk_pos;
288  if (pos == NULL)
289  pos = heap->root;
290  element = pos->element;
291  heap->walk_pos =
292  (0 ==
294  2)) ? pos->right_child : pos->left_child;
295  return element;
296 }
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 369 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().

371 {
372  struct GNUNET_CONTAINER_HeapNode *node;
373 
374  node = GNUNET_new(struct GNUNET_CONTAINER_HeapNode);
375  node->heap = heap;
376  node->element = element;
377  node->cost = cost;
378  heap->size++;
379  if (NULL == heap->root)
380  heap->root = node;
381  else
382  insert_node(heap, heap->root, node);
383  GNUNET_assert(heap->size == heap->root->tree_size + 1);
384  CHECK(heap->root);
385  return node;
386 }
#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 396 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().

397 {
398  void *ret;
399  struct GNUNET_CONTAINER_HeapNode *root;
400 
401  if (NULL == (root = heap->root))
402  return NULL;
403  heap->size--;
404  ret = root->element;
405  if (root->left_child == NULL)
406  {
407  heap->root = root->right_child;
408  if (root->right_child != NULL)
409  root->right_child->parent = NULL;
410  }
411  else if (root->right_child == NULL)
412  {
413  heap->root = root->left_child;
414  root->left_child->parent = NULL;
415  }
416  else
417  {
418  root->left_child->parent = NULL;
419  root->right_child->parent = NULL;
420  heap->root = root->left_child;
421  insert_node(heap, heap->root, root->right_child);
422  }
423  if (heap->walk_pos == root)
424  heap->walk_pos = heap->root;
425  GNUNET_free(root);
426 #if EXTRA_CHECKS
427  GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) ||
428  (heap->size == heap->root->tree_size + 1));
429  CHECK(heap->root);
430 #endif
431  return ret;
432 }
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.
unsigned int size
Number of elements in the heap.
static int ret
Final status code.
Definition: gnunet-arm.c:89
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 512 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().

513 {
514  void *ret;
515  struct GNUNET_CONTAINER_Heap *heap;
516 
517  heap = node->heap;
518  CHECK(heap->root);
519  if (heap->walk_pos == node)
521  remove_node(node);
522  heap->size--;
523  ret = node->element;
524  if (heap->walk_pos == node)
525  heap->walk_pos = NULL;
526  GNUNET_free(node);
527 #if EXTRA_CHECKS
528  CHECK(heap->root);
529  GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) ||
530  (heap->size == heap->root->tree_size + 1));
531 #endif
532  return ret;
533 }
#define CHECK(n)
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
unsigned int size
Number of elements in the heap.
static int ret
Final status code.
Definition: gnunet-arm.c:89
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 543 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().

545 {
546  struct GNUNET_CONTAINER_Heap *heap = node->heap;
547 
548  remove_node(node);
549  node->cost = new_cost;
550  if (NULL == heap->root)
551  heap->root = node;
552  else
553  insert_node(heap,
554  heap->root,
555  node);
556 }
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: