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: bucket.h /main/3 1996/06/11 17:19:00 cde-hal $
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.
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.
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
45 /***************************************************************/
47 //Implementation of the dynamic perfect hashing algorithm, based on:
49 // "Dynamic Perfect Hashing: Upper and Lower Bounds"
53 // M. Dietzfelbinger, A. Karlin, K. Mehlhorn,
54 // F. Meyer auf der Heider, H. Rohnert and
60 /***************************************************************/
63 /***************************************************************/
64 // Programmer: QiFan Chen
65 // Date: June 14, 1992
66 // Language: C++ (2.0)
67 // Machine: SUN SPARCstation IPC
68 /***************************************************************/
73 #include "utility/funcs.h"
74 #include "utility/prandom.h"
75 #include "dynhash/data.h"
78 /**************************************************************/
79 // define a data object that is shared by the first
80 // and the second level hash functions
81 /**************************************************************/
84 prandom rand_generator; // rand generator
85 int p; // prime number p
86 int sum; // the value of the lhs of condition 4
87 int limit; // the value of the rhs of condition 4
88 data_t* internal_L; // the list representation
91 /****************************/
92 // A bucket object forms a
93 // second level hash function
94 /****************************/
98 static int upper_limit; // set to 2*Mj*Mj by first()
101 int k; // valye k used in H_{{2M_j}^2}()
102 int Mj; // size window
103 int wj; // keys in the bucket
104 int old_wj; // value of wj after a memory allocation
105 data_tPtr data_array; // key array
107 void rehash_all(data_t& dt, shared_t&); // rehash all keys
108 void select_h_params(shared_t&); // select the parameter k
111 bucket(int new_Mj, int old_wj);
114 int h(int key, shared_t&); // hash function H_{{2M_j}^2}()
115 int M_size() { return Mj; }; // the value of Mj
116 int wj_size() { return wj; }; // the value of wj
118 Boolean insert(data_t& dt, shared_t&); // insert a key
119 Boolean remove(data_t& dt, shared_t&); // remove a key
120 Boolean member(data_t& dt, shared_t&); // member test
122 int first(); // iterate over all keys in
123 data_t& operator()(int ind); // the bucket
124 void next(int& ind); // terminate condition: -1
126 friend ostream& operator<<(ostream&, bucket&);
129 typedef bucket* bucketPtr;