cde/programs/dtinfo/DtMmdb/index/fast_mphf.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: fast_mphf.cc /main/5 1996/07/18 14:35:57 drk $
  25  *
  26  * Copyright (c) 1992 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 #define NUM_BITS_INCREASES 5
  52
  53 #include "index/fast_mphf.h"
  54
  55 #ifdef C_API
  56 tbl_cache *fast_mphf::v_tbl_cache_ptr = 0;
  57 #define v_tbl_cache (*v_tbl_cache_ptr)
  58 #else
  59 tbl_cache fast_mphf::v_tbl_cache;
  60 #endif
  61
  62 tbl_record::~tbl_record()
  63 {
  64    delete v_tbl0;
  65    delete v_tbl1;
  66 }
  67
  68 tbl_cache::tbl_cache() : f_array(10)
  69 {
  70 }
  71
  72 tbl_cache::~tbl_cache()
  73 {
  74    for ( int v=0; v<f_array.no_elmts(); v++ ) {
  75       delete (tbl_record*)f_array[v];
  76    }
  77 }
  78
  79
  80 void tbl_cache::init_table(int hash_tbl_sz, int seed, atoi_pearson*& t1, atoi_pearson*& t2)
  81 {
  82    int x = f_array.no_elmts();
  83    tbl_record *y = 0;
  84
  85    for ( int v=0; v<x; v++ ) {
  86       y = (tbl_record*)f_array[v];
  87
  88       if ( y -> v_tbl0 != 0 && y -> v_seed == seed )
  89       {
  90
  91        t1 = y -> v_tbl0;
  92        t2 = y -> v_tbl1;
  93
  94 /*
  95 MESSAGE(cerr, "USE cached TABLE!");
  96 debug(cerr, int(v_tbl0));
  97 debug(cerr, int(v_tbl1));
  98 */
  99        return ;
 100      }
 101    }
 102
 103    pm_random z(seed);
 104    t1 = new atoi_pearson(hash_tbl_sz, 128, z);
 105    t2 = new atoi_pearson(hash_tbl_sz, 128, z);
 106
 107    y = new tbl_record(seed, t1, t2);
 108    f_array.insert(y, x);
 109    f_array.reset_elmts(x+1);
 110 }
 111
 112 fast_mphf::fast_mphf(c_code_t c_cd): long_pstring(c_cd),
 113    v_long_string_core_indexed(false),
 114    v_no_ps(0), v_p1(0), v_p2(0),
 115    r(0), v_seed(0), t(0)
 116 {
 117 #ifdef C_API
 118    if ( v_tbl_cache_ptr == 0 ) {
 119      v_tbl_cache_ptr = new tbl_cache;
 120    }
 121 #endif
 122
 123    v_tbl0 = 0;
 124    v_tbl1 = 0;
 125 }
 126
 127 void fast_mphf::init_persistent_info(persistent_info* x)
 128 {
 129    long_pstring::init_persistent_info(x);
 130    if ( get_mode(OLD_OBJECT) == false ) {
 131       v_hash_tbl_sz = 0;
 132       v_no_ps = 0;
 133       v_p1 = 0;
 134       v_p2 = 0;
 135       r = 0;
 136       v_seed = 0;
 137       t = 0;
 138       hash::init_data_member();
 139    }
 140 }
 141
 142 fast_mphf::~fast_mphf()
 143 {
 144 /*
 145    delete v_tbl0;
 146    delete v_tbl1;
 147
 148 #ifdef C_API
 149    if ( v_tbl_cache_ptr ) {
 150       for (int i=0; i<10; i++ )
 151            delete v_tbl_cache_ptr[i];
 152       delete v_tbl_cache_ptr;
 153       v_tbl_cache_ptr = 0;
 154    }
 155 #endif
 156 */
 157 }
 158
 159 io_status fast_mphf::asciiIn(istream& in)
 160 {
 161    in >> v_hash_tbl_sz;
 162    in >> v_no_ps;
 163    in >> v_p1;
 164    in >> v_p2;
 165    in >> r;
 166    in >> v_seed;
 167
 168 /*
 169 MESSAGE(cerr, "in fast_mphf::asciiIn()");
 170 debug(cerr, my_oid());
 171 debug(cerr, v_hash_tbl_sz);
 172 debug(cerr, v_no_ps);
 173 debug(cerr, v_p1);
 174 debug(cerr, v_p2);
 175 debug(cerr, r);
 176 debug(cerr, v_seed);
 177 */
 178
 179    v_key_set_sz = v_hash_tbl_sz ;
 180
 181    in.get(); // skip the '\n' after seed
 182
 183    long_pstring::asciiIn(in);
 184
 185    if ( v_key_set_sz > 0 ) {
 186       t = (int)(flog2(v_key_set_sz)) + 1; // bits of each g value.
 187       if ( floor(flog2(v_key_set_sz)) < flog2(v_key_set_sz) )
 188          t++;
 189
 190 //MESSAGE(cerr, "compacted array:");
 191 //debug(cerr, long_pstring::size());
 192
 193 //for (int z=0; z<long_pstring::size()/4; z++) {
 194 // cerr << ((unsigned*)long_pstring::get())[z] << " ";
 195 //}
 196 //cerr << "\n";
 197
 198
 199       v_hash_func_sz = v_no_ps*sizeof(unsigned)+128*2+6*sizeof(int);
 200
 201       init_map_tbls();
 202
 203    } else {
 204       v_hash_func_sz = 0;
 205       t = 0;
 206    }
 207
 208    set_mode(UPDATE, true);
 209
 210    return done;
 211 }
 212
 213 Boolean fast_mphf::init_map_tbls()
 214 {
 215 /*
 216 MESSAGE(cerr, "in fast_mphf::init_map_tbls()");
 217 debug(cerr, (void*)this);
 218 debug(cerr, my_oid());
 219 debug(cerr, v_key_set_sz);
 220 debug(cerr, v_hash_tbl_sz);
 221 debug(cerr, int(this));
 222 debug(cerr, v_no_ps);
 223 debug(cerr, v_p1);
 224 debug(cerr, v_p2);
 225 debug(cerr, r);
 226 debug(cerr, v_seed);
 227 debug(cerr, t);
 228 //debug(cerr, (void*)&v_tbl_cache);
 229 */
 230
 231
 232
 233   if ( v_key_set_sz > 0 ) {
 234      v_tbl_cache.init_table(v_hash_tbl_sz, v_seed, v_tbl0, v_tbl1);
 235   }
 236
 237    //long_pstring::init_run_data();
 238
 239    return true;
 240 }
 241
 242 int fast_mphf::hashTo(const key_type& k)
 243 {
 244    if ( v_long_string_core_indexed == false ) {
 245       v_long_string_core_indexed = true;
 246    }
 247 /*
 248 cerr << "\n";
 249 MESSAGE(cerr, "fast_mphf:: hashTO()");
 250 debug(cerr, k);
 251 */
 252
 253
 254    if ( v_hash_tbl_sz == 0 ) {
 255       throw(stringException("hash table empty"));
 256    }
 257
 258    int i = v_tbl0 -> atoi(k.get(), k.size(), r, v_key_set_sz); // for halmphf
 259
 260
 261    if ( i < v_p1 ) {
 262      i %= v_p2;
 263    } else {
 264      i %= v_no_ps - v_p2;
 265      i += v_p2;
 266    }
 267
 268    int gv, c_bit;
 269    gValue(i, gv, c_bit);
 270
 271
 272
 273    //i = v_tbl1 -> atoi(k, c_bit+r+1) + gv;
 274 //debug(cerr, c_bit+r);
 275
 276    i = v_tbl1 -> atoi(k.get(), k.size(), c_bit+r+1, v_hash_tbl_sz) + gv; // for halmphf
 277
 278
 279    return i % v_hash_tbl_sz;
 280 }
 281
 282 int fast_mphf::gValue(int i, int& gvalue, int& ctl_bit)
 283 {
 284    if ( !INRANGE(i, 0, v_no_ps-1) ) {
 285       throw(boundaryException(0, v_no_ps-1, i));
 286    }
 287
 288    int a, b;
 289    unsigned un_compacted, un_compacted1;
 290
 291    a = b = t * i ;
 292    a /=  BITS_IN(unsigned);
 293    b %=  BITS_IN(unsigned);
 294
 295    unsigned value_at_a, value_at_a_plus;
 296 /*
 297 debug(cerr, a);
 298 debug(cerr, b);
 299 debug(cerr, t);
 300 */
 301
 302    char x_buf[10];
 303
 304    long_pstring::extract(a*sizeof(a), (a+1)*sizeof(a), x_buf);
 305
 306    memcpy((char*)&value_at_a, x_buf, sizeof(value_at_a));
 307
 308
 309 //cerr << "Extract: at " << a << "; the int =" << value_at_a << endl;
 310 #ifdef PORTABLE_DB
 311    if ( swap_order() == true )
 312       ORDER_SWAP_UINT(value_at_a);
 313 #endif
 314 //cerr << "after swap " << a << "; the int =" << value_at_a << endl;
 315
 316 //debug(cerr, hex(value_at_a));
 317
 318
 319    if ( BITS_IN(unsigned) - b >= t ) {
 320
 321        un_compacted = getbits(value_at_a, BITS_IN(unsigned) - b, t);
 322
 323    } else {
 324
 325       long_pstring::extract((a+1)*sizeof(a), (a+2)*sizeof(a), x_buf);
 326
 327       memcpy((char*)&value_at_a_plus, x_buf, sizeof(value_at_a_plus));
 328
 329 //cerr << "Extract+1: at " << (a+1) << "; the int =" << value_at_a_plus << endl;
 330 #ifdef PORTABLE_DB
 331       if ( swap_order() == true )
 332          ORDER_SWAP_UINT(value_at_a_plus);
 333 #endif
 334 //cerr << "after swap " << (a+1) << "; the int =" << value_at_a_plus << endl;
 335
 336 //debug(cerr, hex(value_at_a_plus));
 337
 338        un_compacted1 =
 339          getbits(value_at_a, BITS_IN(unsigned) - b, BITS_IN(unsigned) - b);
 340        un_compacted =
 341          getbits(value_at_a_plus, BITS_IN(unsigned), t - BITS_IN(unsigned) + b);
 342        un_compacted1 <<= ( t - BITS_IN(unsigned) + b);
 343        un_compacted |= un_compacted1;
 344    }
 345 //debug(cerr, hex(un_compacted));
 346
 347    ctl_bit = un_compacted & (unsigned)1;
 348    gvalue = un_compacted >> 1;
 349    return 0;
 350 }
 351
 352 Boolean fast_mphf::build(const char *from)
 353 {
 354    fstream in(from, ios::in);
 355    return build(in);
 356 }
 357
 358
 359 Boolean fast_mphf::build(istream& in)
 360 {
 361    int ok = -1;
 362
 363    sorter stor(in);
 364
 365    params pms;
 366
 367    pms.v_n = stor.no_unique_keys();
 368
 369    pms.select_value();
 370
 371    buffer mphf_spec(LBUFSIZ);
 372    //buffer& mphf_spec = get_store() -> aux_buf();
 373    mphf_spec.set_swap_order(swap_order());
 374
 375    int i=0;
 376    while ( i<NUM_BITS_INCREASES && ok != 0 ) {
 377
 378       ok = compute_a_mphf(stor.unique_keys(), pms, mphf_spec);
 379
 380       switch (ok) {
 381
 382           case 0:
 383              break;
 384
 385           case 1:
 386              pms.re_select_value();
 387              break;
 388
 389           case -1:
 390              throw(stringException("finding a mphf failed"));
 391       }
 392
 393       i++;
 394    }
 395
 396    if ( ok != 0 ) {
 397       set_mode(HEALTH, false);
 398       throw(stringException("finding a mphf failed"));
 399    }
 400
 401    istrstream strin(mphf_spec.get_base(), mphf_spec.content_sz());
 402
 403    if ( !strin ) {
 404       throw(streamException(strin.rdstate()));
 405    }
 406
 407    asciiIn(strin);
 408
 409    set_mode(HEALTH, true);
 410
 411    return true;
 412 }
 413
 414 void
 415 fast_mphf::print_mapping(const char *key_file, int option)
 416 {
 417 //debug(cerr, option);
 418    MESSAGE(cerr, "print_mapping()");
 419
 420    char string[LBUFSIZ];
 421    fstream in(key_file, ios::in);
 422
 423    if ( !in ) {
 424      throw(streamException(in.rdstate()));
 425    }
 426
 427    char *hash_table = new char[v_hash_tbl_sz];
 428    for (int i = 0; i < v_hash_tbl_sz; hash_table[i++] = 0 );
 429
 430    ostring lbuf(LBUFSIZ);
 431
 432
 433    while ( in.getline(string, LBUFSIZ, '\n') ) {
 434
 435 //     string[strlen(string)-1] = '\0';
 436
 437 //debug(cerr, string);
 438 //debug(cerr, strlen(string));
 439
 440      lbuf.reset();
 441      lbuf.set(string, strlen(string));
 442
 443      int hash  = hashTo(lbuf) ;
 444
 445      if ( option == 1 ) {
 446         cout << " string = " << string;
 447         cout  << ", hash = " << hash << "\n";
 448      }
 449
 450      if ( hash_table[hash] == 1 )
 451         MESSAGE(cerr, "mapping_print(): panic: mphf hash collision");
 452      else
 453         hash_table[hash] = 1;
 454
 455     in.getline(string, LBUFSIZ, '\n');
 456    }
 457
 458    MESSAGE(cerr, "print_mapping() done");
 459 }
 460
 461 void fast_mphf::print_tbls(ostream& out)
 462 {
 463    debug(out, *v_tbl0);
 464    debug(out, *v_tbl1);
 465 }
 466
 467 void fast_mphf::print_gvalues(ostream& out)
 468 {
 469    int gv, cbit;
 470    for (int i = 0; i<v_no_ps; i++ ) {
 471       out << i;
 472       gValue(i, gv, cbit);
 473       out << " " <<  gv << " " << cbit << "\n";
 474    }
 475 }
 476
 477 int fast_mphf::print_bits(unsigned x, ostream& out)
 478 {
 479    for ( int i=0; i<8*sizeof(unsigned); i++ ) {
 480       if ( BIT_TEST(x, 0x80000000) )
 481         out << "1";
 482       else
 483         out << "0";
 484       x = x << 1;
 485    }
 486    out << "\n";
 487    return 0;
 488 }
 489
 490
 491 int fast_mphf::cdr_sizeof()
 492 {
 493    return long_pstring::cdr_sizeof() + hash::cdr_sizeof() +
 494           6*sizeof(unsigned int);
 495 }
 496
 497 io_status fast_mphf::cdrOut(buffer& buf)
 498 {
 499    long_pstring::cdrOut(buf);
 500    hash::cdrOut(buf);
 501
 502    buf.put(v_no_ps);
 503    buf.put(v_p1);
 504    buf.put(v_p2);
 505    buf.put(r);
 506    buf.put(v_seed);
 507    buf.put(t);
 508
 509    return done;
 510 }
 511
 512 io_status fast_mphf::cdrIn(buffer& buf)
 513 {
 514    long_pstring::cdrIn(buf);
 515    hash::cdrIn(buf);
 516
 517    buf.get(v_no_ps);
 518    buf.get(v_p1);
 519    buf.get(v_p2);
 520    buf.get(r);
 521    buf.get(v_seed);
 522    buf.get(t);
 523
 524    init_map_tbls();
 525
 526    return done;
 527 }
 528
 529
 530
 531 MMDB_BODIES(fast_mphf)
 532 HANDLER_BODIES(fast_mphf)