1 2 #pragma ident "%Z%%M% %I% %E% SMI" 3 4 /* 5 ** 2001 September 22 6 ** 7 ** The author disclaims copyright to this source code. In place of 8 ** a legal notice, here is a blessing: 9 ** 10 ** May you do good and not evil. 11 ** May you find forgiveness for yourself and forgive others. 12 ** May you share freely, never taking more than you give. 13 ** 14 ************************************************************************* 15 ** This is the header file for the generic hash-table implemenation 16 ** used in SQLite. 17 ** 18 ** $Id: hash.h,v 1.6 2004/01/08 02:17:33 drh Exp $ 19 */ 20 #ifndef _SQLITE_HASH_H_ 21 #define _SQLITE_HASH_H_ 22 23 /* Forward declarations of structures. */ 24 typedef struct Hash Hash; 25 typedef struct HashElem HashElem; 26 27 /* A complete hash table is an instance of the following structure. 28 ** The internals of this structure are intended to be opaque -- client 29 ** code should not attempt to access or modify the fields of this structure 30 ** directly. Change this structure only by using the routines below. 31 ** However, many of the "procedures" and "functions" for modifying and 32 ** accessing this structure are really macros, so we can't really make 33 ** this structure opaque. 34 */ 35 struct Hash { 36 char keyClass; /* SQLITE_HASH_INT, _POINTER, _STRING, _BINARY */ 37 char copyKey; /* True if copy of key made on insert */ 38 int count; /* Number of entries in this table */ 39 HashElem *first; /* The first element of the array */ 40 int htsize; /* Number of buckets in the hash table */ 41 struct _ht { /* the hash table */ 42 int count; /* Number of entries with this hash */ 43 HashElem *chain; /* Pointer to first entry with this hash */ 44 } *ht; 45 }; 46 47 /* Each element in the hash table is an instance of the following 48 ** structure. All elements are stored on a single doubly-linked list. 49 ** 50 ** Again, this structure is intended to be opaque, but it can't really 51 ** be opaque because it is used by macros. 52 */ 53 struct HashElem { 54 HashElem *next, *prev; /* Next and previous elements in the table */ 55 void *data; /* Data associated with this element */ 56 void *pKey; int nKey; /* Key associated with this element */ 57 }; 58 59 /* 60 ** There are 4 different modes of operation for a hash table: 61 ** 62 ** SQLITE_HASH_INT nKey is used as the key and pKey is ignored. 63 ** 64 ** SQLITE_HASH_POINTER pKey is used as the key and nKey is ignored. 65 ** 66 ** SQLITE_HASH_STRING pKey points to a string that is nKey bytes long 67 ** (including the null-terminator, if any). Case 68 ** is ignored in comparisons. 69 ** 70 ** SQLITE_HASH_BINARY pKey points to binary data nKey bytes long. 71 ** memcmp() is used to compare keys. 72 ** 73 ** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY 74 ** if the copyKey parameter to HashInit is 1. 75 */ 76 #define SQLITE_HASH_INT 1 77 /* #define SQLITE_HASH_POINTER 2 // NOT USED */ 78 #define SQLITE_HASH_STRING 3 79 #define SQLITE_HASH_BINARY 4 80 81 /* 82 ** Access routines. To delete, insert a NULL pointer. 83 */ 84 void sqliteHashInit(Hash*, int keytype, int copyKey); 85 void *sqliteHashInsert(Hash*, const void *pKey, int nKey, void *pData); 86 void *sqliteHashFind(const Hash*, const void *pKey, int nKey); 87 void sqliteHashClear(Hash*); 88 89 /* 90 ** Macros for looping over all elements of a hash table. The idiom is 91 ** like this: 92 ** 93 ** Hash h; 94 ** HashElem *p; 95 ** ... 96 ** for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){ 97 ** SomeStructure *pData = sqliteHashData(p); 98 ** // do something with pData 99 ** } 100 */ 101 #define sqliteHashFirst(H) ((H)->first) 102 #define sqliteHashNext(E) ((E)->next) 103 #define sqliteHashData(E) ((E)->data) 104 #define sqliteHashKey(E) ((E)->pKey) 105 #define sqliteHashKeysize(E) ((E)->nKey) 106 107 /* 108 ** Number of entries in a hash table 109 */ 110 #define sqliteHashCount(H) ((H)->count) 111 112 #endif /* _SQLITE_HASH_H_ */ 113