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.h>
  57 #endif
  58
  59 int steps[] = { 2, 3, 5, 7, 11, 13, 17, 21, 23, 29, 31, 37, 41, 43, 47, 51 };
  60 int no_steps;
  61
  62 #define PRIME_LEVLE_2 2147483647
  63
  64 imp_die::imp_die(int prime, int expected_n) :
  65 p(prime), H(0), B(0), n(0), bucket_array(0), hash_table(0),
  66 free_list_head(0), collected_records(0)
  67 {
  68    alloc_table(int(2.5*expected_n));
  69    init_table();
  70
  71    rand_generator.seed();
  72    k = rand_generator.rand();
  73
  74    no_steps = sizeof(steps) / sizeof(int);
  75 }
  76
  77 imp_die::~imp_die()
  78 {
  79 //debug(cerr, H);
  80 //debug(cerr, B);
  81 //debug(cerr, n);
  82
  83    for ( int i = 0; i<B; i++ ) {
  84       delete bucket_array[i];
  85    }
  86
  87    bucket_holder* x = free_list_head;
  88    while ( x ) {
  89       bucket_holder* y = x -> next;
  90       delete x;
  91       x = y ;
  92    }
  93
  94    x = collected_records;
  95    while ( x ) {
  96       bucket_holder* y = x -> next;
  97       delete x -> data_ptr;
  98       delete x;
  99       x = y ;
 100    }
 101
 102    delete hash_table;
 103    delete bucket_array ;
 104 }
 105
 106 //**********************************************************
 107 // allocate new memory for the bucket table and hash table.
 108 // H is the size of the bucket table before
 109 // expansion. new\_H is the new size.
 110 //**********************************************************
 111 void imp_die::alloc_table(int new_H)
 112 {
 113    if ( bucket_array ) {
 114       for ( int i = 0; i<B; delete bucket_array[i++] );
 115       delete bucket_array ;
 116    }
 117
 118    B = new_H/2;
 119    bucket_array = new imp_bucketPtr[B];
 120
 121    if ( hash_table ) {
 122       delete hash_table;
 123    }
 124
 125    hash_table = new data_tPtr[new_H];
 126
 127    H = new_H;
 128 }
 129
 130 void imp_die::init_table()
 131 {
 132    for ( int i = 0; i < B; i++ ) {
 133       bucket_array[i] = 0 ;
 134    }
 135    for ( i = 0; i < H; i++ ) {
 136       hash_table[i] = 0;
 137    }
 138 }
 139
 140 void imp_die::clean()
 141 {
 142    n = 0;
 143    collect_all_keys();
 144
 145    for ( int i=0; i<B; i++ ) {
 146       if ( bucket_array[i] ) {
 147          delete bucket_array[i];
 148          bucket_array[i] = 0 ;
 149       }
 150    }
 151
 152    for ( i=0; i<H; i++ )
 153       hash_table[i] = 0;
 154 }
 155
 156 /*****************************/
 157 // collect all keys into
 158 // bcuket_list_head
 159 /*****************************/
 160 void imp_die::collect_all_keys()
 161 {
 162    for ( int i = 0; i < B; i++ )
 163       if ( bucket_array[i] ) {
 164
 165          bucket_holder *x ;
 166          if ( free_list_head ) {
 167             x = free_list_head ;
 168 //debug(cerr, "get from free list");
 169             free_list_head = free_list_head -> next;
 170          } else {
 171 //debug(cerr, "get from new");
 172             x = new bucket_holder;
 173          }
 174 //debug(cerr, int(x));
 175
 176          x -> data_ptr = bucket_array[i] -> remove_all();
 177
 178          delete bucket_array[i];
 179          bucket_array[i] = 0;
 180
 181          x -> next = collected_records;
 182          collected_records = x;
 183       }
 184 }
 185
 186 /*****************************/
 187 // rehash all keys
 188 /*****************************/
 189 Boolean imp_die::rehash()
 190 {
 191    while ( 1 ) {
 192
 193       collect_all_keys();
 194
 195       if ( 2*n > H ) alloc_table(2*H);
 196
 197       init_table();
 198
 199       k = rand_generator.rand();
 200
 201       bucket_holder *x = collected_records;
 202       while ( x ) {
 203
 204          data_t* y = x -> data_ptr;
 205
 206          while ( y ) {
 207
 208             data_t *z = (data_t*)(y -> v_succ);
 209
 210             y -> v_pred = 0;
 211             y -> v_succ = 0;
 212
 213             int hash = y -> bucket_num(k, p, B);
 214
 215             if ( bucket_array[hash] == 0 )
 216                bucket_array[hash] = new imp_bucket;
 217
 218             bucket_array[hash] -> insert(y);
 219
 220             y = z;
 221          }
 222
 223          x = x -> next;
 224       }
 225
 226       free_list_head = collected_records;
 227       collected_records = 0;
 228
 229       Boolean rehash_done = true;
 230
 231       for ( int i = 0; i < B; i++ )
 232          if ( bucket_array[i] ) {
 233             if ( bucket_rehash(i) == false ) {
 234                 debug(cerr, i);
 235                 debug(cerr, *bucket_array[i]);
 236                 rehash_done = false;
 237                 break;
 238                 //throw(stringException("rehash() failed"));
 239             }
 240          }
 241
 242       if ( rehash_done == true )
 243         return true;
 244    }
 245 }
 246
 247 /************************************/
 248 // insert
 249 /************************************/
 250 Boolean imp_die::insert(data_t& v)
 251 {
 252    n++;
 253
 254    int hash = v.bucket_num(k, p, B);
 255
 256    if ( bucket_insert(hash, v) == false )
 257       rehash();
 258
 259    return true;
 260 }
 261
 262 /******************************************/
 263 // remove operation
 264 /******************************************/
 265 Boolean imp_die::remove(data_t& v)
 266 {
 267 MESSAGE(cerr, "imp_die::remove(data_t& v)");
 268    int hash = v.bucket_num(k, p, B);
 269
 270 /*********************************/
 271 // assure the bucket is not empty
 272 /*********************************/
 273    if ( bucket_remove(hash, v) == false )
 274        return false;
 275
 276    n--;
 277
 278 /*********************************/
 279 // delete the bucket if it becomes
 280 // empty
 281 /*********************************/
 282    if ( bucket_array[hash] -> empty() == true ) {
 283       delete bucket_array[hash];
 284       bucket_array[hash] = 0;
 285    }
 286
 287    return true;
 288 }
 289
 290 /*******************************************************/
 291 // first level hash function
 292 /*******************************************************/
 293 int imp_die::h(int key) const
 294 {
 295    return abs( k * key ) % p % B;
 296 }
 297
 298 //static to_print = false;
 299 /****************************************/
 300 // select a proper value for parameter k
 301 /****************************************/
 302 Boolean imp_die::bucket_fix_k(int bucket_num)
 303 {
 304    int loops = 0;
 305
 306    Boolean injective = false;
 307
 308    imp_bucket& x = *bucket_array[bucket_num];
 309
 310 /*
 311 MESSAGE(cerr, "bucket_fix_k()");
 312 debug(cerr, x);
 313
 314 if ( bucket_num == 412 )
 315   to_print = true;
 316 else
 317   to_print = false;
 318 */
 319
 320    while ( injective == false && loops < H ) {
 321
 322       injective = test_injective(x);
 323       if ( injective == false ) {
 324          loops ++;
 325          x.k = abs(rand_generator.rand()) % ( p - 1 ) + 1;
 326       }
 327    }
 328
 329    return true;
 330 }
 331
 332 Boolean imp_die::test_injective(imp_bucket& x)
 333 {
 334 //MESSAGE(cerr, "test_injective()");
 335    long ind_out = x.first();
 336    while ( ind_out != 0 ) {
 337
 338       data_t* out = x(ind_out);
 339
 340 /*
 341 if ( to_print == true ) {
 342 debug(cerr, x.k);
 343 debug(cerr, x.rotate);
 344 debug(cerr, p);
 345 debug(cerr, M);
 346 }
 347 */
 348       int hash_out = out -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 349
 350       long ind_in = ind_out;
 351       x.next(ind_in);
 352
 353       while ( ind_in != 0 ) {
 354
 355          data_t* in = x(ind_in);
 356
 357          int hash_in = in -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 358
 359          if ( hash_out == hash_in ) {
 360
 361 /*
 362 if ( to_print == true )
 363 {
 364       debug(cerr, x);
 365       debug(cerr, ind_in);
 366       debug(cerr, ind_out);
 367       debug(cerr, hash_in);
 368       debug(cerr, hash_out);
 369 }
 370 */
 371
 372             return false;
 373          }
 374
 375          x.next(ind_in);
 376       }
 377
 378       x.next(ind_out);
 379    }
 380
 381    return true;
 382 }
 383
 384 Boolean imp_die::bucket_rotate(int bucket_num)
 385 {
 386    imp_bucket& x = *bucket_array[bucket_num];
 387
 388    int loops = 0;
 389
 390    int z = rand_generator.rand();
 391
 392    x.rotate = z % (H - 1) + 1;
 393    int step = steps[z % no_steps];
 394
 395    Boolean all_fit = false;
 396    int hash;
 397
 398    while ( all_fit == false && loops < H ) {
 399
 400       long ind = x.first();
 401       while ( ind != 0 ) {
 402
 403          data_t* data_ptr = x(ind);
 404          hash = data_ptr -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 405
 406          if ( hash_table[hash] != 0 ) {
 407             long ind1 = x.first();
 408             while ( ind1 != ind ) {
 409
 410                hash = x(ind1) -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
 411
 412                hash_table[hash] = 0;
 413
 414                x.next(ind1);
 415             }
 416             loops ++;
 417             x.rotate += step;
 418             break;
 419          }
 420          hash_table[hash] = data_ptr;
 421          x.next(ind);
 422       }
 423       all_fit = ( ind == 0 ) ? true : false;
 424    }
 425
 426    return all_fit ;
 427 }
 428
 429 Boolean imp_die::bucket_insert(int bucket_num, data_t& v)
 430 {
 431    if ( bucket_array[bucket_num] == 0 ) {
 432       bucket_array[bucket_num] = new imp_bucket();
 433    }
 434
 435    imp_bucketPtr x = bucket_array[bucket_num];
 436
 437    data_t* y = 0;
 438
 439    if ( collected_records ) {
 440      bucket_holder* first_list = collected_records;
 441      y = first_list -> data_ptr;
 442
 443      first_list -> data_ptr = (data_t*)(y -> v_succ);
 444
 445      if ( first_list -> data_ptr == 0 ) {
 446         collected_records = collected_records -> next;
 447         delete first_list;
 448      }
 449
 450      *y = v;
 451
 452    } else
 453       y = new data_t(v);
 454
 455    x -> insert(y);
 456    int hash = y -> slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 457
 458    if ( hash_table[hash] == 0 ) {
 459       hash_table[hash] = y;
 460       return true;
 461    }
 462
 463 //*******************************
 464 // clear the hash table entries
 465 //*******************************
 466    long ind = x -> first();
 467    while ( ind ) {
 468       int hash = (*x)(ind) -> slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 469
 470       if ( hash_table[hash] && *hash_table[hash] == *(*x)(ind) )
 471          hash_table[hash] = 0;
 472       x -> next(ind);
 473    }
 474
 475    return bucket_rehash(bucket_num);
 476 /*
 477 debug(cerr, bucket_num);
 478 debug(cerr, int(x));
 479 debug(cerr, int(bucket_array));
 480 debug(cerr, int(bucket_array[bucket_num]));
 481 */
 482
 483 }
 484
 485
 486 //*******************************
 487 // rehash keys in the bucket
 488 //*******************************
 489 Boolean imp_die::bucket_rehash(int bucket_num)
 490 {
 491    bucket_fix_k(bucket_num);
 492    return bucket_rotate(bucket_num);
 493 }
 494
 495 Boolean imp_die::bucket_remove(int bucket_num, data_t& v)
 496 {
 497    imp_bucketPtr x = bucket_array[bucket_num];
 498
 499    if ( x == 0 ) return false;
 500
 501    int hash = v.slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 502
 503    if ( hash_table[hash] && *hash_table[hash] == v ) {
 504
 505       x -> delete_cell(hash_table[hash]);
 506       delete hash_table[hash];
 507       hash_table[hash] = 0;
 508
 509 //MESSAGE(cerr, "afterremove the entry");
 510 //debug(cerr, *x);
 511
 512       return true;
 513    } else
 514       return false;
 515 }
 516
 517 Boolean imp_die::bucket_member(int bucket_num, data_t& v) const
 518 {
 519 /*
 520 debug(cerr, bucket_num);
 521 debug(cerr, v);
 522 */
 523
 524    imp_bucketPtr x = bucket_array[bucket_num];
 525
 526    if ( x == 0 ) {
 527 //MESSAGE(cerr, "empty bucket");
 528 //debug(cerr, int(bucket_array));
 529       return false;
 530    }
 531
 532    int hash = v.slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
 533
 534    if ( hash_table[hash] ) {
 535       v.dt = hash_table[hash] -> dt;
 536       if ( *hash_table[hash] == v ) {
 537 /*
 538 MESSAGE(cerr, "hash table entry match");
 539 debug(cerr, int(this));
 540 debug(cerr, v);
 541 debug(cerr, *hash_table[hash]);
 542 */
 543
 544          return true;
 545       } else {
 546          return false;
 547       }
 548    } else {
 549       return false;
 550    }
 551 }
 552
 553 int imp_die::first_bucket()
 554 {
 555    if ( B > 0 )
 556       return 0;
 557    else
 558       return -1;
 559 }
 560
 561 void imp_die::next_bucket(int& ind)
 562 {
 563    if ( ind >= B )
 564       ind = -1;
 565    else
 566       ind++;
 567 }
 568
 569 imp_bucket* imp_die::get_bucket(int& ind)
 570 {
 571    while ( ind < B && bucket_array[ind] == 0 )
 572      ind++;
 573
 574    if ( ind >= B )
 575       return 0;
 576    else
 577       return bucket_array[ind];
 578 }
 579
 580 /*******************************************************/
 581 // print operation
 582 /*******************************************************/
 583 ostream& imp_die::asciiOut(ostream& out)
 584 {
 585    int ind = first_bucket();
 586
 587    while ( ind != -1 ) {
 588
 589       imp_bucket* bucket = get_bucket(ind);
 590
 591       if ( bucket )
 592          out << *bucket;
 593
 594       next_bucket(ind);
 595    }
 596
 597    return out;
 598 }
 599
 600 istream& imp_die::asciiIn(istream& in)
 601 {
 602    data_t actor;
 603
 604    while ( in >> actor ) {
 605       insert(actor);
 606    }
 607
 608    return in;
 609 }
 610
 611 ostream& imp_die::asciiOut(ostream& out, print_func_ptr_t print_f)
 612 {
 613
 614    int ind = first_bucket();
 615
 616    while ( ind != -1 ) {
 617
 618       imp_bucket* bucket = get_bucket(ind);
 619
 620       if ( bucket ) {
 621          bucket -> asciiOut(out, print_f);
 622       }
 623
 624       next_bucket(ind);
 625    }
 626
 627    return out;
 628 }