Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

wvhashtable.h

Go to the documentation of this file.
00001 /*
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  * 
00005  * Small, efficient, type-safe hash table (also known as "dictionary")
00006  * class.  These are typically used to store a reasonably large number
00007  * of objects (in no particular order) and find them quickly when needed.
00008  * 
00009  * Two semi-distinct types of hash tables are supported:  tables and
00010  * dictionaries.
00011  * 
00012  * TABLE EXAMPLE:
00013  *       DeclareWvTable(WvString);
00014  *       int main()
00015  *       {
00016  *           WvString s("foo"), s2("blue"), s3("foo");
00017  *           WvStringTable t(10);  // suggested size: 10 elements
00018  *           t.add(&s); t.add(&s2);
00019  *           printf("%s %s\n", t[s]->str, t[s3]->str); // prints "foo" "foo"
00020  *           ...
00021  *       }
00022  * Here, the WvStrings "foo" and "blue" are stored in the table, and then
00023  * "foo" is looked up twice (both table searches return &s).  The suggested
00024  * table size is given as 10 elements; this is only a suggestion, and
00025  * places no limit on the number of elements (though if you have many more
00026  * than this, it will get slower).
00027  * 
00028  * To match an element, the WvString operator== function is used.  That
00029  * means this particular example is rather foolish since if you already
00030  * have the search string, you do not need to find it in the table.  Objects
00031  * with more specific == operators might have more luck.
00032  * 
00033  * 
00034  * DICTIONARY EXAMPLE:
00035  *       class IntStr
00036  *       {
00037  *           int *key;
00038  *           WvString data;
00039  *       }
00040  *       DeclareWvDict(IntStr, int, key[0]);
00041  * 
00042  *       ...
00043  *       IntStrDict d(100);
00044  * 
00045  * Here, we are creating a dictionary that stores strings indexed by
00046  * integers.  d[5] might return the address of IntStr number 5, which
00047  * in turn contains WvString number 5.  When matching elements in this case,
00048  * a comparison is only done on key[0] of the two elements; thus, it is
00049  * not the operator== of IntStr that is important, but rather the operator==
00050  * for int.  (In this case, the operator== of int is predefined.)
00051  * 
00052  * The only reason *key is declared as a pointer in this example is to
00053  * demonstrate how to use pointer-based keys with our syntax.  In this case
00054  * it would certainly make more sense to use "int key;" and
00055  * DeclareWvDict(IntStr, key).  Note though, that "int *key;" and
00056  * DeclareWvDict(IntStr, key) is almost certainly not what you want, since
00057  * it would compare the POINTERS, not their values.
00058  * 
00059  * 
00060  * NOTES:
00061  *    - This class acts a lot like the WvList class in wvlinklist.h,
00062  *        possibly because it is based on an array of WvLists.  You
00063  *        should see wvlinklist.h for many interesting usage notes.
00064  *        (We support iterators in exactly the same way that WvLists do.)
00065  * 
00066  */
00067 #ifndef __WVHASHTABLE_H
00068 #define __WVHASHTABLE_H
00069 
00070 #include "wvlinklist.h"
00071 
00072 // no need to #include wvstring.h just for this
00073 class WvString;
00074 
00075 // predefined hashing functions (note: string hashes are case-insensitive)
00076 unsigned WvHash(const WvString &s);
00077 unsigned WvHash(const char *s);
00078 unsigned WvHash(const int &i);
00079 
00080 // this base class has some non-inlined functions that work for all
00081 // data types.
00082 class WvHashTableBase
00083 {
00084 protected:
00085     typedef bool Comparator(const void *, const void *);
00086     
00087     WvHashTableBase(unsigned _numslots);
00088     WvHashTableBase(const WvHashTableBase &t); // copy constructor - not defined anywhere!
00089     WvHashTableBase& operator= (const WvHashTableBase &t);
00090     void setup()
00091         { /* default: do nothing */ }
00092     void shutdown()
00093         { /* default: do nothing */ }
00094     WvLink *prevlink(WvListBase *slots, const void *data,
00095                      unsigned hash, Comparator *comp);
00096     void *genfind(WvListBase *slots, const void *data,
00097                   unsigned hash, Comparator *comp);
00098 public:
00099     unsigned numslots;
00100     WvListBase *slots;
00101     
00102     size_t count() const;
00103 
00104     // base class for the auto-declared hash table iterators
00105     class IterBase
00106     {
00107     public:
00108         WvHashTableBase *tbl;
00109         unsigned tblindex;
00110         WvLink *link;
00111         
00112         IterBase(WvHashTableBase &_tbl)
00113             { tbl = &_tbl; }
00114         void rewind()
00115             { tblindex = 0; link = &tbl->slots[0].head; }
00116         WvLink *next();
00117         WvLink *cur() const
00118             { return link; }
00119     };
00120 };
00121 
00122 
00123 // this used to be ugly, but now it's just kind of weird and hacky.
00124 
00125 typedef const void *WvFieldPointer(const void *obj);
00126 
00127 template <class _type_, class _ftype_, WvFieldPointer *fptr>
00128 class WvHashTable : public WvHashTableBase
00129 {
00130 protected:
00131     //static const _ftype_ *fptr(const _type_ *obj)
00132     //    { return (const _ftype_*)(((const char *)obj) + _fieldofs_); }
00133     unsigned hash(const _type_ *data)
00134         { return WvHash(*(const _ftype_ *)fptr(data)); }
00135     static bool comparator(const void *key, const void *elem)
00136         { return *(_ftype_ *)key == *(const _ftype_ *)fptr((const _type_ *)elem); }
00137 
00138 public:
00139     WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
00140         { slots = new WvList<_type_>[numslots]; setup(); }
00141 
00142     WvList<_type_> *sl()
00143         { return (WvList<_type_> *)slots; }
00144 
00145     ~WvHashTable()
00146         { shutdown(); delete[] sl(); }
00147 
00148     void add(_type_ *data, bool auto_free)
00149         { sl()[hash(data) % numslots].append(data, auto_free); }
00150 
00151     _type_ *operator[] (const _ftype_ &key)
00152         { return (_type_ *)genfind(slots, &key, WvHash(key), comparator); }
00153 
00154     void remove(const _type_ *data)
00155     {
00156         unsigned h = hash(data);
00157         WvLink *l = prevlink(slots, fptr(data), h, comparator);
00158         if (l && l->next) sl()[h % numslots].unlink_after(l);
00159     }
00160 
00161     void zap()
00162     {
00163         delete[] sl();
00164         slots = new WvList<_type_>[numslots];
00165     }
00166 
00167     class Iter : public WvHashTableBase::IterBase
00168     {
00169     public:
00170         Iter(WvHashTable &_tbl) : IterBase(_tbl)
00171             { }
00172         _type_ *ptr() const
00173             { return (_type_ *)link->data; }
00174         WvIterStuff(_type_);
00175     };
00176 
00177     typedef class WvSorter<_type_,WvHashTableBase,WvHashTableBase::IterBase>
00178         Sorter;
00179 };
00180 
00181 
00182 // the _hack container class is necessary because if DeclareWvDict is run
00183 // inside a class definition, the typedef can't access this function for
00184 // some reason (g++ bug or c++ bug?  The world is left wondering...)
00185 //
00186 // Of course, the typedef _itself_ wouldn't be necessary if I could make the
00187 // new class's constructor call the template's constructor by name.  I'm
00188 // almost _certain_ that's a g++ bug.
00189 //
00190 #define __WvDict_base(_classname_, _type_, _ftype_, _field_, _extra_)   \
00191     struct _classname_##_hack                                           \
00192     {                                                                   \
00193         static inline const void *_classname_##_fptr_(const void *obj)  \
00194             { return &((*(const _type_ *)obj) _field_); }               \
00195     };                                                                  \
00196                                                                         \
00197     typedef WvHashTable<_type_, _ftype_,                                \
00198                         _classname_##_hack::_classname_##_fptr_>        \
00199                         _classname_##Base;                              \
00200                                                                         \
00201     class _classname_ : public _classname_##Base                        \
00202     {                                                                   \
00203     public:                                                             \
00204         _classname_(unsigned _numslots) : _classname_##Base(_numslots)  \
00205                 { }                                                     \
00206         void add(_type_ *data, bool auto_free)                          \
00207                 { _classname_##Base::add(data, auto_free); };           \
00208         _extra_                                                         \
00209     };
00210 
00211 
00212 #define DeclareWvDict3(_type_, _newname_, _ftype_, _field_, _extra_)    \
00213         __WvDict_base(_newname_, _type_, _ftype_, . _field_, _extra_)
00214 #define DeclareWvDict2(_type_, _ftype_, _field_, _extra_)               \
00215         DeclareWvDict3(_type_, _type_##Dict, _ftype_, _field_, _extra_)
00216 #define DeclareWvDict(_type_, _ftype_, _field_)                         \
00217         DeclareWvDict2(_type_, _ftype_, _field_, )
00218 
00219 #define DeclareWvTable3(_type_, _newname_, _extra_)                     \
00220         __WvDict_base(_newname_, _type_, _type_, , _extra_)
00221 #define DeclareWvTable2(_type_, _extra_)                                \
00222         DeclareWvTable3(_type_, _type_##Table, _extra_)
00223 #define DeclareWvTable(_type_) DeclareWvTable2(_type_, )
00224 
00225 
00226 #endif // __WVHASHTABLE_H

Generated on Sun Aug 25 12:42:08 2002 for WvStreams by doxygen1.2.15