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