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 
39 {
44 
49 
54 
59 
63  void *element;
64 
69 
74  unsigned int tree_size;
75 
76 };
77 
82 {
83 
88 
93 
97  unsigned int size;
98 
103 
104 };
105 
106 
107 #if EXTRA_CHECKS
108 
113 static void
114 check (const struct GNUNET_CONTAINER_HeapNode *node)
115 {
116  if (NULL == node)
117  return;
118  GNUNET_assert (node->tree_size ==
119  ((node->left_child ==
120  NULL) ? 0 : 1 + node->left_child->tree_size) +
121  ((node->right_child ==
122  NULL) ? 0 : 1 + node->right_child->tree_size));
123  check (node->left_child);
124  check (node->right_child);
125 }
126 
127 
128 #define CHECK(n) check(n)
129 #else
130 #define CHECK(n) do {} while (0)
131 #endif
132 
133 
140 struct GNUNET_CONTAINER_Heap *
142 {
143  struct GNUNET_CONTAINER_Heap *heap;
144 
145  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
146  heap->order = order;
147  return heap;
148 }
149 
150 
157 void
159 {
160  GNUNET_break (heap->size == 0);
161  GNUNET_free (heap);
162 }
163 
164 
171 void *
173 {
174  if (heap->root == NULL)
175  return NULL;
176  return heap->root->element;
177 }
178 
179 
189 int
191  void **element,
193 {
194  if (NULL == heap->root)
195  return GNUNET_NO;
196  if (NULL != element)
197  *element = heap->root->element;
198  if (NULL != cost)
199  *cost = heap->root->cost;
200  return GNUNET_YES;
201 }
202 
203 
210 unsigned int
212 {
213  return heap->size;
214 }
215 
216 
225  *node)
226 {
227  return node->cost;
228 }
229 
230 
240 static int
242  struct GNUNET_CONTAINER_HeapNode *node,
243  GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
244 {
245  if (node == NULL)
246  return GNUNET_YES;
247  if (GNUNET_YES !=
248  node_iterator (heap, node->left_child, iterator, iterator_cls))
249  return GNUNET_NO;
250  if (GNUNET_YES !=
251  node_iterator (heap, node->right_child, iterator, iterator_cls))
252  return GNUNET_NO;
253  return iterator (iterator_cls, node, node->element, node->cost);
254 }
255 
256 
264 void
267  void *iterator_cls)
268 {
269  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
270 }
271 
272 
284 void *
286 {
287  struct GNUNET_CONTAINER_HeapNode *pos;
288  void *element;
289 
290  if (heap->root == NULL)
291  return NULL;
292  pos = heap->walk_pos;
293  if (pos == NULL)
294  pos = heap->root;
295  element = pos->element;
296  heap->walk_pos =
297  (0 ==
299  2)) ? pos->right_child : pos->left_child;
300  return element;
301 }
302 
303 
312 static void
314  struct GNUNET_CONTAINER_HeapNode *pos,
315  struct GNUNET_CONTAINER_HeapNode *node)
316 {
318 
319  GNUNET_assert (node->parent == NULL);
320  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
321  node->cost)
322  : (pos->cost <= node->cost))
323  {
324  /* node is descendent of pos */
325  pos->tree_size += (1 + node->tree_size);
326  if (pos->left_child == NULL)
327  {
328  pos->left_child = node;
329  node->parent = pos;
330  return;
331  }
332  if (pos->right_child == NULL)
333  {
334  pos->right_child = node;
335  node->parent = pos;
336  return;
337  }
338  /* keep it balanced by descending into smaller subtree */
339  if (pos->left_child->tree_size < pos->right_child->tree_size)
340  pos = pos->left_child;
341  else
342  pos = pos->right_child;
343  }
344  /* make 'node' parent of 'pos' */
345  parent = pos->parent;
346  pos->parent = NULL;
347  node->parent = parent;
348  if (NULL == parent)
349  {
350  heap->root = node;
351  }
352  else
353  {
354  if (parent->left_child == pos)
355  parent->left_child = node;
356  else
357  parent->right_child = node;
358  }
359  /* insert 'pos' below 'node' */
360  insert_node (heap, node, pos);
361  CHECK (pos);
362 }
363 
364 
376 {
377  struct GNUNET_CONTAINER_HeapNode *node;
378 
379  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
380  node->heap = heap;
381  node->element = element;
382  node->cost = cost;
383  heap->size++;
384  if (NULL == heap->root)
385  heap->root = node;
386  else
387  insert_node (heap, heap->root, node);
388  GNUNET_assert (heap->size == heap->root->tree_size + 1);
389  CHECK (heap->root);
390  return node;
391 }
392 
393 
400 void *
402 {
403  void *ret;
404  struct GNUNET_CONTAINER_HeapNode *root;
405 
406  if (NULL == (root = heap->root))
407  return NULL;
408  heap->size--;
409  ret = root->element;
410  if (root->left_child == NULL)
411  {
412  heap->root = root->right_child;
413  if (root->right_child != NULL)
414  root->right_child->parent = NULL;
415  }
416  else if (root->right_child == NULL)
417  {
418  heap->root = root->left_child;
419  root->left_child->parent = NULL;
420  }
421  else
422  {
423  root->left_child->parent = NULL;
424  root->right_child->parent = NULL;
425  heap->root = root->left_child;
426  insert_node (heap, heap->root, root->right_child);
427  }
428  if (heap->walk_pos == root)
429  heap->walk_pos = heap->root;
430  GNUNET_free (root);
431 #if EXTRA_CHECKS
432  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
433  (heap->size == heap->root->tree_size + 1));
434  CHECK (heap->root);
435 #endif
436  return ret;
437 }
438 
439 
446 static void
448 {
449  struct GNUNET_CONTAINER_HeapNode *ancestor;
450  struct GNUNET_CONTAINER_Heap *heap = node->heap;
451 
452  /* update 'size' of the ancestors */
453  ancestor = node;
454  while (NULL != (ancestor = ancestor->parent))
455  ancestor->tree_size--;
456 
457  /* update 'size' of node itself */
458  if (node->left_child != NULL)
459  node->tree_size -= (1 + node->left_child->tree_size);
460  if (node->right_child != NULL)
461  node->tree_size -= (1 + node->right_child->tree_size);
462 
463  /* unlink 'node' itself and insert children in its place */
464  if (node->parent == NULL)
465  {
466  if (node->left_child != NULL)
467  {
468  heap->root = node->left_child;
469  node->left_child->parent = NULL;
470  if (node->right_child != NULL)
471  {
472  node->right_child->parent = NULL;
473  insert_node (heap, heap->root, node->right_child);
474  }
475  }
476  else
477  {
478  heap->root = node->right_child;
479  if (node->right_child != NULL)
480  node->right_child->parent = NULL;
481  }
482  }
483  else
484  {
485  if (node->parent->left_child == node)
486  node->parent->left_child = NULL;
487  else
488  node->parent->right_child = NULL;
489  if (node->left_child != NULL)
490  {
491  node->left_child->parent = NULL;
492  node->parent->tree_size -= (1 + node->left_child->tree_size);
493  insert_node (heap, node->parent, node->left_child);
494  }
495  if (node->right_child != NULL)
496  {
497  node->right_child->parent = NULL;
498  node->parent->tree_size -= (1 + node->right_child->tree_size);
499  insert_node (heap, node->parent, node->right_child);
500  }
501  }
502  node->parent = NULL;
503  node->left_child = NULL;
504  node->right_child = NULL;
505  GNUNET_assert (node->tree_size == 0);
506  CHECK (heap->root);
507 }
508 
509 
516 void *
518 {
519  void *ret;
520  struct GNUNET_CONTAINER_Heap *heap;
521 
522  heap = node->heap;
523  CHECK (heap->root);
524  if (heap->walk_pos == node)
526  remove_node (node);
527  heap->size--;
528  ret = node->element;
529  if (heap->walk_pos == node)
530  heap->walk_pos = NULL;
531  GNUNET_free (node);
532 #if EXTRA_CHECKS
533  CHECK (heap->root);
534  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
535  (heap->size == heap->root->tree_size + 1));
536 #endif
537  return ret;
538 }
539 
540 
547 void
550 {
551  struct GNUNET_CONTAINER_Heap *heap = node->heap;
552 
553  remove_node (node);
554  node->cost = new_cost;
555  if (NULL == heap->root)
556  heap->root = node;
557  else
558  insert_node (heap,
559  heap->root,
560  node);
561 }
562 
563 
564 /* 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:81
#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:80
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.