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. */ 21 typedef struct fts1Hash fts1Hash; 22 typedef 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 */ 32 struct 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 */ 52 struct 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 */ 76 void sqlite3Fts1HashInit(fts1Hash*, int keytype, int copyKey); 77 void *sqlite3Fts1HashInsert(fts1Hash*, const void *pKey, int nKey, void *pData); 78 void *sqlite3Fts1HashFind(const fts1Hash*, const void *pKey, int nKey); 79 void 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
