src/common/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"

#define MEM_PTR         char *

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