1 files changed, 93 insertions, 237 deletions

diff --git a/third_party/sqlite/src/hash.c b/third_party/sqlite/src/hash.c
index df73698..9f1587a 100644
--- a/third_party/sqlite/src/hash.c
+++ b/third_party/sqlite/src/hash.c
@@ -12,7 +12,7 @@
 ** This is the implementation of generic hash-tables
 ** used in SQLite.
 **
-** $Id: hash.c,v 1.30 2008/06/20 14:59:51 danielk1977 Exp $
+** $Id: hash.c,v 1.38 2009/05/09 23:29:12 drh Exp $
 */
 #include "sqliteInt.h"
 #include <assert.h>
@@ -21,22 +21,9 @@
 ** fields of the Hash structure.
 **
 ** "pNew" is a pointer to the hash table that is to be initialized.
-** keyClass is one of the constants SQLITE_HASH_INT, SQLITE_HASH_POINTER,
-** SQLITE_HASH_BINARY, or SQLITE_HASH_STRING.  The value of keyClass 
-** determines what kind of key the hash table will use.  "copyKey" is
-** true if the hash table should make its own private copy of keys and
-** false if it should just use the supplied pointer.  CopyKey only makes
-** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
-** for other key classes.
 */
-void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
+void sqlite3HashInit(Hash *pNew){
   assert( pNew!=0 );
-  assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
-  pNew->keyClass = keyClass;
-#if 0
-  if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
-#endif
-  pNew->copyKey = copyKey;
   pNew->first = 0;
   pNew->count = 0;
   pNew->htsize = 0;
@@ -58,135 +45,28 @@ void sqlite3HashClear(Hash *pH){
   pH->htsize = 0;
   while( elem ){
     HashElem *next_elem = elem->next;
-    if( pH->copyKey && elem->pKey ){
-      sqlite3_free(elem->pKey);
-    }
     sqlite3_free(elem);
     elem = next_elem;
   }
   pH->count = 0;
 }
 
-#if 0 /* NOT USED */
-/*
-** Hash and comparison functions when the mode is SQLITE_HASH_INT
-*/
-static int intHash(const void *pKey, int nKey){
-  return nKey ^ (nKey<<8) ^ (nKey>>8);
-}
-static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
-  return n2 - n1;
-}
-#endif
-
-#if 0 /* NOT USED */
 /*
-** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
+** The hashing function.
 */
-static int ptrHash(const void *pKey, int nKey){
-  uptr x = Addr(pKey);
-  return x ^ (x<<8) ^ (x>>8);
-}
-static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
-  if( pKey1==pKey2 ) return 0;
-  if( pKey1<pKey2 ) return -1;
-  return 1;
-}
-#endif
-
-/*
-** Hash and comparison functions when the mode is SQLITE_HASH_STRING
-*/
-static int strHash(const void *pKey, int nKey){
-  const char *z = (const char *)pKey;
+static unsigned int strHash(const char *z, int nKey){
   int h = 0;
-  if( nKey<=0 ) nKey = strlen(z);
+  assert( nKey>=0 );
   while( nKey > 0  ){
     h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
     nKey--;
   }
-  return h & 0x7fffffff;
-}
-static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
-  if( n1!=n2 ) return 1;
-  return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
+  return h;
 }
 
-/*
-** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
-*/
-static int binHash(const void *pKey, int nKey){
-  int h = 0;
-  const char *z = (const char *)pKey;
-  while( nKey-- > 0 ){
-    h = (h<<3) ^ h ^ *(z++);
-  }
-  return h & 0x7fffffff;
-}
-static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
-  if( n1!=n2 ) return 1;
-  return memcmp(pKey1,pKey2,n1);
-}
-
-/*
-** Return a pointer to the appropriate hash function given the key class.
-**
-** The C syntax in this function definition may be unfamilar to some 
-** programmers, so we provide the following additional explanation:
-**
-** The name of the function is "hashFunction".  The function takes a
-** single parameter "keyClass".  The return value of hashFunction()
-** is a pointer to another function.  Specifically, the return value
-** of hashFunction() is a pointer to a function that takes two parameters
-** with types "const void*" and "int" and returns an "int".
-*/
-static int (*hashFunction(int keyClass))(const void*,int){
-#if 0  /* HASH_INT and HASH_POINTER are never used */
-  switch( keyClass ){
-    case SQLITE_HASH_INT:     return &intHash;
-    case SQLITE_HASH_POINTER: return &ptrHash;
-    case SQLITE_HASH_STRING:  return &strHash;
-    case SQLITE_HASH_BINARY:  return &binHash;;
-    default: break;
-  }
-  return 0;
-#else
-  if( keyClass==SQLITE_HASH_STRING ){
-    return &strHash;
-  }else{
-    assert( keyClass==SQLITE_HASH_BINARY );
-    return &binHash;
-  }
-#endif
-}
 
-/*
-** Return a pointer to the appropriate hash function given the key class.
-**
-** For help in interpreted the obscure C code in the function definition,
-** see the header comment on the previous function.
-*/
-static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
-#if 0 /* HASH_INT and HASH_POINTER are never used */
-  switch( keyClass ){
-    case SQLITE_HASH_INT:     return &intCompare;
-    case SQLITE_HASH_POINTER: return &ptrCompare;
-    case SQLITE_HASH_STRING:  return &strCompare;
-    case SQLITE_HASH_BINARY:  return &binCompare;
-    default: break;
-  }
-  return 0;
-#else
-  if( keyClass==SQLITE_HASH_STRING ){
-    return &strCompare;
-  }else{
-    assert( keyClass==SQLITE_HASH_BINARY );
-    return &binCompare;
-  }
-#endif
-}
-
-/* Link an element into the hash table
+/* 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 */
@@ -194,7 +74,13 @@ static void insertElement(
   HashElem *pNew         /* The element to be inserted */
 ){
   HashElem *pHead;       /* First element already in pEntry */
-  pHead = pEntry->chain;
+  if( pEntry ){
+    pHead = pEntry->count ? pEntry->chain : 0;
+    pEntry->count++;
+    pEntry->chain = pNew;
+  }else{
+    pHead = 0;
+  }
   if( pHead ){
     pNew->next = pHead;
     pNew->prev = pHead->prev;
@@ -207,46 +93,45 @@ static void insertElement(
     pNew->prev = 0;
     pH->first = pNew;
   }
-  pEntry->count++;
-  pEntry->chain = pNew;
 }
 
 
 /* Resize the hash table so that it cantains "new_size" buckets.
-** "new_size" must be a power of 2.  The hash table might fail 
-** to resize if sqlite3_malloc() fails.
+**
+** The hash table might fail to resize if sqlite3_malloc() fails or
+** if the new size is the same as the prior size.
+** Return TRUE if the resize occurs and false if not.
 */
-static void rehash(Hash *pH, int new_size){
+static int rehash(Hash *pH, unsigned int new_size){
   struct _ht *new_ht;            /* The new hash table */
   HashElem *elem, *next_elem;    /* For looping over existing elements */
-  int (*xHash)(const void*,int); /* The hash function */
 
-#ifdef SQLITE_MALLOC_SOFT_LIMIT
+#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;
+  if( new_size==pH->htsize ) return 0;
 #endif
 
-  /* There is a call to sqlite3_malloc() inside rehash(). If there is
-  ** already an allocation at pH->ht, then if this malloc() fails it
-  ** is benign (since failing to resize a hash table is a performance
-  ** hit only, not a fatal error).
+  /* 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.
   */
-  if( pH->htsize>0 ) sqlite3BeginBenignMalloc();
-  new_ht = (struct _ht *)sqlite3MallocZero( new_size*sizeof(struct _ht) );
-  if( pH->htsize>0 ) sqlite3EndBenignMalloc();
+  sqlite3BeginBenignMalloc();
+  new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) );
+  sqlite3EndBenignMalloc();
 
-  if( new_ht==0 ) return;
+  if( new_ht==0 ) return 0;
   sqlite3_free(pH->ht);
   pH->ht = new_ht;
-  pH->htsize = new_size;
-  xHash = hashFunction(pH->keyClass);
+  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){
-    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
+    unsigned int h = strHash(elem->pKey, elem->nKey) % 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
@@ -255,25 +140,26 @@ static void rehash(Hash *pH, int new_size){
 */
 static HashElem *findElementGivenHash(
   const Hash *pH,     /* The pH to be searched */
-  const void *pKey,   /* The key we are searching for */
-  int nKey,
-  int h               /* The hash for this key. */
+  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. */
 ){
   HashElem *elem;                /* Used to loop thru the element list */
   int count;                     /* Number of elements left to test */
-  int (*xCompare)(const void*,int,const void*,int);  /* comparison function */
 
   if( pH->ht ){
     struct _ht *pEntry = &pH->ht[h];
     elem = pEntry->chain;
     count = pEntry->count;
-    xCompare = compareFunction(pH->keyClass);
-    while( count-- && elem ){
-      if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
-        return elem;
-      }
-      elem = elem->next;
+  }else{
+    elem = pH->first;
+    count = pH->count;
+  }
+  while( count-- && ALWAYS(elem) ){
+    if( elem->nKey==nKey && sqlite3StrNICmp(elem->pKey,pKey,nKey)==0 ){ 
+      return elem;
     }
+    elem = elem->next;
   }
   return 0;
 }
@@ -284,7 +170,7 @@ static HashElem *findElementGivenHash(
 static void removeElementGivenHash(
   Hash *pH,         /* The pH containing "elem" */
   HashElem* elem,   /* The element to be removed from the pH */
-  int h             /* Hash value for the element */
+  unsigned int h    /* Hash value for the element */
 ){
   struct _ht *pEntry;
   if( elem->prev ){
@@ -295,16 +181,13 @@ static void removeElementGivenHash(
   if( elem->next ){
     elem->next->prev = elem->prev;
   }
-  pEntry = &pH->ht[h];
-  if( pEntry->chain==elem ){
-    pEntry->chain = elem->next;
-  }
-  pEntry->count--;
-  if( pEntry->count<=0 ){
-    pEntry->chain = 0;
-  }
-  if( pH->copyKey ){
-    sqlite3_free(elem->pKey);
+  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--;
@@ -316,30 +199,22 @@ static void removeElementGivenHash(
 }
 
 /* Attempt to locate an element of the hash table pH with a key
-** that matches pKey,nKey.  Return a pointer to the corresponding 
-** HashElem structure for this element if it is found, or NULL
-** otherwise.
-*/
-HashElem *sqlite3HashFindElem(const Hash *pH, const void *pKey, int nKey){
-  int h;             /* A hash on key */
-  HashElem *elem;    /* The element that matches key */
-  int (*xHash)(const void*,int);  /* The hash function */
-
-  if( pH==0 || pH->ht==0 ) return 0;
-  xHash = hashFunction(pH->keyClass);
-  assert( xHash!=0 );
-  h = (*xHash)(pKey,nKey);
-  elem = findElementGivenHash(pH,pKey,nKey, h % pH->htsize);
-  return elem;
-}
-
-/* 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
 ** found, or NULL if there is no match.
 */
-void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
+void *sqlite3HashFind(const Hash *pH, const char *pKey, int nKey){
   HashElem *elem;    /* The element that matches key */
-  elem = sqlite3HashFindElem(pH, pKey, nKey);
+  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);
   return elem ? elem->data : 0;
 }
 
@@ -347,8 +222,7 @@ void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
 ** and the data is "data".
 **
 ** If no element exists with a matching key, then a new
-** element is created.  A copy of the key is made if the copyKey
-** flag is set.  NULL is returned.
+** 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.
@@ -358,66 +232,48 @@ void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
 ** 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 void *pKey, int nKey, void *data){
-  int hraw;             /* Raw hash value of the key */
-  int h;                /* the hash of the key modulo hash table size */
+void *sqlite3HashInsert(Hash *pH, const char *pKey, int nKey, 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 */
-  int (*xHash)(const void*,int);  /* The hash function */
 
   assert( pH!=0 );
-  xHash = hashFunction(pH->keyClass);
-  assert( xHash!=0 );
-  hraw = (*xHash)(pKey, nKey);
+  assert( pKey!=0 );
+  assert( nKey>=0 );
   if( pH->htsize ){
-    h = hraw % pH->htsize;
-    elem = findElementGivenHash(pH,pKey,nKey,h);
-    if( elem ){
-      void *old_data = elem->data;
-      if( data==0 ){
-        removeElementGivenHash(pH,elem,h);
-      }else{
-        elem->data = data;
-        if( !pH->copyKey ){
-          elem->pKey = (void *)pKey;
-        }
-        assert(nKey==elem->nKey);
-      }
-      return old_data;
+    h = strHash(pKey, nKey) % pH->htsize;
+  }else{
+    h = 0;
+  }
+  elem = findElementGivenHash(pH,pKey,nKey,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;
-  if( pH->copyKey && pKey!=0 ){
-    new_elem->pKey = sqlite3Malloc( nKey );
-    if( new_elem->pKey==0 ){
-      sqlite3_free(new_elem);
-      return data;
-    }
-    memcpy((void*)new_elem->pKey, pKey, nKey);
-  }else{
-    new_elem->pKey = (void*)pKey;
-  }
+  new_elem->pKey = pKey;
   new_elem->nKey = nKey;
+  new_elem->data = data;
   pH->count++;
-  if( pH->htsize==0 ){
-    rehash(pH, 128/sizeof(pH->ht[0]));
-    if( pH->htsize==0 ){
-      pH->count = 0;
-      if( pH->copyKey ){
-        sqlite3_free(new_elem->pKey);
-      }
-      sqlite3_free(new_elem);
-      return data;
+  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;
     }
   }
-  if( pH->count > pH->htsize ){
-    rehash(pH,pH->htsize*2);
+  if( pH->ht ){
+    insertElement(pH, &pH->ht[h], new_elem);
+  }else{
+    insertElement(pH, 0, new_elem);
   }
-  assert( pH->htsize>0 );
-  h = hraw % pH->htsize;
-  insertElement(pH, &pH->ht[h], new_elem);
-  new_elem->data = data;
   return 0;
 }