D:/projects/ACE/proto/Source/hash.h

Go to the documentation of this file.

#ifndef _HASH_H
#define _HASH_H

#if defined(_MSC_VER)
#include <hash_set>
#elif defined(__GNUC__)
// GCC stores hash_set in ext subdirectory.
#include <ext/hash_set>
#endif

// We use std::pair here.
#include <utility>

#include "pool.h"
#include "utils.h"

namespace ace {

#if defined(_MSC_VER)
template<class _Type, class _Comp>
#elif defined(__GNUC__)
template<class _Type, class _HashFunc, class _Comp>
#endif
class HashedStore {
#if defined(_MSC_VER)
    typedef typename stdext::hash_set<_Type *, _Comp> _hash_table_t;
#elif defined(__GNUC__)
    typedef typename __gnu_cxx::hash_set<_Type *, _HashFunc, _Comp> _hash_table_t;
#endif

    typedef typename std::pair<typename _hash_table_t::iterator, bool> _hash_table_pair_ib_t;
    typedef typename std::pair<typename _hash_table_t::const_iterator, bool> _hash_table_pair_cib_t;
    ContinuousPool<_Type> _memory_pool;
    _hash_table_t _hash_table;

#if defined(_MSC_VER)

    _hash_table_pair_ib_t _lower_bound(_Type& key) throw() {
        //
        static _hash_table_t::key_compare comp;
        // Search for N-gram in hash tables.
        _hash_table_t::iterator iter = _hash_table.lower_bound(&key);
        if ( iter != _hash_table.end() ) {
            // Compare (pointers to) ngrams using string_store_t comparator.
            if ( !comp(&key, *iter) && !comp(*iter, &key) ) {
                // Already stored within!
                return _hash_table_pair_ib_t(iter, true);
            }
        }
        // Otherwise => not found.
        return _hash_table_pair_ib_t(iter, false);
    }
    _hash_table_pair_cib_t _lower_bound(const _Type& key) const throw() {
        //
        static _hash_table_t::key_compare comp;
        // Search for N-gram in hash tables.
        _hash_table_t::const_iterator iter = _hash_table.lower_bound(&key);
        if ( iter != _hash_table.end() ) {
            // Compare (pointers to) ngrams using string_store_t comparator.
            if ( !comp(&key, *iter) && !comp(*iter, &key) ) {
                // Already stored within!
                return _hash_table_pair_cib_t(iter, true);
            }
        }
        // Otherwise => not found.
        return _hash_table_pair_cib_t(iter, false);
    }
#elif defined(__GNUC__)

    _hash_table_pair_ib_t _find(const _Type& key) throw() {
        static typename _hash_table_t::key_equal comp;
        _Type& _key = const_cast<_Type&>(key);
        // Search for N-gram in hash tables.
        std::pair<typename _hash_table_t::iterator, typename _hash_table_t::iterator> ip = _hash_table.equal_range(&_key);
        if ( ip.first != ip.second ) {
            // Already stored within!
            return _hash_table_pair_ib_t(ip.first, true);
        }
        // Otherwise => not found.
        return _hash_table_pair_ib_t(_hash_table.end(), false);
    }
    _hash_table_pair_cib_t _find(const _Type& key) const throw() {
        static typename _hash_table_t::key_equal comp;
        _Type& _key = const_cast<_Type&>(key);
        // Search for N-gram in hash tables.
        std::pair<typename _hash_table_t::const_iterator, typename _hash_table_t::iterator> ip = _hash_table.equal_range(&_key);
        if ( ip.first != ip.second ) {
            // Already stored within!
            return _hash_table_pair_cib_t(ip.first, true);
        }
        // Otherwise => not found.
        return _hash_table_pair_cib_t(_hash_table.end(), false);
    }
#endif

    HashedStore(const HashedStore&);
    HashedStore& operator=(const HashedStore&);
public:
    typedef typename std::pair<_Type *, bool> insert_status_t;
    HashedStore(size_t memory_pool_block_size = 4096): _memory_pool(memory_pool_block_size), _hash_table() {}
    ~HashedStore(void) throw() {
        _memory_pool.clear();
    }
    _Type * get(const _Type& key) const throw() {   
#if defined(_MSC_VER)
        // Search for N-gram in hash tables using _lower_bound private method.
        _hash_table_pair_cib_t pair_cib = _lower_bound(key);
#elif defined(__GNUC__)
        // Search for N-gram in hash tables using _find private method.
        _hash_table_pair_cib_t pair_cib = _find(key);
#endif
        if ( pair_cib.second ) {
            // Founded!
            return *pair_cib.first;
        }
        // Otherwise => not found.
        return NULL;
    }
    inline _Type * shift(const _Type *from, ptrdiff_t offset = 1) const throw() {   return _memory_pool.shift(from, offset); }
    inline const _Type * start(void) const throw() { return _memory_pool.start(); }
#if defined(_MSC_VER)
    insert_status_t insert(_Type& key) {
        // Search for N-gram in hash tables using _lower_bound private method.
        _hash_table_pair_ib_t pair_ib = _lower_bound(key);
#elif defined(__GNUC__)
    insert_status_t insert(const _Type& key) {
        // Search for N-gram in hash tables using _find private method.
        _hash_table_pair_ib_t pair_ib = _find(key);
#endif

        if ( pair_ib.second ) {
            // Founded!
            return insert_status_t(*pair_ib.first, false);
        }

        // New object - new memory needed...
        // Parameter is obsolete, so pass 1...
        void *mem = _memory_pool.get_memory(1); // This may throw.
        
        // Copy passed word to new memory using copy constructor and placement new,
        // insert pointer to hash table and return dereferenced iterator.
#if defined(_MSC_VER)
        // Note: On MSVC2005 version of hash_set libraries iterator hint is ignored.
        return insert_status_t(*_hash_table.insert(pair_ib.first, new (mem) _Type(key)), true);
#elif defined(__GNUC__)
        _hash_table.insert(new (mem) _Type(key));
        return insert_status_t(*_hash_table.insert(new (mem) _Type(key)).first, true);
#endif
    }

};

} // namespace ace

#endif

---