WvStreams
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 #endif // __WVHASHTABLE_H