BGI/SOAPdenovo2/standardPregraph/dfib.c

   1 /*
   2  * dfib.c
   3  *
   4  * This file is part of SOAPdenovo.
   5  *
   6  */
   7
   8 /*-
   9  * Copyright 1997-2003 John-Mark Gurney.
  10  * All rights reserved.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  *  $Id: dfib.c,v 1.12 2007/10/19 13:09:26 zerbino Exp $
  34  *
  35  */
  36 #include <limits.h>
  37 #include <stdlib.h>
  38
  39 #include "dfib.h"
  40 #include "dfibpriv.h"
  41 #include "extfunc2.h"
  42
  43 #define HEAPBLOCKSIZE 1000
  44 static int dfh_comparedata ( DFibHeap * h, Time key, unsigned int data, DFibHeapNode * b );
  45 static DFibHeapNode * allocateDFibHeapNode ( DFibHeap * heap )
  46 {
  47         return ( DFibHeapNode * ) getItem ( heap->nodeMemory );
  48 };
  49
  50 static void deallocateDFibHeapNode ( DFibHeapNode * a, DFibHeap * heap )
  51 {
  52         returnItem ( heap->nodeMemory, a );
  53 }
  54
  55 IDnum dfibheap_getSize ( DFibHeap * heap )
  56 {
  57         return heap->dfh_n;
  58 }
  59
  60 #define swap(type, a, b)        \
  61         do {            \
  62                 type c;     \
  63                 c = a;      \
  64                 a = b;      \
  65                 b = c;      \
  66         } while (0)     \
  67
  68 #define INT_BITS        (sizeof(IDnum) * 8)
  69
  70 static inline IDnum ceillog2 ( IDnum a )
  71 {
  72         IDnum oa;
  73         IDnum i;
  74         IDnum b;
  75         IDnum cons;
  76         oa = a;
  77         b = INT_BITS / 2;
  78         i = 0;
  79
  80         while ( b )
  81         {
  82                 i = ( i << 1 );
  83                 cons = ( ( IDnum ) 1 ) << b;
  84
  85                 if ( a >= cons )
  86                 {
  87                         a /= cons;
  88                         i = i | 1;
  89                 }
  90                 else
  91                 {
  92                         a &= cons - 1;
  93                 }
  94
  95                 b /= 2;
  96         }
  97
  98         if ( ( ( ( IDnum ) 1 << i ) ) == oa )
  99         {
 100                 return i;
 101         }
 102         else
 103         {
 104                 return i + 1;
 105         }
 106 }
 107
 108 /*
 109  * Public Heap Functions
 110  */
 111 DFibHeap * dfh_makekeyheap ()
 112 {
 113         DFibHeap * n;
 114
 115         if ( ( n = malloc ( sizeof * n ) ) == NULL )
 116         {
 117                 return NULL;
 118         }
 119
 120         n->nodeMemory = createMem_manager ( HEAPBLOCKSIZE, sizeof ( DFibHeapNode ) );
 121         n->dfh_n = 0;
 122         n->dfh_Dl = -1;
 123         n->dfh_cons = NULL;
 124         n->dfh_min = NULL;
 125         n->dfh_root = NULL;
 126         return n;
 127 }
 128
 129 void dfh_deleteheap ( DFibHeap * h )
 130 {
 131         fprintf ( stderr, "DFibHeap: %lld node(s) allocated.\n", h->nodeMemory->counter );
 132         freeMem_manager ( h->nodeMemory );
 133         h->nodeMemory = NULL;
 134
 135         if ( h->dfh_cons != NULL )
 136         {
 137                 free ( h->dfh_cons );
 138         }
 139
 140         free ( h );
 141 }
 142
 143 /*
 144  * Public Key Heap Functions
 145  */
 146 DFibHeapNode * dfh_insertkey ( DFibHeap * h, Time key, unsigned int data )
 147 {
 148         DFibHeapNode * x;
 149
 150         if ( ( x = dfhe_newelem ( h ) ) == NULL )
 151         {
 152                 return NULL;
 153         }
 154
 155         /* just insert on root list, and make sure it's not the new min */
 156         x->dfhe_data = data;
 157         x->dfhe_key = key;
 158         dfh_insertel ( h, x );
 159         return x;
 160 }
 161
 162 Time dfh_replacekey ( DFibHeap * h, DFibHeapNode * x, Time key )
 163 {
 164         Time ret;
 165         ret = x->dfhe_key;
 166         ( void ) dfh_replacekeydata ( h, x, key, x->dfhe_data );
 167         return ret;
 168 }
 169
 170 unsigned int minInDHeap ( DFibHeap * h )
 171 {
 172         if ( h->dfh_min )
 173         {
 174                 return h->dfh_min->dfhe_data;
 175         }
 176         else
 177         {
 178                 return 0;
 179         }
 180 }
 181
 182 boolean HasMin ( DFibHeap * h )
 183 {
 184         if ( h->dfh_min )
 185         {
 186                 return 1;
 187         }
 188         else
 189         {
 190                 return 0;
 191         }
 192 }
 193
 194 unsigned int dfh_replacekeydata ( DFibHeap * h, DFibHeapNode * x, Time key, unsigned int data )
 195 {
 196         unsigned int odata;
 197         Time okey;
 198         DFibHeapNode * y;
 199         int r;
 200         odata = x->dfhe_data;
 201         okey = x->dfhe_key;
 202
 203         /*
 204          * we can increase a key by deleting and reinserting, that
 205          * requires O(lgn) time.
 206          */
 207         if ( ( r = dfh_comparedata ( h, key, data, x ) ) > 0 )
 208         {
 209                 /* XXX - bad code! */
 210                 abort ();
 211         }
 212
 213         x->dfhe_data = data;
 214         x->dfhe_key = key;
 215
 216         /* because they are equal, we don't have to do anything */
 217         if ( r == 0 )
 218         {
 219                 return odata;
 220         }
 221
 222         y = x->dfhe_p;
 223
 224         if ( okey == key )
 225         {
 226                 return odata;
 227         }
 228
 229         if ( y != NULL && dfh_compare ( h, x, y ) <= 0 )
 230         {
 231                 dfh_cut ( h, x, y );
 232                 dfh_cascading_cut ( h, y );
 233         }
 234
 235         /*
 236          * the = is so that the call from dfh_delete will delete the proper
 237          * element.
 238          */
 239         if ( dfh_compare ( h, x, h->dfh_min ) <= 0 )
 240         {
 241                 h->dfh_min = x;
 242         }
 243
 244         return odata;
 245 }
 246
 247 /*
 248  * Public void * Heap Functions
 249  */
 250 /*
 251  * this will return these values:
 252  *  NULL    failed for some reason
 253  *  ptr token to use for manipulation of data
 254  */
 255 unsigned int dfh_extractmin ( DFibHeap * h )
 256 {
 257         DFibHeapNode * z;
 258         unsigned int ret;
 259         ret = 0;
 260
 261         if ( h->dfh_min != NULL )
 262         {
 263                 z = dfh_extractminel ( h );
 264                 ret = z->dfhe_data;
 265                 deallocateDFibHeapNode ( z, h );
 266         }
 267
 268         return ret;
 269 }
 270
 271 unsigned int dfh_replacedata ( DFibHeapNode * x, unsigned int data )
 272 {
 273         unsigned int odata = x->dfhe_data;
 274         //printf("replace node value %d with %d\n",x->dfhe_data,data);
 275         x->dfhe_data = data;
 276         return odata;
 277 }
 278
 279 unsigned int dfh_delete ( DFibHeap * h, DFibHeapNode * x )
 280 {
 281         unsigned int k;
 282         //printf("destroy node %d in dheap\n",x->dfhe_data);
 283         k = x->dfhe_data;
 284         dfh_replacekey ( h, x, INT_MIN );
 285         dfh_extractmin ( h );
 286         return k;
 287 }
 288
 289 /*
 290  * begin of private element fuctions
 291  */
 292 static DFibHeapNode * dfh_extractminel ( DFibHeap * h )
 293 {
 294         DFibHeapNode * ret;
 295         DFibHeapNode * x, *y, *orig;
 296         ret = h->dfh_min;
 297         orig = NULL;
 298
 299         /* put all the children on the root list */
 300         /* for true consistancy, we should use dfhe_remove */
 301         for ( x = ret->dfhe_child; x != orig && x != NULL; )
 302         {
 303                 if ( orig == NULL )
 304                 {
 305                         orig = x;
 306                 }
 307
 308                 y = x->dfhe_right;
 309                 x->dfhe_p = NULL;
 310                 dfh_insertrootlist ( h, x );
 311                 x = y;
 312         }
 313
 314         /* remove minimum from root list */
 315         dfh_removerootlist ( h, ret );
 316         h->dfh_n--;
 317
 318         /* if we aren't empty, consolidate the heap */
 319         if ( h->dfh_n == 0 )
 320         {
 321                 h->dfh_min = NULL;
 322         }
 323         else
 324         {
 325                 h->dfh_min = ret->dfhe_right;
 326                 dfh_consolidate ( h );
 327         }
 328
 329         return ret;
 330 }
 331
 332 static void dfh_insertrootlist ( DFibHeap * h, DFibHeapNode * x )
 333 {
 334         if ( h->dfh_root == NULL )
 335         {
 336                 h->dfh_root = x;
 337                 x->dfhe_left = x;
 338                 x->dfhe_right = x;
 339                 return;
 340         }
 341
 342         dfhe_insertafter ( h->dfh_root, x );
 343 }
 344
 345 static void dfh_removerootlist ( DFibHeap * h, DFibHeapNode * x )
 346 {
 347         if ( x->dfhe_left == x )
 348         {
 349                 h->dfh_root = NULL;
 350         }
 351         else
 352         {
 353                 h->dfh_root = dfhe_remove ( x );
 354         }
 355 }
 356
 357 static void dfh_consolidate ( DFibHeap * h )
 358 {
 359         DFibHeapNode ** a;
 360         DFibHeapNode * w;
 361         DFibHeapNode * y;
 362         DFibHeapNode * x;
 363         IDnum i;
 364         IDnum d;
 365         IDnum D;
 366         dfh_checkcons ( h );
 367         /* assign a the value of h->dfh_cons so I don't have to rewrite code */
 368         D = h->dfh_Dl + 1;
 369         a = h->dfh_cons;
 370
 371         for ( i = 0; i < D; i++ )
 372         {
 373                 a[i] = NULL;
 374         }
 375
 376         while ( ( w = h->dfh_root ) != NULL )
 377         {
 378                 x = w;
 379                 dfh_removerootlist ( h, w );
 380                 d = x->dfhe_degree;
 381
 382                 /* XXX - assert that d < D */
 383                 while ( a[d] != NULL )
 384                 {
 385                         y = a[d];
 386
 387                         if ( dfh_compare ( h, x, y ) > 0 )
 388                         {
 389                                 swap ( DFibHeapNode *, x, y );
 390                         }
 391
 392                         dfh_heaplink ( h, y, x );
 393                         a[d] = NULL;
 394                         d++;
 395                 }
 396
 397                 a[d] = x;
 398         }
 399
 400         h->dfh_min = NULL;
 401
 402         for ( i = 0; i < D; i++ )
 403                 if ( a[i] != NULL )
 404                 {
 405                         dfh_insertrootlist ( h, a[i] );
 406
 407                         if ( h->dfh_min == NULL || dfh_compare ( h, a[i], h->dfh_min ) < 0 )
 408                         {
 409                                 h->dfh_min = a[i];
 410                         }
 411                 }
 412 }
 413
 414 static void dfh_heaplink ( DFibHeap * h, DFibHeapNode * y, DFibHeapNode * x )
 415 {
 416         /* make y a child of x */
 417         if ( x->dfhe_child == NULL )
 418         {
 419                 x->dfhe_child = y;
 420         }
 421         else
 422         {
 423                 dfhe_insertbefore ( x->dfhe_child, y );
 424         }
 425
 426         y->dfhe_p = x;
 427         x->dfhe_degree++;
 428         y->dfhe_mark = 0;
 429 }
 430
 431 static void dfh_cut ( DFibHeap * h, DFibHeapNode * x, DFibHeapNode * y )
 432 {
 433         dfhe_remove ( x );
 434         y->dfhe_degree--;
 435         dfh_insertrootlist ( h, x );
 436         x->dfhe_p = NULL;
 437         x->dfhe_mark = 0;
 438 }
 439
 440 static void dfh_cascading_cut ( DFibHeap * h, DFibHeapNode * y )
 441 {
 442         DFibHeapNode * z;
 443
 444         while ( ( z = y->dfhe_p ) != NULL )
 445         {
 446                 if ( y->dfhe_mark == 0 )
 447                 {
 448                         y->dfhe_mark = 1;
 449                         return;
 450                 }
 451                 else
 452                 {
 453                         dfh_cut ( h, y, z );
 454                         y = z;
 455                 }
 456         }
 457 }
 458
 459 /*
 460  * begining of handling elements of dfibheap
 461  */
 462 static DFibHeapNode * dfhe_newelem ( DFibHeap * h )
 463 {
 464         DFibHeapNode * e;
 465
 466         if ( ( e = allocateDFibHeapNode ( h ) ) == NULL )
 467         {
 468                 return NULL;
 469         }
 470
 471         e->dfhe_degree = 0;
 472         e->dfhe_mark = 0;
 473         e->dfhe_p = NULL;
 474         e->dfhe_child = NULL;
 475         e->dfhe_left = e;
 476         e->dfhe_right = e;
 477         e->dfhe_data = 0;
 478         return e;
 479 }
 480
 481 static void dfhe_insertafter ( DFibHeapNode * a, DFibHeapNode * b )
 482 {
 483         if ( a == a->dfhe_right )
 484         {
 485                 a->dfhe_right = b;
 486                 a->dfhe_left = b;
 487                 b->dfhe_right = a;
 488                 b->dfhe_left = a;
 489         }
 490         else
 491         {
 492                 b->dfhe_right = a->dfhe_right;
 493                 a->dfhe_right->dfhe_left = b;
 494                 a->dfhe_right = b;
 495                 b->dfhe_left = a;
 496         }
 497 }
 498
 499 static inline void dfhe_insertbefore ( DFibHeapNode * a, DFibHeapNode * b )
 500 {
 501         dfhe_insertafter ( a->dfhe_left, b );
 502 }
 503
 504 static DFibHeapNode * dfhe_remove ( DFibHeapNode * x )
 505 {
 506         DFibHeapNode * ret;
 507
 508         if ( x == x->dfhe_left )
 509         {
 510                 ret = NULL;
 511         }
 512         else
 513         {
 514                 ret = x->dfhe_left;
 515         }
 516
 517         /* fix the parent pointer */
 518         if ( x->dfhe_p != NULL && x->dfhe_p->dfhe_child == x )
 519         {
 520                 x->dfhe_p->dfhe_child = ret;
 521         }
 522
 523         x->dfhe_right->dfhe_left = x->dfhe_left;
 524         x->dfhe_left->dfhe_right = x->dfhe_right;
 525         /* clear out hanging pointers */
 526         x->dfhe_p = NULL;
 527         x->dfhe_left = x;
 528         x->dfhe_right = x;
 529         return ret;
 530 }
 531
 532 static void dfh_checkcons ( DFibHeap * h )
 533 {
 534         IDnum oDl;
 535
 536         /* make sure we have enough memory allocated to "reorganize" */
 537         if ( h->dfh_Dl == -1 || h->dfh_n > ( 1 << h->dfh_Dl ) )
 538         {
 539                 oDl = h->dfh_Dl;
 540
 541                 if ( ( h->dfh_Dl = ceillog2 ( h->dfh_n ) + 1 ) < 8 )
 542                 {
 543                         h->dfh_Dl = 8;
 544                 }
 545
 546                 if ( oDl != h->dfh_Dl )
 547                         { h->dfh_cons = ( DFibHeapNode ** ) realloc ( h->dfh_cons, sizeof * h->dfh_cons * ( h->dfh_Dl + 1 ) ); }
 548
 549                 if ( h->dfh_cons == NULL )
 550                 {
 551                         abort ();
 552                 }
 553         }
 554 }
 555
 556 static int dfh_compare ( DFibHeap * h, DFibHeapNode * a, DFibHeapNode * b )
 557 {
 558         if ( a->dfhe_key < b->dfhe_key )
 559         {
 560                 return -1;
 561         }
 562
 563         if ( a->dfhe_key == b->dfhe_key )
 564         {
 565                 return 0;
 566         }
 567
 568         return 1;
 569 }
 570
 571 static int dfh_comparedata ( DFibHeap * h, Time key, unsigned int data, DFibHeapNode * b )
 572 {
 573         DFibHeapNode a;
 574         a.dfhe_key = key;
 575         a.dfhe_data = data;
 576         return dfh_compare ( h, &a, b );
 577 }
 578
 579 static void dfh_insertel ( DFibHeap * h, DFibHeapNode * x )
 580 {
 581         dfh_insertrootlist ( h, x );
 582
 583         if ( h->dfh_min == NULL || x->dfhe_key < h->dfh_min->dfhe_key )
 584         {
 585                 h->dfh_min = x;
 586         }
 587
 588         h->dfh_n++;
 589 }
 590
 591 Time dfibheap_el_getKey ( DFibHeapNode * node )
 592 {
 593         return node->dfhe_key;
 594 }