diff options
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r-- | src/util/container_heap.c | 329 |
1 files changed, 162 insertions, 167 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index d5dca20ef..3c8e6ce58 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -1,22 +1,22 @@ | |||
1 | /* | 1 | /* |
2 | This file is part of GNUnet. | 2 | This file is part of GNUnet. |
3 | Copyright (C) 2008, 2009 GNUnet e.V. | 3 | Copyright (C) 2008, 2009 GNUnet e.V. |
4 | 4 | ||
5 | GNUnet is free software: you can redistribute it and/or modify it | 5 | GNUnet is free software: you can redistribute it and/or modify it |
6 | under the terms of the GNU Affero General Public License as published | 6 | under the terms of the GNU Affero General Public License as published |
7 | by the Free Software Foundation, either version 3 of the License, | 7 | by the Free Software Foundation, either version 3 of the License, |
8 | or (at your option) any later version. | 8 | or (at your option) any later version. |
9 | 9 | ||
10 | GNUnet is distributed in the hope that it will be useful, but | 10 | GNUnet is distributed in the hope that it will be useful, but |
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | 11 | WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Affero General Public License for more details. | 13 | Affero General Public License for more details. |
14 | 14 | ||
15 | You should have received a copy of the GNU Affero General Public License | 15 | You should have received a copy of the GNU Affero General Public License |
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | 17 | ||
18 | SPDX-License-Identifier: AGPL3.0-or-later | 18 | SPDX-License-Identifier: AGPL3.0-or-later |
19 | */ | 19 | */ |
20 | 20 | ||
21 | /** | 21 | /** |
22 | * @file util/container_heap.c | 22 | * @file util/container_heap.c |
@@ -28,15 +28,14 @@ | |||
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", __VA_ARGS__) |
32 | 32 | ||
33 | #define EXTRA_CHECKS 0 | 33 | #define EXTRA_CHECKS 0 |
34 | 34 | ||
35 | /** | 35 | /** |
36 | * Node in the heap. | 36 | * Node in the heap. |
37 | */ | 37 | */ |
38 | struct GNUNET_CONTAINER_HeapNode | 38 | struct GNUNET_CONTAINER_HeapNode { |
39 | { | ||
40 | /** | 39 | /** |
41 | * Heap this node belongs to. | 40 | * Heap this node belongs to. |
42 | */ | 41 | */ |
@@ -72,15 +71,12 @@ struct GNUNET_CONTAINER_HeapNode | |||
72 | * (excluding this node itself). | 71 | * (excluding this node itself). |
73 | */ | 72 | */ |
74 | unsigned int tree_size; | 73 | unsigned int tree_size; |
75 | |||
76 | }; | 74 | }; |
77 | 75 | ||
78 | /** | 76 | /** |
79 | * Handle to a node in a heap. | 77 | * Handle to a node in a heap. |
80 | */ | 78 | */ |
81 | struct GNUNET_CONTAINER_Heap | 79 | struct GNUNET_CONTAINER_Heap { |
82 | { | ||
83 | |||
84 | /** | 80 | /** |
85 | * Root of the heap. | 81 | * Root of the heap. |
86 | */ | 82 | */ |
@@ -100,7 +96,6 @@ struct GNUNET_CONTAINER_Heap | |||
100 | * How is the heap sorted? | 96 | * How is the heap sorted? |
101 | */ | 97 | */ |
102 | enum GNUNET_CONTAINER_HeapOrder order; | 98 | enum GNUNET_CONTAINER_HeapOrder order; |
103 | |||
104 | }; | 99 | }; |
105 | 100 | ||
106 | 101 | ||
@@ -111,17 +106,17 @@ struct GNUNET_CONTAINER_Heap | |||
111 | * @param node subtree to check | 106 | * @param node subtree to check |
112 | */ | 107 | */ |
113 | static void | 108 | static void |
114 | check (const struct GNUNET_CONTAINER_HeapNode *node) | 109 | check(const struct GNUNET_CONTAINER_HeapNode *node) |
115 | { | 110 | { |
116 | if (NULL == node) | 111 | if (NULL == node) |
117 | return; | 112 | return; |
118 | GNUNET_assert (node->tree_size == | 113 | GNUNET_assert(node->tree_size == |
119 | ((node->left_child == | 114 | ((node->left_child == |
120 | NULL) ? 0 : 1 + node->left_child->tree_size) + | 115 | NULL) ? 0 : 1 + node->left_child->tree_size) + |
121 | ((node->right_child == | 116 | ((node->right_child == |
122 | NULL) ? 0 : 1 + node->right_child->tree_size)); | 117 | NULL) ? 0 : 1 + node->right_child->tree_size)); |
123 | check (node->left_child); | 118 | check(node->left_child); |
124 | check (node->right_child); | 119 | check(node->right_child); |
125 | } | 120 | } |
126 | 121 | ||
127 | 122 | ||
@@ -138,11 +133,11 @@ check (const struct GNUNET_CONTAINER_HeapNode *node) | |||
138 | * @return handle to the heap | 133 | * @return handle to the heap |
139 | */ | 134 | */ |
140 | struct GNUNET_CONTAINER_Heap * | 135 | struct GNUNET_CONTAINER_Heap * |
141 | GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order) | 136 | GNUNET_CONTAINER_heap_create(enum GNUNET_CONTAINER_HeapOrder order) |
142 | { | 137 | { |
143 | struct GNUNET_CONTAINER_Heap *heap; | 138 | struct GNUNET_CONTAINER_Heap *heap; |
144 | 139 | ||
145 | heap = GNUNET_new (struct GNUNET_CONTAINER_Heap); | 140 | heap = GNUNET_new(struct GNUNET_CONTAINER_Heap); |
146 | heap->order = order; | 141 | heap->order = order; |
147 | return heap; | 142 | return heap; |
148 | } | 143 | } |
@@ -155,10 +150,10 @@ GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order) | |||
155 | * @param heap heap to destroy | 150 | * @param heap heap to destroy |
156 | */ | 151 | */ |
157 | void | 152 | void |
158 | GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) | 153 | GNUNET_CONTAINER_heap_destroy(struct GNUNET_CONTAINER_Heap *heap) |
159 | { | 154 | { |
160 | GNUNET_break (heap->size == 0); | 155 | GNUNET_break(heap->size == 0); |
161 | GNUNET_free (heap); | 156 | GNUNET_free(heap); |
162 | } | 157 | } |
163 | 158 | ||
164 | 159 | ||
@@ -169,7 +164,7 @@ GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) | |||
169 | * @return Element at the root, or NULL if heap is empty. | 164 | * @return Element at the root, or NULL if heap is empty. |
170 | */ | 165 | */ |
171 | void * | 166 | void * |
172 | GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap) | 167 | GNUNET_CONTAINER_heap_peek(const struct GNUNET_CONTAINER_Heap *heap) |
173 | { | 168 | { |
174 | if (heap->root == NULL) | 169 | if (heap->root == NULL) |
175 | return NULL; | 170 | return NULL; |
@@ -187,9 +182,9 @@ GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap) | |||
187 | * #GNUNET_NO if the heap is empty. | 182 | * #GNUNET_NO if the heap is empty. |
188 | */ | 183 | */ |
189 | int | 184 | int |
190 | GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap, | 185 | GNUNET_CONTAINER_heap_peek2(const struct GNUNET_CONTAINER_Heap *heap, |
191 | void **element, | 186 | void **element, |
192 | GNUNET_CONTAINER_HeapCostType *cost) | 187 | GNUNET_CONTAINER_HeapCostType *cost) |
193 | { | 188 | { |
194 | if (NULL == heap->root) | 189 | if (NULL == heap->root) |
195 | return GNUNET_NO; | 190 | return GNUNET_NO; |
@@ -208,7 +203,7 @@ GNUNET_CONTAINER_heap_peek2 (const struct GNUNET_CONTAINER_Heap *heap, | |||
208 | * @return number of elements stored | 203 | * @return number of elements stored |
209 | */ | 204 | */ |
210 | unsigned int | 205 | unsigned int |
211 | GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap) | 206 | GNUNET_CONTAINER_heap_get_size(const struct GNUNET_CONTAINER_Heap *heap) |
212 | { | 207 | { |
213 | return heap->size; | 208 | return heap->size; |
214 | } | 209 | } |
@@ -221,8 +216,8 @@ GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap) | |||
221 | * @return cost of the node | 216 | * @return cost of the node |
222 | */ | 217 | */ |
223 | GNUNET_CONTAINER_HeapCostType | 218 | GNUNET_CONTAINER_HeapCostType |
224 | GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode | 219 | GNUNET_CONTAINER_heap_node_get_cost(const struct GNUNET_CONTAINER_HeapNode |
225 | *node) | 220 | *node) |
226 | { | 221 | { |
227 | return node->cost; | 222 | return node->cost; |
228 | } | 223 | } |
@@ -238,19 +233,19 @@ GNUNET_CONTAINER_heap_node_get_cost (const struct GNUNET_CONTAINER_HeapNode | |||
238 | * @return GNUNET_YES to continue to iterate | 233 | * @return GNUNET_YES to continue to iterate |
239 | */ | 234 | */ |
240 | static int | 235 | static int |
241 | node_iterator (const struct GNUNET_CONTAINER_Heap *heap, | 236 | node_iterator(const struct GNUNET_CONTAINER_Heap *heap, |
242 | struct GNUNET_CONTAINER_HeapNode *node, | 237 | struct GNUNET_CONTAINER_HeapNode *node, |
243 | GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) | 238 | GNUNET_CONTAINER_HeapIterator iterator, void *iterator_cls) |
244 | { | 239 | { |
245 | if (node == NULL) | 240 | if (node == NULL) |
246 | return GNUNET_YES; | 241 | return GNUNET_YES; |
247 | if (GNUNET_YES != | 242 | if (GNUNET_YES != |
248 | node_iterator (heap, node->left_child, iterator, iterator_cls)) | 243 | node_iterator(heap, node->left_child, iterator, iterator_cls)) |
249 | return GNUNET_NO; | 244 | return GNUNET_NO; |
250 | if (GNUNET_YES != | 245 | if (GNUNET_YES != |
251 | node_iterator (heap, node->right_child, iterator, iterator_cls)) | 246 | node_iterator(heap, node->right_child, iterator, iterator_cls)) |
252 | return GNUNET_NO; | 247 | return GNUNET_NO; |
253 | return iterator (iterator_cls, node, node->element, node->cost); | 248 | return iterator(iterator_cls, node, node->element, node->cost); |
254 | } | 249 | } |
255 | 250 | ||
256 | 251 | ||
@@ -262,11 +257,11 @@ node_iterator (const struct GNUNET_CONTAINER_Heap *heap, | |||
262 | * @param iterator_cls closure for iterator | 257 | * @param iterator_cls closure for iterator |
263 | */ | 258 | */ |
264 | void | 259 | void |
265 | GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, | 260 | GNUNET_CONTAINER_heap_iterate(const struct GNUNET_CONTAINER_Heap *heap, |
266 | GNUNET_CONTAINER_HeapIterator iterator, | 261 | GNUNET_CONTAINER_HeapIterator iterator, |
267 | void *iterator_cls) | 262 | void *iterator_cls) |
268 | { | 263 | { |
269 | (void) node_iterator (heap, heap->root, iterator, iterator_cls); | 264 | (void)node_iterator(heap, heap->root, iterator, iterator_cls); |
270 | } | 265 | } |
271 | 266 | ||
272 | 267 | ||
@@ -282,7 +277,7 @@ GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, | |||
282 | * NULL if the tree is empty. | 277 | * NULL if the tree is empty. |
283 | */ | 278 | */ |
284 | void * | 279 | void * |
285 | GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) | 280 | GNUNET_CONTAINER_heap_walk_get_next(struct GNUNET_CONTAINER_Heap *heap) |
286 | { | 281 | { |
287 | struct GNUNET_CONTAINER_HeapNode *pos; | 282 | struct GNUNET_CONTAINER_HeapNode *pos; |
288 | void *element; | 283 | void *element; |
@@ -294,9 +289,9 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) | |||
294 | pos = heap->root; | 289 | pos = heap->root; |
295 | element = pos->element; | 290 | element = pos->element; |
296 | heap->walk_pos = | 291 | heap->walk_pos = |
297 | (0 == | 292 | (0 == |
298 | GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, | 293 | GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, |
299 | 2)) ? pos->right_child : pos->left_child; | 294 | 2)) ? pos->right_child : pos->left_child; |
300 | return element; | 295 | return element; |
301 | } | 296 | } |
302 | 297 | ||
@@ -310,55 +305,55 @@ GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) | |||
310 | * @param node node to insert (which may be a subtree itself) | 305 | * @param node node to insert (which may be a subtree itself) |
311 | */ | 306 | */ |
312 | static void | 307 | static void |
313 | insert_node (struct GNUNET_CONTAINER_Heap *heap, | 308 | insert_node(struct GNUNET_CONTAINER_Heap *heap, |
314 | struct GNUNET_CONTAINER_HeapNode *pos, | 309 | struct GNUNET_CONTAINER_HeapNode *pos, |
315 | struct GNUNET_CONTAINER_HeapNode *node) | 310 | struct GNUNET_CONTAINER_HeapNode *node) |
316 | { | 311 | { |
317 | struct GNUNET_CONTAINER_HeapNode *parent; | 312 | struct GNUNET_CONTAINER_HeapNode *parent; |
318 | 313 | ||
319 | GNUNET_assert (node->parent == NULL); | 314 | GNUNET_assert(node->parent == NULL); |
320 | while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= | 315 | while ((heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ? (pos->cost >= |
321 | node->cost) | 316 | node->cost) |
322 | : (pos->cost <= node->cost)) | 317 | : (pos->cost <= node->cost)) |
323 | { | ||
324 | /* node is descendent of pos */ | ||
325 | pos->tree_size += (1 + node->tree_size); | ||
326 | if (pos->left_child == NULL) | ||
327 | { | ||
328 | pos->left_child = node; | ||
329 | node->parent = pos; | ||
330 | return; | ||
331 | } | ||
332 | if (pos->right_child == NULL) | ||
333 | { | 318 | { |
334 | pos->right_child = node; | 319 | /* node is descendent of pos */ |
335 | node->parent = pos; | 320 | pos->tree_size += (1 + node->tree_size); |
336 | return; | 321 | if (pos->left_child == NULL) |
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; | ||
337 | } | 338 | } |
338 | /* keep it balanced by descending into smaller subtree */ | ||
339 | if (pos->left_child->tree_size < pos->right_child->tree_size) | ||
340 | pos = pos->left_child; | ||
341 | else | ||
342 | pos = pos->right_child; | ||
343 | } | ||
344 | /* make 'node' parent of 'pos' */ | 339 | /* make 'node' parent of 'pos' */ |
345 | parent = pos->parent; | 340 | parent = pos->parent; |
346 | pos->parent = NULL; | 341 | pos->parent = NULL; |
347 | node->parent = parent; | 342 | node->parent = parent; |
348 | if (NULL == parent) | 343 | if (NULL == parent) |
349 | { | 344 | { |
350 | heap->root = node; | 345 | heap->root = node; |
351 | } | 346 | } |
352 | else | 347 | else |
353 | { | 348 | { |
354 | if (parent->left_child == pos) | 349 | if (parent->left_child == pos) |
355 | parent->left_child = node; | 350 | parent->left_child = node; |
356 | else | 351 | else |
357 | parent->right_child = node; | 352 | parent->right_child = node; |
358 | } | 353 | } |
359 | /* insert 'pos' below 'node' */ | 354 | /* insert 'pos' below 'node' */ |
360 | insert_node (heap, node, pos); | 355 | insert_node(heap, node, pos); |
361 | CHECK (pos); | 356 | CHECK(pos); |
362 | } | 357 | } |
363 | 358 | ||
364 | 359 | ||
@@ -371,12 +366,12 @@ insert_node (struct GNUNET_CONTAINER_Heap *heap, | |||
371 | * @return node for the new element | 366 | * @return node for the new element |
372 | */ | 367 | */ |
373 | struct GNUNET_CONTAINER_HeapNode * | 368 | struct GNUNET_CONTAINER_HeapNode * |
374 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, | 369 | GNUNET_CONTAINER_heap_insert(struct GNUNET_CONTAINER_Heap *heap, void *element, |
375 | GNUNET_CONTAINER_HeapCostType cost) | 370 | GNUNET_CONTAINER_HeapCostType cost) |
376 | { | 371 | { |
377 | struct GNUNET_CONTAINER_HeapNode *node; | 372 | struct GNUNET_CONTAINER_HeapNode *node; |
378 | 373 | ||
379 | node = GNUNET_new (struct GNUNET_CONTAINER_HeapNode); | 374 | node = GNUNET_new(struct GNUNET_CONTAINER_HeapNode); |
380 | node->heap = heap; | 375 | node->heap = heap; |
381 | node->element = element; | 376 | node->element = element; |
382 | node->cost = cost; | 377 | node->cost = cost; |
@@ -384,9 +379,9 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, | |||
384 | if (NULL == heap->root) | 379 | if (NULL == heap->root) |
385 | heap->root = node; | 380 | heap->root = node; |
386 | else | 381 | else |
387 | insert_node (heap, heap->root, node); | 382 | insert_node(heap, heap->root, node); |
388 | GNUNET_assert (heap->size == heap->root->tree_size + 1); | 383 | GNUNET_assert(heap->size == heap->root->tree_size + 1); |
389 | CHECK (heap->root); | 384 | CHECK(heap->root); |
390 | return node; | 385 | return node; |
391 | } | 386 | } |
392 | 387 | ||
@@ -398,7 +393,7 @@ GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, void *element, | |||
398 | * @return element data stored at the root node, NULL if heap is empty | 393 | * @return element data stored at the root node, NULL if heap is empty |
399 | */ | 394 | */ |
400 | void * | 395 | void * |
401 | GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) | 396 | GNUNET_CONTAINER_heap_remove_root(struct GNUNET_CONTAINER_Heap *heap) |
402 | { | 397 | { |
403 | void *ret; | 398 | void *ret; |
404 | struct GNUNET_CONTAINER_HeapNode *root; | 399 | struct GNUNET_CONTAINER_HeapNode *root; |
@@ -408,30 +403,30 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) | |||
408 | heap->size--; | 403 | heap->size--; |
409 | ret = root->element; | 404 | ret = root->element; |
410 | if (root->left_child == NULL) | 405 | if (root->left_child == NULL) |
411 | { | 406 | { |
412 | heap->root = root->right_child; | 407 | heap->root = root->right_child; |
413 | if (root->right_child != NULL) | 408 | if (root->right_child != NULL) |
414 | root->right_child->parent = NULL; | 409 | root->right_child->parent = NULL; |
415 | } | 410 | } |
416 | else if (root->right_child == NULL) | 411 | else if (root->right_child == NULL) |
417 | { | 412 | { |
418 | heap->root = root->left_child; | 413 | heap->root = root->left_child; |
419 | root->left_child->parent = NULL; | 414 | root->left_child->parent = NULL; |
420 | } | 415 | } |
421 | else | 416 | else |
422 | { | 417 | { |
423 | root->left_child->parent = NULL; | 418 | root->left_child->parent = NULL; |
424 | root->right_child->parent = NULL; | 419 | root->right_child->parent = NULL; |
425 | heap->root = root->left_child; | 420 | heap->root = root->left_child; |
426 | insert_node (heap, heap->root, root->right_child); | 421 | insert_node(heap, heap->root, root->right_child); |
427 | } | 422 | } |
428 | if (heap->walk_pos == root) | 423 | if (heap->walk_pos == root) |
429 | heap->walk_pos = heap->root; | 424 | heap->walk_pos = heap->root; |
430 | GNUNET_free (root); | 425 | GNUNET_free(root); |
431 | #if EXTRA_CHECKS | 426 | #if EXTRA_CHECKS |
432 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || | 427 | GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) || |
433 | (heap->size == heap->root->tree_size + 1)); | 428 | (heap->size == heap->root->tree_size + 1)); |
434 | CHECK (heap->root); | 429 | CHECK(heap->root); |
435 | #endif | 430 | #endif |
436 | return ret; | 431 | return ret; |
437 | } | 432 | } |
@@ -444,7 +439,7 @@ GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) | |||
444 | * 'size' field of the tree. | 439 | * 'size' field of the tree. |
445 | */ | 440 | */ |
446 | static void | 441 | static void |
447 | remove_node (struct GNUNET_CONTAINER_HeapNode *node) | 442 | remove_node(struct GNUNET_CONTAINER_HeapNode *node) |
448 | { | 443 | { |
449 | struct GNUNET_CONTAINER_HeapNode *ancestor; | 444 | struct GNUNET_CONTAINER_HeapNode *ancestor; |
450 | struct GNUNET_CONTAINER_Heap *heap = node->heap; | 445 | struct GNUNET_CONTAINER_Heap *heap = node->heap; |
@@ -462,48 +457,48 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node) | |||
462 | 457 | ||
463 | /* unlink 'node' itself and insert children in its place */ | 458 | /* unlink 'node' itself and insert children in its place */ |
464 | if (node->parent == NULL) | 459 | if (node->parent == NULL) |
465 | { | ||
466 | if (node->left_child != NULL) | ||
467 | { | 460 | { |
468 | heap->root = node->left_child; | 461 | if (node->left_child != NULL) |
469 | node->left_child->parent = NULL; | 462 | { |
470 | if (node->right_child != NULL) | 463 | heap->root = node->left_child; |
471 | { | 464 | node->left_child->parent = NULL; |
472 | node->right_child->parent = NULL; | 465 | if (node->right_child != NULL) |
473 | insert_node (heap, heap->root, node->right_child); | 466 | { |
474 | } | 467 | node->right_child->parent = NULL; |
475 | } | 468 | insert_node(heap, heap->root, node->right_child); |
476 | else | 469 | } |
477 | { | 470 | } |
478 | heap->root = node->right_child; | 471 | else |
479 | if (node->right_child != NULL) | 472 | { |
480 | node->right_child->parent = NULL; | 473 | heap->root = node->right_child; |
474 | if (node->right_child != NULL) | ||
475 | node->right_child->parent = NULL; | ||
476 | } | ||
481 | } | 477 | } |
482 | } | ||
483 | else | 478 | else |
484 | { | ||
485 | if (node->parent->left_child == node) | ||
486 | node->parent->left_child = NULL; | ||
487 | else | ||
488 | node->parent->right_child = NULL; | ||
489 | if (node->left_child != NULL) | ||
490 | { | 479 | { |
491 | node->left_child->parent = NULL; | 480 | if (node->parent->left_child == node) |
492 | node->parent->tree_size -= (1 + node->left_child->tree_size); | 481 | node->parent->left_child = NULL; |
493 | insert_node (heap, node->parent, node->left_child); | 482 | else |
494 | } | 483 | node->parent->right_child = NULL; |
495 | if (node->right_child != NULL) | 484 | if (node->left_child != NULL) |
496 | { | 485 | { |
497 | node->right_child->parent = NULL; | 486 | node->left_child->parent = NULL; |
498 | node->parent->tree_size -= (1 + node->right_child->tree_size); | 487 | node->parent->tree_size -= (1 + node->left_child->tree_size); |
499 | insert_node (heap, node->parent, node->right_child); | 488 | insert_node(heap, node->parent, node->left_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 | } | ||
500 | } | 496 | } |
501 | } | ||
502 | node->parent = NULL; | 497 | node->parent = NULL; |
503 | node->left_child = NULL; | 498 | node->left_child = NULL; |
504 | node->right_child = NULL; | 499 | node->right_child = NULL; |
505 | GNUNET_assert (node->tree_size == 0); | 500 | GNUNET_assert(node->tree_size == 0); |
506 | CHECK (heap->root); | 501 | CHECK(heap->root); |
507 | } | 502 | } |
508 | 503 | ||
509 | 504 | ||
@@ -514,25 +509,25 @@ remove_node (struct GNUNET_CONTAINER_HeapNode *node) | |||
514 | * @return element data stored at the node | 509 | * @return element data stored at the node |
515 | */ | 510 | */ |
516 | void * | 511 | void * |
517 | GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node) | 512 | GNUNET_CONTAINER_heap_remove_node(struct GNUNET_CONTAINER_HeapNode *node) |
518 | { | 513 | { |
519 | void *ret; | 514 | void *ret; |
520 | struct GNUNET_CONTAINER_Heap *heap; | 515 | struct GNUNET_CONTAINER_Heap *heap; |
521 | 516 | ||
522 | heap = node->heap; | 517 | heap = node->heap; |
523 | CHECK (heap->root); | 518 | CHECK(heap->root); |
524 | if (heap->walk_pos == node) | 519 | if (heap->walk_pos == node) |
525 | (void) GNUNET_CONTAINER_heap_walk_get_next (heap); | 520 | (void)GNUNET_CONTAINER_heap_walk_get_next(heap); |
526 | remove_node (node); | 521 | remove_node(node); |
527 | heap->size--; | 522 | heap->size--; |
528 | ret = node->element; | 523 | ret = node->element; |
529 | if (heap->walk_pos == node) | 524 | if (heap->walk_pos == node) |
530 | heap->walk_pos = NULL; | 525 | heap->walk_pos = NULL; |
531 | GNUNET_free (node); | 526 | GNUNET_free(node); |
532 | #if EXTRA_CHECKS | 527 | #if EXTRA_CHECKS |
533 | CHECK (heap->root); | 528 | CHECK(heap->root); |
534 | GNUNET_assert (((heap->size == 0) && (heap->root == NULL)) || | 529 | GNUNET_assert(((heap->size == 0) && (heap->root == NULL)) || |
535 | (heap->size == heap->root->tree_size + 1)); | 530 | (heap->size == heap->root->tree_size + 1)); |
536 | #endif | 531 | #endif |
537 | return ret; | 532 | return ret; |
538 | } | 533 | } |
@@ -545,19 +540,19 @@ GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_HeapNode *node) | |||
545 | * @param new_cost new cost for the node | 540 | * @param new_cost new cost for the node |
546 | */ | 541 | */ |
547 | void | 542 | void |
548 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_HeapNode *node, | 543 | GNUNET_CONTAINER_heap_update_cost(struct GNUNET_CONTAINER_HeapNode *node, |
549 | GNUNET_CONTAINER_HeapCostType new_cost) | 544 | GNUNET_CONTAINER_HeapCostType new_cost) |
550 | { | 545 | { |
551 | struct GNUNET_CONTAINER_Heap *heap = node->heap; | 546 | struct GNUNET_CONTAINER_Heap *heap = node->heap; |
552 | 547 | ||
553 | remove_node (node); | 548 | remove_node(node); |
554 | node->cost = new_cost; | 549 | node->cost = new_cost; |
555 | if (NULL == heap->root) | 550 | if (NULL == heap->root) |
556 | heap->root = node; | 551 | heap->root = node; |
557 | else | 552 | else |
558 | insert_node (heap, | 553 | insert_node(heap, |
559 | heap->root, | 554 | heap->root, |
560 | node); | 555 | node); |
561 | } | 556 | } |
562 | 557 | ||
563 | 558 | ||