From a35d8518925f61827e7936e1b4f2b49b163eeaaf Mon Sep 17 00:00:00 2001
From: drh <drh@noemail.net>
Date: Wed, 5 Jul 2017 23:33:33 +0000
Subject: [PATCH] Make the hash table implementation a little smaller and
 faster.

FossilOrigin-Name: f762f1effe1ce893d6b67815ad8b585bae2c1621d9199dac9c85d39dad16e774
---
 manifest      | 14 +++++++-------
 manifest.uuid |  2 +-
 src/hash.c    | 18 ++++++++----------
 3 files changed, 16 insertions(+), 18 deletions(-)

diff --git a/manifest b/manifest
index 2015d53bd9..9df8c640f4 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Have\sfts3\svirtual\stable\scursors\sfree\sinternal\sresources\swhen\sthey\sreach\sEOF,\ninstead\sof\swaiting\suntil\sthe\sxClose\smethod\sis\scalled.
-D 2017-07-05T18:48:07.731
+C Make\sthe\shash\stable\simplementation\sa\slittle\ssmaller\sand\sfaster.
+D 2017-07-05T23:33:33.766
 F Makefile.in 081e48dfe7f995d57ce1a88ddf4d2917b4349158648a6cd45b42beae30de3a12
 F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434
 F Makefile.msc 4ebb1d257cac7fb1bcb4ba59278416d410ff1c4bf59447a9c37a415f3516056a
@@ -406,7 +406,7 @@ F src/fault.c 460f3e55994363812d9d60844b2a6de88826e007
 F src/fkey.c 5ff2c895fe087756d8085dc1a9bc229b5670e2a65c3929dd87c71e43649af333
 F src/func.c 9d52522cc8ae7f5cdadfe14594262f1618bc1f86083c4cd6da861b4cf5af6174
 F src/global.c 8a6ab6b4d91effb96ffa81b39f0d70c862abca157f8aaa194600a4a8b7923344
-F src/hash.c 63d0ee752a3b92d4695b2b1f5259c4621b2cfebd
+F src/hash.c a12580e143f10301ed5166ea4964ae2853d3905a511d4e0c44497245c7ce1f7a
 F src/hash.h ab34c5c54a9e9de2e790b24349ba5aab3dbb4fd4
 F src/hwtime.h 747c1bbe9df21a92e9c50f3bbec1de841dc5e5da
 F src/in-operator.md 10cd8f4bcd225a32518407c2fb2484089112fd71
@@ -1628,7 +1628,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93
 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
 F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
 F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 2bce64c8864b616f9ab0063f64d0ceb2f83e53e110970c6b3b11003cba5c8804
-R 6015f51321fa56ca0aea7f128543d185
-U dan
-Z ff4e48dc3c6989947963449987db258e
+P b6b14ab6c8f9758a64e5fd29203f8fa610b5c4ef917de9be51ae55e072fad4ed
+R a69ecc17bd9958907f3d555d6d660116
+U drh
+Z 52f15ece476189b3984a89ea468128d8
diff --git a/manifest.uuid b/manifest.uuid
index eee94eb382..497a9658e6 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-b6b14ab6c8f9758a64e5fd29203f8fa610b5c4ef917de9be51ae55e072fad4ed
\ No newline at end of file
+f762f1effe1ce893d6b67815ad8b585bae2c1621d9199dac9c85d39dad16e774
\ No newline at end of file
diff --git a/src/hash.c b/src/hash.c
index 62b695a1bb..79bb85ac01 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -140,8 +140,9 @@ static int rehash(Hash *pH, unsigned int new_size){
 }
 
 /* This function (for internal use only) locates an element in an
-** hash table that matches the given key.  The hash for this key is
-** also computed and returned in the *pH parameter.
+** hash table that matches the given key.  If no element is found,
+** a pointer to a static null element with HashElem.data==0 is returned.
+** If pH is not NULL, then the hash for this key is written to *pH.
 */
 static HashElem *findElementWithHash(
   const Hash *pH,     /* The pH to be searched */
@@ -151,6 +152,7 @@ static HashElem *findElementWithHash(
   HashElem *elem;                /* Used to loop thru the element list */
   int count;                     /* Number of elements left to test */
   unsigned int h;                /* The computed hash */
+  static HashElem nullElement = { 0, 0, 0, 0 };
 
   if( pH->ht ){   /*OPTIMIZATION-IF-TRUE*/
     struct _ht *pEntry;
@@ -163,7 +165,7 @@ static HashElem *findElementWithHash(
     elem = pH->first;
     count = pH->count;
   }
-  *pHash = h;
+  if( pHash ) *pHash = h;
   while( count-- ){
     assert( elem!=0 );
     if( sqlite3StrICmp(elem->pKey,pKey)==0 ){ 
@@ -171,7 +173,7 @@ static HashElem *findElementWithHash(
     }
     elem = elem->next;
   }
-  return 0;
+  return &nullElement;
 }
 
 /* Remove a single entry from the hash table given a pointer to that
@@ -213,13 +215,9 @@ static void removeElementGivenHash(
 ** found, or NULL if there is no match.
 */
 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 );
-  elem = findElementWithHash(pH, pKey, &h);
-  return elem ? elem->data : 0;
+  return findElementWithHash(pH, pKey, 0)->data;
 }
 
 /* Insert an element into the hash table pH.  The key is pKey
@@ -244,7 +242,7 @@ void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){
   assert( pH!=0 );
   assert( pKey!=0 );
   elem = findElementWithHash(pH,pKey,&h);
-  if( elem ){
+  if( elem->data ){
     void *old_data = elem->data;
     if( data==0 ){
       removeElementGivenHash(pH,elem,h);
-- 
2.47.2