source4/lib/appweb/ejs-2.0/mpr/mprSymbol.c

   1 /*
   2  *      @file   mprSym.cpp
   3  *      @brief  Fast hashing symbol table lookup module
   4  *      @overview This symbol table uses a fast key lookup mechanism. Keys are
   5  *              strings and the value entries are arbitrary pointers. The keys are
   6  *              hashed into a series of buckets which then have a chain of hash
   7  *              entries using the standard doubly linked list classes (List/Link).
   8  *              The chain in in collating sequence so search time through the chain
   9  *              is on average (N/hashSize)/2.
  10  *      @remarks This module is not thread-safe. It is the callers responsibility
  11  *      to perform all thread synchronization.
  12  */
  13 /********************************* Copyright **********************************/
  14 /*
  15  *      @copy   default
  16  *
  17  *      Copyright (c) Mbedthis Software LLC, 2003-2006. All Rights Reserved.
  18  *
  19  *      This software is distributed under commercial and open source licenses.
  20  *      You may use the GPL open source license described below or you may acquire
  21  *      a commercial license from Mbedthis Software. You agree to be fully bound
  22  *      by the terms of either license. Consult the LICENSE.TXT distributed with
  23  *      this software for full details.
  24  *
  25  *      This software is open source; you can redistribute it and/or modify it
  26  *      under the terms of the GNU General Public License as published by the
  27  *      Free Software Foundation; either version 2 of the License, or (at your
  28  *      option) any later version. See the GNU General Public License for more
  29  *      details at: http: *www.mbedthis.com/downloads/gplLicense.html
  30  *
  31  *      This program is distributed WITHOUT ANY WARRANTY; without even the
  32  *      implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  33  *
  34  *      This GPL license does NOT permit incorporating this software into
  35  *      proprietary programs. If you are unable to comply with the GPL, you must
  36  *      acquire a commercial license to use this software. Commercial licenses
  37  *      for this software and support services are available from Mbedthis
  38  *      Software at http: *www.mbedthis.com
  39  *
  40  *      @end
  41  */
  42 /********************************** Includes **********************************/
  43
  44 #include        "mpr.h"
  45
  46 /**************************** Forward Declarations ****************************/
  47
  48 static int hashIndex(const char *key, int size);
  49 static MprSymbol        *lookupInner(int *bucketIndex, MprSymbol **prevSp,
  50         MprSymbolTable *table, const char *key);
  51
  52 /*********************************** Code *************************************/
  53 /*
  54  *      Create a new symbol table of a given size. Caller should provide a size
  55  *      that is a prime number for the greatest efficiency. Caller should use
  56  *      mprFree to free the symbol table.
  57  */
  58
  59 MprSymbolTable *mprCreateSymbolTable(MprCtx ctx, int hashSize)
  60 {
  61         MprSymbolTable  *table;
  62
  63         table = mprAllocTypeZeroed(ctx, MprSymbolTable);
  64         if (table == 0) {
  65                 return 0;
  66         }
  67
  68         if (hashSize < MPR_DEFAULT_HASH_SIZE) {
  69                 hashSize = MPR_DEFAULT_HASH_SIZE;
  70         }
  71         table->hashSize = hashSize;
  72
  73         table->count = 0;
  74         table->hashSize = hashSize;
  75         table->buckets = mprAllocZeroedBlock(MPR_LOC_ARGS(table),
  76                 sizeof(MprSymbol*) * hashSize);
  77
  78         if (table->buckets == 0) {
  79                 mprFree(table);
  80                 return 0;
  81         }
  82
  83         return table;
  84 }
  85
  86 /******************************************************************************/
  87 /*
  88  *      Insert an entry into the symbol table. If the entry already exists, update
  89  *      its value. Order of insertion is not preserved.
  90  */
  91
  92 MprSymbol *mprInsertSymbol(MprSymbolTable *table, const char *key, void *ptr)
  93 {
  94         MprSymbol               *sp, *prevSp;
  95         int                             index;
  96
  97         sp = lookupInner(&index, &prevSp, table, key);
  98
  99         if (sp != 0) {
 100                 /*
 101                  *      Already exists. Just update the data.
 102                  */
 103                 sp->data = ptr;
 104                 return sp;
 105         }
 106
 107         /*
 108          *      New entry
 109          */
 110         sp = mprAllocTypeZeroed(table, MprSymbol);
 111         if (sp == 0) {
 112                 return 0;
 113         }
 114
 115         sp->data = ptr;
 116         sp->key = mprStrdup(sp, key);
 117         sp->bucket = index;
 118
 119         sp->next = table->buckets[index];
 120         table->buckets[index] = sp;
 121
 122         table->count++;
 123         return sp;
 124 }
 125
 126 /******************************************************************************/
 127 /*
 128  *      Remove an entry from the table
 129  */
 130
 131 int mprRemoveSymbol(MprSymbolTable *table, const char *key)
 132 {
 133         MprSymbol       *sp, *prevSp;
 134         int                     index;
 135
 136         if ((sp = lookupInner(&index, &prevSp, table, key)) == 0) {
 137                 return MPR_ERR_NOT_FOUND;
 138         }
 139
 140         if (prevSp) {
 141                 prevSp->next = sp->next;
 142         } else {
 143                 table->buckets[index] = sp->next;
 144         }
 145         table->count--;
 146
 147         mprFree(sp);
 148         return 0;
 149 }
 150
 151 /******************************************************************************/
 152 /*
 153  *      Lookup a key and return the hash entry
 154  */
 155
 156 void *mprLookupSymbol(MprSymbolTable *table, const char *key)
 157 {
 158         MprSymbol       *sp;
 159
 160         mprAssert(key);
 161
 162         sp = lookupInner(0, 0, table, key);
 163         if (sp == 0) {
 164                 return 0;
 165         }
 166         return sp->data;
 167 }
 168
 169 /******************************************************************************/
 170
 171 static MprSymbol *lookupInner(int *bucketIndex, MprSymbol **prevSp,
 172         MprSymbolTable *table, const char *key)
 173 {
 174         MprSymbol       *sp, *prev;
 175         int                     index, rc;
 176
 177         mprAssert(key);
 178
 179         index = hashIndex(key, table->hashSize);
 180         if (bucketIndex) {
 181                 *bucketIndex = index;
 182         }
 183
 184         sp = table->buckets[index];
 185         prev = 0;
 186
 187         while (sp) {
 188                 rc = strcmp(sp->key, key);
 189                 if (rc == 0) {
 190                         if (prevSp) {
 191                                 *prevSp = prev;
 192                         }
 193                         return sp;
 194                 }
 195                 prev = sp;
 196                 mprAssert(sp != sp->next);
 197                 sp = sp->next;
 198         }
 199         return 0;
 200 }
 201
 202 /******************************************************************************/
 203
 204 int mprGetSymbolCount(MprSymbolTable *table)
 205 {
 206         return table->count;
 207 }
 208
 209 /******************************************************************************/
 210 /*
 211  *      Return the first entry in the table.
 212  */
 213
 214 MprSymbol *mprGetFirstSymTab(MprSymbolTable *table)
 215 {
 216         MprSymbol       *sp;
 217         int                     i;
 218
 219         mprAssert(table);
 220
 221         for (i = 0; i < table->hashSize; i++) {
 222                 if ((sp = (MprSymbol*) table->buckets[i]) != 0) {
 223                         return sp;
 224                 }
 225         }
 226         return 0;
 227 }
 228
 229 /******************************************************************************/
 230 /*
 231  *      Return the next entry in the table
 232  */
 233
 234 MprSymbol *mprGetNextSymTab(MprSymbolTable *table, MprSymbol *last)
 235 {
 236         MprSymbol       *sp;
 237         int                     i;
 238
 239         mprAssert(table);
 240
 241         if (last->next) {
 242                 return last->next;
 243         }
 244
 245         for (i = last->bucket + 1; i < table->hashSize; i++) {
 246                 if ((sp = (MprSymbol*) table->buckets[i]) != 0) {
 247                         return sp;
 248                 }
 249         }
 250         return 0;
 251 }
 252
 253 /******************************************************************************/
 254 /*
 255  *      Hash the key to produce a hash index.
 256  */
 257
 258 static int hashIndex(const char *key, int size)
 259 {
 260         uint            sum;
 261
 262         sum = 0;
 263         while (*key) {
 264                 sum += (sum * 33) + *key++;
 265         }
 266
 267         return sum % size;
 268 }
 269
 270 /******************************************************************************/
 271 /*
 272  * Local variables:
 273  * tab-width: 4
 274  * c-basic-offset: 4
 275  * End:
 276  * vim:tw=78
 277  * vim600: sw=4 ts=4 fdm=marker
 278  * vim<600: sw=4 ts=4
 279  */