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
  91 void
  92 internal_print (struct GNUNET_CONTAINER_heap_node *root)
  93 {
  94   fprintf (stdout, "%llu\n", (unsigned long long) root->cost);
  95   if (root->left_child != NULL)
  96     {
  97       fprintf (stdout, "LEFT of %llu\n", (unsigned long long) root->cost);
  98       internal_print (root->left_child);
  99     }
 100   if (root->right_child != NULL)
 101     {
 102       fprintf (stdout, "RIGHT of %llu\n", (unsigned long long) root->cost);
 103       internal_print (root->right_child);
 104     }
 105 }
 106
 107 void
 108 printTree (struct GNUNET_CONTAINER_Heap *root)
 109 {
 110   internal_print (root->root);
 111 }
 112
 113 struct GNUNET_CONTAINER_Heap *
 114 GNUNET_CONTAINER_heap_create (enum GNUNET_CONTAINER_HeapOrder type)
 115 {
 116   struct GNUNET_CONTAINER_Heap *heap;
 117   heap = malloc (sizeof (struct GNUNET_CONTAINER_Heap));
 118   heap->max_size = -1;
 119   heap->type = type;
 120   heap->root = NULL;
 121   heap->traversal_pos = NULL;
 122   heap->size = 0;
 123
 124   return heap;
 125 }
 126
 127 void
 128 GNUNET_CONTAINER_heap_destroy (struct GNUNET_CONTAINER_Heap *heap)
 129 {
 130   while (heap->size > 0)
 131       GNUNET_CONTAINER_heap_remove_root (heap);
 132   GNUNET_free (heap);
 133   return;
 134 }
 135
 136 struct GNUNET_CONTAINER_heap_node *
 137 find_element (struct GNUNET_CONTAINER_heap_node *node, void *element)
 138 {
 139   struct GNUNET_CONTAINER_heap_node *ret;
 140   ret = NULL;
 141   if (node == NULL)
 142     return NULL;
 143
 144   if (node->element == element)
 145     return node;
 146
 147   if (node->left_child != NULL)
 148     ret = find_element (node->left_child, element);
 149
 150   if (node->right_child != NULL)
 151     ret = find_element (node->right_child, element);
 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   return;
 245 }
 246
 247 void
 248 percolateHeap (struct GNUNET_CONTAINER_heap_node *pos,
 249                struct GNUNET_CONTAINER_Heap *root)
 250 {
 251
 252   while ((pos->parent != NULL) &&
 253          (((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 254            && (pos->parent->cost < pos->cost))
 255           || ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 256               && (pos->parent->cost > pos->cost))))
 257     {
 258       swapNodes (pos, pos->parent, root);
 259       pos = pos->parent;
 260     }
 261
 262   return;
 263 }
 264
 265
 266
 267 void
 268 percolateDownHeap (struct GNUNET_CONTAINER_heap_node *pos,
 269                    struct GNUNET_CONTAINER_Heap *root)
 270 {
 271   struct GNUNET_CONTAINER_heap_node *switchNeighbor;
 272
 273   switchNeighbor = pos;
 274
 275   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX))
 276     {
 277       if ((pos->left_child != NULL)
 278           && (pos->left_child->cost > switchNeighbor->cost))
 279         {
 280           switchNeighbor = pos->left_child;
 281         }
 282
 283       if ((pos->right_child != NULL)
 284           && (pos->right_child->cost > switchNeighbor->cost))
 285         {
 286           switchNeighbor = pos->right_child;
 287         }
 288     }
 289   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN))
 290     {
 291       if ((pos->left_child != NULL)
 292           && (pos->left_child->cost < switchNeighbor->cost))
 293         {
 294           switchNeighbor = pos->left_child;
 295         }
 296
 297       if ((pos->right_child != NULL)
 298           && (pos->right_child->cost < switchNeighbor->cost))
 299         {
 300           switchNeighbor = pos->right_child;
 301         }
 302     }
 303
 304   if (switchNeighbor != pos)
 305     {
 306       swapNodes (switchNeighbor, pos, root);
 307       percolateDownHeap (switchNeighbor, root);
 308     }
 309
 310   return;
 311 }
 312
 313 void *
 314 GNUNET_CONTAINER_heap_remove_node (struct GNUNET_CONTAINER_Heap *root,
 315                                    void *element)
 316 {
 317   void *ret;
 318   struct GNUNET_CONTAINER_heap_node *del_node;
 319   struct GNUNET_CONTAINER_heap_node *last;
 320   GNUNET_CONTAINER_HeapCost old_cost;
 321
 322   del_node = NULL;
 323   del_node = find_element (root->root, element);
 324
 325   if (del_node == NULL)
 326     return NULL;
 327   else if (del_node == root->root)
 328     return GNUNET_CONTAINER_heap_remove_root (root);
 329
 330   ret = del_node->element;
 331   last = getPos (root, root->size);
 332
 333   old_cost = del_node->cost;
 334   del_node->element = last->element;
 335   del_node->cost = last->cost;
 336
 337   if (last->parent->left_child == last)
 338     last->parent->left_child = NULL;
 339   if (last->parent->right_child == last)
 340     last->parent->right_child = NULL;
 341
 342   if (root->traversal_pos == last)
 343     {
 344       root->traversal_pos = root->root;
 345     }
 346   GNUNET_free (last);
 347   root->size--;
 348
 349   if (del_node->cost > old_cost)
 350     {
 351       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 352         percolateHeap (del_node, root);
 353       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 354         percolateDownHeap (del_node, root);
 355     }
 356   else if (del_node->cost < old_cost)
 357     {
 358       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 359         percolateDownHeap (del_node, root);
 360       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 361         percolateHeap (del_node, root);
 362     }
 363
 364   return ret;
 365 }
 366
 367 int
 368 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
 369                               void *element, GNUNET_CONTAINER_HeapCost cost)
 370 {
 371   struct GNUNET_CONTAINER_heap_node *new_pos;
 372   int ret;
 373   ret = GNUNET_YES;
 374
 375   if (root->max_size > root->size)
 376     {
 377       new_pos = getNextPos (root);
 378       new_pos->element = element;
 379       new_pos->cost = cost;
 380       root->size++;
 381
 382       percolateHeap (new_pos, root);
 383     }
 384   else
 385     {
 386       ret = GNUNET_NO;
 387     }
 388
 389   return ret;
 390 }
 391
 392 void *
 393 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
 394 {
 395   void *ret;
 396   struct GNUNET_CONTAINER_heap_node *root_node;
 397   struct GNUNET_CONTAINER_heap_node *last;
 398
 399   if ((root == NULL) || (root->size == 0) || (root->root == NULL))
 400     return NULL;
 401
 402   root_node = root->root;
 403   ret = root_node->element;
 404   last = getPos (root, root->size);
 405
 406   if ((root_node == last) && (root->size == 1))
 407     {
 408       /* We are removing the last node in the heap! */
 409       root->root = NULL;
 410       root->traversal_pos = NULL;
 411       root->size = 0;
 412       return ret;
 413     }
 414
 415   if (last->parent->left_child == last)
 416     last->parent->left_child = NULL;
 417   else if (last->parent->right_child == last)
 418     last->parent->right_child = NULL;
 419
 420   root_node->element = last->element;
 421   root_node->cost = last->cost;
 422
 423   if (root->traversal_pos == last)
 424     {
 425       root->traversal_pos = root->root;
 426     }
 427
 428   GNUNET_free (last);
 429   root->size--;
 430   percolateDownHeap (root->root, root);
 431   return ret;
 432 }
 433
 434 static int
 435 updatedCost (struct GNUNET_CONTAINER_Heap *root,
 436              struct GNUNET_CONTAINER_heap_node *node)
 437 {
 438   struct GNUNET_CONTAINER_heap_node *parent;
 439
 440   if (node == NULL)
 441     return GNUNET_SYSERR;
 442
 443   parent = node->parent;
 444
 445   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
 446       && (node->cost > parent->cost))
 447     percolateHeap (node, root);
 448   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
 449            && (node->cost < parent->cost))
 450     percolateHeap (node, root);
 451   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 452     percolateDownHeap (node, root);
 453   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 454     percolateDownHeap (node, root);
 455
 456   return GNUNET_YES;
 457 }
 458
 459
 460 int
 461 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
 462                                    void *element,
 463                                    GNUNET_CONTAINER_HeapCost new_cost)
 464 {
 465   struct GNUNET_CONTAINER_heap_node *node;
 466   int ret = GNUNET_YES;
 467   node = find_element (root->root, element);
 468   if (node == NULL)
 469     return GNUNET_NO;
 470
 471   node->cost = new_cost;
 472   ret = updatedCost (root, node);
 473   return ret;
 474 }
 475
 476 void
 477 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
 478                    struct GNUNET_CONTAINER_heap_node *node,
 479                    GNUNET_CONTAINER_HeapIterator iterator, void *cls)
 480 {
 481   if (node == NULL)
 482     return;
 483   internal_iterator (root, node->left_child, iterator, cls);
 484   internal_iterator (root, node->right_child, iterator, cls);
 485   iterator (cls, node->element, node->cost);
 486 }
 487
 488 int
 489 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 490                                GNUNET_CONTAINER_HeapIterator iterator,
 491                                void *cls)
 492 {
 493   internal_iterator (heap, heap->root, iterator, cls);
 494   return GNUNET_OK;
 495 }
 496
 497 void *
 498 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
 499 {
 500   unsigned int choice;
 501   void *element;
 502
 503   if ((root->traversal_pos == NULL) && (root->root != NULL))
 504     {
 505       root->traversal_pos = root->root;
 506     }
 507
 508   if (root->traversal_pos == NULL)
 509     return NULL;
 510
 511   element = root->traversal_pos->element;
 512
 513   choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, 2);
 514
 515   switch (choice)
 516     {
 517     case 1:
 518       root->traversal_pos = root->traversal_pos->right_child;
 519       break;
 520     case 0:
 521       root->traversal_pos = root->traversal_pos->left_child;
 522       break;
 523     }
 524
 525   return element;
 526
 527 }
 528
 529 unsigned int
 530 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
 531 {
 532   return heap->size;
 533 }
 534
 535 /* end of heap.c */