1 /*****************************************************************************/ 2 /*! 3 *\file hash_map.h 4 *\brief hash map implementation 5 * 6 * Author: Alexander Fuchs 7 * 8 * Created: Fri Oct 13 11:04:00 2006 9 * 10 * <hr> 11 * 12 * License to use, copy, modify, sell and/or distribute this software 13 * and its documentation for any purpose is hereby granted without 14 * royalty, subject to the terms and conditions defined in the \ref 15 * LICENSE file provided with this distribution. 16 * 17 * <hr> 18 */ 19 /*****************************************************************************/ 20 21 /* 22 * Copyright (c) 1996,1997 23 * Silicon Graphics Computer Systems, Inc. 24 * 25 * Permission to use, copy, modify, distribute and sell this software 26 * and its documentation for any purpose is hereby granted without fee, 27 * provided that the above copyright notice appear in all copies and 28 * that both that copyright notice and this permission notice appear 29 * in supporting documentation. Silicon Graphics makes no 30 * representations about the suitability of this software for any 31 * purpose. It is provided "as is" without express or implied warranty. 32 * 33 * 34 * Copyright (c) 1994 35 * Hewlett-Packard Company 36 * 37 * Permission to use, copy, modify, distribute and sell this software 38 * and its documentation for any purpose is hereby granted without fee, 39 * provided that the above copyright notice appear in all copies and 40 * that both that copyright notice and this permission notice appear 41 * in supporting documentation. Hewlett-Packard Company makes no 42 * representations about the suitability of this software for any 43 * purpose. It is provided "as is" without express or implied warranty. 44 * 45 */ 46 47 // this implementation is in essence a subset of the SGI implementation: 48 // http://www.sgi.com/tech/stl/stl_hash_map.h 49 50 #ifndef _cvc3__hash__hash_map_h_ 51 #define _cvc3__hash__hash_map_h_ 52 53 #include "hash_fun.h" 54 #include "hash_table.h" 55 #include <functional> 56 #include <utility> 57 58 namespace Hash { 59 60 // select1st is an extension taken from the SGI 61 // implementation of the STL file functional: 62 // http://www.sgi.com/tech/stl/stl_function.h 63 template <class _Pair> 64 struct _Select1st : public std::unary_function<_Pair, typename _Pair::first_type> { operator_Select1st65 const typename _Pair::first_type& operator()(const _Pair& __x) const { 66 return __x.first; 67 } 68 }; 69 70 71 /*! hash map implementation based on the sgi interface: 72 http://www.sgi.com/tech/stl/hash_map.html 73 74 _Key: hash key type 75 _Data: data to store 76 _HashFcn: functional class providing a hash function: size_type (_Key) 77 _EqualKey: functional class providing a comparison function: bool(_Key, _Key) 78 returns true iff two keys are considered to be equal 79 */ 80 template <class _Key, class _Data, class _HashFcn = hash<_Key>, 81 class _EqualKey = std::equal_to<_Key> > 82 class hash_map { 83 84 /// types 85 protected: 86 // note: const _Key must be used for _Value and _ExtractKey. 87 // if one is const and the other is not, 88 // then extracting a key will require a conversion and a temporary 89 // (at least in debug mode), 90 // so that the reference returned by _ExtractKey point to a temporary. 91 typedef hash_table<_Key, std::pair<const _Key, _Data>, 92 _HashFcn, _EqualKey, _Select1st<std::pair<const _Key, _Data> > > 93 _hash_table; 94 95 public: 96 // typedefs as custom for other implementations 97 typedef typename _hash_table::size_type size_type; 98 typedef typename _hash_table::key_type key_type; 99 typedef _Data data_type; 100 typedef typename _hash_table::value_type value_type; 101 typedef typename _hash_table::hasher hasher; 102 typedef typename _hash_table::key_equal key_equal; 103 104 public: 105 // iterators 106 typedef typename _hash_table::iterator iterator; 107 typedef typename _hash_table::const_iterator const_iterator; 108 109 /// variables 110 111 protected: 112 // the hash table 113 _hash_table d_table; 114 115 116 /// methods 117 118 public: 119 /// constructors 120 121 // default size is 16 buckets hash_map()122 hash_map() : 123 d_table() 124 { }; 125 126 // specifiy initial number of buckets - must be positive hash_map(size_type initial_capacity)127 hash_map(size_type initial_capacity) : 128 d_table(initial_capacity) 129 { }; 130 131 // specifiy initial number of buckets and hash function hash_map(size_type initial_capacity,const _HashFcn & hash)132 hash_map(size_type initial_capacity, const _HashFcn& hash) : 133 d_table(initial_capacity, hash) 134 { }; 135 136 // specifiy initial number of buckets, hash and equal function hash_map(size_type initial_capacity,const _HashFcn & hash,const _EqualKey & equal)137 hash_map(size_type initial_capacity, 138 const _HashFcn& hash, const _EqualKey& equal) : 139 d_table(initial_capacity, hash, equal) 140 { }; 141 142 // copy hash map. hash_map(const hash_map & other)143 hash_map(const hash_map& other) : 144 d_table(other.d_table) 145 { }; 146 147 // assign hash map 148 hash_map& operator=(const hash_map& other) { 149 if (this != &other) { 150 d_table = other.d_table; 151 } 152 153 return *this; 154 } 155 swap(hash_map & other)156 void swap(hash_map& other) { 157 d_table.swap(other.d_table); 158 } 159 160 // removes all entries, number of buckets is not reduced. clear()161 void clear() { 162 d_table.clear(); 163 }; 164 165 166 167 /// operations 168 169 170 // returns end iterator if key was not bound find(const key_type & key)171 iterator find(const key_type& key) { 172 return d_table.find(key); 173 } 174 175 // const version of find find(const key_type & key)176 const_iterator find(const key_type& key) const { 177 return d_table.find(key); 178 } 179 180 // if key in value is already bound, 181 // returns that binding, 182 // otherwise inserts a default value and returns a reference to it. 183 data_type& operator[](const key_type& key) { 184 return d_table.find_or_insert(std::make_pair(key, data_type())).second; 185 } 186 187 188 // adds the mapping from key to data, if key is still unbound 189 // otherwise returns false insert(const value_type & entry)190 std::pair<iterator, bool> insert(const value_type& entry) { 191 return d_table.insert(entry); 192 } 193 194 // removes binding of key 195 // returns number of keys removed, 196 // i.e. 1 if key was bound, 0 if key was not bound. erase(const key_type & key)197 size_type erase(const key_type& key) { 198 return d_table.erase(key); 199 } 200 201 // removes element pointed to by iter, 202 // returns element after iter. erase(const const_iterator & i)203 const_iterator erase(const const_iterator& i) { 204 return d_table.erase(i); 205 } 206 207 208 /// status 209 210 // is the key bound? contains(const key_type & key)211 bool contains(const key_type& key) const { 212 return d_table.contains(key); 213 } 214 215 // returns the number of times a key is bound, 216 // i.e. 0 or 1 count(const _Key & key)217 size_type count(const _Key& key) const { 218 return d_table.count(key); 219 } 220 221 // is the hash map empty? empty()222 bool empty() const { 223 return d_table.empty(); 224 } 225 226 // the number of elements in the hash map size()227 size_type size() const { 228 return d_table.size(); 229 } 230 231 // the number of buckets in the hash map bucket_count()232 size_type bucket_count() const { 233 return d_table.bucket_count(); 234 } 235 236 // returns the average number of elements per bucket load_factor()237 float load_factor() const { 238 return d_table.load_factor(); 239 } 240 241 242 243 /// iterators 244 245 // returns forward iterator to iterate over all key/data pairs begin()246 iterator begin() { 247 return d_table.begin(); 248 } 249 250 // const version of begin begin()251 const_iterator begin() const { 252 return d_table.begin(); 253 } 254 255 256 // returns end iterator end()257 iterator end() { 258 return d_table.end(); 259 } 260 261 // const version of end end()262 const_iterator end() const { 263 return d_table.end(); 264 } 265 }; 266 267 } 268 269 #endif 270