GNUnet  0.11.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", \
32  __VA_ARGS__)
33 
34 #define EXTRA_CHECKS 0
35 
40 {
45 
50 
55 
60 
64  void *element;
65 
70 
75  unsigned int tree_size;
76 };
77 
82 {
87 
92 
96  unsigned int size;
97 
102 };
103 
104 
105 #if EXTRA_CHECKS
106 
111 static void
112 check (const struct GNUNET_CONTAINER_HeapNode *node)
113 {
114  if (NULL == node)
115  return;
116  GNUNET_assert (node->tree_size ==
117  ((node->left_child ==
118  NULL) ? 0 : 1 + node->left_child->tree_size)
119  + ((node->right_child ==
120  NULL) ? 0 : 1 + node->right_child->tree_size));
121  check (node->left_child);
122  check (node->right_child);
123 }
124 
125 
126 #define CHECK(n) check (n)
127 #else
128 #define CHECK(n) do {} while (0)
129 #endif
130 
131 
138 struct GNUNET_CONTAINER_Heap *
140 {
141  struct GNUNET_CONTAINER_Heap *heap;
142 
143  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
144  heap->order = order;
145  return heap;
146 }
147 
148 
155 void
157 {
158  GNUNET_break (heap->size == 0);
159  GNUNET_free (heap);
160 }
161 
162 
169 void *
171 {
172  if (heap->root == NULL)
173  return NULL;
174  return heap->root->element;
175 }
176 
177 
187 int
189  void **element,
191 {
192  if (NULL == heap->root)
193  return GNUNET_NO;
194  if (NULL != element)
195  *element = heap->root->element;
196  if (NULL != cost)
197  *cost = heap->root->cost;
198  return GNUNET_YES;
199 }
200 
201 
208 unsigned int
210 {
211  return heap->size;
212 }
213 
214 
223  *node)
224 {
225  return node->cost;
226 }
227 
228 
238 static int
240  struct GNUNET_CONTAINER_HeapNode *node,
241  GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
242 {
243  if (node == NULL)
244  return GNUNET_YES;
245  if (GNUNET_YES !=
246  node_iterator (heap, node->left_child, iterator, iterator_cls))
247  return GNUNET_NO;
248  if (GNUNET_YES !=
249  node_iterator (heap, node->right_child, iterator, iterator_cls))
250  return GNUNET_NO;
251  return iterator (iterator_cls, node, node->element, node->cost);
252 }
253 
254 
262 void
265  void *iterator_cls)
266 {
267  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
268 }
269 
270 
282 void *
284 {
285  struct GNUNET_CONTAINER_HeapNode *pos;
286  void *element;
287 
288  if (heap->root == NULL)
289  return NULL;
290  pos = heap->walk_pos;
291  if (pos == NULL)
292  pos = heap->root;
293  element = pos->element;
294  heap->walk_pos =
295  (0 ==
297  2)) ? pos->right_child : pos->left_child;
298  return element;
299 }
300 
301 
310 static void
312  struct GNUNET_CONTAINER_HeapNode *pos,
313  struct GNUNET_CONTAINER_HeapNode *node)
314 {
316 
317  GNUNET_assert (node->parent == NULL);
318  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
319  node->cost)
320  : (pos->cost <= node->cost))
321  {
322  /* node is descendent of pos */
323  pos->tree_size += (1 + node->tree_size);
324  if (pos->left_child == NULL)
325  {
326  pos->left_child = node;
327  node->parent = pos;
328  return;
329  }
330  if (pos->right_child == NULL)
331  {
332  pos->right_child = node;
333  node->parent = pos;
334  return;
335  }
336  /* keep it balanced by descending into smaller subtree */
337  if (pos->left_child->tree_size < pos->right_child->tree_size)
338  pos = pos->left_child;
339  else
340  pos = pos->right_child;
341  }
342  /* make 'node' parent of 'pos' */
343  parent = pos->parent;
344  pos->parent = NULL;
345  node->parent = parent;
346  if (NULL == parent)
347  {
348  heap->root = node;
349  }
350  else
351  {
352  if (parent->left_child == pos)
353  parent->left_child = node;
354  else
355  parent->right_child = node;
356  }
357  /* insert 'pos' below 'node' */
358  insert_node (heap, node, pos);
359  CHECK (pos);
360 }
361 
362 
374 {
375  struct GNUNET_CONTAINER_HeapNode *node;
376 
377  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
378  node->heap = heap;
379  node->element = element;
380  node->cost = cost;
381  heap->size++;
382  if (NULL == heap->root)
383  heap->root = node;
384  else
385  insert_node (heap, heap->root, node);
386  GNUNET_assert (heap->size == heap->root->tree_size + 1);
387  CHECK (heap->root);
388  return node;
389 }
390 
391 
398 void *
400 {
401  void *ret;
402  struct GNUNET_CONTAINER_HeapNode *root;
403 
404  if (NULL == (root = heap->root))
405  return NULL;
406  heap->size--;
407  ret = root->element;
408  if (root->left_child == NULL)
409  {
410  heap->root = root->right_child;
411  if (root->right_child != NULL)
412  root->right_child->parent = NULL;
413  }
414  else if (root->right_child == NULL)
415  {
416  heap->root = root->left_child;
417  root->left_child->parent = NULL;
418  }
419  else
420  {
421  root->left_child->parent = NULL;
422  root->right_child->parent = NULL;
423  heap->root = root->left_child;
424  insert_node (heap, heap->root, root->right_child);
425  }
426  if (heap->walk_pos == root)
427  heap->walk_pos = heap->root;
428  GNUNET_free (root);
429 #if EXTRA_CHECKS
430  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
431  (heap->size == heap->root->tree_size + 1));
432  CHECK (heap->root);
433 #endif
434  return ret;
435 }
436 
437 
444 static void
446 {
447  struct GNUNET_CONTAINER_HeapNode *ancestor;
448  struct GNUNET_CONTAINER_Heap *heap = node->heap;
449 
450  /* update 'size' of the ancestors */
451  ancestor = node;
452  while (NULL != (ancestor = ancestor->parent))
453  ancestor->tree_size--;
454 
455  /* update 'size' of node itself */
456  if (node->left_child != NULL)
457  node->tree_size -= (1 + node->left_child->tree_size);
458  if (node->right_child != NULL)
459  node->tree_size -= (1 + node->right_child->tree_size);
460 
461  /* unlink 'node' itself and insert children in its place */
462  if (node->parent == NULL)
463  {
464  if (node->left_child != NULL)
465  {
466  heap->root = node->left_child;
467  node->left_child->parent = NULL;
468  if (node->right_child != NULL)
469  {
470  node->right_child->parent = NULL;
471  insert_node (heap, heap->root, node->right_child);
472  }
473  }
474  else
475  {
476  heap->root = node->right_child;
477  if (node->right_child != NULL)
478  node->right_child->parent = NULL;
479  }
480  }
481  else
482  {
483  if (node->parent->left_child == node)
484  node->parent->left_child = NULL;
485  else
486  node->parent->right_child = NULL;
487  if (node->left_child != NULL)
488  {
489  node->left_child->parent = NULL;
490  node->parent->tree_size -= (1 + node->left_child->tree_size);
491  insert_node (heap, node->parent, node->left_child);
492  }
493  if (node->right_child != NULL)
494  {
495  node->right_child->parent = NULL;
496  node->parent->tree_size -= (1 + node->right_child->tree_size);
497  insert_node (heap, node->parent, node->right_child);
498  }
499  }
500  node->parent = NULL;
501  node->left_child = NULL;
502  node->right_child = NULL;
503  GNUNET_assert (node->tree_size == 0);
504  CHECK (heap->root);
505 }
506 
507 
514 void *
516 {
517  void *ret;
518  struct GNUNET_CONTAINER_Heap *heap;
519 
520  heap = node->heap;
521  CHECK (heap->root);
522  if (heap->walk_pos == node)
524  remove_node (node);
525  heap->size--;
526  ret = node->element;
527  if (heap->walk_pos == node)
528  heap->walk_pos = NULL;
529  GNUNET_free (node);
530 #if EXTRA_CHECKS
531  CHECK (heap->root);
532  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
533  (heap->size == heap->root->tree_size + 1));
534 #endif
535  return ret;
536 }
537 
538 
545 void
548 {
549  struct GNUNET_CONTAINER_Heap *heap = node->heap;
550 
551  remove_node (node);
552  node->cost = new_cost;
553  if (NULL == heap->root)
554  heap->root = node;
555  else
556  insert_node (heap,
557  heap->root,
558  node);
559 }
560 
561 
562 /* 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.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
#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 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.