Improvements to the hash table used to store symbols in the schema, so that

it works better (requires fewer calls to sqlite3StrICmp()) for large schemas,
and uses less code space.

FossilOrigin-Name: 0318b68c845c84eded757c67f820e1783551574ac9e5670be640c4bfe22a934b

2 files changed, 24 insertions, 20 deletions

diff --git a/src/hash.c b/src/hash.c
index 8ec043f11..c822cb5f1 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -55,11 +55,19 @@ void sqlite3HashClear(Hash *pH){
 static unsigned int strHash(const char *z){
   unsigned int h = 0;
   unsigned char c;
-  while( (c = (unsigned char)*z++)!=0 ){     /*OPTIMIZATION-IF-TRUE*/
+  while( z[0] ){     /*OPTIMIZATION-IF-TRUE*/
     /* Knuth multiplicative hashing.  (Sorting & Searching, p. 510).
     ** 0x9e3779b1 is 2654435761 which is the closest prime number to
-    ** (2**32)*golden_ratio, where golden_ratio = (sqrt(5) - 1)/2. */
-    h += sqlite3UpperToLower[c];
+    ** (2**32)*golden_ratio, where golden_ratio = (sqrt(5) - 1)/2.
+    **
+    ** Only bits 0xdf for ASCII and bits 0xbf for EBCDIC each octet are
+    ** hashed since the omitted bits determine the upper/lower case difference.
+    */
+#ifdef SQLITE_EBCDIC
+    h += 0xbf & (unsigned char)*(z++);
+#else
+    h += 0xdf & (unsigned char)*(z++);
+#endif
     h *= 0x9e3779b1;
   }
   return h;
@@ -132,9 +140,8 @@ static int rehash(Hash *pH, unsigned int new_size){
   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) % new_size;
     next_elem = elem->next;
-    insertElement(pH, &new_ht[h], elem);
+    insertElement(pH, &new_ht[elem->h % new_size], elem);
   }
   return 1;
 }
@@ -154,21 +161,20 @@ static HashElem *findElementWithHash(
   unsigned int h;                /* The computed hash */
   static HashElem nullElement = { 0, 0, 0, 0 };
 
+  h = strHash(pKey);
   if( pH->ht ){   /*OPTIMIZATION-IF-TRUE*/
     struct _ht *pEntry;
-    h = strHash(pKey) % pH->htsize;
-    pEntry = &pH->ht[h];
+    pEntry = &pH->ht[h % pH->htsize];
     elem = pEntry->chain;
     count = pEntry->count;
   }else{
-    h = 0;
     elem = pH->first;
     count = pH->count;
   }
   if( pHash ) *pHash = h;
   while( count ){
     assert( elem!=0 );
-    if( sqlite3StrICmp(elem->pKey,pKey)==0 ){ 
+    if( h==elem->h && sqlite3StrICmp(elem->pKey,pKey)==0 ){ 
       return elem;
     }
     elem = elem->next;
@@ -180,10 +186,9 @@ static HashElem *findElementWithHash(
 /* Remove a single entry from the hash table given a pointer to that
 ** element and a hash on the element's key.
 */
-static void removeElementGivenHash(
+static void removeElement(
   Hash *pH,         /* The pH containing "elem" */
-  HashElem* elem,   /* The element to be removed from the pH */
-  unsigned int h    /* Hash value for the element */
+  HashElem *elem    /* The element to be removed from the pH */
 ){
   struct _ht *pEntry;
   if( elem->prev ){
@@ -195,7 +200,7 @@ static void removeElementGivenHash(
     elem->next->prev = elem->prev;
   }
   if( pH->ht ){
-    pEntry = &pH->ht[h];
+    pEntry = &pH->ht[elem->h % pH->htsize];
     if( pEntry->chain==elem ){
       pEntry->chain = elem->next;
     }
@@ -246,7 +251,7 @@ void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
   if( elem->data ){
     void *old_data = elem->data;
     if( data==0 ){
-      removeElementGivenHash(pH,elem,h);
+      removeElement(pH,elem);
     }else{
       elem->data = data;
       elem->pKey = pKey;
@@ -257,14 +262,12 @@ void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
   new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
   if( new_elem==0 ) return data;
   new_elem->pKey = pKey;
+  new_elem->h = h;
   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) % pH->htsize;
-    }
+  if( pH->count>=5 && pH->count > 2*pH->htsize ){
+    rehash(pH, pH->count*3);
   }
-  insertElement(pH, pH->ht ? &pH->ht[h] : 0, new_elem);
+  insertElement(pH, pH->ht ? &pH->ht[new_elem->h % pH->htsize] : 0, new_elem);
   return 0;
 }
diff --git a/src/hash.h b/src/hash.h
index 3f491e45c..cff65d6e5 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -60,6 +60,7 @@ struct HashElem {
   HashElem *next, *prev;       /* Next and previous elements in the table */
   void *data;                  /* Data associated with this element */
   const char *pKey;            /* Key associated with this element */
+  unsigned int h;              /* hash for pKey */
 };
 
 /*