Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members | Related Pages

wvhashtable.h

00001 /* -*- Mode: C++ -*-
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2002 Net Integration Technologies, Inc.
00004  *
00005  * A hash table container.  See also wvscatterhash.h, which is newer, faster,
00006  * and better.
00007  */
00008 #ifndef __WVHASHTABLE_H
00009 #define __WVHASHTABLE_H
00010 
00011 #include "wvhash.h"
00012 #include "wvlinklist.h"
00013 #include <assert.h>
00014 
00087 class WvHashTableBase
00088 {
00089     // Copy constructor - not defined anywhere!
00090     WvHashTableBase(const WvHashTableBase &t); 
00091 protected:
00092     WvHashTableBase(unsigned _numslots);
00093     virtual ~WvHashTableBase() {}; 
00094     WvHashTableBase& operator= (const WvHashTableBase &t);
00095     void setup()
00096         { /* default: do nothing */ }
00097     void shutdown()
00098         { /* default: do nothing */ }
00099     WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const;
00100     void *genfind(WvListBase *slots, const void *data, unsigned hash) const;
00101 
00102     virtual bool compare(const void *key, const void *elem) const = 0;
00103 public:
00104     unsigned numslots;
00105     WvListBase *wvslots;
00106 
00111     size_t count() const;
00112 
00117     bool isempty() const;
00118 
00119     // base class for the auto-declared hash table iterators
00120     class IterBase
00121     {
00122     public:
00123         WvHashTableBase *tbl;
00124         unsigned tblindex;
00125         WvLink *link;
00126         
00127         IterBase(WvHashTableBase &_tbl) : tbl(& _tbl)
00128             { }
00129         IterBase(const IterBase &other) : tbl(other.tbl),
00130             tblindex(other.tblindex), link(other.link)
00131             { }
00132         void rewind()
00133             { tblindex = 0; link = &tbl->wvslots[0].head; }
00134         WvLink *next();
00135         WvLink *cur() const
00136             { return link; }
00137         void *vptr() const
00138             { return link->data; }
00139     };
00140 };
00141 
00142 
00143 template <
00144     class T,                                            // element type
00145     class K,                                            // key type
00146     class Accessor,                                     // element to key
00147     template <class> class Comparator = OpEqComp        // comparison func
00148 >
00149 class WvHashTable : public WvHashTableBase
00150 {
00151     // copy constructor: not defined anywhere!
00152     WvHashTable(const WvHashTable &h);
00153 protected:
00154     typedef Comparator<K> MyComparator; 
00155 
00156     unsigned hash(const T *data)
00157         { return WvHash(*Accessor::get_key(data)); }
00158 
00159     virtual bool compare(const void *key, const void *elem) const
00160         { return MyComparator::compare((const K *)key,
00161                 Accessor::get_key((const T *)elem)); }
00162 
00163 public:
00169     WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
00170         { wvslots = new WvList<T>[numslots]; setup(); }
00171 
00172     WvList<T> *sl()
00173         { return (WvList<T> *)wvslots; }
00174 
00175     virtual ~WvHashTable()
00176         { shutdown(); deletev sl(); }
00177 
00178     void add(T *data, bool auto_free)
00179         { sl()[hash(data) % numslots].append(data, auto_free); }
00180 
00181     WvLink *getlink(const K &key)
00182         { return prevlink(wvslots, &key, WvHash(key))->next; }
00183 
00184     T *operator[] (const K &key) const
00185         { return (T *)genfind(wvslots, &key, WvHash(key)); }
00186 
00187     void remove(const T *data)
00188     {
00189         unsigned h = hash(data);
00190         WvLink *l = prevlink(wvslots, Accessor::get_key(data), h);
00191         if (l && l->next) sl()[h % numslots].unlink_after(l);
00192     }
00193 
00194     void zap()
00195     {
00196         deletev sl();
00197         wvslots = new WvList<T>[numslots];
00198     }
00199 
00200     class Iter : public WvHashTableBase::IterBase
00201     {
00202     public:
00203         Iter(WvHashTable &_tbl) : IterBase(_tbl)
00204             { }
00205         Iter(const Iter &other) : IterBase(other)
00206             { }
00207         T *ptr() const
00208             { return (T *)link->data; }
00209         WvIterStuff(T);
00210     };
00211 
00212     typedef class WvSorter<T, WvHashTableBase, WvHashTableBase::IterBase>
00213         Sorter;
00214 };
00215 
00216 
00217 // ******************************************
00218 // WvDict and WvTable
00219 
00220 
00221 #define DeclareWvDict2(_classname_,  _type_, _ftype_, _field_)          \
00222         __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_)
00223 
00224 #define DeclareWvDict(_type_, _ftype_, _field_)                         \
00225         DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_)
00226 
00227 #define DeclareWvTable2(_classname_, _type_)                            \
00228         __WvDict_base(_classname_, _type_, _type_, obj)
00229 
00230 #define DeclareWvTable(_type_)                                          \
00231         DeclareWvTable2(_type_##Table, _type_)
00232 
00233 
00234 #define __WvDict_base(_classname_, _type_, _ftype_, _field_)            \
00235     template <class T, class K>                                         \
00236     struct _classname_##Accessor                                        \
00237     {                                                                   \
00238         static const K *get_key(const T *obj)                    \
00239             { return _field_; }                                         \
00240     };                                                                  \
00241                                                                         \
00242     typedef WvHashTable<_type_, _ftype_,                                \
00243              _classname_##Accessor<_type_, _ftype_> > _classname_
00244 
00245 
00246 
00247 // ******************************************
00248 // WvMap
00249 
00250 // *****************************
00251 // WvPair
00252 
00253 // Type specification to facilitate auto_free
00254 // Object type - ignores auto_free
00255 template<typename TKey, typename _TData>
00256 class WvMapPair
00257 {
00258     typedef _TData TData;
00259 public:
00260     TKey key;
00261     TData data;
00262     WvMapPair(const TKey &_key, const TData &_data, bool _auto_free)
00263         : key(_key), data(_data) { };
00264 };
00265 
00266 
00267 // Pointer type
00268 template<typename TKey, typename _TData>
00269 class WvMapPair<TKey, _TData*>
00270 {
00271     typedef _TData* TData;
00272 public:
00273     TKey key;
00274     TData data;
00275     WvMapPair(const TKey &_key, const TData &_data, bool _auto_free)
00276         : key(_key), data(_data), auto_free(_auto_free) { };
00277     virtual ~WvMapPair()
00278         { if (auto_free) delete data; };
00279 protected:
00280     bool auto_free;
00281 };
00282 
00283 
00284 // *****************************
00285 // Main map template
00286 //
00287 // Since operator[] returns a reference you should always check
00288 //      if the element exists() before using it.
00289 // Alternatively, use find(), to get a pointer to the data type,
00290 //      which will be null if the element does not exist.
00291 
00292 template
00293 <
00294     typename TKey,
00295     typename TData,
00296     template <class> class Comparator = OpEqComp,
00297     // Warning: Funny looking syntax follows!
00298     // If we decide that WvScatterHash is the One True Hash,
00299     //      just get rid of this part
00300     template
00301     <
00302         class,
00303         class,
00304         class,
00305         template <class> class
00306     > class BackendHash = WvHashTable
00307 >
00308 class WvMap : public BackendHash<WvMapPair<TKey, TData>, TKey,
00309         WvMap<TKey, TData, Comparator, BackendHash>, Comparator>
00310 {
00311 protected: 
00312     typedef WvMapPair<TKey, TData> MyPair;
00313     typedef WvMap<TKey, TData, Comparator, BackendHash> MyMap;
00314     typedef BackendHash<MyPair, TKey, MyMap, Comparator> MyHashTable;
00315 
00316     // We need this last_accessed thing to make sure exists()/operator[]
00317     //      does not cost us two hash lookups
00318     mutable MyPair* last_accessed;
00319     MyPair* find_helper(const TKey &key) const
00320     {
00321         if (last_accessed &&
00322                 Comparator<TKey>::compare(&last_accessed->key, &key))
00323             return last_accessed;
00324         return last_accessed = MyHashTable::operator[](key);
00325     }
00326     
00327     // copy constructor: not defined anywhere!
00328     WvMap(const WvMap &m);
00329 
00330 public:
00331     // accessor method for WvHashTable to use
00332     static const TKey *get_key(const MyPair *obj)
00333         { return &obj->key; }
00334 
00335     WvMap(int s) : MyHashTable(s), last_accessed(NULL)  { };
00336     TData *find(const TKey &key) const
00337     {
00338         MyPair* p = find_helper(key);
00339         return p ? &p->data : (TData*)NULL;
00340     }
00341     MyPair *find_pair(const TKey &key) const
00342     {
00343         return find_helper(key);
00344     }
00345     TData &operator[](const TKey &key) const
00346     {
00347         MyPair* p = find_helper(key);
00348         assert(p && "WvMap: operator[] called with a non-existent key");
00349         return p->data;
00350     }
00351     bool exists(const TKey &key) const
00352         { return find_helper(key); }
00353     void set(const TKey &key, const TData &data, bool auto_free = false)
00354     {
00355         if (find_helper(key))
00356             remove(key);
00357         add(key, data, auto_free);
00358     }
00359     void add(const TKey &key, const TData &data, bool auto_free = false)
00360         { MyHashTable::add(new MyPair(key, data, auto_free), true); }
00361     void remove(const TKey &key)
00362     {
00363         last_accessed = NULL;
00364         MyHashTable::remove(MyHashTable::operator[](key));
00365     } 
00366     void zap()
00367     {
00368         MyHashTable::zap();
00369         last_accessed = NULL;
00370     }
00371     typedef typename MyHashTable::Iter Iter;
00372 }; 
00373 
00374 
00375 #endif // __WVHASHTABLE_H

Generated on Sun Jul 10 17:30:56 2005 for WvStreams by  doxygen 1.4.0