Sierra Toolkit  Version of the Day
hash_map_eastl.h
1 /*
2 Copyright (C) 2009-2010 Electronic Arts, Inc. All rights reserved.
3 
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 
8 1. Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of
14  its contributors may be used to endorse or promote products derived
15  from this software without specific prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 
30 // EASTL/hash_map.h
31 //
32 // Copyright (c) 2005, Electronic Arts. All rights reserved.
33 // Written and maintained by Paul Pedriana.
35 
37 // This file is based on the TR1 (technical report 1) reference implementation
38 // of the unordered_set/unordered_map C++ classes as of about 4/2005. Most likely
39 // many or all C++ library vendors' implementations of this classes will be
40 // based off of the reference version and so will look pretty similar to this
41 // file as well as other vendors' versions.
43 
44 
45 #ifndef EASTL_HASH_MAP_H
46 #define EASTL_HASH_MAP_H
47 
48 
49 #include <stk_util/util/config_eastl.h>
50 #include <stk_util/util/hashtable_eastl.h>
51 #include <stk_util/util/functional_eastl.h>
52 #include <stk_util/util/utility_eastl.h>
53 
54 
55 
56 namespace eastl
57 {
58 
63  #ifndef EASTL_HASH_MAP_DEFAULT_NAME
64  #define EASTL_HASH_MAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_map" // Unless the user overrides something, this is "EASTL hash_map".
65  #endif
66 
67 
72  #ifndef EASTL_HASH_MULTIMAP_DEFAULT_NAME
73  #define EASTL_HASH_MULTIMAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_multimap" // Unless the user overrides something, this is "EASTL hash_multimap".
74  #endif
75 
76 
79  #ifndef EASTL_HASH_MAP_DEFAULT_ALLOCATOR
80  #define EASTL_HASH_MAP_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MAP_DEFAULT_NAME)
81  #endif
82 
85  #ifndef EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR
86  #define EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MULTIMAP_DEFAULT_NAME)
87  #endif
88 
89 
90 
124  template <typename Key, typename T, typename Hash = eastl::hash<Key>, typename Predicate = eastl::equal_to<Key>,
125  typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false>
126  class hash_map
127  : public hashtable<Key, eastl::pair<const Key, T>, Allocator, eastl::use_first<eastl::pair<const Key, T> >, Predicate,
128  Hash, mod_range_hashing, default_ranged_hash, prime_rehash_policy, bCacheHashCode, true, true>
129  {
130  public:
131  typedef hashtable<Key, eastl::pair<const Key, T>, Allocator,
133  Predicate, Hash, mod_range_hashing, default_ranged_hash,
134  prime_rehash_policy, bCacheHashCode, true, true> base_type;
136  typedef typename base_type::size_type size_type;
137  typedef typename base_type::key_type key_type;
138  typedef T mapped_type;
139  typedef typename base_type::value_type value_type; // Note that this is pair<const key_type, mapped_type>.
140  typedef typename base_type::allocator_type allocator_type;
141  typedef typename base_type::node_type node_type;
143  typedef typename base_type::iterator iterator;
144 
145  #if !defined(__GNUC__) || (__GNUC__ >= 3) // GCC 2.x has a bug which we work around.
146  using base_type::insert;
147  #endif
148 
149  public:
154  explicit hash_map(const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR)
156  Predicate(), eastl::use_first<eastl::pair<const Key, T> >(), allocator)
157  {
158  // Empty
159  }
160 
161 
168  explicit hash_map(size_type nBucketCount, const Hash& hashFunction = Hash(),
169  const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR)
170  : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
171  predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
172  {
173  // Empty
174  }
175 
176 
182  template <typename ForwardIterator>
183  hash_map(ForwardIterator first, ForwardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(),
184  const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR)
185  : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
186  predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
187  {
188  // Empty
189  }
190 
191 
198  insert_return_type insert(const key_type& key)
199  {
200  return base_type::DoInsertKey(key, true_type());
201  }
202 
203 
204  #if defined(__GNUC__) && (__GNUC__ < 3) // If using old GCC (GCC 2.x has a bug which we work around)
205  template <typename InputIterator>
206  void insert(InputIterator first, InputIterator last) { return base_type::insert(first, last); }
207  insert_return_type insert(const value_type& value) { return base_type::insert(value); }
208  iterator insert(const_iterator it, const value_type& value) { return base_type::insert(it, value); }
209  #endif
210 
211 
212  mapped_type& operator[](const key_type& key)
213  {
214  const typename base_type::iterator it = base_type::find(key);
215  if(it != base_type::end())
216  return (*it).second;
217  return (*base_type::insert(value_type(key, mapped_type())).first).second;
218  }
219 
220  }; // hash_map
221 
222 
223 
224 
225 
226 
233  template <typename Key, typename T, typename Hash = eastl::hash<Key>, typename Predicate = eastl::equal_to<Key>,
234  typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false>
236  : public hashtable<Key, eastl::pair<const Key, T>, Allocator, eastl::use_first<eastl::pair<const Key, T> >, Predicate,
237  Hash, mod_range_hashing, default_ranged_hash, prime_rehash_policy, bCacheHashCode, true, false>
238  {
239  public:
240  typedef hashtable<Key, eastl::pair<const Key, T>, Allocator,
242  Predicate, Hash, mod_range_hashing, default_ranged_hash,
243  prime_rehash_policy, bCacheHashCode, true, false> base_type;
245  typedef typename base_type::size_type size_type;
246  typedef typename base_type::key_type key_type;
247  typedef T mapped_type;
248  typedef typename base_type::value_type value_type; // Note that this is pair<const key_type, mapped_type>.
249  typedef typename base_type::allocator_type allocator_type;
250  typedef typename base_type::node_type node_type;
252  typedef typename base_type::iterator iterator;
253 
254  #if !defined(__GNUC__) || (__GNUC__ >= 3) // GCC 2.x has a bug which we work around.
255  using base_type::insert;
256  #endif
257 
258  public:
263  explicit hash_multimap(const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR)
265  Predicate(), eastl::use_first<eastl::pair<const Key, T> >(), allocator)
266  {
267  // Empty
268  }
269 
270 
277  explicit hash_multimap(size_type nBucketCount, const Hash& hashFunction = Hash(),
278  const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR)
279  : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
280  predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
281  {
282  // Empty
283  }
284 
285 
291  template <typename ForwardIterator>
292  hash_multimap(ForwardIterator first, ForwardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(),
293  const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR)
294  : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
295  predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
296  {
297  // Empty
298  }
299 
300 
307  insert_return_type insert(const key_type& key)
308  {
309  return base_type::DoInsertKey(key, false_type());
310  }
311 
312 
313  #if defined(__GNUC__) && (__GNUC__ < 3) // If using old GCC (GCC 2.x has a bug which we work around)
314  template <typename InputIterator>
315  void insert(InputIterator first, InputIterator last) { return base_type::insert(first, last); }
316  insert_return_type insert(const value_type& value) { return base_type::insert(value); }
317  iterator insert(const_iterator it, const value_type& value) { return base_type::insert(it, value); }
318  #endif
319 
320 
321  }; // hash_multimap
322 
323 
324 
325 
326 } // namespace eastl
327 
328 
329 #endif // Header include guard
insert_return_type insert(const key_type &key)
hash_map(ForwardIterator first, ForwardIterator last, size_type nBucketCount=0, const Hash &hashFunction=Hash(), const Predicate &predicate=Predicate(), const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hash_map"))
hash_multimap(size_type nBucketCount, const Hash &hashFunction=Hash(), const Predicate &predicate=Predicate(), const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hash_multimap"))
hash_map(size_type nBucketCount, const Hash &hashFunction=Hash(), const Predicate &predicate=Predicate(), const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hash_map"))
insert_return_type insert(const key_type &key)
hash_map(const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hash_map"))
hash_multimap(const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hash_multimap"))
hash_multimap(ForwardIterator first, ForwardIterator last, size_type nBucketCount=0, const Hash &hashFunction=Hash(), const Predicate &predicate=Predicate(), const allocator_type &allocator=allocator_type(EASTL_DEFAULT_NAME_PREFIX " hash_multimap"))
EA Standard Template Library.