cde/programs/dtinfo/DtMmdb/dynhash/bucket.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: bucket.cc /main/3 1996/06/11 17:18:55 cde-hal $
  25  *
  26  * Copyright (c) 1992 HaL Computer Systems, Inc.  All rights reserved.
  27  * UNPUBLISHED -- rights reserved under the Copyright Laws of the United
  28  * States.  Use of a copyright notice is precautionary only and does not
  29  * imply publication or disclosure.
  30  *
  31  * This software contains confidential information and trade secrets of HaL
  32  * Computer Systems, Inc.  Use, disclosure, or reproduction is prohibited
  33  * without the prior express written permission of HaL Computer Systems, Inc.
  34  *
  35  *                         RESTRICTED RIGHTS LEGEND
  36  * Use, duplication, or disclosure by the Government is subject to
  37  * restrictions as set forth in subparagraph (c)(l)(ii) of the Rights in
  38  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  39  *                        HaL Computer Systems, Inc.
  40  *                  1315 Dell Avenue, Campbell, CA  95008
  41  *
  42  */
  43
  44
  45 #include "dynhash/bucket.h"
  46
  47 int bucket::upper_limit;
  48
  49 bucket::bucket(int new_Mj, int owj) : wj(0), Mj(new_Mj), old_wj(owj)
  50 {
  51    k = 19;
  52    data_array = new data_t[2*Mj*Mj];
  53 }
  54
  55 bucket::~bucket()
  56 {
  57    delete [2 * Mj * Mj] data_array;
  58 }
  59
  60 /***********************************************/
  61 // rehash the existing keys and the new key
  62 // 'data'
  63 /***********************************************/
  64 void bucket::rehash_all(data_t& data, shared_t& sh)
  65 {
  66    int j = 0;
  67    int ind = first();
  68    while ( ind != -1 ) {
  69       sh.internal_L[j++] = (*this)(ind);
  70       data_array[ind].marked = false;
  71       next(ind);
  72    }
  73    sh.internal_L[j] = data;
  74
  75    select_h_params(sh);
  76
  77    for ( ind = 0; ind <= j; ind++ ) {
  78        int hash = h(sh.internal_L[ind].key, sh);
  79        data_array[hash] = sh.internal_L[ind];
  80        data_array[hash].marked = true;
  81    }
  82 }
  83
  84 /****************************************/
  85 // select a proper value for parameter k
  86 // sh contains useful variables from the
  87 // first level hash table.
  88 /****************************************/
  89 void bucket::select_h_params(shared_t& sh)
  90 {
  91    Boolean injective = false;
  92    int loops = 0;
  93
  94 /******************************************/
  95 // loop until an injective mapping is found
  96 /******************************************/
  97
  98    while ( injective == false ) {
  99       k = sh.rand_generator.rand() % (sh.p - 1) + 1;
 100       injective = true;
 101       for ( int i=0; i<wj; i++ ) {
 102           int hash = h( sh.internal_L[i].key, sh  );
 103           if ( data_array[hash].marked == false ) {
 104              data_array[hash].marked = true ;
 105           } else {
 106             for ( int j = 0; j<2*Mj*Mj; j++ )
 107                data_array[j].marked = false;
 108             injective = false;
 109             break;
 110           }
 111       }
 112       loops ++;
 113       if ( loops >= 20 ) { // supposedly loop twice
 114          debug(cerr, loops);
 115          debug(cerr, Mj);
 116          debug(cerr, wj);
 117          debug(cerr, k);
 118          for ( int i=0; i<wj; i++ ) {
 119             int hash = h( sh.internal_L[i].key, sh  );
 120             debug(cerr, sh.internal_L[i]);
 121             debug(cerr, hash);
 122          }
 123          throw(boundaryException(1, 20, loops));
 124       }
 125    }
 126 }
 127
 128 /************************************************/
 129 // insert
 130 /************************************************/
 131 Boolean bucket::insert(data_t& data, shared_t& sh)
 132 {
 133    wj++;
 134    int j = h(data.key, sh);
 135
 136    if ( wj <= Mj ) {
 137
 138 /**********************/
 139 // space is enough
 140 /**********************/
 141
 142       if ( data_array[j].marked == false ) {
 143          data_array[j] = data;
 144          data_array[j].marked = true;
 145       } else
 146       if ( data_array[j].key == data.key) {
 147          debug(cerr,  data_array[j]);
 148          debug(cerr,  data);
 149          MESSAGE(cerr, "key is in the set");
 150          return true;
 151       } else
 152          rehash_all(data, sh);
 153
 154       return true;
 155    } else {
 156
 157 /***************************/
 158 // need to double the space
 159 // debug(cerr, "rehash bucket");
 160 // debug(cerr, data.key);
 161 /***************************/
 162
 163       int old_contribute = 2 * old_wj * old_wj;
 164       int new_contribute = 2 * wj * wj;
 165       if ( sh.sum - old_contribute + new_contribute < sh.limit ) {
 166
 167 /**************************************/
 168 // if condition 4 holds, we just rehash
 169 // keys in this table
 170 /**************************************/
 171          sh.sum -= old_contribute;
 172          sh.sum += new_contribute;
 173          old_wj = wj;
 174
 175          data_t *x = new data_t[8*Mj*Mj];
 176
 177          int ind = first();
 178
 179 /********************/
 180 // collect records
 181 /********************/
 182          while ( ind != -1 ) {
 183             x[ind] = (*this)(ind);
 184             next(ind);
 185          }
 186
 187 /*****************************/
 188 // allocate new space
 189 /*****************************/
 190          delete [2*Mj*Mj] data_array;
 191          data_array = x;
 192
 193          Mj *= 2;
 194
 195 /*****************************/
 196 // re-hash keys in this bucket
 197 /*****************************/
 198          rehash_all(data, sh);
 199
 200          return true;
 201
 202       } else {
 203 /*******************************/
 204 // Condition 4 does not hold.
 205 // Return false to signal a
 206 // entire set re-hash.
 207 /*******************************/
 208          return false;
 209       }
 210    }
 211 }
 212
 213 /*******************************/
 214 // compute the hash value
 215 /*******************************/
 216 int bucket::h(int key, shared_t& sh)
 217 {
 218    return ( (abs( k * key )) % (sh.p) ) % (2 * Mj * Mj);
 219 }
 220
 221 /*******************************/
 222 // membership test
 223 /*******************************/
 224 Boolean bucket::member(data_t& data, shared_t& sh)
 225 {
 226    int pos = h( data.key, sh );
 227    if ( data_array[pos].marked == true ) {
 228       data.dt = data_array[pos].dt;
 229
 230       if ( data_array[pos].key == data.key )
 231          return true;
 232       else
 233          return false;
 234
 235    } else {
 236       data.key = -1;
 237       return false;
 238    }
 239 }
 240
 241 /*******************************/
 242 // remove operation
 243 /*******************************/
 244 Boolean bucket::remove(data_t& data, shared_t& sh)
 245 {
 246    int pos = h( data.key, sh );
 247
 248    if ( data_array[pos].marked == true &&
 249         data_array[pos].key == data.key) {
 250
 251       data_array[pos].marked = false;
 252       wj--;
 253       return true;
 254
 255    } else {
 256       MESSAGE(cerr, "+++++++++++++++");
 257       debug(cerr, wj);
 258       debug(cerr, *this);
 259       debug(cerr, data);
 260       debug(cerr, data_array[pos]);
 261       MESSAGE(cerr, "data is not in the key set");
 262       MESSAGE(cerr, "+++++++++++++++");
 263       return false;
 264    }
 265 }
 266
 267 /***********************************************/
 268 // iteration operations
 269 /***********************************************/
 270 int bucket::first()
 271 {
 272    upper_limit = 2 * Mj * Mj;
 273    if ( wj == 0 )
 274       return -1;
 275    else {
 276       int i=0;
 277       while ( data_array[i].marked == false ) {
 278          if ( i >= upper_limit ) {
 279             debug(cerr, i);
 280             debug(cerr, upper_limit);
 281             throw(stringException("hash table is in inconsistent status"));
 282          }
 283          i++;
 284       }
 285       return i;
 286    }
 287 }
 288
 289 data_t& bucket::operator()(int ind)
 290 {
 291    return data_array[ind];
 292 }
 293
 294 void bucket::next(int& ind)
 295 {
 296    for ( int j = ind+1; j < upper_limit; j ++ )
 297       if ( data_array[j].marked == true ) {
 298          ind = j;
 299          return;
 300       }
 301
 302    ind = -1;
 303 }
 304
 305 /***********************************************/
 306 // print operation
 307 /***********************************************/
 308 ostream& operator<<(ostream& out, bucket& bt)
 309 {
 310    int ind = bt.first();
 311    while ( ind != -1 ) {
 312       debug(out, bt(ind));
 313       bt.next(ind);
 314    }
 315    return out;
 316 }