AryaWu/sqlite

1/*2** 2001 September 223**4** The author disclaims copyright to this source code.  In place of5** 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 implementation13** used in SQLite.14*/15#ifndef SQLITE_HASH_H16#define SQLITE_HASH_H17 18/* Forward declarations of structures. */19typedef struct Hash Hash;20typedef struct HashElem HashElem;21 22/* A complete hash table is an instance of the following structure.23** The internals of this structure are intended to be opaque -- client24** code should not attempt to access or modify the fields of this structure25** directly.  Change this structure only by using the routines below.26** However, some of the "procedures" and "functions" for modifying and27** accessing this structure are really macros, so we can't really make28** this structure opaque.29**30** All elements of the hash table are on a single doubly-linked list.31** Hash.first points to the head of this list.32**33** There are Hash.htsize buckets.  Each bucket points to a spot in34** the global doubly-linked list.  The contents of the bucket are the35** element pointed to plus the next _ht.count-1 elements in the list.36**37** Hash.htsize and Hash.ht may be zero.  In that case lookup is done38** by a linear search of the global list.  For small tables, the 39** Hash.ht table is never allocated because if there are few elements40** in the table, it is faster to do a linear search than to manage41** the hash table.42*/43struct Hash {44  unsigned int htsize;      /* Number of buckets in the hash table */45  unsigned int count;       /* Number of entries in this table */46  HashElem *first;          /* The first element of the array */47  struct _ht {              /* the hash table */48    unsigned int count;        /* Number of entries with this hash */49    HashElem *chain;           /* Pointer to first entry with this hash */50  } *ht;51};52 53/* Each element in the hash table is an instance of the following 54** structure.  All elements are stored on a single doubly-linked list.55**56** Again, this structure is intended to be opaque, but it can't really57** be opaque because it is used by macros.58*/59struct HashElem {60  HashElem *next, *prev;       /* Next and previous elements in the table */61  void *data;                  /* Data associated with this element */62  const char *pKey;            /* Key associated with this element */63  unsigned int h;              /* hash for pKey */64};65 66/*67** Access routines.  To delete, insert a NULL pointer.68*/69void sqlite3HashInit(Hash*);70void *sqlite3HashInsert(Hash*, const char *pKey, void *pData);71void *sqlite3HashFind(const Hash*, const char *pKey);72void sqlite3HashClear(Hash*);73 74/*75** Macros for looping over all elements of a hash table.  The idiom is76** like this:77**78**   Hash h;79**   HashElem *p;80**   ...81**   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){82**     SomeStructure *pData = sqliteHashData(p);83**     // do something with pData84**   }85*/86#define sqliteHashFirst(H)  ((H)->first)87#define sqliteHashNext(E)   ((E)->next)88#define sqliteHashData(E)   ((E)->data)89/* #define sqliteHashKey(E)    ((E)->pKey) // NOT USED */90/* #define sqliteHashKeysize(E) ((E)->nKey)  // NOT USED */91 92/*93** Number of entries in a hash table94*/95#define sqliteHashCount(H)  ((H)->count)96 97#endif /* SQLITE_HASH_H */98