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