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 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 void
 103 internal_print (struct GNUNET_CONTAINER_heap_node *root)
 104 {
 105   fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
 106   if (root->left_child != NULL)
 107     {
 108       fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
 109       internal_print (root->left_child);
 110     }
 111   if (root->right_child != NULL)
 112     {
 113       fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
 114       internal_print (root->right_child);
 115     }
 116 }
 117
 118 void
 119 printTree (struct GNUNET_CONTAINER_Heap *root)
 120 {
 121   internal_print (root->root);
 122 }
 123
 124 struct GNUNET_CONTAINER_Heap *
 125 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
 126 {
 127   struct GNUNET_CONTAINER_Heap *heap;
 128   heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
 129   heap->max_size = -1;
 130   heap->type = type;
 131   heap->root = NULL;
 132   heap->traversal_pos = NULL;
 133   heap->size = 0;
 134
 135   return heap;
 136 }
 137
 138 void
 139 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
 140 {
 141   while (heap->size > 0)
 142       GNUNET_CONTAINER_heap_remove_root (heap);
 143   GNUNET_free (heap);
 144   return;
 145 }
 146
 147 struct GNUNET_CONTAINER_heap_node *
 148 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
 149 {
 150   struct GNUNET_CONTAINER_heap_node *ret;
 151   ret = NULL;
 152   if (node == NULL)
 153     return NULL;
 154
 155   if (node->element == element)
 156     return node;
 157
 158   if (node->left_child != NULL)
 159     ret = find_element (node->left_child, element);
 160
 161   if (node->right_child != NULL)
 162     ret = find_element (node->right_child, element);
 163
 164   return ret;
 165 }
 166
 167 static struct GNUNET_CONTAINER_heap_node *
 168 getNextPos (struct GNUNET_CONTAINER_Heap *root)
 169 {
 170   struct GNUNET_CONTAINER_heap_node *ret;
 171   struct GNUNET_CONTAINER_heap_node *parent;
 172   int pos;
 173   int i;
 174
 175   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_heap_node));
 176   pos = root->size + 1;
 177   ret->left_child = NULL;
 178   ret->right_child = NULL;
 179
 180   if (0 == root->size)
 181     {
 182       ret->parent = NULL;
 183       root->root = ret;
 184     }
 185   else
 186     {
 187       parent = root->root;
 188       for (i = next_power_of_2(pos) >> 2; i > 1; i >>= 1)
 189         {
 190           if (((pos / i) % 2) == 0)
 191             parent = parent->left_child;
 192           else
 193             parent = parent->right_child;
 194         }
 195
 196       ret->parent = parent;
 197       if ((pos % 2) == 0)
 198         parent->left_child = ret;
 199       else
 200         parent->right_child = ret;
 201
 202     }
 203
 204   return ret;
 205
 206 }
 207
 208 static struct GNUNET_CONTAINER_heap_node *
 209 getPos (struct GNUNET_CONTAINER_Heap *root, unsigned int pos)
 210 {
 211   struct GNUNET_CONTAINER_heap_node *ret;
 212   int i;
 213
 214   ret = NULL;
 215   if (pos > root->size)
 216     {
 217       return ret;
 218     }
 219   else
 220     {
 221       ret = root->root;
 222       for (i = next_power_of_2(pos) >> 2; i > 0; i >>= 1)
 223         {
 224           if (((pos / i) % 2) == 0)
 225             ret = ret->left_child;
 226           else
 227             ret = ret->right_child;
 228         }
 229     }
 230
 231   return ret;
 232
 233 }
 234
 235 void
 236 swapNodes (struct GNUNET_CONTAINER_heap_node *first,
 237            struct GNUNET_CONTAINER_heap_node *second,
 238            struct GNUNET_CONTAINER_Heap *root)
 239 {
 240   void *temp_element;
 241   GNUNET_CONTAINER_HeapCost temp_cost;
 242
 243   temp_element = first->element;
 244   temp_cost = first->cost;
 245   first->element = second->element;
 246   first->cost = second->cost;
 247   second->element = temp_element;
 248   second->cost = temp_cost;
 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
 388       percolateHeap (new_pos, root);
 389     }
 390   else
 391     {
 392       ret = GNUNET_NO;
 393     }
 394
 395   return ret;
 396 }
 397
 398 void *
 399 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
 400 {
 401   void *ret;
 402   struct GNUNET_CONTAINER_heap_node *root_node;
 403   struct GNUNET_CONTAINER_heap_node *last;
 404
 405   if ((root == NULL) || (root->size == 0) || (root->root == NULL))
 406     return NULL;
 407
 408   root_node = root->root;
 409   ret = root_node->element;
 410   last = getPos (root, root->size);
 411
 412   if ((root_node == last) && (root->size == 1))
 413     {
 414       /* We are removing the last node in the heap! */
 415       root->root = NULL;
 416       root->traversal_pos = NULL;
 417       root->size = 0;
 418       return ret;
 419     }
 420
 421   if (last->parent->left_child == last)
 422     last->parent->left_child = NULL;
 423   else if (last->parent->right_child == last)
 424     last->parent->right_child = NULL;
 425
 426   root_node->element = last->element;
 427   root_node->cost = last->cost;
 428
 429   if (root->traversal_pos == last)
 430     {
 431       root->traversal_pos = root->root;
 432     }
 433
 434   GNUNET_free (last);
 435   root->size--;
 436   percolateDownHeap (root->root, root);
 437   return ret;
 438 }
 439
 440 static int
 441 updatedCost (struct GNUNET_CONTAINER_Heap *root,
 442              struct GNUNET_CONTAINER_heap_node *node)
 443 {
 444   struct GNUNET_CONTAINER_heap_node *parent;
 445
 446   if (node == NULL)
 447     return GNUNET_SYSERR;
 448
 449   parent = node->parent;
 450
 451   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
 452       && (node->cost > parent->cost))
 453     percolateHeap (node, root);
 454   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
 455            && (node->cost < parent->cost))
 456     percolateHeap (node, root);
 457   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 458     percolateDownHeap (node, root);
 459   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 460     percolateDownHeap (node, root);
 461
 462   return GNUNET_YES;
 463 }
 464
 465
 466 int
 467 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
 468                                    void *element,
 469                                    GNUNET_CONTAINER_HeapCost new_cost)
 470 {
 471   struct GNUNET_CONTAINER_heap_node *node;
 472   int ret = GNUNET_YES;
 473   node = find_element (root->root, element);
 474   if (node == NULL)
 475     return GNUNET_NO;
 476
 477   node->cost = new_cost;
 478   ret = updatedCost (root, node);
 479   return ret;
 480 }
 481
 482 void
 483 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
 484                    struct GNUNET_CONTAINER_heap_node *node,
 485                    GNUNET_CONTAINER_HeapIterator iterator, void *cls)
 486 {
 487   if (node == NULL)
 488     return;
 489   internal_iterator (root, node->left_child, iterator, cls);
 490   internal_iterator (root, node->right_child, iterator, cls);
 491   iterator (cls, node->element, node->cost);
 492 }
 493
 494 int
 495 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 496                                GNUNET_CONTAINER_HeapIterator iterator,
 497                                void *cls)
 498 {
 499   internal_iterator (heap, heap->root, iterator, cls);
 500   return GNUNET_OK;
 501 }
 502
 503 void *
 504 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
 505 {
 506   unsigned int choice;
 507   void *element;
 508
 509   if ((root->traversal_pos == NULL) && (root->root != NULL))
 510     {
 511       root->traversal_pos = root->root;
 512     }
 513
 514   if (root->traversal_pos == NULL)
 515     return NULL;
 516
 517   element = root->traversal_pos->element;
 518
 519   choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
 520
 521   switch (choice)
 522     {
 523     case 1:
 524       root->traversal_pos = root->traversal_pos->right_child;
 525       break;
 526     case 0:
 527       root->traversal_pos = root->traversal_pos->left_child;
 528       break;
 529     }
 530
 531   return element;
 532
 533 }
 534
 535 unsigned int
 536 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
 537 {
 538   return heap->size;
 539 }
 540
 541 /* end of heap.c */