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 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... | |
Min- or max-heap with arbitrary element removal.
typedef uint64_t GNUNET_CONTAINER_HeapCostType |
Cost by which elements in a heap can be ordered.
Definition at line 2136 of file gnunet_container_lib.h.
typedef enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_HeapIterator) (void *cls, struct GNUNET_CONTAINER_HeapNode *node, void *element, GNUNET_CONTAINER_HeapCostType cost) |
Iterator for heap.
cls | closure |
node | internal node of the heap |
element | value stored at the node |
cost | cost associated with the node |
Definition at line 2240 of file gnunet_container_lib.h.
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.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create | ( | enum GNUNET_CONTAINER_HeapOrder | order | ) |
Create a new heap.
order | how should the heap be sorted? |
Definition at line 134 of file container_heap.c.
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().
void GNUNET_CONTAINER_heap_destroy | ( | struct GNUNET_CONTAINER_Heap * | heap | ) |
Destroys the heap.
Only call on a heap that is already empty.
heap | heap to destroy |
Definition at line 145 of file container_heap.c.
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().
void * GNUNET_CONTAINER_heap_peek | ( | const struct GNUNET_CONTAINER_Heap * | heap | ) |
Get element stored at the root of heap.
heap | Heap to inspect. |
Definition at line 153 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().
unsigned int GNUNET_CONTAINER_heap_get_size | ( | const struct GNUNET_CONTAINER_Heap * | heap | ) |
Get the current size of the heap.
heap | the heap to get the size of |
Definition at line 186 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(), schedule_peer_transmission(), setup_state_record(), and start_dht_request().
GNUNET_CONTAINER_HeapCostType GNUNET_CONTAINER_heap_node_get_cost | ( | const struct GNUNET_CONTAINER_HeapNode * | node | ) |
Get the current cost of the node.
node | the node to get the cost of |
Definition at line 193 of file container_heap.c.
References GNUNET_CONTAINER_HeapNode::cost.
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.
heap | the heap |
iterator | function to call on each entry |
iterator_cls | closure for iterator |
Definition at line 227 of file container_heap.c.
References node_iterator(), and GNUNET_CONTAINER_Heap::root.
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.
heap | heap to walk |
Definition at line 236 of file container_heap.c.
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().
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.
heap | heap to modify |
element | element to insert |
cost | cost for the element |
Definition at line 317 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 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().
void * GNUNET_CONTAINER_heap_remove_root | ( | struct GNUNET_CONTAINER_Heap * | heap | ) |
Remove root of the heap.
heap | heap to modify |
heap | heap to modify |
Definition at line 344 of file container_heap.c.
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().
void * GNUNET_CONTAINER_heap_remove_node | ( | struct GNUNET_CONTAINER_HeapNode * | node | ) |
Removes a node from the heap.
node | node to remove |
node | node to remove |
Definition at line 460 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 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().
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.
node | node for which the cost is to be changed |
new_cost | new cost for the node |
Definition at line 485 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(), reschedule_receiver_timeout(), reschedule_sender_timeout(), route_message(), route_packet(), update_iterator(), and update_next_challenge_time().