src/util/container_heap.c

   1 /*
   2  This file is part of GNUnet.
   3  (C) 2008 Christian Grothoff (and other contributing authors)
   4
   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.
   9
  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.
  14
  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.
  19  */
  20
  21 /**
  22  * @author Nathan Evans
  23  * @file util/container_heap.c
  24  * @brief Implementation of heap operations
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_protocols.h"
  29 #include "gnunet_util_lib.h"
  30
  31 /*
  32  * Struct that is stored in hashmap, pointers to
  33  * locations in min_heap and max_heap.
  34  */
  35 struct GNUNET_CONTAINER_heap_info
  36 {
  37   struct GNUNET_CONTAINER_heap_node *min_loc;
  38
  39   struct GNUNET_CONTAINER_heap_node *max_loc;
  40
  41 };
  42
  43 /*
  44  * Generic heap node structure, contains pointer to parent
  45  * left child, right child, and actual neighbor.
  46  */
  47 struct GNUNET_CONTAINER_heap_node
  48 {
  49   struct GNUNET_CONTAINER_heap_node *parent;
  50
  51   struct GNUNET_CONTAINER_heap_node *left_child;
  52
  53   struct GNUNET_CONTAINER_heap_node *right_child;
  54
  55   GNUNET_CONTAINER_HeapCost cost;
  56
  57   void *element;
  58
  59 };
  60
  61 struct GNUNET_CONTAINER_Heap
  62 {
  63   unsigned int size;
  64
  65   unsigned int max_size;
  66
  67   enum GNUNET_CONTAINER_HeapOrder type;
  68
  69   struct GNUNET_CONTAINER_heap_node *root;
  70
  71   struct GNUNET_CONTAINER_heap_node *traversal_pos;
  72
  73 };
  74
  75
  76 /**
  77  * Returns element stored at root of tree, doesn't effect anything
  78  *
  79  * @param heap the heap
  80  * @return NULL if the heap is empty
  81  */
  82 void *GNUNET_CONTAINER_heap_peek (struct GNUNET_CONTAINER_Heap *heap)
  83 {
  84   return heap->root;
  85 }
  86
  87
  88 void
  89 internal_print (struct GNUNET_CONTAINER_heap_node *root)
  90 {
  91   fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
  92   if (root->left_child != NULL)
  93     {
  94       fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
  95       internal_print (root->left_child);
  96     }
  97   if (root->right_child != NULL)
  98     {
  99       fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
 100       internal_print (root->right_child);
 101     }
 102 }
 103
 104 void
 105 printTree (struct GNUNET_CONTAINER_Heap *root)
 106 {
 107   internal_print (root->root);
 108 }
 109
 110 struct GNUNET_CONTAINER_Heap *
 111 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
 112 {
 113   struct GNUNET_CONTAINER_Heap *heap;
 114   heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
 115   heap->max_size = -1;
 116   heap->type = type;
 117   heap->root = NULL;
 118   heap->traversal_pos = NULL;
 119   heap->size = 0;
 120
 121   return heap;
 122 }
 123
 124 void
 125 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
 126 {
 127   void *unused;
 128   while (heap->size > 0)
 129     {
 130       unused = GNUNET_CONTAINER_heap_remove_root (heap);
 131     }
 132
 133   GNUNET_free (heap);
 134   return;
 135 }
 136
 137 struct GNUNET_CONTAINER_heap_node *
 138 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
 139 {
 140   struct GNUNET_CONTAINER_heap_node *ret;
 141   ret = NULL;
 142   if ((node != NULL) && (node->element == element))
 143     {
 144       ret = node;
 145     }
 146
 147   if ((ret == NULL) && (node->left_child != NULL))
 148     {
 149       ret = find_element (node->left_child, element);
 150     }
 151
 152   if ((ret == NULL) && (node->right_child != NULL))
 153     {
 154       ret = find_element (node->right_child, element);
 155     }
 156
 157   return ret;
 158 }
 159
 160 static struct GNUNET_CONTAINER_heap_node *
 161 getNextPos (struct GNUNET_CONTAINER_Heap *root)
 162 {
 163   struct GNUNET_CONTAINER_heap_node *ret;
 164   struct GNUNET_CONTAINER_heap_node *parent;
 165   int pos;
 166   int depth;
 167   int i;
 168
 169   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
 170   pos = root->size + 1;
 171   depth = (int) log2 (pos);
 172   ret->left_child = NULL;
 173   ret->right_child = NULL;
 174
 175   if (depth == 0)
 176     {
 177       ret->parent = NULL;
 178       root->root = ret;
 179     }
 180   else
 181     {
 182       parent = root->root;
 183       for (i = depth; i > 1; i--)
 184         {
 185           if (((pos / (1 << (i - 1))) % 2) == 0)
 186             parent = parent->left_child;
 187           else
 188             parent = parent->right_child;
 189         }
 190
 191       ret->parent = parent;
 192       if ((pos % 2) == 0)
 193         parent->left_child = ret;
 194       else
 195         parent->right_child = ret;
 196
 197     }
 198
 199   return ret;
 200
 201 }
 202
 203 static struct GNUNET_CONTAINER_heap_node *
 204 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
 205 {
 206   struct GNUNET_CONTAINER_heap_node *ret;
 207
 208   int depth;
 209   int i;
 210
 211   depth = (int) log2 (pos);
 212   ret = NULL;
 213   if (pos > root->size)
 214     {
 215       return ret;
 216     }
 217   else
 218     {
 219       ret = root->root;
 220       for (i = depth; i > 0; i--)
 221         {
 222           if (((pos / (1 << (i - 1))) % 2) == 0)
 223             ret = ret->left_child;
 224           else
 225             ret = ret->right_child;
 226         }
 227     }
 228
 229   return ret;
 230
 231 }
 232
 233 void
 234 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
 235            struct GNUNET_CONTAINER_heap_node *second,
 236            struct GNUNET_CONTAINER_Heap *root)
 237 {
 238   void *temp_element;
 239   GNUNET_CONTAINER_HeapCost temp_cost;
 240
 241   temp_element = first->element;
 242   temp_cost = first->cost;
 243   first->element = second->element;
 244   first->cost = second->cost;
 245   second->element = temp_element;
 246   second->cost = temp_cost;
 247
 248 /*
 249  * I still worry that there is some good reason for
 250  * elements being location aware... but it eludes me
 251  * for the moment...
 252   if ((root->type == GNUNET_DV_MAX_HEAP))
 253     {
 254       first->neighbor->max_loc = first;
 255       second->neighbor->max_loc = second;
 256     }
 257   else if ((root->type == GNUNET_DV_MIN_HEAP))
 258     {
 259       first->neighbor->min_loc = first;
 260       second->neighbor->min_loc = second;
 261     }
 262 */
 263   return;
 264 }
 265
 266 void
 267 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
 268                struct GNUNET_CONTAINER_Heap *root)
 269 {
 270
 271   while ((pos->parent != NULL) &&
 272          (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 273            && (pos->parent->cost < pos->cost))
 274           || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 275               && (pos->parent->cost > pos->cost))))
 276     {
 277       swapNodes (pos, pos->parent, root);
 278       pos = pos->parent;
 279     }
 280
 281   return;
 282 }
 283
 284
 285
 286 void
 287 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
 288                    struct GNUNET_CONTAINER_Heap *root)
 289 {
 290   struct GNUNET_CONTAINER_heap_node *switchNeighbor;
 291
 292   switchNeighbor = pos;
 293
 294   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
 295     {
 296       if ((pos->left_child != NULL)
 297           && (pos->left_child->cost > switchNeighbor->cost))
 298         {
 299           switchNeighbor = pos->left_child;
 300         }
 301
 302       if ((pos->right_child != NULL)
 303           && (pos->right_child->cost > switchNeighbor->cost))
 304         {
 305           switchNeighbor = pos->right_child;
 306         }
 307     }
 308   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
 309     {
 310       if ((pos->left_child != NULL)
 311           && (pos->left_child->cost < switchNeighbor->cost))
 312         {
 313           switchNeighbor = pos->left_child;
 314         }
 315
 316       if ((pos->right_child != NULL)
 317           && (pos->right_child->cost < switchNeighbor->cost))
 318         {
 319           switchNeighbor = pos->right_child;
 320         }
 321     }
 322
 323   if (switchNeighbor != pos)
 324     {
 325       swapNodes (switchNeighbor, pos, root);
 326       percolateDownHeap (switchNeighbor, root);
 327     }
 328
 329   return;
 330 }
 331
 332 void *
 333 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
 334                                    void *element)
 335 {
 336   void *ret;
 337   struct GNUNET_CONTAINER_heap_node *del_node;
 338   struct GNUNET_CONTAINER_heap_node *last;
 339   GNUNET_CONTAINER_HeapCost old_cost;
 340
 341   del_node = NULL;
 342   del_node = find_element (root->root, element);
 343
 344   if (del_node == NULL)
 345     return NULL;
 346   else if (del_node == root->root)
 347     return GNUNET_CONTAINER_heap_remove_root (root);
 348
 349   ret = del_node->element;
 350   last = getPos (root, root->size);
 351
 352   old_cost = del_node->cost;
 353   del_node->element = last->element;
 354   del_node->cost = last->cost;
 355
 356   if (last->parent->left_child == last)
 357     last->parent->left_child = NULL;
 358   if (last->parent->right_child == last)
 359     last->parent->right_child = NULL;
 360
 361   if (root->traversal_pos == last)
 362     {
 363       root->traversal_pos = root->root;
 364     }
 365   GNUNET_free (last);
 366   root->size--;
 367
 368   if (del_node->cost > old_cost)
 369     {
 370       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 371         percolateHeap (del_node, root);
 372       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 373         percolateDownHeap (del_node, root);
 374     }
 375   else if (del_node->cost < old_cost)
 376     {
 377       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 378         percolateDownHeap (del_node, root);
 379       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 380         percolateHeap (del_node, root);
 381     }
 382
 383   return ret;
 384 }
 385
 386 int
 387 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
 388                               void *element, GNUNET_CONTAINER_HeapCost cost)
 389 {
 390   struct GNUNET_CONTAINER_heap_node *new_pos;
 391   int ret;
 392   ret = GNUNET_YES;
 393
 394   if (root->max_size > root->size)
 395     {
 396       new_pos = getNextPos (root);
 397       new_pos->element = element;
 398       new_pos->cost = cost;
 399       root->size++;
 400       /*We no longer can tolerate pointers between heaps :( */
 401       /*if (root->type == GNUNET_DV_MIN_HEAP)
 402          new_pos->neighbor->min_loc = new_pos;
 403          else if (root->type == GNUNET_DV_MAX_HEAP)
 404          new_pos->neighbor->max_loc = new_pos; */
 405
 406       percolateHeap (new_pos, root);
 407     }
 408   else
 409     {
 410       ret = GNUNET_NO;
 411     }
 412
 413   return ret;
 414 }
 415
 416 void *
 417 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
 418 {
 419   void *ret;
 420   struct GNUNET_CONTAINER_heap_node *root_node;
 421   struct GNUNET_CONTAINER_heap_node *last;
 422
 423   root_node = root->root;
 424   ret = root_node->element;
 425   last = getPos (root, root->size);
 426
 427   if ((root_node == last) && (root->size == 1))
 428     {
 429       /* We are removing the last node in the heap! */
 430       root->root = NULL;
 431       root->traversal_pos = NULL;
 432       root->size = 0;
 433       return ret;
 434     }
 435
 436   if (last->parent->left_child == last)
 437     last->parent->left_child = NULL;
 438   else if (last->parent->right_child == last)
 439     last->parent->right_child = NULL;
 440
 441   root_node->element = last->element;
 442   root_node->cost = last->cost;
 443
 444   if (root->traversal_pos == last)
 445     {
 446       root->traversal_pos = root->root;
 447     }
 448
 449   GNUNET_free (last);
 450   root->size--;
 451   percolateDownHeap (root->root, root);
 452   return ret;
 453 }
 454
 455 static int
 456 updatedCost (struct GNUNET_CONTAINER_Heap *root,
 457              struct GNUNET_CONTAINER_heap_node *node)
 458 {
 459   struct GNUNET_CONTAINER_heap_node *parent;
 460
 461   if (node == NULL)
 462     return GNUNET_SYSERR;
 463
 464   parent = node->parent;
 465
 466   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
 467       && (node->cost > parent->cost))
 468     percolateHeap (node, root);
 469   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
 470            && (node->cost < parent->cost))
 471     percolateHeap (node, root);
 472   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 473     percolateDownHeap (node, root);
 474   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 475     percolateDownHeap (node, root);
 476
 477   return GNUNET_YES;
 478 }
 479
 480
 481 int
 482 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
 483                                    void *element,
 484                                    GNUNET_CONTAINER_HeapCost new_cost)
 485 {
 486   struct GNUNET_CONTAINER_heap_node *node;
 487   int ret = GNUNET_YES;
 488   node = find_element (root->root, element);
 489   if (node == NULL)
 490     return GNUNET_NO;
 491
 492   node->cost = new_cost;
 493   ret = updatedCost (root, node);
 494   return ret;
 495 }
 496
 497 void
 498 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
 499                    struct GNUNET_CONTAINER_heap_node *node,
 500                    GNUNET_CONTAINER_HeapIterator iterator, void *cls)
 501 {
 502   if (node == NULL)
 503     return;
 504   internal_iterator (root, node->left_child, iterator, cls);
 505   internal_iterator (root, node->right_child, iterator, cls);
 506   iterator (cls, node->element, node->cost);
 507 }
 508
 509 int
 510 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 511                                GNUNET_CONTAINER_HeapIterator iterator,
 512                                void *cls)
 513 {
 514   internal_iterator (heap, heap->root, iterator, cls);
 515   return GNUNET_OK;
 516 }
 517
 518 void *
 519 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
 520 {
 521   unsigned int choice;
 522   void *element;
 523
 524   if ((root->traversal_pos == NULL) && (root->root != NULL))
 525     {
 526       root->traversal_pos = root->root;
 527     }
 528
 529   if (root->traversal_pos == NULL)
 530     return NULL;
 531
 532   element = root->traversal_pos->element;
 533
 534   choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
 535
 536   switch (choice)
 537     {
 538     case 1:
 539       root->traversal_pos = root->traversal_pos->right_child;
 540       break;
 541     case 0:
 542       root->traversal_pos = root->traversal_pos->left_child;
 543       break;
 544     }
 545
 546   return element;
 547
 548 }
 549
 550 unsigned int
 551 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
 552 {
 553   return heap->size;
 554 }
 555
 556 /* end of heap.c */