Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

wvhashtable.h

Go to the documentation of this file.
00001 /* -*- Mode: C++ -*-
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  *
00005  * A hash table container.
00006  */
00007 #ifndef __WVHASHTABLE_H
00008 #define __WVHASHTABLE_H
00009 
00010 #include "wvlinklist.h"
00011 #include "wvstring.h"
00012 
00013 // predefined hashing functions (note: string hashes are case-insensitive)
00014 unsigned WvHash(WvStringParm s);
00015 unsigned WvHash(const char *s);
00016 unsigned WvHash(const int &i);
00017 
00018 /**
00019  * A small, efficient, type-safe hash table (also known as dictionary)
00020  * container class.
00021  * 
00022  * These are typically used to store a reasonably large number
00023  * of objects in no particular order and find them quickly when needed.
00024  * 
00025  * Two semi-distinct types of hash tables are supported:  tables and
00026  * dictionaries.
00027  * 
00028  * TABLE EXAMPLE:
00029  * 
00030  *   DeclareWvTable(WvString);
00031  *   int main()
00032  *   {
00033  *       WvString s("foo"), s2("blue"), s3("foo");
00034  *       WvStringTable t(10);  // suggested size: 10 elements
00035  *       t.add(&s); t.add(&s2);
00036  *       printf("%s %s\n", t[s]->str, t[s3]->str); // prints "foo" "foo"
00037  *   }
00038  * 
00039  * 
00040  * Here, the WvStrings "foo" and "blue" are stored in the table, and then
00041  * "foo" is looked up twice.  Both table searches return &s.
00042  * The suggested table size of 10 elements places no upper bound on
00043  * the maximum number of elements, but optimizes the hash table for
00044  * holding roughly 10 elements.
00045  * 
00046  * To match an element, the WvString operator== function is used.  That
00047  * means this particular example is rather contrived since if you already
00048  * have the search string, you do not need to find it in the table.
00049  * Objects with more specific operator== might have more luck.
00050  * 
00051  * DICTIONARY EXAMPLE:
00052  * 
00053  *   class IntStr
00054  *   {
00055  *       int *key;
00056  *       WvString data;
00057  *   }
00058  *   DeclareWvDict(IntStr, int, key[0]);
00059  *   IntStrDict d(100);
00060  * 
00061  * 
00062  * Here, we are creating a dictionary that stores strings indexed by
00063  * integers.  d[5] might return the address of IntStr number 5, which
00064  * in turn contains WvString number 5.  When matching elements in this case,
00065  * a comparison is only done on key[0] of the two elements; thus, it is
00066  * not the operator== of IntStr that is important, but rather the operator==
00067  * for int.  (In this case, the operator== of int is predefined.)
00068  * 
00069  * The only reason *key is declared as a pointer in this example is to
00070  * demonstrate how to use pointer-based keys with our syntax.  In this case
00071  * it would certainly make more sense to use int key; and
00072  * DeclareWvDict(IntStr, key).  Note though, that int *key; and
00073  * DeclareWvDict(IntStr, key) is almost certainly not what you want, since
00074  * it would compare the POINTERS, not their values.
00075  * 
00076  * The interface of this class resembles that of WvList by design.
00077  * In particular, we support iterators in a similar way.
00078  * 
00079  * @see WvList<T>
00080  */
00081 
00082 /**
00083  * The untyped base class of WvHashTable<T>.
00084  * 
00085  * Putting common code in here allows us to prevent it from being
00086  * replicated by each template instantiation of WvHashTable<T>.
00087  * 
00088  */
00089 
00090 class WvHashTableBase
00091 {
00092     // Copy constructor - not defined anywhere!
00093     WvHashTableBase(const WvHashTableBase &t); 
00094 protected:
00095     WvHashTableBase(unsigned _numslots);
00096     virtual ~WvHashTableBase() {}; 
00097     WvHashTableBase& operator= (const WvHashTableBase &t);
00098     void setup()
00099         { /* default: do nothing */ }
00100     void shutdown()
00101         { /* default: do nothing */ }
00102     WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const;
00103     void *genfind(WvListBase *slots, const void *data, unsigned hash) const;
00104 
00105     virtual bool compare(const void *key, const void *elem) const = 0;
00106 public:
00107     unsigned numslots;
00108     WvListBase *wvslots;
00109 
00110     /**
00111      * Returns the number of elements in the hash table.
00112      * Returns: the number of elements
00113      */
00114     size_t count() const;
00115 
00116     /**
00117      * Returns true if the hash table is empty.
00118      * Returns: true if empty
00119      */
00120     bool isempty() const;
00121 
00122     // base class for the auto-declared hash table iterators
00123     class IterBase
00124     {
00125     public:
00126         WvHashTableBase *tbl;
00127         unsigned tblindex;
00128         WvLink *link;
00129         
00130         IterBase(WvHashTableBase &_tbl) : tbl(& _tbl)
00131             { }
00132         IterBase(const IterBase &other) : tbl(other.tbl),
00133             tblindex(other.tblindex), link(other.link)
00134             { }
00135         void rewind()
00136             { tblindex = 0; link = &tbl->wvslots[0].head; }
00137         WvLink *next();
00138         WvLink *cur() const
00139             { return link; }
00140         void *vptr() const
00141             { return link->data; }
00142     };
00143 };
00144 
00145 
00146 // Default comparison function used by WvHashTable
00147 template <class K>
00148 struct OpEqComp
00149 {
00150     static bool compare(const K *key1, const K *key2)
00151         { return *key1 == *key2; }
00152 };
00153 
00154 
00155 // Case-insensitive comparison function for WvHastTable
00156 template <class K>
00157 struct StrCaseComp
00158 {
00159     static bool compare(const K *key1, const K *key2)
00160         { return strcasecmp(*key1, *key2) == 0; }
00161 };
00162 
00163 
00164 template <
00165     class T,                                            // element type
00166     class K,                                            // key type
00167     class Accessor,                                     // element to key
00168     template <class> class Comparator = OpEqComp        // comparison func
00169 >
00170 class WvHashTable : public WvHashTableBase
00171 {
00172     // copy constructor: not defined anywhere!
00173     WvHashTable(const WvHashTable &h);
00174 protected:
00175     typedef Comparator<K> MyComparator; 
00176 
00177     unsigned hash(const T *data)
00178         { return WvHash(*Accessor::get_key(data)); }
00179 
00180     virtual bool compare(const void *key, const void *elem) const
00181         { return MyComparator::compare((const K *)key,
00182                 Accessor::get_key((const T *)elem)); }
00183 
00184 public:
00185     /**
00186      * Creates a hash table.
00187      *
00188      * "numslots" is the suggested number of slots
00189      */
00190     WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
00191         { wvslots = new WvList<T>[numslots]; setup(); }
00192 
00193     WvList<T> *sl()
00194         { return (WvList<T> *)wvslots; }
00195 
00196     virtual ~WvHashTable()
00197         { shutdown(); delete[] sl(); }
00198 
00199     void add(T *data, bool auto_free)
00200         { sl()[hash(data) % numslots].append(data, auto_free); }
00201 
00202     WvLink *getlink(const K &key)
00203         { return prevlink(wvslots, &key, WvHash(key))->next; }
00204 
00205     T *operator[] (const K &key) const
00206         { return (T *)genfind(wvslots, &key, WvHash(key)); }
00207 
00208     void remove(const T *data)
00209     {
00210         unsigned h = hash(data);
00211         WvLink *l = prevlink(wvslots, Accessor::get_key(data), h);
00212         if (l && l->next) sl()[h % numslots].unlink_after(l);
00213     }
00214 
00215     void zap()
00216     {
00217         delete[] sl();
00218         wvslots = new WvList<T>[numslots];
00219     }
00220 
00221     class Iter : public WvHashTableBase::IterBase
00222     {
00223     public:
00224         Iter(WvHashTable &_tbl) : IterBase(_tbl)
00225             { }
00226         Iter(const Iter &other) : IterBase(other)
00227             { }
00228         T *ptr() const
00229             { return (T *)link->data; }
00230         WvIterStuff(T);
00231     };
00232 
00233     typedef class WvSorter<T, WvHashTableBase, WvHashTableBase::IterBase>
00234         Sorter;
00235 };
00236 
00237 
00238 // ******************************************
00239 // WvDict and WvTable
00240 
00241 
00242 #define DeclareWvDict2(_classname_,  _type_, _ftype_, _field_)          \
00243         __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_)
00244 
00245 #define DeclareWvDict(_type_, _ftype_, _field_)                         \
00246         DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_)
00247 
00248 #define DeclareWvTable2(_classname_, _type_)                            \
00249         __WvDict_base(_classname_, _type_, _type_, obj)
00250 
00251 #define DeclareWvTable(_type_)                                          \
00252         DeclareWvTable2(_type_##Table, _type_)
00253 
00254 
00255 #define __WvDict_base(_classname_, _type_, _ftype_, _field_)            \
00256     template <class T, class K>                                         \
00257     struct _classname_##Accessor                                        \
00258     {                                                                   \
00259         static const K *get_key(const T *obj)                    \
00260             { return _field_; }                                         \
00261     };                                                                  \
00262                                                                         \
00263     typedef WvHashTable<_type_, _ftype_,                                \
00264              _classname_##Accessor<_type_, _ftype_> > _classname_
00265 
00266 
00267 
00268 // ******************************************
00269 // WvMap
00270 
00271 // *****************************
00272 // WvPair
00273 
00274 // Type specification to facilitate auto_free
00275 // Object type - ignores auto_free
00276 template<typename TKey, typename _TData>
00277 class WvMapPair
00278 {
00279     typedef _TData TData;
00280 public:
00281     TKey key;
00282     TData data;
00283     WvMapPair(const TKey &_key, const TData &_data, bool _auto_free)
00284         : key(_key), data(_data) { };
00285 };
00286 
00287 
00288 // Pointer type
00289 template<typename TKey, typename _TData>
00290 class WvMapPair<TKey, _TData*>
00291 {
00292     typedef _TData* TData;
00293 public:
00294     TKey key;
00295     TData data;
00296     WvMapPair(const TKey &_key, const TData &_data, bool _auto_free)
00297         : key(_key), data(_data), auto_free(_auto_free) { };
00298     virtual ~WvMapPair()
00299         { if (auto_free) delete data; };
00300 protected:
00301     bool auto_free;
00302 };
00303 
00304 
00305 // *****************************
00306 // Main map template
00307 //
00308 // Since operator[] returns a reference you should always check
00309 //      if the element exists() before using it.
00310 // Alternatively, use find(), to get a pointer to the data type,
00311 //      which will be null if the element does not exist.
00312 
00313 template
00314 <
00315     typename TKey,
00316     typename TData,
00317     template <class> class Comparator = OpEqComp,
00318     // Warning: Funny looking syntax follows!
00319     // If we decide that WvScatterHash is the One True Hash,
00320     //      just get rid of this part
00321     template
00322     <
00323         class,
00324         class,
00325         class,
00326         template <class> class
00327     > class BackendHash = WvHashTable
00328 >
00329 class WvMap : public BackendHash<WvMapPair<TKey, TData>, TKey,
00330         WvMap<TKey, TData, Comparator, BackendHash>, Comparator>
00331 {
00332 protected: 
00333     typedef WvMapPair<TKey, TData> MyPair;
00334     typedef WvMap<TKey, TData, Comparator, BackendHash> MyMap;
00335     typedef BackendHash<MyPair, TKey, MyMap, Comparator> MyHashTable;
00336 
00337     // We need this last_accessed thing to make sure exists()/operator[]
00338     //      does not cost us two hash lookups
00339     mutable MyPair* last_accessed;
00340     MyPair* find_helper(const TKey &key) const
00341     {
00342         if (last_accessed &&
00343                 Comparator<TKey>::compare(&last_accessed->key, &key))
00344             return last_accessed;
00345         return last_accessed = MyHashTable::operator[](key);
00346     }
00347     
00348     // copy constructor: not defined anywhere!
00349     WvMap(const WvMap &m);
00350 
00351 public:
00352     // accessor method for WvHashTable to use
00353     static const TKey *get_key(const MyPair *obj)
00354         { return &obj->key; }
00355 
00356     WvMap(int s) : MyHashTable(s), last_accessed(NULL)  { };
00357     TData *find(const TKey &key) const
00358     {
00359         MyPair* p = find_helper(key);
00360         return p ? &p->data : (TData*)NULL;
00361     }
00362     TData &operator[](const TKey &key) const
00363     {
00364         MyPair* p = find_helper(key);
00365         assert(p && "WvMap: operator[] called with a non-existent key");
00366         return p->data;
00367     }
00368     bool exists(const TKey &key) const
00369         { return find_helper(key); }
00370     void set(const TKey &key, const TData &data, bool auto_free = false)
00371     {
00372         if (find_helper(key))
00373             remove(key);
00374         add(key, data, auto_free);
00375     }
00376     void add(const TKey &key, const TData &data, bool auto_free = false)
00377         { MyHashTable::add(new MyPair(key, data, auto_free), true); }
00378     void remove(const TKey &key)
00379     {
00380         last_accessed = NULL;
00381         MyHashTable::remove(MyHashTable::operator[](key));
00382     } 
00383     typedef typename MyHashTable::Iter Iter;
00384 }; 
00385 
00386 
00387 #endif // __WVHASHTABLE_H

Generated on Sat Mar 13 14:55:42 2004 for WvStreams by doxygen 1.3.6-20040222