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