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