diff options
author | Christian Grothoff <christian@grothoff.org> | 2011-11-04 14:00:32 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2011-11-04 14:00:32 +0000 |
commit | 83b19539f4d322b43683f5838b72e9ec2c8e6073 (patch) | |
tree | d0ab9329fcbefe360d9d14e2ace21a6b3396dfe9 /src/util/container_heap.c | |
parent | 28a2eb43281a1f08a67954f07beb9af3a9bc9a35 (diff) | |
download | gnunet-83b19539f4d322b43683f5838b72e9ec2c8e6073.tar.gz gnunet-83b19539f4d322b43683f5838b72e9ec2c8e6073.zip |
curly wars / auto-indentation
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r-- | src/util/container_heap.c | 201 |
1 files changed, 100 insertions, 101 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index 051b85a25..c34e220ce 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -116,10 +116,10 @@ check (const struct GNUNET_CONTAINER_HeapNode *node) | |||
116 | if (NULL == node) | 116 | if (NULL == node) |
117 | return; | 117 | return; |
118 | GNUNET_assert (node->tree_size == | 118 | GNUNET_assert (node->tree_size == |
119 | ((node->left_child == | 119 | ((node->left_child == |
120 | NULL) ? 0 : 1 + node->left_child->tree_size) + | 120 | NULL) ? 0 : 1 + node->left_child->tree_size) + |
121 | ((node->right_child == | 121 | ((node->right_child == |
122 | NULL) ? 0 : 1 + node->right_child->tree_size)); | 122 | NULL) ? 0 : 1 + node->right_child->tree_size)); |
123 | check (node->left_child); | 123 | check (node->left_child); |
124 | check (node->right_child); | 124 | check (node->right_child); |
125 | } | 125 | } |
@@ -198,7 +198,7 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap) | |||
198 | */ | 198 | */ |
199 | GNUNET_CONTAINER_HeapCostType | 199 | GNUNET_CONTAINER_HeapCostType |
200 | GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode | 200 | GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode |
201 | * node) | 201 | *node) |
202 | { | 202 | { |
203 | return node->cost; | 203 | return node->cost; |
204 | } | 204 | } |
@@ -214,8 +214,8 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode | |||
214 | */ | 214 | */ |
215 | static int | 215 | static int |
216 | node_iterator (const struct GNUNET_CONTAINER_Heap *heap, | 216 | node_iterator (const struct GNUNET_CONTAINER_Heap *heap, |
217 | struct GNUNET_CONTAINER_HeapNode *node, | 217 | struct GNUNET_CONTAINER_HeapNode *node, |
218 | GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) | 218 | GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) |
219 | { | 219 | { |
220 | if (node == NULL) | 220 | if (node == NULL) |
221 | return GNUNET_YES; | 221 | return GNUNET_YES; |
@@ -238,8 +238,8 @@ node_iterator (const struct GNUNET_CONTAINER_Heap *heap, | |||
238 | */ | 238 | */ |
239 | void | 239 | void |
240 | GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, | 240 | GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, |
241 | GNUNET_CONTAINER_HeapIterator iterator, | 241 | GNUNET_CONTAINER_HeapIterator iterator, |
242 | void *iterator_cls) | 242 | void *iterator_cls) |
243 | { | 243 | { |
244 | (void) node_iterator (heap, heap->root, iterator, iterator_cls); | 244 | (void) node_iterator (heap, heap->root, iterator, iterator_cls); |
245 | } | 245 | } |
@@ -269,9 +269,9 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) | |||
269 | pos = heap->root; | 269 | pos = heap->root; |
270 | element = pos->element; | 270 | element = pos->element; |
271 | heap->walk_pos = | 271 | heap->walk_pos = |
272 | (0 == | 272 | (0 == |
273 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, | 273 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, |
274 | 2)) ? pos->right_child : pos->left_child; | 274 | 2)) ? pos->right_child : pos->left_child; |
275 | return element; | 275 | return element; |
276 | } | 276 | } |
277 | 277 | ||
@@ -286,51 +286,51 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) | |||
286 | */ | 286 | */ |
287 | static void | 287 | static void |
288 | insert_node (struct GNUNET_CONTAINER_Heap *heap, | 288 | insert_node (struct GNUNET_CONTAINER_Heap *heap, |
289 | struct GNUNET_CONTAINER_HeapNode *pos, | 289 | struct GNUNET_CONTAINER_HeapNode *pos, |
290 | struct GNUNET_CONTAINER_HeapNode *node) | 290 | struct GNUNET_CONTAINER_HeapNode *node) |
291 | { | 291 | { |
292 | struct GNUNET_CONTAINER_HeapNode *parent; | 292 | struct GNUNET_CONTAINER_HeapNode *parent; |
293 | 293 | ||
294 | GNUNET_assert (node->parent == NULL); | 294 | GNUNET_assert (node->parent == NULL); |
295 | while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= | 295 | while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= |
296 | node->cost) | 296 | node->cost) |
297 | : (pos->cost <= node->cost)) | 297 | : (pos->cost <= node->cost)) |
298 | { | ||
299 | /* node is descendent of pos */ | ||
300 | pos->tree_size += (1 + node->tree_size); | ||
301 | if (pos->left_child == NULL) | ||
298 | { | 302 | { |
299 | /* node is descendent of pos */ | 303 | pos->left_child = node; |
300 | pos->tree_size += (1 + node->tree_size); | 304 | node->parent = pos; |
301 | if (pos->left_child == NULL) | 305 | return; |
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; | ||
318 | } | 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; | ||
318 | } | ||
319 | /* make 'node' parent of 'pos' */ | 319 | /* make 'node' parent of 'pos' */ |
320 | parent = pos->parent; | 320 | parent = pos->parent; |
321 | pos->parent = NULL; | 321 | pos->parent = NULL; |
322 | node->parent = parent; | 322 | node->parent = parent; |
323 | if (NULL == parent) | 323 | if (NULL == parent) |
324 | { | 324 | { |
325 | heap->root = node; | 325 | heap->root = node; |
326 | } | 326 | } |
327 | else | 327 | else |
328 | { | 328 | { |
329 | if (parent->left_child == pos) | 329 | if (parent->left_child == pos) |
330 | parent->left_child = node; | 330 | parent->left_child = node; |
331 | else | 331 | else |
332 | parent->right_child = node; | 332 | parent->right_child = node; |
333 | } | 333 | } |
334 | /* insert 'pos' below 'node' */ | 334 | /* insert 'pos' below 'node' */ |
335 | insert_node (heap, node, pos); | 335 | insert_node (heap, node, pos); |
336 | CHECK (pos); | 336 | CHECK (pos); |
@@ -346,9 +346,8 @@ insert_node (struct GNUNET_CONTAINER_Heap *heap, | |||
346 | * @return node for the new element | 346 | * @return node for the new element |
347 | */ | 347 | */ |
348 | struct GNUNET_CONTAINER_HeapNode * | 348 | struct GNUNET_CONTAINER_HeapNode * |
349 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, | 349 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, |
350 | void *element, | 350 | GNUNET_CONTAINER_HeapCostType cost) |
351 | GNUNET_CONTAINER_HeapCostType cost) | ||
352 | { | 351 | { |
353 | struct GNUNET_CONTAINER_HeapNode *node; | 352 | struct GNUNET_CONTAINER_HeapNode *node; |
354 | 353 | ||
@@ -384,27 +383,27 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) | |||
384 | heap->size--; | 383 | heap->size--; |
385 | ret = root->element; | 384 | ret = root->element; |
386 | if (root->left_child == NULL) | 385 | if (root->left_child == NULL) |
387 | { | 386 | { |
388 | heap->root = root->right_child; | 387 | heap->root = root->right_child; |
389 | if (root->right_child != NULL) | 388 | if (root->right_child != NULL) |
390 | root->right_child->parent = NULL; | 389 | root->right_child->parent = NULL; |
391 | } | 390 | } |
392 | else if (root->right_child == NULL) | 391 | else if (root->right_child == NULL) |
393 | { | 392 | { |
394 | heap->root = root->left_child; | 393 | heap->root = root->left_child; |
395 | root->left_child->parent = NULL; | 394 | root->left_child->parent = NULL; |
396 | } | 395 | } |
397 | else | 396 | else |
398 | { | 397 | { |
399 | root->left_child->parent = NULL; | 398 | root->left_child->parent = NULL; |
400 | root->right_child->parent = NULL; | 399 | root->right_child->parent = NULL; |
401 | heap->root = root->left_child; | 400 | heap->root = root->left_child; |
402 | insert_node (heap, heap->root, root->right_child); | 401 | insert_node (heap, heap->root, root->right_child); |
403 | } | 402 | } |
404 | GNUNET_free (root); | 403 | GNUNET_free (root); |
405 | #if DEBUG | 404 | #if DEBUG |
406 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || | 405 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || |
407 | (heap->size == heap->root->tree_size + 1)); | 406 | (heap->size == heap->root->tree_size + 1)); |
408 | CHECK (heap->root); | 407 | CHECK (heap->root); |
409 | #endif | 408 | #endif |
410 | return ret; | 409 | return ret; |
@@ -436,43 +435,43 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node) | |||
436 | 435 | ||
437 | /* unlink 'node' itself and insert children in its place */ | 436 | /* unlink 'node' itself and insert children in its place */ |
438 | if (node->parent == NULL) | 437 | if (node->parent == NULL) |
438 | { | ||
439 | if (node->left_child != NULL) | ||
439 | { | 440 | { |
440 | if (node->left_child != NULL) | 441 | heap->root = node->left_child; |
441 | { | 442 | node->left_child->parent = NULL; |
442 | heap->root = node->left_child; | 443 | if (node->right_child != NULL) |
443 | node->left_child->parent = NULL; | 444 | { |
444 | if (node->right_child != NULL) | 445 | node->right_child->parent = NULL; |
445 | { | 446 | insert_node (heap, heap->root, node->right_child); |
446 | node->right_child->parent = NULL; | 447 | } |
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 | } | ||
456 | } | 448 | } |
457 | else | 449 | else |
458 | { | 450 | { |
459 | if (node->parent->left_child == node) | 451 | heap->root = node->right_child; |
460 | node->parent->left_child = NULL; | ||
461 | else | ||
462 | node->parent->right_child = NULL; | ||
463 | if (node->left_child != NULL) | ||
464 | { | ||
465 | node->left_child->parent = NULL; | ||
466 | node->parent->tree_size -= (1 + node->left_child->tree_size); | ||
467 | insert_node (heap, node->parent, node->left_child); | ||
468 | } | ||
469 | if (node->right_child != NULL) | 452 | if (node->right_child != NULL) |
470 | { | 453 | node->right_child->parent = NULL; |
471 | node->right_child->parent = NULL; | 454 | } |
472 | node->parent->tree_size -= (1 + node->right_child->tree_size); | 455 | } |
473 | insert_node (heap, node->parent, node->right_child); | 456 | else |
474 | } | 457 | { |
458 | if (node->parent->left_child == node) | ||
459 | node->parent->left_child = NULL; | ||
460 | else | ||
461 | node->parent->right_child = NULL; | ||
462 | if (node->left_child != NULL) | ||
463 | { | ||
464 | node->left_child->parent = NULL; | ||
465 | node->parent->tree_size -= (1 + node->left_child->tree_size); | ||
466 | insert_node (heap, node->parent, node->left_child); | ||
467 | } | ||
468 | if (node->right_child != NULL) | ||
469 | { | ||
470 | node->right_child->parent = NULL; | ||
471 | node->parent->tree_size -= (1 + node->right_child->tree_size); | ||
472 | insert_node (heap, node->parent, node->right_child); | ||
475 | } | 473 | } |
474 | } | ||
476 | node->parent = NULL; | 475 | node->parent = NULL; |
477 | node->left_child = NULL; | 476 | node->left_child = NULL; |
478 | node->right_child = NULL; | 477 | node->right_child = NULL; |
@@ -506,7 +505,7 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node) | |||
506 | #if DEBUG | 505 | #if DEBUG |
507 | CHECK (heap->root); | 506 | CHECK (heap->root); |
508 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || | 507 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || |
509 | (heap->size == heap->root->tree_size + 1)); | 508 | (heap->size == heap->root->tree_size + 1)); |
510 | #endif | 509 | #endif |
511 | return ret; | 510 | return ret; |
512 | } | 511 | } |
@@ -521,19 +520,19 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node) | |||
521 | */ | 520 | */ |
522 | void | 521 | void |
523 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, | 522 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, |
524 | struct GNUNET_CONTAINER_HeapNode *node, | 523 | struct GNUNET_CONTAINER_HeapNode *node, |
525 | GNUNET_CONTAINER_HeapCostType new_cost) | 524 | GNUNET_CONTAINER_HeapCostType new_cost) |
526 | { | 525 | { |
527 | #if DEBUG | 526 | #if DEBUG |
528 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || | 527 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || |
529 | (heap->size == heap->root->tree_size + 1)); | 528 | (heap->size == heap->root->tree_size + 1)); |
530 | CHECK (heap->root); | 529 | CHECK (heap->root); |
531 | #endif | 530 | #endif |
532 | remove_node (node); | 531 | remove_node (node); |
533 | #if DEBUG | 532 | #if DEBUG |
534 | CHECK (heap->root); | 533 | CHECK (heap->root); |
535 | GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) || | 534 | GNUNET_assert (((heap->size == 1) && (heap->root == NULL)) || |
536 | (heap->size == heap->root->tree_size + 2)); | 535 | (heap->size == heap->root->tree_size + 2)); |
537 | #endif | 536 | #endif |
538 | node->cost = new_cost; | 537 | node->cost = new_cost; |
539 | if (heap->root == NULL) | 538 | if (heap->root == NULL) |
@@ -543,7 +542,7 @@ GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, | |||
543 | #if DEBUG | 542 | #if DEBUG |
544 | CHECK (heap->root); | 543 | CHECK (heap->root); |
545 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || | 544 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || |
546 | (heap->size == heap->root->tree_size + 1)); | 545 | (heap->size == heap->root->tree_size + 1)); |
547 | #endif | 546 | #endif |
548 | } | 547 | } |
549 | 548 | ||