1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sqlite3api/SQLite/fts3_hash.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,374 @@
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 used in SQLite.
1.16 +** We've modified it slightly to serve as a standalone hash table
1.17 +** implementation for the full-text indexing module.
1.18 +*/
1.19 +
1.20 +/*
1.21 +** The code in this file is only compiled if:
1.22 +**
1.23 +** * The FTS3 module is being built as an extension
1.24 +** (in which case SQLITE_CORE is not defined), or
1.25 +**
1.26 +** * The FTS3 module is being built into the core of
1.27 +** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
1.28 +*/
1.29 +#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
1.30 +
1.31 +#include <assert.h>
1.32 +#include <stdlib.h>
1.33 +#include <string.h>
1.34 +
1.35 +#include "sqlite3.h"
1.36 +#include "fts3_hash.h"
1.37 +
1.38 +/*
1.39 +** Malloc and Free functions
1.40 +*/
1.41 +static void *fts3HashMalloc(int n){
1.42 + void *p = sqlite3_malloc(n);
1.43 + if( p ){
1.44 + memset(p, 0, n);
1.45 + }
1.46 + return p;
1.47 +}
1.48 +static void fts3HashFree(void *p){
1.49 + sqlite3_free(p);
1.50 +}
1.51 +
1.52 +/* Turn bulk memory into a hash table object by initializing the
1.53 +** fields of the Hash structure.
1.54 +**
1.55 +** "pNew" is a pointer to the hash table that is to be initialized.
1.56 +** keyClass is one of the constants
1.57 +** FTS3_HASH_BINARY or FTS3_HASH_STRING. The value of keyClass
1.58 +** determines what kind of key the hash table will use. "copyKey" is
1.59 +** true if the hash table should make its own private copy of keys and
1.60 +** false if it should just use the supplied pointer.
1.61 +*/
1.62 +void sqlite3Fts3HashInit(fts3Hash *pNew, int keyClass, int copyKey){
1.63 + assert( pNew!=0 );
1.64 + assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_HASH_BINARY );
1.65 + pNew->keyClass = keyClass;
1.66 + pNew->copyKey = copyKey;
1.67 + pNew->first = 0;
1.68 + pNew->count = 0;
1.69 + pNew->htsize = 0;
1.70 + pNew->ht = 0;
1.71 +}
1.72 +
1.73 +/* Remove all entries from a hash table. Reclaim all memory.
1.74 +** Call this routine to delete a hash table or to reset a hash table
1.75 +** to the empty state.
1.76 +*/
1.77 +void sqlite3Fts3HashClear(fts3Hash *pH){
1.78 + fts3HashElem *elem; /* For looping over all elements of the table */
1.79 +
1.80 + assert( pH!=0 );
1.81 + elem = pH->first;
1.82 + pH->first = 0;
1.83 + fts3HashFree(pH->ht);
1.84 + pH->ht = 0;
1.85 + pH->htsize = 0;
1.86 + while( elem ){
1.87 + fts3HashElem *next_elem = elem->next;
1.88 + if( pH->copyKey && elem->pKey ){
1.89 + fts3HashFree(elem->pKey);
1.90 + }
1.91 + fts3HashFree(elem);
1.92 + elem = next_elem;
1.93 + }
1.94 + pH->count = 0;
1.95 +}
1.96 +
1.97 +/*
1.98 +** Hash and comparison functions when the mode is FTS3_HASH_STRING
1.99 +*/
1.100 +static int fts3StrHash(const void *pKey, int nKey){
1.101 + const char *z = (const char *)pKey;
1.102 + int h = 0;
1.103 + if( nKey<=0 ) nKey = (int) strlen(z);
1.104 + while( nKey > 0 ){
1.105 + h = (h<<3) ^ h ^ *z++;
1.106 + nKey--;
1.107 + }
1.108 + return h & 0x7fffffff;
1.109 +}
1.110 +static int fts3StrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.111 + if( n1!=n2 ) return 1;
1.112 + return strncmp((const char*)pKey1,(const char*)pKey2,n1);
1.113 +}
1.114 +
1.115 +/*
1.116 +** Hash and comparison functions when the mode is FTS3_HASH_BINARY
1.117 +*/
1.118 +static int fts3BinHash(const void *pKey, int nKey){
1.119 + int h = 0;
1.120 + const char *z = (const char *)pKey;
1.121 + while( nKey-- > 0 ){
1.122 + h = (h<<3) ^ h ^ *(z++);
1.123 + }
1.124 + return h & 0x7fffffff;
1.125 +}
1.126 +static int fts3BinCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.127 + if( n1!=n2 ) return 1;
1.128 + return memcmp(pKey1,pKey2,n1);
1.129 +}
1.130 +
1.131 +/*
1.132 +** Return a pointer to the appropriate hash function given the key class.
1.133 +**
1.134 +** The C syntax in this function definition may be unfamilar to some
1.135 +** programmers, so we provide the following additional explanation:
1.136 +**
1.137 +** The name of the function is "ftsHashFunction". The function takes a
1.138 +** single parameter "keyClass". The return value of ftsHashFunction()
1.139 +** is a pointer to another function. Specifically, the return value
1.140 +** of ftsHashFunction() is a pointer to a function that takes two parameters
1.141 +** with types "const void*" and "int" and returns an "int".
1.142 +*/
1.143 +static int (*ftsHashFunction(int keyClass))(const void*,int){
1.144 + if( keyClass==FTS3_HASH_STRING ){
1.145 + return &fts3StrHash;
1.146 + }else{
1.147 + assert( keyClass==FTS3_HASH_BINARY );
1.148 + return &fts3BinHash;
1.149 + }
1.150 +}
1.151 +
1.152 +/*
1.153 +** Return a pointer to the appropriate hash function given the key class.
1.154 +**
1.155 +** For help in interpreted the obscure C code in the function definition,
1.156 +** see the header comment on the previous function.
1.157 +*/
1.158 +static int (*ftsCompareFunction(int keyClass))(const void*,int,const void*,int){
1.159 + if( keyClass==FTS3_HASH_STRING ){
1.160 + return &fts3StrCompare;
1.161 + }else{
1.162 + assert( keyClass==FTS3_HASH_BINARY );
1.163 + return &fts3BinCompare;
1.164 + }
1.165 +}
1.166 +
1.167 +/* Link an element into the hash table
1.168 +*/
1.169 +static void fts3HashInsertElement(
1.170 + fts3Hash *pH, /* The complete hash table */
1.171 + struct _fts3ht *pEntry, /* The entry into which pNew is inserted */
1.172 + fts3HashElem *pNew /* The element to be inserted */
1.173 +){
1.174 + fts3HashElem *pHead; /* First element already in pEntry */
1.175 + pHead = pEntry->chain;
1.176 + if( pHead ){
1.177 + pNew->next = pHead;
1.178 + pNew->prev = pHead->prev;
1.179 + if( pHead->prev ){ pHead->prev->next = pNew; }
1.180 + else { pH->first = pNew; }
1.181 + pHead->prev = pNew;
1.182 + }else{
1.183 + pNew->next = pH->first;
1.184 + if( pH->first ){ pH->first->prev = pNew; }
1.185 + pNew->prev = 0;
1.186 + pH->first = pNew;
1.187 + }
1.188 + pEntry->count++;
1.189 + pEntry->chain = pNew;
1.190 +}
1.191 +
1.192 +
1.193 +/* Resize the hash table so that it cantains "new_size" buckets.
1.194 +** "new_size" must be a power of 2. The hash table might fail
1.195 +** to resize if sqliteMalloc() fails.
1.196 +*/
1.197 +static void fts3Rehash(fts3Hash *pH, int new_size){
1.198 + struct _fts3ht *new_ht; /* The new hash table */
1.199 + fts3HashElem *elem, *next_elem; /* For looping over existing elements */
1.200 + int (*xHash)(const void*,int); /* The hash function */
1.201 +
1.202 + assert( (new_size & (new_size-1))==0 );
1.203 + new_ht = (struct _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) );
1.204 + if( new_ht==0 ) return;
1.205 + fts3HashFree(pH->ht);
1.206 + pH->ht = new_ht;
1.207 + pH->htsize = new_size;
1.208 + xHash = ftsHashFunction(pH->keyClass);
1.209 + for(elem=pH->first, pH->first=0; elem; elem = next_elem){
1.210 + int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
1.211 + next_elem = elem->next;
1.212 + fts3HashInsertElement(pH, &new_ht[h], elem);
1.213 + }
1.214 +}
1.215 +
1.216 +/* This function (for internal use only) locates an element in an
1.217 +** hash table that matches the given key. The hash for this key has
1.218 +** already been computed and is passed as the 4th parameter.
1.219 +*/
1.220 +static fts3HashElem *fts3FindElementByHash(
1.221 + const fts3Hash *pH, /* The pH to be searched */
1.222 + const void *pKey, /* The key we are searching for */
1.223 + int nKey,
1.224 + int h /* The hash for this key. */
1.225 +){
1.226 + fts3HashElem *elem; /* Used to loop thru the element list */
1.227 + int count; /* Number of elements left to test */
1.228 + int (*xCompare)(const void*,int,const void*,int); /* comparison function */
1.229 +
1.230 + if( pH->ht ){
1.231 + struct _fts3ht *pEntry = &pH->ht[h];
1.232 + elem = pEntry->chain;
1.233 + count = pEntry->count;
1.234 + xCompare = ftsCompareFunction(pH->keyClass);
1.235 + while( count-- && elem ){
1.236 + if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
1.237 + return elem;
1.238 + }
1.239 + elem = elem->next;
1.240 + }
1.241 + }
1.242 + return 0;
1.243 +}
1.244 +
1.245 +/* Remove a single entry from the hash table given a pointer to that
1.246 +** element and a hash on the element's key.
1.247 +*/
1.248 +static void fts3RemoveElementByHash(
1.249 + fts3Hash *pH, /* The pH containing "elem" */
1.250 + fts3HashElem* elem, /* The element to be removed from the pH */
1.251 + int h /* Hash value for the element */
1.252 +){
1.253 + struct _fts3ht *pEntry;
1.254 + if( elem->prev ){
1.255 + elem->prev->next = elem->next;
1.256 + }else{
1.257 + pH->first = elem->next;
1.258 + }
1.259 + if( elem->next ){
1.260 + elem->next->prev = elem->prev;
1.261 + }
1.262 + pEntry = &pH->ht[h];
1.263 + if( pEntry->chain==elem ){
1.264 + pEntry->chain = elem->next;
1.265 + }
1.266 + pEntry->count--;
1.267 + if( pEntry->count<=0 ){
1.268 + pEntry->chain = 0;
1.269 + }
1.270 + if( pH->copyKey && elem->pKey ){
1.271 + fts3HashFree(elem->pKey);
1.272 + }
1.273 + fts3HashFree( elem );
1.274 + pH->count--;
1.275 + if( pH->count<=0 ){
1.276 + assert( pH->first==0 );
1.277 + assert( pH->count==0 );
1.278 + fts3HashClear(pH);
1.279 + }
1.280 +}
1.281 +
1.282 +/* Attempt to locate an element of the hash table pH with a key
1.283 +** that matches pKey,nKey. Return the data for this element if it is
1.284 +** found, or NULL if there is no match.
1.285 +*/
1.286 +void *sqlite3Fts3HashFind(const fts3Hash *pH, const void *pKey, int nKey){
1.287 + int h; /* A hash on key */
1.288 + fts3HashElem *elem; /* The element that matches key */
1.289 + int (*xHash)(const void*,int); /* The hash function */
1.290 +
1.291 + if( pH==0 || pH->ht==0 ) return 0;
1.292 + xHash = ftsHashFunction(pH->keyClass);
1.293 + assert( xHash!=0 );
1.294 + h = (*xHash)(pKey,nKey);
1.295 + assert( (pH->htsize & (pH->htsize-1))==0 );
1.296 + elem = fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1));
1.297 + return elem ? elem->data : 0;
1.298 +}
1.299 +
1.300 +/* Insert an element into the hash table pH. The key is pKey,nKey
1.301 +** and the data is "data".
1.302 +**
1.303 +** If no element exists with a matching key, then a new
1.304 +** element is created. A copy of the key is made if the copyKey
1.305 +** flag is set. NULL is returned.
1.306 +**
1.307 +** If another element already exists with the same key, then the
1.308 +** new data replaces the old data and the old data is returned.
1.309 +** The key is not copied in this instance. If a malloc fails, then
1.310 +** the new data is returned and the hash table is unchanged.
1.311 +**
1.312 +** If the "data" parameter to this function is NULL, then the
1.313 +** element corresponding to "key" is removed from the hash table.
1.314 +*/
1.315 +void *sqlite3Fts3HashInsert(
1.316 + fts3Hash *pH, /* The hash table to insert into */
1.317 + const void *pKey, /* The key */
1.318 + int nKey, /* Number of bytes in the key */
1.319 + void *data /* The data */
1.320 +){
1.321 + int hraw; /* Raw hash value of the key */
1.322 + int h; /* the hash of the key modulo hash table size */
1.323 + fts3HashElem *elem; /* Used to loop thru the element list */
1.324 + fts3HashElem *new_elem; /* New element added to the pH */
1.325 + int (*xHash)(const void*,int); /* The hash function */
1.326 +
1.327 + assert( pH!=0 );
1.328 + xHash = ftsHashFunction(pH->keyClass);
1.329 + assert( xHash!=0 );
1.330 + hraw = (*xHash)(pKey, nKey);
1.331 + assert( (pH->htsize & (pH->htsize-1))==0 );
1.332 + h = hraw & (pH->htsize-1);
1.333 + elem = fts3FindElementByHash(pH,pKey,nKey,h);
1.334 + if( elem ){
1.335 + void *old_data = elem->data;
1.336 + if( data==0 ){
1.337 + fts3RemoveElementByHash(pH,elem,h);
1.338 + }else{
1.339 + elem->data = data;
1.340 + }
1.341 + return old_data;
1.342 + }
1.343 + if( data==0 ) return 0;
1.344 + new_elem = (fts3HashElem*)fts3HashMalloc( sizeof(fts3HashElem) );
1.345 + if( new_elem==0 ) return data;
1.346 + if( pH->copyKey && pKey!=0 ){
1.347 + new_elem->pKey = fts3HashMalloc( nKey );
1.348 + if( new_elem->pKey==0 ){
1.349 + fts3HashFree(new_elem);
1.350 + return data;
1.351 + }
1.352 + memcpy((void*)new_elem->pKey, pKey, nKey);
1.353 + }else{
1.354 + new_elem->pKey = (void*)pKey;
1.355 + }
1.356 + new_elem->nKey = nKey;
1.357 + pH->count++;
1.358 + if( pH->htsize==0 ){
1.359 + fts3Rehash(pH,8);
1.360 + if( pH->htsize==0 ){
1.361 + pH->count = 0;
1.362 + fts3HashFree(new_elem);
1.363 + return data;
1.364 + }
1.365 + }
1.366 + if( pH->count > pH->htsize ){
1.367 + fts3Rehash(pH,pH->htsize*2);
1.368 + }
1.369 + assert( pH->htsize>0 );
1.370 + assert( (pH->htsize & (pH->htsize-1))==0 );
1.371 + h = hraw & (pH->htsize-1);
1.372 + fts3HashInsertElement(pH, &pH->ht[h], new_elem);
1.373 + new_elem->data = data;
1.374 + return 0;
1.375 +}
1.376 +
1.377 +#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */