Annotation of embedaddon/sqlite3/ext/fts2/fts2_hash.c, revision 1.1
1.1 ! misho 1: /*
! 2: ** 2001 September 22
! 3: **
! 4: ** The author disclaims copyright to this source code. In place of
! 5: ** a legal notice, here is a blessing:
! 6: **
! 7: ** May you do good and not evil.
! 8: ** May you find forgiveness for yourself and forgive others.
! 9: ** May you share freely, never taking more than you give.
! 10: **
! 11: *************************************************************************
! 12: ** This is the implementation of generic hash-tables used in SQLite.
! 13: ** We've modified it slightly to serve as a standalone hash table
! 14: ** implementation for the full-text indexing module.
! 15: */
! 16:
! 17: /*
! 18: ** The code in this file is only compiled if:
! 19: **
! 20: ** * The FTS2 module is being built as an extension
! 21: ** (in which case SQLITE_CORE is not defined), or
! 22: **
! 23: ** * The FTS2 module is being built into the core of
! 24: ** SQLite (in which case SQLITE_ENABLE_FTS2 is defined).
! 25: */
! 26: #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2)
! 27:
! 28: #include <assert.h>
! 29: #include <stdlib.h>
! 30: #include <string.h>
! 31:
! 32: #include "sqlite3.h"
! 33: #include "fts2_hash.h"
! 34:
! 35: /*
! 36: ** Malloc and Free functions
! 37: */
! 38: static void *fts2HashMalloc(int n){
! 39: void *p = sqlite3_malloc(n);
! 40: if( p ){
! 41: memset(p, 0, n);
! 42: }
! 43: return p;
! 44: }
! 45: static void fts2HashFree(void *p){
! 46: sqlite3_free(p);
! 47: }
! 48:
! 49: /* Turn bulk memory into a hash table object by initializing the
! 50: ** fields of the Hash structure.
! 51: **
! 52: ** "pNew" is a pointer to the hash table that is to be initialized.
! 53: ** keyClass is one of the constants
! 54: ** FTS2_HASH_BINARY or FTS2_HASH_STRING. The value of keyClass
! 55: ** determines what kind of key the hash table will use. "copyKey" is
! 56: ** true if the hash table should make its own private copy of keys and
! 57: ** false if it should just use the supplied pointer.
! 58: */
! 59: void sqlite3Fts2HashInit(fts2Hash *pNew, int keyClass, int copyKey){
! 60: assert( pNew!=0 );
! 61: assert( keyClass>=FTS2_HASH_STRING && keyClass<=FTS2_HASH_BINARY );
! 62: pNew->keyClass = keyClass;
! 63: pNew->copyKey = copyKey;
! 64: pNew->first = 0;
! 65: pNew->count = 0;
! 66: pNew->htsize = 0;
! 67: pNew->ht = 0;
! 68: }
! 69:
! 70: /* Remove all entries from a hash table. Reclaim all memory.
! 71: ** Call this routine to delete a hash table or to reset a hash table
! 72: ** to the empty state.
! 73: */
! 74: void sqlite3Fts2HashClear(fts2Hash *pH){
! 75: fts2HashElem *elem; /* For looping over all elements of the table */
! 76:
! 77: assert( pH!=0 );
! 78: elem = pH->first;
! 79: pH->first = 0;
! 80: fts2HashFree(pH->ht);
! 81: pH->ht = 0;
! 82: pH->htsize = 0;
! 83: while( elem ){
! 84: fts2HashElem *next_elem = elem->next;
! 85: if( pH->copyKey && elem->pKey ){
! 86: fts2HashFree(elem->pKey);
! 87: }
! 88: fts2HashFree(elem);
! 89: elem = next_elem;
! 90: }
! 91: pH->count = 0;
! 92: }
! 93:
! 94: /*
! 95: ** Hash and comparison functions when the mode is FTS2_HASH_STRING
! 96: */
! 97: static int strHash(const void *pKey, int nKey){
! 98: const char *z = (const char *)pKey;
! 99: int h = 0;
! 100: if( nKey<=0 ) nKey = (int) strlen(z);
! 101: while( nKey > 0 ){
! 102: h = (h<<3) ^ h ^ *z++;
! 103: nKey--;
! 104: }
! 105: return h & 0x7fffffff;
! 106: }
! 107: static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
! 108: if( n1!=n2 ) return 1;
! 109: return strncmp((const char*)pKey1,(const char*)pKey2,n1);
! 110: }
! 111:
! 112: /*
! 113: ** Hash and comparison functions when the mode is FTS2_HASH_BINARY
! 114: */
! 115: static int binHash(const void *pKey, int nKey){
! 116: int h = 0;
! 117: const char *z = (const char *)pKey;
! 118: while( nKey-- > 0 ){
! 119: h = (h<<3) ^ h ^ *(z++);
! 120: }
! 121: return h & 0x7fffffff;
! 122: }
! 123: static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
! 124: if( n1!=n2 ) return 1;
! 125: return memcmp(pKey1,pKey2,n1);
! 126: }
! 127:
! 128: /*
! 129: ** Return a pointer to the appropriate hash function given the key class.
! 130: **
! 131: ** The C syntax in this function definition may be unfamilar to some
! 132: ** programmers, so we provide the following additional explanation:
! 133: **
! 134: ** The name of the function is "hashFunction". The function takes a
! 135: ** single parameter "keyClass". The return value of hashFunction()
! 136: ** is a pointer to another function. Specifically, the return value
! 137: ** of hashFunction() is a pointer to a function that takes two parameters
! 138: ** with types "const void*" and "int" and returns an "int".
! 139: */
! 140: static int (*hashFunction(int keyClass))(const void*,int){
! 141: if( keyClass==FTS2_HASH_STRING ){
! 142: return &strHash;
! 143: }else{
! 144: assert( keyClass==FTS2_HASH_BINARY );
! 145: return &binHash;
! 146: }
! 147: }
! 148:
! 149: /*
! 150: ** Return a pointer to the appropriate hash function given the key class.
! 151: **
! 152: ** For help in interpreted the obscure C code in the function definition,
! 153: ** see the header comment on the previous function.
! 154: */
! 155: static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
! 156: if( keyClass==FTS2_HASH_STRING ){
! 157: return &strCompare;
! 158: }else{
! 159: assert( keyClass==FTS2_HASH_BINARY );
! 160: return &binCompare;
! 161: }
! 162: }
! 163:
! 164: /* Link an element into the hash table
! 165: */
! 166: static void insertElement(
! 167: fts2Hash *pH, /* The complete hash table */
! 168: struct _fts2ht *pEntry, /* The entry into which pNew is inserted */
! 169: fts2HashElem *pNew /* The element to be inserted */
! 170: ){
! 171: fts2HashElem *pHead; /* First element already in pEntry */
! 172: pHead = pEntry->chain;
! 173: if( pHead ){
! 174: pNew->next = pHead;
! 175: pNew->prev = pHead->prev;
! 176: if( pHead->prev ){ pHead->prev->next = pNew; }
! 177: else { pH->first = pNew; }
! 178: pHead->prev = pNew;
! 179: }else{
! 180: pNew->next = pH->first;
! 181: if( pH->first ){ pH->first->prev = pNew; }
! 182: pNew->prev = 0;
! 183: pH->first = pNew;
! 184: }
! 185: pEntry->count++;
! 186: pEntry->chain = pNew;
! 187: }
! 188:
! 189:
! 190: /* Resize the hash table so that it cantains "new_size" buckets.
! 191: ** "new_size" must be a power of 2. The hash table might fail
! 192: ** to resize if sqliteMalloc() fails.
! 193: */
! 194: static void rehash(fts2Hash *pH, int new_size){
! 195: struct _fts2ht *new_ht; /* The new hash table */
! 196: fts2HashElem *elem, *next_elem; /* For looping over existing elements */
! 197: int (*xHash)(const void*,int); /* The hash function */
! 198:
! 199: assert( (new_size & (new_size-1))==0 );
! 200: new_ht = (struct _fts2ht *)fts2HashMalloc( new_size*sizeof(struct _fts2ht) );
! 201: if( new_ht==0 ) return;
! 202: fts2HashFree(pH->ht);
! 203: pH->ht = new_ht;
! 204: pH->htsize = new_size;
! 205: xHash = hashFunction(pH->keyClass);
! 206: for(elem=pH->first, pH->first=0; elem; elem = next_elem){
! 207: int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
! 208: next_elem = elem->next;
! 209: insertElement(pH, &new_ht[h], elem);
! 210: }
! 211: }
! 212:
! 213: /* This function (for internal use only) locates an element in an
! 214: ** hash table that matches the given key. The hash for this key has
! 215: ** already been computed and is passed as the 4th parameter.
! 216: */
! 217: static fts2HashElem *findElementGivenHash(
! 218: const fts2Hash *pH, /* The pH to be searched */
! 219: const void *pKey, /* The key we are searching for */
! 220: int nKey,
! 221: int h /* The hash for this key. */
! 222: ){
! 223: fts2HashElem *elem; /* Used to loop thru the element list */
! 224: int count; /* Number of elements left to test */
! 225: int (*xCompare)(const void*,int,const void*,int); /* comparison function */
! 226:
! 227: if( pH->ht ){
! 228: struct _fts2ht *pEntry = &pH->ht[h];
! 229: elem = pEntry->chain;
! 230: count = pEntry->count;
! 231: xCompare = compareFunction(pH->keyClass);
! 232: while( count-- && elem ){
! 233: if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
! 234: return elem;
! 235: }
! 236: elem = elem->next;
! 237: }
! 238: }
! 239: return 0;
! 240: }
! 241:
! 242: /* Remove a single entry from the hash table given a pointer to that
! 243: ** element and a hash on the element's key.
! 244: */
! 245: static void removeElementGivenHash(
! 246: fts2Hash *pH, /* The pH containing "elem" */
! 247: fts2HashElem* elem, /* The element to be removed from the pH */
! 248: int h /* Hash value for the element */
! 249: ){
! 250: struct _fts2ht *pEntry;
! 251: if( elem->prev ){
! 252: elem->prev->next = elem->next;
! 253: }else{
! 254: pH->first = elem->next;
! 255: }
! 256: if( elem->next ){
! 257: elem->next->prev = elem->prev;
! 258: }
! 259: pEntry = &pH->ht[h];
! 260: if( pEntry->chain==elem ){
! 261: pEntry->chain = elem->next;
! 262: }
! 263: pEntry->count--;
! 264: if( pEntry->count<=0 ){
! 265: pEntry->chain = 0;
! 266: }
! 267: if( pH->copyKey && elem->pKey ){
! 268: fts2HashFree(elem->pKey);
! 269: }
! 270: fts2HashFree( elem );
! 271: pH->count--;
! 272: if( pH->count<=0 ){
! 273: assert( pH->first==0 );
! 274: assert( pH->count==0 );
! 275: fts2HashClear(pH);
! 276: }
! 277: }
! 278:
! 279: /* Attempt to locate an element of the hash table pH with a key
! 280: ** that matches pKey,nKey. Return the data for this element if it is
! 281: ** found, or NULL if there is no match.
! 282: */
! 283: void *sqlite3Fts2HashFind(const fts2Hash *pH, const void *pKey, int nKey){
! 284: int h; /* A hash on key */
! 285: fts2HashElem *elem; /* The element that matches key */
! 286: int (*xHash)(const void*,int); /* The hash function */
! 287:
! 288: if( pH==0 || pH->ht==0 ) return 0;
! 289: xHash = hashFunction(pH->keyClass);
! 290: assert( xHash!=0 );
! 291: h = (*xHash)(pKey,nKey);
! 292: assert( (pH->htsize & (pH->htsize-1))==0 );
! 293: elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
! 294: return elem ? elem->data : 0;
! 295: }
! 296:
! 297: /* Insert an element into the hash table pH. The key is pKey,nKey
! 298: ** and the data is "data".
! 299: **
! 300: ** If no element exists with a matching key, then a new
! 301: ** element is created. A copy of the key is made if the copyKey
! 302: ** flag is set. NULL is returned.
! 303: **
! 304: ** If another element already exists with the same key, then the
! 305: ** new data replaces the old data and the old data is returned.
! 306: ** The key is not copied in this instance. If a malloc fails, then
! 307: ** the new data is returned and the hash table is unchanged.
! 308: **
! 309: ** If the "data" parameter to this function is NULL, then the
! 310: ** element corresponding to "key" is removed from the hash table.
! 311: */
! 312: void *sqlite3Fts2HashInsert(
! 313: fts2Hash *pH, /* The hash table to insert into */
! 314: const void *pKey, /* The key */
! 315: int nKey, /* Number of bytes in the key */
! 316: void *data /* The data */
! 317: ){
! 318: int hraw; /* Raw hash value of the key */
! 319: int h; /* the hash of the key modulo hash table size */
! 320: fts2HashElem *elem; /* Used to loop thru the element list */
! 321: fts2HashElem *new_elem; /* New element added to the pH */
! 322: int (*xHash)(const void*,int); /* The hash function */
! 323:
! 324: assert( pH!=0 );
! 325: xHash = hashFunction(pH->keyClass);
! 326: assert( xHash!=0 );
! 327: hraw = (*xHash)(pKey, nKey);
! 328: assert( (pH->htsize & (pH->htsize-1))==0 );
! 329: h = hraw & (pH->htsize-1);
! 330: elem = findElementGivenHash(pH,pKey,nKey,h);
! 331: if( elem ){
! 332: void *old_data = elem->data;
! 333: if( data==0 ){
! 334: removeElementGivenHash(pH,elem,h);
! 335: }else{
! 336: elem->data = data;
! 337: }
! 338: return old_data;
! 339: }
! 340: if( data==0 ) return 0;
! 341: new_elem = (fts2HashElem*)fts2HashMalloc( sizeof(fts2HashElem) );
! 342: if( new_elem==0 ) return data;
! 343: if( pH->copyKey && pKey!=0 ){
! 344: new_elem->pKey = fts2HashMalloc( nKey );
! 345: if( new_elem->pKey==0 ){
! 346: fts2HashFree(new_elem);
! 347: return data;
! 348: }
! 349: memcpy((void*)new_elem->pKey, pKey, nKey);
! 350: }else{
! 351: new_elem->pKey = (void*)pKey;
! 352: }
! 353: new_elem->nKey = nKey;
! 354: pH->count++;
! 355: if( pH->htsize==0 ){
! 356: rehash(pH,8);
! 357: if( pH->htsize==0 ){
! 358: pH->count = 0;
! 359: fts2HashFree(new_elem);
! 360: return data;
! 361: }
! 362: }
! 363: if( pH->count > pH->htsize ){
! 364: rehash(pH,pH->htsize*2);
! 365: }
! 366: assert( pH->htsize>0 );
! 367: assert( (pH->htsize & (pH->htsize-1))==0 );
! 368: h = hraw & (pH->htsize-1);
! 369: insertElement(pH, &pH->ht[h], new_elem);
! 370: new_elem->data = data;
! 371: return 0;
! 372: }
! 373:
! 374: #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2) */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fts2_hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / ext / fts2