cv/mgflib/lookup.c

/* Copyright (c) 1994 Regents of the University of California */

#ifndef lint
static char SCCSid[] = "$SunId$ LBL";
#endif

/*
 * Table lookup routines
 */

#include <stdio.h>
#include "lookup.h"

#ifndef MEM_PTR
#define MEM_PTR         void *
#endif

extern MEM_PTR  calloc();


int
lu_init(tbl, nel)               /* initialize tbl for at least nel elements */
register LUTAB  *tbl;
int     nel;
{
        static int  hsiztab[] = {
                31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 0
        };
        register int  *hsp;

        nel += nel>>1;                  /* 66% occupancy */
        for (hsp = hsiztab; *hsp; hsp++)
                if (*hsp > nel)
                        break;
        if (!(tbl->tsiz = *hsp))
                tbl->tsiz = nel*2 + 1;          /* not always prime */
        tbl->tabl = (LUENT *)calloc(tbl->tsiz, sizeof(LUENT));
        if (tbl->tabl == NULL)
                tbl->tsiz = 0;
        tbl->ndel = 0;
        return(tbl->tsiz);
}


long
lu_shash(s)                     /* hash a nul-terminated string */
register char  *s;
{
        register int    i = 0;
        register long   h = 0;

        while (*s)
                h ^= (long)(*s++ & 0xff) << (i++ & 0xf);
        return(h);
}


LUENT *
lu_find(tbl, key)               /* find a table entry */
register LUTAB  *tbl;
char    *key;
{
        long    hval;
        int     i;
        register int    ndx;
        register LUENT  *oldtabl;
                                        /* look up object */
        hval = (*tbl->hashf)(key);
tryagain:
        for (i = 0; i < tbl->tsiz; i++) {
                ndx = (hval + i*i) % tbl->tsiz;
                if (tbl->tabl[ndx].key == NULL) {
                        tbl->tabl[ndx].hval = hval;
                        return(&tbl->tabl[ndx]);
                }
                if ( tbl->tabl[ndx].hval == hval && (tbl->keycmp == NULL ||
                                !(*tbl->keycmp)(tbl->tabl[ndx].key, key)) )
                        return(&tbl->tabl[ndx]);
        }
                                        /* table is full, reallocate */
        oldtabl = tbl->tabl;
        ndx = tbl->tsiz;
        i = tbl->ndel;
        if (!lu_init(tbl, ndx-i+1)) {   /* no more memory! */
                tbl->tabl = oldtabl;
                tbl->tsiz = ndx;
                tbl->ndel = i;
                return(NULL);
        }
        if (!ndx)
                goto tryagain;
        /*
         * The following code may fail if the user has reclaimed many
         * deleted entries and the system runs out of memory in a
         * recursive call to lu_find().
         */
        while (ndx--)
                if (oldtabl[ndx].key != NULL)
                        if (oldtabl[ndx].data != NULL)
                                *lu_find(tbl, oldtabl[ndx].key) = oldtabl[ndx];
                        else if (tbl->freek != NULL)
                                (*tbl->freek)(oldtabl[ndx].key);
        free((MEM_PTR)oldtabl);
        goto tryagain;                  /* should happen only once! */
}


void
lu_delete(tbl, key)             /* delete a table entry */
register LUTAB  *tbl;
char    *key;
{
        register LUENT  *le;

        if ((le = lu_find(tbl, key)) == NULL)
                return;
        if (le->key == NULL || le->data == NULL)
                return;
        if (tbl->freed != NULL)
                (*tbl->freed)(le->data);
        le->data = NULL;
        tbl->ndel++;
}


void
lu_done(tbl)                    /* free table and contents */
register LUTAB  *tbl;
{
        register LUENT  *tp;

        if (!tbl->tsiz)
                return;
        for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
                if (tp->key != NULL) {
                        if (tbl->freek != NULL)
                                (*tbl->freek)(tp->key);
                        if (tp->data != NULL && tbl->freed != NULL)
                                (*tbl->freed)(tp->data);
                }
        free((MEM_PTR)tbl->tabl);
        tbl->tabl = NULL;
        tbl->tsiz = 0;
        tbl->ndel = 0;
}
Revision:	1.5
Committed:	Tue Apr 11 13:33:27 1995 UTC (29 years, 1 month ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.4:	+2 -2 lines
Log Message:	minor mods
#	User	Rev	Content
1	greg	1.1	/* Copyright (c) 1994 Regents of the University of California */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ LBL";
5			#endif
6
7			/*
8			* Table lookup routines
9			*/
10
11			#include <stdio.h>
12			#include "lookup.h"
13
14			#ifndef MEM_PTR
15			#define MEM_PTR void *
16			#endif
17
18			extern MEM_PTR calloc();
19
20
21			int
22			lu_init(tbl, nel) /* initialize tbl for at least nel elements */
23			register LUTAB *tbl;
24			int nel;
25			{
26			static int hsiztab[] = {
27			31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 0
28			};
29			register int *hsp;
30
31	greg	1.2	nel += nel>>1; /* 66% occupancy */
32	greg	1.1	for (hsp = hsiztab; *hsp; hsp++)
33			if (*hsp > nel)
34			break;
35			if (!(tbl->tsiz = *hsp))
36			tbl->tsiz = nel2 + 1; / not always prime */
37			tbl->tabl = (LUENT *)calloc(tbl->tsiz, sizeof(LUENT));
38			if (tbl->tabl == NULL)
39			tbl->tsiz = 0;
40	greg	1.2	tbl->ndel = 0;
41	greg	1.1	return(tbl->tsiz);
42			}
43
44
45	greg	1.4	long
46			lu_shash(s) /* hash a nul-terminated string */
47	greg	1.1	register char *s;
48			{
49	greg	1.4	register int i = 0;
50			register long h = 0;
51	greg	1.1
52			while (*s)
53	greg	1.5	h ^= (long)(*s++ & 0xff) << (i++ & 0xf);
54	greg	1.1	return(h);
55			}
56
57
58			LUENT *
59			lu_find(tbl, key) /* find a table entry */
60			register LUTAB *tbl;
61			char *key;
62			{
63	greg	1.4	long hval;
64			int i;
65			register int ndx;
66			register LUENT *oldtabl;
67	greg	1.1	/* look up object */
68	greg	1.4	hval = (*tbl->hashf)(key);
69	greg	1.1	tryagain:
70			for (i = 0; i < tbl->tsiz; i++) {
71			ndx = (hval + i*i) % tbl->tsiz;
72	greg	1.4	if (tbl->tabl[ndx].key == NULL) {
73			tbl->tabl[ndx].hval = hval;
74			return(&tbl->tabl[ndx]);
75			}
76			if ( tbl->tabl[ndx].hval == hval && (tbl->keycmp == NULL \|\|
77			!(*tbl->keycmp)(tbl->tabl[ndx].key, key)) )
78	greg	1.1	return(&tbl->tabl[ndx]);
79			}
80			/* table is full, reallocate */
81			oldtabl = tbl->tabl;
82			ndx = tbl->tsiz;
83	greg	1.2	i = tbl->ndel;
84	greg	1.5	if (!lu_init(tbl, ndx-i+1)) { /* no more memory! */
85	greg	1.1	tbl->tabl = oldtabl;
86			tbl->tsiz = ndx;
87	greg	1.2	tbl->ndel = i;
88	greg	1.1	return(NULL);
89			}
90			if (!ndx)
91			goto tryagain;
92	greg	1.3	/*
93			* The following code may fail if the user has reclaimed many
94			* deleted entries and the system runs out of memory in a
95			* recursive call to lu_find().
96			*/
97	greg	1.1	while (ndx--)
98	greg	1.2	if (oldtabl[ndx].key != NULL)
99			if (oldtabl[ndx].data != NULL)
100			*lu_find(tbl, oldtabl[ndx].key) = oldtabl[ndx];
101			else if (tbl->freek != NULL)
102			(*tbl->freek)(oldtabl[ndx].key);
103	greg	1.1	free((MEM_PTR)oldtabl);
104			goto tryagain; /* should happen only once! */
105			}
106
107
108			void
109	greg	1.2	lu_delete(tbl, key) /* delete a table entry */
110			register LUTAB *tbl;
111			char *key;
112	greg	1.1	{
113	greg	1.2	register LUENT *le;
114
115			if ((le = lu_find(tbl, key)) == NULL)
116			return;
117			if (le->key == NULL \|\| le->data == NULL)
118			return;
119			if (tbl->freed != NULL)
120			(*tbl->freed)(le->data);
121			le->data = NULL;
122			tbl->ndel++;
123			}
124
125
126			void
127			lu_done(tbl) /* free table and contents */
128			register LUTAB *tbl;
129			{
130	greg	1.1	register LUENT *tp;
131
132			if (!tbl->tsiz)
133			return;
134	greg	1.2	for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
135			if (tp->key != NULL) {
136			if (tbl->freek != NULL)
137			(*tbl->freek)(tp->key);
138			if (tp->data != NULL && tbl->freed != NULL)
139			(*tbl->freed)(tp->data);
140			}
141	greg	1.1	free((MEM_PTR)tbl->tabl);
142			tbl->tabl = NULL;
143			tbl->tsiz = 0;
144	greg	1.2	tbl->ndel = 0;
145	greg	1.1	}