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 _FTS1_HASH_H_ 18#define _FTS1_HASH_H_ 19 20/* Forward declarations of structures. */ 21typedef struct fts1Hash fts1Hash; 22typedef struct fts1HashElem fts1HashElem; 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 fts1Hash { 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 fts1HashElem *first; /* The first element of the array */ 37 void *(*xMalloc)(int); /* malloc() function to use */ 38 void (*xFree)(void *); /* free() function to use */ 39 int htsize; /* Number of buckets in the hash table */ 40 struct _fts1ht { /* the hash table */ 41 int count; /* Number of entries with this hash */ 42 fts1HashElem *chain; /* Pointer to first entry with this hash */ 43 } *ht; 44}; 45 46/* Each element in the hash table is an instance of the following 47** structure. All elements are stored on a single doubly-linked list. 48** 49** Again, this structure is intended to be opaque, but it can't really 50** be opaque because it is used by macros. 51*/ 52struct fts1HashElem { 53 fts1HashElem *next, *prev; /* Next and previous elements in the table */ 54 void *data; /* Data associated with this element */ 55 void *pKey; int nKey; /* Key associated with this element */ 56}; 57 58/* 59** There are 2 different modes of operation for a hash table: 60** 61** FTS1_HASH_STRING pKey points to a string that is nKey bytes long 62** (including the null-terminator, if any). Case 63** is respected in comparisons. 64** 65** FTS1_HASH_BINARY pKey points to binary data nKey bytes long. 66** memcmp() is used to compare keys. 67** 68** A copy of the key is made if the copyKey parameter to fts1HashInit is 1. 69*/ 70#define FTS1_HASH_STRING 1 71#define FTS1_HASH_BINARY 2 72 73/* 74** Access routines. To delete, insert a NULL pointer. 75*/ 76void sqlite3Fts1HashInit(fts1Hash*, int keytype, int copyKey); 77void *sqlite3Fts1HashInsert(fts1Hash*, const void *pKey, int nKey, void *pData); 78void *sqlite3Fts1HashFind(const fts1Hash*, const void *pKey, int nKey); 79void sqlite3Fts1HashClear(fts1Hash*); 80 81/* 82** Shorthand for the functions above 83*/ 84#define fts1HashInit sqlite3Fts1HashInit 85#define fts1HashInsert sqlite3Fts1HashInsert 86#define fts1HashFind sqlite3Fts1HashFind 87#define fts1HashClear sqlite3Fts1HashClear 88 89/* 90** Macros for looping over all elements of a hash table. The idiom is 91** like this: 92** 93** fts1Hash h; 94** fts1HashElem *p; 95** ... 96** for(p=fts1HashFirst(&h); p; p=fts1HashNext(p)){ 97** SomeStructure *pData = fts1HashData(p); 98** // do something with pData 99** } 100*/ 101#define fts1HashFirst(H) ((H)->first) 102#define fts1HashNext(E) ((E)->next) 103#define fts1HashData(E) ((E)->data) 104#define fts1HashKey(E) ((E)->pKey) 105#define fts1HashKeysize(E) ((E)->nKey) 106 107/* 108** Number of entries in a hash table 109*/ 110#define fts1HashCount(H) ((H)->count) 111 112#endif /* _FTS1_HASH_H_ */ 113