1 |
dpavlin |
604 |
/* |
2 |
|
|
The Malete project - the Z39.2/Z39.50 database framework of OpenIsis. |
3 |
|
|
Version 0.9.x (patchlevel see file Version) |
4 |
|
|
Copyright (C) 2001-2003 by Erik Grziwotz, erik@openisis.org |
5 |
|
|
|
6 |
|
|
This library is free software; you can redistribute it and/or |
7 |
|
|
modify it under the terms of the GNU Lesser General Public |
8 |
|
|
License as published by the Free Software Foundation; either |
9 |
|
|
version 2.1 of the License, or (at your option) any later version. |
10 |
|
|
|
11 |
|
|
This library is distributed in the hope that it will be useful, |
12 |
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 |
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
14 |
|
|
See the GNU Lesser General Public License for more details. |
15 |
|
|
|
16 |
|
|
You should have received a copy of the GNU Lesser General Public |
17 |
|
|
License along with this library; if not, write to the Free Software |
18 |
|
|
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
19 |
|
|
|
20 |
|
|
see README for more information |
21 |
|
|
EOH */ |
22 |
|
|
|
23 |
|
|
/* |
24 |
|
|
$Id: hash.c,v 1.2 2004/03/29 09:35:20 kripke Exp $ |
25 |
|
|
the hashtable |
26 |
|
|
*/ |
27 |
|
|
|
28 |
|
|
#include "../pw/pw.h" |
29 |
|
|
|
30 |
|
|
/* ************************************************************ |
31 |
|
|
private functions |
32 |
|
|
*/ |
33 |
|
|
|
34 |
|
|
/* |
35 |
|
|
add a bucket |
36 |
|
|
*/ |
37 |
|
|
#define HLNEWF( l, t ) do { \ |
38 |
|
|
if ( (l)->fav || lExtend( l, 0, 1 ) ) { \ |
39 |
|
|
Fld *__f = (l)->fld - (l)->fld->tag--; \ |
40 |
|
|
__f->tag = t; \ |
41 |
|
|
__f->val = 0; \ |
42 |
|
|
__f->len = 0; \ |
43 |
|
|
(l)->fav --; \ |
44 |
|
|
} } while(0) |
45 |
|
|
|
46 |
|
|
/* |
47 |
|
|
the cdb hash function ( without h/256 ) |
48 |
|
|
*/ |
49 |
|
|
#define CDB_CALC(i,s) i ^= ( i += i << 5, (int) *s++ ) |
50 |
|
|
|
51 |
|
|
static OPT_INLINE int hs ( const char *s, register int len ) |
52 |
|
|
{ |
53 |
|
|
register int i = 5381, n = (len + 7 ) / 8; |
54 |
|
|
if ( ! len ) return i; |
55 |
|
|
switch ( len % 8 ) { |
56 |
|
|
case 0: do { CDB_CALC(i,s); |
57 |
|
|
case 7: CDB_CALC(i,s); |
58 |
|
|
case 6: CDB_CALC(i,s); |
59 |
|
|
case 5: CDB_CALC(i,s); |
60 |
|
|
case 4: CDB_CALC(i,s); |
61 |
|
|
case 3: CDB_CALC(i,s); |
62 |
|
|
case 2: CDB_CALC(i,s); |
63 |
|
|
case 1: CDB_CALC(i,s); |
64 |
|
|
} while ( --n ); |
65 |
|
|
} |
66 |
|
|
return i; |
67 |
|
|
} /* hs */ |
68 |
|
|
|
69 |
|
|
/* |
70 |
|
|
lookup key in a bucket, if found the corresponding entry is assigned |
71 |
|
|
to res |
72 |
|
|
*/ |
73 |
|
|
static OPT_INLINE |
74 |
|
|
HEntry * gethe ( Fld *fld, int hv, const char *key, int len ) |
75 |
|
|
{ |
76 |
|
|
int i; |
77 |
|
|
register const char *p, *q; |
78 |
|
|
HEntry *he; |
79 |
|
|
if ( fld->len ) { |
80 |
|
|
for ( he = (HEntry *) fld->val; he; he=he->nxt ) { |
81 |
|
|
if ( hv != he->hv || ( i = len ) != he->len ) continue; |
82 |
|
|
for ( p = key, q = he->key, --i; *p++ == *q++; --i ) { |
83 |
|
|
if ( !i ) { |
84 |
|
|
return he; |
85 |
|
|
} |
86 |
|
|
} |
87 |
|
|
} |
88 |
|
|
} |
89 |
|
|
return 0; |
90 |
|
|
} /* gethe */ |
91 |
|
|
|
92 |
|
|
/* |
93 |
|
|
rebuild the table. this is done if: |
94 |
|
|
1. the load factor is > HLOADMAX, or |
95 |
|
|
2. the fragmentation is > HMAXFRAG |
96 |
|
|
mode signals if the number of buckets has to be extended |
97 |
|
|
or to be reduced, this is done if less than HSHRINKLOAD of the buckets are |
98 |
|
|
used |
99 |
|
|
*/ |
100 |
|
|
static void OPT_STDCALL hRebuild ( HTable *table, int mode ) |
101 |
|
|
{ |
102 |
|
|
int i, nsiz, osiz = HSIZ(table); |
103 |
|
|
HEntry *ohe, *nhe; |
104 |
|
|
Fld *fld; |
105 |
|
|
List *nl = (List * )mAlloc(sizeof(List)); |
106 |
|
|
HSTAT(table) |
107 |
|
|
#ifndef NDEBUG |
108 |
|
|
table->coll = 0; |
109 |
|
|
#endif |
110 |
|
|
if ( mode ) { |
111 |
|
|
nsiz = osiz << HSHIFT; |
112 |
|
|
table->mask |= ( table->mask <<= HSHIFT, 1 ); |
113 |
|
|
} else if ( HSHRINKLOAD > HCURLOAD(table) && HINITIAL < HSIZ(table) ) { |
114 |
|
|
nsiz = (unsigned) osiz >> HSHIFT; |
115 |
|
|
table->mask = (unsigned) table->mask >> HSHIFT; |
116 |
|
|
} else |
117 |
|
|
nsiz = osiz; |
118 |
|
|
lInit( nl, "%.*s", table->list->fld->len, table->list->fld->val ); |
119 |
|
|
lExtend( nl, 0, nsiz ); |
120 |
|
|
for ( i = 0; nsiz > i; ++i ) |
121 |
|
|
HLNEWF( nl, i+1 ); |
122 |
|
|
for ( i = 1; osiz >= i; ++i ) { |
123 |
|
|
if ( ( fld = table->list->fld+i)->len ) { |
124 |
|
|
for ( ohe = (HEntry *) fld->val; ohe; ohe = ohe->nxt ) { |
125 |
|
|
int j = ohe->hv & table->mask; |
126 |
|
|
unsigned n = HESIZ(ohe); |
127 |
|
|
fld = nl->fld+j+1; |
128 |
|
|
if ( LAVL( nl ) >= n || lExtend( nl, n, -1 ) ) { |
129 |
|
|
nhe = (HEntry *) nl->buf; |
130 |
|
|
memcpy( nhe, ohe, n ); |
131 |
|
|
nhe->nxt = 0; |
132 |
|
|
#ifndef NDEBUG |
133 |
|
|
nhe->dpt = 1; |
134 |
|
|
#endif |
135 |
|
|
if ( fld->len ) { |
136 |
|
|
nhe->nxt = (HEntry *) fld->val; |
137 |
|
|
#ifndef NDEBUG |
138 |
|
|
nhe->dpt = nhe->nxt->dpt + 1; |
139 |
|
|
++table->coll; |
140 |
|
|
#endif |
141 |
|
|
} |
142 |
|
|
fld->val = (char *) nhe; |
143 |
|
|
fld->len += n; |
144 |
|
|
nl->buf += n; |
145 |
|
|
} |
146 |
|
|
} |
147 |
|
|
} |
148 |
|
|
} |
149 |
|
|
table->dsize = 0; |
150 |
|
|
lFini( table->list ); |
151 |
|
|
mFree( table->list ); |
152 |
|
|
table->list = nl; |
153 |
|
|
HSTAT(table) |
154 |
|
|
} /* hRebuild */ |
155 |
|
|
|
156 |
|
|
/* ************************************************************ |
157 |
|
|
public functions |
158 |
|
|
*/ |
159 |
|
|
|
160 |
|
|
/* |
161 |
|
|
get |
162 |
|
|
*/ |
163 |
|
|
HEntry * OPT_STDCALL hGet ( HTable *table, const char *key, int len ) |
164 |
|
|
{ |
165 |
|
|
int hv = hs( key, len); |
166 |
|
|
return gethe( (table)->list->fld+1+(hv & table->mask), hv, key, len ); |
167 |
|
|
} /* hGet */ |
168 |
|
|
|
169 |
|
|
/* |
170 |
|
|
add |
171 |
|
|
*/ |
172 |
|
|
HEntry * OPT_STDCALL hAdd ( HTable *table, const char *key, int len ) |
173 |
|
|
{ |
174 |
|
|
int hv = hs( key, len); |
175 |
|
|
Fld *fld = (table)->list->fld+1+(hv & table->mask); |
176 |
|
|
HEntry *he = gethe( fld, hv, key, len ); |
177 |
|
|
if ( he ) { |
178 |
|
|
#ifndef NDEBUG |
179 |
|
|
eRr( LOG_DEBUG, "already there %.*s <--> %.*s", he->len, he->key, |
180 |
|
|
len, key ); |
181 |
|
|
#endif |
182 |
|
|
return he; |
183 |
|
|
} |
184 |
|
|
/* |
185 |
|
|
create new entry |
186 |
|
|
*/ |
187 |
|
|
{ |
188 |
|
|
unsigned need = sizeof(HEntry) + len - HEDEFKEYLEN; |
189 |
|
|
if ( LAVL( table->list ) >= need |
190 |
|
|
|| lExtend( table->list, need, -1 ) ) { |
191 |
|
|
he = (HEntry *) table->list->buf; |
192 |
|
|
he->nxt = 0; |
193 |
|
|
he->obj = 0; |
194 |
|
|
#ifndef NDEBUG |
195 |
|
|
he->dpt = 1; |
196 |
|
|
#endif |
197 |
|
|
he->hv = hv; |
198 |
|
|
he->len = len; |
199 |
|
|
memcpy( he->key, key, len ); |
200 |
|
|
if ( fld->len ) { |
201 |
|
|
he->nxt = (HEntry *) fld->val; |
202 |
|
|
#ifndef NDEBUG |
203 |
|
|
++table->coll; |
204 |
|
|
he->dpt = he->nxt->dpt + 1; |
205 |
|
|
#endif |
206 |
|
|
} |
207 |
|
|
fld->val = (char *) he; |
208 |
|
|
fld->len += need; |
209 |
|
|
table->list->buf += need; |
210 |
|
|
++table->nume; |
211 |
|
|
if ( HMAXLOAD < HCURLOAD(table) ) { |
212 |
|
|
hRebuild( table, 1 ); |
213 |
|
|
return gethe ( (table)->list->fld+1+(hv & table->mask), |
214 |
|
|
hv, key, len ); |
215 |
|
|
} |
216 |
|
|
return he; |
217 |
|
|
} |
218 |
|
|
} |
219 |
|
|
return 0; |
220 |
|
|
} /* hAdd */ |
221 |
|
|
|
222 |
|
|
|
223 |
|
|
HEntry* OPT_STDCALL hSet ( HTable *t, const char *key, int len, Obj *o ) |
224 |
|
|
{ |
225 |
|
|
HEntry *he = hAdd(t, key, len); |
226 |
|
|
if ( he ) |
227 |
|
|
he->obj = o; |
228 |
|
|
return he; |
229 |
|
|
} /* hSet */ |
230 |
|
|
|
231 |
|
|
|
232 |
|
|
/* |
233 |
|
|
delete entry and check fragmentation |
234 |
|
|
*/ |
235 |
|
|
int OPT_STDCALL hDel ( HTable *table, const char *key, int len ) |
236 |
|
|
{ |
237 |
|
|
int hv = hs( key, len); |
238 |
|
|
Fld *fld = (table)->list->fld+1+(hv & table->mask); |
239 |
|
|
HEntry *he = gethe( fld, hv, key, len ); |
240 |
|
|
if ( he ) { |
241 |
|
|
int siz = HESIZ(he); |
242 |
|
|
HEntry *prev = (HEntry *) fld->val; |
243 |
|
|
if ( prev == he ) { |
244 |
|
|
fld->val = (char *)he->nxt; |
245 |
|
|
} else { |
246 |
|
|
for ( ; prev->nxt != he; prev = prev->nxt ); |
247 |
|
|
prev->nxt = he->nxt; |
248 |
|
|
} |
249 |
|
|
#ifndef NDEBUG |
250 |
|
|
if ( fld->val ) { |
251 |
|
|
((HEntry *) fld->val)->dpt--; |
252 |
|
|
--table->coll; |
253 |
|
|
} |
254 |
|
|
#endif |
255 |
|
|
fld->len -= siz; |
256 |
|
|
--table->nume; |
257 |
|
|
table->dsize += siz; |
258 |
|
|
if ( HMAXFRAG < HCURFRAG(table) ) |
259 |
|
|
hRebuild( table, 0 ); |
260 |
|
|
return 1; |
261 |
|
|
} |
262 |
|
|
return 0; |
263 |
|
|
} /* hDel */ |
264 |
|
|
|
265 |
|
|
/* |
266 |
|
|
table initialisation |
267 |
|
|
*/ |
268 |
|
|
HTable * OPT_STDCALL hInit ( HTable *table, const char* header ) |
269 |
|
|
{ |
270 |
|
|
int i; |
271 |
|
|
table->list = (List * ) mAlloc( sizeof( *table->list ) ); |
272 |
|
|
lInit( table->list, header ); |
273 |
|
|
for ( i = 0; HINITIAL > i; ++i ) |
274 |
|
|
HLNEWF( table->list, i+1 ); |
275 |
|
|
table->mask = HINITIAL-1; |
276 |
|
|
table->nume = table->dsize = 0; |
277 |
|
|
#ifndef NDEBUG |
278 |
|
|
table->coll = 0; |
279 |
|
|
#endif |
280 |
|
|
return table; |
281 |
|
|
} /* hInit */ |
282 |
|
|
|
283 |
|
|
/* |
284 |
|
|
free the list |
285 |
|
|
the table itself is not freed |
286 |
|
|
*/ |
287 |
|
|
void OPT_STDCALL hFini ( HTable *table ) |
288 |
|
|
{ |
289 |
|
|
lFini( table->list ); |
290 |
|
|
mFree( table->list ); |
291 |
|
|
table->mask = table->nume = table->dsize = 0; |
292 |
|
|
#ifndef NDEBUG |
293 |
|
|
table->coll = 0; |
294 |
|
|
#endif |
295 |
|
|
} /* hFini */ |
296 |
|
|
|
297 |
|
|
#ifndef NDEBUG |
298 |
|
|
/* |
299 |
|
|
hashtable statistics |
300 |
|
|
*/ |
301 |
|
|
void OPT_STDCALL hstat ( HTable *table ) |
302 |
|
|
{ |
303 |
|
|
int j, i, n = HSIZ(table); |
304 |
|
|
HEntry *he; |
305 |
|
|
for ( i = 1, j = 0; n >= i; ++i ) { |
306 |
|
|
he = (HEntry *) (table->list->fld+i)->val; |
307 |
|
|
if ( he ) |
308 |
|
|
j = he->dpt > j ? he->dpt : j; |
309 |
|
|
} |
310 |
|
|
eRr( LOG_DEBUG, "hash stats:\n\tnum buckets: %u\n\tnum entries: %u\n\tload: %u\n\tlist buf size: %u\n\tdel size: %u\n\tfrag: %u\n\tcollisions: %u\n\tcollision rate: %u\n\tmaxdepth: %u", HSIZ(table), table->nume, HCURLOAD(table), LSIZ(table->list), table->dsize, HCURFRAG(table), table->coll, (table->coll*100)/( table->nume ? table->nume : 1 ), j ); |
311 |
|
|
|
312 |
|
|
} /* hstat */ |
313 |
|
|
|
314 |
|
|
#endif |