• Login
• Recent changes

• [Show pagesource]
• [Old revisions]

#ifndef FINDSHARE_H
#define FINDSHARE_H
//see findshare.txt in doc folder
 
 
#include <hash_map>
#include "..\_geom\aaa_first.h"
 
namespace fsh
{    template< typename K, typename V >
    class mh // Meta-Handle< "keyType", "valueType" >
    {    typedef K const * pcK;
        typedef K* pK;
        typedef V const * pcV;
        typedef V* pV;
        //The following three static functions are to be specialized by the user:
        static size_t key_hash(pcK);    //left undefined, needs specialization
        static bool equal_keys(pcK, pcK);        //left undefined, needs specialization
        static void free_handle(pK,pV);        //left undefined, needs specialization
        //Functors needed by stdext::hash_map. They simply call the private, static,
        //user-specialized functions (above) for hash code gen. and equality test.
        //September 2006 update:
        //The stdext::hash_map that comes with vc7 is quite different from
        //the hash map I was using originally. Instead of taking separate functors
        //for hash and comparison, it takes a single argument of class value_compare.
        //Here's their usage example:
        /*
        // hash_map_value_comp.cpp
        // compile with: /EHsc
        #include <hash_map>
        #include <iostream>
        int main( )
        {
            using namespace std;
            using namespace stdext;
            hash_map <int, int, hash_compare<int, less<int> > > hm1;
            hash_map <int, int, hash_compare<int, less<int> > >
            ::value_compare vc1 = hm1.value_comp( );
            pair< hash_map<int,int>::iterator, bool > pr1, pr2;
            pr1= hm1.insert ( hash_map <int, int> :: value_type ( 1, 10 ) );
            pr2= hm1.insert ( hash_map <int, int> :: value_type ( 2, 5 ) );
            if( vc1( *pr1.first, *pr2.first ) == true )   
            {
                cout << "The element ( 1,10 ) precedes the element ( 2,5 )."
                    << endl;
            }
            else   
            {
                cout << "The element ( 1,10 ) does not precede the element ( 2,5 )."
                    << endl;
            }
            if( vc1 ( *pr2.first, *pr1.first ) == true )
            {
                cout << "The element ( 2,5 ) precedes the element ( 1,10 )."
                    << endl;
            }
            else   
            {
                cout << "The element ( 2,5 ) does not precede the element ( 1,10 )."
                    << endl;
            }
        }
        */
#if 0
        //I don't quite understand, but I've used stdext::hash_map before, and it
        //didn't really need any functors if the mapped type has a size_t conversion
        //operator (which returns a hash value), so I'll just comment out for now.
        struct hf //hash functor
        {    size_t operator()(pcK pcK) const
            {    return mh<K,V>::key_hash(pcK); } //key_hash is usr-specialization
        };
        struct eq //equality comparison functor
        {    bool operator()(pcK pcK1, pcK pcK2)
            {    return mh<K,V>::equal_keys(pcK1,pcK2); } //equal_keys 2b usr-specialized
        };
#endif
        friend struct hf; friend struct eq;
        //std::hash_map, like std::map, stores objects of type std::pair< key, data >
        //Class C will be the type of the data part of this pair. It is a
        //wrapper of the V template type whiC simply adds a ref-count to it.
        class C //Counted-const-value wrapper
        {    friend class mh<K,V>;
            C() : rc_(0) {}
            C(pV pv) : pv_(pv), rc_(0) {}
            pcV inc_usr() const { ++rc_; return pv_; }
            size_t dec_usr() const { return --rc_; }
            void clr_usr() const { rc_=0; }
            //copy ctor, copy assignment and dtor, as generated by the compiler, are
            //just fine; and used by stl::pair; so don't disable! No ownership issues.
            pcV pv_;
            mutable size_t rc_;
        };
    public:
        class M : public stdext::hash_map<pK,C/*,hf,eq*/>
        {
        public:
            M(/*const size_t sz*/) : stdext::hash_map<pK,C/*,hf,eq*/>(/*sz*/) {}
        };
    private:
        typedef typename M::iterator I;
        class R : public std::pair<typename stdext::hash_map<pK,C/*,hf,eq*/>::iterator,bool>
        {
        public:
            R(std::pair<typename stdext::hash_map<pK,C/*,hf,eq*/>::iterator,bool> const & ibp)
                : std::pair<typename stdext::hash_map<pK,C/*,hf,eq*/>::iterator,bool>(ibp) {}
        };
        //Our two non-static (per mh) data members:
        I    it_;    //just used to decrement the map entry's ref count
        pcV    pv_;    //mh-cached copy of the pv_ in the hash table entry
        //Static section: --dealing with the std::hash_map, common repository...
        static M * m_;        //the hash_map, allocated singleton-like.
        static M * the_map(); //instantiates a hf map on demand
        static void clear(); //clears and deletes the hf map
        static size_t uc_; //global use count, for hash_map de-allocation
        static void inc_usr(){ ++uc_; }
        static bool dec_usr(){ return --uc_==0; }
        //acquisition: (the heart of findshare):
        I acq(pK k);
    public:
        //ctor's and dtor
        explicit mh<K,V>() : it_(), pv_(NULL) {}
        explicit mh<K,V>(pK k);
        mh<K,V>(mh<K,V> const & h);
        mh<K,V>& operator=(pK k); //intended for uninitd only
        mh<K,V>& operator=(mh<K,V> const & h); //intended for uninitd only
        virtual ~mh<K,V>() = 0; //inherit struct from handle to remove long template names
        V const & operator()() const { assert(pv_); return *pv_; } //f'n call op. rets ref to val
        bool got_val() const { return pv_ != 0; }
        void set_val(pcV); //only for first-time-key handles
};    };
 
// static vars:
template< typename K, typename V >
typename fsh::mh<K,V>::M * fsh::mh<K,V>::m_ = 0 ; 
template< typename K, typename V >
 size_t fsh::mh<K,V>::uc_ = 0;
 
// singleton static fn's:
template< typename K, typename V >
typename fsh::mh<K,V>::M *  fsh::mh<K,V>::the_map()
{    if( !m_ )
    {    m_ = new M(/*777*/);
        uc_ = 0;
    }
    return m_;
}
template < typename K, typename V >
 void fsh::mh<K,V>::clear()
{    if( m_ )
    {    m_->clear();
        delete m_;
        m_ = 0;
}    }
 
//acquisition (the heart of findshare): "find, or else create & insert"
template < typename K, typename V >
typename fsh::mh<K,V>::I fsh::mh<K,V>::acq(pK pk)
{    static M* pm = the_map();
    assert( the_map() );
    I iter(pm->find(pk)); //find.. if found we're done; else...
    if( iter == pm->end() ) //i.e.: if key not found in hash map
    {    //pV pv = make_handle(pk); //user specialization that generates id
        R res // insert new key/value pair in hash map
          ( pm->insert( I::value_type( pk, NULL ) ) );
        assert(res.second); //make sure that insertion succeded
        iter = res.first;  //successful insert :-)
        (*iter).second.clr_usr(); //start ref-count at zero
    }
    return iter;
}
template < typename K, typename V >
 void fsh::mh<K,V>::set_val(pcV pv) //only for first-time-key handles
{    assert(!pv_); if(!pv_) pv_ = pv;
    assert(!(*it_).second.pv_);
    if(!(*it_).second.pv_) (*it_).second.pv_ = pv;        
}
 
//ctor, assignment and dtor:
template < typename K, typename V >
 fsh::mh<K,V>::mh(pK pcK)
 : it_(acq(pcK)), pv_((*it_).second.inc_usr()){inc_usr();}
template < typename K, typename V >
 fsh::mh<K,V>::mh(mh<K,V> const & h)
 : it_(h.it_), pv_((*it_).second.inc_usr()){inc_usr();}
template < typename K, typename V >
 fsh::mh<K,V>& fsh::mh<K,V>::operator=(pK pcK) //intended for uninitd only
{    assert( !pv_ );
    it_ = acq(pcK);
    pv_ = (*it_).second.inc_usr();
    inc_usr();
    return *this;
}
template < typename K, typename V >
 fsh::mh<K,V>& fsh::mh<K,V>::operator=(fsh::mh<K,V> const & h) //intended for uninitd only
{    assert( this != &h );
    assert( !pv_ );
    assert( h.pv_ );
    it_ = h.it_;
    pv_ = (*it_).second.inc_usr();
    inc_usr();
    return *this;
}
template < typename K, typename V >
 fsh::mh<K,V>::~mh()
{    M* pm;
    assert( the_map() );
    if( (pm=the_map()) )
    {    assert( pv_ );
        if( !(*it_).second.dec_usr() )
        {    assert( (*it_).first );
            pV temp_pv = const_cast<pV>(pv_);
            pK temp_pk = (*it_).first;
            the_map()->erase(it_);
            free_handle(temp_pk,temp_pv); //usr-def'd specialization
            if( dec_usr() ) clear();
        }
        else if( dec_usr() ) assert( false ); //ERROR: use-counts out of synC!
}    }
 
#endif