Back to index

radiance  4R0+20100331
lookup.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: lookup.c,v 1.11 2003/11/21 07:15:29 greg Exp $";
00003 #endif
00004 /*
00005  * Table lookup routines
00006  */
00007 
00008 #include <stdio.h>
00009 #include <stdlib.h>
00010 
00011 #include "lookup.h"
00012 
00013 
00014 int
00015 lu_init(tbl, nel)           /* initialize tbl for at least nel elements */
00016 register LUTAB       *tbl;
00017 int    nel;
00018 {
00019        static int  hsiztab[] = {
00020               31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, 16381, 
00021               32749, 65521, 131071, 262139, 524287, 1048573, 2097143, 
00022               4194301, 8388593, 0
00023        };
00024        register int  *hsp;
00025 
00026        nel += nel>>1;                     /* 66% occupancy */
00027        for (hsp = hsiztab; *hsp; hsp++)
00028               if (*hsp > nel)
00029                      break;
00030        if (!(tbl->tsiz = *hsp))
00031               tbl->tsiz = nel*2 + 1;             /* not always prime */
00032        tbl->tabl = (LUENT *)calloc(tbl->tsiz, sizeof(LUENT));
00033        if (tbl->tabl == NULL)
00034               tbl->tsiz = 0;
00035        tbl->ndel = 0;
00036        return(tbl->tsiz);
00037 }
00038 
00039 
00040 unsigned long
00041 lu_shash(s)                 /* hash a nul-terminated string */
00042 char   *s;
00043 {
00044        static unsigned char shuffle[256] = {
00045               0, 157, 58, 215, 116, 17, 174, 75, 232, 133, 34,
00046               191, 92, 249, 150, 51, 208, 109, 10, 167, 68, 225,
00047               126, 27, 184, 85, 242, 143, 44, 201, 102, 3, 160,
00048               61, 218, 119, 20, 177, 78, 235, 136, 37, 194, 95,
00049               252, 153, 54, 211, 112, 13, 170, 71, 228, 129, 30,
00050               187, 88, 245, 146, 47, 204, 105, 6, 163, 64, 221,
00051               122, 23, 180, 81, 238, 139, 40, 197, 98, 255, 156,
00052               57, 214, 115, 16, 173, 74, 231, 132, 33, 190, 91,
00053               248, 149, 50, 207, 108, 9, 166, 67, 224, 125, 26,
00054               183, 84, 241, 142, 43, 200, 101, 2, 159, 60, 217,
00055               118, 19, 176, 77, 234, 135, 36, 193, 94, 251, 152,
00056               53, 210, 111, 12, 169, 70, 227, 128, 29, 186, 87,
00057               244, 145, 46, 203, 104, 5, 162, 63, 220, 121, 22,
00058               179, 80, 237, 138, 39, 196, 97, 254, 155, 56, 213,
00059               114, 15, 172, 73, 230, 131, 32, 189, 90, 247, 148,
00060               49, 206, 107, 8, 165, 66, 223, 124, 25, 182, 83,
00061               240, 141, 42, 199, 100, 1, 158, 59, 216, 117, 18,
00062               175, 76, 233, 134, 35, 192, 93, 250, 151, 52, 209,
00063               110, 11, 168, 69, 226, 127, 28, 185, 86, 243, 144,
00064               45, 202, 103, 4, 161, 62, 219, 120, 21, 178, 79,
00065               236, 137, 38, 195, 96, 253, 154, 55, 212, 113, 14,
00066               171, 72, 229, 130, 31, 188, 89, 246, 147, 48, 205,
00067               106, 7, 164, 65, 222, 123, 24, 181, 82, 239, 140,
00068               41, 198, 99
00069        };
00070        register int  i = 0;
00071        register unsigned long      h = 0;
00072        register unsigned char *t = (unsigned char *)s;
00073 
00074        while (*t)
00075               h ^= (unsigned long)shuffle[*t++] << ((i+=11) & 0xf);
00076 
00077        return(h);
00078 }
00079 
00080 
00081 LUENT *
00082 lu_find(tbl, key)           /* find a table entry */
00083 register LUTAB       *tbl;
00084 char   *key;
00085 {
00086        unsigned long hval;
00087        int    i, n;
00088        register int  ndx;
00089        register LUENT       *le;
00090                                    /* look up object */
00091        if (tbl->tsiz == 0 && !lu_init(tbl, 1))
00092               return(NULL);
00093        hval = (*tbl->hashf)(key);
00094 tryagain:
00095        ndx = hval % tbl->tsiz;
00096        for (i = 0, n = 1; i < tbl->tsiz; i++, n += 2) {
00097               le = &tbl->tabl[ndx];
00098               if (le->key == NULL) {
00099                      le->hval = hval;
00100                      return(le);
00101               }
00102               if (le->hval == hval && 
00103                     (tbl->keycmp == NULL || !(*tbl->keycmp)(le->key, key))) {
00104                      return(le);
00105               }
00106               if ((ndx += n) >= tbl->tsiz)       /* this happens rarely */
00107                      ndx = ndx % tbl->tsiz;
00108        }
00109                                    /* table is full, reallocate */
00110        le = tbl->tabl;
00111        ndx = tbl->tsiz;
00112        i = tbl->ndel;
00113        if (!lu_init(tbl, ndx-i+1)) {      /* no more memory! */
00114               tbl->tabl = le;
00115               tbl->tsiz = ndx;
00116               tbl->ndel = i;
00117               return(NULL);
00118        }
00119        /*
00120         * The following code may fail if the user has reclaimed many
00121         * deleted entries and the system runs out of memory in a
00122         * recursive call to lu_find().
00123         */
00124        while (ndx--)
00125               if (le[ndx].key != NULL) {
00126                      if (le[ndx].data != NULL)
00127                             *lu_find(tbl,le[ndx].key) = le[ndx];
00128                      else if (tbl->freek != NULL)
00129                             (*tbl->freek)(le[ndx].key);
00130               }
00131        free((void *)le);
00132        goto tryagain;                     /* should happen only once! */
00133 }
00134 
00135 
00136 void
00137 lu_delete(tbl, key)         /* delete a table entry */
00138 register LUTAB       *tbl;
00139 char   *key;
00140 {
00141        register LUENT       *le;
00142 
00143        if ((le = lu_find(tbl, key)) == NULL)
00144               return;
00145        if (le->key == NULL || le->data == NULL)
00146               return;
00147        if (tbl->freed != NULL)
00148               (*tbl->freed)(le->data);
00149        le->data = NULL;
00150        tbl->ndel++;
00151 }
00152 
00153 
00154 int
00155 lu_doall(tbl, f)            /* loop through all valid table entries */
00156 register LUTAB       *tbl;
00157 int    (*f)(LUENT *);
00158 {
00159        int    rval = 0;
00160        register LUENT       *tp;
00161 
00162        for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
00163               if (tp->data != NULL) {
00164                      if (f != NULL)
00165                             rval += (*f)(tp);
00166                      else
00167                             rval++;
00168               }
00169        return(rval);
00170 }
00171 
00172 
00173 void
00174 lu_done(tbl)                /* free table and contents */
00175 register LUTAB       *tbl;
00176 {
00177        register LUENT       *tp;
00178 
00179        if (!tbl->tsiz)
00180               return;
00181        for (tp = tbl->tabl + tbl->tsiz; tp-- > tbl->tabl; )
00182               if (tp->key != NULL) {
00183                      if (tbl->freek != NULL)
00184                             (*tbl->freek)(tp->key);
00185                      if (tp->data != NULL && tbl->freed != NULL)
00186                             (*tbl->freed)(tp->data);
00187               }
00188        free((void *)tbl->tabl);
00189        tbl->tabl = NULL;
00190        tbl->tsiz = 0;
00191        tbl->ndel = 0;
00192 }