GNUnet  0.17.6
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
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 
132 struct GNUNET_CONTAINER_Heap *
134 {
135  struct GNUNET_CONTAINER_Heap *heap;
136 
137  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
138  heap->order = order;
139  return heap;
140 }
141 
142 
143 void
145 {
146  GNUNET_break (heap->size == 0);
147  GNUNET_free (heap);
148 }
149 
150 
151 void *
153 {
154  if (heap->root == NULL)
155  return NULL;
156  return heap->root->element;
157 }
158 
159 
169 int
171  void **element,
173 {
174  if (NULL == heap->root)
175  return GNUNET_NO;
176  if (NULL != element)
177  *element = heap->root->element;
178  if (NULL != cost)
179  *cost = heap->root->cost;
180  return GNUNET_YES;
181 }
182 
183 
184 unsigned int
186 {
187  return heap->size;
188 }
189 
190 
193  *node)
194 {
195  return node->cost;
196 }
197 
198 
208 static int
210  struct GNUNET_CONTAINER_HeapNode *node,
211  GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
212 {
213  if (node == NULL)
214  return GNUNET_YES;
215  if (GNUNET_YES !=
216  node_iterator (heap, node->left_child, iterator, iterator_cls))
217  return GNUNET_NO;
218  if (GNUNET_YES !=
219  node_iterator (heap, node->right_child, iterator, iterator_cls))
220  return GNUNET_NO;
221  return iterator (iterator_cls, node, node->element, node->cost);
222 }
223 
224 
225 void
228  void *iterator_cls)
229 {
230  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
231 }
232 
233 
234 void *
236 {
237  struct GNUNET_CONTAINER_HeapNode *pos;
238  void *element;
239 
240  if (heap->root == NULL)
241  return NULL;
242  pos = heap->walk_pos;
243  if (pos == NULL)
244  pos = heap->root;
245  element = pos->element;
246  heap->walk_pos =
247  (0 ==
249  2)) ? pos->right_child : pos->left_child;
250  return element;
251 }
252 
253 
262 static void
264  struct GNUNET_CONTAINER_HeapNode *pos,
265  struct GNUNET_CONTAINER_HeapNode *node)
266 {
268 
269  GNUNET_assert (node->parent == NULL);
270  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
271  node->cost)
272  : (pos->cost <= node->cost))
273  {
274  /* node is descendent of pos */
275  pos->tree_size += (1 + node->tree_size);
276  if (pos->left_child == NULL)
277  {
278  pos->left_child = node;
279  node->parent = pos;
280  return;
281  }
282  if (pos->right_child == NULL)
283  {
284  pos->right_child = node;
285  node->parent = pos;
286  return;
287  }
288  /* keep it balanced by descending into smaller subtree */
289  if (pos->left_child->tree_size < pos->right_child->tree_size)
290  pos = pos->left_child;
291  else
292  pos = pos->right_child;
293  }
294  /* make 'node' parent of 'pos' */
295  parent = pos->parent;
296  pos->parent = NULL;
297  node->parent = parent;
298  if (NULL == parent)
299  {
300  heap->root = node;
301  }
302  else
303  {
304  if (parent->left_child == pos)
305  parent->left_child = node;
306  else
307  parent->right_child = node;
308  }
309  /* insert 'pos' below 'node' */
310  insert_node (heap, node, pos);
311  CHECK (pos);
312 }
313 
314 
318 {
319  struct GNUNET_CONTAINER_HeapNode *node;
320 
321  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
322  node->heap = heap;
323  node->element = element;
324  node->cost = cost;
325  heap->size++;
326  if (NULL == heap->root)
327  heap->root = node;
328  else
329  insert_node (heap, heap->root, node);
331  CHECK (heap->root);
332  return node;
333 }
334 
335 
342 void *
344 {
345  void *ret;
346  struct GNUNET_CONTAINER_HeapNode *root;
347 
348  if (NULL == (root = heap->root))
349  return NULL;
350  heap->size--;
351  ret = root->element;
352  if (root->left_child == NULL)
353  {
354  heap->root = root->right_child;
355  if (root->right_child != NULL)
356  root->right_child->parent = NULL;
357  }
358  else if (root->right_child == NULL)
359  {
360  heap->root = root->left_child;
361  root->left_child->parent = NULL;
362  }
363  else
364  {
365  root->left_child->parent = NULL;
366  root->right_child->parent = NULL;
367  heap->root = root->left_child;
368  insert_node (heap, heap->root, root->right_child);
369  }
370  if (heap->walk_pos == root)
371  heap->walk_pos = heap->root;
372  GNUNET_free (root);
373 #if EXTRA_CHECKS
374  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
375  (heap->size == heap->root->tree_size + 1));
376  CHECK (heap->root);
377 #endif
378  return ret;
379 }
380 
381 
388 static void
390 {
391  struct GNUNET_CONTAINER_HeapNode *ancestor;
392  struct GNUNET_CONTAINER_Heap *heap = node->heap;
393 
394  /* update 'size' of the ancestors */
395  ancestor = node;
396  while (NULL != (ancestor = ancestor->parent))
397  ancestor->tree_size--;
398 
399  /* update 'size' of node itself */
400  if (node->left_child != NULL)
401  node->tree_size -= (1 + node->left_child->tree_size);
402  if (node->right_child != NULL)
403  node->tree_size -= (1 + node->right_child->tree_size);
404 
405  /* unlink 'node' itself and insert children in its place */
406  if (node->parent == NULL)
407  {
408  if (node->left_child != NULL)
409  {
410  heap->root = node->left_child;
411  node->left_child->parent = NULL;
412  if (node->right_child != NULL)
413  {
414  node->right_child->parent = NULL;
415  insert_node (heap, heap->root, node->right_child);
416  }
417  }
418  else
419  {
420  heap->root = node->right_child;
421  if (node->right_child != NULL)
422  node->right_child->parent = NULL;
423  }
424  }
425  else
426  {
427  if (node->parent->left_child == node)
428  node->parent->left_child = NULL;
429  else
430  node->parent->right_child = NULL;
431  if (node->left_child != NULL)
432  {
433  node->left_child->parent = NULL;
434  node->parent->tree_size -= (1 + node->left_child->tree_size);
435  insert_node (heap, node->parent, node->left_child);
436  }
437  if (node->right_child != NULL)
438  {
439  node->right_child->parent = NULL;
440  node->parent->tree_size -= (1 + node->right_child->tree_size);
441  insert_node (heap, node->parent, node->right_child);
442  }
443  }
444  node->parent = NULL;
445  node->left_child = NULL;
446  node->right_child = NULL;
447  GNUNET_assert (node->tree_size == 0);
448  CHECK (heap->root);
449 }
450 
451 
458 void *
460 {
461  void *ret;
462  struct GNUNET_CONTAINER_Heap *heap;
463 
464  heap = node->heap;
465  CHECK (heap->root);
466  if (heap->walk_pos == node)
468  remove_node (node);
469  heap->size--;
470  ret = node->element;
471  if (heap->walk_pos == node)
472  heap->walk_pos = NULL;
473  GNUNET_free (node);
474 #if EXTRA_CHECKS
475  CHECK (heap->root);
476  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
477  (heap->size == heap->root->tree_size + 1));
478 #endif
479  return ret;
480 }
481 
482 
483 void
486 {
487  struct GNUNET_CONTAINER_Heap *heap = node->heap;
488 
489  remove_node (node);
490  node->cost = new_cost;
491  if (NULL == heap->root)
492  heap->root = node;
493  else
494  insert_node (heap,
495  heap->root,
496  node);
497 }
498 
499 
500 /* end of heap.c */
static void remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Remove the given node 'node' from the tree and update the 'tree_size' fields accordingly.
static void insert_node(struct GNUNET_CONTAINER_Heap *heap, struct GNUNET_CONTAINER_HeapNode *pos, struct GNUNET_CONTAINER_HeapNode *node)
Insert the given node 'node' into the subtree starting at 'pos' (while keeping the tree somewhat bala...
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 CHECK(n)
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
Container classes for GNUnet.
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_WEAK
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
void * GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap)
Remove root of the heap.
GNUNET_CONTAINER_HeapOrder
Heap type, either max or min.
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
GNUNET_CONTAINER_HeapCostType GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode *node)
Get the current cost of the node.
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.
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.
enum GNUNET_GenericReturnValue(* GNUNET_CONTAINER_HeapIterator)(void *cls, struct GNUNET_CONTAINER_HeapNode *node, void *element, GNUNET_CONTAINER_HeapCostType cost)
Iterator for heap.
void * GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
Perform a random walk of the tree.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
unsigned int GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap)
Get the current size of the heap.
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.
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.
void GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap)
Destroys the heap.
@ GNUNET_CONTAINER_HEAP_ORDER_MAX
Heap with the maximum cost at the root.
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.
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
void * element
Our element.
struct GNUNET_CONTAINER_HeapNode * parent
Parent node.
struct GNUNET_CONTAINER_Heap * heap
Heap this node belongs to.
struct GNUNET_CONTAINER_HeapNode * left_child
Left child.
GNUNET_CONTAINER_HeapCostType cost
Cost for this element.
unsigned int tree_size
Number of elements below this node in the heap (excluding this node itself).
struct GNUNET_CONTAINER_HeapNode * right_child
Right child.
Handle to a node in a heap.
struct GNUNET_CONTAINER_HeapNode * root
Root of the heap.
unsigned int size
Number of elements in the heap.
struct GNUNET_CONTAINER_HeapNode * walk_pos
Current position of our random walk.
enum GNUNET_CONTAINER_HeapOrder order
How is the heap sorted?