[sql] Import reference version of SQLite 3.8.7.4.

third_party/sqlite/sqlite-src-3080704/src/hash.c

 /*
 ** 2001 September 22
 **
 ** The author disclaims copyright to this source code.  In place of
 ** a legal notice, here is a blessing:
 **
 **    May you do good and not evil.
 **    May you find forgiveness for yourself and forgive others.
 **    May you share freely, never taking more than you give.
 **
@@ skipping 34 matching lines @@
     HashElem *next_elem = elem->next;
     sqlite3_free(elem);
     elem = next_elem;
   }
   pH->count = 0;
 }
 
 /*
 ** The hashing function.
 */
-static unsigned int strHash(const char *z, int nKey){
-  int h = 0;
-  assert( nKey>=0 );
-  while( nKey > 0  ){
-    h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
-    nKey--;
+static unsigned int strHash(const char *z){
+  unsigned int h = 0;
+  unsigned char c;
+  while( (c = (unsigned char)*z++)!=0 ){
+    h = (h<<3) ^ h ^ sqlite3UpperToLower[c];
   }
   return h;
 }
 
 
 /* Link pNew element into the hash table pH.  If pEntry!=0 then also
 ** insert pNew into the pEntry hash bucket.
 */
 static void insertElement(
   Hash *pH,              /* The complete hash table */
@@ skipping 35 matching lines @@
 
 #if SQLITE_MALLOC_SOFT_LIMIT>0
   if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){
     new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);
   }
   if( new_size==pH->htsize ) return 0;
 #endif
 
   /* The inability to allocates space for a larger hash table is
   ** a performance hit but it is not a fatal error.  So mark the
-  ** allocation as a benign.
+  ** allocation as a benign. Use sqlite3Malloc()/memset(0) instead of 
+  ** sqlite3MallocZero() to make the allocation, as sqlite3MallocZero()
+  ** only zeroes the requested number of bytes whereas this module will
+  ** use the actual amount of space allocated for the hash table (which
+  ** may be larger than the requested amount).
   */
   sqlite3BeginBenignMalloc();
   new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) );
   sqlite3EndBenignMalloc();
 
   if( new_ht==0 ) return 0;
   sqlite3_free(pH->ht);
   pH->ht = new_ht;
   pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht);
   memset(new_ht, 0, new_size*sizeof(struct _ht));
   for(elem=pH->first, pH->first=0; elem; elem = next_elem){
-    unsigned int h = strHash(elem->pKey, elem->nKey) % new_size;
+    unsigned int h = strHash(elem->pKey) % new_size;
     next_elem = elem->next;
     insertElement(pH, &new_ht[h], elem);
   }
   return 1;
 }
 
 /* This function (for internal use only) locates an element in an
-** hash table that matches the given key.  The hash for this key has
-** already been computed and is passed as the 4th parameter.
+** hash table that matches the given key.  The hash for this key is
+** also computed and returned in the *pH parameter.
 */
-static HashElem *findElementGivenHash(
+static HashElem *findElementWithHash(
   const Hash *pH,     /* The pH to be searched */
   const char *pKey,   /* The key we are searching for */
-  int nKey,           /* Bytes in key (not counting zero terminator) */
-  unsigned int h      /* The hash for this key. */
+  unsigned int *pHash /* Write the hash value here */
 ){
   HashElem *elem;                /* Used to loop thru the element list */
   int count;                     /* Number of elements left to test */
+  unsigned int h;                /* The computed hash */
 
   if( pH->ht ){
-    struct _ht *pEntry = &pH->ht[h];
+    struct _ht *pEntry;
+    h = strHash(pKey) % pH->htsize;
+    pEntry = &pH->ht[h];
     elem = pEntry->chain;
     count = pEntry->count;
   }else{
+    h = 0;
     elem = pH->first;
     count = pH->count;
   }
-  while( count-- && ALWAYS(elem) ){
-    if( elem->nKey==nKey && sqlite3StrNICmp(elem->pKey,pKey,nKey)==0 ){ 
+  *pHash = h;
+  while( count-- ){
+    assert( elem!=0 );
+    if( sqlite3StrICmp(elem->pKey,pKey)==0 ){ 
       return elem;
     }
     elem = elem->next;
   }
   return 0;
 }
 
 /* Remove a single entry from the hash table given a pointer to that
 ** element and a hash on the element's key.
 */
@@ skipping 14 matching lines @@
   if( pH->ht ){
     pEntry = &pH->ht[h];
     if( pEntry->chain==elem ){
       pEntry->chain = elem->next;
     }
     pEntry->count--;
     assert( pEntry->count>=0 );
   }
   sqlite3_free( elem );
   pH->count--;
-  if( pH->count<=0 ){
+  if( pH->count==0 ){
     assert( pH->first==0 );
     assert( pH->count==0 );
     sqlite3HashClear(pH);
   }
 }
 
 /* Attempt to locate an element of the hash table pH with a key
-** that matches pKey,nKey.  Return the data for this element if it is
+** that matches pKey.  Return the data for this element if it is
 ** found, or NULL if there is no match.
 */
-void *sqlite3HashFind(const Hash *pH, const char *pKey, int nKey){
+void *sqlite3HashFind(const Hash *pH, const char *pKey){
   HashElem *elem;    /* The element that matches key */
   unsigned int h;    /* A hash on key */
 
   assert( pH!=0 );
   assert( pKey!=0 );
-  assert( nKey>=0 );
-  if( pH->ht ){
-    h = strHash(pKey, nKey) % pH->htsize;
-  }else{
-    h = 0;
-  }
-  elem = findElementGivenHash(pH, pKey, nKey, h);
+  elem = findElementWithHash(pH, pKey, &h);
   return elem ? elem->data : 0;
 }
 
-/* Insert an element into the hash table pH.  The key is pKey,nKey
+/* Insert an element into the hash table pH.  The key is pKey
 ** and the data is "data".
 **
 ** If no element exists with a matching key, then a new
 ** element is created and NULL is returned.
 **
 ** If another element already exists with the same key, then the
 ** new data replaces the old data and the old data is returned.
 ** The key is not copied in this instance.  If a malloc fails, then
 ** the new data is returned and the hash table is unchanged.
 **
 ** If the "data" parameter to this function is NULL, then the
 ** element corresponding to "key" is removed from the hash table.
 */
-void *sqlite3HashInsert(Hash *pH, const char *pKey, int nKey, void *data){
+void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
   unsigned int h;       /* the hash of the key modulo hash table size */
   HashElem *elem;       /* Used to loop thru the element list */
   HashElem *new_elem;   /* New element added to the pH */
 
   assert( pH!=0 );
   assert( pKey!=0 );
-  assert( nKey>=0 );
-  if( pH->htsize ){
-    h = strHash(pKey, nKey) % pH->htsize;
-  }else{
-    h = 0;
-  }
-  elem = findElementGivenHash(pH,pKey,nKey,h);
+  elem = findElementWithHash(pH,pKey,&h);
   if( elem ){
     void *old_data = elem->data;
     if( data==0 ){
       removeElementGivenHash(pH,elem,h);
     }else{
       elem->data = data;
       elem->pKey = pKey;
-      assert(nKey==elem->nKey);
     }
     return old_data;
   }
   if( data==0 ) return 0;
   new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
   if( new_elem==0 ) return data;
   new_elem->pKey = pKey;
-  new_elem->nKey = nKey;
   new_elem->data = data;
   pH->count++;
   if( pH->count>=10 && pH->count > 2*pH->htsize ){
     if( rehash(pH, pH->count*2) ){
       assert( pH->htsize>0 );
-      h = strHash(pKey, nKey) % pH->htsize;
+      h = strHash(pKey) % pH->htsize;
     }
   }
-  if( pH->ht ){
-    insertElement(pH, &pH->ht[h], new_elem);
-  }else{
-    insertElement(pH, 0, new_elem);
-  }
+  insertElement(pH, pH->ht ? &pH->ht[h] : 0, new_elem);
   return 0;
 }