Annotation of embedaddon/sqlite3/ext/fts3/fts3_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 FTS3 module is being built as an extension
! 21: ** (in which case SQLITE_CORE is not defined), or
! 22: **
! 23: ** * The FTS3 module is being built into the core of
! 24: ** SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
! 25: */
! 26: #include "fts3Int.h"
! 27: #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
! 28:
! 29: #include <assert.h>
! 30: #include <stdlib.h>
! 31: #include <string.h>
! 32:
! 33: #include "fts3_hash.h"
! 34:
! 35: /*
! 36: ** Malloc and Free functions
! 37: */
! 38: static void *fts3HashMalloc(int n){
! 39: void *p = sqlite3_malloc(n);
! 40: if( p ){
! 41: memset(p, 0, n);
! 42: }
! 43: return p;
! 44: }
! 45: static void fts3HashFree(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: ** FTS3_HASH_BINARY or FTS3_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 sqlite3Fts3HashInit(Fts3Hash *pNew, char keyClass, char copyKey){
! 60: assert( pNew!=0 );
! 61: assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_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 sqlite3Fts3HashClear(Fts3Hash *pH){
! 75: Fts3HashElem *elem; /* For looping over all elements of the table */
! 76:
! 77: assert( pH!=0 );
! 78: elem = pH->first;
! 79: pH->first = 0;
! 80: fts3HashFree(pH->ht);
! 81: pH->ht = 0;
! 82: pH->htsize = 0;
! 83: while( elem ){
! 84: Fts3HashElem *next_elem = elem->next;
! 85: if( pH->copyKey && elem->pKey ){
! 86: fts3HashFree(elem->pKey);
! 87: }
! 88: fts3HashFree(elem);
! 89: elem = next_elem;
! 90: }
! 91: pH->count = 0;
! 92: }
! 93:
! 94: /*
! 95: ** Hash and comparison functions when the mode is FTS3_HASH_STRING
! 96: */
! 97: static int fts3StrHash(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 fts3StrCompare(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 FTS3_HASH_BINARY
! 114: */
! 115: static int fts3BinHash(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 fts3BinCompare(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 "ftsHashFunction". The function takes a
! 135: ** single parameter "keyClass". The return value of ftsHashFunction()
! 136: ** is a pointer to another function. Specifically, the return value
! 137: ** of ftsHashFunction() 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 (*ftsHashFunction(int keyClass))(const void*,int){
! 141: if( keyClass==FTS3_HASH_STRING ){
! 142: return &fts3StrHash;
! 143: }else{
! 144: assert( keyClass==FTS3_HASH_BINARY );
! 145: return &fts3BinHash;
! 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 (*ftsCompareFunction(int keyClass))(const void*,int,const void*,int){
! 156: if( keyClass==FTS3_HASH_STRING ){
! 157: return &fts3StrCompare;
! 158: }else{
! 159: assert( keyClass==FTS3_HASH_BINARY );
! 160: return &fts3BinCompare;
! 161: }
! 162: }
! 163:
! 164: /* Link an element into the hash table
! 165: */
! 166: static void fts3HashInsertElement(
! 167: Fts3Hash *pH, /* The complete hash table */
! 168: struct _fts3ht *pEntry, /* The entry into which pNew is inserted */
! 169: Fts3HashElem *pNew /* The element to be inserted */
! 170: ){
! 171: Fts3HashElem *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: ** Return non-zero if a memory allocation error occurs.
! 195: */
! 196: static int fts3Rehash(Fts3Hash *pH, int new_size){
! 197: struct _fts3ht *new_ht; /* The new hash table */
! 198: Fts3HashElem *elem, *next_elem; /* For looping over existing elements */
! 199: int (*xHash)(const void*,int); /* The hash function */
! 200:
! 201: assert( (new_size & (new_size-1))==0 );
! 202: new_ht = (struct _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) );
! 203: if( new_ht==0 ) return 1;
! 204: fts3HashFree(pH->ht);
! 205: pH->ht = new_ht;
! 206: pH->htsize = new_size;
! 207: xHash = ftsHashFunction(pH->keyClass);
! 208: for(elem=pH->first, pH->first=0; elem; elem = next_elem){
! 209: int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
! 210: next_elem = elem->next;
! 211: fts3HashInsertElement(pH, &new_ht[h], elem);
! 212: }
! 213: return 0;
! 214: }
! 215:
! 216: /* This function (for internal use only) locates an element in an
! 217: ** hash table that matches the given key. The hash for this key has
! 218: ** already been computed and is passed as the 4th parameter.
! 219: */
! 220: static Fts3HashElem *fts3FindElementByHash(
! 221: const Fts3Hash *pH, /* The pH to be searched */
! 222: const void *pKey, /* The key we are searching for */
! 223: int nKey,
! 224: int h /* The hash for this key. */
! 225: ){
! 226: Fts3HashElem *elem; /* Used to loop thru the element list */
! 227: int count; /* Number of elements left to test */
! 228: int (*xCompare)(const void*,int,const void*,int); /* comparison function */
! 229:
! 230: if( pH->ht ){
! 231: struct _fts3ht *pEntry = &pH->ht[h];
! 232: elem = pEntry->chain;
! 233: count = pEntry->count;
! 234: xCompare = ftsCompareFunction(pH->keyClass);
! 235: while( count-- && elem ){
! 236: if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
! 237: return elem;
! 238: }
! 239: elem = elem->next;
! 240: }
! 241: }
! 242: return 0;
! 243: }
! 244:
! 245: /* Remove a single entry from the hash table given a pointer to that
! 246: ** element and a hash on the element's key.
! 247: */
! 248: static void fts3RemoveElementByHash(
! 249: Fts3Hash *pH, /* The pH containing "elem" */
! 250: Fts3HashElem* elem, /* The element to be removed from the pH */
! 251: int h /* Hash value for the element */
! 252: ){
! 253: struct _fts3ht *pEntry;
! 254: if( elem->prev ){
! 255: elem->prev->next = elem->next;
! 256: }else{
! 257: pH->first = elem->next;
! 258: }
! 259: if( elem->next ){
! 260: elem->next->prev = elem->prev;
! 261: }
! 262: pEntry = &pH->ht[h];
! 263: if( pEntry->chain==elem ){
! 264: pEntry->chain = elem->next;
! 265: }
! 266: pEntry->count--;
! 267: if( pEntry->count<=0 ){
! 268: pEntry->chain = 0;
! 269: }
! 270: if( pH->copyKey && elem->pKey ){
! 271: fts3HashFree(elem->pKey);
! 272: }
! 273: fts3HashFree( elem );
! 274: pH->count--;
! 275: if( pH->count<=0 ){
! 276: assert( pH->first==0 );
! 277: assert( pH->count==0 );
! 278: fts3HashClear(pH);
! 279: }
! 280: }
! 281:
! 282: Fts3HashElem *sqlite3Fts3HashFindElem(
! 283: const Fts3Hash *pH,
! 284: const void *pKey,
! 285: int nKey
! 286: ){
! 287: int h; /* A hash on key */
! 288: int (*xHash)(const void*,int); /* The hash function */
! 289:
! 290: if( pH==0 || pH->ht==0 ) return 0;
! 291: xHash = ftsHashFunction(pH->keyClass);
! 292: assert( xHash!=0 );
! 293: h = (*xHash)(pKey,nKey);
! 294: assert( (pH->htsize & (pH->htsize-1))==0 );
! 295: return fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1));
! 296: }
! 297:
! 298: /*
! 299: ** Attempt to locate an element of the hash table pH with a key
! 300: ** that matches pKey,nKey. Return the data for this element if it is
! 301: ** found, or NULL if there is no match.
! 302: */
! 303: void *sqlite3Fts3HashFind(const Fts3Hash *pH, const void *pKey, int nKey){
! 304: Fts3HashElem *pElem; /* The element that matches key (if any) */
! 305:
! 306: pElem = sqlite3Fts3HashFindElem(pH, pKey, nKey);
! 307: return pElem ? pElem->data : 0;
! 308: }
! 309:
! 310: /* Insert an element into the hash table pH. The key is pKey,nKey
! 311: ** and the data is "data".
! 312: **
! 313: ** If no element exists with a matching key, then a new
! 314: ** element is created. A copy of the key is made if the copyKey
! 315: ** flag is set. NULL is returned.
! 316: **
! 317: ** If another element already exists with the same key, then the
! 318: ** new data replaces the old data and the old data is returned.
! 319: ** The key is not copied in this instance. If a malloc fails, then
! 320: ** the new data is returned and the hash table is unchanged.
! 321: **
! 322: ** If the "data" parameter to this function is NULL, then the
! 323: ** element corresponding to "key" is removed from the hash table.
! 324: */
! 325: void *sqlite3Fts3HashInsert(
! 326: Fts3Hash *pH, /* The hash table to insert into */
! 327: const void *pKey, /* The key */
! 328: int nKey, /* Number of bytes in the key */
! 329: void *data /* The data */
! 330: ){
! 331: int hraw; /* Raw hash value of the key */
! 332: int h; /* the hash of the key modulo hash table size */
! 333: Fts3HashElem *elem; /* Used to loop thru the element list */
! 334: Fts3HashElem *new_elem; /* New element added to the pH */
! 335: int (*xHash)(const void*,int); /* The hash function */
! 336:
! 337: assert( pH!=0 );
! 338: xHash = ftsHashFunction(pH->keyClass);
! 339: assert( xHash!=0 );
! 340: hraw = (*xHash)(pKey, nKey);
! 341: assert( (pH->htsize & (pH->htsize-1))==0 );
! 342: h = hraw & (pH->htsize-1);
! 343: elem = fts3FindElementByHash(pH,pKey,nKey,h);
! 344: if( elem ){
! 345: void *old_data = elem->data;
! 346: if( data==0 ){
! 347: fts3RemoveElementByHash(pH,elem,h);
! 348: }else{
! 349: elem->data = data;
! 350: }
! 351: return old_data;
! 352: }
! 353: if( data==0 ) return 0;
! 354: if( (pH->htsize==0 && fts3Rehash(pH,8))
! 355: || (pH->count>=pH->htsize && fts3Rehash(pH, pH->htsize*2))
! 356: ){
! 357: pH->count = 0;
! 358: return data;
! 359: }
! 360: assert( pH->htsize>0 );
! 361: new_elem = (Fts3HashElem*)fts3HashMalloc( sizeof(Fts3HashElem) );
! 362: if( new_elem==0 ) return data;
! 363: if( pH->copyKey && pKey!=0 ){
! 364: new_elem->pKey = fts3HashMalloc( nKey );
! 365: if( new_elem->pKey==0 ){
! 366: fts3HashFree(new_elem);
! 367: return data;
! 368: }
! 369: memcpy((void*)new_elem->pKey, pKey, nKey);
! 370: }else{
! 371: new_elem->pKey = (void*)pKey;
! 372: }
! 373: new_elem->nKey = nKey;
! 374: pH->count++;
! 375: assert( pH->htsize>0 );
! 376: assert( (pH->htsize & (pH->htsize-1))==0 );
! 377: h = hraw & (pH->htsize-1);
! 378: fts3HashInsertElement(pH, &pH->ht[h], new_elem);
! 379: new_elem->data = data;
! 380: return 0;
! 381: }
! 382:
! 383: #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fts3_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 / fts3