sqlite3/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 ** $Id$
  16 */
  17 #include "sqliteInt.h"
  18 #include <assert.h>
  19
  20 /* Turn bulk memory into a hash table object by initializing the
  21 ** fields of the Hash structure.
  22 **
  23 ** "pNew" is a pointer to the hash table that is to be initialized.
  24 ** keyClass is one of the constants SQLITE_HASH_INT, SQLITE_HASH_POINTER,
  25 ** SQLITE_HASH_BINARY, or SQLITE_HASH_STRING.  The value of keyClass
  26 ** determines what kind of key the hash table will use.  "copyKey" is
  27 ** true if the hash table should make its own private copy of keys and
  28 ** false if it should just use the supplied pointer.  CopyKey only makes
  29 ** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
  30 ** for other key classes.
  31 */
  32 void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
  33   assert( pNew!=0 );
  34   assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
  35   pNew->keyClass = keyClass;
  36 #if 0
  37   if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
  38 #endif
  39   pNew->copyKey = copyKey;
  40   pNew->first = 0;
  41   pNew->count = 0;
  42   pNew->htsize = 0;
  43   pNew->ht = 0;
  44 }
  45
  46 /* Remove all entries from a hash table.  Reclaim all memory.
  47 ** Call this routine to delete a hash table or to reset a hash table
  48 ** to the empty state.
  49 */
  50 void sqlite3HashClear(Hash *pH){
  51   HashElem *elem;         /* For looping over all elements of the table */
  52
  53   assert( pH!=0 );
  54   elem = pH->first;
  55   pH->first = 0;
  56   if( pH->ht ) sqliteFree(pH->ht);
  57   pH->ht = 0;
  58   pH->htsize = 0;
  59   while( elem ){
  60     HashElem *next_elem = elem->next;
  61     if( pH->copyKey && elem->pKey ){
  62       sqliteFree(elem->pKey);
  63     }
  64     sqliteFree(elem);
  65     elem = next_elem;
  66   }
  67   pH->count = 0;
  68 }
  69
  70 #if 0 /* NOT USED */
  71 /*
  72 ** Hash and comparison functions when the mode is SQLITE_HASH_INT
  73 */
  74 static int intHash(const void *pKey, int nKey){
  75   return nKey ^ (nKey<<8) ^ (nKey>>8);
  76 }
  77 static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  78   return n2 - n1;
  79 }
  80 #endif
  81
  82 #if 0 /* NOT USED */
  83 /*
  84 ** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
  85 */
  86 static int ptrHash(const void *pKey, int nKey){
  87   uptr x = Addr(pKey);
  88   return x ^ (x<<8) ^ (x>>8);
  89 }
  90 static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
  91   if( pKey1==pKey2 ) return 0;
  92   if( pKey1<pKey2 ) return -1;
  93   return 1;
  94 }
  95 #endif
  96
  97 /*
  98 ** Hash and comparison functions when the mode is SQLITE_HASH_STRING
  99 */
 100 static int strHash(const void *pKey, int nKey){
 101   const char *z = (const char *)pKey;
 102   int h = 0;
 103   if( nKey<=0 ) nKey = strlen(z);
 104   while( nKey > 0  ){
 105     h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
 106     nKey--;
 107   }
 108   return h & 0x7fffffff;
 109 }
 110 static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 111   if( n1!=n2 ) return 1;
 112   return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
 113 }
 114
 115 /*
 116 ** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
 117 */
 118 static int binHash(const void *pKey, int nKey){
 119   int h = 0;
 120   const char *z = (const char *)pKey;
 121   while( nKey-- > 0 ){
 122     h = (h<<3) ^ h ^ *(z++);
 123   }
 124   return h & 0x7fffffff;
 125 }
 126 static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
 127   if( n1!=n2 ) return 1;
 128   return memcmp(pKey1,pKey2,n1);
 129 }
 130
 131 /*
 132 ** Return a pointer to the appropriate hash function given the key class.
 133 **
 134 ** The C syntax in this function definition may be unfamilar to some
 135 ** programmers, so we provide the following additional explanation:
 136 **
 137 ** The name of the function is "hashFunction".  The function takes a
 138 ** single parameter "keyClass".  The return value of hashFunction()
 139 ** is a pointer to another function.  Specifically, the return value
 140 ** of hashFunction() is a pointer to a function that takes two parameters
 141 ** with types "const void*" and "int" and returns an "int".
 142 */
 143 static int (*hashFunction(int keyClass))(const void*,int){
 144 #if 0  /* HASH_INT and HASH_POINTER are never used */
 145   switch( keyClass ){
 146     case SQLITE_HASH_INT:     return &intHash;
 147     case SQLITE_HASH_POINTER: return &ptrHash;
 148     case SQLITE_HASH_STRING:  return &strHash;
 149     case SQLITE_HASH_BINARY:  return &binHash;;
 150     default: break;
 151   }
 152   return 0;
 153 #else
 154   if( keyClass==SQLITE_HASH_STRING ){
 155     return &strHash;
 156   }else{
 157     assert( keyClass==SQLITE_HASH_BINARY );
 158     return &binHash;
 159   }
 160 #endif
 161 }
 162
 163 /*
 164 ** Return a pointer to the appropriate hash function given the key class.
 165 **
 166 ** For help in interpreted the obscure C code in the function definition,
 167 ** see the header comment on the previous function.
 168 */
 169 static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
 170 #if 0 /* HASH_INT and HASH_POINTER are never used */
 171   switch( keyClass ){
 172     case SQLITE_HASH_INT:     return &intCompare;
 173     case SQLITE_HASH_POINTER: return &ptrCompare;
 174     case SQLITE_HASH_STRING:  return &strCompare;
 175     case SQLITE_HASH_BINARY:  return &binCompare;
 176     default: break;
 177   }
 178   return 0;
 179 #else
 180   if( keyClass==SQLITE_HASH_STRING ){
 181     return &strCompare;
 182   }else{
 183     assert( keyClass==SQLITE_HASH_BINARY );
 184     return &binCompare;
 185   }
 186 #endif
 187 }
 188
 189 /* Link an element into the hash table
 190 */
 191 static void insertElement(
 192   Hash *pH,              /* The complete hash table */
 193   struct _ht *pEntry,    /* The entry into which pNew is inserted */
 194   HashElem *pNew         /* The element to be inserted */
 195 ){
 196   HashElem *pHead;       /* First element already in pEntry */
 197   pHead = pEntry->chain;
 198   if( pHead ){
 199     pNew->next = pHead;
 200     pNew->prev = pHead->prev;
 201     if( pHead->prev ){ pHead->prev->next = pNew; }
 202     else             { pH->first = pNew; }
 203     pHead->prev = pNew;
 204   }else{
 205     pNew->next = pH->first;
 206     if( pH->first ){ pH->first->prev = pNew; }
 207     pNew->prev = 0;
 208     pH->first = pNew;
 209   }
 210   pEntry->count++;
 211   pEntry->chain = pNew;
 212 }
 213
 214
 215 /* Resize the hash table so that it cantains "new_size" buckets.
 216 ** "new_size" must be a power of 2.  The hash table might fail
 217 ** to resize if sqliteMalloc() fails.
 218 */
 219 static void rehash(Hash *pH, int new_size){
 220   struct _ht *new_ht;            /* The new hash table */
 221   HashElem *elem, *next_elem;    /* For looping over existing elements */
 222   int (*xHash)(const void*,int); /* The hash function */
 223
 224   assert( (new_size & (new_size-1))==0 );
 225   new_ht = (struct _ht *)sqliteMalloc( new_size*sizeof(struct _ht) );
 226   if( new_ht==0 ) return;
 227   if( pH->ht ) sqliteFree(pH->ht);
 228   pH->ht = new_ht;
 229   pH->htsize = new_size;
 230   xHash = hashFunction(pH->keyClass);
 231   for(elem=pH->first, pH->first=0; elem; elem = next_elem){
 232     int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
 233     next_elem = elem->next;
 234     insertElement(pH, &new_ht[h], elem);
 235   }
 236 }
 237
 238 /* This function (for internal use only) locates an element in an
 239 ** hash table that matches the given key.  The hash for this key has
 240 ** already been computed and is passed as the 4th parameter.
 241 */
 242 static HashElem *findElementGivenHash(
 243   const Hash *pH,     /* The pH to be searched */
 244   const void *pKey,   /* The key we are searching for */
 245   int nKey,
 246   int h               /* The hash for this key. */
 247 ){
 248   HashElem *elem;                /* Used to loop thru the element list */
 249   int count;                     /* Number of elements left to test */
 250   int (*xCompare)(const void*,int,const void*,int);  /* comparison function */
 251
 252   if( pH->ht ){
 253     struct _ht *pEntry = &pH->ht[h];
 254     elem = pEntry->chain;
 255     count = pEntry->count;
 256     xCompare = compareFunction(pH->keyClass);
 257     while( count-- && elem ){
 258       if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
 259         return elem;
 260       }
 261       elem = elem->next;
 262     }
 263   }
 264   return 0;
 265 }
 266
 267 /* Remove a single entry from the hash table given a pointer to that
 268 ** element and a hash on the element's key.
 269 */
 270 static void removeElementGivenHash(
 271   Hash *pH,         /* The pH containing "elem" */
 272   HashElem* elem,   /* The element to be removed from the pH */
 273   int h             /* Hash value for the element */
 274 ){
 275   struct _ht *pEntry;
 276   if( elem->prev ){
 277     elem->prev->next = elem->next;
 278   }else{
 279     pH->first = elem->next;
 280   }
 281   if( elem->next ){
 282     elem->next->prev = elem->prev;
 283   }
 284   pEntry = &pH->ht[h];
 285   if( pEntry->chain==elem ){
 286     pEntry->chain = elem->next;
 287   }
 288   pEntry->count--;
 289   if( pEntry->count<=0 ){
 290     pEntry->chain = 0;
 291   }
 292   if( pH->copyKey && elem->pKey ){
 293     sqliteFree(elem->pKey);
 294   }
 295   sqliteFree( elem );
 296   pH->count--;
 297 }
 298
 299 /* Attempt to locate an element of the hash table pH with a key
 300 ** that matches pKey,nKey.  Return the data for this element if it is
 301 ** found, or NULL if there is no match.
 302 */
 303 void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
 304   int h;             /* A hash on key */
 305   HashElem *elem;    /* The element that matches key */
 306   int (*xHash)(const void*,int);  /* The hash function */
 307
 308   if( pH==0 || pH->ht==0 ) return 0;
 309   xHash = hashFunction(pH->keyClass);
 310   assert( xHash!=0 );
 311   h = (*xHash)(pKey,nKey);
 312   assert( (pH->htsize & (pH->htsize-1))==0 );
 313   elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
 314   return elem ? elem->data : 0;
 315 }
 316
 317 /* Insert an element into the hash table pH.  The key is pKey,nKey
 318 ** and the data is "data".
 319 **
 320 ** If no element exists with a matching key, then a new
 321 ** element is created.  A copy of the key is made if the copyKey
 322 ** flag is set.  NULL is returned.
 323 **
 324 ** If another element already exists with the same key, then the
 325 ** new data replaces the old data and the old data is returned.
 326 ** The key is not copied in this instance.  If a malloc fails, then
 327 ** the new data is returned and the hash table is unchanged.
 328 **
 329 ** If the "data" parameter to this function is NULL, then the
 330 ** element corresponding to "key" is removed from the hash table.
 331 */
 332 void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
 333   int hraw;             /* Raw hash value of the key */
 334   int h;                /* the hash of the key modulo hash table size */
 335   HashElem *elem;       /* Used to loop thru the element list */
 336   HashElem *new_elem;   /* New element added to the pH */
 337   int (*xHash)(const void*,int);  /* The hash function */
 338
 339   assert( pH!=0 );
 340   xHash = hashFunction(pH->keyClass);
 341   assert( xHash!=0 );
 342   hraw = (*xHash)(pKey, nKey);
 343   assert( (pH->htsize & (pH->htsize-1))==0 );
 344   h = hraw & (pH->htsize-1);
 345   elem = findElementGivenHash(pH,pKey,nKey,h);
 346   if( elem ){
 347     void *old_data = elem->data;
 348     if( data==0 ){
 349       removeElementGivenHash(pH,elem,h);
 350     }else{
 351       elem->data = data;
 352     }
 353     return old_data;
 354   }
 355   if( data==0 ) return 0;
 356   new_elem = (HashElem*)sqliteMalloc( sizeof(HashElem) );
 357   if( new_elem==0 ) return data;
 358   if( pH->copyKey && pKey!=0 ){
 359     new_elem->pKey = sqliteMallocRaw( nKey );
 360     if( new_elem->pKey==0 ){
 361       sqliteFree(new_elem);
 362       return data;
 363     }
 364     memcpy((void*)new_elem->pKey, pKey, nKey);
 365   }else{
 366     new_elem->pKey = (void*)pKey;
 367   }
 368   new_elem->nKey = nKey;
 369   pH->count++;
 370   if( pH->htsize==0 ){
 371     rehash(pH,8);
 372     if( pH->htsize==0 ){
 373       pH->count = 0;
 374       sqliteFree(new_elem);
 375       return data;
 376     }
 377   }
 378   if( pH->count > pH->htsize ){
 379     rehash(pH,pH->htsize*2);
 380   }
 381   assert( pH->htsize>0 );
 382   assert( (pH->htsize & (pH->htsize-1))==0 );
 383   h = hraw & (pH->htsize-1);
 384   insertElement(pH, &pH->ht[h], new_elem);
 385   new_elem->data = data;
 386   return 0;
 387 }