cde/programs/dtinfo/DtMmdb/dynhash/imp_die.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  * $XConsortium: imp_die.C /main/5 1996/08/21 15:52:00 drk $
  25  *
  26  * Copyright (c) 1993 HAL Computer Systems International, Ltd.
  27  * All rights reserved.  Unpublished -- rights reserved under
  28  * the Copyright Laws of the United States.  USE OF A COPYRIGHT
  29  * NOTICE IS PRECAUTIONARY ONLY AND DOES NOT IMPLY PUBLICATION
  30  * OR DISCLOSURE.
  31  *
  32  * THIS SOFTWARE CONTAINS CONFIDENTIAL INFORMATION AND TRADE
  33  * SECRETS OF HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.  USE,
  34  * DISCLOSURE, OR REPRODUCTION IS PROHIBITED WITHOUT THE
  35  * PRIOR EXPRESS WRITTEN PERMISSION OF HAL COMPUTER SYSTEMS
  36  * INTERNATIONAL, LTD.
  37  *
  38  *                         RESTRICTED RIGHTS LEGEND
  39  * Use, duplication, or disclosure by the Government is subject
  40  * to the restrictions as set forth in subparagraph (c)(l)(ii)
  41  * of the Rights in Technical Data and Computer Software clause
  42  * at DFARS 252.227-7013.
  43  *
  44  *          HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
  45  *                  1315 Dell Avenue
  46  *                  Campbell, CA  95008
  47  *
  48  */
  49
  50
  51 #include "dynhash/imp_die.h"
  52
  53 #ifdef C_API
  54 #include "utility/c_iostream.h"
  55 #else
  56 #include <iostream>
  57 using namespace std;
  58 #endif
  59
  60 int steps[] = { 2, 3, 5, 7, 11, 13, 17, 21, 23, 29, 31, 37, 41, 43, 47, 51 };
  61 int no_steps;
  62
  63 #define PRIME_LEVLE_2 2147483647
  64
  65 imp_die::imp_die(int prime, int expected_n) :
  66 p(prime), H(0), B(0), n(0), bucket_array(0), hash_table(0),
  67 free_list_head(0), collected_records(0)
  68 {
  69    alloc_table(int(2.5*expected_n));
  70    init_table();
  71
  72    rand_generator.seed();
  73    k = rand_generator.rand();
  74
  75    no_steps = sizeof(steps) / sizeof(int);
  76 }
  77
  78 imp_die::~imp_die()
  79 {
  80 //debug(cerr, H);
  81 //debug(cerr, B);
  82 //debug(cerr, n);
  83
  84    for ( int i = 0; i<B; i++ ) {
  85       delete bucket_array[i];
  86    }
  87
  88    bucket_holder* x = free_list_head;
  89    while ( x ) {
  90       bucket_holder* y = x -> next;
  91       delete x;
  92       x = y ;
  93    }
  94
  95    x = collected_records;
  96    while ( x ) {
  97       bucket_holder* y = x -> next;
  98       delete x -> data_ptr;
  99       delete x;
 100       x = y ;
 101    }
 102
 103    delete hash_table;
 104    delete bucket_array ;
 105 }
 106
 107 //**********************************************************
 108 // allocate new memory for the bucket table and hash table.
 109 // H is the size of the bucket table before
 110 // expansion. new\_H is the new size.
 111 //**********************************************************
 112 void imp_die::alloc_table(int new_H)
 113 {
 114    if ( bucket_array ) {
 115       for ( int i = 0; i<B; delete bucket_array[i++] );
 116       delete bucket_array ;
 117    }
 118
 119    B = new_H/2;
 120    bucket_array = new imp_bucketPtr[B];
 121
 122    if ( hash_table ) {
 123       delete hash_table;
 124    }
 125
 126    hash_table = new data_tPtr[new_H];
 127
 128    H = new_H;
 129 }
 130
 131 void imp_die::init_table()
 132 {
 133    int i;
 134    for ( i = 0; i < B; i++ ) {
 135       bucket_array[i] = 0 ;
 136    }
 137    for ( i = 0; i < H; i++ ) {
 138       hash_table[i] = 0;
 139    }
 140 }
 141
 142 void imp_die::clean()
 143 {
 144    n = 0;
 145    collect_all_keys();
 146
 147    int i;
 148    for ( i=0; i<B; i++ ) {
 149       if ( bucket_array[i] ) {
 150          delete bucket_array[i];
 151          bucket_array[i] = 0 ;
 152       }
 153    }
 154
 155    for ( i=0; i<H; i++ )
 156       hash_table[i] = 0;
 157 }
 158
 159 /*****************************/
 160 // collect all keys into
 161 // bcuket_list_head
 162 /*****************************/
 163 void imp_die::collect_all_keys()
 164 {
 165    for ( int i = 0; i < B; i++ )
 166       if ( bucket_array[i] ) {
 167
 168          bucket_holder *x ;
 169          if ( free_list_head ) {
 170             x = free_list_head ;
 171 //debug(cerr, "get from free list");
 172             free_list_head = free_list_head -> next;
 173          } else {
 174 //debug(cerr, "get from new");
 175             x = new bucket_holder;
 176          }
 177 //debug(cerr, int(x));
 178
 179          x -> data_ptr = bucket_array[i] -> remove_all();
 180
 181          delete bucket_array[i];
 182          bucket_array[i] = 0;
 183
 184          x -> next = collected_records;
 185          collected_records = x;
 186       }
 187 }
 188
 189 /*****************************/
 190 // rehash all keys
 191 /*****************************/
 192 Boolean imp_die::rehash()
 193 {
 194    while ( 1 ) {
 195
 196       collect_all_keys();
 197
 198       if ( 2*n > H ) alloc_table(2*H);
 199
 200       init_table();
 201
 202       k = rand_generator.rand();
 203
 204       bucket_holder *x = collected_records;
 205       while ( x ) {
 206
 207          data_t* y = x -> data_ptr;
 208
 209          while ( y ) {
 210
 211             data_t *z = (data_t*)(y -> v_succ);
 212
 213             y -> v_pred = 0;
 214             y -> v_succ = 0;
 215
 216             int hash = y -> bucket_num(k, p, B);
 217
 218             if ( bucket_array[hash] == 0 )
 219                bucket_array[hash] = new imp_bucket;
 220
 221             bucket_array[hash] -> insert(y);
 222
 223             y = z;
 224          }
 225
 226          x = x -> next;
 227       }
 228
 229       free_list_head = collected_records;
 230       collected_records = 0;
 231
 232       Boolean rehash_done = true;
 233
 234       for ( int i = 0; i < B; i++ )
 235          if ( bucket_array[i] ) {
 236             if ( bucket_rehash(i) == false ) {
 237                 debug(cerr, i);
 238                 debug(cerr, *bucket_array[i]);
 239                 rehash_done = false;
 240                 break;
 241                 //throw(stringException("rehash() failed"));
 242             }
 243          }
 244
 245       if ( rehash_done == true )
 246         return true;
 247    }
 248 }
 249
 250 /************************************/
 251 // insert
 252 /************************************/
 253 Boolean imp_die::insert(data_t& v)
 254 {
 255    n++;
 256
 257    int hash = v.bucket_num(k, p, B);
 258
 259    if ( bucket_insert(hash, v) == false )
 260       rehash();
 261
 262    return true;
 263 }
 264
 265 /******************************************/
 266 // remove operation
 267 /******************************************/
 268 Boolean imp_die::remove(data_t& v)
 269 {
 270 MESSAGE(cerr, "imp_die::remove(data_t& v)");
 271    int hash = v.bucket_num(k, p, B);
 272
 273 /*********************************/
 274 // assure the bucket is not empty
 275 /*********************************/
 276    if ( bucket_remove(hash, v) == false )
 277        return false;
 278
 279    n--;
 280
 281 /*********************************/
 282 // delete the bucket if it becomes
 283 // empty
 284 /*********************************/
 285    if ( bucket_array[hash] -> empty() == true ) {
 286       delete bucket_array[hash];
 287       bucket_array[hash] = 0;
 288    }
 289
 290    return true;
 291 }
 292
 293 /*******************************************************/
 294 // first level hash function
 295 /*******************************************************/
 296 int imp_die::h(int key) const
 297 {
 298    return abs( k * key ) % p % B;
 299 }
 300
 301 //static to_print = false;
 302 /****************************************/
 303 // select a proper value for parameter k
 304 /****************************************/
 305 Boolean imp_die::bucket_fix_k(int bucket_num)
 306 {
 307    int loops = 0;
 308
 309    Boolean injective = false;
 310
 311    imp_bucket& x = *bucket_array[bucket_num];
 312
 313 /*
 314 MESSAGE(cerr, "bucket_fix_k()");
 315 debug(cerr, x);
 316
 317 if ( bucket_num == 412 )
 318   to_print = true;
 319 else
 320   to_print = false;
 321 */
 322
 323    while ( injective == false && loops < H ) {
 324
 325       injective = test_injective(x);
 326       if ( injective == false ) {
 327          loops ++;
 328          x.k = abs(rand_generator.rand()) % ( p - 1 ) + 1;
 329       }
 330    }
 331
 332    return true;
 333 }
 334
 335 Boolean imp_die::test_injective(imp_bucket& x)
 336 {
 337 //MESSAGE(cerr, "test_injective()");
 338    long ind_out = x.first();
 339    while ( ind_out != 0 ) {
 340
 341       data_t* out = x(ind_out);
 342
 343 /*
 344 if ( to_print == true ) {
 345 debug(cerr, x.k);
 346 debug(cerr, x.rotate);
 347 debug(cerr, p);
 348 debug(cerr, M);
 349 }
 350 */
 351       int hash_out = out -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 352
 353       long ind_in = ind_out;
 354       x.next(ind_in);
 355
 356       while ( ind_in != 0 ) {
 357
 358          data_t* in = x(ind_in);
 359
 360          int hash_in = in -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 361
 362          if ( hash_out == hash_in ) {
 363
 364 /*
 365 if ( to_print == true )
 366 {
 367       debug(cerr, x);
 368       debug(cerr, ind_in);
 369       debug(cerr, ind_out);
 370       debug(cerr, hash_in);
 371       debug(cerr, hash_out);
 372 }
 373 */
 374
 375             return false;
 376          }
 377
 378          x.next(ind_in);
 379       }
 380
 381       x.next(ind_out);
 382    }
 383
 384    return true;
 385 }
 386
 387 Boolean imp_die::bucket_rotate(int bucket_num)
 388 {
 389    imp_bucket& x = *bucket_array[bucket_num];
 390
 391    int loops = 0;
 392
 393    int z = rand_generator.rand();
 394
 395    x.rotate = z % (H - 1) + 1;
 396    int step = steps[z % no_steps];
 397
 398    Boolean all_fit = false;
 399    int hash;
 400
 401    while ( all_fit == false && loops < H ) {
 402
 403       long ind = x.first();
 404       while ( ind != 0 ) {
 405
 406          data_t* data_ptr = x(ind);
 407          hash = data_ptr -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 408
 409          if ( hash_table[hash] != 0 ) {
 410             long ind1 = x.first();
 411             while ( ind1 != ind ) {
 412
 413                hash = x(ind1) -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 414
 415                hash_table[hash] = 0;
 416
 417                x.next(ind1);
 418             }
 419             loops ++;
 420             x.rotate += step;
 421             break;
 422          }
 423          hash_table[hash] = data_ptr;
 424          x.next(ind);
 425       }
 426       all_fit = ( ind == 0 ) ? true : false;
 427    }
 428
 429    return all_fit ;
 430 }
 431
 432 Boolean imp_die::bucket_insert(int bucket_num, data_t& v)
 433 {
 434    if ( bucket_array[bucket_num] == 0 ) {
 435       bucket_array[bucket_num] = new imp_bucket();
 436    }
 437
 438    imp_bucketPtr x = bucket_array[bucket_num];
 439
 440    data_t* y = 0;
 441
 442    if ( collected_records ) {
 443      bucket_holder* first_list = collected_records;
 444      y = first_list -> data_ptr;
 445
 446      first_list -> data_ptr = (data_t*)(y -> v_succ);
 447
 448      if ( first_list -> data_ptr == 0 ) {
 449         collected_records = collected_records -> next;
 450         delete first_list;
 451      }
 452
 453      *y = v;
 454
 455    } else
 456       y = new data_t(v);
 457
 458    x -> insert(y);
 459    int hash = y -> slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 460
 461    if ( hash_table[hash] == 0 ) {
 462       hash_table[hash] = y;
 463       return true;
 464    }
 465
 466 //*******************************
 467 // clear the hash table entries
 468 //*******************************
 469    long ind = x -> first();
 470    while ( ind ) {
 471       int hash = (*x)(ind) -> slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 472
 473       if ( hash_table[hash] && *hash_table[hash] == *(*x)(ind) )
 474          hash_table[hash] = 0;
 475       x -> next(ind);
 476    }
 477
 478    return bucket_rehash(bucket_num);
 479 /*
 480 debug(cerr, bucket_num);
 481 debug(cerr, int(x));
 482 debug(cerr, int(bucket_array));
 483 debug(cerr, int(bucket_array[bucket_num]));
 484 */
 485
 486 }
 487
 488
 489 //*******************************
 490 // rehash keys in the bucket
 491 //*******************************
 492 Boolean imp_die::bucket_rehash(int bucket_num)
 493 {
 494    bucket_fix_k(bucket_num);
 495    return bucket_rotate(bucket_num);
 496 }
 497
 498 Boolean imp_die::bucket_remove(int bucket_num, data_t& v)
 499 {
 500    imp_bucketPtr x = bucket_array[bucket_num];
 501
 502    if ( x == 0 ) return false;
 503
 504    int hash = v.slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 505
 506    if ( hash_table[hash] && *hash_table[hash] == v ) {
 507
 508       x -> delete_cell(hash_table[hash]);
 509       delete hash_table[hash];
 510       hash_table[hash] = 0;
 511
 512 //MESSAGE(cerr, "afterremove the entry");
 513 //debug(cerr, *x);
 514
 515       return true;
 516    } else
 517       return false;
 518 }
 519
 520 Boolean imp_die::bucket_member(int bucket_num, data_t& v) const
 521 {
 522 /*
 523 debug(cerr, bucket_num);
 524 debug(cerr, v);
 525 */
 526
 527    imp_bucketPtr x = bucket_array[bucket_num];
 528
 529    if ( x == 0 ) {
 530 //MESSAGE(cerr, "empty bucket");
 531 //debug(cerr, int(bucket_array));
 532       return false;
 533    }
 534
 535    int hash = v.slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 536
 537    if ( hash_table[hash] ) {
 538       v.dt = hash_table[hash] -> dt;
 539       if ( *hash_table[hash] == v ) {
 540 /*
 541 MESSAGE(cerr, "hash table entry match");
 542 debug(cerr, int(this));
 543 debug(cerr, v);
 544 debug(cerr, *hash_table[hash]);
 545 */
 546
 547          return true;
 548       } else {
 549          return false;
 550       }
 551    } else {
 552       return false;
 553    }
 554 }
 555
 556 int imp_die::first_bucket()
 557 {
 558    if ( B > 0 )
 559       return 0;
 560    else
 561       return -1;
 562 }
 563
 564 void imp_die::next_bucket(int& ind)
 565 {
 566    if ( ind >= B )
 567       ind = -1;
 568    else
 569       ind++;
 570 }
 571
 572 imp_bucket* imp_die::get_bucket(int& ind)
 573 {
 574    while ( ind < B && bucket_array[ind] == 0 )
 575      ind++;
 576
 577    if ( ind >= B )
 578       return 0;
 579    else
 580       return bucket_array[ind];
 581 }
 582
 583 /*******************************************************/
 584 // print operation
 585 /*******************************************************/
 586 ostream& imp_die::asciiOut(ostream& out)
 587 {
 588    int ind = first_bucket();
 589
 590    while ( ind != -1 ) {
 591
 592       imp_bucket* bucket = get_bucket(ind);
 593
 594       if ( bucket )
 595          out << *bucket;
 596
 597       next_bucket(ind);
 598    }
 599
 600    return out;
 601 }
 602
 603 istream& imp_die::asciiIn(istream& in)
 604 {
 605    data_t actor;
 606
 607    while ( in >> actor ) {
 608       insert(actor);
 609    }
 610
 611    return in;
 612 }
 613
 614 ostream& imp_die::asciiOut(ostream& out, print_func_ptr_t print_f)
 615 {
 616
 617    int ind = first_bucket();
 618
 619    while ( ind != -1 ) {
 620
 621       imp_bucket* bucket = get_bucket(ind);
 622
 623       if ( bucket ) {
 624          bucket -> asciiOut(out, print_f);
 625       }
 626
 627       next_bucket(ind);
 628    }
 629
 630    return out;
 631 }