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 _FTS2_HASH_H_ 18#define _FTS2_HASH_H_ 19 20/* Forward declarations of structures. */ 21typedef struct fts2Hash fts2Hash; 22typedef struct fts2HashElem fts2HashElem; 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 fts2Hash { 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 fts2HashElem *first; /* The first element of the array */ 37 int htsize; /* Number of buckets in the hash table */ 38 struct _fts2ht { /* the hash table */ 39 int count; /* Number of entries with this hash */ 40 fts2HashElem *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 fts2HashElem { 51 fts2HashElem *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** FTS2_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** FTS2_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 fts2HashInit is 1. 67*/ 68#define FTS2_HASH_STRING 1 69#define FTS2_HASH_BINARY 2 70 71/* 72** Access routines. To delete, insert a NULL pointer. 73*/ 74void sqlite3Fts2HashInit(fts2Hash*, int keytype, int copyKey); 75void *sqlite3Fts2HashInsert(fts2Hash*, const void *pKey, int nKey, void *pData); 76void *sqlite3Fts2HashFind(const fts2Hash*, const void *pKey, int nKey); 77void sqlite3Fts2HashClear(fts2Hash*); 78 79/* 80** Shorthand for the functions above 81*/ 82#define fts2HashInit sqlite3Fts2HashInit 83#define fts2HashInsert sqlite3Fts2HashInsert 84#define fts2HashFind sqlite3Fts2HashFind 85#define fts2HashClear sqlite3Fts2HashClear 86 87/* 88** Macros for looping over all elements of a hash table. The idiom is 89** like this: 90** 91** fts2Hash h; 92** fts2HashElem *p; 93** ... 94** for(p=fts2HashFirst(&h); p; p=fts2HashNext(p)){ 95** SomeStructure *pData = fts2HashData(p); 96** // do something with pData 97** } 98*/ 99#define fts2HashFirst(H) ((H)->first) 100#define fts2HashNext(E) ((E)->next) 101#define fts2HashData(E) ((E)->data) 102#define fts2HashKey(E) ((E)->pKey) 103#define fts2HashKeysize(E) ((E)->nKey) 104 105/* 106** Number of entries in a hash table 107*/ 108#define fts2HashCount(H) ((H)->count) 109 110#endif /* _FTS2_HASH_H_ */ 111