/[webpac]/openisis/0.9.9e/pw/hash.c
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Contents of /openisis/0.9.9e/pw/hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 604 - (show annotations)
Mon Dec 27 21:49:01 2004 UTC (19 years, 2 months ago) by dpavlin
File MIME type: text/plain
File size: 7515 byte(s)
import of new openisis release, 0.9.9e

1 /*
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

  ViewVC Help
Powered by ViewVC 1.1.26