third_party/sqlite/sqlite-src-3080704/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 ){
  59     h = (h<<3) ^ h ^ sqlite3UpperToLower[c];
  60   }
  61   return h;
  62 }
  63
  64
  65 /* Link pNew element into the hash table pH.  If pEntry!=0 then also
  66 ** insert pNew into the pEntry hash bucket.
  67 */
  68 static void insertElement(
  69   Hash *pH,              /* The complete hash table */
  70   struct _ht *pEntry,    /* The entry into which pNew is inserted */
  71   HashElem *pNew         /* The element to be inserted */
  72 ){
  73   HashElem *pHead;       /* First element already in pEntry */
  74   if( pEntry ){
  75     pHead = pEntry->count ? pEntry->chain : 0;
  76     pEntry->count++;
  77     pEntry->chain = pNew;
  78   }else{
  79     pHead = 0;
  80   }
  81   if( pHead ){
  82     pNew->next = pHead;
  83     pNew->prev = pHead->prev;
  84     if( pHead->prev ){ pHead->prev->next = pNew; }
  85     else             { pH->first = pNew; }
  86     pHead->prev = pNew;
  87   }else{
  88     pNew->next = pH->first;
  89     if( pH->first ){ pH->first->prev = pNew; }
  90     pNew->prev = 0;
  91     pH->first = pNew;
  92   }
  93 }
  94
  95
  96 /* Resize the hash table so that it cantains "new_size" buckets.
  97 **
  98 ** The hash table might fail to resize if sqlite3_malloc() fails or
  99 ** if the new size is the same as the prior size.
 100 ** Return TRUE if the resize occurs and false if not.
 101 */
 102 static int rehash(Hash *pH, unsigned int new_size){
 103   struct _ht *new_ht;            /* The new hash table */
 104   HashElem *elem, *next_elem;    /* For looping over existing elements */
 105
 106 #if SQLITE_MALLOC_SOFT_LIMIT>0
 107   if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){
 108     new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);
 109   }
 110   if( new_size==pH->htsize ) return 0;
 111 #endif
 112
 113   /* The inability to allocates space for a larger hash table is
 114   ** a performance hit but it is not a fatal error.  So mark the
 115   ** allocation as a benign. Use sqlite3Malloc()/memset(0) instead of
 116   ** sqlite3MallocZero() to make the allocation, as sqlite3MallocZero()
 117   ** only zeroes the requested number of bytes whereas this module will
 118   ** use the actual amount of space allocated for the hash table (which
 119   ** may be larger than the requested amount).
 120   */
 121   sqlite3BeginBenignMalloc();
 122   new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) );
 123   sqlite3EndBenignMalloc();
 124
 125   if( new_ht==0 ) return 0;
 126   sqlite3_free(pH->ht);
 127   pH->ht = new_ht;
 128   pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht);
 129   memset(new_ht, 0, new_size*sizeof(struct _ht));
 130   for(elem=pH->first, pH->first=0; elem; elem = next_elem){
 131     unsigned int h = strHash(elem->pKey) % new_size;
 132     next_elem = elem->next;
 133     insertElement(pH, &new_ht[h], elem);
 134   }
 135   return 1;
 136 }
 137
 138 /* This function (for internal use only) locates an element in an
 139 ** hash table that matches the given key.  The hash for this key is
 140 ** also computed and returned in the *pH parameter.
 141 */
 142 static HashElem *findElementWithHash(
 143   const Hash *pH,     /* The pH to be searched */
 144   const char *pKey,   /* The key we are searching for */
 145   unsigned int *pHash /* Write the hash value here */
 146 ){
 147   HashElem *elem;                /* Used to loop thru the element list */
 148   int count;                     /* Number of elements left to test */
 149   unsigned int h;                /* The computed hash */
 150
 151   if( pH->ht ){
 152     struct _ht *pEntry;
 153     h = strHash(pKey) % pH->htsize;
 154     pEntry = &pH->ht[h];
 155     elem = pEntry->chain;
 156     count = pEntry->count;
 157   }else{
 158     h = 0;
 159     elem = pH->first;
 160     count = pH->count;
 161   }
 162   *pHash = h;
 163   while( count-- ){
 164     assert( elem!=0 );
 165     if( sqlite3StrICmp(elem->pKey,pKey)==0 ){
 166       return elem;
 167     }
 168     elem = elem->next;
 169   }
 170   return 0;
 171 }
 172
 173 /* Remove a single entry from the hash table given a pointer to that
 174 ** element and a hash on the element's key.
 175 */
 176 static void removeElementGivenHash(
 177   Hash *pH,         /* The pH containing "elem" */
 178   HashElem* elem,   /* The element to be removed from the pH */
 179   unsigned int h    /* Hash value for the element */
 180 ){
 181   struct _ht *pEntry;
 182   if( elem->prev ){
 183     elem->prev->next = elem->next;
 184   }else{
 185     pH->first = elem->next;
 186   }
 187   if( elem->next ){
 188     elem->next->prev = elem->prev;
 189   }
 190   if( pH->ht ){
 191     pEntry = &pH->ht[h];
 192     if( pEntry->chain==elem ){
 193       pEntry->chain = elem->next;
 194     }
 195     pEntry->count--;
 196     assert( pEntry->count>=0 );
 197   }
 198   sqlite3_free( elem );
 199   pH->count--;
 200   if( pH->count==0 ){
 201     assert( pH->first==0 );
 202     assert( pH->count==0 );
 203     sqlite3HashClear(pH);
 204   }
 205 }
 206
 207 /* Attempt to locate an element of the hash table pH with a key
 208 ** that matches pKey.  Return the data for this element if it is
 209 ** found, or NULL if there is no match.
 210 */
 211 void *sqlite3HashFind(const Hash *pH, const char *pKey){
 212   HashElem *elem;    /* The element that matches key */
 213   unsigned int h;    /* A hash on key */
 214
 215   assert( pH!=0 );
 216   assert( pKey!=0 );
 217   elem = findElementWithHash(pH, pKey, &h);
 218   return elem ? elem->data : 0;
 219 }
 220
 221 /* Insert an element into the hash table pH.  The key is pKey
 222 ** and the data is "data".
 223 **
 224 ** If no element exists with a matching key, then a new
 225 ** element is created and NULL is returned.
 226 **
 227 ** If another element already exists with the same key, then the
 228 ** new data replaces the old data and the old data is returned.
 229 ** The key is not copied in this instance.  If a malloc fails, then
 230 ** the new data is returned and the hash table is unchanged.
 231 **
 232 ** If the "data" parameter to this function is NULL, then the
 233 ** element corresponding to "key" is removed from the hash table.
 234 */
 235 void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
 236   unsigned int h;       /* the hash of the key modulo hash table size */
 237   HashElem *elem;       /* Used to loop thru the element list */
 238   HashElem *new_elem;   /* New element added to the pH */
 239
 240   assert( pH!=0 );
 241   assert( pKey!=0 );
 242   elem = findElementWithHash(pH,pKey,&h);
 243   if( elem ){
 244     void *old_data = elem->data;
 245     if( data==0 ){
 246       removeElementGivenHash(pH,elem,h);
 247     }else{
 248       elem->data = data;
 249       elem->pKey = pKey;
 250     }
 251     return old_data;
 252   }
 253   if( data==0 ) return 0;
 254   new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
 255   if( new_elem==0 ) return data;
 256   new_elem->pKey = pKey;
 257   new_elem->data = data;
 258   pH->count++;
 259   if( pH->count>=10 && pH->count > 2*pH->htsize ){
 260     if( rehash(pH, pH->count*2) ){
 261       assert( pH->htsize>0 );
 262       h = strHash(pKey) % pH->htsize;
 263     }
 264   }
 265   insertElement(pH, pH->ht ? &pH->ht[h] : 0, new_elem);
 266   return 0;
 267 }