cde/programs/dtinfo/DtMmdb/diskhash/disk_hash.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: disk_hash.cc /main/5 1996/07/18 14:28:19 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 "diskhash/disk_hash.h"
  52 #include "api/transaction.h"
  53
  54 extern transaction* g_transac;
  55
  56 int dsteps[] = { 2, 3, 5, 7, 11, 13, 17, 21, 23, 29, 31 };
  57 int no_dsteps;
  58
  59 #define KPB     20      // keys per bucket
  60 #define REHASHS  5      // number of rehashs in a row with
  61                         // fixed bucket size
  62 #define TOP_LEVEL_PARAMS (sizeof(k) + sizeof(p) + sizeof(M) + \
  63                           sizeof(n) + sizeof(v))
  64
  65 //static buffer buf(LBUFSIZ);
  66
  67 disk_hash::disk_hash(page_storage* store, int prime, int expected_n) :
  68 index_agent(), key_store(store), buf(store -> aux_buf())
  69 {
  70    if ( g_transac ) {
  71       g_transac -> book(store);
  72    }
  73
  74    buf.set_swap_order(store -> swap_order());
  75
  76    rand_generator.seed();
  77    no_dsteps = sizeof(dsteps) / sizeof(int);
  78
  79    init_params(prime, expected_n);
  80
  81    bucket_vector = new bucket_array(M+v, store);
  82    hash_vector = new void_ptr_array(2*MAX(expected_n, (int) n));
  83
  84    k_vector = new void_ptr_array(M+v);
  85    r_vector = new void_ptr_array(M+v);
  86
  87    k_vector -> reset_vptr(voidPtr(1));
  88
  89 }
  90
  91 disk_hash::~disk_hash()
  92 {
  93    delete bucket_vector;
  94    delete hash_vector;
  95
  96    delete k_vector;
  97    delete r_vector;
  98 }
  99
 100 void disk_hash::init_params(int prime, int expected_n)
 101 {
 102    int pgs = key_store -> pages();
 103
 104    if ( pgs > 0 ) {
 105       if ( (*key_store)(1, page_storage::READ) -> count() != 2 ) {
 106          throw(stringException("corruptted primary bucket"));
 107       }
 108
 109 /////////////////////////////////
 110 // read in params from the store
 111 /////////////////////////////////
 112       buf.reset();
 113
 114       (*key_store)(1, page_storage::READ) -> get(1, buf);
 115
 116       buf.get(k).get(p).get(M).get(n).get(v);
 117
 118     } else {
 119 ///////////////////////////////////////
 120 // init the store. bucket 1 is reserved
 121 // for top level function params
 122 ///////////////////////////////////////
 123       set_p(prime);
 124       set_k(rand_generator.rand());
 125       set_M(MAX(1, expected_n/KPB));
 126       set_v(MAX(1, M/4));
 127       set_n(0);
 128
 129       key_store -> add_page_frames(1);
 130
 131       int slot_num; char* z;
 132       (*key_store)(1, page_storage::WRITE) ->
 133          alloc_slot(slot_num, TOP_LEVEL_PARAMS, z);
 134
 135       if ( slot_num != 1 ) {
 136          throw(stringException("corruptted primary bucket"));
 137       }
 138
 139       sync_params();
 140    }
 141 }
 142
 143 void disk_hash::sync_params()
 144 {
 145    buf.reset();
 146    buf.put(k).put(p).put(M).put(n).put(v);
 147    (*key_store)(1, page_storage::WRITE) -> update_slot(1, buf);
 148 }
 149
 150 void disk_hash::clean()
 151 {
 152    throw(stringException("void disk_hash::clean(): not implemented yet"));
 153 }
 154
 155 ///////////////////////////////////////////////////////////////
 156 // rehash all keys
 157 ///////////////////////////////////////////////////////////////
 158 Boolean disk_hash::rehash(data_t& w)
 159 {
 160 //MESSAGE(cerr, "REHASH:");
 161    char tmp_name[PATHSIZ];
 162    snprintf(tmp_name, sizeof(tmp_name), "%s.tmp", key_store -> my_name());
 163
 164    fstream pool(form("%s/%s", key_store -> my_path(), tmp_name),
 165                 ios::in | ios::out
 166                );
 167
 168    for ( int i=0; i<bucket_vector -> count(); i++ ) {
 169       pool << bucket_vector -> get_bucket(i);
 170    }
 171    pool << w;
 172
 173
 174    Boolean ok = false;
 175
 176    for ( int rehashs=0; rehashs<REHASHS; rehashs++ ) {
 177
 178 /////////////////////
 179 // adjust params
 180 /////////////////////
 181       int old_M = M;
 182       int old_v = v;
 183
 184       set_M(MAX(n/KPB, 2*M));
 185       set_v(M/4);
 186
 187       int delta = M + v - old_M - old_v;
 188
 189       k_vector -> expandWith(delta);
 190       r_vector -> expandWith(delta);
 191
 192 //////////////////////////////////////////
 193 // expand the buckets and the hash table
 194 //////////////////////////////////////////
 195       bucket_vector -> expandWith(MAX(0, M+v - bucket_vector -> count()));
 196       hash_vector -> expandWith(MAX(0, 2*n - hash_vector -> count()));
 197
 198 /////////////////////
 199 // clean buckets
 200 /////////////////////
 201       for ( int i=0; i<bucket_vector -> count(); i++ ) {
 202          bucket_vector -> get_bucket(i).remove_all();
 203       }
 204
 205       if ( _rehash(pool) == true ) {
 206          ok = true;
 207          break;
 208       }
 209    }
 210
 211    if ( ok == false )
 212       throw(stringException("rehash() failed"));
 213
 214    del_file(tmp_name, key_store -> my_path());
 215
 216    return true;
 217 }
 218
 219 Boolean disk_hash::_rehash(fstream& pool)
 220 {
 221    pool.clear(); pool.seekg(0, ios::beg);
 222
 223    hash_vector -> reset_vptr(voidPtr(0));
 224    k_vector -> reset_vptr(voidPtr(1));
 225    r_vector -> reset_vptr(voidPtr(0));
 226
 227    set_k(rand_generator.rand());
 228
 229    data_t x((char*)0, 0, 0);
 230
 231    while ( pool >> x ) {
 232       if ( _insert(x, false) == false )
 233          return false;
 234    }
 235
 236    return true;
 237 }
 238
 239 /************************************/
 240 // insert
 241 /************************************/
 242 Boolean disk_hash::insert(data_t& w)
 243 {
 244    if ( _insert(w, true) == false )
 245       throw(stringException("disk_hash::insert() failed"));
 246
 247    n++;
 248    sync_params();
 249
 250    return true;
 251 }
 252
 253 Boolean disk_hash::_insert(data_t& w, Boolean rehash_if_fail)
 254 {
 255    int hash = w.bucket_num(k, p, M);
 256
 257 //int hash = w.key.int_key;
 258 //debug(cerr, hash);
 259
 260    disk_bucket& b = bucket_vector -> get_bucket(hash);
 261
 262    int slot_num = b.insert(&w);
 263
 264    if ( slot_num != 0 ) {
 265       caching(b, w, slot_num);
 266    } else {
 267 ///////////////////////////////////
 268 // insert into the overflow bucket
 269 ///////////////////////////////////
 270
 271 //MESSAGE(cerr, "INSERT to overflow buckets");
 272 //debug(cerr, hash);
 273
 274       for ( hash %= v; hash < (int) v; hash++ ) {
 275
 276          disk_bucket& overflowb = bucket_vector -> get_bucket(hash+M);
 277
 278          slot_num = overflowb.insert(&w);
 279
 280          if ( slot_num != 0 ) {
 281            caching(overflowb, w, slot_num);
 282            break;
 283          }
 284       }
 285
 286       if ( slot_num == 0 && rehash_if_fail == true )
 287          return rehash(w);
 288    }
 289
 290    if ( slot_num != 0 )
 291       return true;
 292    else
 293       return false;
 294 }
 295
 296 void disk_hash::caching(disk_bucket& b, data_t& w, int slot_num)
 297 {
 298 //debug(cerr, b.bnum());
 299 //debug(cerr, k_vector -> count());
 300
 301    int kv = int((long)(*k_vector)[b.bnum()]);
 302    int rv = int((long)(*r_vector)[b.bnum()]);
 303
 304 ///////////////////////////////////////////
 305 // cache all keys in the bycket except w.
 306 // In fact, only need to cache keys whose
 307 // hash vector slots have been updated.
 308 // It is to be enhanced.
 309 ///////////////////////////////////////////
 310
 311    int ind = b.first();
 312    while ( ind != 0 && ind != slot_num ) {
 313
 314       data_t* x = b(ind);
 315
 316       if ( x ) {
 317          hash_vector -> insert(
 318                    (voidPtr)(size_t)ind,
 319                    x -> slot_num(kv, rv, p, hash_vector -> count())
 320                               );
 321       }
 322
 323       delete x;
 324
 325       b.next(ind);
 326    }
 327
 328 ////////////////////////////////////////
 329 // cache w. it is always in the cache.
 330 // others may be overwritten.
 331 ////////////////////////////////////////
 332    hash_vector -> insert(
 333          (voidPtr)(size_t)slot_num,
 334          w.slot_num(kv, rv, p, hash_vector -> count())
 335                         );
 336 }
 337
 338 /******************************************/
 339 // remove operation
 340 /******************************************/
 341 Boolean disk_hash::remove(data_t& w)
 342 {
 343    int slot_num;
 344    disk_bucket* b = 0;
 345    if ( member(w, b, slot_num) == true ) {
 346
 347       b -> remove(slot_num);
 348
 349       n--;
 350       sync_params();
 351
 352       return true;
 353    } else
 354       return false;
 355 }
 356
 357 Boolean disk_hash::member(data_t& w)
 358 {
 359 //MESSAGE(cerr, "disk_hash::member():");
 360 //asciiOut(cerr);
 361 //MESSAGE(cerr, "+++++++++++++");
 362    disk_bucket* b = 0;
 363    int slot_num;
 364    return member(w, b, slot_num);
 365 }
 366
 367 Boolean disk_hash::member(data_t& w, disk_bucket*& b, int& slot_num) const
 368 {
 369    int hash = w.bucket_num(k, p, M);
 370
 371 //int hash = w.key.int_key;
 372 //debug(cerr, hash);
 373
 374    b = &bucket_vector -> get_bucket(hash);
 375
 376    int kv = int((long)(*k_vector)[b -> bnum()]);
 377    int rv = int((long)(*r_vector)[b -> bnum()]);
 378
 379    slot_num =
 380      int((long)(*hash_vector)[w.slot_num(kv, rv, p, hash_vector -> count())]);
 381
 382 //debug(cerr, slot_num);
 383
 384    if ( b -> member(w, slot_num) == true )
 385       return true;
 386
 387    if ( b -> overflow() == true ) {
 388
 389       for ( hash %= v; hash < (int) v; hash++ ) {
 390
 391          b = &bucket_vector -> get_bucket(hash+M);
 392
 393          if ( b -> member(w, slot_num) == true ) {
 394             return true;
 395          }
 396       }
 397    }
 398
 399    return false;
 400 }
 401
 402 int disk_hash::first_bucket()
 403 {
 404    return ( M > 0 ) ? 0 : -1;
 405 }
 406
 407 disk_bucket* disk_hash::get_bucket(int& ind)
 408 {
 409    return &bucket_vector -> get_bucket(ind);
 410 }
 411
 412 void disk_hash::next_bucket(int& ind)
 413 {
 414    ind = ( ind >= (int)(M+v-1) ) ? -1 : (ind+1);
 415 }
 416
 417
 418 /*******************************************************/
 419 // print operation
 420 /*******************************************************/
 421 ostream& disk_hash::asciiOut(ostream& out)
 422 {
 423    int ind = first_bucket();
 424
 425    while ( ind != -1 ) {
 426
 427 //MESSAGE(cerr, "New Bucket:");
 428 //debug(cerr, ind);
 429       disk_bucket* bucket = get_bucket(ind);
 430
 431       if ( bucket ) {
 432          out << *bucket;
 433       }
 434
 435       next_bucket(ind);
 436    }
 437
 438    return out;
 439 }
 440
 441 istream& disk_hash::asciiIn(istream& in)
 442 {
 443    data_t actor;
 444
 445    while ( in >> actor ) {
 446       _insert(actor, true);
 447       n++;
 448    }
 449
 450    sync_params();
 451
 452    return in;
 453 }
 454
 455 ostream& disk_hash::asciiOut(ostream& out, print_func_ptr_t print_f)
 456 {
 457
 458    int ind = first_bucket();
 459
 460    while ( ind != -1 ) {
 461
 462       disk_bucket* bucket = get_bucket(ind);
 463
 464       if ( bucket ) {
 465          bucket -> asciiOut(out, print_f);
 466       }
 467
 468       next_bucket(ind);
 469    }
 470
 471    return out;
 472 }
 473
 474 void disk_hash::out_params()
 475 {
 476    debug(cerr, k);
 477    debug(cerr, p);
 478    debug(cerr, M);
 479    debug(cerr, v);
 480    debug(cerr, n);
 481 }