diff options
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r-- | src/util/container_heap.c | 295 |
1 files changed, 149 insertions, 146 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index 3c8e6ce58..35d7cd4ab 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -28,14 +28,16 @@ | |||
28 | #include "platform.h" | 28 | #include "platform.h" |
29 | #include "gnunet_container_lib.h" | 29 | #include "gnunet_container_lib.h" |
30 | 30 | ||
31 | #define LOG(kind, ...) GNUNET_log_from(kind, "util-container-heap", __VA_ARGS__) | 31 | #define LOG(kind, ...) GNUNET_log_from (kind, "util-container-heap", \ |
32 | __VA_ARGS__) | ||
32 | 33 | ||
33 | #define EXTRA_CHECKS 0 | 34 | #define EXTRA_CHECKS 0 |
34 | 35 | ||
35 | /** | 36 | /** |
36 | * Node in the heap. | 37 | * Node in the heap. |
37 | */ | 38 | */ |
38 | struct GNUNET_CONTAINER_HeapNode { | 39 | struct GNUNET_CONTAINER_HeapNode |
40 | { | ||
39 | /** | 41 | /** |
40 | * Heap this node belongs to. | 42 | * Heap this node belongs to. |
41 | */ | 43 | */ |
@@ -76,7 +78,8 @@ struct GNUNET_CONTAINER_HeapNode { | |||
76 | /** | 78 | /** |
77 | * Handle to a node in a heap. | 79 | * Handle to a node in a heap. |
78 | */ | 80 | */ |
79 | struct GNUNET_CONTAINER_Heap { | 81 | struct GNUNET_CONTAINER_Heap |
82 | { | ||
80 | /** | 83 | /** |
81 | * Root of the heap. | 84 | * Root of the heap. |
82 | */ | 85 | */ |
@@ -106,21 +109,21 @@ struct GNUNET_CONTAINER_Heap { | |||
106 | * @param node subtree to check | 109 | * @param node subtree to check |
107 | */ | 110 | */ |
108 | static void | 111 | static void |
109 | check(const struct GNUNET_CONTAINER_HeapNode *node) | 112 | check (const struct GNUNET_CONTAINER_HeapNode *node) |
110 | { | 113 | { |
111 | if (NULL == node) | 114 | if (NULL == node) |
112 | return; | 115 | return; |
113 | GNUNET_assert(node->tree_size == | 116 | GNUNET_assert (node->tree_size == |
114 | ((node->left_child == | 117 | ((node->left_child == |
115 | NULL) ? 0 : 1 + node->left_child->tree_size) + | 118 | NULL) ? 0 : 1 + node->left_child->tree_size) |
116 | ((node->right_child == | 119 | + ((node->right_child == |
117 | NULL) ? 0 : 1 + node->right_child->tree_size)); | 120 | NULL) ? 0 : 1 + node->right_child->tree_size)); |
118 | check(node->left_child); | 121 | check (node->left_child); |
119 | check(node->right_child); | 122 | check (node->right_child); |
120 | } | 123 | } |
121 | 124 | ||
122 | 125 | ||
123 | #define CHECK(n) check(n) | 126 | #define CHECK(n) check (n) |
124 | #else | 127 | #else |
125 | #define CHECK(n) do {} while (0) | 128 | #define CHECK(n) do {} while (0) |
126 | #endif | 129 | #endif |
@@ -133,11 +136,11 @@ check(const struct GNUNET_CONTAINER_HeapNode *node) | |||
133 | * @return handle to the heap | 136 | * @return handle to the heap |
134 | */ | 137 | */ |
135 | struct GNUNET_CONTAINER_Heap * | 138 | struct GNUNET_CONTAINER_Heap * |
136 | GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order) | 139 | GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order) |
137 | { | 140 | { |
138 | struct GNUNET_CONTAINER_Heap *heap; | 141 | struct GNUNET_CONTAINER_Heap *heap; |
139 | 142 | ||
140 | heap = GNUNET_new(struct GNUNET_CONTAINER_Heap); | 143 | heap = GNUNET_new (struct GNUNET_CONTAINER_Heap); |
141 | heap->order = order; | 144 | heap->order = order; |
142 | return heap; | 145 | return heap; |
143 | } | 146 | } |
@@ -150,10 +153,10 @@ GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order) | |||
150 | * @param heap heap to destroy | 153 | * @param heap heap to destroy |
151 | */ | 154 | */ |
152 | void | 155 | void |
153 | GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap) | 156 | GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) |
154 | { | 157 | { |
155 | GNUNET_break(heap->size == 0); | 158 | GNUNET_break (heap->size == 0); |
156 | GNUNET_free(heap); | 159 | GNUNET_free (heap); |
157 | } | 160 | } |
158 | 161 | ||
159 | 162 | ||
@@ -164,7 +167,7 @@ GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap) | |||
164 | * @return Element at the root, or NULL if heap is empty. | 167 | * @return Element at the root, or NULL if heap is empty. |
165 | */ | 168 | */ |
166 | void * | 169 | void * |
167 | GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap) | 170 | GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap) |
168 | { | 171 | { |
169 | if (heap->root == NULL) | 172 | if (heap->root == NULL) |
170 | return NULL; | 173 | return NULL; |
@@ -182,9 +185,9 @@ GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap) | |||
182 | * #GNUNET_NO if the heap is empty. | 185 | * #GNUNET_NO if the heap is empty. |
183 | */ | 186 | */ |
184 | int | 187 | int |
185 | GNUNET_CONTAINER_heap_peek2(const struct GNUNET_CONTAINER_Heap *heap, | 188 | GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap, |
186 | void **element, | 189 | void **element, |
187 | GNUNET_CONTAINER_HeapCostType *cost) | 190 | GNUNET_CONTAINER_HeapCostType *cost) |
188 | { | 191 | { |
189 | if (NULL == heap->root) | 192 | if (NULL == heap->root) |
190 | return GNUNET_NO; | 193 | return GNUNET_NO; |
@@ -203,7 +206,7 @@ GNUNET_CONTAINER_heap_peek2(const struct GNUNET_CONTAINER_Heap *heap, | |||
203 | * @return number of elements stored | 206 | * @return number of elements stored |
204 | */ | 207 | */ |
205 | unsigned int | 208 | unsigned int |
206 | GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap) | 209 | GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap) |
207 | { | 210 | { |
208 | return heap->size; | 211 | return heap->size; |
209 | } | 212 | } |
@@ -216,8 +219,8 @@ GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap) | |||
216 | * @return cost of the node | 219 | * @return cost of the node |
217 | */ | 220 | */ |
218 | GNUNET_CONTAINER_HeapCostType | 221 | GNUNET_CONTAINER_HeapCostType |
219 | GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode | 222 | GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode |
220 | *node) | 223 | *node) |
221 | { | 224 | { |
222 | return node->cost; | 225 | return node->cost; |
223 | } | 226 | } |
@@ -233,19 +236,19 @@ GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode | |||
233 | * @return GNUNET_YES to continue to iterate | 236 | * @return GNUNET_YES to continue to iterate |
234 | */ | 237 | */ |
235 | static int | 238 | static int |
236 | node_iterator(const struct GNUNET_CONTAINER_Heap *heap, | 239 | node_iterator (const struct GNUNET_CONTAINER_Heap *heap, |
237 | struct GNUNET_CONTAINER_HeapNode *node, | 240 | struct GNUNET_CONTAINER_HeapNode *node, |
238 | GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) | 241 | GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) |
239 | { | 242 | { |
240 | if (node == NULL) | 243 | if (node == NULL) |
241 | return GNUNET_YES; | 244 | return GNUNET_YES; |
242 | if (GNUNET_YES != | 245 | if (GNUNET_YES != |
243 | node_iterator(heap, node->left_child, iterator, iterator_cls)) | 246 | node_iterator (heap, node->left_child, iterator, iterator_cls)) |
244 | return GNUNET_NO; | 247 | return GNUNET_NO; |
245 | if (GNUNET_YES != | 248 | if (GNUNET_YES != |
246 | node_iterator(heap, node->right_child, iterator, iterator_cls)) | 249 | node_iterator (heap, node->right_child, iterator, iterator_cls)) |
247 | return GNUNET_NO; | 250 | return GNUNET_NO; |
248 | return iterator(iterator_cls, node, node->element, node->cost); | 251 | return iterator (iterator_cls, node, node->element, node->cost); |
249 | } | 252 | } |
250 | 253 | ||
251 | 254 | ||
@@ -257,11 +260,11 @@ node_iterator(const struct GNUNET_CONTAINER_Heap *heap, | |||
257 | * @param iterator_cls closure for iterator | 260 | * @param iterator_cls closure for iterator |
258 | */ | 261 | */ |
259 | void | 262 | void |
260 | GNUNET_CONTAINER_heap_iterate(const struct GNUNET_CONTAINER_Heap *heap, | 263 | GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, |
261 | GNUNET_CONTAINER_HeapIterator iterator, | 264 | GNUNET_CONTAINER_HeapIterator iterator, |
262 | void *iterator_cls) | 265 | void *iterator_cls) |
263 | { | 266 | { |
264 | (void)node_iterator(heap, heap->root, iterator, iterator_cls); | 267 | (void) node_iterator (heap, heap->root, iterator, iterator_cls); |
265 | } | 268 | } |
266 | 269 | ||
267 | 270 | ||
@@ -277,7 +280,7 @@ GNUNET_CONTAINER_heap_iterate(const struct GNUNET_CONTAINER_Heap *heap, | |||
277 | * NULL if the tree is empty. | 280 | * NULL if the tree is empty. |
278 | */ | 281 | */ |
279 | void * | 282 | void * |
280 | GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap) | 283 | GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) |
281 | { | 284 | { |
282 | struct GNUNET_CONTAINER_HeapNode *pos; | 285 | struct GNUNET_CONTAINER_HeapNode *pos; |
283 | void *element; | 286 | void *element; |
@@ -290,8 +293,8 @@ GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap) | |||
290 | element = pos->element; | 293 | element = pos->element; |
291 | heap->walk_pos = | 294 | heap->walk_pos = |
292 | (0 == | 295 | (0 == |
293 | GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, | 296 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, |
294 | 2)) ? pos->right_child : pos->left_child; | 297 | 2)) ? pos->right_child : pos->left_child; |
295 | return element; | 298 | return element; |
296 | } | 299 | } |
297 | 300 | ||
@@ -305,55 +308,55 @@ GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap) | |||
305 | * @param node node to insert (which may be a subtree itself) | 308 | * @param node node to insert (which may be a subtree itself) |
306 | */ | 309 | */ |
307 | static void | 310 | static void |
308 | insert_node(struct GNUNET_CONTAINER_Heap *heap, | 311 | insert_node (struct GNUNET_CONTAINER_Heap *heap, |
309 | struct GNUNET_CONTAINER_HeapNode *pos, | 312 | struct GNUNET_CONTAINER_HeapNode *pos, |
310 | struct GNUNET_CONTAINER_HeapNode *node) | 313 | struct GNUNET_CONTAINER_HeapNode *node) |
311 | { | 314 | { |
312 | struct GNUNET_CONTAINER_HeapNode *parent; | 315 | struct GNUNET_CONTAINER_HeapNode *parent; |
313 | 316 | ||
314 | GNUNET_assert(node->parent == NULL); | 317 | GNUNET_assert (node->parent == NULL); |
315 | while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= | 318 | while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= |
316 | node->cost) | 319 | node->cost) |
317 | : (pos->cost <= node->cost)) | 320 | : (pos->cost <= node->cost)) |
321 | { | ||
322 | /* node is descendent of pos */ | ||
323 | pos->tree_size += (1 + node->tree_size); | ||
324 | if (pos->left_child == NULL) | ||
325 | { | ||
326 | pos->left_child = node; | ||
327 | node->parent = pos; | ||
328 | return; | ||
329 | } | ||
330 | if (pos->right_child == NULL) | ||
318 | { | 331 | { |
319 | /* node is descendent of pos */ | 332 | pos->right_child = node; |
320 | pos->tree_size += (1 + node->tree_size); | 333 | node->parent = pos; |
321 | if (pos->left_child == NULL) | 334 | return; |
322 | { | ||
323 | pos->left_child = node; | ||
324 | node->parent = pos; | ||
325 | return; | ||
326 | } | ||
327 | if (pos->right_child == NULL) | ||
328 | { | ||
329 | pos->right_child = node; | ||
330 | node->parent = pos; | ||
331 | return; | ||
332 | } | ||
333 | /* keep it balanced by descending into smaller subtree */ | ||
334 | if (pos->left_child->tree_size < pos->right_child->tree_size) | ||
335 | pos = pos->left_child; | ||
336 | else | ||
337 | pos = pos->right_child; | ||
338 | } | 335 | } |
336 | /* keep it balanced by descending into smaller subtree */ | ||
337 | if (pos->left_child->tree_size < pos->right_child->tree_size) | ||
338 | pos = pos->left_child; | ||
339 | else | ||
340 | pos = pos->right_child; | ||
341 | } | ||
339 | /* make 'node' parent of 'pos' */ | 342 | /* make 'node' parent of 'pos' */ |
340 | parent = pos->parent; | 343 | parent = pos->parent; |
341 | pos->parent = NULL; | 344 | pos->parent = NULL; |
342 | node->parent = parent; | 345 | node->parent = parent; |
343 | if (NULL == parent) | 346 | if (NULL == parent) |
344 | { | 347 | { |
345 | heap->root = node; | 348 | heap->root = node; |
346 | } | 349 | } |
347 | else | 350 | else |
348 | { | 351 | { |
349 | if (parent->left_child == pos) | 352 | if (parent->left_child == pos) |
350 | parent->left_child = node; | 353 | parent->left_child = node; |
351 | else | 354 | else |
352 | parent->right_child = node; | 355 | parent->right_child = node; |
353 | } | 356 | } |
354 | /* insert 'pos' below 'node' */ | 357 | /* insert 'pos' below 'node' */ |
355 | insert_node(heap, node, pos); | 358 | insert_node (heap, node, pos); |
356 | CHECK(pos); | 359 | CHECK (pos); |
357 | } | 360 | } |
358 | 361 | ||
359 | 362 | ||
@@ -366,12 +369,12 @@ insert_node(struct GNUNET_CONTAINER_Heap *heap, | |||
366 | * @return node for the new element | 369 | * @return node for the new element |
367 | */ | 370 | */ |
368 | struct GNUNET_CONTAINER_HeapNode * | 371 | struct GNUNET_CONTAINER_HeapNode * |
369 | GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, | 372 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, |
370 | GNUNET_CONTAINER_HeapCostType cost) | 373 | GNUNET_CONTAINER_HeapCostType cost) |
371 | { | 374 | { |
372 | struct GNUNET_CONTAINER_HeapNode *node; | 375 | struct GNUNET_CONTAINER_HeapNode *node; |
373 | 376 | ||
374 | node = GNUNET_new(struct GNUNET_CONTAINER_HeapNode); | 377 | node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode); |
375 | node->heap = heap; | 378 | node->heap = heap; |
376 | node->element = element; | 379 | node->element = element; |
377 | node->cost = cost; | 380 | node->cost = cost; |
@@ -379,9 +382,9 @@ GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, | |||
379 | if (NULL == heap->root) | 382 | if (NULL == heap->root) |
380 | heap->root = node; | 383 | heap->root = node; |
381 | else | 384 | else |
382 | insert_node(heap, heap->root, node); | 385 | insert_node (heap, heap->root, node); |
383 | GNUNET_assert(heap->size == heap->root->tree_size + 1); | 386 | GNUNET_assert (heap->size == heap->root->tree_size + 1); |
384 | CHECK(heap->root); | 387 | CHECK (heap->root); |
385 | return node; | 388 | return node; |
386 | } | 389 | } |
387 | 390 | ||
@@ -393,7 +396,7 @@ GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, | |||
393 | * @return element data stored at the root node, NULL if heap is empty | 396 | * @return element data stored at the root node, NULL if heap is empty |
394 | */ | 397 | */ |
395 | void * | 398 | void * |
396 | GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap) | 399 | GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) |
397 | { | 400 | { |
398 | void *ret; | 401 | void *ret; |
399 | struct GNUNET_CONTAINER_HeapNode *root; | 402 | struct GNUNET_CONTAINER_HeapNode *root; |
@@ -403,30 +406,30 @@ GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap) | |||
403 | heap->size--; | 406 | heap->size--; |
404 | ret = root->element; | 407 | ret = root->element; |
405 | if (root->left_child == NULL) | 408 | if (root->left_child == NULL) |
406 | { | 409 | { |
407 | heap->root = root->right_child; | 410 | heap->root = root->right_child; |
408 | if (root->right_child != NULL) | 411 | if (root->right_child != NULL) |
409 | root->right_child->parent = NULL; | 412 | root->right_child->parent = NULL; |
410 | } | 413 | } |
411 | else if (root->right_child == NULL) | 414 | else if (root->right_child == NULL) |
412 | { | 415 | { |
413 | heap->root = root->left_child; | 416 | heap->root = root->left_child; |
414 | root->left_child->parent = NULL; | 417 | root->left_child->parent = NULL; |
415 | } | 418 | } |
416 | else | 419 | else |
417 | { | 420 | { |
418 | root->left_child->parent = NULL; | 421 | root->left_child->parent = NULL; |
419 | root->right_child->parent = NULL; | 422 | root->right_child->parent = NULL; |
420 | heap->root = root->left_child; | 423 | heap->root = root->left_child; |
421 | insert_node(heap, heap->root, root->right_child); | 424 | insert_node (heap, heap->root, root->right_child); |
422 | } | 425 | } |
423 | if (heap->walk_pos == root) | 426 | if (heap->walk_pos == root) |
424 | heap->walk_pos = heap->root; | 427 | heap->walk_pos = heap->root; |
425 | GNUNET_free(root); | 428 | GNUNET_free (root); |
426 | #if EXTRA_CHECKS | 429 | #if EXTRA_CHECKS |
427 | GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) || | 430 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || |
428 | (heap->size == heap->root->tree_size + 1)); | 431 | (heap->size == heap->root->tree_size + 1)); |
429 | CHECK(heap->root); | 432 | CHECK (heap->root); |
430 | #endif | 433 | #endif |
431 | return ret; | 434 | return ret; |
432 | } | 435 | } |
@@ -439,7 +442,7 @@ GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap) | |||
439 | * 'size' field of the tree. | 442 | * 'size' field of the tree. |
440 | */ | 443 | */ |
441 | static void | 444 | static void |
442 | remove_node(struct GNUNET_CONTAINER_HeapNode *node) | 445 | remove_node (struct GNUNET_CONTAINER_HeapNode *node) |
443 | { | 446 | { |
444 | struct GNUNET_CONTAINER_HeapNode *ancestor; | 447 | struct GNUNET_CONTAINER_HeapNode *ancestor; |
445 | struct GNUNET_CONTAINER_Heap *heap = node->heap; | 448 | struct GNUNET_CONTAINER_Heap *heap = node->heap; |
@@ -457,48 +460,48 @@ remove_node(struct GNUNET_CONTAINER_HeapNode *node) | |||
457 | 460 | ||
458 | /* unlink 'node' itself and insert children in its place */ | 461 | /* unlink 'node' itself and insert children in its place */ |
459 | if (node->parent == NULL) | 462 | if (node->parent == NULL) |
463 | { | ||
464 | if (node->left_child != NULL) | ||
465 | { | ||
466 | heap->root = node->left_child; | ||
467 | node->left_child->parent = NULL; | ||
468 | if (node->right_child != NULL) | ||
469 | { | ||
470 | node->right_child->parent = NULL; | ||
471 | insert_node (heap, heap->root, node->right_child); | ||
472 | } | ||
473 | } | ||
474 | else | ||
460 | { | 475 | { |
461 | if (node->left_child != NULL) | 476 | heap->root = node->right_child; |
462 | { | 477 | if (node->right_child != NULL) |
463 | heap->root = node->left_child; | 478 | node->right_child->parent = NULL; |
464 | node->left_child->parent = NULL; | ||
465 | if (node->right_child != NULL) | ||
466 | { | ||
467 | node->right_child->parent = NULL; | ||
468 | insert_node(heap, heap->root, node->right_child); | ||
469 | } | ||
470 | } | ||
471 | else | ||
472 | { | ||
473 | heap->root = node->right_child; | ||
474 | if (node->right_child != NULL) | ||
475 | node->right_child->parent = NULL; | ||
476 | } | ||
477 | } | 479 | } |
480 | } | ||
478 | else | 481 | else |
482 | { | ||
483 | if (node->parent->left_child == node) | ||
484 | node->parent->left_child = NULL; | ||
485 | else | ||
486 | node->parent->right_child = NULL; | ||
487 | if (node->left_child != NULL) | ||
479 | { | 488 | { |
480 | if (node->parent->left_child == node) | 489 | node->left_child->parent = NULL; |
481 | node->parent->left_child = NULL; | 490 | node->parent->tree_size -= (1 + node->left_child->tree_size); |
482 | else | 491 | insert_node (heap, node->parent, node->left_child); |
483 | node->parent->right_child = NULL; | 492 | } |
484 | if (node->left_child != NULL) | 493 | if (node->right_child != NULL) |
485 | { | 494 | { |
486 | node->left_child->parent = NULL; | 495 | node->right_child->parent = NULL; |
487 | node->parent->tree_size -= (1 + node->left_child->tree_size); | 496 | node->parent->tree_size -= (1 + node->right_child->tree_size); |
488 | insert_node(heap, node->parent, node->left_child); | 497 | insert_node (heap, node->parent, node->right_child); |
489 | } | ||
490 | if (node->right_child != NULL) | ||
491 | { | ||
492 | node->right_child->parent = NULL; | ||
493 | node->parent->tree_size -= (1 + node->right_child->tree_size); | ||
494 | insert_node(heap, node->parent, node->right_child); | ||
495 | } | ||
496 | } | 498 | } |
499 | } | ||
497 | node->parent = NULL; | 500 | node->parent = NULL; |
498 | node->left_child = NULL; | 501 | node->left_child = NULL; |
499 | node->right_child = NULL; | 502 | node->right_child = NULL; |
500 | GNUNET_assert(node->tree_size == 0); | 503 | GNUNET_assert (node->tree_size == 0); |
501 | CHECK(heap->root); | 504 | CHECK (heap->root); |
502 | } | 505 | } |
503 | 506 | ||
504 | 507 | ||
@@ -509,25 +512,25 @@ remove_node(struct GNUNET_CONTAINER_HeapNode *node) | |||
509 | * @return element data stored at the node | 512 | * @return element data stored at the node |
510 | */ | 513 | */ |
511 | void * | 514 | void * |
512 | GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node) | 515 | GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node) |
513 | { | 516 | { |
514 | void *ret; | 517 | void *ret; |
515 | struct GNUNET_CONTAINER_Heap *heap; | 518 | struct GNUNET_CONTAINER_Heap *heap; |
516 | 519 | ||
517 | heap = node->heap; | 520 | heap = node->heap; |
518 | CHECK(heap->root); | 521 | CHECK (heap->root); |
519 | if (heap->walk_pos == node) | 522 | if (heap->walk_pos == node) |
520 | (void)GNUNET_CONTAINER_heap_walk_get_next(heap); | 523 | (void) GNUNET_CONTAINER_heap_walk_get_next (heap); |
521 | remove_node(node); | 524 | remove_node (node); |
522 | heap->size--; | 525 | heap->size--; |
523 | ret = node->element; | 526 | ret = node->element; |
524 | if (heap->walk_pos == node) | 527 | if (heap->walk_pos == node) |
525 | heap->walk_pos = NULL; | 528 | heap->walk_pos = NULL; |
526 | GNUNET_free(node); | 529 | GNUNET_free (node); |
527 | #if EXTRA_CHECKS | 530 | #if EXTRA_CHECKS |
528 | CHECK(heap->root); | 531 | CHECK (heap->root); |
529 | GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) || | 532 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || |
530 | (heap->size == heap->root->tree_size + 1)); | 533 | (heap->size == heap->root->tree_size + 1)); |
531 | #endif | 534 | #endif |
532 | return ret; | 535 | return ret; |
533 | } | 536 | } |
@@ -540,19 +543,19 @@ GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node) | |||
540 | * @param new_cost new cost for the node | 543 | * @param new_cost new cost for the node |
541 | */ | 544 | */ |
542 | void | 545 | void |
543 | GNUNET_CONTAINER_heap_update_cost(struct GNUNET_CONTAINER_HeapNode *node, | 546 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node, |
544 | GNUNET_CONTAINER_HeapCostType new_cost) | 547 | GNUNET_CONTAINER_HeapCostType new_cost) |
545 | { | 548 | { |
546 | struct GNUNET_CONTAINER_Heap *heap = node->heap; | 549 | struct GNUNET_CONTAINER_Heap *heap = node->heap; |
547 | 550 | ||
548 | remove_node(node); | 551 | remove_node (node); |
549 | node->cost = new_cost; | 552 | node->cost = new_cost; |
550 | if (NULL == heap->root) | 553 | if (NULL == heap->root) |
551 | heap->root = node; | 554 | heap->root = node; |
552 | else | 555 | else |
553 | insert_node(heap, | 556 | insert_node (heap, |
554 | heap->root, | 557 | heap->root, |
555 | node); | 558 | node); |
556 | } | 559 | } |
557 | 560 | ||
558 | 561 | ||