aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_heap.c
diff options
context:
space:
mode:
authorChristian Grothoff <christian@grothoff.org>2011-10-11 09:43:04 +0000
committerChristian Grothoff <christian@grothoff.org>2011-10-11 09:43:04 +0000
commitd9d94d0e53d26af75ec8241383d166544ebd79f3 (patch)
tree9080b73624389403a198257fe0547bb4634e64d2 /src/util/container_heap.c
parent2d792ee2e9cc0c993b8907e2c8edb0c2b8465343 (diff)
downloadgnunet-d9d94d0e53d26af75ec8241383d166544ebd79f3.tar.gz
gnunet-d9d94d0e53d26af75ec8241383d166544ebd79f3.zip
converting to GNUNET_LOG_from*
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r--src/util/container_heap.c202
1 files changed, 102 insertions, 100 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c
index cd4d7909a..051b85a25 100644
--- a/src/util/container_heap.c
+++ b/src/util/container_heap.c
@@ -28,6 +28,7 @@
28#include "platform.h" 28#include "platform.h"
29#include "gnunet_util_lib.h" 29#include "gnunet_util_lib.h"
30 30
31#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
31 32
32#define DEBUG 0 33#define DEBUG 0
33 34
@@ -115,10 +116,10 @@ check (const struct GNUNET_CONTAINER_HeapNode *node)
115 if (NULL == node) 116 if (NULL == node)
116 return; 117 return;
117 GNUNET_assert (node->tree_size == 118 GNUNET_assert (node->tree_size ==
118 ((node->left_child == 119 ((node->left_child ==
119 NULL) ? 0 : 1 + node->left_child->tree_size) + 120 NULL) ? 0 : 1 + node->left_child->tree_size) +
120 ((node->right_child == 121 ((node->right_child ==
121 NULL) ? 0 : 1 + node->right_child->tree_size)); 122 NULL) ? 0 : 1 + node->right_child->tree_size));
122 check (node->left_child); 123 check (node->left_child);
123 check (node->right_child); 124 check (node->right_child);
124} 125}
@@ -197,7 +198,7 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap)
197 */ 198 */
198GNUNET_CONTAINER_HeapCostType 199GNUNET_CONTAINER_HeapCostType
199GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode 200GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
200 *node) 201 * node)
201{ 202{
202 return node->cost; 203 return node->cost;
203} 204}
@@ -213,8 +214,8 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode
213 */ 214 */
214static int 215static int
215node_iterator (const struct GNUNET_CONTAINER_Heap *heap, 216node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
216 struct GNUNET_CONTAINER_HeapNode *node, 217 struct GNUNET_CONTAINER_HeapNode *node,
217 GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) 218 GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls)
218{ 219{
219 if (node == NULL) 220 if (node == NULL)
220 return GNUNET_YES; 221 return GNUNET_YES;
@@ -237,8 +238,8 @@ node_iterator (const struct GNUNET_CONTAINER_Heap *heap,
237 */ 238 */
238void 239void
239GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, 240GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap,
240 GNUNET_CONTAINER_HeapIterator iterator, 241 GNUNET_CONTAINER_HeapIterator iterator,
241 void *iterator_cls) 242 void *iterator_cls)
242{ 243{
243 (void) node_iterator (heap, heap->root, iterator, iterator_cls); 244 (void) node_iterator (heap, heap->root, iterator, iterator_cls);
244} 245}
@@ -268,9 +269,9 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
268 pos = heap->root; 269 pos = heap->root;
269 element = pos->element; 270 element = pos->element;
270 heap->walk_pos = 271 heap->walk_pos =
271 (0 == 272 (0 ==
272 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 273 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
273 2)) ? pos->right_child : pos->left_child; 274 2)) ? pos->right_child : pos->left_child;
274 return element; 275 return element;
275} 276}
276 277
@@ -285,51 +286,51 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap)
285 */ 286 */
286static void 287static void
287insert_node (struct GNUNET_CONTAINER_Heap *heap, 288insert_node (struct GNUNET_CONTAINER_Heap *heap,
288 struct GNUNET_CONTAINER_HeapNode *pos, 289 struct GNUNET_CONTAINER_HeapNode *pos,
289 struct GNUNET_CONTAINER_HeapNode *node) 290 struct GNUNET_CONTAINER_HeapNode *node)
290{ 291{
291 struct GNUNET_CONTAINER_HeapNode *parent; 292 struct GNUNET_CONTAINER_HeapNode *parent;
292 293
293 GNUNET_assert (node->parent == NULL); 294 GNUNET_assert (node->parent == NULL);
294 while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= 295 while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >=
295 node->cost) 296 node->cost)
296 : (pos->cost <= node->cost)) 297 : (pos->cost <= node->cost))
297 {
298 /* node is descendent of pos */
299 pos->tree_size += (1 + node->tree_size);
300 if (pos->left_child == NULL)
301 { 298 {
302 pos->left_child = node; 299 /* node is descendent of pos */
303 node->parent = pos; 300 pos->tree_size += (1 + node->tree_size);
304 return; 301 if (pos->left_child == NULL)
302 {
303 pos->left_child = node;
304 node->parent = pos;
305 return;
306 }
307 if (pos->right_child == NULL)
308 {
309 pos->right_child = node;
310 node->parent = pos;
311 return;
312 }
313 /* keep it balanced by descending into smaller subtree */
314 if (pos->left_child->tree_size < pos->right_child->tree_size)
315 pos = pos->left_child;
316 else
317 pos = pos->right_child;
305 } 318 }
306 if (pos->right_child == NULL)
307 {
308 pos->right_child = node;
309 node->parent = pos;
310 return;
311 }
312 /* keep it balanced by descending into smaller subtree */
313 if (pos->left_child->tree_size < pos->right_child->tree_size)
314 pos = pos->left_child;
315 else
316 pos = pos->right_child;
317 }
318 /* make 'node' parent of 'pos' */ 319 /* make 'node' parent of 'pos' */
319 parent = pos->parent; 320 parent = pos->parent;
320 pos->parent = NULL; 321 pos->parent = NULL;
321 node->parent = parent; 322 node->parent = parent;
322 if (NULL == parent) 323 if (NULL == parent)
323 { 324 {
324 heap->root = node; 325 heap->root = node;
325 } 326 }
326 else 327 else
327 { 328 {
328 if (parent->left_child == pos) 329 if (parent->left_child == pos)
329 parent->left_child = node; 330 parent->left_child = node;
330 else 331 else
331 parent->right_child = node; 332 parent->right_child = node;
332 } 333 }
333 /* insert 'pos' below 'node' */ 334 /* insert 'pos' below 'node' */
334 insert_node (heap, node, pos); 335 insert_node (heap, node, pos);
335 CHECK (pos); 336 CHECK (pos);
@@ -345,8 +346,9 @@ insert_node (struct GNUNET_CONTAINER_Heap *heap,
345 * @return node for the new element 346 * @return node for the new element
346 */ 347 */
347struct GNUNET_CONTAINER_HeapNode * 348struct GNUNET_CONTAINER_HeapNode *
348GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, 349GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap,
349 GNUNET_CONTAINER_HeapCostType cost) 350 void *element,
351 GNUNET_CONTAINER_HeapCostType cost)
350{ 352{
351 struct GNUNET_CONTAINER_HeapNode *node; 353 struct GNUNET_CONTAINER_HeapNode *node;
352 354
@@ -382,27 +384,27 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap)
382 heap->size--; 384 heap->size--;
383 ret = root->element; 385 ret = root->element;
384 if (root->left_child == NULL) 386 if (root->left_child == NULL)
385 { 387 {
386 heap->root = root->right_child; 388 heap->root = root->right_child;
387 if (root->right_child != NULL) 389 if (root->right_child != NULL)
388 root->right_child->parent = NULL; 390 root->right_child->parent = NULL;
389 } 391 }
390 else if (root->right_child == NULL) 392 else if (root->right_child == NULL)
391 { 393 {
392 heap->root = root->left_child; 394 heap->root = root->left_child;
393 root->left_child->parent = NULL; 395 root->left_child->parent = NULL;
394 } 396 }
395 else 397 else
396 { 398 {
397 root->left_child->parent = NULL; 399 root->left_child->parent = NULL;
398 root->right_child->parent = NULL; 400 root->right_child->parent = NULL;
399 heap->root = root->left_child; 401 heap->root = root->left_child;
400 insert_node (heap, heap->root, root->right_child); 402 insert_node (heap, heap->root, root->right_child);
401 } 403 }
402 GNUNET_free (root); 404 GNUNET_free (root);
403#if DEBUG 405#if DEBUG
404 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || 406 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
405 (heap->size == heap->root->tree_size + 1)); 407 (heap->size == heap->root->tree_size + 1));
406 CHECK (heap->root); 408 CHECK (heap->root);
407#endif 409#endif
408 return ret; 410 return ret;
@@ -434,43 +436,43 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node)
434 436
435 /* unlink 'node' itself and insert children in its place */ 437 /* unlink 'node' itself and insert children in its place */
436 if (node->parent == NULL) 438 if (node->parent == NULL)
437 {
438 if (node->left_child != NULL)
439 { 439 {
440 heap->root = node->left_child; 440 if (node->left_child != NULL)
441 node->left_child->parent = NULL; 441 {
442 if (node->right_child != NULL) 442 heap->root = node->left_child;
443 { 443 node->left_child->parent = NULL;
444 node->right_child->parent = NULL; 444 if (node->right_child != NULL)
445 insert_node (heap, heap->root, node->right_child); 445 {
446 } 446 node->right_child->parent = NULL;
447 insert_node (heap, heap->root, node->right_child);
448 }
449 }
450 else
451 {
452 heap->root = node->right_child;
453 if (node->right_child != NULL)
454 node->right_child->parent = NULL;
455 }
447 } 456 }
448 else
449 {
450 heap->root = node->right_child;
451 if (node->right_child != NULL)
452 node->right_child->parent = NULL;
453 }
454 }
455 else 457 else
456 {
457 if (node->parent->left_child == node)
458 node->parent->left_child = NULL;
459 else
460 node->parent->right_child = NULL;
461 if (node->left_child != NULL)
462 { 458 {
463 node->left_child->parent = NULL; 459 if (node->parent->left_child == node)
464 node->parent->tree_size -= (1 + node->left_child->tree_size); 460 node->parent->left_child = NULL;
465 insert_node (heap, node->parent, node->left_child); 461 else
466 } 462 node->parent->right_child = NULL;
467 if (node->right_child != NULL) 463 if (node->left_child != NULL)
468 { 464 {
469 node->right_child->parent = NULL; 465 node->left_child->parent = NULL;
470 node->parent->tree_size -= (1 + node->right_child->tree_size); 466 node->parent->tree_size -= (1 + node->left_child->tree_size);
471 insert_node (heap, node->parent, node->right_child); 467 insert_node (heap, node->parent, node->left_child);
468 }
469 if (node->right_child != NULL)
470 {
471 node->right_child->parent = NULL;
472 node->parent->tree_size -= (1 + node->right_child->tree_size);
473 insert_node (heap, node->parent, node->right_child);
474 }
472 } 475 }
473 }
474 node->parent = NULL; 476 node->parent = NULL;
475 node->left_child = NULL; 477 node->left_child = NULL;
476 node->right_child = NULL; 478 node->right_child = NULL;
@@ -504,7 +506,7 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
504#if DEBUG 506#if DEBUG
505 CHECK (heap->root); 507 CHECK (heap->root);
506 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || 508 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
507 (heap->size == heap->root->tree_size + 1)); 509 (heap->size == heap->root->tree_size + 1));
508#endif 510#endif
509 return ret; 511 return ret;
510} 512}
@@ -519,19 +521,19 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node)
519 */ 521 */
520void 522void
521GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, 523GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
522 struct GNUNET_CONTAINER_HeapNode *node, 524 struct GNUNET_CONTAINER_HeapNode *node,
523 GNUNET_CONTAINER_HeapCostType new_cost) 525 GNUNET_CONTAINER_HeapCostType new_cost)
524{ 526{
525#if DEBUG 527#if DEBUG
526 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || 528 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
527 (heap->size == heap->root->tree_size + 1)); 529 (heap->size == heap->root->tree_size + 1));
528 CHECK (heap->root); 530 CHECK (heap->root);
529#endif 531#endif
530 remove_node (node); 532 remove_node (node);
531#if DEBUG 533#if DEBUG
532 CHECK (heap->root); 534 CHECK (heap->root);
533 GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) || 535 GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) ||
534 (heap->size == heap->root->tree_size + 2)); 536 (heap->size == heap->root->tree_size + 2));
535#endif 537#endif
536 node->cost = new_cost; 538 node->cost = new_cost;
537 if (heap->root == NULL) 539 if (heap->root == NULL)
@@ -541,7 +543,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap,
541#if DEBUG 543#if DEBUG
542 CHECK (heap->root); 544 CHECK (heap->root);
543 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || 545 GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) ||
544 (heap->size == heap->root->tree_size + 1)); 546 (heap->size == heap->root->tree_size + 1));
545#endif 547#endif
546} 548}
547 549