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 _HASH_H_ 18#define _HASH_H_ 19 20/* Forward declarations of structures. */ 21typedef struct Hash Hash; 22typedef struct HashElem HashElem; 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 Hash { 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 HashElem *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 _ht { /* the hash table */ 41 int count; /* Number of entries with this hash */ 42 HashElem *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 HashElem { 53 HashElem *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 4 different modes of operation for a hash table: 60** 61** HASH_INT nKey is used as the key and pKey is ignored. 62** 63** HASH_POINTER pKey is used as the key and nKey is ignored. 64** 65** HASH_STRING pKey points to a string that is nKey bytes long 66** (including the null-terminator, if any). Case 67** is respected in comparisons. 68** 69** HASH_BINARY pKey points to binary data nKey bytes long. 70** memcmp() is used to compare keys. 71** 72** A copy of the key is made for HASH_STRING and HASH_BINARY 73** if the copyKey parameter to HashInit is 1. 74*/ 75/* #define HASH_INT 1 // NOT USED */ 76/* #define HASH_POINTER 2 // NOT USED */ 77#define HASH_STRING 3 78#define HASH_BINARY 4 79 80/* 81** Access routines. To delete, insert a NULL pointer. 82*/ 83void HashInit(Hash*, int keytype, int copyKey); 84void *HashInsert(Hash*, const void *pKey, int nKey, void *pData); 85void *HashFind(const Hash*, const void *pKey, int nKey); 86void HashClear(Hash*); 87 88/* 89** Macros for looping over all elements of a hash table. The idiom is 90** like this: 91** 92** Hash h; 93** HashElem *p; 94** ... 95** for(p=HashFirst(&h); p; p=HashNext(p)){ 96** SomeStructure *pData = HashData(p); 97** // do something with pData 98** } 99*/ 100#define HashFirst(H) ((H)->first) 101#define HashNext(E) ((E)->next) 102#define HashData(E) ((E)->data) 103#define HashKey(E) ((E)->pKey) 104#define HashKeysize(E) ((E)->nKey) 105 106/* 107** Number of entries in a hash table 108*/ 109#define HashCount(H) ((H)->count) 110 111#endif /* _HASH_H_ */ 112