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. 14 ** 15 ** $Id: hash.h,v 1.12 2008/10/10 17:41:29 drh Exp $ 16 */ 17 #ifndef _SQLITE_HASH_H_ 18 #define _SQLITE_HASH_H_ 19 20 /* Forward declarations of structures. */ 21 typedef struct Hash Hash; 22 typedef 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 */ 32 struct Hash { 33 unsigned int copyKey: 1; /* True if copy of key made on insert */ 34 unsigned int htsize : 31; /* Number of buckets in the hash table */ 35 unsigned int count; /* Number of entries in this table */ 36 HashElem *first; /* The first element of the array */ 37 struct _ht { /* the hash table */ 38 int count; /* Number of entries with this hash */ 39 HashElem *chain; /* Pointer to first entry with this hash */ 40 } *ht; 41 }; 42 43 /* Each element in the hash table is an instance of the following 44 ** structure. All elements are stored on a single doubly-linked list. 45 ** 46 ** Again, this structure is intended to be opaque, but it can't really 47 ** be opaque because it is used by macros. 48 */ 49 struct HashElem { 50 HashElem *next, *prev; /* Next and previous elements in the table */ 51 void *data; /* Data associated with this element */ 52 void *pKey; int nKey; /* Key associated with this element */ 53 }; 54 55 /* 56 ** Access routines. To delete, insert a NULL pointer. 57 */ 58 void sqlite3HashInit(Hash*, int copyKey); 59 void *sqlite3HashInsert(Hash*, const void *pKey, int nKey, void *pData); 60 void *sqlite3HashFind(const Hash*, const void *pKey, int nKey); 61 HashElem *sqlite3HashFindElem(const Hash*, const void *pKey, int nKey); 62 void sqlite3HashClear(Hash*); 63 64 /* 65 ** Macros for looping over all elements of a hash table. The idiom is 66 ** like this: 67 ** 68 ** Hash h; 69 ** HashElem *p; 70 ** ... 71 ** for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){ 72 ** SomeStructure *pData = sqliteHashData(p); 73 ** // do something with pData 74 ** } 75 */ 76 #define sqliteHashFirst(H) ((H)->first) 77 #define sqliteHashNext(E) ((E)->next) 78 #define sqliteHashData(E) ((E)->data) 79 #define sqliteHashKey(E) ((E)->pKey) 80 #define sqliteHashKeysize(E) ((E)->nKey) 81 82 /* 83 ** Number of entries in a hash table 84 */ 85 #define sqliteHashCount(H) ((H)->count) 86 87 #endif /* _SQLITE_HASH_H_ */ 88