2 This file is part of GNUnet.
3 (C) 2008 Christian Grothoff (and other contributing authors)
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
7 by the Free Software Foundation; either version 2, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
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
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @author Nathan Evans
23 * @file util/container_heap.c
24 * @brief Implementation of heap operations
28 #include "gnunet_protocols.h"
29 #include "gnunet_util.h"
30 #include "gnunet_util_containers.h"
33 * Struct that is stored in hashmap, pointers to
34 * locations in min_heap and max_heap.
36 struct GNUNET_CONTAINER_heap_info
38 struct GNUNET_CONTAINER_heap_node *min_loc;
40 struct GNUNET_CONTAINER_heap_node *max_loc;
45 * Generic heap node structure, contains pointer to parent
46 * left child, right child, and actual neighbor.
48 struct GNUNET_CONTAINER_heap_node
50 struct GNUNET_CONTAINER_heap_node *parent;
52 struct GNUNET_CONTAINER_heap_node *left_child;
54 struct GNUNET_CONTAINER_heap_node *right_child;
56 GNUNET_CONTAINER_HeapCost cost;
62 struct GNUNET_CONTAINER_Heap
66 unsigned int max_size;
70 struct GNUNET_CONTAINER_heap_node *root;
72 struct GNUNET_CONTAINER_heap_node *traversal_pos;
77 internal_print (struct GNUNET_CONTAINER_heap_node *root)
79 fprintf (stdout, "%d\n", root->cost);
80 if (root->left_child != NULL)
82 fprintf (stdout, "LEFT of %d\n", root->cost);
83 internal_print (root->left_child);
85 if (root->right_child != NULL)
87 fprintf (stdout, "RIGHT of %d\n", root->cost);
88 internal_print (root->right_child);
93 printTree (struct GNUNET_CONTAINER_Heap *root)
95 internal_print (root->root);
98 struct GNUNET_CONTAINER_Heap *
99 GNUNET_CONTAINER_heap_create (enum type)
101 struct GNUNET_CONTAINER_Heap *heap;
102 heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
106 heap->traversal_pos = NULL;
113 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
116 while (heap->size > 0)
118 unused = GNUNET_CONTAINER_heap_remove_root (heap);
125 struct GNUNET_CONTAINER_heap_node *
126 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
128 struct GNUNET_CONTAINER_heap_node *ret;
130 if ((node != NULL) && (node->element == element))
135 if ((ret == NULL) && (node->left_child != NULL))
137 ret = find_element (node->left_child, element);
140 if ((ret == NULL) && (node->right_child != NULL))
142 ret = find_element (node->right_child, element);
148 static struct GNUNET_CONTAINER_heap_node *
149 getNextPos (struct GNUNET_CONTAINER_Heap *root)
151 struct GNUNET_CONTAINER_heap_node *ret;
152 struct GNUNET_CONTAINER_heap_node *parent;
157 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
158 pos = root->size + 1;
159 depth = (int) log2 (pos);
160 ret->left_child = NULL;
161 ret->right_child = NULL;
171 for (i = depth; i > 1; i--)
173 if (((pos / (1 << (i - 1))) % 2) == 0)
174 parent = parent->left_child;
176 parent = parent->right_child;
179 ret->parent = parent;
181 parent->left_child = ret;
183 parent->right_child = ret;
191 static struct GNUNET_CONTAINER_heap_node *
192 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
194 struct GNUNET_CONTAINER_heap_node *ret;
199 depth = (int) log2 (pos);
201 if (pos > root->size)
208 for (i = depth; i > 0; i--)
210 if (((pos / (1 << (i - 1))) % 2) == 0)
211 ret = ret->left_child;
213 ret = ret->right_child;
222 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
223 struct GNUNET_CONTAINER_heap_node *second,
224 struct GNUNET_CONTAINER_Heap *root)
227 GNUNET_CONTAINER_HeapCost temp_cost;
229 temp_element = first->element;
230 temp_cost = first->cost;
231 first->element = second->element;
232 first->cost = second->cost;
233 second->element = temp_element;
234 second->cost = temp_cost;
237 * I still worry that there is some good reason for
238 * elements being location aware... but it eludes me
240 if ((root->type == GNUNET_DV_MAX_HEAP))
242 first->neighbor->max_loc = first;
243 second->neighbor->max_loc = second;
245 else if ((root->type == GNUNET_DV_MIN_HEAP))
247 first->neighbor->min_loc = first;
248 second->neighbor->min_loc = second;
255 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
256 struct GNUNET_CONTAINER_Heap *root)
259 while ((pos->parent != NULL) &&
260 (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
261 && (pos->parent->cost < pos->cost))
262 || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
263 && (pos->parent->cost > pos->cost))))
265 swapNodes (pos, pos->parent, root);
275 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
276 struct GNUNET_CONTAINER_Heap *root)
278 struct GNUNET_CONTAINER_heap_node *switchNeighbor;
280 switchNeighbor = pos;
282 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
284 if ((pos->left_child != NULL)
285 && (pos->left_child->cost > switchNeighbor->cost))
287 switchNeighbor = pos->left_child;
290 if ((pos->right_child != NULL)
291 && (pos->right_child->cost > switchNeighbor->cost))
293 switchNeighbor = pos->right_child;
296 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
298 if ((pos->left_child != NULL)
299 && (pos->left_child->cost < switchNeighbor->cost))
301 switchNeighbor = pos->left_child;
304 if ((pos->right_child != NULL)
305 && (pos->right_child->cost < switchNeighbor->cost))
307 switchNeighbor = pos->right_child;
311 if (switchNeighbor != pos)
313 swapNodes (switchNeighbor, pos, root);
314 percolateDownHeap (switchNeighbor, root);
321 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
325 struct GNUNET_CONTAINER_heap_node *del_node;
326 struct GNUNET_CONTAINER_heap_node *last;
327 GNUNET_CONTAINER_HeapCost old_cost;
330 del_node = find_element (root->root, element);
332 if (del_node == NULL)
334 else if (del_node == root->root)
335 return GNUNET_CONTAINER_heap_remove_root (root);
337 ret = del_node->element;
338 last = getPos (root, root->size);
340 old_cost = del_node->cost;
341 del_node->element = last->element;
342 del_node->cost = last->cost;
344 if (last->parent->left_child == last)
345 last->parent->left_child = NULL;
346 if (last->parent->right_child == last)
347 last->parent->right_child = NULL;
349 if (root->traversal_pos == last)
351 root->traversal_pos = root->root;
356 if (del_node->cost > old_cost)
358 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
359 percolateHeap (del_node, root);
360 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
361 percolateDownHeap (del_node, root);
363 else if (del_node->cost < old_cost)
365 if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
366 percolateDownHeap (del_node, root);
367 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
368 percolateHeap (del_node, root);
375 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
376 void *element, GNUNET_CONTAINER_HeapCost cost)
378 struct GNUNET_CONTAINER_heap_node *new_pos;
382 if (root->max_size > root->size)
384 new_pos = getNextPos (root);
385 new_pos->element = element;
386 new_pos->cost = cost;
388 /*We no longer can tolerate pointers between heaps :( */
389 /*if (root->type == GNUNET_DV_MIN_HEAP)
390 new_pos->neighbor->min_loc = new_pos;
391 else if (root->type == GNUNET_DV_MAX_HEAP)
392 new_pos->neighbor->max_loc = new_pos; */
394 percolateHeap (new_pos, root);
405 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
408 struct GNUNET_CONTAINER_heap_node *root_node;
409 struct GNUNET_CONTAINER_heap_node *last;
411 root_node = root->root;
412 ret = root_node->element;
413 last = getPos (root, root->size);
415 if ((root_node == last) && (root->size == 1))
417 /* We are removing the last node in the heap! */
419 root->traversal_pos = NULL;
424 if (last->parent->left_child == last)
425 last->parent->left_child = NULL;
426 else if (last->parent->right_child == last)
427 last->parent->right_child = NULL;
429 root_node->element = last->element;
430 root_node->cost = last->cost;
432 if (root->traversal_pos == last)
434 root->traversal_pos = root->root;
439 percolateDownHeap (root->root, root);
444 updatedCost (struct GNUNET_CONTAINER_Heap *root,
445 struct GNUNET_CONTAINER_heap_node *node)
447 struct GNUNET_CONTAINER_heap_node *parent;
450 return GNUNET_SYSERR;
452 parent = node->parent;
454 if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
455 && (node->cost > parent->cost))
456 percolateHeap (node, root);
457 else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
458 && (node->cost < parent->cost))
459 percolateHeap (node, root);
460 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
461 percolateDownHeap (node, root);
462 else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
463 percolateDownHeap (node, root);
470 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
472 GNUNET_CONTAINER_HeapCost new_cost)
474 struct GNUNET_CONTAINER_heap_node *node;
475 int ret = GNUNET_YES;
476 node = find_element (root->root, element);
480 node->cost = new_cost;
481 ret = updatedCost (root, node);
486 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
487 struct GNUNET_CONTAINER_heap_node *node,
488 GNUNET_CONTAINER_HeapIterator iterator, void *cls)
492 internal_iterator (root, node->left_child, iterator, cls);
493 internal_iterator (root, node->right_child, iterator, cls);
494 iterator (node->element, node->cost, root, cls);
498 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
499 GNUNET_CONTAINER_HeapIterator iterator,
502 internal_iterator (heap, heap->root, iterator, cls);
507 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
512 if ((root->traversal_pos == NULL) && (root->root != NULL))
514 root->traversal_pos = root->root;
517 if (root->traversal_pos == NULL)
520 element = root->traversal_pos->element;
522 choice = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2);
527 root->traversal_pos = root->traversal_pos->right_child;
530 root->traversal_pos = root->traversal_pos->left_child;
539 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)