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_ */