- Main Page
- Namespaces
- Classes
- Files

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

Go to the documentation of this file.

    00001
    00012 #ifndef _HASH_H
    00013 #define _HASH_H
    00014
    00015 #if defined(_MSC_VER)
    00016 #include <hash_set>
    00017 #elif defined(__GNUC__)
    00018 // GCC stores hash_set in ext subdirectory.
    00019 #include <ext/hash_set>
    00020 #endif
    00021
    00022 // We use std::pair here.
    00023 #include <utility>
    00024
    00025 #include "pool.h"
    00026 #include "utils.h"
    00027
    00028 namespace ace {
    00029
    00032 #if defined(_MSC_VER)
    00033 template<class _Type, class _Comp>
    00034 #elif defined(__GNUC__)
    00035 template<class _Type, class _HashFunc, class _Comp>
    00036 #endif
    00037 class HashedStore {
    00040 #if defined(_MSC_VER)
    00041     typedef typename stdext::hash_set<_Type *, _Comp> _hash_table_t;
    00042 #elif defined(__GNUC__)
    00043     typedef typename __gnu_cxx::hash_set<_Type *, _HashFunc, _Comp> _hash_table_t;
    00044 #endif
    00045
    00047     typedef typename std::pair<typename _hash_table_t::iterator, bool> _hash_table_pair_ib_t;
    00050     typedef typename std::pair<typename _hash_table_t::const_iterator, bool> _hash_table_pair_cib_t;
    00053     ContinuousPool<_Type> _memory_pool;
    00056     _hash_table_t _hash_table;
    00057
    00058 #if defined(_MSC_VER)
    00059
    00061     _hash_table_pair_ib_t _lower_bound(_Type& key) throw() {
    00062         //
    00063         static _hash_table_t::key_compare comp;
    00064         // Search for N-gram in hash tables.
    00065         _hash_table_t::iterator iter = _hash_table.lower_bound(&key);
    00066         if ( iter != _hash_table.end() ) {
    00067             // Compare (pointers to) ngrams using string_store_t comparator.
    00068             if ( !comp(&key, *iter) && !comp(*iter, &key) ) {
    00069                 // Already stored within!
    00070                 return _hash_table_pair_ib_t(iter, true);
    00071             }
    00072         }
    00073         // Otherwise => not found.
    00074         return _hash_table_pair_ib_t(iter, false);
    00075     }
    00078     _hash_table_pair_cib_t _lower_bound(const _Type& key) const throw() {
    00079         //
    00080         static _hash_table_t::key_compare comp;
    00081         // Search for N-gram in hash tables.
    00082         _hash_table_t::const_iterator iter = _hash_table.lower_bound(&key);
    00083         if ( iter != _hash_table.end() ) {
    00084             // Compare (pointers to) ngrams using string_store_t comparator.
    00085             if ( !comp(&key, *iter) && !comp(*iter, &key) ) {
    00086                 // Already stored within!
    00087                 return _hash_table_pair_cib_t(iter, true);
    00088             }
    00089         }
    00090         // Otherwise => not found.
    00091         return _hash_table_pair_cib_t(iter, false);
    00092     }
    00093 #elif defined(__GNUC__)
    00094
    00096     _hash_table_pair_ib_t _find(const _Type& key) throw() {
    00097         static typename _hash_table_t::key_equal comp;
    00098         _Type& _key = const_cast<_Type&>(key);
    00099         // Search for N-gram in hash tables.
    00100         std::pair<typename _hash_table_t::iterator, typename _hash_table_t::iterator> ip = _hash_table.equal_range(&_key);
    00101         if ( ip.first != ip.second ) {
    00102             // Already stored within!
    00103             return _hash_table_pair_ib_t(ip.first, true);
    00104         }
    00105         // Otherwise => not found.
    00106         return _hash_table_pair_ib_t(_hash_table.end(), false);
    00107     }
    00110     _hash_table_pair_cib_t _find(const _Type& key) const throw() {
    00111         static typename _hash_table_t::key_equal comp;
    00112         _Type& _key = const_cast<_Type&>(key);
    00113         // Search for N-gram in hash tables.
    00114         std::pair<typename _hash_table_t::const_iterator, typename _hash_table_t::iterator> ip = _hash_table.equal_range(&_key);
    00115         if ( ip.first != ip.second ) {
    00116             // Already stored within!
    00117             return _hash_table_pair_cib_t(ip.first, true);
    00118         }
    00119         // Otherwise => not found.
    00120         return _hash_table_pair_cib_t(_hash_table.end(), false);
    00121     }
    00122 #endif
    00123
    00125     HashedStore(const HashedStore&);
    00128     HashedStore& operator=(const HashedStore&);
    00129 public:
    00132     typedef typename std::pair<_Type *, bool> insert_status_t;
    00135     HashedStore(size_t memory_pool_block_size = 4096): _memory_pool(memory_pool_block_size), _hash_table() {}
    00138     ~HashedStore(void) throw() {
    00139         _memory_pool.clear();
    00140     }
    00143     _Type * get(const _Type& key) const throw() {
    00144 #if defined(_MSC_VER)
    00145         // Search for N-gram in hash tables using _lower_bound private method.
    00146         _hash_table_pair_cib_t pair_cib = _lower_bound(key);
    00147 #elif defined(__GNUC__)
    00148         // Search for N-gram in hash tables using _find private method.
    00149         _hash_table_pair_cib_t pair_cib = _find(key);
    00150 #endif
    00151         if ( pair_cib.second ) {
    00152             // Founded!
    00153             return *pair_cib.first;
    00154         }
    00155         // Otherwise => not found.
    00156         return NULL;
    00157     }
    00160     inline _Type * shift(const _Type *from, ptrdiff_t offset = 1) const throw() {   return _memory_pool.shift(from, offset); }
    00163     inline const _Type * start(void) const throw() { return _memory_pool.start(); }
    00166 #if defined(_MSC_VER)
    00167     insert_status_t insert(_Type& key) {
    00168         // Search for N-gram in hash tables using _lower_bound private method.
    00169         _hash_table_pair_ib_t pair_ib = _lower_bound(key);
    00170 #elif defined(__GNUC__)
    00171     insert_status_t insert(const _Type& key) {
    00172         // Search for N-gram in hash tables using _find private method.
    00173         _hash_table_pair_ib_t pair_ib = _find(key);
    00174 #endif
    00175
    00176         if ( pair_ib.second ) {
    00177             // Founded!
    00178             return insert_status_t(*pair_ib.first, false);
    00179         }
    00180
    00181         // New object - new memory needed...
    00182         // Parameter is obsolete, so pass 1...
    00183         void *mem = _memory_pool.get_memory(1); // This may throw.
    00184
    00185         // Copy passed word to new memory using copy constructor and placement new,
    00186         // insert pointer to hash table and return dereferenced iterator.
    00187 #if defined(_MSC_VER)
    00188         // Note: On MSVC2005 version of hash_set libraries iterator hint is ignored.
    00189         return insert_status_t(*_hash_table.insert(pair_ib.first, new (mem) _Type(key)), true);
    00190 #elif defined(__GNUC__)
    00191         _hash_table.insert(new (mem) _Type(key));
    00192         return insert_status_t(*_hash_table.insert(new (mem) _Type(key)).first, true);
    00193 #endif
    00194     }
    00195
    00196 };
    00197
    00198 } // namespace ace
    00199
    00200 #endif