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;
        register 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;
        /*
         * 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.3
Committed:	Thu Jun 23 08:48:28 1994 UTC (29 years, 10 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.2:	+6 -1 lines
Log Message:	change in comment
#	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	greg	1.3	register LUENT *oldtabl;
65	greg	1.1	/* 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	greg	1.3	/*
87			* The following code may fail if the user has reclaimed many
88			* deleted entries and the system runs out of memory in a
89			* recursive call to lu_find().
90			*/
91	greg	1.1	while (ndx--)
92	greg	1.2	if (oldtabl[ndx].key != NULL)
93			if (oldtabl[ndx].data != NULL)
94			*lu_find(tbl, oldtabl[ndx].key) = oldtabl[ndx];
95			else if (tbl->freek != NULL)
96			(*tbl->freek)(oldtabl[ndx].key);
97	greg	1.1	free((MEM_PTR)oldtabl);
98			goto tryagain; /* should happen only once! */
99			}
100
101
102			void
103	greg	1.2	lu_delete(tbl, key) /* delete a table entry */
104			register LUTAB *tbl;
105			char *key;
106	greg	1.1	{
107	greg	1.2	register LUENT *le;
108
109			if ((le = lu_find(tbl, key)) == NULL)
110			return;
111			if (le->key == NULL \|\| le->data == NULL)
112			return;
113			if (tbl->freed != NULL)
114			(*tbl->freed)(le->data);
115			le->data = NULL;
116			tbl->ndel++;
117			}
118
119
120			void
121			lu_done(tbl) /* free table and contents */
122			register LUTAB *tbl;
123			{
124	greg	1.1	register LUENT *tp;
125
126			if (!tbl->tsiz)
127			return;
128	greg	1.2	for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
129			if (tp->key != NULL) {
130			if (tbl->freek != NULL)
131			(*tbl->freek)(tp->key);
132			if (tp->data != NULL && tbl->freed != NULL)
133			(*tbl->freed)(tp->data);
134			}
135	greg	1.1	free((MEM_PTR)tbl->tabl);
136			tbl->tabl = NULL;
137			tbl->tsiz = 0;
138	greg	1.2	tbl->ndel = 0;
139	greg	1.1	}