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: hash.c,v 1.31 2008/10/10 17:41:29 drh Exp $

    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 ** "copyKey" is true if the hash table should make its own private

    25 ** copy of keys and false if it should just use the supplied pointer.

    26 */

    27 void sqlite3HashInit(Hash *pNew, int copyKey){

    28   assert( pNew!=0 );

    29   pNew->copyKey = copyKey!=0;

    30   pNew->first = 0;

    31   pNew->count = 0;

    32   pNew->htsize = 0;

    33   pNew->ht = 0;

    34 }

    35 

    36 /* Remove all entries from a hash table.  Reclaim all memory.

    37 ** Call this routine to delete a hash table or to reset a hash table

    38 ** to the empty state.

    39 */

    40 void sqlite3HashClear(Hash *pH){

    41   HashElem *elem;         /* For looping over all elements of the table */

    42 

    43   assert( pH!=0 );

    44   elem = pH->first;

    45   pH->first = 0;

    46   sqlite3_free(pH->ht);

    47   pH->ht = 0;

    48   pH->htsize = 0;

    49   while( elem ){

    50     HashElem *next_elem = elem->next;

    51     if( pH->copyKey && elem->pKey ){

    52       sqlite3_free(elem->pKey);

    53     }

    54     sqlite3_free(elem);

    55     elem = next_elem;

    56   }

    57   pH->count = 0;

    58 }

    59 

    60 /*

    61 ** Hash and comparison functions when the mode is SQLITE_HASH_STRING

    62 */

    63 static int strHash(const void *pKey, int nKey){

    64   const char *z = (const char *)pKey;

    65   int h = 0;

    66   if( nKey<=0 ) nKey = strlen(z);

    67   while( nKey > 0  ){

    68     h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];

    69     nKey--;

    70   }

    71   return h & 0x7fffffff;

    72 }

    73 static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){

    74   if( n1!=n2 ) return 1;

    75   return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);

    76 }

    77 

    78 

    79 /* Link an element into the hash table

    80 */

    81 static void insertElement(

    82   Hash *pH,              /* The complete hash table */

    83   struct _ht *pEntry,    /* The entry into which pNew is inserted */

    84   HashElem *pNew         /* The element to be inserted */

    85 ){

    86   HashElem *pHead;       /* First element already in pEntry */

    87   pHead = pEntry->chain;

    88   if( pHead ){

    89     pNew->next = pHead;

    90     pNew->prev = pHead->prev;

    91     if( pHead->prev ){ pHead->prev->next = pNew; }

    92     else             { pH->first = pNew; }

    93     pHead->prev = pNew;

    94   }else{

    95     pNew->next = pH->first;

    96     if( pH->first ){ pH->first->prev = pNew; }

    97     pNew->prev = 0;

    98     pH->first = pNew;

    99   }

   100   pEntry->count++;

   101   pEntry->chain = pNew;

   102 }

   103 

   104 

   105 /* Resize the hash table so that it cantains "new_size" buckets.

   106 ** "new_size" must be a power of 2.  The hash table might fail 

   107 ** to resize if sqlite3_malloc() fails.

   108 */

   109 static void rehash(Hash *pH, int new_size){

   110   struct _ht *new_ht;            /* The new hash table */

   111   HashElem *elem, *next_elem;    /* For looping over existing elements */

   112 

   113 #ifdef SQLITE_MALLOC_SOFT_LIMIT

   114   if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){

   115     new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);

   116   }

   117   if( new_size==pH->htsize ) return;

   118 #endif

   119 

   120   /* There is a call to sqlite3_malloc() inside rehash(). If there is

   121   ** already an allocation at pH->ht, then if this malloc() fails it

   122   ** is benign (since failing to resize a hash table is a performance

   123   ** hit only, not a fatal error).

   124   */

   125   if( pH->htsize>0 ) sqlite3BeginBenignMalloc();

   126   new_ht = (struct _ht *)sqlite3MallocZero( new_size*sizeof(struct _ht) );

   127   if( pH->htsize>0 ) sqlite3EndBenignMalloc();

   128 

   129   if( new_ht==0 ) return;

   130   sqlite3_free(pH->ht);

   131   pH->ht = new_ht;

   132   pH->htsize = new_size;

   133   for(elem=pH->first, pH->first=0; elem; elem = next_elem){

   134     int h = strHash(elem->pKey, elem->nKey) & (new_size-1);

   135     next_elem = elem->next;

   136     insertElement(pH, &new_ht[h], elem);

   137   }

   138 }

   139 

   140 /* This function (for internal use only) locates an element in an

   141 ** hash table that matches the given key.  The hash for this key has

   142 ** already been computed and is passed as the 4th parameter.

   143 */

   144 static HashElem *findElementGivenHash(

   145   const Hash *pH,     /* The pH to be searched */

   146   const void *pKey,   /* The key we are searching for */

   147   int nKey,

   148   int h               /* The hash for this key. */

   149 ){

   150   HashElem *elem;                /* Used to loop thru the element list */

   151   int count;                     /* Number of elements left to test */

   152 

   153   if( pH->ht ){

   154     struct _ht *pEntry = &pH->ht[h];

   155     elem = pEntry->chain;

   156     count = pEntry->count;

   157     while( count-- && elem ){

   158       if( strCompare(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 

   159         return elem;

   160       }

   161       elem = elem->next;

   162     }

   163   }

   164   return 0;

   165 }

   166 

   167 /* Remove a single entry from the hash table given a pointer to that

   168 ** element and a hash on the element's key.

   169 */

   170 static void removeElementGivenHash(

   171   Hash *pH,         /* The pH containing "elem" */

   172   HashElem* elem,   /* The element to be removed from the pH */

   173   int h             /* Hash value for the element */

   174 ){

   175   struct _ht *pEntry;

   176   if( elem->prev ){

   177     elem->prev->next = elem->next; 

   178   }else{

   179     pH->first = elem->next;

   180   }

   181   if( elem->next ){

   182     elem->next->prev = elem->prev;

   183   }

   184   pEntry = &pH->ht[h];

   185   if( pEntry->chain==elem ){

   186     pEntry->chain = elem->next;

   187   }

   188   pEntry->count--;

   189   if( pEntry->count<=0 ){

   190     pEntry->chain = 0;

   191   }

   192   if( pH->copyKey ){

   193     sqlite3_free(elem->pKey);

   194   }

   195   sqlite3_free( elem );

   196   pH->count--;

   197   if( pH->count<=0 ){

   198     assert( pH->first==0 );

   199     assert( pH->count==0 );

   200     sqlite3HashClear(pH);

   201   }

   202 }

   203 

   204 /* Attempt to locate an element of the hash table pH with a key

   205 ** that matches pKey,nKey.  Return a pointer to the corresponding 

   206 ** HashElem structure for this element if it is found, or NULL

   207 ** otherwise.

   208 */

   209 HashElem *sqlite3HashFindElem(const Hash *pH, const void *pKey, int nKey){

   210   int h;             /* A hash on key */

   211   HashElem *elem;    /* The element that matches key */

   212 

   213   if( pH==0 || pH->ht==0 ) return 0;

   214   h = strHash(pKey,nKey);

   215   elem = findElementGivenHash(pH,pKey,nKey, h % pH->htsize);

   216   return elem;

   217 }

   218 

   219 /* Attempt to locate an element of the hash table pH with a key

   220 ** that matches pKey,nKey.  Return the data for this element if it is

   221 ** found, or NULL if there is no match.

   222 */

   223 void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){

   224   HashElem *elem;    /* The element that matches key */

   225   elem = sqlite3HashFindElem(pH, pKey, nKey);

   226   return elem ? elem->data : 0;

   227 }

   228 

   229 /* Insert an element into the hash table pH.  The key is pKey,nKey

   230 ** and the data is "data".

   231 **

   232 ** If no element exists with a matching key, then a new

   233 ** element is created.  A copy of the key is made if the copyKey

   234 ** flag is set.  NULL is returned.

   235 **

   236 ** If another element already exists with the same key, then the

   237 ** new data replaces the old data and the old data is returned.

   238 ** The key is not copied in this instance.  If a malloc fails, then

   239 ** the new data is returned and the hash table is unchanged.

   240 **

   241 ** If the "data" parameter to this function is NULL, then the

   242 ** element corresponding to "key" is removed from the hash table.

   243 */

   244 void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){

   245   int hraw;             /* Raw hash value of the key */

   246   int h;                /* the hash of the key modulo hash table size */

   247   HashElem *elem;       /* Used to loop thru the element list */

   248   HashElem *new_elem;   /* New element added to the pH */

   249 

   250   assert( pH!=0 );

   251   hraw = strHash(pKey, nKey);

   252   if( pH->htsize ){

   253     h = hraw % pH->htsize;

   254     elem = findElementGivenHash(pH,pKey,nKey,h);

   255     if( elem ){

   256       void *old_data = elem->data;

   257       if( data==0 ){

   258         removeElementGivenHash(pH,elem,h);

   259       }else{

   260         elem->data = data;

   261         if( !pH->copyKey ){

   262           elem->pKey = (void *)pKey;

   263         }

   264         assert(nKey==elem->nKey);

   265       }

   266       return old_data;

   267     }

   268   }

   269   if( data==0 ) return 0;

   270   new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );

   271   if( new_elem==0 ) return data;

   272   if( pH->copyKey && pKey!=0 ){

   273     new_elem->pKey = sqlite3Malloc( nKey );

   274     if( new_elem->pKey==0 ){

   275       sqlite3_free(new_elem);

   276       return data;

   277     }

   278     memcpy((void*)new_elem->pKey, pKey, nKey);

   279   }else{

   280     new_elem->pKey = (void*)pKey;

   281   }

   282   new_elem->nKey = nKey;

   283   pH->count++;

   284   if( pH->htsize==0 ){

   285     rehash(pH, 128/sizeof(pH->ht[0]));

   286     if( pH->htsize==0 ){

   287       pH->count = 0;

   288       if( pH->copyKey ){

   289         sqlite3_free(new_elem->pKey);

   290       }

   291       sqlite3_free(new_elem);

   292       return data;

   293     }

   294   }

   295   if( pH->count > pH->htsize ){

   296     rehash(pH,pH->htsize*2);

   297   }

   298   assert( pH->htsize>0 );

   299   h = hraw % pH->htsize;

   300   insertElement(pH, &pH->ht[h], new_elem);

   301   new_elem->data = data;

   302   return 0;

   303 }