This source file includes following definitions.
- fts3HashMalloc
- fts3HashFree
- sqlite3Fts3HashInit
- sqlite3Fts3HashClear
- fts3StrHash
- fts3StrCompare
- fts3BinHash
- fts3BinCompare
- ftsHashFunction
- ftsCompareFunction
- fts3HashInsertElement
- fts3Rehash
- fts3FindElementByHash
- fts3RemoveElementByHash
- sqlite3Fts3HashFindElem
- sqlite3Fts3HashFind
- sqlite3Fts3HashInsert
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "sqlite3.h"
#include "fts3_hash.h"
static void *fts3HashMalloc(int n){
void *p = sqlite3_malloc(n);
if( p ){
memset(p, 0, n);
}
return p;
}
static void fts3HashFree(void *p){
sqlite3_free(p);
}
void sqlite3Fts3HashInit(Fts3Hash *pNew, char keyClass, char copyKey){
assert( pNew!=0 );
assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_HASH_BINARY );
pNew->keyClass = keyClass;
pNew->copyKey = copyKey;
pNew->first = 0;
pNew->count = 0;
pNew->htsize = 0;
pNew->ht = 0;
}
void sqlite3Fts3HashClear(Fts3Hash *pH){
Fts3HashElem *elem;
assert( pH!=0 );
elem = pH->first;
pH->first = 0;
fts3HashFree(pH->ht);
pH->ht = 0;
pH->htsize = 0;
while( elem ){
Fts3HashElem *next_elem = elem->next;
if( pH->copyKey && elem->pKey ){
fts3HashFree(elem->pKey);
}
fts3HashFree(elem);
elem = next_elem;
}
pH->count = 0;
}
static int fts3StrHash(const void *pKey, int nKey){
const char *z = (const char *)pKey;
int h = 0;
if( nKey<=0 ) nKey = (int) strlen(z);
while( nKey > 0 ){
h = (h<<3) ^ h ^ *z++;
nKey--;
}
return h & 0x7fffffff;
}
static int fts3StrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
if( n1!=n2 ) return 1;
return strncmp((const char*)pKey1,(const char*)pKey2,n1);
}
static int fts3BinHash(const void *pKey, int nKey){
int h = 0;
const char *z = (const char *)pKey;
while( nKey-- > 0 ){
h = (h<<3) ^ h ^ *(z++);
}
return h & 0x7fffffff;
}
static int fts3BinCompare(const void *pKey1, int n1, const void *pKey2, int n2){
if( n1!=n2 ) return 1;
return memcmp(pKey1,pKey2,n1);
}
static int (*ftsHashFunction(int keyClass))(const void*,int){
if( keyClass==FTS3_HASH_STRING ){
return &fts3StrHash;
}else{
assert( keyClass==FTS3_HASH_BINARY );
return &fts3BinHash;
}
}
static int (*ftsCompareFunction(int keyClass))(const void*,int,const void*,int){
if( keyClass==FTS3_HASH_STRING ){
return &fts3StrCompare;
}else{
assert( keyClass==FTS3_HASH_BINARY );
return &fts3BinCompare;
}
}
static void fts3HashInsertElement(
Fts3Hash *pH,
struct _fts3ht *pEntry,
Fts3HashElem *pNew
){
Fts3HashElem *pHead;
pHead = pEntry->chain;
if( pHead ){
pNew->next = pHead;
pNew->prev = pHead->prev;
if( pHead->prev ){ pHead->prev->next = pNew; }
else { pH->first = pNew; }
pHead->prev = pNew;
}else{
pNew->next = pH->first;
if( pH->first ){ pH->first->prev = pNew; }
pNew->prev = 0;
pH->first = pNew;
}
pEntry->count++;
pEntry->chain = pNew;
}
static int fts3Rehash(Fts3Hash *pH, int new_size){
struct _fts3ht *new_ht;
Fts3HashElem *elem, *next_elem;
int (*xHash)(const void*,int);
assert( (new_size & (new_size-1))==0 );
new_ht = (struct _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) );
if( new_ht==0 ) return 1;
fts3HashFree(pH->ht);
pH->ht = new_ht;
pH->htsize = new_size;
xHash = ftsHashFunction(pH->keyClass);
for(elem=pH->first, pH->first=0; elem; elem = next_elem){
int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
next_elem = elem->next;
fts3HashInsertElement(pH, &new_ht[h], elem);
}
return 0;
}
static Fts3HashElem *fts3FindElementByHash(
const Fts3Hash *pH,
const void *pKey,
int nKey,
int h
){
Fts3HashElem *elem;
int count;
int (*xCompare)(const void*,int,const void*,int);
if( pH->ht ){
struct _fts3ht *pEntry = &pH->ht[h];
elem = pEntry->chain;
count = pEntry->count;
xCompare = ftsCompareFunction(pH->keyClass);
while( count-- && elem ){
if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){
return elem;
}
elem = elem->next;
}
}
return 0;
}
static void fts3RemoveElementByHash(
Fts3Hash *pH,
Fts3HashElem* elem,
int h
){
struct _fts3ht *pEntry;
if( elem->prev ){
elem->prev->next = elem->next;
}else{
pH->first = elem->next;
}
if( elem->next ){
elem->next->prev = elem->prev;
}
pEntry = &pH->ht[h];
if( pEntry->chain==elem ){
pEntry->chain = elem->next;
}
pEntry->count--;
if( pEntry->count<=0 ){
pEntry->chain = 0;
}
if( pH->copyKey && elem->pKey ){
fts3HashFree(elem->pKey);
}
fts3HashFree( elem );
pH->count--;
if( pH->count<=0 ){
assert( pH->first==0 );
assert( pH->count==0 );
fts3HashClear(pH);
}
}
Fts3HashElem *sqlite3Fts3HashFindElem(
const Fts3Hash *pH,
const void *pKey,
int nKey
){
int h;
int (*xHash)(const void*,int);
if( pH==0 || pH->ht==0 ) return 0;
xHash = ftsHashFunction(pH->keyClass);
assert( xHash!=0 );
h = (*xHash)(pKey,nKey);
assert( (pH->htsize & (pH->htsize-1))==0 );
return fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1));
}
void *sqlite3Fts3HashFind(const Fts3Hash *pH, const void *pKey, int nKey){
Fts3HashElem *pElem;
pElem = sqlite3Fts3HashFindElem(pH, pKey, nKey);
return pElem ? pElem->data : 0;
}
void *sqlite3Fts3HashInsert(
Fts3Hash *pH,
const void *pKey,
int nKey,
void *data
){
int hraw;
int h;
Fts3HashElem *elem;
Fts3HashElem *new_elem;
int (*xHash)(const void*,int);
assert( pH!=0 );
xHash = ftsHashFunction(pH->keyClass);
assert( xHash!=0 );
hraw = (*xHash)(pKey, nKey);
assert( (pH->htsize & (pH->htsize-1))==0 );
h = hraw & (pH->htsize-1);
elem = fts3FindElementByHash(pH,pKey,nKey,h);
if( elem ){
void *old_data = elem->data;
if( data==0 ){
fts3RemoveElementByHash(pH,elem,h);
}else{
elem->data = data;
}
return old_data;
}
if( data==0 ) return 0;
if( (pH->htsize==0 && fts3Rehash(pH,8))
|| (pH->count>=pH->htsize && fts3Rehash(pH, pH->htsize*2))
){
pH->count = 0;
return data;
}
assert( pH->htsize>0 );
new_elem = (Fts3HashElem*)fts3HashMalloc( sizeof(Fts3HashElem) );
if( new_elem==0 ) return data;
if( pH->copyKey && pKey!=0 ){
new_elem->pKey = fts3HashMalloc( nKey );
if( new_elem->pKey==0 ){
fts3HashFree(new_elem);
return data;
}
memcpy((void*)new_elem->pKey, pKey, nKey);
}else{
new_elem->pKey = (void*)pKey;
}
new_elem->nKey = nKey;
pH->count++;
assert( pH->htsize>0 );
assert( (pH->htsize & (pH->htsize-1))==0 );
h = hraw & (pH->htsize-1);
fts3HashInsertElement(pH, &pH->ht[h], new_elem);
new_elem->data = data;
return 0;
}
#endif