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

wvscatterhash.h

00001 /* -*- Mode: C++ -*-
00002  * Worldvisions Weaver Software:
00003  *   Copyright (C) 1997-2003 Net Integration Technologies, Inc.
00004  *
00005  * A hash table container.
00006  */
00007 #ifndef __WVSCATTERHASH_H
00008 #define __WVSCATTERHASH_H
00009 
00010 #include "wvxplc.h"   // for deletev.  ick.
00011 #include "wvhash.h"
00012 #include "wvsorter.h"
00013 #include <sys/types.h>
00014 
00015 #define REBUILD_LOAD_FACTOR 0.45
00016 #define RESIZE_LOAD_FACTOR 0.4
00017 
00018 #define IS_OCCUPIED(x) (x.status >> 1)
00019 #define IS_AUTO_FREE(x) (x.status == 3)
00020 #define IS_DELETED(x) (x.status == 1)
00021 
00022 class WvScatterHashBase
00023 {
00024 public:
00025     WvScatterHashBase(unsigned _numslots);
00026     virtual ~WvScatterHashBase() { deletev xslots; }
00027 
00028     struct pair
00029     {
00030         void *data;
00031         unsigned status : 2;
00032     };
00033 
00034     static struct pair null_pair;
00035     static const unsigned prime_numbers[];
00036 
00037     size_t count() const { return num; }
00038     bool isempty() const { return !num; }
00039     size_t slowcount() const;
00040   
00041     /******* IterBase ******/
00042     class IterBase
00043     {
00044     public:
00045         IterBase(WvScatterHashBase &_table) : table(&_table) { }
00046 
00047         IterBase(const IterBase &other)
00048             : table(other.table), index(other.index) { }
00049 
00050         void rewind() { index = 0; }
00051         bool cur()
00052             { return index <= table->numslots; }
00053         void *vptr()
00054             { return get(); }
00055         
00056         bool next()
00057         {
00058             if (!table)
00059                 return false;
00060 
00061             /* FIXME: Couldn't this be a *little* clearer? */
00062             while (++index <= table->numslots &&
00063                    !IS_OCCUPIED(table->xslots[index-1])) { }
00064 
00065             return index <= table->numslots;
00066         }
00067 
00068         bool get_autofree()
00069             { return IS_AUTO_FREE(table->xslots[index-1]); }
00070 
00071         void set_autofree(bool auto_free)
00072             { table->xslots[index-1].status = auto_free ? 3 : 2; }
00073 
00074     protected:
00075         void *get() const { return table->xslots[index-1].data; }
00076 
00077         WvScatterHashBase *table;
00078         unsigned index;
00079     };
00080 
00081 
00082 protected:
00083     virtual unsigned do_hash(const void *data) = 0;
00084     virtual void do_delete(void *data) = 0;
00085 
00086     friend class IterBase;
00087 
00088     pair *xslots;
00089     int prime_index;
00090     unsigned numslots;
00091 
00092     pair *genfind(const void *data, unsigned hash) const;
00093     void _add(void *data, bool auto_free);
00094     void _add(void *data, unsigned hash, bool auto_free);
00095     void _remove(const void *data, unsigned hash);
00096     void _zap();
00097     void _set_autofree(const void *data, unsigned hash, bool auto_free);
00098     bool _get_autofree(const void *data, unsigned hash);
00099 
00100     virtual bool compare(const void *key, const void *elem) const = 0;
00101 
00102 
00103 private:
00104     void rebuild();
00105     unsigned second_hash(unsigned hash) const
00106         { return (hash % (numslots - 1)) + 1; }
00107     unsigned curhash(unsigned hash, unsigned hash2, unsigned attempt) const
00108         //{ return (hash + attempt * attempt) % numslots; }
00109         { return (hash + attempt*hash2) % numslots; }
00110 
00111     size_t used;
00112     size_t num;
00113 };
00114 
00115 
00116 template <
00117     class T,                                            // element type
00118     class K,                                            // key type
00119     class Accessor,                                     // element to key
00120     template <class> class Comparator = OpEqComp        // comparison func
00121 >
00122 class WvScatterHash : public WvScatterHashBase
00123 {
00124 protected:
00125     typedef Comparator<K> MyComparator;
00126 
00127     virtual bool compare(const void *key, const void *elem) const
00128         { return MyComparator::compare((const K *)key,
00129                 Accessor::get_key((const T *)elem)); }
00130 
00131     unsigned hash(const T *data)
00132         { return WvHash(*Accessor::get_key(data)); }
00133 
00134     virtual unsigned do_hash(const void *data)
00135         { return hash((const T *)data); }
00136 
00137     virtual void do_delete(void *data)
00138         { delete (T *)data; }    
00139 
00140 public:
00141     WvScatterHash(unsigned _numslots = 0) : WvScatterHashBase(_numslots) { }
00142     virtual ~WvScatterHash() { _zap(); }
00143 
00144     T *operator[] (const K &key) const
00145         { return (T *)(genfind(&key, WvHash(key))->data); }
00146 
00147     void add(const T *data, bool auto_free = false)
00148         { _add((void *)data, hash(data), auto_free); }
00149 
00150     void remove(const T *data)
00151         { _remove(Accessor::get_key(data), hash(data)); }
00152 
00153     void set_autofree(const T *data, bool auto_free)
00154         { _set_autofree(Accessor::get_key(data), hash(data), auto_free); }
00155 
00156     bool get_autofree(const T *data)
00157         { return _get_autofree(Accessor::get_key(data), hash(data)); }
00158 
00159     void zap()
00160         { _zap(); }
00161 
00162 
00163     class Iter : public WvScatterHashBase::IterBase
00164     {
00165     public:
00166         Iter(WvScatterHash &_table) : IterBase(_table) { }
00167         Iter(const Iter &other) : IterBase(other) { }
00168 
00169         int *getstatus() { return &xslots[index-1].status; }
00170 
00171         T *ptr() const
00172             { return (T *)(get()); }
00173 
00174         WvIterStuff(T);
00175     };
00176 
00177     typedef class WvSorter<T, WvScatterHashBase, WvScatterHashBase::IterBase>
00178         Sorter;
00179 };
00180 
00181 
00182 #define DeclareWvScatterDict2(_classname_,  _type_, _ftype_, _field_)     \
00183         __WvScatterDict_base(_classname_, _type_, _ftype_, &obj->_field_)
00184 
00185 #define DeclareWvScatterDict(_type_, _ftype_, _field_)                    \
00186         DeclareWvScatterDict2(_type_##Dict, _type_, _ftype_, _field_)
00187 
00188 #define DeclareWvScatterTable2(_classname_, _type_)                       \
00189         __WvScatterDict_base(_classname_, _type_, _type_, obj)
00190 
00191 #define DeclareWvScatterTable(_type_)                                     \
00192         DeclareWvScatterTable2(_type_##Table, _type_)
00193 
00194 
00195 #define __WvScatterDict_base(_classname_, _type_, _ftype_, _field_)       \
00196     template <class T, class K>                                           \
00197     struct _classname_##Accessor                                          \
00198     {                                                                     \
00199         static const K *get_key(const T *obj)                             \
00200             { return _field_; }                                           \
00201     };                                                                    \
00202                                                                           \
00203     typedef WvScatterHash<_type_, _ftype_,                                \
00204              _classname_##Accessor<_type_, _ftype_> > _classname_
00205 
00206 
00207 #endif //_WVSCATTERHASH_H

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