src/hash.c

   1 /*
   2 ** 2001 September 22
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 ** This is the implementation of generic hash-tables
  13 ** used in SQLite.
  14 */
  15 #include "sqliteInt.h"
  16 #include <assert.h>
  17
  18 /* Turn bulk memory into a hash table object by initializing the
  19 ** fields of the Hash structure.
  20 **
  21 ** "pNew" is a pointer to the hash table that is to be initialized.
  22 */
  23 void sqlite3HashInit(Hash *pNew){
  24   assert( pNew!=0 );
  25   pNew->first = 0;
  26   pNew->count = 0;
  27   pNew->htsize = 0;
  28   pNew->ht = 0;
  29 }
  30
  31 /* Remove all entries from a hash table.  Reclaim all memory.
  32 ** Call this routine to delete a hash table or to reset a hash table
  33 ** to the empty state.
  34 */
  35 void sqlite3HashClear(Hash *pH){
  36   HashElem *elem;         /* For looping over all elements of the table */
  37
  38   assert( pH!=0 );
  39   elem = pH->first;
  40   pH->first = 0;
  41   sqlite3_free(pH->ht);
  42   pH->ht = 0;
  43   pH->htsize = 0;
  44   while( elem ){
  45     HashElem *next_elem = elem->next;
  46     sqlite3_free(elem);
  47     elem = next_elem;
  48   }
  49   pH->count = 0;
  50 }
  51
  52 /*
  53 ** The hashing function.
  54 */
  55 static unsigned int strHash(const char *z){
  56   unsigned int h = 0;
  57   unsigned char c;
  58   while( (c = (unsigned char)*z++)!=0 ){     /*OPTIMIZATION-IF-TRUE*/
  59     /* Knuth multiplicative hashing.  (Sorting & Searching, p. 510).
  60     ** 0x9e3779b1 is 2654435761 which is the closest prime number to
  61     ** (2**32)*golden_ratio, where golden_ratio = (sqrt(5) - 1)/2. */
  62     h += sqlite3UpperToLower[c];
  63     h *= 0x9e3779b1;
  64   }
  65   return h;
  66 }
  67
  68
  69 /* Link pNew element into the hash table pH.  If pEntry!=0 then also
  70 ** insert pNew into the pEntry hash bucket.
  71 */
  72 static void insertElement(
  73   Hash *pH,              /* The complete hash table */
  74   struct _ht *pEntry,    /* The entry into which pNew is inserted */
  75   HashElem *pNew         /* The element to be inserted */
  76 ){
  77   HashElem *pHead;       /* First element already in pEntry */
  78   if( pEntry ){
  79     pHead = pEntry->count ? pEntry->chain : 0;
  80     pEntry->count++;
  81     pEntry->chain = pNew;
  82   }else{
  83     pHead = 0;
  84   }
  85   if( pHead ){
  86     pNew->next = pHead;
  87     pNew->prev = pHead->prev;
  88     if( pHead->prev ){ pHead->prev->next = pNew; }
  89     else             { pH->first = pNew; }
  90     pHead->prev = pNew;
  91   }else{
  92     pNew->next = pH->first;
  93     if( pH->first ){ pH->first->prev = pNew; }
  94     pNew->prev = 0;
  95     pH->first = pNew;
  96   }
  97 }
  98
  99
 100 /* Resize the hash table so that it cantains "new_size" buckets.
 101 **
 102 ** The hash table might fail to resize if sqlite3_malloc() fails or
 103 ** if the new size is the same as the prior size.
 104 ** Return TRUE if the resize occurs and false if not.
 105 */
 106 static int rehash(Hash *pH, unsigned int new_size){
 107   struct _ht *new_ht;            /* The new hash table */
 108   HashElem *elem, *next_elem;    /* For looping over existing elements */
 109
 110 #if SQLITE_MALLOC_SOFT_LIMIT>0
 111   if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){
 112     new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);
 113   }
 114   if( new_size==pH->htsize ) return 0;
 115 #endif
 116
 117   /* The inability to allocates space for a larger hash table is
 118   ** a performance hit but it is not a fatal error.  So mark the
 119   ** allocation as a benign. Use sqlite3Malloc()/memset(0) instead of
 120   ** sqlite3MallocZero() to make the allocation, as sqlite3MallocZero()
 121   ** only zeroes the requested number of bytes whereas this module will
 122   ** use the actual amount of space allocated for the hash table (which
 123   ** may be larger than the requested amount).
 124   */
 125   sqlite3BeginBenignMalloc();
 126   new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) );
 127   sqlite3EndBenignMalloc();
 128
 129   if( new_ht==0 ) return 0;
 130   sqlite3_free(pH->ht);
 131   pH->ht = new_ht;
 132   pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht);
 133   memset(new_ht, 0, new_size*sizeof(struct _ht));
 134   for(elem=pH->first, pH->first=0; elem; elem = next_elem){
 135     unsigned int h = strHash(elem->pKey) % new_size;
 136     next_elem = elem->next;
 137     insertElement(pH, &new_ht[h], elem);
 138   }
 139   return 1;
 140 }
 141
 142 /* This function (for internal use only) locates an element in an
 143 ** hash table that matches the given key.  If no element is found,
 144 ** a pointer to a static null element with HashElem.data==0 is returned.
 145 ** If pH is not NULL, then the hash for this key is written to *pH.
 146 */
 147 static HashElem *findElementWithHash(
 148   const Hash *pH,     /* The pH to be searched */
 149   const char *pKey,   /* The key we are searching for */
 150   unsigned int *pHash /* Write the hash value here */
 151 ){
 152   HashElem *elem;                /* Used to loop thru the element list */
 153   int count;                     /* Number of elements left to test */
 154   unsigned int h;                /* The computed hash */
 155   static HashElem nullElement = { 0, 0, 0, 0 };
 156
 157   if( pH->ht ){   /*OPTIMIZATION-IF-TRUE*/
 158     struct _ht *pEntry;
 159     h = strHash(pKey) % pH->htsize;
 160     pEntry = &pH->ht[h];
 161     elem = pEntry->chain;
 162     count = pEntry->count;
 163   }else{
 164     h = 0;
 165     elem = pH->first;
 166     count = pH->count;
 167   }
 168   if( pHash ) *pHash = h;
 169   while( count-- ){
 170     assert( elem!=0 );
 171     if( sqlite3StrICmp(elem->pKey,pKey)==0 ){
 172       return elem;
 173     }
 174     elem = elem->next;
 175   }
 176   return &nullElement;
 177 }
 178
 179 /* Remove a single entry from the hash table given a pointer to that
 180 ** element and a hash on the element's key.
 181 */
 182 static void removeElementGivenHash(
 183   Hash *pH,         /* The pH containing "elem" */
 184   HashElem* elem,   /* The element to be removed from the pH */
 185   unsigned int h    /* Hash value for the element */
 186 ){
 187   struct _ht *pEntry;
 188   if( elem->prev ){
 189     elem->prev->next = elem->next;
 190   }else{
 191     pH->first = elem->next;
 192   }
 193   if( elem->next ){
 194     elem->next->prev = elem->prev;
 195   }
 196   if( pH->ht ){
 197     pEntry = &pH->ht[h];
 198     if( pEntry->chain==elem ){
 199       pEntry->chain = elem->next;
 200     }
 201     pEntry->count--;
 202     assert( pEntry->count>=0 );
 203   }
 204   sqlite3_free( elem );
 205   pH->count--;
 206   if( pH->count==0 ){
 207     assert( pH->first==0 );
 208     assert( pH->count==0 );
 209     sqlite3HashClear(pH);
 210   }
 211 }
 212
 213 /* Attempt to locate an element of the hash table pH with a key
 214 ** that matches pKey.  Return the data for this element if it is
 215 ** found, or NULL if there is no match.
 216 */
 217 void *sqlite3HashFind(const Hash *pH, const char *pKey){
 218   assert( pH!=0 );
 219   assert( pKey!=0 );
 220   return findElementWithHash(pH, pKey, 0)->data;
 221 }
 222
 223 /* Insert an element into the hash table pH.  The key is pKey
 224 ** and the data is "data".
 225 **
 226 ** If no element exists with a matching key, then a new
 227 ** element is created and NULL is returned.
 228 **
 229 ** If another element already exists with the same key, then the
 230 ** new data replaces the old data and the old data is returned.
 231 ** The key is not copied in this instance.  If a malloc fails, then
 232 ** the new data is returned and the hash table is unchanged.
 233 **
 234 ** If the "data" parameter to this function is NULL, then the
 235 ** element corresponding to "key" is removed from the hash table.
 236 */
 237 void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
 238   unsigned int h;       /* the hash of the key modulo hash table size */
 239   HashElem *elem;       /* Used to loop thru the element list */
 240   HashElem *new_elem;   /* New element added to the pH */
 241
 242   assert( pH!=0 );
 243   assert( pKey!=0 );
 244   elem = findElementWithHash(pH,pKey,&h);
 245   if( elem->data ){
 246     void *old_data = elem->data;
 247     if( data==0 ){
 248       removeElementGivenHash(pH,elem,h);
 249     }else{
 250       elem->data = data;
 251       elem->pKey = pKey;
 252     }
 253     return old_data;
 254   }
 255   if( data==0 ) return 0;
 256   new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
 257   if( new_elem==0 ) return data;
 258   new_elem->pKey = pKey;
 259   new_elem->data = data;
 260   pH->count++;
 261   if( pH->count>=10 && pH->count > 2*pH->htsize ){
 262     if( rehash(pH, pH->count*2) ){
 263       assert( pH->htsize>0 );
 264       h = strHash(pKey) % pH->htsize;
 265     }
 266   }
 267   insertElement(pH, pH->ht ? &pH->ht[h] : 0, new_elem);
 268   return 0;
 269 }