GNUnet  0.19.3
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 
29 #include "platform.h"
30 #include "gnunet_util_lib.h"
31 
32 #define LOG(kind, ...) GNUNET_log_from (kind, "util-container-heap", \
33  __VA_ARGS__)
34 
35 #define EXTRA_CHECKS 0
36 
41 {
46 
51 
56 
61 
65  void *element;
66 
71 
76  unsigned int tree_size;
77 };
78 
83 {
88 
93 
97  unsigned int size;
98 
103 };
104 
105 
106 #if EXTRA_CHECKS
112 static void
113 check (const struct GNUNET_CONTAINER_HeapNode *node)
114 {
115  if (NULL == node)
116  return;
117  GNUNET_assert (node->tree_size ==
118  ((node->left_child ==
119  NULL) ? 0 : 1 + node->left_child->tree_size)
120  + ((node->right_child ==
121  NULL) ? 0 : 1 + node->right_child->tree_size));
122  check (node->left_child);
123  check (node->right_child);
124 }
125 
126 
127 #define CHECK(n) check (n)
128 #else
129 #define CHECK(n) do {} while (0)
130 #endif
131 
132 
133 struct GNUNET_CONTAINER_Heap *
135 {
136  struct GNUNET_CONTAINER_Heap *heap;
137 
138  heap = GNUNET_new (struct GNUNET_CONTAINER_Heap);
139  heap->order = order;
140  return heap;
141 }
142 
143 
144 void
146 {
147  GNUNET_break (heap->size == 0);
148  GNUNET_free (heap);
149 }
150 
151 
152 void *
154 {
155  if (heap->root == NULL)
156  return NULL;
157  return heap->root->element;
158 }
159 
160 
170 int
172  void **element,
174 {
175  if (NULL == heap->root)
176  return GNUNET_NO;
177  if (NULL != element)
178  *element = heap->root->element;
179  if (NULL != cost)
180  *cost = heap->root->cost;
181  return GNUNET_YES;
182 }
183 
184 
185 unsigned int
187 {
188  return heap->size;
189 }
190 
191 
194  *node)
195 {
196  return node->cost;
197 }
198 
199 
209 static int
211  struct GNUNET_CONTAINER_HeapNode *node,
212  GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
213 {
214  if (node == NULL)
215  return GNUNET_YES;
216  if (GNUNET_YES !=
217  node_iterator (heap, node->left_child, iterator, iterator_cls))
218  return GNUNET_NO;
219  if (GNUNET_YES !=
220  node_iterator (heap, node->right_child, iterator, iterator_cls))
221  return GNUNET_NO;
222  return iterator (iterator_cls, node, node->element, node->cost);
223 }
224 
225 
226 void
229  void *iterator_cls)
230 {
231  (void) node_iterator (heap, heap->root, iterator, iterator_cls);
232 }
233 
234 
235 void *
237 {
238  struct GNUNET_CONTAINER_HeapNode *pos;
239  void *element;
240 
241  if (heap->root == NULL)
242  return NULL;
243  pos = heap->walk_pos;
244  if (pos == NULL)
245  pos = heap->root;
246  element = pos->element;
247  heap->walk_pos =
248  (0 ==
250  2)) ? pos->right_child : pos->left_child;
251  return element;
252 }
253 
254 
263 static void
265  struct GNUNET_CONTAINER_HeapNode *pos,
266  struct GNUNET_CONTAINER_HeapNode *node)
267 {
269 
270  GNUNET_assert (node->parent == NULL);
271  while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
272  node->cost)
273  : (pos->cost <= node->cost))
274  {
275  /* node is descendent of pos */
276  pos->tree_size += (1 + node->tree_size);
277  if (pos->left_child == NULL)
278  {
279  pos->left_child = node;
280  node->parent = pos;
281  return;
282  }
283  if (pos->right_child == NULL)
284  {
285  pos->right_child = node;
286  node->parent = pos;
287  return;
288  }
289  /* keep it balanced by descending into smaller subtree */
290  if (pos->left_child->tree_size < pos->right_child->tree_size)
291  pos = pos->left_child;
292  else
293  pos = pos->right_child;
294  }
295  /* make 'node' parent of 'pos' */
296  parent = pos->parent;
297  pos->parent = NULL;
298  node->parent = parent;
299  if (NULL == parent)
300  {
301  heap->root = node;
302  }
303  else
304  {
305  if (parent->left_child == pos)
306  parent->left_child = node;
307  else
308  parent->right_child = node;
309  }
310  /* insert 'pos' below 'node' */
311  insert_node (heap, node, pos);
312  CHECK (pos);
313 }
314 
315 
319 {
320  struct GNUNET_CONTAINER_HeapNode *node;
321 
322  node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode);
323  node->heap = heap;
324  node->element = element;
325  node->cost = cost;
326  heap->size++;
327  if (NULL == heap->root)
328  heap->root = node;
329  else
330  insert_node (heap, heap->root, node);
332  CHECK (heap->root);
333  return node;
334 }
335 
336 
343 void *
345 {
346  void *ret;
347  struct GNUNET_CONTAINER_HeapNode *root;
348 
349  if (NULL == (root = heap->root))
350  return NULL;
351  heap->size--;
352  ret = root->element;
353  if (root->left_child == NULL)
354  {
355  heap->root = root->right_child;
356  if (root->right_child != NULL)
357  root->right_child->parent = NULL;
358  }
359  else if (root->right_child == NULL)
360  {
361  heap->root = root->left_child;
362  root->left_child->parent = NULL;
363  }
364  else
365  {
366  root->left_child->parent = NULL;
367  root->right_child->parent = NULL;
368  heap->root = root->left_child;
369  insert_node (heap, heap->root, root->right_child);
370  }
371  if (heap->walk_pos == root)
372  heap->walk_pos = heap->root;
373  GNUNET_free (root);
374 #if EXTRA_CHECKS
375  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
376  (heap->size == heap->root->tree_size + 1));
377  CHECK (heap->root);
378 #endif
379  return ret;
380 }
381 
382 
389 static void
391 {
392  struct GNUNET_CONTAINER_HeapNode *ancestor;
393  struct GNUNET_CONTAINER_Heap *heap = node->heap;
394 
395  /* update 'size' of the ancestors */
396  ancestor = node;
397  while (NULL != (ancestor = ancestor->parent))
398  ancestor->tree_size--;
399 
400  /* update 'size' of node itself */
401  if (node->left_child != NULL)
402  node->tree_size -= (1 + node->left_child->tree_size);
403  if (node->right_child != NULL)
404  node->tree_size -= (1 + node->right_child->tree_size);
405 
406  /* unlink 'node' itself and insert children in its place */
407  if (node->parent == NULL)
408  {
409  if (node->left_child != NULL)
410  {
411  heap->root = node->left_child;
412  node->left_child->parent = NULL;
413  if (node->right_child != NULL)
414  {
415  node->right_child->parent = NULL;
416  insert_node (heap, heap->root, node->right_child);
417  }
418  }
419  else
420  {
421  heap->root = node->right_child;
422  if (node->right_child != NULL)
423  node->right_child->parent = NULL;
424  }
425  }
426  else
427  {
428  if (node->parent->left_child == node)
429  node->parent->left_child = NULL;
430  else
431  node->parent->right_child = NULL;
432  if (node->left_child != NULL)
433  {
434  node->left_child->parent = NULL;
435  node->parent->tree_size -= (1 + node->left_child->tree_size);
436  insert_node (heap, node->parent, node->left_child);
437  }
438  if (node->right_child != NULL)
439  {
440  node->right_child->parent = NULL;
441  node->parent->tree_size -= (1 + node->right_child->tree_size);
442  insert_node (heap, node->parent, node->right_child);
443  }
444  }
445  node->parent = NULL;
446  node->left_child = NULL;
447  node->right_child = NULL;
448  GNUNET_assert (node->tree_size == 0);
449  CHECK (heap->root);
450 }
451 
452 
459 void *
461 {
462  void *ret;
463  struct GNUNET_CONTAINER_Heap *heap;
464 
465  heap = node->heap;
466  CHECK (heap->root);
467  if (heap->walk_pos == node)
469  remove_node (node);
470  heap->size--;
471  ret = node->element;
472  if (heap->walk_pos == node)
473  heap->walk_pos = NULL;
474  GNUNET_free (node);
475 #if EXTRA_CHECKS
476  CHECK (heap->root);
477  GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
478  (heap->size == heap->root->tree_size + 1));
479 #endif
480  return ret;
481 }
482 
483 
484 void
487 {
488  struct GNUNET_CONTAINER_Heap *heap = node->heap;
489 
490  remove_node (node);
491  node->cost = new_cost;
492  if (NULL == heap->root)
493  heap->root = node;
494  else
495  insert_node (heap,
496  heap->root,
497  node);
498 }
499 
500 
501 /* 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
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
#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?