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