GNUnet 0.22.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 134 of file container_heap.c.

135{
136 struct GNUNET_CONTAINER_Heap *heap;
137
138 heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
139 heap->order = order;
140 return heap;
141}
#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(), 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 145 of file container_heap.c.

146{
147 GNUNET_break (heap->size == 0);
148 GNUNET_free (heap);
149}
#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 __attribute__(), cleanup(), destroy_peer(), do_shutdown(), free_virtual_link(), 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(), and libgnunet_plugin_datastore_heap_done().

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

154{
155 if (heap->root == NULL)
156 return NULL;
157 return heap->root->element;
158}
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 186 of file container_heap.c.

187{
188 return heap->size;
189}

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(), 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 193 of file container_heap.c.

195{
196 return node->cost;
197}
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 227 of file container_heap.c.

230{
231 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
232}
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.

References node_iterator(), and GNUNET_CONTAINER_Heap::root.

Here is the call 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 236 of file container_heap.c.

237{
238 struct GNUNET_CONTAINER_HeapNode *pos;
239 void *element;
240
241 if (heap->root == NULL)
242 return NULL;
243 pos = heap->walk_pos;
244 if (pos == NULL)
245 pos = heap->root;
246 element = pos->element;
247 heap->walk_pos =
248 (0 ==
250 2)) ? pos->right_child : pos->left_child;
251 return element;
252}
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 317 of file container_heap.c.

319{
320 struct GNUNET_CONTAINER_HeapNode *node;
321
323 node->heap = heap;
324 node->element = element;
325 node->cost = cost;
326 heap->size++;
327 if (NULL == heap->root)
328 heap->root = node;
329 else
330 insert_node (heap, heap->root, node);
332 CHECK (heap->root);
333 return node;
334}
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 create_receiver(), 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(), plan(), route_packet(), schedule_peer_transmission(), setup_sender(), setup_state_record(), start_dht_request(), transmit_next_request_task(), 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 344 of file container_heap.c.

345{
346 void *ret;
347 struct GNUNET_CONTAINER_HeapNode *root;
348
349 if (NULL == (root = heap->root))
350 return NULL;
351 heap->size--;
352 ret = root->element;
353 if (root->left_child == NULL)
354 {
355 heap->root = root->right_child;
356 if (root->right_child != NULL)
357 root->right_child->parent = NULL;
358 }
359 else if (root->right_child == NULL)
360 {
361 heap->root = root->left_child;
362 root->left_child->parent = NULL;
363 }
364 else
365 {
366 root->left_child->parent = NULL;
367 root->right_child->parent = NULL;
368 heap->root = root->left_child;
370 }
371 if (heap->walk_pos == root)
373 GNUNET_free (root);
374#if EXTRA_CHECKS
375 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
376 (heap->size == heap->root->tree_size + 1));
377 CHECK (heap->root);
378#endif
379 return ret;
380}
static int ret
Final status code.
Definition: gnunet-arm.c:93
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 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(), schedule_peer_transmission(), setup_state_record(), start_dht_request(), and transmit_next_request_task().

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

461{
462 void *ret;
463 struct GNUNET_CONTAINER_Heap *heap;
464
465 heap = node->heap;
466 CHECK (heap->root);
467 if (heap->walk_pos == node)
469 remove_node (node);
470 heap->size--;
471 ret = node->element;
472 if (heap->walk_pos == node)
473 heap->walk_pos = NULL;
474 GNUNET_free (node);
475#if EXTRA_CHECKS
476 CHECK (heap->root);
477 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
478 (heap->size == heap->root->tree_size + 1));
479#endif
480 return ret;
481}
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 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(), receiver_destroy(), remove_client_query_record(), and sender_destroy().

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

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

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(), 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: