00001
00012 #ifndef _HASH_H
00013 #define _HASH_H
00014
00015 #if defined(_MSC_VER)
00016 #include <hash_set>
00017 #elif defined(__GNUC__)
00018
00019 #include <ext/hash_set>
00020 #endif
00021
00022
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
00065 _hash_table_t::iterator iter = _hash_table.lower_bound(&key);
00066 if ( iter != _hash_table.end() ) {
00067
00068 if ( !comp(&key, *iter) && !comp(*iter, &key) ) {
00069
00070 return _hash_table_pair_ib_t(iter, true);
00071 }
00072 }
00073
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
00082 _hash_table_t::const_iterator iter = _hash_table.lower_bound(&key);
00083 if ( iter != _hash_table.end() ) {
00084
00085 if ( !comp(&key, *iter) && !comp(*iter, &key) ) {
00086
00087 return _hash_table_pair_cib_t(iter, true);
00088 }
00089 }
00090
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
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
00103 return _hash_table_pair_ib_t(ip.first, true);
00104 }
00105
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
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
00117 return _hash_table_pair_cib_t(ip.first, true);
00118 }
00119
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
00146 _hash_table_pair_cib_t pair_cib = _lower_bound(key);
00147 #elif defined(__GNUC__)
00148
00149 _hash_table_pair_cib_t pair_cib = _find(key);
00150 #endif
00151 if ( pair_cib.second ) {
00152
00153 return *pair_cib.first;
00154 }
00155
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
00169 _hash_table_pair_ib_t pair_ib = _lower_bound(key);
00170 #elif defined(__GNUC__)
00171 insert_status_t insert(const _Type& key) {
00172
00173 _hash_table_pair_ib_t pair_ib = _find(key);
00174 #endif
00175
00176 if ( pair_ib.second ) {
00177
00178 return insert_status_t(*pair_ib.first, false);
00179 }
00180
00181
00182
00183 void *mem = _memory_pool.get_memory(1);
00184
00185
00186
00187 #if defined(_MSC_VER)
00188
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 }
00199
00200 #endif