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