1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/extensions/sqlite/sqlite-source/hash.c Sun Jul 29 01:15:31 2007 +0000
1.3 @@ -0,0 +1,397 @@
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 + pNew->xMalloc = sqlite3MallocX;
1.48 + pNew->xFree = sqlite3FreeX;
1.49 +}
1.50 +
1.51 +/* Remove all entries from a hash table. Reclaim all memory.
1.52 +** Call this routine to delete a hash table or to reset a hash table
1.53 +** to the empty state.
1.54 +*/
1.55 +void sqlite3HashClear(Hash *pH){
1.56 + HashElem *elem; /* For looping over all elements of the table */
1.57 +
1.58 + assert( pH!=0 );
1.59 + elem = pH->first;
1.60 + pH->first = 0;
1.61 + if( pH->ht ) pH->xFree(pH->ht);
1.62 + pH->ht = 0;
1.63 + pH->htsize = 0;
1.64 + while( elem ){
1.65 + HashElem *next_elem = elem->next;
1.66 + if( pH->copyKey && elem->pKey ){
1.67 + pH->xFree(elem->pKey);
1.68 + }
1.69 + pH->xFree(elem);
1.70 + elem = next_elem;
1.71 + }
1.72 + pH->count = 0;
1.73 +}
1.74 +
1.75 +#if 0 /* NOT USED */
1.76 +/*
1.77 +** Hash and comparison functions when the mode is SQLITE_HASH_INT
1.78 +*/
1.79 +static int intHash(const void *pKey, int nKey){
1.80 + return nKey ^ (nKey<<8) ^ (nKey>>8);
1.81 +}
1.82 +static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.83 + return n2 - n1;
1.84 +}
1.85 +#endif
1.86 +
1.87 +#if 0 /* NOT USED */
1.88 +/*
1.89 +** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
1.90 +*/
1.91 +static int ptrHash(const void *pKey, int nKey){
1.92 + uptr x = Addr(pKey);
1.93 + return x ^ (x<<8) ^ (x>>8);
1.94 +}
1.95 +static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.96 + if( pKey1==pKey2 ) return 0;
1.97 + if( pKey1<pKey2 ) return -1;
1.98 + return 1;
1.99 +}
1.100 +#endif
1.101 +
1.102 +/*
1.103 +** Hash and comparison functions when the mode is SQLITE_HASH_STRING
1.104 +*/
1.105 +static int strHash(const void *pKey, int nKey){
1.106 + const char *z = (const char *)pKey;
1.107 + int h = 0;
1.108 + if( nKey<=0 ) nKey = strlen(z);
1.109 + while( nKey > 0 ){
1.110 + h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
1.111 + nKey--;
1.112 + }
1.113 + return h & 0x7fffffff;
1.114 +}
1.115 +static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.116 + if( n1!=n2 ) return 1;
1.117 + return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
1.118 +}
1.119 +
1.120 +/*
1.121 +** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
1.122 +*/
1.123 +static int binHash(const void *pKey, int nKey){
1.124 + int h = 0;
1.125 + const char *z = (const char *)pKey;
1.126 + while( nKey-- > 0 ){
1.127 + h = (h<<3) ^ h ^ *(z++);
1.128 + }
1.129 + return h & 0x7fffffff;
1.130 +}
1.131 +static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.132 + if( n1!=n2 ) return 1;
1.133 + return memcmp(pKey1,pKey2,n1);
1.134 +}
1.135 +
1.136 +/*
1.137 +** Return a pointer to the appropriate hash function given the key class.
1.138 +**
1.139 +** The C syntax in this function definition may be unfamilar to some
1.140 +** programmers, so we provide the following additional explanation:
1.141 +**
1.142 +** The name of the function is "hashFunction". The function takes a
1.143 +** single parameter "keyClass". The return value of hashFunction()
1.144 +** is a pointer to another function. Specifically, the return value
1.145 +** of hashFunction() is a pointer to a function that takes two parameters
1.146 +** with types "const void*" and "int" and returns an "int".
1.147 +*/
1.148 +static int (*hashFunction(int keyClass))(const void*,int){
1.149 +#if 0 /* HASH_INT and HASH_POINTER are never used */
1.150 + switch( keyClass ){
1.151 + case SQLITE_HASH_INT: return &intHash;
1.152 + case SQLITE_HASH_POINTER: return &ptrHash;
1.153 + case SQLITE_HASH_STRING: return &strHash;
1.154 + case SQLITE_HASH_BINARY: return &binHash;;
1.155 + default: break;
1.156 + }
1.157 + return 0;
1.158 +#else
1.159 + if( keyClass==SQLITE_HASH_STRING ){
1.160 + return &strHash;
1.161 + }else{
1.162 + assert( keyClass==SQLITE_HASH_BINARY );
1.163 + return &binHash;
1.164 + }
1.165 +#endif
1.166 +}
1.167 +
1.168 +/*
1.169 +** Return a pointer to the appropriate hash function given the key class.
1.170 +**
1.171 +** For help in interpreted the obscure C code in the function definition,
1.172 +** see the header comment on the previous function.
1.173 +*/
1.174 +static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
1.175 +#if 0 /* HASH_INT and HASH_POINTER are never used */
1.176 + switch( keyClass ){
1.177 + case SQLITE_HASH_INT: return &intCompare;
1.178 + case SQLITE_HASH_POINTER: return &ptrCompare;
1.179 + case SQLITE_HASH_STRING: return &strCompare;
1.180 + case SQLITE_HASH_BINARY: return &binCompare;
1.181 + default: break;
1.182 + }
1.183 + return 0;
1.184 +#else
1.185 + if( keyClass==SQLITE_HASH_STRING ){
1.186 + return &strCompare;
1.187 + }else{
1.188 + assert( keyClass==SQLITE_HASH_BINARY );
1.189 + return &binCompare;
1.190 + }
1.191 +#endif
1.192 +}
1.193 +
1.194 +/* Link an element into the hash table
1.195 +*/
1.196 +static void insertElement(
1.197 + Hash *pH, /* The complete hash table */
1.198 + struct _ht *pEntry, /* The entry into which pNew is inserted */
1.199 + HashElem *pNew /* The element to be inserted */
1.200 +){
1.201 + HashElem *pHead; /* First element already in pEntry */
1.202 + pHead = pEntry->chain;
1.203 + if( pHead ){
1.204 + pNew->next = pHead;
1.205 + pNew->prev = pHead->prev;
1.206 + if( pHead->prev ){ pHead->prev->next = pNew; }
1.207 + else { pH->first = pNew; }
1.208 + pHead->prev = pNew;
1.209 + }else{
1.210 + pNew->next = pH->first;
1.211 + if( pH->first ){ pH->first->prev = pNew; }
1.212 + pNew->prev = 0;
1.213 + pH->first = pNew;
1.214 + }
1.215 + pEntry->count++;
1.216 + pEntry->chain = pNew;
1.217 +}
1.218 +
1.219 +
1.220 +/* Resize the hash table so that it cantains "new_size" buckets.
1.221 +** "new_size" must be a power of 2. The hash table might fail
1.222 +** to resize if sqliteMalloc() fails.
1.223 +*/
1.224 +static void rehash(Hash *pH, int new_size){
1.225 + struct _ht *new_ht; /* The new hash table */
1.226 + HashElem *elem, *next_elem; /* For looping over existing elements */
1.227 + int (*xHash)(const void*,int); /* The hash function */
1.228 +
1.229 + assert( (new_size & (new_size-1))==0 );
1.230 + new_ht = (struct _ht *)pH->xMalloc( new_size*sizeof(struct _ht) );
1.231 + if( new_ht==0 ) return;
1.232 + if( pH->ht ) pH->xFree(pH->ht);
1.233 + pH->ht = new_ht;
1.234 + pH->htsize = new_size;
1.235 + xHash = hashFunction(pH->keyClass);
1.236 + for(elem=pH->first, pH->first=0; elem; elem = next_elem){
1.237 + int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
1.238 + next_elem = elem->next;
1.239 + insertElement(pH, &new_ht[h], elem);
1.240 + }
1.241 +}
1.242 +
1.243 +/* This function (for internal use only) locates an element in an
1.244 +** hash table that matches the given key. The hash for this key has
1.245 +** already been computed and is passed as the 4th parameter.
1.246 +*/
1.247 +static HashElem *findElementGivenHash(
1.248 + const Hash *pH, /* The pH to be searched */
1.249 + const void *pKey, /* The key we are searching for */
1.250 + int nKey,
1.251 + int h /* The hash for this key. */
1.252 +){
1.253 + HashElem *elem; /* Used to loop thru the element list */
1.254 + int count; /* Number of elements left to test */
1.255 + int (*xCompare)(const void*,int,const void*,int); /* comparison function */
1.256 +
1.257 + if( pH->ht ){
1.258 + struct _ht *pEntry = &pH->ht[h];
1.259 + elem = pEntry->chain;
1.260 + count = pEntry->count;
1.261 + xCompare = compareFunction(pH->keyClass);
1.262 + while( count-- && elem ){
1.263 + if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
1.264 + return elem;
1.265 + }
1.266 + elem = elem->next;
1.267 + }
1.268 + }
1.269 + return 0;
1.270 +}
1.271 +
1.272 +/* Remove a single entry from the hash table given a pointer to that
1.273 +** element and a hash on the element's key.
1.274 +*/
1.275 +static void removeElementGivenHash(
1.276 + Hash *pH, /* The pH containing "elem" */
1.277 + HashElem* elem, /* The element to be removed from the pH */
1.278 + int h /* Hash value for the element */
1.279 +){
1.280 + struct _ht *pEntry;
1.281 + if( elem->prev ){
1.282 + elem->prev->next = elem->next;
1.283 + }else{
1.284 + pH->first = elem->next;
1.285 + }
1.286 + if( elem->next ){
1.287 + elem->next->prev = elem->prev;
1.288 + }
1.289 + pEntry = &pH->ht[h];
1.290 + if( pEntry->chain==elem ){
1.291 + pEntry->chain = elem->next;
1.292 + }
1.293 + pEntry->count--;
1.294 + if( pEntry->count<=0 ){
1.295 + pEntry->chain = 0;
1.296 + }
1.297 + if( pH->copyKey ){
1.298 + pH->xFree(elem->pKey);
1.299 + }
1.300 + pH->xFree( elem );
1.301 + pH->count--;
1.302 + if( pH->count<=0 ){
1.303 + assert( pH->first==0 );
1.304 + assert( pH->count==0 );
1.305 + sqlite3HashClear(pH);
1.306 + }
1.307 +}
1.308 +
1.309 +/* Attempt to locate an element of the hash table pH with a key
1.310 +** that matches pKey,nKey. Return the data for this element if it is
1.311 +** found, or NULL if there is no match.
1.312 +*/
1.313 +void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
1.314 + int h; /* A hash on key */
1.315 + HashElem *elem; /* The element that matches key */
1.316 + int (*xHash)(const void*,int); /* The hash function */
1.317 +
1.318 + if( pH==0 || pH->ht==0 ) return 0;
1.319 + xHash = hashFunction(pH->keyClass);
1.320 + assert( xHash!=0 );
1.321 + h = (*xHash)(pKey,nKey);
1.322 + assert( (pH->htsize & (pH->htsize-1))==0 );
1.323 + elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
1.324 + return elem ? elem->data : 0;
1.325 +}
1.326 +
1.327 +/* Insert an element into the hash table pH. The key is pKey,nKey
1.328 +** and the data is "data".
1.329 +**
1.330 +** If no element exists with a matching key, then a new
1.331 +** element is created. A copy of the key is made if the copyKey
1.332 +** flag is set. NULL is returned.
1.333 +**
1.334 +** If another element already exists with the same key, then the
1.335 +** new data replaces the old data and the old data is returned.
1.336 +** The key is not copied in this instance. If a malloc fails, then
1.337 +** the new data is returned and the hash table is unchanged.
1.338 +**
1.339 +** If the "data" parameter to this function is NULL, then the
1.340 +** element corresponding to "key" is removed from the hash table.
1.341 +*/
1.342 +void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
1.343 + int hraw; /* Raw hash value of the key */
1.344 + int h; /* the hash of the key modulo hash table size */
1.345 + HashElem *elem; /* Used to loop thru the element list */
1.346 + HashElem *new_elem; /* New element added to the pH */
1.347 + int (*xHash)(const void*,int); /* The hash function */
1.348 +
1.349 + assert( pH!=0 );
1.350 + xHash = hashFunction(pH->keyClass);
1.351 + assert( xHash!=0 );
1.352 + hraw = (*xHash)(pKey, nKey);
1.353 + assert( (pH->htsize & (pH->htsize-1))==0 );
1.354 + h = hraw & (pH->htsize-1);
1.355 + elem = findElementGivenHash(pH,pKey,nKey,h);
1.356 + if( elem ){
1.357 + void *old_data = elem->data;
1.358 + if( data==0 ){
1.359 + removeElementGivenHash(pH,elem,h);
1.360 + }else{
1.361 + elem->data = data;
1.362 + }
1.363 + return old_data;
1.364 + }
1.365 + if( data==0 ) return 0;
1.366 + new_elem = (HashElem*)pH->xMalloc( sizeof(HashElem) );
1.367 + if( new_elem==0 ) return data;
1.368 + if( pH->copyKey && pKey!=0 ){
1.369 + new_elem->pKey = pH->xMalloc( nKey );
1.370 + if( new_elem->pKey==0 ){
1.371 + pH->xFree(new_elem);
1.372 + return data;
1.373 + }
1.374 + memcpy((void*)new_elem->pKey, pKey, nKey);
1.375 + }else{
1.376 + new_elem->pKey = (void*)pKey;
1.377 + }
1.378 + new_elem->nKey = nKey;
1.379 + pH->count++;
1.380 + if( pH->htsize==0 ){
1.381 + rehash(pH,8);
1.382 + if( pH->htsize==0 ){
1.383 + pH->count = 0;
1.384 + if( pH->copyKey ){
1.385 + pH->xFree(new_elem->pKey);
1.386 + }
1.387 + pH->xFree(new_elem);
1.388 + return data;
1.389 + }
1.390 + }
1.391 + if( pH->count > pH->htsize ){
1.392 + rehash(pH,pH->htsize*2);
1.393 + }
1.394 + assert( pH->htsize>0 );
1.395 + assert( (pH->htsize & (pH->htsize-1))==0 );
1.396 + h = hraw & (pH->htsize-1);
1.397 + insertElement(pH, &pH->ht[h], new_elem);
1.398 + new_elem->data = data;
1.399 + return 0;
1.400 +}
