hash.h

   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 implementation
  13 ** used in SQLite.
  14 */
  15 #ifndef SQLITE_HASH_H
  16 #define SQLITE_HASH_H
  17
  18 #include <stddef.h>
  19 #include <stdint.h>
  20
  21 #include "system.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, some of the "procedures" and "functions" for modifying and
  32 ** accessing this structure are really macros, so we can not really make
  33 ** this structure opaque.
  34 **
  35 ** All elements of the hash table are on a single doubly-linked list.
  36 ** Hash.first points to the head of this list.
  37 **
  38 ** There are Hash.size buckets.  Each bucket points to a spot in
  39 ** the global doubly-linked list.  The contents of the bucket are the
  40 ** element pointed to plus the next table.count-1 elements in the list.
  41 **
  42 ** Hash.size and Hash.table may be zero.  In that case lookup is done
  43 ** by a linear search of the global list.  For small tables, the
  44 ** Hash.table table is never allocated because if there are few elements
  45 ** in the table, it is faster to do a linear search than to manage
  46 ** the hash table.
  47 */
  48 struct Hash {
  49   uint32_t size;        /* Number of buckets in the hash table */
  50   uint32_t count;       /* Number of entries in this table */
  51   HashElem *first;      /* The first element of the array */
  52   struct HashTable {    /* the hash table */
  53     HashElem *chain;    /* Pointer to first entry with this hash */
  54     uint32_t count;     /* Number of entries with this hash */
  55   } *table;
  56 };
  57
  58 /* Each element in the hash table is an instance of the following
  59 ** structure.  All elements are stored on a single doubly-linked list.
  60 **
  61 ** Again, this structure is intended to be opaque, but it can not really
  62 ** be opaque because it is used by macros.
  63 */
  64 struct HashElem {
  65   HashElem *next, *prev;  /* Next and previous elements in the table */
  66   void *data;             /* Data associated with this element */
  67   const char *keyPtr;     /* Key associated with this element */
  68   uint32_t keySize;       /* Size of the Key associated with this element */
  69   uint32_t keyHash;       /* Hash of the Key associated with this element */
  70 };
  71
  72 /*
  73 ** Access routines.
  74 */
  75 void HashInit(Hash *) NONNULL (1) ACCESS (write_only, 1);
  76 void *HashInsert(Hash *, const void *keyPtr, uint32_t keySize, void *pData)
  77   NONNULL (1, 2, 4) ACCESS (read_only, 2, 3) ACCESS (none, 4);
  78 void *HashRemove(Hash *, const void *keyPtr, uint32_t keySize)
  79   NONNULL (1, 2) ACCESS (read_only, 1) ACCESS (read_only, 2, 3);
  80 void *HashFind(const Hash *, const void *keyPtr, uint32_t keySize)
  81   NONNULL (1, 2) PURE ACCESS (read_only, 2, 3);
  82 void HashClear(Hash *) NONNULL (1);
  83 void HashClearWithDestructor(Hash *, void (*)(void *)) NONNULL (1, 2);
  84
  85 /*
  86 ** Macros for looping over all elements of a hash table.  The idiom is
  87 ** like this:
  88 **
  89 **   Hash h;
  90 **   HashElem *p;
  91 **   ...
  92 **   for(p=HashFirst(&h); p; p=HashNext(p)){
  93 **     SomeStructure *pData = HashData(p);
  94 **     // do something with pData
  95 **   }
  96 */
  97 #define HashFirst(H)   ((H)->first)
  98 #define HashNext(E)    ((E)->next)
  99 #define HashData(E)    ((E)->data)
 100 #define HashKeyPtr(E)  ((E)->keyPtr)
 101 #define HashKeySize(E) ((E)->keySize)
 102
 103 /*
 104 ** Number of entries in a hash table
 105 */
 106 /* #define HashCount(H)  ((H)->count) // NOT USED */
 107
 108 #endif /* SQLITE_HASH_H */