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