cde/programs/dtinfo/DtMmdb/hmphf/buckets.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: buckets.cc /main/3 1996/06/11 17:19:53 cde-hal $
  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
  52 #include "hmphf/buckets.h"
  53
  54 bucket::bucket(char* key, int orig_position, Boolean copy) :
  55    v_no_keys(1),
  56    v_count(0),
  57    v_control_bit(-1),
  58    v_g_value(0),
  59    v_orig_pos(orig_position)
  60 {
  61
  62    char* x = 0;
  63    int len;
  64
  65    switch (copy) {
  66      case true:
  67        len = strlen(key);
  68        x = new char[len + 1];
  69        *((char *) memcpy(x, key, len) + len) = '\0';
  70        break;
  71      case false:
  72        x = key;
  73        break;
  74    }
  75    key_ptr = new slist_void_ptr_cell(x);
  76 }
  77
  78 bucket::~bucket()
  79 {
  80    slist_void_ptr_cell *lp = key_ptr;
  81    slist_void_ptr_cell* tmp_lp = 0;
  82
  83    while ( lp ) {
  84
  85       tmp_lp = lp;
  86       lp = (slist_void_ptr_cell*)(lp -> v_succ);
  87       delete tmp_lp;
  88    }
  89 }
  90
  91 int bucket::add_key(char* key, Boolean copy)
  92 {
  93    char *x = 0;
  94    int len;
  95
  96    switch (copy) {
  97      case true:
  98        len = strlen(key);
  99        x = new char[len + 1];
 100        *((char *) memcpy(x, key, len) + len) = '\0';
 101        break;
 102      case false:
 103        x = key;
 104        break;
 105    }
 106
 107    slist_void_ptr_cell* z = new slist_void_ptr_cell(x);
 108
 109     z -> v_succ = key_ptr;
 110     key_ptr = z;
 111
 112     v_no_keys++;
 113     return v_no_keys;
 114 }
 115
 116 ostream& operator<<(ostream& out, bucket& bt)
 117 {
 118    slist_void_ptr_cell *lp = bt.key_ptr;
 119
 120    while ( lp ) {
 121
 122       out << ((char*)(lp -> void_ptr())) << " ";
 123       lp = (slist_void_ptr_cell*)(lp -> v_succ);
 124
 125    }
 126    out << "\n";
 127    return out;
 128 }
 129
 130 ////////////////////////////////////////////////////
 131 //
 132 //
 133 ////////////////////////////////////////////////////
 134
 135 //buckets::buckets(char* key_file, params& pms) :
 136
 137 buckets::buckets(char** keys, params& pms) :
 138 v_no_buckets(pms.v_b), v_max_bucket_sz(0),
 139 rnd(pms.v_seed),
 140 b_convertor(pms.v_n, 128, rnd),
 141 h_convertor(pms.v_n, 128, rnd)
 142 {
 143    v_bucket_array = new bucketPtr[v_no_buckets];
 144
 145    unsigned int i;
 146    for ( i=0; i < (unsigned int) v_no_buckets; v_bucket_array[i++] = 0);
 147
 148 //debug(cerr, pms);
 149
 150    int hash, k;
 151    for ( i=0; i<pms.v_n; i++ ) {
 152
 153 //debug(cerr, keys[i]);
 154       hash = bucket_num(keys[i], pms);
 155
 156       if ( v_bucket_array[hash] == 0 ) {
 157          v_bucket_array[hash] = new bucket(keys[i], hash, false);
 158          k = 1;
 159       } else {
 160          k = v_bucket_array[hash] -> add_key(keys[i], false);
 161       }
 162
 163       v_max_bucket_sz = MAX(v_max_bucket_sz, k);
 164    }
 165
 166    sort_by_size();
 167 }
 168
 169 buckets::~buckets()
 170 {
 171    for ( int i=0; i<v_no_buckets; i++ )
 172       delete v_bucket_array[i];
 173
 174    delete v_bucket_array;
 175 }
 176
 177 void buckets::set_control_bit(int cb)
 178 {
 179    for ( int i=0; i<v_no_buckets; i++ ) {
 180       if ( (*this)[i] )
 181          (*this)[i] -> set_control_bit(cb);
 182    }
 183 }
 184
 185 int buckets::bucket_num(char* k, params& pms)
 186 {
 187 //MESSAGE(cerr, "bucket_num");
 188 //debug(cerr, k);
 189    int sum = b_convertor.atoi(k, strlen(k), pms.v_r, pms.v_n);
 190
 191 //debug(cerr, sum);
 192
 193    if ( sum < (int) pms.v_p1 ) {
 194       sum %= pms.v_p2;
 195    } else {
 196       sum %= (pms.v_b - pms.v_p2);
 197       sum += pms.v_p2;
 198    }
 199
 200 //debug(cerr, sum);
 201
 202    return sum;
 203 }
 204
 205 //int buckets::hash_value(char* k, int offset, int range)
 206 //{
 207 ///*
 208 //MESSAGE(cerr, "hash_value");
 209 //debug(cerr, k);
 210 //*/
 211 ////debug(cerr, strlen(k));
 212 //
 213 //
 214 //
 215 ///*
 216 //debug(cerr, offset+1);
 217 //debug(cerr, range);
 218 //*/
 219 //   int hv = h_convertor.atoi(k, strlen(k), offset+1, range);
 220 //
 221 ////debug(cerr, hv);
 222 //
 223 ///*
 224 //if ( strcmp(k, "mphf_funcs.h") == 0 ||
 225 //     strcmp(k, "mmdb_fast_mphf") == 0 ) {
 226 //debug(cerr, k);
 227 //debug(cerr, offset);
 228 //debug(cerr, range);
 229 //debug(cerr, hv);
 230 //}
 231 //*/
 232 //
 233 //   return hv;
 234 //}
 235
 236 void buckets::sort_by_size()
 237 {
 238 //MESSAGE(cerr, "sort()");
 239    int* links = new int[v_no_buckets];
 240    int i;
 241    for ( i=0; i<v_no_buckets; links[i++]=-1 );
 242
 243    int* sizes = new int[v_max_bucket_sz+1];
 244    for ( i=0; i<v_max_bucket_sz+1; sizes[i++]=-1 );
 245
 246 // arrage buckets according to their size
 247    int x;
 248    for ( i = 0; i < v_no_buckets; i++ ) {
 249
 250       if ( v_bucket_array[i] == 0 )
 251          continue;
 252
 253       x = v_bucket_array[i] -> v_no_keys;
 254
 255       links[i] = sizes[x];
 256
 257       sizes[x] = i;
 258    }
 259
 260    bucketPtr* new_bkt_array = new bucketPtr[v_no_buckets];
 261
 262    int j=0;
 263    int idx;
 264    for ( i = v_max_bucket_sz; i >= 0; i-- ) {
 265
 266       if ( sizes[i] == -1 )
 267         continue;
 268
 269       idx = sizes[i];
 270
 271 //debug(cerr, i);
 272       while ( idx != -1 ) {
 273
 274          new_bkt_array[j++] = v_bucket_array[idx];
 275
 276 //debug(cerr, new_bkt_array[j-1] -> v_no_keys);
 277 //debug(cerr, *new_bkt_array[j-1]);
 278
 279          v_bucket_array[idx] = 0;
 280
 281          idx = links[idx];
 282       }
 283    }
 284
 285    for ( ; j<v_no_buckets; new_bkt_array[j++] = 0 );
 286
 287    delete sizes;
 288    delete links;
 289
 290    delete v_bucket_array;
 291    v_bucket_array = new_bkt_array;
 292 }
 293
 294
 295 /*************************************************/
 296 /* return -1 if no more pattern can be generated */
 297 /* return 0 if a pattern is generated            */
 298 /*************************************************/
 299 int
 300 buckets::get_pattern(int idx, int_pattern& pat, params& pms)
 301 {
 302
 303    v_bucket_array[idx] -> v_control_bit++;
 304    for ( ; v_bucket_array[idx] -> v_control_bit<2 ;
 305            v_bucket_array[idx] -> v_control_bit ++
 306    ) {
 307
 308       if ( use_current_params(idx, pat, pms) == 0 )
 309           return 0;
 310
 311    }
 312    return -1;
 313 }
 314
 315 int
 316 buckets::use_current_params(int idx, int_pattern& pat,
 317                             params& pms, Boolean use_g_value)
 318 {
 319    int i = 0;
 320    slist_void_ptr_cell *lp = v_bucket_array[idx] -> key_ptr;
 321
 322    while ( lp ) {
 323
 324
 325 //debug(cerr, (char*)(lp -> void_ptr()));
 326 //cerr << (char*)(lp -> void_ptr()) << "\n";
 327
 328      if ( use_g_value == false ) {
 329         pat.insert(
 330             hash_value( ((char*)(lp -> void_ptr())),
 331                  pms.v_r + v_bucket_array[idx] -> v_control_bit,
 332                  pms.v_n
 333                       ),
 334          i++
 335                   );
 336      } else {
 337
 338 //cerr << (char*)(lp -> void_ptr()) << "\n";
 339 //debug(cerr, pms.r + v_bucket_array[idx] -> v_control_bit);
 340 /*
 341 debug(cerr, ((ostring*)(lp -> void_ptr())) -> get());
 342 int from_tbl1 =  hash_value(
 343                  ((char*)(lp -> void_ptr())),
 344                  pms.r + v_bucket_array[idx] -> v_control_bit,
 345                  pms.n
 346                  );
 347
 348 debug(cerr, from_tbl1);
 349 debug(cerr, v_bucket_array[idx] -> v_g_value);
 350 */
 351
 352          pat.insert(
 353            (
 354                hash_value(
 355                  ((char*)(lp -> void_ptr())),
 356                  pms.v_r + v_bucket_array[idx] -> v_control_bit,
 357                  pms.v_n
 358                          )
 359                +
 360                v_bucket_array[idx] -> v_g_value
 361            ) % pms.v_n,
 362            i++
 363           );
 364       }
 365       lp = (slist_void_ptr_cell*)(lp -> v_succ);
 366    }
 367
 368 //debug(cerr, v_bucket_array[idx] -> no_keys());
 369    pat.reset_elmts(v_bucket_array[idx] -> no_keys());
 370
 371 //debug(cerr, pat);
 372
 373    return pat.duplicate();
 374 }
 375
 376 ostream& operator<<(ostream& out, buckets& bts)
 377 {
 378    for ( int i=0; i<bts.no_buckets(); i++ )
 379       if ( bts[i] ) {
 380          debug(cerr, bts[i] -> orig_pos());
 381          debug(out, *bts[i]);
 382       }
 383
 384    return out;
 385 }
 386