| 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 implementation |
| 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. */ |
| 21 |
typedef struct Fts3Hash Fts3Hash; |
| 22 |
typedef 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 |
*/ |
| 32 |
struct 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 |
*/ |
| 50 |
struct 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 |
*/ |
| 74 |
void sqlite3Fts3HashInit(Fts3Hash *pNew, char keyClass, char copyKey); |
| 75 |
void *sqlite3Fts3HashInsert(Fts3Hash*, const void *pKey, int nKey, void *pData); |
| 76 |
void *sqlite3Fts3HashFind(const Fts3Hash*, const void *pKey, int nKey); |
| 77 |
void sqlite3Fts3HashClear(Fts3Hash*); |
| 78 |
Fts3HashElem *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_ */ |