Back to index

lightning-sunbird  0.9+nobinonly
hash.h
Go to the documentation of this file.
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.9 2006/02/14 10:48:39 danielk1977 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   void *(*xMalloc)(int);  /* malloc() function to use */
00038   void (*xFree)(void *);  /* free() function to use */
00039   int htsize;             /* Number of buckets in the hash table */
00040   struct _ht {            /* the hash table */
00041     int count;               /* Number of entries with this hash */
00042     HashElem *chain;         /* Pointer to first entry with this hash */
00043   } *ht;
00044 };
00045 
00046 /* Each element in the hash table is an instance of the following 
00047 ** structure.  All elements are stored on a single doubly-linked list.
00048 **
00049 ** Again, this structure is intended to be opaque, but it can't really
00050 ** be opaque because it is used by macros.
00051 */
00052 struct HashElem {
00053   HashElem *next, *prev;   /* Next and previous elements in the table */
00054   void *data;              /* Data associated with this element */
00055   void *pKey; int nKey;    /* Key associated with this element */
00056 };
00057 
00058 /*
00059 ** There are 4 different modes of operation for a hash table:
00060 **
00061 **   SQLITE_HASH_INT         nKey is used as the key and pKey is ignored.
00062 **
00063 **   SQLITE_HASH_POINTER     pKey is used as the key and nKey is ignored.
00064 **
00065 **   SQLITE_HASH_STRING      pKey points to a string that is nKey bytes long
00066 **                           (including the null-terminator, if any).  Case
00067 **                           is ignored in comparisons.
00068 **
00069 **   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
00070 **                           memcmp() is used to compare keys.
00071 **
00072 ** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
00073 ** if the copyKey parameter to HashInit is 1.  
00074 */
00075 /* #define SQLITE_HASH_INT       1 // NOT USED */
00076 /* #define SQLITE_HASH_POINTER   2 // NOT USED */
00077 #define SQLITE_HASH_STRING    3
00078 #define SQLITE_HASH_BINARY    4
00079 
00080 /*
00081 ** Access routines.  To delete, insert a NULL pointer.
00082 */
00083 void sqlite3HashInit(Hash*, int keytype, int copyKey);
00084 void *sqlite3HashInsert(Hash*, const void *pKey, int nKey, void *pData);
00085 void *sqlite3HashFind(const Hash*, const void *pKey, int nKey);
00086 void sqlite3HashClear(Hash*);
00087 
00088 /*
00089 ** Macros for looping over all elements of a hash table.  The idiom is
00090 ** like this:
00091 **
00092 **   Hash h;
00093 **   HashElem *p;
00094 **   ...
00095 **   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){
00096 **     SomeStructure *pData = sqliteHashData(p);
00097 **     // do something with pData
00098 **   }
00099 */
00100 #define sqliteHashFirst(H)  ((H)->first)
00101 #define sqliteHashNext(E)   ((E)->next)
00102 #define sqliteHashData(E)   ((E)->data)
00103 #define sqliteHashKey(E)    ((E)->pKey)
00104 #define sqliteHashKeysize(E) ((E)->nKey)
00105 
00106 /*
00107 ** Number of entries in a hash table
00108 */
00109 #define sqliteHashCount(H)  ((H)->count)
00110 
00111 #endif /* _SQLITE_HASH_H_ */