1.1 --- a/extensions/sqlite/sqlite-source/hash.c Fri Aug 03 07:56:31 2012 -0400
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,418 +0,0 @@
1.4 -/*
1.5 -** 2001 September 22
1.6 -**
1.7 -** The author disclaims copyright to this source code. In place of
1.8 -** a legal notice, here is a blessing:
1.9 -**
1.10 -** May you do good and not evil.
1.11 -** May you find forgiveness for yourself and forgive others.
1.12 -** May you share freely, never taking more than you give.
1.13 -**
1.14 -*************************************************************************
1.15 -** This is the implementation of generic hash-tables
1.16 -** used in SQLite.
1.17 -**
1.18 -** $Id$
1.19 -*/
1.20 -#include "sqliteInt.h"
1.21 -#include <assert.h>
1.22 -
1.23 -/* Turn bulk memory into a hash table object by initializing the
1.24 -** fields of the Hash structure.
1.25 -**
1.26 -** "pNew" is a pointer to the hash table that is to be initialized.
1.27 -** keyClass is one of the constants SQLITE_HASH_INT, SQLITE_HASH_POINTER,
1.28 -** SQLITE_HASH_BINARY, or SQLITE_HASH_STRING. The value of keyClass
1.29 -** determines what kind of key the hash table will use. "copyKey" is
1.30 -** true if the hash table should make its own private copy of keys and
1.31 -** false if it should just use the supplied pointer. CopyKey only makes
1.32 -** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
1.33 -** for other key classes.
1.34 -*/
1.35 -void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
1.36 - assert( pNew!=0 );
1.37 - assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
1.38 - pNew->keyClass = keyClass;
1.39 -#if 0
1.40 - if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
1.41 -#endif
1.42 - pNew->copyKey = copyKey;
1.43 - pNew->first = 0;
1.44 - pNew->count = 0;
1.45 - pNew->htsize = 0;
1.46 - pNew->ht = 0;
1.47 -}
1.48 -
1.49 -/* Remove all entries from a hash table. Reclaim all memory.
1.50 -** Call this routine to delete a hash table or to reset a hash table
1.51 -** to the empty state.
1.52 -*/
1.53 -void sqlite3HashClear(Hash *pH){
1.54 - HashElem *elem; /* For looping over all elements of the table */
1.55 -
1.56 - assert( pH!=0 );
1.57 - elem = pH->first;
1.58 - pH->first = 0;
1.59 - if( pH->ht ) sqlite3_free(pH->ht);
1.60 - pH->ht = 0;
1.61 - pH->htsize = 0;
1.62 - while( elem ){
1.63 - HashElem *next_elem = elem->next;
1.64 - if( pH->copyKey && elem->pKey ){
1.65 - sqlite3_free(elem->pKey);
1.66 - }
1.67 - sqlite3_free(elem);
1.68 - elem = next_elem;
1.69 - }
1.70 - pH->count = 0;
1.71 -}
1.72 -
1.73 -#if 0 /* NOT USED */
1.74 -/*
1.75 -** Hash and comparison functions when the mode is SQLITE_HASH_INT
1.76 -*/
1.77 -static int intHash(const void *pKey, int nKey){
1.78 - return nKey ^ (nKey<<8) ^ (nKey>>8);
1.79 -}
1.80 -static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.81 - return n2 - n1;
1.82 -}
1.83 -#endif
1.84 -
1.85 -#if 0 /* NOT USED */
1.86 -/*
1.87 -** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
1.88 -*/
1.89 -static int ptrHash(const void *pKey, int nKey){
1.90 - uptr x = Addr(pKey);
1.91 - return x ^ (x<<8) ^ (x>>8);
1.92 -}
1.93 -static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.94 - if( pKey1==pKey2 ) return 0;
1.95 - if( pKey1<pKey2 ) return -1;
1.96 - return 1;
1.97 -}
1.98 -#endif
1.99 -
1.100 -/*
1.101 -** Hash and comparison functions when the mode is SQLITE_HASH_STRING
1.102 -*/
1.103 -static int strHash(const void *pKey, int nKey){
1.104 - const char *z = (const char *)pKey;
1.105 - int h = 0;
1.106 - if( nKey<=0 ) nKey = strlen(z);
1.107 - while( nKey > 0 ){
1.108 - h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
1.109 - nKey--;
1.110 - }
1.111 - return h & 0x7fffffff;
1.112 -}
1.113 -static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.114 - if( n1!=n2 ) return 1;
1.115 - return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
1.116 -}
1.117 -
1.118 -/*
1.119 -** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
1.120 -*/
1.121 -static int binHash(const void *pKey, int nKey){
1.122 - int h = 0;
1.123 - const char *z = (const char *)pKey;
1.124 - while( nKey-- > 0 ){
1.125 - h = (h<<3) ^ h ^ *(z++);
1.126 - }
1.127 - return h & 0x7fffffff;
1.128 -}
1.129 -static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.130 - if( n1!=n2 ) return 1;
1.131 - return memcmp(pKey1,pKey2,n1);
1.132 -}
1.133 -
1.134 -/*
1.135 -** Return a pointer to the appropriate hash function given the key class.
1.136 -**
1.137 -** The C syntax in this function definition may be unfamilar to some
1.138 -** programmers, so we provide the following additional explanation:
1.139 -**
1.140 -** The name of the function is "hashFunction". The function takes a
1.141 -** single parameter "keyClass". The return value of hashFunction()
1.142 -** is a pointer to another function. Specifically, the return value
1.143 -** of hashFunction() is a pointer to a function that takes two parameters
1.144 -** with types "const void*" and "int" and returns an "int".
1.145 -*/
1.146 -static int (*hashFunction(int keyClass))(const void*,int){
1.147 -#if 0 /* HASH_INT and HASH_POINTER are never used */
1.148 - switch( keyClass ){
1.149 - case SQLITE_HASH_INT: return &intHash;
1.150 - case SQLITE_HASH_POINTER: return &ptrHash;
1.151 - case SQLITE_HASH_STRING: return &strHash;
1.152 - case SQLITE_HASH_BINARY: return &binHash;;
1.153 - default: break;
1.154 - }
1.155 - return 0;
1.156 -#else
1.157 - if( keyClass==SQLITE_HASH_STRING ){
1.158 - return &strHash;
1.159 - }else{
1.160 - assert( keyClass==SQLITE_HASH_BINARY );
1.161 - return &binHash;
1.162 - }
1.163 -#endif
1.164 -}
1.165 -
1.166 -/*
1.167 -** Return a pointer to the appropriate hash function given the key class.
1.168 -**
1.169 -** For help in interpreted the obscure C code in the function definition,
1.170 -** see the header comment on the previous function.
1.171 -*/
1.172 -static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
1.173 -#if 0 /* HASH_INT and HASH_POINTER are never used */
1.174 - switch( keyClass ){
1.175 - case SQLITE_HASH_INT: return &intCompare;
1.176 - case SQLITE_HASH_POINTER: return &ptrCompare;
1.177 - case SQLITE_HASH_STRING: return &strCompare;
1.178 - case SQLITE_HASH_BINARY: return &binCompare;
1.179 - default: break;
1.180 - }
1.181 - return 0;
1.182 -#else
1.183 - if( keyClass==SQLITE_HASH_STRING ){
1.184 - return &strCompare;
1.185 - }else{
1.186 - assert( keyClass==SQLITE_HASH_BINARY );
1.187 - return &binCompare;
1.188 - }
1.189 -#endif
1.190 -}
1.191 -
1.192 -/* Link an element into the hash table
1.193 -*/
1.194 -static void insertElement(
1.195 - Hash *pH, /* The complete hash table */
1.196 - struct _ht *pEntry, /* The entry into which pNew is inserted */
1.197 - HashElem *pNew /* The element to be inserted */
1.198 -){
1.199 - HashElem *pHead; /* First element already in pEntry */
1.200 - pHead = pEntry->chain;
1.201 - if( pHead ){
1.202 - pNew->next = pHead;
1.203 - pNew->prev = pHead->prev;
1.204 - if( pHead->prev ){ pHead->prev->next = pNew; }
1.205 - else { pH->first = pNew; }
1.206 - pHead->prev = pNew;
1.207 - }else{
1.208 - pNew->next = pH->first;
1.209 - if( pH->first ){ pH->first->prev = pNew; }
1.210 - pNew->prev = 0;
1.211 - pH->first = pNew;
1.212 - }
1.213 - pEntry->count++;
1.214 - pEntry->chain = pNew;
1.215 -}
1.216 -
1.217 -
1.218 -/* Resize the hash table so that it cantains "new_size" buckets.
1.219 -** "new_size" must be a power of 2. The hash table might fail
1.220 -** to resize if sqlite3_malloc() fails.
1.221 -*/
1.222 -static void rehash(Hash *pH, int new_size){
1.223 - struct _ht *new_ht; /* The new hash table */
1.224 - HashElem *elem, *next_elem; /* For looping over existing elements */
1.225 - int (*xHash)(const void*,int); /* The hash function */
1.226 -
1.227 - assert( (new_size & (new_size-1))==0 );
1.228 -
1.229 - /* There is a call to sqlite3_malloc() inside rehash(). If there is
1.230 - ** already an allocation at pH->ht, then if this malloc() fails it
1.231 - ** is benign (since failing to resize a hash table is a performance
1.232 - ** hit only, not a fatal error).
1.233 - */
1.234 - sqlite3MallocBenignFailure(pH->htsize>0);
1.235 -
1.236 - new_ht = (struct _ht *)sqlite3MallocZero( new_size*sizeof(struct _ht) );
1.237 - if( new_ht==0 ) return;
1.238 - if( pH->ht ) sqlite3_free(pH->ht);
1.239 - pH->ht = new_ht;
1.240 - pH->htsize = new_size;
1.241 - xHash = hashFunction(pH->keyClass);
1.242 - for(elem=pH->first, pH->first=0; elem; elem = next_elem){
1.243 - int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
1.244 - next_elem = elem->next;
1.245 - insertElement(pH, &new_ht[h], elem);
1.246 - }
1.247 -}
1.248 -
1.249 -/* This function (for internal use only) locates an element in an
1.250 -** hash table that matches the given key. The hash for this key has
1.251 -** already been computed and is passed as the 4th parameter.
1.252 -*/
1.253 -static HashElem *findElementGivenHash(
1.254 - const Hash *pH, /* The pH to be searched */
1.255 - const void *pKey, /* The key we are searching for */
1.256 - int nKey,
1.257 - int h /* The hash for this key. */
1.258 -){
1.259 - HashElem *elem; /* Used to loop thru the element list */
1.260 - int count; /* Number of elements left to test */
1.261 - int (*xCompare)(const void*,int,const void*,int); /* comparison function */
1.262 -
1.263 - if( pH->ht ){
1.264 - struct _ht *pEntry = &pH->ht[h];
1.265 - elem = pEntry->chain;
1.266 - count = pEntry->count;
1.267 - xCompare = compareFunction(pH->keyClass);
1.268 - while( count-- && elem ){
1.269 - if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
1.270 - return elem;
1.271 - }
1.272 - elem = elem->next;
1.273 - }
1.274 - }
1.275 - return 0;
1.276 -}
1.277 -
1.278 -/* Remove a single entry from the hash table given a pointer to that
1.279 -** element and a hash on the element's key.
1.280 -*/
1.281 -static void removeElementGivenHash(
1.282 - Hash *pH, /* The pH containing "elem" */
1.283 - HashElem* elem, /* The element to be removed from the pH */
1.284 - int h /* Hash value for the element */
1.285 -){
1.286 - struct _ht *pEntry;
1.287 - if( elem->prev ){
1.288 - elem->prev->next = elem->next;
1.289 - }else{
1.290 - pH->first = elem->next;
1.291 - }
1.292 - if( elem->next ){
1.293 - elem->next->prev = elem->prev;
1.294 - }
1.295 - pEntry = &pH->ht[h];
1.296 - if( pEntry->chain==elem ){
1.297 - pEntry->chain = elem->next;
1.298 - }
1.299 - pEntry->count--;
1.300 - if( pEntry->count<=0 ){
1.301 - pEntry->chain = 0;
1.302 - }
1.303 - if( pH->copyKey ){
1.304 - sqlite3_free(elem->pKey);
1.305 - }
1.306 - sqlite3_free( elem );
1.307 - pH->count--;
1.308 - if( pH->count<=0 ){
1.309 - assert( pH->first==0 );
1.310 - assert( pH->count==0 );
1.311 - sqlite3HashClear(pH);
1.312 - }
1.313 -}
1.314 -
1.315 -/* Attempt to locate an element of the hash table pH with a key
1.316 -** that matches pKey,nKey. Return a pointer to the corresponding
1.317 -** HashElem structure for this element if it is found, or NULL
1.318 -** otherwise.
1.319 -*/
1.320 -HashElem *sqlite3HashFindElem(const Hash *pH, const void *pKey, int nKey){
1.321 - int h; /* A hash on key */
1.322 - HashElem *elem; /* The element that matches key */
1.323 - int (*xHash)(const void*,int); /* The hash function */
1.324 -
1.325 - if( pH==0 || pH->ht==0 ) return 0;
1.326 - xHash = hashFunction(pH->keyClass);
1.327 - assert( xHash!=0 );
1.328 - h = (*xHash)(pKey,nKey);
1.329 - assert( (pH->htsize & (pH->htsize-1))==0 );
1.330 - elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
1.331 - return elem;
1.332 -}
1.333 -
1.334 -/* Attempt to locate an element of the hash table pH with a key
1.335 -** that matches pKey,nKey. Return the data for this element if it is
1.336 -** found, or NULL if there is no match.
1.337 -*/
1.338 -void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
1.339 - HashElem *elem; /* The element that matches key */
1.340 - elem = sqlite3HashFindElem(pH, pKey, nKey);
1.341 - return elem ? elem->data : 0;
1.342 -}
1.343 -
1.344 -/* Insert an element into the hash table pH. The key is pKey,nKey
1.345 -** and the data is "data".
1.346 -**
1.347 -** If no element exists with a matching key, then a new
1.348 -** element is created. A copy of the key is made if the copyKey
1.349 -** flag is set. NULL is returned.
1.350 -**
1.351 -** If another element already exists with the same key, then the
1.352 -** new data replaces the old data and the old data is returned.
1.353 -** The key is not copied in this instance. If a malloc fails, then
1.354 -** the new data is returned and the hash table is unchanged.
1.355 -**
1.356 -** If the "data" parameter to this function is NULL, then the
1.357 -** element corresponding to "key" is removed from the hash table.
1.358 -*/
1.359 -void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
1.360 - int hraw; /* Raw hash value of the key */
1.361 - int h; /* the hash of the key modulo hash table size */
1.362 - HashElem *elem; /* Used to loop thru the element list */
1.363 - HashElem *new_elem; /* New element added to the pH */
1.364 - int (*xHash)(const void*,int); /* The hash function */
1.365 -
1.366 - assert( pH!=0 );
1.367 - xHash = hashFunction(pH->keyClass);
1.368 - assert( xHash!=0 );
1.369 - hraw = (*xHash)(pKey, nKey);
1.370 - assert( (pH->htsize & (pH->htsize-1))==0 );
1.371 - h = hraw & (pH->htsize-1);
1.372 - elem = findElementGivenHash(pH,pKey,nKey,h);
1.373 - if( elem ){
1.374 - void *old_data = elem->data;
1.375 - if( data==0 ){
1.376 - removeElementGivenHash(pH,elem,h);
1.377 - }else{
1.378 - elem->data = data;
1.379 - if( !pH->copyKey ){
1.380 - elem->pKey = (void *)pKey;
1.381 - }
1.382 - assert(nKey==elem->nKey);
1.383 - }
1.384 - return old_data;
1.385 - }
1.386 - if( data==0 ) return 0;
1.387 - new_elem = (HashElem*)sqlite3_malloc( sizeof(HashElem) );
1.388 - if( new_elem==0 ) return data;
1.389 - if( pH->copyKey && pKey!=0 ){
1.390 - new_elem->pKey = sqlite3_malloc( nKey );
1.391 - if( new_elem->pKey==0 ){
1.392 - sqlite3_free(new_elem);
1.393 - return data;
1.394 - }
1.395 - memcpy((void*)new_elem->pKey, pKey, nKey);
1.396 - }else{
1.397 - new_elem->pKey = (void*)pKey;
1.398 - }
1.399 - new_elem->nKey = nKey;
1.400 - pH->count++;
1.401 - if( pH->htsize==0 ){
1.402 - rehash(pH,8);
1.403 - if( pH->htsize==0 ){
1.404 - pH->count = 0;
1.405 - if( pH->copyKey ){
1.406 - sqlite3_free(new_elem->pKey);
1.407 - }
1.408 - sqlite3_free(new_elem);
1.409 - return data;
1.410 - }
1.411 - }
1.412 - if( pH->count > pH->htsize ){
1.413 - rehash(pH,pH->htsize*2);
1.414 - }
1.415 - assert( pH->htsize>0 );
1.416 - assert( (pH->htsize & (pH->htsize-1))==0 );
1.417 - h = hraw & (pH->htsize-1);
1.418 - insertElement(pH, &pH->ht[h], new_elem);
1.419 - new_elem->data = data;
1.420 - return 0;
1.421 -}
