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);
}


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

        while (*s)
                h = (h<<1 & 0x7fff) ^ (*s++ & 0xff);
        return(h);
}


LUENT *
lu_find(tbl, key)               /* find a table entry */
register LUTAB  *tbl;
char    *key;
{
        int  hval, i;
        register int  ndx;
        LUENT  *oldtabl;
                                        /* look up object */
        hval = lu_hash(key);
tryagain:
        for (i = 0; i < tbl->tsiz; i++) {
                ndx = (hval + i*i) % tbl->tsiz;
                if (tbl->tabl[ndx].key == NULL ||
                                !strcmp(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)) {     /* no more memory! */
                tbl->tabl = oldtabl;
                tbl->tsiz = ndx;
                tbl->ndel = i;
                return(NULL);
        }
        if (!ndx)
                goto tryagain;
        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.2
Committed:	Thu Jun 23 07:48:41 1994 UTC (29 years, 11 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.1:	+38 -15 lines
Log Message:	improved table lookup routines with new delete function
#	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			int
46			lu_hash(s) /* hash a nul-terminated string */
47			register char *s;
48			{
49			register int h = 0;
50
51			while (*s)
52			h = (h<<1 & 0x7fff) ^ (*s++ & 0xff);
53			return(h);
54			}
55
56
57			LUENT *
58			lu_find(tbl, key) /* find a table entry */
59			register LUTAB *tbl;
60			char *key;
61			{
62			int hval, i;
63			register int ndx;
64			LUENT *oldtabl;
65			/* look up object */
66			hval = lu_hash(key);
67			tryagain:
68			for (i = 0; i < tbl->tsiz; i++) {
69			ndx = (hval + i*i) % tbl->tsiz;
70			if (tbl->tabl[ndx].key == NULL \|\|
71			!strcmp(tbl->tabl[ndx].key, key))
72			return(&tbl->tabl[ndx]);
73			}
74			/* table is full, reallocate */
75			oldtabl = tbl->tabl;
76			ndx = tbl->tsiz;
77	greg	1.2	i = tbl->ndel;
78			if (!lu_init(tbl, ndx-i)) { /* no more memory! */
79	greg	1.1	tbl->tabl = oldtabl;
80			tbl->tsiz = ndx;
81	greg	1.2	tbl->ndel = i;
82	greg	1.1	return(NULL);
83			}
84			if (!ndx)
85			goto tryagain;
86			while (ndx--)
87	greg	1.2	if (oldtabl[ndx].key != NULL)
88			if (oldtabl[ndx].data != NULL)
89			*lu_find(tbl, oldtabl[ndx].key) = oldtabl[ndx];
90			else if (tbl->freek != NULL)
91			(*tbl->freek)(oldtabl[ndx].key);
92	greg	1.1	free((MEM_PTR)oldtabl);
93			goto tryagain; /* should happen only once! */
94			}
95
96
97			void
98	greg	1.2	lu_delete(tbl, key) /* delete a table entry */
99			register LUTAB *tbl;
100			char *key;
101	greg	1.1	{
102	greg	1.2	register LUENT *le;
103
104			if ((le = lu_find(tbl, key)) == NULL)
105			return;
106			if (le->key == NULL \|\| le->data == NULL)
107			return;
108			if (tbl->freed != NULL)
109			(*tbl->freed)(le->data);
110			le->data = NULL;
111			tbl->ndel++;
112			}
113
114
115			void
116			lu_done(tbl) /* free table and contents */
117			register LUTAB *tbl;
118			{
119	greg	1.1	register LUENT *tp;
120
121			if (!tbl->tsiz)
122			return;
123	greg	1.2	for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
124			if (tp->key != NULL) {
125			if (tbl->freek != NULL)
126			(*tbl->freek)(tp->key);
127			if (tp->data != NULL && tbl->freed != NULL)
128			(*tbl->freed)(tp->data);
129			}
130	greg	1.1	free((MEM_PTR)tbl->tabl);
131			tbl->tabl = NULL;
132			tbl->tsiz = 0;
133	greg	1.2	tbl->ndel = 0;
134	greg	1.1	}