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