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 contains "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   unsigned 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     count--;
 176   }
 177   return &nullElement;
 178 }
 179
 180 /* Remove a single entry from the hash table given a pointer to that
 181 ** element and a hash on the element's key.
 182 */
 183 static void removeElementGivenHash(
 184   Hash *pH,         /* The pH containing "elem" */
 185   HashElem* elem,   /* The element to be removed from the pH */
 186   unsigned int h    /* Hash value for the element */
 187 ){
 188   struct _ht *pEntry;
 189   if( elem->prev ){
 190     elem->prev->next = elem->next;
 191   }else{
 192     pH->first = elem->next;
 193   }
 194   if( elem->next ){
 195     elem->next->prev = elem->prev;
 196   }
 197   if( pH->ht ){
 198     pEntry = &pH->ht[h];
 199     if( pEntry->chain==elem ){
 200       pEntry->chain = elem->next;
 201     }
 202     assert( pEntry->count>0 );
 203     pEntry->count--;
 204   }
 205   sqlite3_free( elem );
 206   pH->count--;
 207   if( pH->count==0 ){
 208     assert( pH->first==0 );
 209     assert( pH->count==0 );
 210     sqlite3HashClear(pH);
 211   }
 212 }
 213
 214 /* Attempt to locate an element of the hash table pH with a key
 215 ** that matches pKey.  Return the data for this element if it is
 216 ** found, or NULL if there is no match.
 217 */
 218 void *sqlite3HashFind(const Hash *pH, const char *pKey){
 219   assert( pH!=0 );
 220   assert( pKey!=0 );
 221   return findElementWithHash(pH, pKey, 0)->data;
 222 }
 223
 224 /* Insert an element into the hash table pH.  The key is pKey
 225 ** and the data is "data".
 226 **
 227 ** If no element exists with a matching key, then a new
 228 ** element is created and NULL is returned.
 229 **
 230 ** If another element already exists with the same key, then the
 231 ** new data replaces the old data and the old data is returned.
 232 ** The key is not copied in this instance.  If a malloc fails, then
 233 ** the new data is returned and the hash table is unchanged.
 234 **
 235 ** If the "data" parameter to this function is NULL, then the
 236 ** element corresponding to "key" is removed from the hash table.
 237 */
 238 void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
 239   unsigned int h;       /* the hash of the key modulo hash table size */
 240   HashElem *elem;       /* Used to loop thru the element list */
 241   HashElem *new_elem;   /* New element added to the pH */
 242
 243   assert( pH!=0 );
 244   assert( pKey!=0 );
 245   elem = findElementWithHash(pH,pKey,&h);
 246   if( elem->data ){
 247     void *old_data = elem->data;
 248     if( data==0 ){
 249       removeElementGivenHash(pH,elem,h);
 250     }else{
 251       elem->data = data;
 252       elem->pKey = pKey;
 253     }
 254     return old_data;
 255   }
 256   if( data==0 ) return 0;
 257   new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
 258   if( new_elem==0 ) return data;
 259   new_elem->pKey = pKey;
 260   new_elem->data = data;
 261   pH->count++;
 262   if( pH->count>=10 && pH->count > 2*pH->htsize ){
 263     if( rehash(pH, pH->count*2) ){
 264       assert( pH->htsize>0 );
 265       h = strHash(pKey) % pH->htsize;
 266     }
 267   }
 268   insertElement(pH, pH->ht ? &pH->ht[h] : 0, new_elem);
 269   return 0;
 270 }