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   else if (del_node == root->root)
 335     return GNUNET_CONTAINER_heap_remove_root (root);
 336
 337   ret = del_node->element;
 338   last = getPos (root, root->size);
 339
 340   old_cost = del_node->cost;
 341   del_node->element = last->element;
 342   del_node->cost = last->cost;
 343
 344   if (last->parent->left_child == last)
 345     last->parent->left_child = NULL;
 346   if (last->parent->right_child == last)
 347     last->parent->right_child = NULL;
 348
 349   if (root->traversal_pos == last)
 350     {
 351       root->traversal_pos = root->root;
 352     }
 353   GNUNET_free (last);
 354   root->size--;
 355
 356   if (del_node->cost > old_cost)
 357     {
 358       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 359         percolateHeap (del_node, root);
 360       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 361         percolateDownHeap (del_node, root);
 362     }
 363   else if (del_node->cost < old_cost)
 364     {
 365       if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 366         percolateDownHeap (del_node, root);
 367       else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 368         percolateHeap (del_node, root);
 369     }
 370
 371   return ret;
 372 }
 373
 374 int
 375 GNUNET_CONTAINER_heap_insert (struct GNUNET_CONTAINER_Heap *root,
 376                               void *element, GNUNET_CONTAINER_HeapCost cost)
 377 {
 378   struct GNUNET_CONTAINER_heap_node *new_pos;
 379   int ret;
 380   ret = GNUNET_YES;
 381
 382   if (root->max_size > root->size)
 383     {
 384       new_pos = getNextPos (root);
 385       new_pos->element = element;
 386       new_pos->cost = cost;
 387       root->size++;
 388       /*We no longer can tolerate pointers between heaps :( */
 389       /*if (root->type == GNUNET_DV_MIN_HEAP)
 390          new_pos->neighbor->min_loc = new_pos;
 391          else if (root->type == GNUNET_DV_MAX_HEAP)
 392          new_pos->neighbor->max_loc = new_pos; */
 393
 394       percolateHeap (new_pos, root);
 395     }
 396   else
 397     {
 398       ret = GNUNET_NO;
 399     }
 400
 401   return ret;
 402 }
 403
 404 void *
 405 GNUNET_CONTAINER_heap_remove_root (struct GNUNET_CONTAINER_Heap *root)
 406 {
 407   void *ret;
 408   struct GNUNET_CONTAINER_heap_node *root_node;
 409   struct GNUNET_CONTAINER_heap_node *last;
 410
 411   root_node = root->root;
 412   ret = root_node->element;
 413   last = getPos (root, root->size);
 414
 415   if ((root_node == last) && (root->size == 1))
 416     {
 417       /* We are removing the last node in the heap! */
 418       root->root = NULL;
 419       root->traversal_pos = NULL;
 420       root->size = 0;
 421       return ret;
 422     }
 423
 424   if (last->parent->left_child == last)
 425     last->parent->left_child = NULL;
 426   else if (last->parent->right_child == last)
 427     last->parent->right_child = NULL;
 428
 429   root_node->element = last->element;
 430   root_node->cost = last->cost;
 431
 432   if (root->traversal_pos == last)
 433     {
 434       root->traversal_pos = root->root;
 435     }
 436
 437   GNUNET_free (last);
 438   root->size--;
 439   percolateDownHeap (root->root, root);
 440   return ret;
 441 }
 442
 443 static int
 444 updatedCost (struct GNUNET_CONTAINER_Heap *root,
 445              struct GNUNET_CONTAINER_heap_node *node)
 446 {
 447   struct GNUNET_CONTAINER_heap_node *parent;
 448
 449   if (node == NULL)
 450     return GNUNET_SYSERR;
 451
 452   parent = node->parent;
 453
 454   if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX) && (parent != NULL)
 455       && (node->cost > parent->cost))
 456     percolateHeap (node, root);
 457   else if ((root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN) && (parent != NULL)
 458            && (node->cost < parent->cost))
 459     percolateHeap (node, root);
 460   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MAX)
 461     percolateDownHeap (node, root);
 462   else if (root->type == GNUNET_CONTAINER_HEAP_ORDER_MIN)
 463     percolateDownHeap (node, root);
 464
 465   return GNUNET_YES;
 466 }
 467
 468
 469 int
 470 GNUNET_CONTAINER_heap_update_cost (struct GNUNET_CONTAINER_Heap *root,
 471                                    void *element,
 472                                    GNUNET_CONTAINER_HeapCost new_cost)
 473 {
 474   struct GNUNET_CONTAINER_heap_node *node;
 475   int ret = GNUNET_YES;
 476   node = find_element (root->root, element);
 477   if (node == NULL)
 478     return GNUNET_NO;
 479
 480   node->cost = new_cost;
 481   ret = updatedCost (root, node);
 482   return ret;
 483 }
 484
 485 void
 486 internal_iterator (struct GNUNET_CONTAINER_Heap *root,
 487                    struct GNUNET_CONTAINER_heap_node *node,
 488                    GNUNET_CONTAINER_HeapIterator iterator, void *cls)
 489 {
 490   if (node == NULL)
 491     return;
 492   internal_iterator (root, node->left_child, iterator, cls);
 493   internal_iterator (root, node->right_child, iterator, cls);
 494   iterator (node->element, node->cost, root, cls);
 495 }
 496
 497 int
 498 GNUNET_CONTAINER_heap_iterate (struct GNUNET_CONTAINER_Heap *heap,
 499                                GNUNET_CONTAINER_HeapIterator iterator,
 500                                void *cls)
 501 {
 502   internal_iterator (heap, heap->root, iterator, cls);
 503   return GNUNET_OK;
 504 }
 505
 506 void *
 507 GNUNET_CONTAINER_heap_walk_get_next (struct GNUNET_CONTAINER_Heap *root)
 508 {
 509   unsigned int choice;
 510   void *element;
 511
 512   if ((root->traversal_pos == NULL) && (root->root != NULL))
 513     {
 514       root->traversal_pos = root->root;
 515     }
 516
 517   if (root->traversal_pos == NULL)
 518     return NULL;
 519
 520   element = root->traversal_pos->element;
 521
 522   choice = GNUNET_random_u32 (GNUNET_RANDOM_QUALITY_WEAK, 2);
 523
 524   switch (choice)
 525     {
 526     case 1:
 527       root->traversal_pos = root->traversal_pos->right_child;
 528       break;
 529     case 0:
 530       root->traversal_pos = root->traversal_pos->left_child;
 531       break;
 532     }
 533
 534   return element;
 535
 536 }
 537
 538 unsigned int
 539 GNUNET_CONTAINER_heap_get_size (struct GNUNET_CONTAINER_Heap *heap)
 540 {
 541   return heap->size;
 542 }
 543
 544 /* end of heap.c */