Sierra Toolkit Version of the Day
hash_map_eastl.h
00001 /*
00002 Copyright (C) 2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/hash_map.h
00031 //
00032 // Copyright (c) 2005, Electronic Arts. All rights reserved.
00033 // Written and maintained by Paul Pedriana.
00035 
00037 // This file is based on the TR1 (technical report 1) reference implementation
00038 // of the unordered_set/unordered_map C++ classes as of about 4/2005. Most likely
00039 // many or all C++ library vendors' implementations of this classes will be
00040 // based off of the reference version and so will look pretty similar to this
00041 // file as well as other vendors' versions.
00043 
00044 
00045 #ifndef EASTL_HASH_MAP_H
00046 #define EASTL_HASH_MAP_H
00047 
00048 
00049 #include <stk_util/util/config_eastl.h>
00050 #include <stk_util/util/hashtable_eastl.h>
00051 #include <stk_util/util/functional_eastl.h>
00052 #include <stk_util/util/utility_eastl.h>
00053 
00054 
00055 
00056 namespace eastl
00057 {
00058 
00063     #ifndef EASTL_HASH_MAP_DEFAULT_NAME
00064         #define EASTL_HASH_MAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_map" // Unless the user overrides something, this is "EASTL hash_map".
00065     #endif
00066 
00067 
00072     #ifndef EASTL_HASH_MULTIMAP_DEFAULT_NAME
00073         #define EASTL_HASH_MULTIMAP_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hash_multimap" // Unless the user overrides something, this is "EASTL hash_multimap".
00074     #endif
00075 
00076 
00079     #ifndef EASTL_HASH_MAP_DEFAULT_ALLOCATOR
00080         #define EASTL_HASH_MAP_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MAP_DEFAULT_NAME)
00081     #endif
00082 
00085     #ifndef EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR
00086         #define EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR allocator_type(EASTL_HASH_MULTIMAP_DEFAULT_NAME)
00087     #endif
00088 
00089 
00090 
00124     template <typename Key, typename T, typename Hash = eastl::hash<Key>, typename Predicate = eastl::equal_to<Key>,
00125               typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false>
00126     class hash_map
00127         : public hashtable<Key, eastl::pair<const Key, T>, Allocator, eastl::use_first<eastl::pair<const Key, T> >, Predicate,
00128                             Hash, mod_range_hashing, default_ranged_hash, prime_rehash_policy, bCacheHashCode, true, true>
00129     {
00130     public:
00131         typedef hashtable<Key, eastl::pair<const Key, T>, Allocator,
00132                           eastl::use_first<eastl::pair<const Key, T> >,
00133                           Predicate, Hash, mod_range_hashing, default_ranged_hash,
00134                           prime_rehash_policy, bCacheHashCode, true, true>        base_type;
00135         typedef hash_map<Key, T, Hash, Predicate, Allocator, bCacheHashCode>      this_type;
00136         typedef typename base_type::size_type                                     size_type;
00137         typedef typename base_type::key_type                                      key_type;
00138         typedef T                                                                 mapped_type;
00139         typedef typename base_type::value_type                                    value_type;     // Note that this is pair<const key_type, mapped_type>.
00140         typedef typename base_type::allocator_type                                allocator_type;
00141         typedef typename base_type::node_type                                     node_type;
00142         typedef typename base_type::insert_return_type                            insert_return_type;
00143         typedef typename base_type::iterator                                      iterator;
00144 
00145         #if !defined(__GNUC__) || (__GNUC__ >= 3) // GCC 2.x has a bug which we work around.
00146         using base_type::insert;
00147         #endif
00148 
00149     public:
00154         explicit hash_map(const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR)
00155             : base_type(0, Hash(), mod_range_hashing(), default_ranged_hash(),
00156                         Predicate(), eastl::use_first<eastl::pair<const Key, T> >(), allocator)
00157         {
00158             // Empty
00159         }
00160 
00161 
00168         explicit hash_map(size_type nBucketCount, const Hash& hashFunction = Hash(),
00169                           const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR)
00170             : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
00171                         predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
00172         {
00173             // Empty
00174         }
00175 
00176 
00182         template <typename ForwardIterator>
00183         hash_map(ForwardIterator first, ForwardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(),
00184                  const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MAP_DEFAULT_ALLOCATOR)
00185             : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
00186                         predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
00187         {
00188             // Empty
00189         }
00190 
00191 
00198         insert_return_type insert(const key_type& key)
00199         {
00200             return base_type::DoInsertKey(key, true_type());
00201         }
00202 
00203 
00204         #if defined(__GNUC__) && (__GNUC__ < 3) // If using old GCC (GCC 2.x has a bug which we work around)
00205             template <typename InputIterator>
00206             void               insert(InputIterator first, InputIterator last)    { return base_type::insert(first, last); }
00207             insert_return_type insert(const value_type& value)                    { return base_type::insert(value);       }
00208             iterator           insert(const_iterator it, const value_type& value) { return base_type::insert(it, value);   }
00209         #endif
00210 
00211 
00212         mapped_type& operator[](const key_type& key)
00213         {
00214             const typename base_type::iterator it = base_type::find(key);
00215             if(it != base_type::end())
00216                 return (*it).second;
00217             return (*base_type::insert(value_type(key, mapped_type())).first).second;
00218         }
00219 
00220     }; // hash_map
00221 
00222 
00223 
00224 
00225 
00226 
00233     template <typename Key, typename T, typename Hash = eastl::hash<Key>, typename Predicate = eastl::equal_to<Key>,
00234               typename Allocator = EASTLAllocatorType, bool bCacheHashCode = false>
00235     class hash_multimap
00236         : public hashtable<Key, eastl::pair<const Key, T>, Allocator, eastl::use_first<eastl::pair<const Key, T> >, Predicate,
00237                            Hash, mod_range_hashing, default_ranged_hash, prime_rehash_policy, bCacheHashCode, true, false>
00238     {
00239     public:
00240         typedef hashtable<Key, eastl::pair<const Key, T>, Allocator,
00241                           eastl::use_first<eastl::pair<const Key, T> >,
00242                           Predicate, Hash, mod_range_hashing, default_ranged_hash,
00243                           prime_rehash_policy, bCacheHashCode, true, false>           base_type;
00244         typedef hash_multimap<Key, T, Hash, Predicate, Allocator, bCacheHashCode>     this_type;
00245         typedef typename base_type::size_type                                         size_type;
00246         typedef typename base_type::key_type                                          key_type;
00247         typedef T                                                                     mapped_type;
00248         typedef typename base_type::value_type                                        value_type;     // Note that this is pair<const key_type, mapped_type>.
00249         typedef typename base_type::allocator_type                                    allocator_type;
00250         typedef typename base_type::node_type                                         node_type;
00251         typedef typename base_type::insert_return_type                                insert_return_type;
00252         typedef typename base_type::iterator                                          iterator;
00253 
00254         #if !defined(__GNUC__) || (__GNUC__ >= 3) // GCC 2.x has a bug which we work around.
00255         using base_type::insert;
00256         #endif
00257 
00258     public:
00263         explicit hash_multimap(const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR)
00264             : base_type(0, Hash(), mod_range_hashing(), default_ranged_hash(),
00265                         Predicate(), eastl::use_first<eastl::pair<const Key, T> >(), allocator)
00266         {
00267             // Empty
00268         }
00269 
00270 
00277         explicit hash_multimap(size_type nBucketCount, const Hash& hashFunction = Hash(),
00278                                const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR)
00279             : base_type(nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
00280                         predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
00281         {
00282             // Empty
00283         }
00284 
00285 
00291         template <typename ForwardIterator>
00292         hash_multimap(ForwardIterator first, ForwardIterator last, size_type nBucketCount = 0, const Hash& hashFunction = Hash(),
00293                       const Predicate& predicate = Predicate(), const allocator_type& allocator = EASTL_HASH_MULTIMAP_DEFAULT_ALLOCATOR)
00294             : base_type(first, last, nBucketCount, hashFunction, mod_range_hashing(), default_ranged_hash(),
00295                         predicate, eastl::use_first<eastl::pair<const Key, T> >(), allocator)
00296         {
00297             // Empty
00298         }
00299 
00300 
00307         insert_return_type insert(const key_type& key)
00308         {
00309             return base_type::DoInsertKey(key, false_type());
00310         }
00311 
00312 
00313         #if defined(__GNUC__) && (__GNUC__ < 3) // If using old GCC (GCC 2.x has a bug which we work around)
00314             template <typename InputIterator>
00315             void               insert(InputIterator first, InputIterator last)    { return base_type::insert(first, last); }
00316             insert_return_type insert(const value_type& value)                    { return base_type::insert(value);       }
00317             iterator           insert(const_iterator it, const value_type& value) { return base_type::insert(it, value);   }
00318         #endif
00319 
00320 
00321     }; // hash_multimap
00322 
00323 
00324 
00325 
00326 } // namespace eastl
00327 
00328 
00329 #endif // Header include guard
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends