diff options
author | Christian Grothoff <christian@grothoff.org> | 2011-10-11 09:43:04 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2011-10-11 09:43:04 +0000 |
commit | d9d94d0e53d26af75ec8241383d166544ebd79f3 (patch) | |
tree | 9080b73624389403a198257fe0547bb4634e64d2 /src/util/container_heap.c | |
parent | 2d792ee2e9cc0c993b8907e2c8edb0c2b8465343 (diff) | |
download | gnunet-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.c | 202 |
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 | */ |
198 | GNUNET_CONTAINER_HeapCostType | 199 | GNUNET_CONTAINER_HeapCostType |
199 | GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode | 200 | GNUNET_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 | */ |
214 | static int | 215 | static int |
215 | node_iterator (const struct GNUNET_CONTAINER_Heap *heap, | 216 | node_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 | */ |
238 | void | 239 | void |
239 | GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, | 240 | GNUNET_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 | */ |
286 | static void | 287 | static void |
287 | insert_node (struct GNUNET_CONTAINER_Heap *heap, | 288 | insert_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 | */ |
347 | struct GNUNET_CONTAINER_HeapNode * | 348 | struct GNUNET_CONTAINER_HeapNode * |
348 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, | 349 | GNUNET_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 | */ |
520 | void | 522 | void |
521 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, | 523 | GNUNET_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 | ||