2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
24 * $XConsortium: imp_die.C /main/5 1996/08/21 15:52:00 drk $
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
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
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.
44 * HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
51 #include "dynhash/imp_die.h"
54 #include "utility/c_iostream.h"
60 int steps[] = { 2, 3, 5, 7, 11, 13, 17, 21, 23, 29, 31, 37, 41, 43, 47, 51 };
63 #define PRIME_LEVLE_2 2147483647
65 imp_die::imp_die(int prime, int expected_n) :
66 p(prime), H(0), B(0), n(0), bucket_array(0), hash_table(0),
67 free_list_head(0), collected_records(0)
69 alloc_table(int(2.5*expected_n));
72 rand_generator.seed();
73 k = rand_generator.rand();
75 no_steps = sizeof(steps) / sizeof(int);
84 for ( int i = 0; i<B; i++ ) {
85 delete bucket_array[i];
88 bucket_holder* x = free_list_head;
90 bucket_holder* y = x -> next;
95 x = collected_records;
97 bucket_holder* y = x -> next;
104 delete bucket_array ;
107 //**********************************************************
108 // allocate new memory for the bucket table and hash table.
109 // H is the size of the bucket table before
110 // expansion. new\_H is the new size.
111 //**********************************************************
112 void imp_die::alloc_table(int new_H)
114 if ( bucket_array ) {
115 for ( int i = 0; i<B; delete bucket_array[i++] );
116 delete bucket_array ;
120 bucket_array = new imp_bucketPtr[B];
126 hash_table = new data_tPtr[new_H];
131 void imp_die::init_table()
134 for ( i = 0; i < B; i++ ) {
135 bucket_array[i] = 0 ;
137 for ( i = 0; i < H; i++ ) {
142 void imp_die::clean()
148 for ( i=0; i<B; i++ ) {
149 if ( bucket_array[i] ) {
150 delete bucket_array[i];
151 bucket_array[i] = 0 ;
155 for ( i=0; i<H; i++ )
159 /*****************************/
160 // collect all keys into
162 /*****************************/
163 void imp_die::collect_all_keys()
165 for ( int i = 0; i < B; i++ )
166 if ( bucket_array[i] ) {
169 if ( free_list_head ) {
171 //debug(cerr, "get from free list");
172 free_list_head = free_list_head -> next;
174 //debug(cerr, "get from new");
175 x = new bucket_holder;
177 //debug(cerr, int(x));
179 x -> data_ptr = bucket_array[i] -> remove_all();
181 delete bucket_array[i];
184 x -> next = collected_records;
185 collected_records = x;
189 /*****************************/
191 /*****************************/
192 Boolean imp_die::rehash()
198 if ( 2*n > H ) alloc_table(2*H);
202 k = rand_generator.rand();
204 bucket_holder *x = collected_records;
207 data_t* y = x -> data_ptr;
211 data_t *z = (data_t*)(y -> v_succ);
216 int hash = y -> bucket_num(k, p, B);
218 if ( bucket_array[hash] == 0 )
219 bucket_array[hash] = new imp_bucket;
221 bucket_array[hash] -> insert(y);
229 free_list_head = collected_records;
230 collected_records = 0;
232 Boolean rehash_done = true;
234 for ( int i = 0; i < B; i++ )
235 if ( bucket_array[i] ) {
236 if ( bucket_rehash(i) == false ) {
238 debug(cerr, *bucket_array[i]);
241 //throw(stringException("rehash() failed"));
245 if ( rehash_done == true )
250 /************************************/
252 /************************************/
253 Boolean imp_die::insert(data_t& v)
257 int hash = v.bucket_num(k, p, B);
259 if ( bucket_insert(hash, v) == false )
265 /******************************************/
267 /******************************************/
268 Boolean imp_die::remove(data_t& v)
270 MESSAGE(cerr, "imp_die::remove(data_t& v)");
271 int hash = v.bucket_num(k, p, B);
273 /*********************************/
274 // assure the bucket is not empty
275 /*********************************/
276 if ( bucket_remove(hash, v) == false )
281 /*********************************/
282 // delete the bucket if it becomes
284 /*********************************/
285 if ( bucket_array[hash] -> empty() == true ) {
286 delete bucket_array[hash];
287 bucket_array[hash] = 0;
293 /*******************************************************/
294 // first level hash function
295 /*******************************************************/
296 int imp_die::h(int key) const
298 return abs( k * key ) % p % B;
301 //static to_print = false;
302 /****************************************/
303 // select a proper value for parameter k
304 /****************************************/
305 Boolean imp_die::bucket_fix_k(int bucket_num)
309 Boolean injective = false;
311 imp_bucket& x = *bucket_array[bucket_num];
314 MESSAGE(cerr, "bucket_fix_k()");
317 if ( bucket_num == 412 )
323 while ( injective == false && loops < H ) {
325 injective = test_injective(x);
326 if ( injective == false ) {
328 x.k = abs(rand_generator.rand()) % ( p - 1 ) + 1;
335 Boolean imp_die::test_injective(imp_bucket& x)
337 //MESSAGE(cerr, "test_injective()");
338 long ind_out = x.first();
339 while ( ind_out != 0 ) {
341 data_t* out = x(ind_out);
344 if ( to_print == true ) {
346 debug(cerr, x.rotate);
351 int hash_out = out -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
353 long ind_in = ind_out;
356 while ( ind_in != 0 ) {
358 data_t* in = x(ind_in);
360 int hash_in = in -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
362 if ( hash_out == hash_in ) {
365 if ( to_print == true )
369 debug(cerr, ind_out);
370 debug(cerr, hash_in);
371 debug(cerr, hash_out);
387 Boolean imp_die::bucket_rotate(int bucket_num)
389 imp_bucket& x = *bucket_array[bucket_num];
393 int z = rand_generator.rand();
395 x.rotate = z % (H - 1) + 1;
396 int step = steps[z % no_steps];
398 Boolean all_fit = false;
401 while ( all_fit == false && loops < H ) {
403 long ind = x.first();
406 data_t* data_ptr = x(ind);
407 hash = data_ptr -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
409 if ( hash_table[hash] != 0 ) {
410 long ind1 = x.first();
411 while ( ind1 != ind ) {
413 hash = x(ind1) -> slot_num(x.k, x.rotate, PRIME_LEVLE_2, H);
415 hash_table[hash] = 0;
423 hash_table[hash] = data_ptr;
426 all_fit = ( ind == 0 ) ? true : false;
432 Boolean imp_die::bucket_insert(int bucket_num, data_t& v)
434 if ( bucket_array[bucket_num] == 0 ) {
435 bucket_array[bucket_num] = new imp_bucket();
438 imp_bucketPtr x = bucket_array[bucket_num];
442 if ( collected_records ) {
443 bucket_holder* first_list = collected_records;
444 y = first_list -> data_ptr;
446 first_list -> data_ptr = (data_t*)(y -> v_succ);
448 if ( first_list -> data_ptr == 0 ) {
449 collected_records = collected_records -> next;
459 int hash = y -> slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
461 if ( hash_table[hash] == 0 ) {
462 hash_table[hash] = y;
466 //*******************************
467 // clear the hash table entries
468 //*******************************
469 long ind = x -> first();
471 int hash = (*x)(ind) -> slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
473 if ( hash_table[hash] && *hash_table[hash] == *(*x)(ind) )
474 hash_table[hash] = 0;
478 return bucket_rehash(bucket_num);
480 debug(cerr, bucket_num);
482 debug(cerr, int(bucket_array));
483 debug(cerr, int(bucket_array[bucket_num]));
489 //*******************************
490 // rehash keys in the bucket
491 //*******************************
492 Boolean imp_die::bucket_rehash(int bucket_num)
494 bucket_fix_k(bucket_num);
495 return bucket_rotate(bucket_num);
498 Boolean imp_die::bucket_remove(int bucket_num, data_t& v)
500 imp_bucketPtr x = bucket_array[bucket_num];
502 if ( x == 0 ) return false;
504 int hash = v.slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
506 if ( hash_table[hash] && *hash_table[hash] == v ) {
508 x -> delete_cell(hash_table[hash]);
509 delete hash_table[hash];
510 hash_table[hash] = 0;
512 //MESSAGE(cerr, "afterremove the entry");
520 Boolean imp_die::bucket_member(int bucket_num, data_t& v) const
523 debug(cerr, bucket_num);
527 imp_bucketPtr x = bucket_array[bucket_num];
530 //MESSAGE(cerr, "empty bucket");
531 //debug(cerr, int(bucket_array));
535 int hash = v.slot_num(x->k, x->rotate, PRIME_LEVLE_2, H);
537 if ( hash_table[hash] ) {
538 v.dt = hash_table[hash] -> dt;
539 if ( *hash_table[hash] == v ) {
541 MESSAGE(cerr, "hash table entry match");
542 debug(cerr, int(this));
544 debug(cerr, *hash_table[hash]);
556 int imp_die::first_bucket()
564 void imp_die::next_bucket(int& ind)
572 imp_bucket* imp_die::get_bucket(int& ind)
574 while ( ind < B && bucket_array[ind] == 0 )
580 return bucket_array[ind];
583 /*******************************************************/
585 /*******************************************************/
586 ostream& imp_die::asciiOut(ostream& out)
588 int ind = first_bucket();
590 while ( ind != -1 ) {
592 imp_bucket* bucket = get_bucket(ind);
603 istream& imp_die::asciiIn(istream& in)
607 while ( in >> actor ) {
614 ostream& imp_die::asciiOut(ostream& out, print_func_ptr_t print_f)
617 int ind = first_bucket();
619 while ( ind != -1 ) {
621 imp_bucket* bucket = get_bucket(ind);
624 bucket -> asciiOut(out, print_f);