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