0.9.9e/pw/hash.c

/*
        The Malete project - the Z39.2/Z39.50 database framework of OpenIsis.
        Version 0.9.x (patchlevel see file Version)
        Copyright (C) 2001-2003 by Erik Grziwotz, erik@openisis.org

        This library is free software; you can redistribute it and/or
        modify it under the terms of the GNU Lesser General Public
        License as published by the Free Software Foundation; either
        version 2.1 of the License, or (at your option) any later version.

        This library is distributed in the hope that it will be useful,
        but WITHOUT ANY WARRANTY; without even the implied warranty of
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
        See the GNU Lesser General Public License for more details.

        You should have received a copy of the GNU Lesser General Public
        License along with this library; if not, write to the Free Software
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

        see README for more information
EOH */

/*
        $Id: hash.c,v 1.2 2004/03/29 09:35:20 kripke Exp $
        the hashtable
*/

#include "../pw/pw.h"

/* ************************************************************
                private functions
*/

/*
        add a bucket
*/
#define HLNEWF( l, t ) do { \
        if ( (l)->fav || lExtend( l, 0, 1 ) ) { \
                Fld *__f = (l)->fld - (l)->fld->tag--; \
                __f->tag = t; \
                __f->val = 0; \
                __f->len = 0; \
                (l)->fav --; \
        } } while(0)

/*
        the cdb hash function ( without h/256 )
*/
#define CDB_CALC(i,s) i ^= ( i += i << 5, (int) *s++ )

static OPT_INLINE int hs ( const char *s, register int len )
{
        register int i = 5381, n = (len + 7 ) / 8;
        if ( ! len ) return i;
        switch ( len % 8 ) {
        case 0: do { CDB_CALC(i,s);
        case 7:      CDB_CALC(i,s);
        case 6:      CDB_CALC(i,s);
        case 5:      CDB_CALC(i,s);
        case 4:      CDB_CALC(i,s);
        case 3:      CDB_CALC(i,s);
        case 2:      CDB_CALC(i,s);
        case 1:      CDB_CALC(i,s);
                } while ( --n );
        }
        return i;
} /* hs */

/*
        lookup key in a bucket, if found the corresponding entry is assigned
        to res
*/
static OPT_INLINE
HEntry * gethe ( Fld *fld, int hv, const char *key, int len )
{
        int i;
        register const char *p, *q;
        HEntry *he;
        if ( fld->len ) {
                for ( he = (HEntry *) fld->val; he; he=he->nxt ) {
                        if ( hv != he->hv || ( i = len ) != he->len ) continue;
                        for ( p = key, q = he->key, --i; *p++ == *q++; --i ) {
                                if ( !i ) {
                                        return he;
                                }
                        }
                }
        }
        return 0;
} /* gethe */

/*
        rebuild the table. this is done if:
                1. the load factor is > HLOADMAX, or
                2. the fragmentation is > HMAXFRAG
        mode signals if the number of buckets has to be extended
        or to be reduced, this is done if less than HSHRINKLOAD of the buckets are
        used
*/
static void OPT_STDCALL hRebuild ( HTable *table, int mode )
{
        int i, nsiz, osiz = HSIZ(table);
        HEntry *ohe, *nhe;
        Fld *fld;
        List *nl = (List * )mAlloc(sizeof(List));
        HSTAT(table)
#ifndef NDEBUG
        table->coll = 0;
#endif
        if ( mode ) {
                nsiz = osiz << HSHIFT;
                table->mask |= ( table->mask <<= HSHIFT, 1 );
        } else if ( HSHRINKLOAD > HCURLOAD(table) && HINITIAL < HSIZ(table) ) {
                nsiz = (unsigned) osiz >> HSHIFT;
                table->mask = (unsigned) table->mask >> HSHIFT;
        } else
                nsiz = osiz;
        lInit( nl, "%.*s", table->list->fld->len, table->list->fld->val );
        lExtend( nl, 0, nsiz );
        for ( i = 0; nsiz > i; ++i )
                HLNEWF( nl, i+1 );
        for ( i = 1; osiz >= i; ++i ) {
                if ( ( fld = table->list->fld+i)->len ) {
                        for ( ohe = (HEntry *) fld->val; ohe; ohe = ohe->nxt ) {
                                int j = ohe->hv & table->mask;
                                unsigned n = HESIZ(ohe);
                                fld = nl->fld+j+1;
                                if ( LAVL( nl ) >= n || lExtend( nl, n, -1 ) ) {
                                        nhe = (HEntry *) nl->buf;
                                        memcpy( nhe, ohe, n );
                                        nhe->nxt = 0;
#ifndef NDEBUG
                                        nhe->dpt = 1;
#endif
                                        if ( fld->len ) {
                                                nhe->nxt = (HEntry *) fld->val;
#ifndef NDEBUG
                                                nhe->dpt = nhe->nxt->dpt + 1;
                                                ++table->coll;
#endif
                                        }
                                        fld->val = (char *) nhe;
                                        fld->len += n;
                                        nl->buf += n;
                                }
                        }
                }
        }
        table->dsize = 0;
        lFini( table->list );
        mFree( table->list );
        table->list = nl;
        HSTAT(table)
} /* hRebuild */

/* ************************************************************
                public functions
*/

/*
        get
*/
HEntry * OPT_STDCALL hGet ( HTable *table, const char *key, int len )
{
        int hv = hs( key, len);
        return gethe( (table)->list->fld+1+(hv & table->mask), hv, key, len );
} /* hGet */

/*
        add
*/
HEntry * OPT_STDCALL hAdd ( HTable *table, const char *key, int len )
{
        int hv = hs( key, len);
        Fld *fld = (table)->list->fld+1+(hv & table->mask);
        HEntry *he = gethe( fld, hv, key, len );
        if ( he ) {
#ifndef NDEBUG
                eRr( LOG_DEBUG, "already there %.*s <--> %.*s", he->len, he->key,
                                len, key );
#endif
                return he;
        }
        /*
                create new entry
        */
        {
                unsigned need = sizeof(HEntry) + len - HEDEFKEYLEN;
                if ( LAVL( table->list ) >= need
                                || lExtend( table->list, need, -1 ) ) {
                        he = (HEntry *) table->list->buf;
                        he->nxt = 0;
                        he->obj = 0;
#ifndef NDEBUG
                        he->dpt = 1;
#endif
                        he->hv = hv;
                        he->len = len;
                        memcpy( he->key, key, len );
                        if ( fld->len ) {
                                he->nxt = (HEntry *) fld->val;
#ifndef NDEBUG
                                ++table->coll;
                                he->dpt = he->nxt->dpt + 1;
#endif
                        }
                        fld->val = (char *) he;
                        fld->len += need;
                        table->list->buf += need;
                        ++table->nume;
                        if ( HMAXLOAD < HCURLOAD(table) ) {
                                hRebuild( table, 1 );
                                return gethe ( (table)->list->fld+1+(hv & table->mask),
                                                hv, key, len );
                        }
                        return he;
                }
        }
        return 0;
} /* hAdd */


HEntry* OPT_STDCALL hSet ( HTable *t, const char *key, int len, Obj *o )
{
        HEntry *he = hAdd(t, key, len);
        if ( he )
                he->obj = o;
        return he;
}       /* hSet */


/*
        delete entry and check fragmentation
*/
int OPT_STDCALL hDel (  HTable *table, const char *key, int len )
{
        int hv = hs( key, len);
        Fld *fld = (table)->list->fld+1+(hv & table->mask);
        HEntry *he = gethe( fld, hv, key, len );
        if ( he ) {
                int siz = HESIZ(he);
                HEntry *prev = (HEntry *) fld->val;
                if ( prev == he ) {
                        fld->val = (char *)he->nxt;
                } else {
                        for ( ; prev->nxt != he; prev = prev->nxt );
                        prev->nxt = he->nxt;
                }
#ifndef NDEBUG
                if ( fld->val ) {
                        ((HEntry *) fld->val)->dpt--;
                        --table->coll;
                }
#endif
                fld->len -= siz;
                --table->nume;
                table->dsize += siz;
                if ( HMAXFRAG < HCURFRAG(table) )
                        hRebuild( table, 0 );
                return 1;
        }
        return 0;
} /* hDel */

/*
        table initialisation
*/
HTable * OPT_STDCALL hInit ( HTable *table, const char* header )
{
        int i;
        table->list = (List * ) mAlloc( sizeof( *table->list ) );
        lInit( table->list, header );
        for ( i = 0; HINITIAL > i; ++i )
                HLNEWF( table->list, i+1 );
        table->mask = HINITIAL-1;
        table->nume = table->dsize = 0;
#ifndef NDEBUG
        table->coll = 0;
#endif
        return table;
} /* hInit */

/*
        free the list
        the table itself is not freed
*/
void OPT_STDCALL hFini ( HTable *table )
{
        lFini( table->list );
        mFree( table->list );
        table->mask = table->nume = table->dsize = 0;
#ifndef NDEBUG
        table->coll = 0;
#endif
} /* hFini */

#ifndef NDEBUG
/*
        hashtable statistics
*/
void OPT_STDCALL hstat ( HTable *table )
{
        int j, i, n =  HSIZ(table);
        HEntry *he;
        for ( i = 1, j = 0; n >= i; ++i ) {
                he = (HEntry *) (table->list->fld+i)->val;
                if ( he )
                        j = he->dpt > j ?  he->dpt : j;
        }
        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 );

} /* hstat */

#endif
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