GNUnet 0.21.1
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
112static void
113check (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
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
144void
146{
147 GNUNET_break (heap->size == 0);
148 GNUNET_free (heap);
149}
150
151
152void *
154{
155 if (heap->root == NULL)
156 return NULL;
157 return heap->root->element;
158}
159
160
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
185unsigned int
187{
188 return heap->size;
189}
190
191
194 *node)
195{
196 return node->cost;
197}
198
199
209static 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
226void
229 void *iterator_cls)
230{
231 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
232}
233
234
235void *
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
263static 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
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
343void *
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;
370 }
371 if (heap->walk_pos == 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
389static 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
459void *
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
484void
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
Final status code.
Definition: gnunet-arm.c:94
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).
void * GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node)
Removes a node from the heap.
void * GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap)
Get element stored at the root of heap.
GNUNET_CONTAINER_HeapOrder
Heap type, either max or min.
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_remove_root(struct GNUNET_CONTAINER_Heap *heap)
Remove root of the heap.
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.
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.
void * GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap)
Perform a random walk of the tree.
@ GNUNET_CONTAINER_HEAP_ORDER_MAX
Heap with the maximum cost at the root.
enum GNUNET_GenericReturnValue 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_GenericReturnValue
Named constants for return values.
@ 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?