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 header file for the generic hash-table implemenation 13** used in SQLite. We've modified it slightly to serve as a standalone 14** hash table implementation for the full-text indexing module. 15** 16*/ 17#ifndef _FTS3_HASH_H_ 18#define _FTS3_HASH_H_ 19 20/* Forward declarations of structures. */ 21typedef struct Fts3Hash Fts3Hash; 22typedef struct Fts3HashElem Fts3HashElem; 23 24/* A complete hash table is an instance of the following structure. 25** The internals of this structure are intended to be opaque -- client 26** code should not attempt to access or modify the fields of this structure 27** directly. Change this structure only by using the routines below. 28** However, many of the "procedures" and "functions" for modifying and 29** accessing this structure are really macros, so we can't really make 30** this structure opaque. 31*/ 32struct Fts3Hash { 33 char keyClass; /* HASH_INT, _POINTER, _STRING, _BINARY */ 34 char copyKey; /* True if copy of key made on insert */ 35 int count; /* Number of entries in this table */ 36 Fts3HashElem *first; /* The first element of the array */ 37 int htsize; /* Number of buckets in the hash table */ 38 struct _fts3ht { /* the hash table */ 39 int count; /* Number of entries with this hash */ 40 Fts3HashElem *chain; /* Pointer to first entry with this hash */ 41 } *ht; 42}; 43 44/* Each element in the hash table is an instance of the following 45** structure. All elements are stored on a single doubly-linked list. 46** 47** Again, this structure is intended to be opaque, but it can't really 48** be opaque because it is used by macros. 49*/ 50struct Fts3HashElem { 51 Fts3HashElem *next, *prev; /* Next and previous elements in the table */ 52 void *data; /* Data associated with this element */ 53 void *pKey; int nKey; /* Key associated with this element */ 54}; 55 56/* 57** There are 2 different modes of operation for a hash table: 58** 59** FTS3_HASH_STRING pKey points to a string that is nKey bytes long 60** (including the null-terminator, if any). Case 61** is respected in comparisons. 62** 63** FTS3_HASH_BINARY pKey points to binary data nKey bytes long. 64** memcmp() is used to compare keys. 65** 66** A copy of the key is made if the copyKey parameter to fts3HashInit is 1. 67*/ 68#define FTS3_HASH_STRING 1 69#define FTS3_HASH_BINARY 2 70 71/* 72** Access routines. To delete, insert a NULL pointer. 73*/ 74void sqlite3Fts3HashInit(Fts3Hash *pNew, char keyClass, char copyKey); 75void *sqlite3Fts3HashInsert(Fts3Hash*, const void *pKey, int nKey, void *pData); 76void *sqlite3Fts3HashFind(const Fts3Hash*, const void *pKey, int nKey); 77void sqlite3Fts3HashClear(Fts3Hash*); 78Fts3HashElem *sqlite3Fts3HashFindElem(const Fts3Hash *, const void *, int); 79 80/* 81** Shorthand for the functions above 82*/ 83#define fts3HashInit sqlite3Fts3HashInit 84#define fts3HashInsert sqlite3Fts3HashInsert 85#define fts3HashFind sqlite3Fts3HashFind 86#define fts3HashClear sqlite3Fts3HashClear 87#define fts3HashFindElem sqlite3Fts3HashFindElem 88 89/* 90** Macros for looping over all elements of a hash table. The idiom is 91** like this: 92** 93** Fts3Hash h; 94** Fts3HashElem *p; 95** ... 96** for(p=fts3HashFirst(&h); p; p=fts3HashNext(p)){ 97** SomeStructure *pData = fts3HashData(p); 98** // do something with pData 99** } 100*/ 101#define fts3HashFirst(H) ((H)->first) 102#define fts3HashNext(E) ((E)->next) 103#define fts3HashData(E) ((E)->data) 104#define fts3HashKey(E) ((E)->pKey) 105#define fts3HashKeysize(E) ((E)->nKey) 106 107/* 108** Number of entries in a hash table 109*/ 110#define fts3HashCount(H) ((H)->count) 111 112#endif /* _FTS3_HASH_H_ */ 113