Heap

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_Heap *	GNUNET_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_HeapNode *	GNUNET_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

typedef uint64_t GNUNET_CONTAINER_HeapCostType

Cost by which elements in a heap can be ordered.

Definition at line 2135 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

cls	closure
node	internal node of the heap
element	value stored at the node
cost	cost associated with the node

Returns

GNUNET_YES if we should continue to iterate, GNUNET_NO if not.

Definition at line 2239 of file gnunet_container_lib.h.

Enumeration Type Documentation

GNUNET_CONTAINER_HeapOrder

enum 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 2142 of file gnunet_container_lib.h.

{
  GNUNET_CONTAINER_HEAP_ORDER_MAX,
 
  GNUNET_CONTAINER_HEAP_ORDER_MIN
};

Function Documentation

GNUNET_CONTAINER_heap_create()

struct GNUNET_CONTAINER_Heap* GNUNET_CONTAINER_heap_create

(

enum GNUNET_CONTAINER_HeapOrder

order

)

Create a new heap.

Parameters

order

how should the heap be sorted?

Returns

handle to the heap

Definition at line 134 of file container_heap.c.

{
  struct GNUNET_CONTAINER_Heap *heap;
 
  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
  heap->order = order;
  return heap;
}

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

heap	heap to destroy

Definition at line 145 of file container_heap.c.

{
  GNUNET_break (heap->size == 0);
  GNUNET_free (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

heap	Heap to inspect.

Returns

Element at the root, or NULL if heap is empty.

Definition at line 153 of file container_heap.c.

{
  if (heap->root == NULL)
    return NULL;
  return heap->root->element;
}

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

heap	the heap to get the size of

Returns

number of elements stored

Definition at line 186 of file container_heap.c.

{
  return heap->size;
}

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

node	the node to get the cost of

Returns

cost of the node

Definition at line 193 of file container_heap.c.

{
  return node->cost;
}

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

heap	the heap
iterator	function to call on each entry
iterator_cls	closure for iterator

Definition at line 227 of file container_heap.c.

{
  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
}

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

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

{
  struct GNUNET_CONTAINER_HeapNode *pos;
  void *element;
 
  if (heap->root == NULL)
    return NULL;
  pos = heap->walk_pos;
  if (pos == NULL)
    pos = heap->root;
  element = pos->element;
  heap->walk_pos =
    (0 ==
     GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
                               2)) ? pos->right_child : pos->left_child;
  return element;
}

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

heap	heap to modify
element	element to insert
cost	cost for the element

Returns

node for the new element

Definition at line 317 of file container_heap.c.

{
  struct GNUNET_CONTAINER_HeapNode *node;
 
  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
  node->heap = heap;
  node->element = element;
  node->cost = cost;
  heap->size++;
  if (NULL == heap->root)
    heap->root = node;
  else
    insert_node (heap, heap->root, node);
  GNUNET_assert (heap->size == heap->root->tree_size + 1);
  CHECK (heap->root);
  return node;
}

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

heap	heap to modify

Returns

element data stored at the root node

Parameters

heap	heap to modify

Returns

element data stored at the root node, NULL if heap is empty

Definition at line 344 of file container_heap.c.

{
  void *ret;
  struct GNUNET_CONTAINER_HeapNode *root;
 
  if (NULL == (root = heap->root))
    return NULL;
  heap->size--;
  ret = root->element;
  if (root->left_child == NULL)
  {
    heap->root = root->right_child;
    if (root->right_child != NULL)
      root->right_child->parent = NULL;
  }
  else if (root->right_child == NULL)
  {
    heap->root = root->left_child;
    root->left_child->parent = NULL;
  }
  else
  {
    root->left_child->parent = NULL;
    root->right_child->parent = NULL;
    heap->root = root->left_child;
    insert_node (heap, heap->root, root->right_child);
  }
  if (heap->walk_pos == root)
    heap->walk_pos = heap->root;
  GNUNET_free (root);
#if EXTRA_CHECKS
  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
                 (heap->size == heap->root->tree_size + 1));
  CHECK (heap->root);
#endif
  return ret;
}

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

node	node to remove

Returns

element data stored at the node, NULL if heap is empty

Parameters

node	node to remove

Returns

element data stored at the node

Definition at line 460 of file container_heap.c.

{
  void *ret;
  struct GNUNET_CONTAINER_Heap *heap;
 
  heap = node->heap;
  CHECK (heap->root);
  if (heap->walk_pos == node)
    (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
  remove_node (node);
  heap->size--;
  ret = node->element;
  if (heap->walk_pos == node)
    heap->walk_pos = NULL;
  GNUNET_free (node);
#if EXTRA_CHECKS
  CHECK (heap->root);
  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
                 (heap->size == heap->root->tree_size + 1));
#endif
  return ret;
}

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

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.

{
  struct GNUNET_CONTAINER_Heap *heap = node->heap;
 
  remove_node (node);
  node->cost = new_cost;
  if (NULL == heap->root)
    heap->root = node;
  else
    insert_node (heap,
                 heap->root,
                 node);
}

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: