Return to hash.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src

Annotation of embedaddon/sqlite3/src/hash.h, revision 1.1

1.1     ! misho       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: #ifndef _SQLITE_HASH_H_
        !            16: #define _SQLITE_HASH_H_
        !            17: 
        !            18: /* Forward declarations of structures. */
        !            19: typedef struct Hash Hash;
        !            20: typedef 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 -- client
        !            24: ** code should not attempt to access or modify the fields of this structure
        !            25: ** directly.  Change this structure only by using the routines below.
        !            26: ** However, some of the "procedures" and "functions" for modifying and
        !            27: ** accessing this structure are really macros, so we can't really make
        !            28: ** 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 in
        !            34: ** the global doubly-linked list.  The contents of the bucket are the
        !            35: ** 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 done
        !            38: ** by a linear search of the global list.  For small tables, the 
        !            39: ** Hash.ht table is never allocated because if there are few elements
        !            40: ** in the table, it is faster to do a linear search than to manage
        !            41: ** the hash table.
        !            42: */
        !            43: struct 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:     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 really
        !            57: ** be opaque because it is used by macros.
        !            58: */
        !            59: struct HashElem {
        !            60:   HashElem *next, *prev;       /* Next and previous elements in the table */
        !            61:   void *data;                  /* Data associated with this element */
        !            62:   const char *pKey; int nKey;  /* Key associated with this element */
        !            63: };
        !            64: 
        !            65: /*
        !            66: ** Access routines.  To delete, insert a NULL pointer.
        !            67: */
        !            68: void sqlite3HashInit(Hash*);
        !            69: void *sqlite3HashInsert(Hash*, const char *pKey, int nKey, void *pData);
        !            70: void *sqlite3HashFind(const Hash*, const char *pKey, int nKey);
        !            71: void sqlite3HashClear(Hash*);
        !            72: 
        !            73: /*
        !            74: ** Macros for looping over all elements of a hash table.  The idiom is
        !            75: ** like this:
        !            76: **
        !            77: **   Hash h;
        !            78: **   HashElem *p;
        !            79: **   ...
        !            80: **   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){
        !            81: **     SomeStructure *pData = sqliteHashData(p);
        !            82: **     // do something with pData
        !            83: **   }
        !            84: */
        !            85: #define sqliteHashFirst(H)  ((H)->first)
        !            86: #define sqliteHashNext(E)   ((E)->next)
        !            87: #define sqliteHashData(E)   ((E)->data)
        !            88: /* #define sqliteHashKey(E)    ((E)->pKey) // NOT USED */
        !            89: /* #define sqliteHashKeysize(E) ((E)->nKey)  // NOT USED */
        !            90: 
        !            91: /*
        !            92: ** Number of entries in a hash table
        !            93: */
        !            94: /* #define sqliteHashCount(H)  ((H)->count) // NOT USED */
        !            95: 
        !            96: #endif /* _SQLITE_HASH_H_ */