diff options
author | Christian Grothoff <christian@grothoff.org> | 2009-12-23 15:09:11 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2009-12-23 15:09:11 +0000 |
commit | 0acc583b6e411a5f1ebd6172458baaad992c456e (patch) | |
tree | 06f2acf19d889249e8c7256c8cbe07d0d3488349 /src/util/container_heap.c | |
parent | 8149805b0539d29420b9e2b5a60fc09b2d69b348 (diff) | |
download | gnunet-0acc583b6e411a5f1ebd6172458baaad992c456e.tar.gz gnunet-0acc583b6e411a5f1ebd6172458baaad992c456e.zip |
updating heap API and implementation
Diffstat (limited to 'src/util/container_heap.c')
-rw-r--r-- | src/util/container_heap.c | 856 |
1 files changed, 428 insertions, 428 deletions
diff --git a/src/util/container_heap.c b/src/util/container_heap.c index 9c6005beb..dbb391ac4 100644 --- a/src/util/container_heap.c +++ b/src/util/container_heap.c | |||
@@ -1,540 +1,540 @@ | |||
1 | /* | 1 | /* |
2 | This file is part of GNUnet. | 2 | This file is part of GNUnet. |
3 | (C) 2008 Christian Grothoff (and other contributing authors) | 3 | (C) 2008, 2009 Christian Grothoff (and other contributing authors) |
4 | 4 | ||
5 | GNUnet is free software; you can redistribute it and/or modify | 5 | GNUnet is free software; you can redistribute it and/or modify |
6 | it under the terms of the GNU General Public License as published | 6 | it under the terms of the GNU General Public License as published |
7 | by the Free Software Foundation; either version 2, or (at your | 7 | by the Free Software Foundation; either version 2, or (at your |
8 | option) any later version. | 8 | 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 | General Public License for more details. | 13 | General Public License for more details. |
14 | 14 | ||
15 | You should have received a copy of the GNU General Public License | 15 | You should have received a copy of the GNU General Public License |
16 | along with GNUnet; see the file COPYING. If not, write to the | 16 | along with GNUnet; see the file COPYING. If not, write to the |
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | 17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
18 | Boston, MA 02111-1307, USA. | 18 | Boston, MA 02111-1307, USA. |
19 | */ | 19 | */ |
20 | 20 | ||
21 | /** | 21 | /** |
22 | * @author Nathan Evans | ||
23 | * @file util/container_heap.c | 22 | * @file util/container_heap.c |
24 | * @brief Implementation of heap operations | 23 | * @brief Implementation of a heap |
24 | * @author Nathan Evans | ||
25 | * @author Christian Grothoff | ||
25 | */ | 26 | */ |
26 | 27 | ||
27 | #include "platform.h" | 28 | #include "platform.h" |
28 | #include "gnunet_protocols.h" | ||
29 | #include "gnunet_util_lib.h" | 29 | #include "gnunet_util_lib.h" |
30 | 30 | ||
31 | |||
32 | #define DEBUG 0 | ||
33 | |||
31 | /** | 34 | /** |
32 | * Generic heap node structure, contains pointer to parent | 35 | * Node in the heap. |
33 | * left child, right child, and actual neighbor. | ||
34 | */ | 36 | */ |
35 | struct GNUNET_CONTAINER_heap_node | 37 | struct GNUNET_CONTAINER_HeapNode |
36 | { | 38 | { |
37 | struct GNUNET_CONTAINER_heap_node *parent; | 39 | /** |
38 | 40 | * Parent node. | |
39 | struct GNUNET_CONTAINER_heap_node *left_child; | 41 | */ |
40 | 42 | struct GNUNET_CONTAINER_HeapNode *parent; | |
41 | struct GNUNET_CONTAINER_heap_node *right_child; | 43 | |
44 | /** | ||
45 | * Left child. | ||
46 | */ | ||
47 | struct GNUNET_CONTAINER_HeapNode *left_child; | ||
48 | |||
49 | /** | ||
50 | * Right child. | ||
51 | */ | ||
52 | struct GNUNET_CONTAINER_HeapNode *right_child; | ||
53 | |||
54 | /** | ||
55 | * Our element. | ||
56 | */ | ||
57 | void *element; | ||
42 | 58 | ||
43 | GNUNET_CONTAINER_HeapCost cost; | 59 | /** |
60 | * Cost for this element. | ||
61 | */ | ||
62 | GNUNET_CONTAINER_HeapCostType cost; | ||
44 | 63 | ||
45 | void *element; | 64 | /** |
65 | * Number of elements below this node in the heap | ||
66 | * (excluding this node itself). | ||
67 | */ | ||
68 | unsigned int tree_size; | ||
46 | 69 | ||
47 | }; | 70 | }; |
48 | 71 | ||
72 | /** | ||
73 | * Handle to a node in a heap. | ||
74 | */ | ||
49 | struct GNUNET_CONTAINER_Heap | 75 | struct GNUNET_CONTAINER_Heap |
50 | { | 76 | { |
51 | unsigned int size; | ||
52 | |||
53 | unsigned int max_size; | ||
54 | 77 | ||
55 | enum GNUNET_CONTAINER_HeapOrder type; | 78 | /** |
79 | * Root of the heap. | ||
80 | */ | ||
81 | struct GNUNET_CONTAINER_HeapNode *root; | ||
56 | 82 | ||
57 | struct GNUNET_CONTAINER_heap_node *root; | 83 | /** |
84 | * Current position of our random walk. | ||
85 | */ | ||
86 | struct GNUNET_CONTAINER_HeapNode *walk_pos; | ||
58 | 87 | ||
59 | struct GNUNET_CONTAINER_heap_node *traversal_pos; | 88 | /** |
89 | * Number of elements in the heap. | ||
90 | */ | ||
91 | unsigned int size; | ||
92 | |||
93 | /** | ||
94 | * How is the heap sorted? | ||
95 | */ | ||
96 | enum GNUNET_CONTAINER_HeapOrder order; | ||
60 | 97 | ||
61 | }; | 98 | }; |
62 | 99 | ||
63 | 100 | ||
101 | #if DEBUG | ||
64 | /** | 102 | /** |
65 | * Returns element stored at root of tree, doesn't effect anything | 103 | * Check if internal invariants hold for the given node. |
66 | * | 104 | * |
67 | * @param heap the heap | 105 | * @param node subtree to check |
68 | * @return NULL if the heap is empty | 106 | */ |
69 | */ | ||
70 | void * | ||
71 | GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap) | ||
72 | { | ||
73 | if ((heap == NULL) || (heap->root == NULL)) | ||
74 | return NULL; | ||
75 | |||
76 | return heap->root->element; | ||
77 | } | ||
78 | |||
79 | static int | ||
80 | next_power_of_2 (int v) | ||
81 | { | ||
82 | v |= v >> 1; | ||
83 | v |= v >> 2; | ||
84 | v |= v >> 4; | ||
85 | v |= v >> 8; | ||
86 | v |= v >> 16; | ||
87 | v++; | ||
88 | return v; | ||
89 | } | ||
90 | |||
91 | #if 0 | ||
92 | static void | 107 | static void |
93 | internal_print (struct GNUNET_CONTAINER_heap_node *root) | 108 | check (const struct GNUNET_CONTAINER_HeapNode *node) |
94 | { | 109 | { |
95 | fprintf (stdout, "%llu\n", (unsigned long long) root->cost); | 110 | if (NULL == node) |
96 | if (root->left_child != NULL) | 111 | return; |
97 | { | 112 | GNUNET_assert (node->tree_size == |
98 | fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost); | 113 | ( (node->left_child == NULL) ? 0 : 1 + node->left_child->tree_size) + |
99 | internal_print (root->left_child); | 114 | ( (node->right_child == NULL) ? 0 : 1 + node->right_child->tree_size) ); |
100 | } | 115 | check (node->left_child); |
101 | if (root->right_child != NULL) | 116 | check (node->right_child); |
102 | { | ||
103 | fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost); | ||
104 | internal_print (root->right_child); | ||
105 | } | ||
106 | } | 117 | } |
107 | 118 | ||
108 | static void | 119 | |
109 | printTree (struct GNUNET_CONTAINER_Heap *root) | 120 | #define CHECK(n) check(n) |
110 | { | 121 | #else |
111 | internal_print (root->root); | 122 | #define CHECK(n) do {} while (0) |
112 | } | ||
113 | #endif | 123 | #endif |
114 | 124 | ||
125 | |||
126 | /** | ||
127 | * Create a new heap. | ||
128 | * | ||
129 | * @param order how should the heap be sorted? | ||
130 | * @return handle to the heap | ||
131 | */ | ||
115 | struct GNUNET_CONTAINER_Heap * | 132 | struct GNUNET_CONTAINER_Heap * |
116 | GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type) | 133 | GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder order) |
117 | { | 134 | { |
118 | struct GNUNET_CONTAINER_Heap *heap; | 135 | struct GNUNET_CONTAINER_Heap *heap; |
119 | heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap)); | ||
120 | heap->max_size = -1; | ||
121 | heap->type = type; | ||
122 | heap->root = NULL; | ||
123 | heap->traversal_pos = NULL; | ||
124 | heap->size = 0; | ||
125 | 136 | ||
137 | heap = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_Heap)); | ||
138 | heap->order = order; | ||
126 | return heap; | 139 | return heap; |
127 | } | 140 | } |
128 | 141 | ||
142 | |||
143 | /** | ||
144 | * Destroys the heap. Only call on a heap that | ||
145 | * is already empty. | ||
146 | * | ||
147 | * @param heap heap to destroy | ||
148 | */ | ||
129 | void | 149 | void |
130 | GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) | 150 | GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap) |
131 | { | 151 | { |
132 | while (heap->size > 0) | 152 | GNUNET_break (heap->size == 0); |
133 | GNUNET_CONTAINER_heap_remove_root (heap); | ||
134 | GNUNET_free (heap); | 153 | GNUNET_free (heap); |
135 | } | 154 | } |
136 | 155 | ||
137 | static struct GNUNET_CONTAINER_heap_node * | 156 | |
138 | find_element (struct GNUNET_CONTAINER_heap_node *node, void *element) | 157 | /** |
158 | * Get element stored at root of heap. | ||
159 | * | ||
160 | * @param heap heap to inspect | ||
161 | * @return NULL if heap is empty | ||
162 | */ | ||
163 | void * | ||
164 | GNUNET_CONTAINER_heap_peek (const struct GNUNET_CONTAINER_Heap *heap) | ||
139 | { | 165 | { |
140 | struct GNUNET_CONTAINER_heap_node *ret; | 166 | if (heap->root == NULL) |
141 | ret = NULL; | ||
142 | if (node == NULL) | ||
143 | return NULL; | 167 | return NULL; |
144 | 168 | return heap->root->element; | |
145 | if (node->element == element) | ||
146 | return node; | ||
147 | |||
148 | if (node->left_child != NULL) | ||
149 | ret = find_element (node->left_child, element); | ||
150 | |||
151 | if ((ret == NULL) && (node->right_child != NULL)) | ||
152 | ret = find_element (node->right_child, element); | ||
153 | |||
154 | return ret; | ||
155 | } | 169 | } |
156 | 170 | ||
157 | static struct GNUNET_CONTAINER_heap_node * | ||
158 | getNextPos (struct GNUNET_CONTAINER_Heap *root) | ||
159 | { | ||
160 | struct GNUNET_CONTAINER_heap_node *ret; | ||
161 | struct GNUNET_CONTAINER_heap_node *parent; | ||
162 | int pos; | ||
163 | int i; | ||
164 | |||
165 | ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node)); | ||
166 | pos = root->size + 1; | ||
167 | ret->left_child = NULL; | ||
168 | ret->right_child = NULL; | ||
169 | |||
170 | if (0 == root->size) | ||
171 | { | ||
172 | ret->parent = NULL; | ||
173 | root->root = ret; | ||
174 | } | ||
175 | else | ||
176 | { | ||
177 | parent = root->root; | ||
178 | for (i = next_power_of_2 (pos) >> 2; i > 1; i >>= 1) | ||
179 | { | ||
180 | if (((pos / i) % 2) == 0) | ||
181 | parent = parent->left_child; | ||
182 | else | ||
183 | parent = parent->right_child; | ||
184 | } | ||
185 | |||
186 | ret->parent = parent; | ||
187 | if ((pos % 2) == 0) | ||
188 | parent->left_child = ret; | ||
189 | else | ||
190 | parent->right_child = ret; | ||
191 | |||
192 | } | ||
193 | |||
194 | return ret; | ||
195 | |||
196 | } | ||
197 | 171 | ||
198 | static struct GNUNET_CONTAINER_heap_node * | 172 | /** |
199 | getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos) | 173 | * Get the current size of the heap |
174 | * | ||
175 | * @param heap the heap to get the size of | ||
176 | * @return number of elements stored | ||
177 | */ | ||
178 | unsigned int | ||
179 | GNUNET_CONTAINER_heap_get_size (const struct GNUNET_CONTAINER_Heap *heap) | ||
200 | { | 180 | { |
201 | struct GNUNET_CONTAINER_heap_node *ret; | 181 | return heap->size; |
202 | unsigned int i; | 182 | } |
203 | |||
204 | ret = NULL; | ||
205 | if (pos > root->size) | ||
206 | { | ||
207 | return ret; | ||
208 | } | ||
209 | else | ||
210 | { | ||
211 | ret = root->root; | ||
212 | for (i = next_power_of_2 (pos) >> 2; i > 0; i >>= 1) | ||
213 | { | ||
214 | if (((pos / i) % 2) == 0) | ||
215 | ret = ret->left_child; | ||
216 | else | ||
217 | ret = ret->right_child; | ||
218 | } | ||
219 | } | ||
220 | 183 | ||
221 | return ret; | ||
222 | 184 | ||
185 | /** | ||
186 | * Iterate over the children of the given node. | ||
187 | * | ||
188 | * @param heap argument to give to iterator | ||
189 | * @param node node to iterate over | ||
190 | * @param iterator function to call on each node | ||
191 | * @param iterator_cls closure for iterator | ||
192 | * @return GNUNET_YES to continue to iterate | ||
193 | */ | ||
194 | static int | ||
195 | node_iterator (const struct GNUNET_CONTAINER_Heap *heap, | ||
196 | struct GNUNET_CONTAINER_HeapNode *node, | ||
197 | GNUNET_CONTAINER_HeapIterator iterator, | ||
198 | void *iterator_cls) | ||
199 | { | ||
200 | if (node == NULL) | ||
201 | return GNUNET_YES; | ||
202 | if (GNUNET_YES != node_iterator (heap, | ||
203 | node->left_child, | ||
204 | iterator, | ||
205 | iterator_cls)) | ||
206 | return GNUNET_NO; | ||
207 | if (GNUNET_YES != node_iterator (heap, | ||
208 | node->right_child, | ||
209 | iterator, | ||
210 | iterator_cls)) | ||
211 | return GNUNET_NO; | ||
212 | return iterator (iterator_cls, | ||
213 | node, | ||
214 | node->element, | ||
215 | node->cost); | ||
223 | } | 216 | } |
224 | 217 | ||
218 | |||
219 | /** | ||
220 | * Iterate over all entries in the heap. | ||
221 | * | ||
222 | * @param heap the heap | ||
223 | * @param iterator function to call on each entry | ||
224 | * @param iterator_cls closure for iterator | ||
225 | */ | ||
225 | void | 226 | void |
226 | swapNodes (struct GNUNET_CONTAINER_heap_node *first, | 227 | GNUNET_CONTAINER_heap_iterate (const struct GNUNET_CONTAINER_Heap *heap, |
227 | struct GNUNET_CONTAINER_heap_node *second, | 228 | GNUNET_CONTAINER_HeapIterator iterator, |
228 | struct GNUNET_CONTAINER_Heap *root) | 229 | void *iterator_cls) |
229 | { | 230 | { |
230 | void *temp_element; | 231 | (void) node_iterator (heap, heap->root, iterator, iterator_cls); |
231 | GNUNET_CONTAINER_HeapCost temp_cost; | ||
232 | |||
233 | temp_element = first->element; | ||
234 | temp_cost = first->cost; | ||
235 | first->element = second->element; | ||
236 | first->cost = second->cost; | ||
237 | second->element = temp_element; | ||
238 | second->cost = temp_cost; | ||
239 | |||
240 | return; | ||
241 | } | 232 | } |
242 | 233 | ||
243 | void | ||
244 | percolateHeap (struct GNUNET_CONTAINER_heap_node *pos, | ||
245 | struct GNUNET_CONTAINER_Heap *root) | ||
246 | { | ||
247 | 234 | ||
248 | while ((pos->parent != NULL) && | 235 | /** |
249 | (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | 236 | * Perform a random walk of the tree. The walk is biased |
250 | && (pos->parent->cost < pos->cost)) | 237 | * towards elements closer to the root of the tree (since |
251 | || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | 238 | * each walk starts at the root and ends at a random leaf). |
252 | && (pos->parent->cost > pos->cost)))) | 239 | * The heap internally tracks the current position of the |
253 | { | 240 | * walk. |
254 | swapNodes (pos, pos->parent, root); | 241 | * |
255 | pos = pos->parent; | 242 | * @param heap heap to walk |
256 | } | 243 | * @return data stored at the next random node in the walk; |
244 | * NULL if the tree is empty. | ||
245 | */ | ||
246 | void * | ||
247 | GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *heap) | ||
248 | { | ||
249 | struct GNUNET_CONTAINER_HeapNode *pos; | ||
250 | void *element; | ||
257 | 251 | ||
258 | return; | 252 | if (heap->root == NULL) |
253 | return NULL; | ||
254 | pos = heap->walk_pos; | ||
255 | if (pos == NULL) | ||
256 | pos = heap->root; | ||
257 | element = pos->element; | ||
258 | heap->walk_pos | ||
259 | = (0 == GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2)) | ||
260 | ? pos->right_child | ||
261 | : pos->left_child; | ||
262 | return element; | ||
259 | } | 263 | } |
260 | 264 | ||
261 | 265 | ||
262 | 266 | /** | |
263 | void | 267 | * Insert the given node 'node' into the subtree starting |
264 | percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos, | 268 | * at 'pos' (while keeping the tree somewhat balanced). |
265 | struct GNUNET_CONTAINER_Heap *root) | 269 | * |
270 | * @param pos existing tree | ||
271 | * @param node node to insert (which may be a subtree itself) | ||
272 | */ | ||
273 | static void | ||
274 | insert_node (struct GNUNET_CONTAINER_Heap *heap, | ||
275 | struct GNUNET_CONTAINER_HeapNode *pos, | ||
276 | struct GNUNET_CONTAINER_HeapNode *node) | ||
266 | { | 277 | { |
267 | struct GNUNET_CONTAINER_heap_node *switchNeighbor; | 278 | struct GNUNET_CONTAINER_HeapNode *parent; |
268 | 279 | ||
269 | switchNeighbor = pos; | 280 | GNUNET_assert (node->parent == NULL); |
270 | 281 | while ( (pos->cost < node->cost) ^ (heap->order == GNUNET_CONTAINER_HEAP_ORDER_MAX) ) | |
271 | if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)) | ||
272 | { | 282 | { |
273 | if ((pos->left_child != NULL) | 283 | /* node is descendent of pos */ |
274 | && (pos->left_child->cost > switchNeighbor->cost)) | 284 | pos->tree_size += (1 + node->tree_size); |
275 | { | 285 | if (pos->left_child == NULL) |
276 | switchNeighbor = pos->left_child; | 286 | { |
277 | } | 287 | pos->left_child = node; |
278 | 288 | node->parent = pos; | |
279 | if ((pos->right_child != NULL) | 289 | return; |
280 | && (pos->right_child->cost > switchNeighbor->cost)) | 290 | } |
281 | { | 291 | if (pos->right_child == NULL) |
282 | switchNeighbor = pos->right_child; | 292 | { |
283 | } | 293 | pos->right_child = node; |
294 | node->parent = pos; | ||
295 | return; | ||
296 | } | ||
297 | /* keep it balanced by descending into smaller subtree */ | ||
298 | if (pos->left_child->tree_size < pos->right_child->tree_size) | ||
299 | pos = pos->left_child; | ||
300 | else | ||
301 | pos = pos->right_child; | ||
284 | } | 302 | } |
285 | else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)) | 303 | /* make 'node' parent of 'pos' */ |
304 | parent = pos->parent; | ||
305 | pos->parent = NULL; | ||
306 | node->parent = parent; | ||
307 | if (NULL == parent) | ||
286 | { | 308 | { |
287 | if ((pos->left_child != NULL) | 309 | heap->root = node; |
288 | && (pos->left_child->cost < switchNeighbor->cost)) | ||
289 | { | ||
290 | switchNeighbor = pos->left_child; | ||
291 | } | ||
292 | |||
293 | if ((pos->right_child != NULL) | ||
294 | && (pos->right_child->cost < switchNeighbor->cost)) | ||
295 | { | ||
296 | switchNeighbor = pos->right_child; | ||
297 | } | ||
298 | } | 310 | } |
299 | 311 | else | |
300 | if (switchNeighbor != pos) | ||
301 | { | 312 | { |
302 | swapNodes (switchNeighbor, pos, root); | 313 | if (parent->left_child == pos) |
303 | percolateDownHeap (switchNeighbor, root); | 314 | parent->left_child = node; |
315 | else | ||
316 | parent->right_child = node; | ||
304 | } | 317 | } |
318 | /* insert 'pos' below 'node' */ | ||
319 | insert_node (heap, node, pos); | ||
320 | CHECK (pos); | ||
321 | } | ||
322 | |||
305 | 323 | ||
306 | return; | 324 | /** |
325 | * Inserts a new element into the heap. | ||
326 | * | ||
327 | * @param heap heap to modify | ||
328 | * @param element element to insert | ||
329 | * @param cost cost for the element | ||
330 | * @return node for the new element | ||
331 | */ | ||
332 | struct GNUNET_CONTAINER_HeapNode * | ||
333 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *heap, | ||
334 | void *element, | ||
335 | GNUNET_CONTAINER_HeapCostType cost) | ||
336 | { | ||
337 | struct GNUNET_CONTAINER_HeapNode *node; | ||
338 | |||
339 | node = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_HeapNode)); | ||
340 | node->element = element; | ||
341 | node->cost = cost; | ||
342 | heap->size++; | ||
343 | if (NULL == heap->root) | ||
344 | heap->root = node; | ||
345 | else | ||
346 | insert_node (heap, heap->root, node); | ||
347 | GNUNET_assert (heap->size == heap->root->tree_size + 1); | ||
348 | CHECK (heap->root); | ||
349 | return node; | ||
307 | } | 350 | } |
308 | 351 | ||
352 | |||
353 | /** | ||
354 | * Remove root of the heap. | ||
355 | * | ||
356 | * @param heap heap to modify | ||
357 | * @return element data stored at the root node, NULL if heap is empty | ||
358 | */ | ||
309 | void * | 359 | void * |
310 | GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root, | 360 | GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *heap) |
311 | void *element) | ||
312 | { | 361 | { |
313 | void *ret; | 362 | void *ret; |
314 | struct GNUNET_CONTAINER_heap_node *del_node; | 363 | struct GNUNET_CONTAINER_HeapNode *root; |
315 | struct GNUNET_CONTAINER_heap_node *last; | ||
316 | GNUNET_CONTAINER_HeapCost old_cost; | ||
317 | 364 | ||
318 | del_node = NULL; | 365 | if (NULL == (root = heap->root)) |
319 | del_node = find_element (root->root, element); | ||
320 | |||
321 | if (del_node == NULL) | ||
322 | return NULL; | 366 | return NULL; |
323 | else if (del_node == root->root) | 367 | heap->size--; |
324 | return GNUNET_CONTAINER_heap_remove_root (root); | 368 | ret = root->element; |
325 | 369 | if (root->left_child == NULL) | |
326 | ret = del_node->element; | ||
327 | last = getPos (root, root->size); | ||
328 | |||
329 | root->size--; | ||
330 | |||
331 | old_cost = del_node->cost; | ||
332 | del_node->element = last->element; | ||
333 | del_node->cost = last->cost; | ||
334 | |||
335 | if (last->parent->left_child == last) | ||
336 | last->parent->left_child = NULL; | ||
337 | if (last->parent->right_child == last) | ||
338 | last->parent->right_child = NULL; | ||
339 | |||
340 | if (root->traversal_pos == last) | ||
341 | { | 370 | { |
342 | root->traversal_pos = root->root; | 371 | heap->root = root->right_child; |
372 | if (root->right_child != NULL) | ||
373 | root->right_child->parent = NULL; | ||
343 | } | 374 | } |
344 | 375 | else if (root->right_child == NULL) | |
345 | if (last == del_node) | ||
346 | { | ||
347 | GNUNET_free (last); | ||
348 | return ret; | ||
349 | } | ||
350 | GNUNET_free (last); | ||
351 | |||
352 | |||
353 | if (del_node->cost > old_cost) | ||
354 | { | 376 | { |
355 | if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | 377 | heap->root = root->left_child; |
356 | percolateHeap (del_node, root); | 378 | if (root->left_child != NULL) |
357 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | 379 | root->left_child->parent = NULL; |
358 | percolateDownHeap (del_node, root); | ||
359 | } | 380 | } |
360 | else if (del_node->cost < old_cost) | 381 | else |
361 | { | 382 | { |
362 | if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | 383 | root->left_child->parent = NULL; |
363 | percolateDownHeap (del_node, root); | 384 | root->right_child->parent = NULL; |
364 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | 385 | heap->root = root->left_child; |
365 | percolateHeap (del_node, root); | 386 | insert_node (heap, heap->root, root->right_child); |
366 | } | 387 | } |
367 | 388 | GNUNET_free (root); | |
389 | #if DEBUG | ||
390 | GNUNET_assert (( (heap->size == 0) && | ||
391 | (heap->root == NULL) ) || | ||
392 | (heap->size == heap->root->tree_size + 1) ); | ||
393 | CHECK (heap->root); | ||
394 | #endif | ||
368 | return ret; | 395 | return ret; |
369 | } | 396 | } |
370 | 397 | ||
371 | int | 398 | |
372 | GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root, | 399 | /** |
373 | void *element, GNUNET_CONTAINER_HeapCost cost) | 400 | * Remove the given node 'node' from the tree and update |
401 | * the 'tree_size' fields accordingly. Preserves the | ||
402 | * children of 'node' and does NOT change the overall | ||
403 | * 'size' field of the tree. | ||
404 | */ | ||
405 | static void | ||
406 | remove_node (struct GNUNET_CONTAINER_Heap *heap, | ||
407 | struct GNUNET_CONTAINER_HeapNode *node) | ||
374 | { | 408 | { |
375 | struct GNUNET_CONTAINER_heap_node *new_pos; | 409 | struct GNUNET_CONTAINER_HeapNode *ancestor; |
376 | int ret; | ||
377 | ret = GNUNET_YES; | ||
378 | 410 | ||
379 | if (root->max_size > root->size) | 411 | /* update 'size' of the ancestors */ |
380 | { | 412 | ancestor = node; |
381 | new_pos = getNextPos (root); | 413 | while (NULL != (ancestor = ancestor->parent)) |
382 | new_pos->element = element; | 414 | ancestor->tree_size--; |
383 | new_pos->cost = cost; | 415 | |
384 | root->size++; | 416 | /* update 'size' of node itself */ |
417 | if (node->left_child != NULL) | ||
418 | node->tree_size -= (1 + node->left_child->tree_size); | ||
419 | if (node->right_child != NULL) | ||
420 | node->tree_size -= (1 + node->right_child->tree_size); | ||
385 | 421 | ||
386 | percolateHeap (new_pos, root); | 422 | /* unlink 'node' itself and insert children in its place */ |
423 | if (node->parent == NULL) | ||
424 | { | ||
425 | if (node->left_child != NULL) | ||
426 | { | ||
427 | heap->root = node->left_child; | ||
428 | node->left_child->parent = NULL; | ||
429 | if (node->right_child != NULL) | ||
430 | { | ||
431 | node->right_child->parent = NULL; | ||
432 | insert_node (heap, heap->root, node->right_child); | ||
433 | } | ||
434 | } | ||
435 | else | ||
436 | { | ||
437 | heap->root = node->right_child; | ||
438 | if (node->right_child != NULL) | ||
439 | node->right_child->parent = NULL; | ||
440 | } | ||
387 | } | 441 | } |
388 | else | 442 | else |
389 | { | 443 | { |
390 | ret = GNUNET_NO; | 444 | if (node->parent->left_child == node) |
445 | node->parent->left_child = NULL; | ||
446 | else | ||
447 | node->parent->right_child = NULL; | ||
448 | if (node->left_child != NULL) | ||
449 | { | ||
450 | node->left_child->parent = NULL; | ||
451 | node->parent->tree_size -= (1 + node->left_child->tree_size); | ||
452 | insert_node (heap, node->parent, node->left_child); | ||
453 | } | ||
454 | if (node->right_child != NULL) | ||
455 | { | ||
456 | node->right_child->parent = NULL; | ||
457 | node->parent->tree_size -= (1 + node->right_child->tree_size); | ||
458 | insert_node (heap, node->parent, node->right_child); | ||
459 | } | ||
391 | } | 460 | } |
392 | 461 | node->parent = NULL; | |
393 | return ret; | 462 | node->left_child = NULL; |
463 | node->right_child = NULL; | ||
464 | GNUNET_assert (node->tree_size == 0); | ||
465 | CHECK (heap->root); | ||
394 | } | 466 | } |
395 | 467 | ||
468 | |||
469 | /** | ||
470 | * Removes a node from the heap. | ||
471 | * | ||
472 | * @param heap heap to modify | ||
473 | * @param node node to remove | ||
474 | * @return element data stored at the node | ||
475 | */ | ||
396 | void * | 476 | void * |
397 | GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root) | 477 | GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *heap, |
478 | struct GNUNET_CONTAINER_HeapNode *node) | ||
398 | { | 479 | { |
399 | void *ret; | 480 | void *ret; |
400 | struct GNUNET_CONTAINER_heap_node *root_node; | 481 | |
401 | struct GNUNET_CONTAINER_heap_node *last; | 482 | CHECK (heap->root); |
402 | 483 | if (heap->walk_pos == node) | |
403 | if ((root == NULL) || (root->size == 0) || (root->root == NULL)) | 484 | (void) GNUNET_CONTAINER_heap_walk_get_next (heap); |
404 | { | 485 | remove_node (heap, node); |
405 | GNUNET_break (0); | 486 | heap->size--; |
406 | return NULL; | 487 | ret = node->element; |
407 | } | 488 | if (heap->walk_pos == node) |
408 | 489 | heap->walk_pos = NULL; | |
409 | root_node = root->root; | 490 | GNUNET_free (node); |
410 | ret = root_node->element; | 491 | #if DEBUG |
411 | last = getPos (root, root->size); | 492 | CHECK (heap->root); |
412 | 493 | GNUNET_assert (( (heap->size == 0) && | |
413 | if ((root_node == last) && (root->size == 1)) | 494 | (heap->root == NULL) ) || |
414 | { | 495 | (heap->size == heap->root->tree_size + 1) ); |
415 | /* We are removing the last node in the heap! */ | 496 | #endif |
416 | GNUNET_free (last); | ||
417 | root->root = NULL; | ||
418 | root->traversal_pos = NULL; | ||
419 | GNUNET_assert (0 == --root->size); | ||
420 | return ret; | ||
421 | } | ||
422 | |||
423 | if (last->parent->left_child == last) | ||
424 | last->parent->left_child = NULL; | ||
425 | else if (last->parent->right_child == last) | ||
426 | last->parent->right_child = NULL; | ||
427 | |||
428 | root_node->element = last->element; | ||
429 | root_node->cost = last->cost; | ||
430 | |||
431 | if (root->traversal_pos == last) | ||
432 | root->traversal_pos = root->root; | ||
433 | GNUNET_free (last); | ||
434 | root->size--; | ||
435 | percolateDownHeap (root->root, root); | ||
436 | return ret; | 497 | return ret; |
437 | } | 498 | } |
438 | 499 | ||
439 | static int | ||
440 | updatedCost (struct GNUNET_CONTAINER_Heap *root, | ||
441 | struct GNUNET_CONTAINER_heap_node *node) | ||
442 | { | ||
443 | struct GNUNET_CONTAINER_heap_node *parent; | ||
444 | |||
445 | if (node == NULL) | ||
446 | return GNUNET_SYSERR; | ||
447 | |||
448 | parent = node->parent; | ||
449 | |||
450 | if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL) | ||
451 | && (node->cost > parent->cost)) | ||
452 | percolateHeap (node, root); | ||
453 | else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL) | ||
454 | && (node->cost < parent->cost)) | ||
455 | percolateHeap (node, root); | ||
456 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) | ||
457 | percolateDownHeap (node, root); | ||
458 | else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) | ||
459 | percolateDownHeap (node, root); | ||
460 | |||
461 | return GNUNET_YES; | ||
462 | } | ||
463 | |||
464 | |||
465 | int | ||
466 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root, | ||
467 | void *element, | ||
468 | GNUNET_CONTAINER_HeapCost new_cost) | ||
469 | { | ||
470 | struct GNUNET_CONTAINER_heap_node *node; | ||
471 | int ret = GNUNET_YES; | ||
472 | node = find_element (root->root, element); | ||
473 | if (node == NULL) | ||
474 | return GNUNET_NO; | ||
475 | |||
476 | node->cost = new_cost; | ||
477 | ret = updatedCost (root, node); | ||
478 | return ret; | ||
479 | } | ||
480 | 500 | ||
501 | /** | ||
502 | * Updates the cost of any node in the tree | ||
503 | * | ||
504 | * @param heap heap to modify | ||
505 | * @param node node for which the cost is to be changed | ||
506 | * @param new_cost new cost for the node | ||
507 | */ | ||
481 | void | 508 | void |
482 | internal_iterator (struct GNUNET_CONTAINER_Heap *root, | 509 | GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *heap, |
483 | struct GNUNET_CONTAINER_heap_node *node, | 510 | struct GNUNET_CONTAINER_HeapNode *node, |
484 | GNUNET_CONTAINER_HeapIterator iterator, void *cls) | 511 | GNUNET_CONTAINER_HeapCostType new_cost) |
485 | { | ||
486 | if (node == NULL) | ||
487 | return; | ||
488 | internal_iterator (root, node->left_child, iterator, cls); | ||
489 | internal_iterator (root, node->right_child, iterator, cls); | ||
490 | iterator (cls, node->element, node->cost); | ||
491 | } | ||
492 | |||
493 | int | ||
494 | GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap, | ||
495 | GNUNET_CONTAINER_HeapIterator iterator, | ||
496 | void *cls) | ||
497 | { | 512 | { |
498 | internal_iterator (heap, heap->root, iterator, cls); | 513 | #if DEBUG |
499 | return GNUNET_OK; | 514 | GNUNET_assert ( ( (heap->size == 0) && |
500 | } | 515 | (heap->root == NULL) ) || |
501 | 516 | (heap->size == heap->root->tree_size + 1) ); | |
502 | void * | 517 | CHECK (heap->root); |
503 | GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root) | 518 | #endif |
504 | { | 519 | remove_node (heap, node); |
505 | unsigned int choice; | 520 | #if DEBUG |
506 | void *element; | 521 | CHECK (heap->root); |
507 | 522 | GNUNET_assert ( ( (heap->size == 1) && | |
508 | if ((root->traversal_pos == NULL) && (root->root != NULL)) | 523 | (heap->root == NULL) ) || |
509 | { | 524 | (heap->size == heap->root->tree_size + 2) ); |
510 | root->traversal_pos = root->root; | 525 | #endif |
511 | } | 526 | node->cost = new_cost; |
512 | 527 | if (heap->root == NULL) | |
513 | if (root->traversal_pos == NULL) | 528 | heap->root = node; |
514 | return NULL; | 529 | else |
515 | 530 | insert_node (heap, heap->root, node); | |
516 | element = root->traversal_pos->element; | 531 | #if DEBUG |
517 | 532 | CHECK (heap->root); | |
518 | choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2); | 533 | GNUNET_assert ( ( (heap->size == 0) && |
519 | 534 | (heap->root == NULL) ) || | |
520 | switch (choice) | 535 | (heap->size == heap->root->tree_size + 1) ); |
521 | { | 536 | #endif |
522 | case 1: | ||
523 | root->traversal_pos = root->traversal_pos->right_child; | ||
524 | break; | ||
525 | case 0: | ||
526 | root->traversal_pos = root->traversal_pos->left_child; | ||
527 | break; | ||
528 | } | ||
529 | |||
530 | return element; | ||
531 | |||
532 | } | 537 | } |
533 | 538 | ||
534 | unsigned int | ||
535 | GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap) | ||
536 | { | ||
537 | return heap->size; | ||
538 | } | ||
539 | 539 | ||
540 | /* end of heap.c */ | 540 | /* end of heap.c */ |