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 "wvtypetraits.h"
00014 #include <assert.h>
00015 
00088 class WvHashTableBase
00089 {
00090     // Copy constructor - not defined anywhere!
00091     WvHashTableBase(const WvHashTableBase &t); 
00092 protected:
00093     WvHashTableBase(unsigned _numslots);
00094     virtual ~WvHashTableBase() {}; 
00095     WvHashTableBase& operator= (const WvHashTableBase &t);
00096     void setup()
00097         { /* default: do nothing */ }
00098     void shutdown()
00099         { /* default: do nothing */ }
00100     WvLink *prevlink(WvListBase *slots, const void *data, unsigned hash) const;
00101     void *genfind(WvListBase *slots, const void *data, unsigned hash) const;
00102 
00103     
00104 
00105     virtual bool compare(const void *key, const void *elem) const = 0;
00106 public:
00107     unsigned numslots;
00108     WvListBase *wvslots;
00109 
00114     size_t count() const;
00115 
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 
00146         bool get_autofree() const
00147         {
00148             return link->get_autofree();
00149         }
00150 
00154         void set_autofree(bool autofree)
00155         {
00156             link->set_autofree(autofree);
00157         }
00158     };
00159 };
00160 
00161 
00162 template <
00163     class T,                                            // element type
00164     class K,                                            // key type
00165     class Accessor,                                     // element to key
00166     template <class> class Comparator = OpEqComp        // comparison func
00167 >
00168 class WvHashTable : public WvHashTableBase
00169 {
00170     // copy constructor: not defined anywhere!
00171     WvHashTable(const WvHashTable &h);
00172 protected:
00173     typedef Comparator<K> MyComparator; 
00174 
00175     unsigned hash(const T *data)
00176         { return WvHash(*Accessor::get_key(data)); }
00177 
00178     virtual bool compare(const void *key, const void *elem) const
00179         { return MyComparator::compare((const K *)key,
00180                 Accessor::get_key((const T *)elem)); }
00181 
00182 public:
00188     WvHashTable(unsigned _numslots) : WvHashTableBase(_numslots)
00189         { wvslots = new WvList<T>[numslots]; setup(); }
00190 
00191     WvList<T> *sl()
00192         { return (WvList<T> *)wvslots; }
00193 
00194     virtual ~WvHashTable()
00195         { shutdown(); deletev sl(); }
00196 
00197     void add(T *data, bool autofree)
00198         { sl()[hash(data) % numslots].append(data, autofree); }
00199 
00200     WvLink *getlink(const K &key)
00201         { return prevlink(wvslots, &key, WvHash(key))->next; }
00202 
00203     T *operator[] (const K &key) const
00204         { return (T *)genfind(wvslots, &key, WvHash(key)); }
00205 
00209     bool get_autofree(const K &key) const
00210     {
00211         WvLink *l = getlink(key);
00212         if (l)
00213             return l->get_autofree();
00214         return false;
00215     }
00216 
00217     bool get_autofree(const T *data) const
00218     {
00219         return get_autofree(hash(data));
00220     }
00221 
00225     void set_autofree(const K &key, bool autofree)
00226     {
00227         WvLink *l = getlink(key);
00228         if (l)
00229             l->set_autofree(autofree);
00230     }
00231 
00232     void set_autofree(const T *data, bool autofree)
00233     {
00234         set_autofree(hash(data), autofree);
00235     }
00236 
00237     void remove(const T *data)
00238     {
00239         unsigned h = hash(data);
00240         WvLink *l = prevlink(wvslots, Accessor::get_key(data), h);
00241         if (l && l->next) sl()[h % numslots].unlink_after(l);
00242     }
00243 
00244     void zap()
00245     {
00246         deletev sl();
00247         wvslots = new WvList<T>[numslots];
00248     }
00249 
00250     class Iter : public WvHashTableBase::IterBase
00251     {
00252     public:
00253         Iter(WvHashTable &_tbl) : IterBase(_tbl)
00254             { }
00255         Iter(const Iter &other) : IterBase(other)
00256             { }
00257         T *ptr() const
00258             { return (T *)link->data; }
00259         WvIterStuff(T);
00260     };
00261 
00262     typedef class WvSorter<T, WvHashTableBase, WvHashTableBase::IterBase>
00263         Sorter;
00264 };
00265 
00266 
00267 // ******************************************
00268 // WvDict and WvTable
00269 
00270 
00271 #define DeclareWvDict2(_classname_,  _type_, _ftype_, _field_)          \
00272         __WvDict_base(_classname_, _type_, _ftype_, &obj->_field_)
00273 
00274 #define DeclareWvDict(_type_, _ftype_, _field_)                         \
00275         DeclareWvDict2(_type_##Dict, _type_, _ftype_, _field_)
00276 
00277 #define DeclareWvTable2(_classname_, _type_)                            \
00278         __WvDict_base(_classname_, _type_, _type_, obj)
00279 
00280 #define DeclareWvTable(_type_)                                          \
00281         DeclareWvTable2(_type_##Table, _type_)
00282 
00283 
00284 #define __WvDict_base(_classname_, _type_, _ftype_, _field_)            \
00285     template <class T, class K>                                         \
00286     struct _classname_##Accessor                                        \
00287     {                                                                   \
00288         static const K *get_key(const T *obj)                    \
00289             { return _field_; }                                         \
00290     };                                                                  \
00291                                                                         \
00292     typedef WvHashTable<_type_, _ftype_,                                \
00293              _classname_##Accessor<_type_, _ftype_> > _classname_
00294 
00295 
00296 
00297 // ******************************************
00298 // WvMap
00299 
00300 // *****************************
00301 // WvPair
00302 
00303 // Type specification to facilitate autofree
00304 // Object type - ignores autofree
00305 template<typename TKey, typename _TData>
00306 class WvMapPair
00307 {
00308     typedef _TData TData;
00309 public:
00310     TKey key;
00311     TData data;
00312     WvMapPair(const TKey &_key, const TData &_data, bool _autofree)
00313         : key(_key), data(_data) { };
00314 };
00315 
00316 
00317 // Pointer type
00318 template<typename TKey, typename _TData>
00319 class WvMapPair<TKey, _TData*>
00320 {
00321     typedef _TData* TData;
00322 public:
00323     TKey key;
00324     TData data;
00325     WvMapPair(const TKey &_key, const TData &_data, bool _autofree)
00326         : key(_key), data(_data), autofree(_autofree) { };
00327     virtual ~WvMapPair()
00328         { if (autofree) WvTraits<_TData>::release(data); };
00329 protected:
00330     bool autofree;
00331 };
00332 
00333 
00334 // *****************************
00335 // Main map template
00336 //
00337 // Since operator[] returns a reference you should always check
00338 //      if the element exists() before using it.
00339 // Alternatively, use find(), to get a pointer to the data type,
00340 //      which will be null if the element does not exist.
00341 
00342 template
00343 <
00344     typename TKey,
00345     typename TData,
00346     template <class> class Comparator = OpEqComp,
00347     // Warning: Funny looking syntax follows!
00348     // If we decide that WvScatterHash is the One True Hash,
00349     //      just get rid of this part
00350     template
00351     <
00352         class,
00353         class,
00354         class,
00355         template <class> class
00356     > class BackendHash = WvHashTable
00357 >
00358 class WvMap : public BackendHash<WvMapPair<TKey, TData>, TKey,
00359         WvMap<TKey, TData, Comparator, BackendHash>, Comparator>
00360 {
00361 protected: 
00362     typedef WvMapPair<TKey, TData> MyPair;
00363     typedef WvMap<TKey, TData, Comparator, BackendHash> MyMap;
00364     typedef BackendHash<MyPair, TKey, MyMap, Comparator> MyHashTable;
00365 
00366     // We need this last_accessed thing to make sure exists()/operator[]
00367     //      does not cost us two hash lookups
00368     mutable MyPair* last_accessed;
00369     MyPair* find_helper(const TKey &key) const
00370     {
00371         if (last_accessed &&
00372                 Comparator<TKey>::compare(&last_accessed->key, &key))
00373             return last_accessed;
00374         return last_accessed = MyHashTable::operator[](key);
00375     }
00376     
00377     // copy constructor: not defined anywhere!
00378     WvMap(const WvMap &m);
00379 
00380 public:
00381     // accessor method for WvHashTable to use
00382     static const TKey *get_key(const MyPair *obj)
00383         { return &obj->key; }
00384 
00385     WvMap(int s) : MyHashTable(s), last_accessed(NULL)  { };
00386     TData *find(const TKey &key) const
00387     {
00388         MyPair* p = find_helper(key);
00389         return p ? &p->data : (TData*)NULL;
00390     }
00391     MyPair *find_pair(const TKey &key) const
00392     {
00393         return find_helper(key);
00394     }
00395     TData &operator[](const TKey &key) const
00396     {
00397         MyPair* p = find_helper(key);
00398         assert(p && "WvMap: operator[] called with a non-existent key");
00399         return p->data;
00400     }
00401     bool exists(const TKey &key) const
00402         { return find_helper(key); }
00403     void set(const TKey &key, const TData &data, bool autofree = false)
00404     {
00405         if (find_helper(key))
00406             remove(key);
00407         add(key, data, autofree);
00408     }
00409     void add(const TKey &key, const TData &data, bool autofree = false)
00410         { MyHashTable::add(new MyPair(key, data, autofree), true); }
00411     void remove(const TKey &key)
00412     {
00413         last_accessed = NULL;
00414         MyHashTable::remove(MyHashTable::operator[](key));
00415     } 
00416     void zap()
00417     {
00418         MyHashTable::zap();
00419         last_accessed = NULL;
00420     }
00421     typedef typename MyHashTable::Iter Iter;
00422 }; 
00423 
00424 
00425 #endif // __WVHASHTABLE_H

Generated on Mon Feb 5 10:54:29 2007 for WvStreams by  doxygen 1.5.1