Main Page | Directories | File List

hash.h

00001 /*
00002 ** 2001 September 22
00003 **
00004 ** The author disclaims copyright to this source code.  In place of
00005 ** a legal notice, here is a blessing:
00006 **
00007 **    May you do good and not evil.
00008 **    May you find forgiveness for yourself and forgive others.
00009 **    May you share freely, never taking more than you give.
00010 **
00011 *************************************************************************
00012 ** This is the header file for the generic hash-table implemenation
00013 ** used in SQLite.
00014 **
00015 ** $Id: hash.h,v 1.6 2004/01/08 02:17:33 drh Exp $
00016 */
00017 #ifndef _SQLITE_HASH_H_
00018 #define _SQLITE_HASH_H_
00019 
00020 /* Forward declarations of structures. */
00021 typedef struct Hash Hash;
00022 typedef struct HashElem HashElem;
00023 
00024 /* A complete hash table is an instance of the following structure.
00025 ** The internals of this structure are intended to be opaque -- client
00026 ** code should not attempt to access or modify the fields of this structure
00027 ** directly.  Change this structure only by using the routines below.
00028 ** However, many of the "procedures" and "functions" for modifying and
00029 ** accessing this structure are really macros, so we can't really make
00030 ** this structure opaque.
00031 */
00032 struct Hash {
00033   char keyClass;          /* SQLITE_HASH_INT, _POINTER, _STRING, _BINARY */
00034   char copyKey;           /* True if copy of key made on insert */
00035   int count;              /* Number of entries in this table */
00036   HashElem *first;        /* The first element of the array */
00037   int htsize;             /* Number of buckets in the hash table */
00038   struct _ht {            /* the hash table */
00039     int count;               /* Number of entries with this hash */
00040     HashElem *chain;         /* Pointer to first entry with this hash */
00041   } *ht;
00042 };
00043 
00044 /* Each element in the hash table is an instance of the following 
00045 ** structure.  All elements are stored on a single doubly-linked list.
00046 **
00047 ** Again, this structure is intended to be opaque, but it can't really
00048 ** be opaque because it is used by macros.
00049 */
00050 struct HashElem {
00051   HashElem *next, *prev;   /* Next and previous elements in the table */
00052   void *data;              /* Data associated with this element */
00053   void *pKey; int nKey;    /* Key associated with this element */
00054 };
00055 
00056 /*
00057 ** There are 4 different modes of operation for a hash table:
00058 **
00059 **   SQLITE_HASH_INT         nKey is used as the key and pKey is ignored.
00060 **
00061 **   SQLITE_HASH_POINTER     pKey is used as the key and nKey is ignored.
00062 **
00063 **   SQLITE_HASH_STRING      pKey points to a string that is nKey bytes long
00064 **                           (including the null-terminator, if any).  Case
00065 **                           is ignored in comparisons.
00066 **
00067 **   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
00068 **                           memcmp() is used to compare keys.
00069 **
00070 ** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
00071 ** if the copyKey parameter to HashInit is 1.  
00072 */
00073 #define SQLITE_HASH_INT       1
00074 /* #define SQLITE_HASH_POINTER   2 // NOT USED */
00075 #define SQLITE_HASH_STRING    3
00076 #define SQLITE_HASH_BINARY    4
00077 
00078 /*
00079 ** Access routines.  To delete, insert a NULL pointer.
00080 */
00081 void sqliteHashInit(Hash*, int keytype, int copyKey);
00082 void *sqliteHashInsert(Hash*, const void *pKey, int nKey, void *pData);
00083 void *sqliteHashFind(const Hash*, const void *pKey, int nKey);
00084 void sqliteHashClear(Hash*);
00085 
00086 /*
00087 ** Macros for looping over all elements of a hash table.  The idiom is
00088 ** like this:
00089 **
00090 **   Hash h;
00091 **   HashElem *p;
00092 **   ...
00093 **   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){
00094 **     SomeStructure *pData = sqliteHashData(p);
00095 **     // do something with pData
00096 **   }
00097 */
00098 #define sqliteHashFirst(H)  ((H)->first)
00099 #define sqliteHashNext(E)   ((E)->next)
00100 #define sqliteHashData(E)   ((E)->data)
00101 #define sqliteHashKey(E)    ((E)->pKey)
00102 #define sqliteHashKeysize(E) ((E)->nKey)
00103 
00104 /*
00105 ** Number of entries in a hash table
00106 */
00107 #define sqliteHashCount(H)  ((H)->count)
00108 
00109 #endif /* _SQLITE_HASH_H_ */

Generated on Sun Dec 25 12:29:51 2005 for sqlite 2.8.17 by  doxygen 1.4.2