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   if ((heap == NULL) || (heap->root == NULL))
  85     return NULL;
  86
  87   return heap->root->element;
  88 }
  89
  90 static int
  91 next_power_of_2(int v)
  92 {
  93   v |= v >> 1;
  94   v |= v >> 2;
  95   v |= v >> 4;
  96   v |= v >> 8;
  97   v |= v >> 16;
  98   v++;
  99   return v;
 100 }
 101
 102 #if 0
 103 static void
 104 internal_print (struct GNUNET_CONTAINER_heap_node *root)
 105 {
 106   fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
 107   if (root->left_child != NULL)
 108     {
 109       fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
 110       internal_print (root->left_child);
 111     }
 112   if (root->right_child != NULL)
 113     {
 114       fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
 115       internal_print (root->right_child);
 116     }
 117 }
 118
 119 static void
 120 printTree (struct GNUNET_CONTAINER_Heap *root)
 121 {
 122   internal_print (root->root);
 123 }
 124 #endif
 125
 126 struct GNUNET_CONTAINER_Heap *
 127 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
 128 {
 129   struct GNUNET_CONTAINER_Heap *heap;
 130   heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
 131   heap->max_size = -1;
 132   heap->type = type;
 133   heap->root = NULL;
 134   heap->traversal_pos = NULL;
 135   heap->size = 0;
 136
 137   return heap;
 138 }
 139
 140 void
 141 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
 142 {
 143   while (heap->size > 0)
 144       GNUNET_CONTAINER_heap_remove_root (heap);
 145   GNUNET_free (heap);
 146   return;
 147 }
 148
 149 struct GNUNET_CONTAINER_heap_node *
 150 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
 151 {
 152   struct GNUNET_CONTAINER_heap_node *ret;
 153   ret = NULL;
 154   if (node == NULL)
 155     return NULL;
 156
 157   if (node->element == element)
 158     return node;
 159
 160   if (node->left_child != NULL)
 161     ret = find_element (node->left_child, element);
 162
 163   if ((ret == NULL) && (node->right_child != NULL))
 164     ret = find_element (node->right_child, element);
 165
 166   return ret;
 167 }
 168
 169 static struct GNUNET_CONTAINER_heap_node *
 170 getNextPos (struct GNUNET_CONTAINER_Heap *root)
 171 {
 172   struct GNUNET_CONTAINER_heap_node *ret;
 173   struct GNUNET_CONTAINER_heap_node *parent;
 174   int pos;
 175   int i;
 176
 177   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
 178   pos = root->size + 1;
 179   ret->left_child = NULL;
 180   ret->right_child = NULL;
 181
 182   if (0 == root->size)
 183     {
 184       ret->parent = NULL;
 185       root->root = ret;
 186     }
 187   else
 188     {
 189       parent = root->root;
 190       for (i = next_power_of_2(pos) >> 2; i > 1; i >>= 1)
 191         {
 192           if (((pos / i) % 2) == 0)
 193             parent = parent->left_child;
 194           else
 195             parent = parent->right_child;
 196         }
 197
 198       ret->parent = parent;
 199       if ((pos % 2) == 0)
 200         parent->left_child = ret;
 201       else
 202         parent->right_child = ret;
 203
 204     }
 205
 206   return ret;
 207
 208 }
 209
 210 static struct GNUNET_CONTAINER_heap_node *
 211 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
 212 {
 213   struct GNUNET_CONTAINER_heap_node *ret;
 214   int i;
 215
 216   ret = NULL;
 217   if (pos > root->size)
 218     {
 219       return ret;
 220     }
 221   else
 222     {
 223       ret = root->root;
 224       for (i = next_power_of_2(pos) >> 2; i > 0; i >>= 1)
 225         {
 226           if (((pos / i) % 2) == 0)
 227             ret = ret->left_child;
 228           else
 229             ret = ret->right_child;
 230         }
 231     }
 232
 233   return ret;
 234
 235 }
 236
 237 void
 238 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
 239            struct GNUNET_CONTAINER_heap_node *second,
 240            struct GNUNET_CONTAINER_Heap *root)
 241 {
 242   void *temp_element;
 243   GNUNET_CONTAINER_HeapCost temp_cost;
 244
 245   temp_element = first->element;
 246   temp_cost = first->cost;
 247   first->element = second->element;
 248   first->cost = second->cost;
 249   second->element = temp_element;
 250   second->cost = temp_cost;
 251
 252   return;
 253 }
 254
 255 void
 256 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
 257                struct GNUNET_CONTAINER_Heap *root)
 258 {
 259
 260   while ((pos->parent != NULL) &&
 261          (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 262            && (pos->parent->cost < pos->cost))
 263           || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 264               && (pos->parent->cost > pos->cost))))
 265     {
 266       swapNodes (pos, pos->parent, root);
 267       pos = pos->parent;
 268     }
 269
 270   return;
 271 }
 272
 273
 274
 275 void
 276 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
 277                    struct GNUNET_CONTAINER_Heap *root)
 278 {
 279   struct GNUNET_CONTAINER_heap_node *switchNeighbor;
 280
 281   switchNeighbor = pos;
 282
 283   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
 284     {
 285       if ((pos->left_child != NULL)
 286           && (pos->left_child->cost > switchNeighbor->cost))
 287         {
 288           switchNeighbor = pos->left_child;
 289         }
 290
 291       if ((pos->right_child != NULL)
 292           && (pos->right_child->cost > switchNeighbor->cost))
 293         {
 294           switchNeighbor = pos->right_child;
 295         }
 296     }
 297   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
 298     {
 299       if ((pos->left_child != NULL)
 300           && (pos->left_child->cost < switchNeighbor->cost))
 301         {
 302           switchNeighbor = pos->left_child;
 303         }
 304
 305       if ((pos->right_child != NULL)
 306           && (pos->right_child->cost < switchNeighbor->cost))
 307         {
 308           switchNeighbor = pos->right_child;
 309         }
 310     }
 311
 312   if (switchNeighbor != pos)
 313     {
 314       swapNodes (switchNeighbor, pos, root);
 315       percolateDownHeap (switchNeighbor, root);
 316     }
 317
 318   return;
 319 }
 320
 321 void *
 322 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
 323                                    void *element)
 324 {
 325   void *ret;
 326   struct GNUNET_CONTAINER_heap_node *del_node;
 327   struct GNUNET_CONTAINER_heap_node *last;
 328   GNUNET_CONTAINER_HeapCost old_cost;
 329
 330   del_node = NULL;
 331   del_node = find_element (root->root, element);
 332
 333   if (del_node == NULL)
 334     return NULL;
 335   else if (del_node == root->root)
 336     return GNUNET_CONTAINER_heap_remove_root (root);
 337
 338   ret = del_node->element;
 339   last = getPos (root, root->size);
 340
 341   old_cost = del_node->cost;
 342   del_node->element = last->element;
 343   del_node->cost = last->cost;
 344
 345   if (last->parent->left_child == last)
 346     last->parent->left_child = NULL;
 347   if (last->parent->right_child == last)
 348     last->parent->right_child = NULL;
 349
 350   if (root->traversal_pos == last)
 351     {
 352       root->traversal_pos = root->root;
 353     }
 354   GNUNET_free (last);
 355   root->size--;
 356
 357   if (del_node->cost > old_cost)
 358     {
 359       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 360         percolateHeap (del_node, root);
 361       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 362         percolateDownHeap (del_node, root);
 363     }
 364   else if (del_node->cost < old_cost)
 365     {
 366       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 367         percolateDownHeap (del_node, root);
 368       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 369         percolateHeap (del_node, root);
 370     }
 371
 372   return ret;
 373 }
 374
 375 int
 376 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
 377                               void *element, GNUNET_CONTAINER_HeapCost cost)
 378 {
 379   struct GNUNET_CONTAINER_heap_node *new_pos;
 380   int ret;
 381   ret = GNUNET_YES;
 382
 383   if (root->max_size > root->size)
 384     {
 385       new_pos = getNextPos (root);
 386       new_pos->element = element;
 387       new_pos->cost = cost;
 388       root->size++;
 389
 390       percolateHeap (new_pos, root);
 391     }
 392   else
 393     {
 394       ret = GNUNET_NO;
 395     }
 396
 397   return ret;
 398 }
 399
 400 void *
 401 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
 402 {
 403   void *ret;
 404   struct GNUNET_CONTAINER_heap_node *root_node;
 405   struct GNUNET_CONTAINER_heap_node *last;
 406
 407   if ((root == NULL) || (root->size == 0) || (root->root == NULL))
 408     return NULL;
 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       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     {
 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 */