xref: /illumos-gate/usr/src/lib/libsqlite/src/hash.h (revision 1da57d55)
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.6 2004/01/08 02:17:33 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   char keyClass;          /* SQLITE_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   int htsize;             /* Number of buckets in the hash table */
38   struct _ht {            /* the hash table */
39     int count;               /* Number of entries with this hash */
40     HashElem *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 HashElem {
51   HashElem *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 4 different modes of operation for a hash table:
58 **
59 **   SQLITE_HASH_INT         nKey is used as the key and pKey is ignored.
60 **
61 **   SQLITE_HASH_POINTER     pKey is used as the key and nKey is ignored.
62 **
63 **   SQLITE_HASH_STRING      pKey points to a string that is nKey bytes long
64 **                           (including the null-terminator, if any).  Case
65 **                           is ignored in comparisons.
66 **
67 **   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long.
68 **                           memcmp() is used to compare keys.
69 **
70 ** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
71 ** if the copyKey parameter to HashInit is 1.
72 */
73 #define SQLITE_HASH_INT       1
74 /* #define SQLITE_HASH_POINTER   2 // NOT USED */
75 #define SQLITE_HASH_STRING    3
76 #define SQLITE_HASH_BINARY    4
77 
78 /*
79 ** Access routines.  To delete, insert a NULL pointer.
80 */
81 void sqliteHashInit(Hash*, int keytype, int copyKey);
82 void *sqliteHashInsert(Hash*, const void *pKey, int nKey, void *pData);
83 void *sqliteHashFind(const Hash*, const void *pKey, int nKey);
84 void sqliteHashClear(Hash*);
85 
86 /*
87 ** Macros for looping over all elements of a hash table.  The idiom is
88 ** like this:
89 **
90 **   Hash h;
91 **   HashElem *p;
92 **   ...
93 **   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){
94 **     SomeStructure *pData = sqliteHashData(p);
95 **     // do something with pData
96 **   }
97 */
98 #define sqliteHashFirst(H)  ((H)->first)
99 #define sqliteHashNext(E)   ((E)->next)
100 #define sqliteHashData(E)   ((E)->data)
101 #define sqliteHashKey(E)    ((E)->pKey)
102 #define sqliteHashKeysize(E) ((E)->nKey)
103 
104 /*
105 ** Number of entries in a hash table
106 */
107 #define sqliteHashCount(H)  ((H)->count)
108 
109 #endif /* _SQLITE_HASH_H_ */
110