GNUnet  0.10.x
container_heap.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2008, 2009 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 
28 #include "platform.h"
29 #include "gnunet_container_lib.h"
30 
31 #define LOG(kind, ...) GNUNET_log_from(kind, "util-container-heap", __VA_ARGS__)
32 
33 #define EXTRA_CHECKS 0
34 
43 
48 
53 
58 
62  void *element;
63 
68 
73  unsigned int tree_size;
74 };
75 
84 
89 
93  unsigned int size;
94 
99 };
100 
101 
102 #if EXTRA_CHECKS
103 
108 static void
109 check(const struct GNUNET_CONTAINER_HeapNode *node)
110 {
111  if (NULL == node)
112  return;
113  GNUNET_assert(node->tree_size ==
114  ((node->left_child ==
115  NULL) ? 0 : 1 + node->left_child->tree_size) +
116  ((node->right_child ==
117  NULL) ? 0 : 1 + node->right_child->tree_size));
118  check(node->left_child);
119  check(node->right_child);
120 }
121 
122 
123 #define CHECK(n) check(n)
124 #else
125 #define CHECK(n) do {} while (0)
126 #endif
127 
128 
135 struct GNUNET_CONTAINER_Heap *
137 {
138  struct GNUNET_CONTAINER_Heap *heap;
139 
140  heap = GNUNET_new(struct GNUNET_CONTAINER_Heap);
141  heap->order = order;
142  return heap;
143 }
144 
145 
152 void
154 {
155  GNUNET_break(heap->size == 0);
156  GNUNET_free(heap);
157 }
158 
159 
166 void *
168 {
169  if (heap->root == NULL)
170  return NULL;
171  return heap->root->element;
172 }
173 
174 
184 int
186  void **element,
188 {
189  if (NULL == heap->root)
190  return GNUNET_NO;
191  if (NULL != element)
192  *element = heap->root->element;
193  if (NULL != cost)
194  *cost = heap->root->cost;
195  return GNUNET_YES;
196 }
197 
198 
205 unsigned int
207 {
208  return heap->size;
209 }
210 
211 
220  *node)
221 {
222  return node->cost;
223 }
224 
225 
235 static int
237  struct GNUNET_CONTAINER_HeapNode *node,
238  GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
239 {
240  if (node == NULL)
241  return GNUNET_YES;
242  if (GNUNET_YES !=
243  node_iterator(heap, node->left_child, iterator, iterator_cls))
244  return GNUNET_NO;
245  if (GNUNET_YES !=
246  node_iterator(heap, node->right_child, iterator, iterator_cls))
247  return GNUNET_NO;
248  return iterator(iterator_cls, node, node->element, node->cost);
249 }
250 
251 
259 void
262  void *iterator_cls)
263 {
264  (void)node_iterator(heap, heap->root, iterator, iterator_cls);
265 }
266 
267 
279 void *
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 }
297 
298 
307 static void
309  struct GNUNET_CONTAINER_HeapNode *pos,
310  struct GNUNET_CONTAINER_HeapNode *node)
311 {
313 
314  GNUNET_assert(node->parent == NULL);
315  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
316  node->cost)
317  : (pos->cost <= node->cost))
318  {
319  /* node is descendent of pos */
320  pos->tree_size += (1 + node->tree_size);
321  if (pos->left_child == NULL)
322  {
323  pos->left_child = node;
324  node->parent = pos;
325  return;
326  }
327  if (pos->right_child == NULL)
328  {
329  pos->right_child = node;
330  node->parent = pos;
331  return;
332  }
333  /* keep it balanced by descending into smaller subtree */
334  if (pos->left_child->tree_size < pos->right_child->tree_size)
335  pos = pos->left_child;
336  else
337  pos = pos->right_child;
338  }
339  /* make 'node' parent of 'pos' */
340  parent = pos->parent;
341  pos->parent = NULL;
342  node->parent = parent;
343  if (NULL == parent)
344  {
345  heap->root = node;
346  }
347  else
348  {
349  if (parent->left_child == pos)
350  parent->left_child = node;
351  else
352  parent->right_child = node;
353  }
354  /* insert 'pos' below 'node' */
355  insert_node(heap, node, pos);
356  CHECK(pos);
357 }
358 
359 
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 }
387 
388 
395 void *
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 }
433 
434 
441 static void
443 {
444  struct GNUNET_CONTAINER_HeapNode *ancestor;
445  struct GNUNET_CONTAINER_Heap *heap = node->heap;
446 
447  /* update 'size' of the ancestors */
448  ancestor = node;
449  while (NULL != (ancestor = ancestor->parent))
450  ancestor->tree_size--;
451 
452  /* update 'size' of node itself */
453  if (node->left_child != NULL)
454  node->tree_size -= (1 + node->left_child->tree_size);
455  if (node->right_child != NULL)
456  node->tree_size -= (1 + node->right_child->tree_size);
457 
458  /* unlink 'node' itself and insert children in its place */
459  if (node->parent == NULL)
460  {
461  if (node->left_child != NULL)
462  {
463  heap->root = node->left_child;
464  node->left_child->parent = NULL;
465  if (node->right_child != NULL)
466  {
467  node->right_child->parent = NULL;
468  insert_node(heap, heap->root, node->right_child);
469  }
470  }
471  else
472  {
473  heap->root = node->right_child;
474  if (node->right_child != NULL)
475  node->right_child->parent = NULL;
476  }
477  }
478  else
479  {
480  if (node->parent->left_child == node)
481  node->parent->left_child = NULL;
482  else
483  node->parent->right_child = NULL;
484  if (node->left_child != NULL)
485  {
486  node->left_child->parent = NULL;
487  node->parent->tree_size -= (1 + node->left_child->tree_size);
488  insert_node(heap, node->parent, node->left_child);
489  }
490  if (node->right_child != NULL)
491  {
492  node->right_child->parent = NULL;
493  node->parent->tree_size -= (1 + node->right_child->tree_size);
494  insert_node(heap, node->parent, node->right_child);
495  }
496  }
497  node->parent = NULL;
498  node->left_child = NULL;
499  node->right_child = NULL;
500  GNUNET_assert(node->tree_size == 0);
501  CHECK(heap->root);
502 }
503 
504 
511 void *
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 }
534 
535 
542 void
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 }
557 
558 
559 /* end of heap.c */
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
#define CHECK(n)
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.
static void insert_node(struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *pos, struct GNUNET_CONTAINER_HeapNode *node)
Insert the given node &#39;node&#39; into the subtree starting at &#39;pos&#39; (while keeping the tree somewhat bala...
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.
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_new(type)
Allocate a struct or union of the given type.
unsigned int size
Number of elements in the heap.
static int ret
Final status code.
Definition: gnunet-arm.c:89
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.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
GNUNET_CONTAINER_HeapOrder
Heap type, either max or min.
void * element
Our element.
static void remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Remove the given node &#39;node&#39; from the tree and update the &#39;tree_size&#39; fields accordingly.
int GNUNET_CONTAINER_heap_peek2(const struct GNUNET_CONTAINER_Heap *heap, void **element, GNUNET_CONTAINER_HeapCostType *cost)
Get element and cost stored at the root of heap.
int(* GNUNET_CONTAINER_HeapIterator)(void *cls, struct GNUNET_CONTAINER_HeapNode *node, void *element, GNUNET_CONTAINER_HeapCostType cost)
Iterator for heap.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
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_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
void * GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
Perform a random walk of the tree.
Node in the heap.
unsigned int GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
Get the current size of the heap.
enum GNUNET_CONTAINER_HeapOrder order
How is the heap sorted?
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
struct GNUNET_CONTAINER_Heap * GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order)
Create a new heap.
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
struct GNUNET_CONTAINER_HeapNode * parent
Parent node.
Heap with the maximum cost at the root.
void * GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap)
Remove root of the heap.
#define GNUNET_YES
Definition: gnunet_common.h:77
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.
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
GNUNET_CONTAINER_HeapCostType GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode *node)
Get the current cost of the node.
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
#define GNUNET_free(ptr)
Wrapper around free.