aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r--src/util/container_heap.c244
1 files changed, 118 insertions, 126 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index a7e79cc7e..c1d478e06 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -94,7 +94,7 @@ struct GNUNET_CONTAINER_Heap
94 * Number of elements in the heap. 94 * Number of elements in the heap.
95 */ 95 */
96 unsigned int size; 96 unsigned int size;
97 97
98 /** 98 /**
99 * How is the heap sorted? 99 * How is the heap sorted?
100 */ 100 */
@@ -108,15 +108,17 @@ struct GNUNET_CONTAINER_Heap
108 * Check if internal invariants hold for the given node. 108 * Check if internal invariants hold for the given node.
109 * 109 *
110 * @param node subtree to check 110 * @param node subtree to check
111 */ 111 */
112static void 112static void
113check (const struct GNUNET_CONTAINER_HeapNode *node) 113check (const struct GNUNET_CONTAINER_HeapNode *node)
114{ 114{
115 if (NULL == node) 115 if (NULL == node)
116 return; 116 return;
117 GNUNET_assert (node->tree_size == 117 GNUNET_assert (node->tree_size ==
118 ( (node->left_child == NULL) ? 0 : 1 + node->left_child->tree_size) + 118 ((node->left_child ==
119 ( (node->right_child == NULL) ? 0 : 1 + node->right_child->tree_size) ); 119 NULL) ? 0 : 1 + node->left_child->tree_size) +
120 ((node->right_child ==
121 NULL) ? 0 : 1 + node->right_child->tree_size));
120 check (node->left_child); 122 check (node->left_child);
121 check (node->right_child); 123 check (node->right_child);
122} 124}
@@ -194,7 +196,8 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
194 * @return cost of the node 196 * @return cost of the node
195 */ 197 */
196GNUNET_CONTAINER_HeapCostType 198GNUNET_CONTAINER_HeapCostType
197GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *node) 199GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
200 *node)
198{ 201{
199 return node->cost; 202 return node->cost;
200} 203}
@@ -210,26 +213,18 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode *nod
210 */ 213 */
211static int 214static int
212node_iterator (const struct GNUNET_CONTAINER_Heap *heap, 215node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
213 struct GNUNET_CONTAINER_HeapNode *node, 216 struct GNUNET_CONTAINER_HeapNode *node,
214 GNUNET_CONTAINER_HeapIterator iterator, 217 GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
215 void *iterator_cls)
216{ 218{
217 if (node == NULL) 219 if (node == NULL)
218 return GNUNET_YES; 220 return GNUNET_YES;
219 if (GNUNET_YES != node_iterator (heap, 221 if (GNUNET_YES != node_iterator (heap,
220 node->left_child, 222 node->left_child, iterator, iterator_cls))
221 iterator,
222 iterator_cls))
223 return GNUNET_NO; 223 return GNUNET_NO;
224 if (GNUNET_YES != node_iterator (heap, 224 if (GNUNET_YES != node_iterator (heap,
225 node->right_child, 225 node->right_child, iterator, iterator_cls))
226 iterator,
227 iterator_cls))
228 return GNUNET_NO; 226 return GNUNET_NO;
229 return iterator (iterator_cls, 227 return iterator (iterator_cls, node, node->element, node->cost);
230 node,
231 node->element,
232 node->cost);
233} 228}
234 229
235 230
@@ -269,13 +264,12 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
269 if (heap->root == NULL) 264 if (heap->root == NULL)
270 return NULL; 265 return NULL;
271 pos = heap->walk_pos; 266 pos = heap->walk_pos;
272 if (pos == NULL) 267 if (pos == NULL)
273 pos = heap->root; 268 pos = heap->root;
274 element = pos->element; 269 element = pos->element;
275 heap->walk_pos 270 heap->walk_pos
276 = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2)) 271 = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2))
277 ? pos->right_child 272 ? pos->right_child : pos->left_child;
278 : pos->left_child;
279 return element; 273 return element;
280} 274}
281 275
@@ -290,51 +284,50 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
290 */ 284 */
291static void 285static void
292insert_node (struct GNUNET_CONTAINER_Heap *heap, 286insert_node (struct GNUNET_CONTAINER_Heap *heap,
293 struct GNUNET_CONTAINER_HeapNode *pos, 287 struct GNUNET_CONTAINER_HeapNode *pos,
294 struct GNUNET_CONTAINER_HeapNode *node) 288 struct GNUNET_CONTAINER_HeapNode *node)
295{ 289{
296 struct GNUNET_CONTAINER_HeapNode *parent; 290 struct GNUNET_CONTAINER_HeapNode *parent;
297 291
298 GNUNET_assert (node->parent == NULL); 292 GNUNET_assert (node->parent == NULL);
299 while ( (heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) 293 while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX)
300 ? (pos->cost >= node->cost) 294 ? (pos->cost >= node->cost) : (pos->cost <= node->cost))
301 : (pos->cost <= node->cost) ) 295 {
296 /* node is descendent of pos */
297 pos->tree_size += (1 + node->tree_size);
298 if (pos->left_child == NULL)
302 { 299 {
303 /* node is descendent of pos */ 300 pos->left_child = node;
304 pos->tree_size += (1 + node->tree_size); 301 node->parent = pos;
305 if (pos->left_child == NULL) 302 return;
306 {
307 pos->left_child = node;
308 node->parent = pos;
309 return;
310 }
311 if (pos->right_child == NULL)
312 {
313 pos->right_child = node;
314 node->parent = pos;
315 return;
316 }
317 /* keep it balanced by descending into smaller subtree */
318 if (pos->left_child->tree_size < pos->right_child->tree_size)
319 pos = pos->left_child;
320 else
321 pos = pos->right_child;
322 } 303 }
304 if (pos->right_child == NULL)
305 {
306 pos->right_child = node;
307 node->parent = pos;
308 return;
309 }
310 /* keep it balanced by descending into smaller subtree */
311 if (pos->left_child->tree_size < pos->right_child->tree_size)
312 pos = pos->left_child;
313 else
314 pos = pos->right_child;
315 }
323 /* make 'node' parent of 'pos' */ 316 /* make 'node' parent of 'pos' */
324 parent = pos->parent; 317 parent = pos->parent;
325 pos->parent = NULL; 318 pos->parent = NULL;
326 node->parent = parent; 319 node->parent = parent;
327 if (NULL == parent) 320 if (NULL == parent)
328 { 321 {
329 heap->root = node; 322 heap->root = node;
330 } 323 }
331 else 324 else
332 { 325 {
333 if (parent->left_child == pos) 326 if (parent->left_child == pos)
334 parent->left_child = node; 327 parent->left_child = node;
335 else 328 else
336 parent->right_child = node; 329 parent->right_child = node;
337 } 330 }
338 /* insert 'pos' below 'node' */ 331 /* insert 'pos' below 'node' */
339 insert_node (heap, node, pos); 332 insert_node (heap, node, pos);
340 CHECK (pos); 333 CHECK (pos);
@@ -351,8 +344,7 @@ insert_node (struct GNUNET_CONTAINER_Heap *heap,
351 */ 344 */
352struct GNUNET_CONTAINER_HeapNode * 345struct GNUNET_CONTAINER_HeapNode *
353GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, 346GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
354 void *element, 347 void *element, GNUNET_CONTAINER_HeapCostType cost)
355 GNUNET_CONTAINER_HeapCostType cost)
356{ 348{
357 struct GNUNET_CONTAINER_HeapNode *node; 349 struct GNUNET_CONTAINER_HeapNode *node;
358 350
@@ -388,28 +380,28 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
388 heap->size--; 380 heap->size--;
389 ret = root->element; 381 ret = root->element;
390 if (root->left_child == NULL) 382 if (root->left_child == NULL)
391 { 383 {
392 heap->root = root->right_child; 384 heap->root = root->right_child;
393 if (root->right_child != NULL) 385 if (root->right_child != NULL)
394 root->right_child->parent = NULL; 386 root->right_child->parent = NULL;
395 } 387 }
396 else if (root->right_child == NULL) 388 else if (root->right_child == NULL)
397 { 389 {
398 heap->root = root->left_child; 390 heap->root = root->left_child;
399 root->left_child->parent = NULL; 391 root->left_child->parent = NULL;
400 } 392 }
401 else 393 else
402 { 394 {
403 root->left_child->parent = NULL; 395 root->left_child->parent = NULL;
404 root->right_child->parent = NULL; 396 root->right_child->parent = NULL;
405 heap->root = root->left_child; 397 heap->root = root->left_child;
406 insert_node (heap, heap->root, root->right_child); 398 insert_node (heap, heap->root, root->right_child);
407 } 399 }
408 GNUNET_free (root); 400 GNUNET_free (root);
409#if DEBUG 401#if DEBUG
410 GNUNET_assert (( (heap->size == 0) && 402 GNUNET_assert (((heap->size == 0) &&
411 (heap->root == NULL) ) || 403 (heap->root == NULL)) ||
412 (heap->size == heap->root->tree_size + 1) ); 404 (heap->size == heap->root->tree_size + 1));
413 CHECK (heap->root); 405 CHECK (heap->root);
414#endif 406#endif
415 return ret; 407 return ret;
@@ -430,7 +422,7 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node)
430 422
431 /* update 'size' of the ancestors */ 423 /* update 'size' of the ancestors */
432 ancestor = node; 424 ancestor = node;
433 while (NULL != (ancestor = ancestor->parent)) 425 while (NULL != (ancestor = ancestor->parent))
434 ancestor->tree_size--; 426 ancestor->tree_size--;
435 427
436 /* update 'size' of node itself */ 428 /* update 'size' of node itself */
@@ -441,43 +433,43 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node)
441 433
442 /* unlink 'node' itself and insert children in its place */ 434 /* unlink 'node' itself and insert children in its place */
443 if (node->parent == NULL) 435 if (node->parent == NULL)
436 {
437 if (node->left_child != NULL)
444 { 438 {
445 if (node->left_child != NULL) 439 heap->root = node->left_child;
446 { 440 node->left_child->parent = NULL;
447 heap->root = node->left_child; 441 if (node->right_child != NULL)
448 node->left_child->parent = NULL; 442 {
449 if (node->right_child != NULL) 443 node->right_child->parent = NULL;
450 { 444 insert_node (heap, heap->root, node->right_child);
451 node->right_child->parent = NULL; 445 }
452 insert_node (heap, heap->root, node->right_child);
453 }
454 }
455 else
456 {
457 heap->root = node->right_child;
458 if (node->right_child != NULL)
459 node->right_child->parent = NULL;
460 }
461 } 446 }
462 else 447 else
463 { 448 {
464 if (node->parent->left_child == node) 449 heap->root = node->right_child;
465 node->parent->left_child = NULL;
466 else
467 node->parent->right_child = NULL;
468 if (node->left_child != NULL)
469 {
470 node->left_child->parent = NULL;
471 node->parent->tree_size -= (1 + node->left_child->tree_size);
472 insert_node (heap, node->parent, node->left_child);
473 }
474 if (node->right_child != NULL) 450 if (node->right_child != NULL)
475 { 451 node->right_child->parent = NULL;
476 node->right_child->parent = NULL; 452 }
477 node->parent->tree_size -= (1 + node->right_child->tree_size); 453 }
478 insert_node (heap, node->parent, node->right_child); 454 else
479 } 455 {
456 if (node->parent->left_child == node)
457 node->parent->left_child = NULL;
458 else
459 node->parent->right_child = NULL;
460 if (node->left_child != NULL)
461 {
462 node->left_child->parent = NULL;
463 node->parent->tree_size -= (1 + node->left_child->tree_size);
464 insert_node (heap, node->parent, node->left_child);
465 }
466 if (node->right_child != NULL)
467 {
468 node->right_child->parent = NULL;
469 node->parent->tree_size -= (1 + node->right_child->tree_size);
470 insert_node (heap, node->parent, node->right_child);
480 } 471 }
472 }
481 node->parent = NULL; 473 node->parent = NULL;
482 node->left_child = NULL; 474 node->left_child = NULL;
483 node->right_child = NULL; 475 node->right_child = NULL;
@@ -498,7 +490,7 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
498 void *ret; 490 void *ret;
499 struct GNUNET_CONTAINER_Heap *heap; 491 struct GNUNET_CONTAINER_Heap *heap;
500 492
501 heap = node->heap; 493 heap = node->heap;
502 CHECK (heap->root); 494 CHECK (heap->root);
503 if (heap->walk_pos == node) 495 if (heap->walk_pos == node)
504 (void) GNUNET_CONTAINER_heap_walk_get_next (heap); 496 (void) GNUNET_CONTAINER_heap_walk_get_next (heap);
@@ -510,9 +502,9 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
510 GNUNET_free (node); 502 GNUNET_free (node);
511#if DEBUG 503#if DEBUG
512 CHECK (heap->root); 504 CHECK (heap->root);
513 GNUNET_assert (( (heap->size == 0) && 505 GNUNET_assert (((heap->size == 0) &&
514 (heap->root == NULL) ) || 506 (heap->root == NULL)) ||
515 (heap->size == heap->root->tree_size + 1) ); 507 (heap->size == heap->root->tree_size + 1));
516#endif 508#endif
517 return ret; 509 return ret;
518} 510}
@@ -527,21 +519,21 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
527 */ 519 */
528void 520void
529GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, 521GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
530 struct GNUNET_CONTAINER_HeapNode *node, 522 struct GNUNET_CONTAINER_HeapNode *node,
531 GNUNET_CONTAINER_HeapCostType new_cost) 523 GNUNET_CONTAINER_HeapCostType new_cost)
532{ 524{
533#if DEBUG 525#if DEBUG
534 GNUNET_assert ( ( (heap->size == 0) && 526 GNUNET_assert (((heap->size == 0) &&
535 (heap->root == NULL) ) || 527 (heap->root == NULL)) ||
536 (heap->size == heap->root->tree_size + 1) ); 528 (heap->size == heap->root->tree_size + 1));
537 CHECK (heap->root); 529 CHECK (heap->root);
538#endif 530#endif
539 remove_node (node); 531 remove_node (node);
540#if DEBUG 532#if DEBUG
541 CHECK (heap->root); 533 CHECK (heap->root);
542 GNUNET_assert ( ( (heap->size == 1) && 534 GNUNET_assert (((heap->size == 1) &&
543 (heap->root == NULL) ) || 535 (heap->root == NULL)) ||
544 (heap->size == heap->root->tree_size + 2) ); 536 (heap->size == heap->root->tree_size + 2));
545#endif 537#endif
546 node->cost = new_cost; 538 node->cost = new_cost;
547 if (heap->root == NULL) 539 if (heap->root == NULL)
@@ -550,9 +542,9 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
550 insert_node (heap, heap->root, node); 542 insert_node (heap, heap->root, node);
551#if DEBUG 543#if DEBUG
552 CHECK (heap->root); 544 CHECK (heap->root);
553 GNUNET_assert ( ( (heap->size == 0) && 545 GNUNET_assert (((heap->size == 0) &&
554 (heap->root == NULL) ) || 546 (heap->root == NULL)) ||
555 (heap->size == heap->root->tree_size + 1) ); 547 (heap->size == heap->root->tree_size + 1));
556#endif 548#endif
557} 549}
558 550
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-27 00:09:37 +0000