Sierra Toolkit Version of the Day
hashtable_eastl.h
00001 /*
00002 Copyright (C) 2005,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/internal/hashtable.h
00031 //
00032 // Written and maintained by Paul Pedriana - 2005.
00034 
00036 // This file implements a hashtable, much like the C++ TR1 hash_set/hash_map.
00037 // proposed classes.
00038 // The primary distinctions between this hashtable and TR1 hash tables are:
00039 //    - hashtable is savvy to an environment that doesn't have exception handling,
00040 //      as is sometimes the case with console or embedded environments.
00041 //    - hashtable is slightly more space-efficient than a conventional std hashtable
00042 //      implementation on platforms with 64 bit size_t. This is
00043 //      because std STL uses size_t (64 bits) in data structures whereby 32 bits
00044 //      of data would be fine.
00045 //    - hashtable can contain objects with alignment requirements. TR1 hash tables
00046 //      cannot do so without a bit of tedious non-portable effort.
00047 //    - hashtable supports debug memory naming natively.
00048 //    - hashtable provides a find function that lets you specify a type that is
00049 //      different from the hash table key type. This is particularly useful for
00050 //      the storing of string objects but finding them by char pointers.
00052 
00054 // This file is currently partially based on the TR1 (technical report 1)
00055 // reference implementation of the hash_set/hash_map C++ classes
00056 // as of about 4/2005.
00058 
00059 
00060 #ifndef EASTL_INTERNAL_HASHTABLE_H
00061 #define EASTL_INTERNAL_HASHTABLE_H
00062 
00063 
00064 #include <stk_util/util/config_eastl.h>
00065 #include <stk_util/util/type_traits_eastl.h>
00066 #include <stk_util/util/allocator_eastl.h>
00067 #include <stk_util/util/iterator_eastl.h>
00068 #include <stk_util/util/functional_eastl.h>
00069 #include <stk_util/util/utility_eastl.h>
00070 #include <stk_util/util/algorithm_eastl.h>
00071 #include <string.h>
00072 
00073 #ifdef _MSC_VER
00074     #pragma warning(push, 0)
00075     #include <new>
00076     #include <stddef.h>
00077     #pragma warning(pop)
00078 #else
00079     #include <new>
00080     #include <stddef.h>
00081 #endif
00082 
00083 #ifdef _MSC_VER
00084     #pragma warning(push)
00085     #pragma warning(disable: 4512)  // 'class' : assignment operator could not be generated.
00086     #pragma warning(disable: 4530)  // C++ exception handler used, but unwind semantics are not enabled. Specify /EHsc
00087 #endif
00088 
00089 
00090 namespace eastl
00091 {
00092 
00097     #ifndef EASTL_HASHTABLE_DEFAULT_NAME
00098         #define EASTL_HASHTABLE_DEFAULT_NAME EASTL_DEFAULT_NAME_PREFIX " hashtable" // Unless the user overrides something, this is "EASTL hashtable".
00099     #endif
00100 
00101 
00104     #ifndef EASTL_HASHTABLE_DEFAULT_ALLOCATOR
00105         #define EASTL_HASHTABLE_DEFAULT_ALLOCATOR allocator_type(EASTL_HASHTABLE_DEFAULT_NAME)
00106     #endif
00107 
00108 
00109 
00116     extern EASTL_API void* gpEmptyBucketArray[2];
00117 
00118 
00119 
00128     template <typename Value, bool bCacheHashCode>
00129     struct hash_node;
00130 
00131     template <typename Value>
00132     struct hash_node<Value, true>
00133     {
00134         Value        mValue;
00135         hash_node*   mpNext;
00136         eastl_size_t mnHashCode;      // See config.h for the definition of eastl_size_t, which defaults to uint32_t.
00137     } EASTL_MAY_ALIAS;
00138 
00139     template <typename Value>
00140     struct hash_node<Value, false>
00141     {
00142         Value      mValue;
00143         hash_node* mpNext;
00144     } EASTL_MAY_ALIAS;
00145 
00146 
00147 
00155     template <typename Value, bool bCacheHashCode>
00156     struct node_iterator_base
00157     {
00158     public:
00159         typedef hash_node<Value, bCacheHashCode> node_type;
00160 
00161         node_type* mpNode;
00162 
00163     public:
00164         node_iterator_base(node_type* pNode)
00165             : mpNode(pNode) { }
00166 
00167         void increment()
00168             { mpNode = mpNode->mpNext; }
00169     };
00170 
00171 
00172 
00180     template <typename Value, bool bConst, bool bCacheHashCode>
00181     struct node_iterator : public node_iterator_base<Value, bCacheHashCode>
00182     {
00183     public:
00184         typedef node_iterator_base<Value, bCacheHashCode>                base_type;
00185         typedef node_iterator<Value, bConst, bCacheHashCode>             this_type;
00186         typedef typename base_type::node_type                            node_type;
00187         typedef Value                                                    value_type;
00188         typedef typename type_select<bConst, const Value*, Value*>::type pointer;
00189         typedef typename type_select<bConst, const Value&, Value&>::type reference;
00190         typedef ptrdiff_t                                                difference_type;
00191         typedef EASTL_ITC_NS::forward_iterator_tag                       iterator_category;
00192 
00193     public:
00194         explicit node_iterator(node_type* pNode = NULL)
00195             : base_type(pNode) { }
00196 
00197         node_iterator(const node_iterator<Value, true, bCacheHashCode>& x)
00198             : base_type(x.mpNode) { }
00199 
00200         reference operator*() const
00201             { return base_type::mpNode->mValue; }
00202 
00203         pointer operator->() const
00204             { return &(base_type::mpNode->mValue); }
00205 
00206         node_iterator& operator++()
00207             { base_type::increment(); return *this; }
00208 
00209         node_iterator operator++(int)
00210             { node_iterator temp(*this); base_type::increment(); return temp; }
00211 
00212     }; // node_iterator
00213 
00214 
00215 
00226     template <typename Value, bool bCacheHashCode>
00227     struct hashtable_iterator_base
00228     {
00229     public:
00230         typedef hash_node<Value, bCacheHashCode> node_type;
00231 
00232     public:
00233         // We use public here because it allows the hashtable class to access
00234         // these without a function call, and we are very strongly avoiding
00235         // function calls in this library, as our primary goal is performance
00236         // over correctness and some compilers (e.g. GCC) are terrible at
00237         // inlining and so avoiding function calls is of major importance.
00238         node_type*  mpNode;      // Current node within current bucket.
00239         node_type** mpBucket;    // Current bucket.
00240 
00241     public:
00242         hashtable_iterator_base(node_type* pNode, node_type** pBucket)
00243             : mpNode(pNode), mpBucket(pBucket) { }
00244 
00245         void increment_bucket()
00246         {
00247             ++mpBucket;
00248             while(*mpBucket == NULL) // We store an extra bucket with some non-NULL value at the end
00249                 ++mpBucket;          // of the bucket array so that finding the end of the bucket
00250             mpNode = *mpBucket;      // array is quick and simple.
00251         }
00252 
00253         void increment()
00254         {
00255             mpNode = mpNode->mpNext;
00256 
00257             while(mpNode == NULL)
00258                 mpNode = *++mpBucket;
00259         }
00260 
00261     }; // hashtable_iterator_base
00262 
00263 
00264 
00265 
00276     template <typename Value, bool bConst, bool bCacheHashCode>
00277     struct hashtable_iterator : public hashtable_iterator_base<Value, bCacheHashCode>
00278     {
00279     public:
00280         typedef hashtable_iterator_base<Value, bCacheHashCode>           base_type;
00281         typedef hashtable_iterator<Value, bConst, bCacheHashCode>        this_type;
00282         typedef hashtable_iterator<Value, false, bCacheHashCode>         this_type_non_const;
00283         typedef typename base_type::node_type                            node_type;
00284         typedef Value                                                    value_type;
00285         typedef typename type_select<bConst, const Value*, Value*>::type pointer;
00286         typedef typename type_select<bConst, const Value&, Value&>::type reference;
00287         typedef ptrdiff_t                                                difference_type;
00288         typedef EASTL_ITC_NS::forward_iterator_tag                       iterator_category;
00289 
00290     public:
00291         hashtable_iterator(node_type* pNode = NULL, node_type** pBucket = NULL)
00292             : base_type(pNode, pBucket) { }
00293 
00294         hashtable_iterator(node_type** pBucket)
00295             : base_type(*pBucket, pBucket) { }
00296 
00297         hashtable_iterator(const this_type_non_const& x)
00298             : base_type(x.mpNode, x.mpBucket) { }
00299 
00300         reference operator*() const
00301             { return base_type::mpNode->mValue; }
00302 
00303         pointer operator->() const
00304             { return &(base_type::mpNode->mValue); }
00305 
00306         hashtable_iterator& operator++()
00307             { base_type::increment(); return *this; }
00308 
00309         hashtable_iterator operator++(int)
00310             { hashtable_iterator temp(*this); base_type::increment(); return temp; }
00311 
00312         const node_type* get_node() const
00313             { return base_type::mpNode; }
00314 
00315     }; // hashtable_iterator
00316 
00317 
00318 
00319 
00330     template <typename Iterator>
00331     inline typename eastl::iterator_traits<Iterator>::difference_type
00332     distance_fw_impl(Iterator first, Iterator last, EASTL_ITC_NS::input_iterator_tag)
00333         { return 0; }
00334 
00335     template <typename Iterator>
00336     inline typename eastl::iterator_traits<Iterator>::difference_type
00337     distance_fw_impl(Iterator first, Iterator last, EASTL_ITC_NS::forward_iterator_tag)
00338         { return eastl::distance(first, last); }
00339 
00340     template <typename Iterator>
00341     inline typename eastl::iterator_traits<Iterator>::difference_type
00342     ht_distance(Iterator first, Iterator last)
00343     {
00344         typedef typename eastl::iterator_traits<Iterator>::iterator_category IC;
00345         return distance_fw_impl(first, last, IC());
00346     }
00347 
00348 
00349 
00350 
00356     struct mod_range_hashing
00357     {
00358         // Defined as eastl_size_t instead of size_t because the latter
00359         // wastes memory and is sometimes slower on 64 bit machines.
00360         uint32_t operator()(uint32_t r, uint32_t n) const
00361             { return r % n; }
00362     };
00363 
00364 
00373     struct default_ranged_hash{ };
00374 
00375 
00381     struct EASTL_API prime_rehash_policy
00382     {
00383     public:
00384         float            mfMaxLoadFactor;
00385         float            mfGrowthFactor;
00386         mutable uint32_t mnNextResize;
00387 
00388     public:
00389         prime_rehash_policy(float fMaxLoadFactor = 1.f)
00390             : mfMaxLoadFactor(fMaxLoadFactor), mfGrowthFactor(2.f), mnNextResize(0) { }
00391 
00392         float GetMaxLoadFactor() const
00393             { return mfMaxLoadFactor; }
00394 
00397         static uint32_t GetPrevBucketCountOnly(uint32_t nBucketCountHint);
00398 
00401         uint32_t GetPrevBucketCount(uint32_t nBucketCountHint) const;
00402 
00405         uint32_t GetNextBucketCount(uint32_t nBucketCountHint) const;
00406 
00409         uint32_t GetBucketCount(uint32_t nElementCount) const;
00410 
00415         eastl::pair<bool, uint32_t>
00416         GetRehashRequired(uint32_t nBucketCount, uint32_t nElementCount, uint32_t nElementAdd) const;
00417     };
00418 
00419 
00420 
00421 
00422 
00424     // Base classes for hashtable. We define these base classes because
00425     // in some cases we want to do different things depending on the
00426     // value of a policy class. In some cases the policy class affects
00427     // which member functions and nested typedefs are defined; we handle that
00428     // by specializing base class templates. Several of the base class templates
00429     // need to access other members of class template hashtable, so we use
00430     // the "curiously recurring template pattern" (parent class is templated
00431     // on type of child class) for them.
00433 
00434 
00440     template <typename RehashPolicy, typename Hashtable>
00441     struct rehash_base { };
00442 
00443     template <typename Hashtable>
00444     struct rehash_base<prime_rehash_policy, Hashtable>
00445     {
00446         // Returns the max load factor, which is the load factor beyond
00447         // which we rebuild the container with a new bucket count.
00448         float get_max_load_factor() const
00449         {
00450             const Hashtable* const pThis = static_cast<const Hashtable*>(this);
00451             return pThis->rehash_policy().GetMaxLoadFactor();
00452         }
00453 
00454         // If you want to make the hashtable never rehash (resize),
00455         // set the max load factor to be a very high number (e.g. 100000.f).
00456         void set_max_load_factor(float fMaxLoadFactor)
00457         {
00458             Hashtable* const pThis = static_cast<Hashtable*>(this);
00459             pThis->rehash_policy(prime_rehash_policy(fMaxLoadFactor));
00460         }
00461     };
00462 
00463 
00464 
00465 
00480     template <typename Key, typename Value, typename ExtractKey, typename Equal,
00481               typename H1, typename H2, typename H, bool bCacheHashCode>
00482     struct hash_code_base;
00483 
00484 
00490     template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2, typename H>
00491     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false>
00492     {
00493     protected:
00494         ExtractKey  mExtractKey;    // To do: Make this member go away entirely, as it never has any data.
00495         Equal       mEqual;         // To do: Make this instance use zero space when it is zero size.
00496         H           mRangedHash;    // To do: Make this instance use zero space when it is zero size
00497 
00498     public:
00499         H1 hash_function() const
00500             { return H1(); }
00501 
00502         Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard
00503             { return mEqual; }       // has specified in its hashtable (unordered_*) proposal.
00504 
00505         const Equal& key_eq() const
00506             { return mEqual; }
00507 
00508         Equal& key_eq()
00509             { return mEqual; }
00510 
00511     protected:
00512         typedef void*    hash_code_t;
00513         typedef uint32_t bucket_index_t;
00514 
00515         hash_code_base(const ExtractKey& extractKey, const Equal& eq, const H1&, const H2&, const H& h)
00516             : mExtractKey(extractKey), mEqual(eq), mRangedHash(h) { }
00517 
00518         hash_code_t get_hash_code(const Key& key) const
00519             { return NULL; }
00520 
00521         bucket_index_t bucket_index(hash_code_t, uint32_t) const
00522             { return (bucket_index_t)0; }
00523 
00524         bucket_index_t bucket_index(const Key& key, hash_code_t, uint32_t nBucketCount) const
00525             { return (bucket_index_t)mRangedHash(key, nBucketCount); }
00526 
00527         bucket_index_t bucket_index(const hash_node<Value, false>* pNode, uint32_t nBucketCount) const
00528             { return (bucket_index_t)mRangedHash(mExtractKey(pNode->mValue), nBucketCount); }
00529 
00530         bool compare(const Key& key, hash_code_t, hash_node<Value, false>* pNode) const
00531             { return mEqual(key, mExtractKey(pNode->mValue)); }
00532 
00533         void copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
00534             { } // Nothing to do.
00535 
00536         void set_code(hash_node<Value, false>* pDest, hash_code_t c) const
00537             { } // Nothing to do.
00538 
00539         void base_swap(hash_code_base& x)
00540         {
00541             eastl::swap(mExtractKey, x.mExtractKey);
00542             eastl::swap(mEqual,      x.mEqual);
00543             eastl::swap(mRangedHash, x.mRangedHash);
00544         }
00545 
00546     }; // hash_code_base
00547 
00548 
00549 
00550     // No specialization for ranged hash function while caching hash codes.
00551     // That combination is meaningless, and trying to do it is an error.
00552 
00553 
00560     template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2, typename H>
00561     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>;
00562 
00563 
00564 
00571     template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2>
00572     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, false>
00573     {
00574     protected:
00575         ExtractKey  mExtractKey;
00576         Equal       mEqual;
00577         H1          m_h1;
00578         H2          m_h2;
00579 
00580     public:
00581         typedef H1 hasher;
00582 
00583         H1 hash_function() const
00584             { return m_h1; }
00585 
00586         Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard
00587             { return mEqual; }       // has specified in its hashtable (unordered_*) proposal.
00588 
00589         const Equal& key_eq() const
00590             { return mEqual; }
00591 
00592         Equal& key_eq()
00593             { return mEqual; }
00594 
00595     protected:
00596         typedef uint32_t hash_code_t;
00597         typedef uint32_t bucket_index_t;
00598         typedef hash_node<Value, false> node_type;
00599 
00600         hash_code_base(const ExtractKey& ex, const Equal& eq, const H1& h1, const H2& h2, const default_ranged_hash&)
00601             : mExtractKey(ex), mEqual(eq), m_h1(h1), m_h2(h2) { }
00602 
00603         hash_code_t get_hash_code(const Key& key) const
00604             { return (hash_code_t)m_h1(key); }
00605 
00606         bucket_index_t bucket_index(hash_code_t c, uint32_t nBucketCount) const
00607             { return (bucket_index_t)m_h2(c, nBucketCount); }
00608 
00609         bucket_index_t bucket_index(const Key&, hash_code_t c, uint32_t nBucketCount) const
00610             { return (bucket_index_t)m_h2(c, nBucketCount); }
00611 
00612         bucket_index_t bucket_index(const node_type* pNode, uint32_t nBucketCount) const
00613             { return (bucket_index_t)m_h2((hash_code_t)m_h1(mExtractKey(pNode->mValue)), nBucketCount); }
00614 
00615         bool compare(const Key& key, hash_code_t, node_type* pNode) const
00616             { return mEqual(key, mExtractKey(pNode->mValue)); }
00617 
00618         void copy_code(node_type*, const node_type*) const
00619             { } // Nothing to do.
00620 
00621         void set_code(node_type*, hash_code_t) const
00622             { } // Nothing to do.
00623 
00624         void base_swap(hash_code_base& x)
00625         {
00626             eastl::swap(mExtractKey, x.mExtractKey);
00627             eastl::swap(mEqual,      x.mEqual);
00628             eastl::swap(m_h1,        x.m_h1);
00629             eastl::swap(m_h2,        x.m_h2);
00630         }
00631 
00632     }; // hash_code_base
00633 
00634 
00635 
00642     template <typename Key, typename Value, typename ExtractKey, typename Equal, typename H1, typename H2>
00643     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, true>
00644     {
00645     protected:
00646         ExtractKey  mExtractKey;
00647         Equal       mEqual;
00648         H1          m_h1;
00649         H2          m_h2;
00650 
00651     public:
00652         typedef H1 hasher;
00653 
00654         H1 hash_function() const
00655             { return m_h1; }
00656 
00657         Equal equal_function() const // Deprecated. Use key_eq() instead, as key_eq is what the new C++ standard
00658             { return mEqual; }       // has specified in its hashtable (unordered_*) proposal.
00659 
00660         const Equal& key_eq() const
00661             { return mEqual; }
00662 
00663         Equal& key_eq()
00664             { return mEqual; }
00665 
00666     protected:
00667         typedef uint32_t hash_code_t;
00668         typedef uint32_t bucket_index_t;
00669         typedef hash_node<Value, true> node_type;
00670 
00671         hash_code_base(const ExtractKey& ex, const Equal& eq, const H1& h1, const H2& h2, const default_ranged_hash&)
00672             : mExtractKey(ex), mEqual(eq), m_h1(h1), m_h2(h2) { }
00673 
00674         hash_code_t get_hash_code(const Key& key) const
00675             { return (hash_code_t)m_h1(key); }
00676 
00677         bucket_index_t bucket_index(hash_code_t c, uint32_t nBucketCount) const
00678             { return (bucket_index_t)m_h2(c, nBucketCount); }
00679 
00680         bucket_index_t bucket_index(const Key&, hash_code_t c, uint32_t nBucketCount) const
00681             { return (bucket_index_t)m_h2(c, nBucketCount); }
00682 
00683         bucket_index_t bucket_index(const node_type* pNode, uint32_t nBucketCount) const
00684             { return (bucket_index_t)m_h2((uint32_t)pNode->mnHashCode, nBucketCount); }
00685 
00686         bool compare(const Key& key, hash_code_t c, node_type* pNode) const
00687             { return (pNode->mnHashCode == c) && mEqual(key, mExtractKey(pNode->mValue)); }
00688 
00689         void copy_code(node_type* pDest, const node_type* pSource) const
00690             { pDest->mnHashCode = pSource->mnHashCode; }
00691 
00692         void set_code(node_type* pDest, hash_code_t c) const
00693             { pDest->mnHashCode = c; }
00694 
00695         void base_swap(hash_code_base& x)
00696         {
00697             eastl::swap(mExtractKey, x.mExtractKey);
00698             eastl::swap(mEqual,      x.mEqual);
00699             eastl::swap(m_h1,        x.m_h1);
00700             eastl::swap(m_h2,        x.m_h2);
00701         }
00702 
00703     }; // hash_code_base
00704 
00705 
00706 
00707 
00708 
00785     template <typename Key, typename Value, typename Allocator, typename ExtractKey,
00786               typename Equal, typename H1, typename H2, typename H,
00787               typename RehashPolicy, bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>
00788     class hashtable
00789         :   public rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys> >,
00790             public hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode>
00791     {
00792     public:
00793         typedef Key                                                                                 key_type;
00794         typedef Value                                                                               value_type;
00795         typedef typename ExtractKey::result_type                                                    mapped_type;
00796         typedef hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode>            hash_code_base_type;
00797         typedef typename hash_code_base_type::hash_code_t                                           hash_code_t;
00798         typedef Allocator                                                                           allocator_type;
00799         typedef Equal                                                                               key_equal;
00800         typedef ptrdiff_t                                                                           difference_type;
00801         typedef eastl_size_t                                                                        size_type;     // See config.h for the definition of eastl_size_t, which defaults to uint32_t.
00802         typedef value_type&                                                                         reference;
00803         typedef const value_type&                                                                   const_reference;
00804         typedef node_iterator<value_type, !bMutableIterators, bCacheHashCode>                       local_iterator;
00805         typedef node_iterator<value_type, true,               bCacheHashCode>                       const_local_iterator;
00806         typedef hashtable_iterator<value_type, !bMutableIterators, bCacheHashCode>                  iterator;
00807         typedef hashtable_iterator<value_type, true,               bCacheHashCode>                  const_iterator;
00808         typedef eastl::reverse_iterator<iterator>                                                   reverse_iterator;
00809         typedef eastl::reverse_iterator<const_iterator>                                             const_reverse_iterator;
00810         typedef hash_node<value_type, bCacheHashCode>                                               node_type;
00811         typedef typename type_select<bUniqueKeys, eastl::pair<iterator, bool>, iterator>::type      insert_return_type;
00812         typedef hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H,
00813                             RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys>           this_type;
00814         typedef RehashPolicy                                                                        rehash_policy_type;
00815         typedef ExtractKey                                                                          extract_key_type;
00816         typedef H1                                                                                  h1_type;
00817         typedef H2                                                                                  h2_type;
00818         typedef H                                                                                   h_type;
00819 
00820         using hash_code_base_type::key_eq;
00821         using hash_code_base_type::hash_function;
00822         using hash_code_base_type::mExtractKey;
00823         using hash_code_base_type::get_hash_code;
00824         using hash_code_base_type::bucket_index;
00825         using hash_code_base_type::compare;
00826         using hash_code_base_type::set_code;
00827 
00828         static const bool kCacheHashCode = bCacheHashCode;
00829 
00830         enum
00831         {
00832             kKeyAlignment         = EASTL_ALIGN_OF(key_type),
00833             kKeyAlignmentOffset   = 0,                          // To do: Make sure this really is zero for all uses of this template.
00834             kValueAlignment       = EASTL_ALIGN_OF(value_type),
00835             kValueAlignmentOffset = 0,                          // To fix: This offset is zero for sets and >0 for maps. Need to fix this.
00836             kAllocFlagBuckets     = 0x00400000                  // Flag to allocator which indicates that we are allocating buckets and not nodes.
00837         };
00838 
00839     protected:
00840         node_type**     mpBucketArray;
00841         size_type       mnBucketCount;
00842         size_type       mnElementCount;
00843         RehashPolicy    mRehashPolicy;  // To do: Use base class optimization to make this go away.
00844         allocator_type  mAllocator;     // To do: Use base class optimization to make this go away.
00845 
00846     public:
00847         hashtable(size_type nBucketCount, const H1&, const H2&, const H&, const Equal&, const ExtractKey&,
00848                   const allocator_type& allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR);
00849 
00850         template <typename FowardIterator>
00851         hashtable(FowardIterator first, FowardIterator last, size_type nBucketCount,
00852                   const H1&, const H2&, const H&, const Equal&, const ExtractKey&,
00853                   const allocator_type& allocator = EASTL_HASHTABLE_DEFAULT_ALLOCATOR); // allocator arg removed because VC7.1 fails on the default arg. To do: Make a second version of this function without a default arg.
00854 
00855         hashtable(const hashtable& x);
00856        ~hashtable();
00857 
00858         allocator_type& get_allocator();
00859         void            set_allocator(const allocator_type& allocator);
00860 
00861         this_type& operator=(const this_type& x);
00862 
00863         void swap(this_type& x);
00864 
00865     public:
00866         iterator begin()
00867         {
00868             iterator i(mpBucketArray);
00869             if(!i.mpNode)
00870                 i.increment_bucket();
00871             return i;
00872         }
00873 
00874         const_iterator begin() const
00875         {
00876             const_iterator i(mpBucketArray);
00877             if(!i.mpNode)
00878                 i.increment_bucket();
00879             return i;
00880         }
00881 
00882         iterator end()
00883             { return iterator(mpBucketArray + mnBucketCount); }
00884 
00885         const_iterator end() const
00886             { return const_iterator(mpBucketArray + mnBucketCount); }
00887 
00888         local_iterator begin(size_type n)
00889             { return local_iterator(mpBucketArray[n]); }
00890 
00891         local_iterator end(size_type)
00892             { return local_iterator(NULL); }
00893 
00894         const_local_iterator begin(size_type n) const
00895             { return const_local_iterator(mpBucketArray[n]); }
00896 
00897         const_local_iterator end(size_type) const
00898             { return const_local_iterator(NULL); }
00899 
00900         bool empty() const
00901         { return mnElementCount == 0; }
00902 
00903         size_type size() const
00904         { return mnElementCount; }
00905 
00906         size_type bucket_count() const
00907         { return mnBucketCount; }
00908 
00909         size_type bucket_size(size_type n) const
00910         { return (size_type)eastl::distance(begin(n), end(n)); }
00911 
00912         //size_type bucket(const key_type& k) const
00913         //    { return bucket_index(k, (hash code here), (uint32_t)mnBucketCount); }
00914 
00915     public:
00916         float load_factor() const
00917             { return (float)mnElementCount / (float)mnBucketCount; }
00918 
00919         // Inherited from the base class.
00920         // Returns the max load factor, which is the load factor beyond
00921         // which we rebuild the container with a new bucket count.
00922         // get_max_load_factor comes from rehash_base.
00923         //    float get_max_load_factor() const;
00924 
00925         // Inherited from the base class.
00926         // If you want to make the hashtable never rehash (resize),
00927         // set the max load factor to be a very high number (e.g. 100000.f).
00928         // set_max_load_factor comes from rehash_base.
00929         //    void set_max_load_factor(float fMaxLoadFactor);
00930 
00933         const rehash_policy_type& rehash_policy() const
00934             { return mRehashPolicy; }
00935 
00938         void rehash_policy(const rehash_policy_type& rehashPolicy);
00939 
00940     public:
00941 
00942         insert_return_type insert(const value_type& value);
00943         iterator           insert(const_iterator, const value_type& value);
00944 
00945         template <typename InputIterator>
00946         void insert(InputIterator first, InputIterator last);
00947 
00948     public:
00949         iterator         erase(iterator position);
00950         iterator         erase(iterator first, iterator last);
00951         reverse_iterator erase(reverse_iterator position);
00952         reverse_iterator erase(reverse_iterator first, reverse_iterator last);
00953         size_type        erase(const key_type& k);
00954 
00955         void clear();
00956         void clear(bool clearBuckets);
00957         void reset();
00958         void rehash(size_type nBucketCount);
00959 
00960     public:
00961         iterator       find(const key_type& key);
00962         const_iterator find(const key_type& key) const;
00963 
00979         template <typename U, typename UHash, typename BinaryPredicate>
00980         iterator       find_as(const U& u, UHash uhash, BinaryPredicate predicate);
00981 
00982         template <typename U, typename UHash, typename BinaryPredicate>
00983         const_iterator find_as(const U& u, UHash uhash, BinaryPredicate predicate) const;
00984 
00985         template <typename U>
00986         iterator       find_as(const U& u);
00987 
00988         template <typename U>
00989         const_iterator find_as(const U& u) const;
00990 
00993         iterator       find_by_hash(hash_code_t c);
00994         const_iterator find_by_hash(hash_code_t c) const;
00995 
00996         size_type      count(const key_type& k) const;
00997 
00998         eastl::pair<iterator, iterator>             equal_range(const key_type& k);
00999         eastl::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
01000 
01001     public:
01002         bool validate() const;
01003         int  validate_iterator(const_iterator i) const;
01004 
01005     protected:
01006         node_type*  DoAllocateNode(const value_type& value);
01007         node_type*  DoAllocateNodeFromKey(const key_type& key);
01008         void        DoFreeNode(node_type* pNode);
01009         void        DoFreeNodes(node_type** pBucketArray, size_type);
01010 
01011         node_type** DoAllocateBuckets(size_type n);
01012         void        DoFreeBuckets(node_type** pBucketArray, size_type n);
01013 
01014         eastl::pair<iterator, bool>        DoInsertValue(const value_type& value, true_type);
01015         iterator                           DoInsertValue(const value_type& value, false_type);
01016 
01017         eastl::pair<iterator, bool>        DoInsertKey(const key_type& key, true_type);
01018         iterator                           DoInsertKey(const key_type& key, false_type);
01019 
01020         void       DoRehash(size_type nBucketCount);
01021         node_type* DoFindNode(node_type* pNode, const key_type& k, hash_code_t c) const;
01022 
01023         template <typename U, typename BinaryPredicate>
01024         node_type* DoFindNode(node_type* pNode, const U& u, BinaryPredicate predicate) const;
01025 
01026         node_type* DoFindNode(node_type* pNode, hash_code_t c) const;
01027 
01028     }; // class hashtable
01029 
01030 
01031 
01032 
01033 
01035     // node_iterator_base
01037 
01038     template <typename Value, bool bCacheHashCode>
01039     inline bool operator==(const node_iterator_base<Value, bCacheHashCode>& a, const node_iterator_base<Value, bCacheHashCode>& b)
01040         { return a.mpNode == b.mpNode; }
01041 
01042     template <typename Value, bool bCacheHashCode>
01043     inline bool operator!=(const node_iterator_base<Value, bCacheHashCode>& a, const node_iterator_base<Value, bCacheHashCode>& b)
01044         { return a.mpNode != b.mpNode; }
01045 
01046 
01047 
01048 
01050     // hashtable_iterator_base
01052 
01053     template <typename Value, bool bCacheHashCode>
01054     inline bool operator==(const hashtable_iterator_base<Value, bCacheHashCode>& a, const hashtable_iterator_base<Value, bCacheHashCode>& b)
01055         { return a.mpNode == b.mpNode; }
01056 
01057     template <typename Value, bool bCacheHashCode>
01058     inline bool operator!=(const hashtable_iterator_base<Value, bCacheHashCode>& a, const hashtable_iterator_base<Value, bCacheHashCode>& b)
01059         { return a.mpNode != b.mpNode; }
01060 
01061 
01062 
01063 
01065     // hashtable
01067 
01068     template <typename K, typename V, typename A, typename EK, typename Eq,
01069               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01070     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>
01071     ::hashtable(size_type nBucketCount, const H1& h1, const H2& h2, const H& h,
01072                 const Eq& eq, const EK& ek, const allocator_type& allocator)
01073         :   rehash_base<RP, hashtable>(),
01074             hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(ek, eq, h1, h2, h),
01075             mnBucketCount(0),
01076             mnElementCount(0),
01077             mRehashPolicy(),
01078             mAllocator(allocator)
01079     {
01080         if(nBucketCount < 2)  // If we are starting in an initially empty state, with no memory allocation done.
01081             reset();
01082         else // Else we are creating a potentially non-empty hashtable...
01083         {
01084             EASTL_ASSERT(nBucketCount < 10000000);
01085             mnBucketCount = (size_type)mRehashPolicy.GetNextBucketCount((uint32_t)nBucketCount);
01086             mpBucketArray = DoAllocateBuckets(mnBucketCount); // mnBucketCount will always be at least 2.
01087         }
01088     }
01089 
01090 
01091 
01092     template <typename K, typename V, typename A, typename EK, typename Eq,
01093               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01094     template <typename FowardIterator>
01095     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(FowardIterator first, FowardIterator last, size_type nBucketCount,
01096                                                                      const H1& h1, const H2& h2, const H& h,
01097                                                                      const Eq& eq, const EK& ek, const allocator_type& allocator)
01098         :   rehash_base<rehash_policy_type, hashtable>(),
01099             hash_code_base<key_type, value_type, extract_key_type, key_equal, h1_type, h2_type, h_type, kCacheHashCode>(ek, eq, h1, h2, h),
01100           //mnBucketCount(0), // This gets re-assigned below.
01101             mnElementCount(0),
01102             mRehashPolicy(),
01103             mAllocator(allocator)
01104     {
01105         if(nBucketCount < 2)
01106         {
01107             const size_type nElementCount = (size_type)eastl::ht_distance(first, last);
01108             mnBucketCount = (size_type)mRehashPolicy.GetBucketCount((uint32_t)nElementCount);
01109         }
01110         else
01111         {
01112             EASTL_ASSERT(nBucketCount < 10000000);
01113             mnBucketCount = nBucketCount;
01114         }
01115 
01116         mpBucketArray = DoAllocateBuckets(mnBucketCount); // mnBucketCount will always be at least 2.
01117 
01118         #if EASTL_EXCEPTIONS_ENABLED
01119             try
01120             {
01121         #endif
01122                 for(; first != last; ++first)
01123                     insert(*first);
01124         #if EASTL_EXCEPTIONS_ENABLED
01125             }
01126             catch(...)
01127             {
01128                 clear();
01129                 DoFreeBuckets(mpBucketArray, mnBucketCount);
01130                 throw;
01131             }
01132         #endif
01133     }
01134 
01135 
01136 
01137     template <typename K, typename V, typename A, typename EK, typename Eq,
01138               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01139     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::hashtable(const this_type& x)
01140         :   rehash_base<RP, hashtable>(x),
01141             hash_code_base<K, V, EK, Eq, H1, H2, H, bC>(x),
01142             mnBucketCount(x.mnBucketCount),
01143             mnElementCount(x.mnElementCount),
01144             mRehashPolicy(x.mRehashPolicy),
01145             mAllocator(x.mAllocator)
01146     {
01147         if(mnElementCount) // If there is anything to copy...
01148         {
01149             mpBucketArray = DoAllocateBuckets(mnBucketCount); // mnBucketCount will be at least 2.
01150 
01151             #if EASTL_EXCEPTIONS_ENABLED
01152                 try
01153                 {
01154             #endif
01155                     for(size_type i = 0; i < x.mnBucketCount; ++i)
01156                     {
01157                         node_type*  pNodeSource = x.mpBucketArray[i];
01158                         node_type** ppNodeDest  = mpBucketArray + i;
01159 
01160                         while(pNodeSource)
01161                         {
01162                             *ppNodeDest = DoAllocateNode(pNodeSource->mValue);
01163                             copy_code(*ppNodeDest, pNodeSource);
01164                             ppNodeDest = &(*ppNodeDest)->mpNext;
01165                             pNodeSource = pNodeSource->mpNext;
01166                         }
01167                     }
01168             #if EASTL_EXCEPTIONS_ENABLED
01169                 }
01170                 catch(...)
01171                 {
01172                     clear();
01173                     DoFreeBuckets(mpBucketArray, mnBucketCount);
01174                     throw;
01175                 }
01176             #endif
01177         }
01178         else
01179         {
01180             // In this case, instead of allocate memory and copy nothing from x,
01181             // we reset ourselves to a zero allocation state.
01182             reset();
01183         }
01184     }
01185 
01186 
01187 
01188     template <typename K, typename V, typename A, typename EK, typename Eq,
01189               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01190     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::allocator_type&
01191     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::get_allocator()
01192     {
01193         return mAllocator;
01194     }
01195 
01196 
01197 
01198     template <typename K, typename V, typename A, typename EK, typename Eq,
01199               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01200     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::set_allocator(const allocator_type& allocator)
01201     {
01202         mAllocator = allocator;
01203     }
01204 
01205 
01206 
01207     template <typename K, typename V, typename A, typename EK, typename Eq,
01208               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01209     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::this_type&
01210     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::operator=(const this_type& x)
01211     {
01212         if(this != &x)
01213         {
01214             clear();
01215 
01216             #if EASTL_ALLOCATOR_COPY_ENABLED
01217                 mAllocator = x.mAllocator;
01218             #endif
01219 
01220             insert(x.begin(), x.end());
01221         }
01222         return *this;
01223     }
01224 
01225 
01226 
01227     template <typename K, typename V, typename A, typename EK, typename Eq,
01228               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01229     inline hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::~hashtable()
01230     {
01231         clear();
01232         DoFreeBuckets(mpBucketArray, mnBucketCount);
01233     }
01234 
01235 
01236 
01237     template <typename K, typename V, typename A, typename EK, typename Eq,
01238               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01239     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
01240     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNode(const value_type& value)
01241     {
01242         node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), kValueAlignment, kValueAlignmentOffset);
01243 
01244         #if EASTL_EXCEPTIONS_ENABLED
01245             try
01246             {
01247         #endif
01248                 ::new(&pNode->mValue) value_type(value);
01249                 pNode->mpNext = NULL;
01250                 return pNode;
01251         #if EASTL_EXCEPTIONS_ENABLED
01252             }
01253             catch(...)
01254             {
01255                 EASTLFree(mAllocator, pNode, sizeof(node_type));
01256                 throw;
01257             }
01258         #endif
01259     }
01260 
01261 
01262 
01263     template <typename K, typename V, typename A, typename EK, typename Eq,
01264               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01265     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
01266     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateNodeFromKey(const key_type& key)
01267     {
01268         node_type* const pNode = (node_type*)allocate_memory(mAllocator, sizeof(node_type), kValueAlignment, kValueAlignmentOffset);
01269 
01270         #if EASTL_EXCEPTIONS_ENABLED
01271             try
01272             {
01273         #endif
01274                 ::new(&pNode->mValue) value_type(key);
01275                 pNode->mpNext = NULL;
01276                 return pNode;
01277         #if EASTL_EXCEPTIONS_ENABLED
01278             }
01279             catch(...)
01280             {
01281                 EASTLFree(mAllocator, pNode, sizeof(node_type));
01282                 throw;
01283             }
01284         #endif
01285     }
01286 
01287 
01288 
01289     template <typename K, typename V, typename A, typename EK, typename Eq,
01290               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01291     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeNode(node_type* pNode)
01292     {
01293         pNode->~node_type();
01294         EASTLFree(mAllocator, pNode, sizeof(node_type));
01295     }
01296 
01297 
01298 
01299     template <typename K, typename V, typename A, typename EK, typename Eq,
01300               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01301     void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeNodes(node_type** pNodeArray, size_type n)
01302     {
01303         for(size_type i = 0; i < n; ++i)
01304         {
01305             node_type* pNode = pNodeArray[i];
01306             while(pNode)
01307             {
01308                 node_type* const pTempNode = pNode;
01309                 pNode = pNode->mpNext;
01310                 DoFreeNode(pTempNode);
01311             }
01312             pNodeArray[i] = NULL;
01313         }
01314     }
01315 
01316 
01317 
01318     template <typename K, typename V, typename A, typename EK, typename Eq,
01319               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01320     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type**
01321     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoAllocateBuckets(size_type n)
01322     {
01323         // We allocate one extra bucket to hold a sentinel, an arbitrary
01324         // non-null pointer. Iterator increment relies on this.
01325         EASTL_ASSERT(n > 1); // We reserve an mnBucketCount of 1 for the shared gpEmptyBucketArray.
01326         EASTL_CT_ASSERT(kAllocFlagBuckets == 0x00400000); // Currently we expect this to be so, because the allocator has a copy of this enum.
01327         node_type** const pBucketArray = (node_type**)EASTLAllocFlags(mAllocator, (n + 1) * sizeof(node_type*), kAllocFlagBuckets);
01328         //eastl::fill(pBucketArray, pBucketArray + n, (node_type*)NULL);
01329         memset(pBucketArray, 0, n * sizeof(node_type*));
01330         pBucketArray[n] = reinterpret_cast<node_type*>((uintptr_t)~0);
01331         return pBucketArray;
01332     }
01333 
01334 
01335 
01336     template <typename K, typename V, typename A, typename EK, typename Eq,
01337               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01338     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFreeBuckets(node_type** pBucketArray, size_type n)
01339     {
01340         // If n <= 1, then pBucketArray is from the shared gpEmptyBucketArray. We don't test
01341         // for pBucketArray == &gpEmptyBucketArray because one library have a different gpEmptyBucketArray
01342         // than another but pass a hashtable to another. So we go by the size.
01343         if(n > 1)
01344             EASTLFree(mAllocator, pBucketArray, (n + 1) * sizeof(node_type*)); // '+1' because DoAllocateBuckets allocates nBucketCount + 1 buckets in order to have a NULL sentinel at the end.
01345     }
01346 
01347 
01348 
01349     template <typename K, typename V, typename A, typename EK, typename Eq,
01350               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01351     void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::swap(this_type& x)
01352     {
01353         if(mAllocator == x.mAllocator) // If allocators are equivalent...
01354         {
01355             // We leave mAllocator as-is.
01356             hash_code_base<K, V, EK, Eq, H1, H2, H, bC>::base_swap(x); // hash_code_base has multiple implementations, so we let them handle the swap.
01357             eastl::swap(mRehashPolicy,  x.mRehashPolicy);
01358             eastl::swap(mpBucketArray,  x.mpBucketArray);
01359             eastl::swap(mnBucketCount,  x.mnBucketCount);
01360             eastl::swap(mnElementCount, x.mnElementCount);
01361         }
01362         else
01363         {
01364             const this_type temp(*this); // Can't call eastl::swap because that would
01365             *this = x;                   // itself call this member swap function.
01366             x     = temp;
01367         }
01368     }
01369 
01370 
01371     template <typename K, typename V, typename A, typename EK, typename Eq,
01372               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01373     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::rehash_policy(const rehash_policy_type& rehashPolicy)
01374     {
01375         mRehashPolicy = rehashPolicy;
01376 
01377         const size_type nBuckets = rehashPolicy.GetBucketCount((uint32_t)mnElementCount);
01378 
01379         if(nBuckets > mnBucketCount)
01380             DoRehash(nBuckets);
01381     }
01382 
01383 
01384 
01385     template <typename K, typename V, typename A, typename EK, typename Eq,
01386               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01387     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01388     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find(const key_type& k)
01389     {
01390         const hash_code_t c = get_hash_code(k);
01391         const size_type   n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01392 
01393         node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
01394         return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
01395     }
01396 
01397 
01398 
01399     template <typename K, typename V, typename A, typename EK, typename Eq,
01400               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01401     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
01402     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find(const key_type& k) const
01403     {
01404         const hash_code_t c = get_hash_code(k);
01405         const size_type   n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01406 
01407         node_type* const pNode = DoFindNode(mpBucketArray[n], k, c);
01408         return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
01409     }
01410 
01411 
01412 
01413     template <typename K, typename V, typename A, typename EK, typename Eq,
01414               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01415     template <typename U, typename UHash, typename BinaryPredicate>
01416     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01417     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other, UHash uhash, BinaryPredicate predicate)
01418     {
01419         const hash_code_t c = (hash_code_t)uhash(other);
01420         const size_type   n = (size_type)(c % mnBucketCount); // This assumes we are using the mod range policy.
01421 
01422         node_type* const pNode = DoFindNode(mpBucketArray[n], other, predicate);
01423         return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
01424     }
01425 
01426 
01427 
01428     template <typename K, typename V, typename A, typename EK, typename Eq,
01429               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01430     template <typename U, typename UHash, typename BinaryPredicate>
01431     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
01432     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other, UHash uhash, BinaryPredicate predicate) const
01433     {
01434         const hash_code_t c = (hash_code_t)uhash(other);
01435         const size_type   n = (size_type)(c % mnBucketCount); // This assumes we are using the mod range policy.
01436 
01437         node_type* const pNode = DoFindNode(mpBucketArray[n], other, predicate);
01438         return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
01439     }
01440 
01441 
01456     template <typename H, typename U>
01457     inline typename H::iterator hashtable_find(H& hashTable, U u)
01458         { return hashTable.find_as(u, eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); }
01459 
01460     template <typename H, typename U>
01461     inline typename H::const_iterator hashtable_find(const H& hashTable, U u)
01462         { return hashTable.find_as(u, eastl::hash<U>(), eastl::equal_to_2<const typename H::key_type, U>()); }
01463 
01464 
01465 
01466     template <typename K, typename V, typename A, typename EK, typename Eq,
01467               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01468     template <typename U>
01469     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01470     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other)
01471         { return eastl::hashtable_find(*this, other); }
01472         // VC++ doesn't appear to like the following, though it seems correct to me.
01473         // So we implement the workaround above until we can straighten this out.
01474         //{ return find_as(other, eastl::hash<U>(), eastl::equal_to_2<const key_type, U>()); }
01475 
01476 
01477     template <typename K, typename V, typename A, typename EK, typename Eq,
01478               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01479     template <typename U>
01480     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
01481     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_as(const U& other) const
01482         { return eastl::hashtable_find(*this, other); }
01483         // VC++ doesn't appear to like the following, though it seems correct to me.
01484         // So we implement the workaround above until we can straighten this out.
01485         //{ return find_as(other, eastl::hash<U>(), eastl::equal_to_2<const key_type, U>()); }
01486 
01487 
01488     template <typename K, typename V, typename A, typename EK, typename Eq,
01489               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01490     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01491     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_by_hash(hash_code_t c)
01492     {
01493         const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
01494 
01495         node_type* const pNode = DoFindNode(mpBucketArray[n], c);
01496         return pNode ? iterator(pNode, mpBucketArray + n) : iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
01497     }
01498 
01499 
01500     template <typename K, typename V, typename A, typename EK, typename Eq,
01501               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01502     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator
01503     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::find_by_hash(hash_code_t c) const
01504     {
01505         const size_type n = (size_type)bucket_index(c, (uint32_t)mnBucketCount);
01506 
01507         node_type* const pNode = DoFindNode(mpBucketArray[n], c);
01508         return pNode ? const_iterator(pNode, mpBucketArray + n) : const_iterator(mpBucketArray + mnBucketCount); // iterator(mpBucketArray + mnBucketCount) == end()
01509     }
01510 
01511 
01512     template <typename K, typename V, typename A, typename EK, typename Eq,
01513               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01514     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::size_type
01515     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::count(const key_type& k) const
01516     {
01517         const hash_code_t c      = get_hash_code(k);
01518         const size_type   n      = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01519         size_type         result = 0;
01520 
01521         // To do: Make a specialization for bU (unique keys) == true and take
01522         // advantage of the fact that the count will always be zero or one in that case.
01523         for(node_type* pNode = mpBucketArray[n]; pNode; pNode = pNode->mpNext)
01524         {
01525             if(compare(k, c, pNode))
01526                 ++result;
01527         }
01528         return result;
01529     }
01530 
01531 
01532 
01533     template <typename K, typename V, typename A, typename EK, typename Eq,
01534               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01535     eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator,
01536                 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator>
01537     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::equal_range(const key_type& k)
01538     {
01539         const hash_code_t c = get_hash_code(k);
01540         const size_type   n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01541 
01542         node_type** head  = mpBucketArray + n;
01543         node_type*  pNode = DoFindNode(*head, k, c);
01544 
01545         if(pNode)
01546         {
01547             node_type* p1 = pNode->mpNext;
01548 
01549             for(; p1; p1 = p1->mpNext)
01550             {
01551                 if(!compare(k, c, p1))
01552                     break;
01553             }
01554 
01555             iterator first(pNode, head);
01556             iterator last(p1, head);
01557 
01558             if(!p1)
01559                 last.increment_bucket();
01560 
01561             return eastl::pair<iterator, iterator>(first, last);
01562         }
01563 
01564         return eastl::pair<iterator, iterator>(iterator(mpBucketArray + mnBucketCount),  // iterator(mpBucketArray + mnBucketCount) == end()
01565                                                iterator(mpBucketArray + mnBucketCount));
01566     }
01567 
01568 
01569 
01570 
01571     template <typename K, typename V, typename A, typename EK, typename Eq,
01572               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01573     eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator,
01574                 typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::const_iterator>
01575     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::equal_range(const key_type& k) const
01576     {
01577         const hash_code_t c     = get_hash_code(k);
01578         const size_type   n     = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01579         node_type**       head  = mpBucketArray + n;
01580         node_type*        pNode = DoFindNode(*head, k, c);
01581 
01582         if(pNode)
01583         {
01584             node_type* p1 = pNode->mpNext;
01585 
01586             for(; p1; p1 = p1->mpNext)
01587             {
01588                 if(!compare(k, c, p1))
01589                     break;
01590             }
01591 
01592             const_iterator first(pNode, head);
01593             const_iterator last(p1, head);
01594 
01595             if(!p1)
01596                 last.increment_bucket();
01597 
01598             return eastl::pair<const_iterator, const_iterator>(first, last);
01599         }
01600 
01601         return eastl::pair<const_iterator, const_iterator>(const_iterator(mpBucketArray + mnBucketCount),  // iterator(mpBucketArray + mnBucketCount) == end()
01602                                                            const_iterator(mpBucketArray + mnBucketCount));
01603     }
01604 
01605 
01606 
01607     template <typename K, typename V, typename A, typename EK, typename Eq,
01608               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01609     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
01610     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode, const key_type& k, hash_code_t c) const
01611     {
01612         for(; pNode; pNode = pNode->mpNext)
01613         {
01614             if(compare(k, c, pNode))
01615                 return pNode;
01616         }
01617         return NULL;
01618     }
01619 
01620 
01621 
01622     template <typename K, typename V, typename A, typename EK, typename Eq,
01623               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01624     template <typename U, typename BinaryPredicate>
01625     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
01626     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode, const U& other, BinaryPredicate predicate) const
01627     {
01628         for(; pNode; pNode = pNode->mpNext)
01629         {
01630             if(predicate(mExtractKey(pNode->mValue), other)) // Intentionally compare with key as first arg and other as second arg.
01631                 return pNode;
01632         }
01633         return NULL;
01634     }
01635 
01636 
01637 
01638     template <typename K, typename V, typename A, typename EK, typename Eq,
01639               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01640     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::node_type*
01641     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoFindNode(node_type* pNode, hash_code_t c) const
01642     {
01643         for(; pNode; pNode = pNode->mpNext)
01644         {
01645             if(pNode->mnHashCode == c)
01646                 return pNode;
01647         }
01648         return NULL;
01649     }
01650 
01651 
01652 
01653     template <typename K, typename V, typename A, typename EK, typename Eq,
01654               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01655     eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
01656     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(const value_type& value, true_type) // true_type means bUniqueKeys is true.
01657     {
01658         const key_type&   k     = mExtractKey(value);
01659         const hash_code_t c     = get_hash_code(k);
01660         size_type         n     = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01661         node_type* const  pNode = DoFindNode(mpBucketArray[n], k, c);
01662 
01663         if(pNode == NULL)
01664         {
01665             const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
01666 
01667             // Allocate the new node before doing the rehash so that we don't
01668             // do a rehash if the allocation throws.
01669             node_type* const pNodeNew = DoAllocateNode(value);
01670             set_code(pNodeNew, c); // This is a no-op for most hashtables.
01671 
01672             #if EASTL_EXCEPTIONS_ENABLED
01673                 try
01674                 {
01675             #endif
01676                     if(bRehash.first)
01677                     {
01678                         n = (size_type)bucket_index(k, c, (uint32_t)bRehash.second);
01679                         DoRehash(bRehash.second);
01680                     }
01681 
01682                     EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
01683                     pNodeNew->mpNext = mpBucketArray[n];
01684                     mpBucketArray[n] = pNodeNew;
01685                     ++mnElementCount;
01686 
01687                     return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
01688             #if EASTL_EXCEPTIONS_ENABLED
01689                 }
01690                 catch(...)
01691                 {
01692                     DoFreeNode(pNodeNew);
01693                     throw;
01694                 }
01695             #endif
01696         }
01697 
01698         return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
01699     }
01700 
01701 
01702 
01703     template <typename K, typename V, typename A, typename EK, typename Eq,
01704               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01705     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01706     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertValue(const value_type& value, false_type) // false_type means bUniqueKeys is false.
01707     {
01708         const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
01709 
01710         if(bRehash.first)
01711             DoRehash(bRehash.second);
01712 
01713         const key_type&   k = mExtractKey(value);
01714         const hash_code_t c = get_hash_code(k);
01715         const size_type   n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01716 
01717         node_type* const pNodeNew = DoAllocateNode(value);
01718         set_code(pNodeNew, c); // This is a no-op for most hashtables.
01719 
01720         // To consider: Possibly make this insertion not make equal elements contiguous.
01721         // As it stands now, we insert equal values contiguously in the hashtable.
01722         // The benefit is that equal_range can work in a sensible manner and that
01723         // erase(value) can more quickly find equal values. The downside is that
01724         // this insertion operation taking some extra time. How important is it to
01725         // us that equal_range span all equal items?
01726         node_type* const pNodePrev = DoFindNode(mpBucketArray[n], k, c);
01727 
01728         if(pNodePrev == NULL)
01729         {
01730             EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
01731             pNodeNew->mpNext = mpBucketArray[n];
01732             mpBucketArray[n] = pNodeNew;
01733         }
01734         else
01735         {
01736             pNodeNew->mpNext  = pNodePrev->mpNext;
01737             pNodePrev->mpNext = pNodeNew;
01738         }
01739 
01740         ++mnElementCount;
01741 
01742         return iterator(pNodeNew, mpBucketArray + n);
01743     }
01744 
01745 
01746 
01747     template <typename K, typename V, typename A, typename EK, typename Eq,
01748               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01749     eastl::pair<typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator, bool>
01750     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(const key_type& key, true_type) // true_type means bUniqueKeys is true.
01751     {
01752         const hash_code_t c     = get_hash_code(key);
01753         size_type         n     = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
01754         node_type* const  pNode = DoFindNode(mpBucketArray[n], key, c);
01755 
01756         if(pNode == NULL)
01757         {
01758             const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
01759 
01760             // Allocate the new node before doing the rehash so that we don't
01761             // do a rehash if the allocation throws.
01762             node_type* const pNodeNew = DoAllocateNodeFromKey(key);
01763             set_code(pNodeNew, c); // This is a no-op for most hashtables.
01764 
01765             #if EASTL_EXCEPTIONS_ENABLED
01766                 try
01767                 {
01768             #endif
01769                     if(bRehash.first)
01770                     {
01771                         n = (size_type)bucket_index(key, c, (uint32_t)bRehash.second);
01772                         DoRehash(bRehash.second);
01773                     }
01774 
01775                     EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
01776                     pNodeNew->mpNext = mpBucketArray[n];
01777                     mpBucketArray[n] = pNodeNew;
01778                     ++mnElementCount;
01779 
01780                     return eastl::pair<iterator, bool>(iterator(pNodeNew, mpBucketArray + n), true);
01781             #if EASTL_EXCEPTIONS_ENABLED
01782                 }
01783                 catch(...)
01784                 {
01785                     DoFreeNode(pNodeNew);
01786                     throw;
01787                 }
01788             #endif
01789         }
01790 
01791         return eastl::pair<iterator, bool>(iterator(pNode, mpBucketArray + n), false);
01792     }
01793 
01794 
01795 
01796     template <typename K, typename V, typename A, typename EK, typename Eq,
01797               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01798     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01799     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoInsertKey(const key_type& key, false_type) // false_type means bUniqueKeys is false.
01800     {
01801         const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, (uint32_t)1);
01802 
01803         if(bRehash.first)
01804             DoRehash(bRehash.second);
01805 
01806         const hash_code_t c = get_hash_code(key);
01807         const size_type   n = (size_type)bucket_index(key, c, (uint32_t)mnBucketCount);
01808 
01809         node_type* const pNodeNew = DoAllocateNodeFromKey(key);
01810         set_code(pNodeNew, c); // This is a no-op for most hashtables.
01811 
01812         // To consider: Possibly make this insertion not make equal elements contiguous.
01813         // As it stands now, we insert equal values contiguously in the hashtable.
01814         // The benefit is that equal_range can work in a sensible manner and that
01815         // erase(value) can more quickly find equal values. The downside is that
01816         // this insertion operation taking some extra time. How important is it to
01817         // us that equal_range span all equal items?
01818         node_type* const pNodePrev = DoFindNode(mpBucketArray[n], key, c);
01819 
01820         if(pNodePrev == NULL)
01821         {
01822             EASTL_ASSERT((void**)mpBucketArray != &gpEmptyBucketArray[0]);
01823             pNodeNew->mpNext = mpBucketArray[n];
01824             mpBucketArray[n] = pNodeNew;
01825         }
01826         else
01827         {
01828             pNodeNew->mpNext  = pNodePrev->mpNext;
01829             pNodePrev->mpNext = pNodeNew;
01830         }
01831 
01832         ++mnElementCount;
01833 
01834         return iterator(pNodeNew, mpBucketArray + n);
01835     }
01836 
01837 
01838 
01839     template <typename K, typename V, typename A, typename EK, typename Eq,
01840               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01841     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert_return_type
01842     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(const value_type& value)
01843     {
01844         return DoInsertValue(value, integral_constant<bool, bU>());
01845     }
01846 
01847 
01848 
01849     template <typename K, typename V, typename A, typename EK, typename Eq,
01850               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01851     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01852     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(const_iterator, const value_type& value)
01853     {
01854         // We ignore the first argument (hint iterator). It's not likely to be useful for hashtable containers.
01855 
01856         #ifdef __MWERKS__ // The Metrowerks compiler has a bug.
01857             insert_return_type result = insert(value);
01858             return result.first; // Note by Paul Pedriana while perusing this code: This code will fail to compile when bU is false (i.e. for multiset, multimap).
01859 
01860         #elif defined(__GNUC__) && (__GNUC__ < 3) // If using old GCC (GCC 2.x has a bug which we work around)
01861             EASTL_ASSERT(empty()); // This function cannot return the correct return value on GCC 2.x. Unless, that is, the container is empty.
01862             DoInsertValue(value, integral_constant<bool, bU>());
01863             return begin(); // This is the wrong answer.
01864         #else
01865             insert_return_type result = DoInsertValue(value, integral_constant<bool, bU>());
01866             return result.first; // Note by Paul Pedriana while perusing this code: This code will fail to compile when bU is false (i.e. for multiset, multimap).
01867         #endif
01868     }
01869 
01870 
01871 
01872     template <typename K, typename V, typename A, typename EK, typename Eq,
01873               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01874     template <typename InputIterator>
01875     void
01876     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::insert(InputIterator first, InputIterator last)
01877     {
01878         const uint32_t nElementAdd = (uint32_t)eastl::ht_distance(first, last);
01879         const eastl::pair<bool, uint32_t> bRehash = mRehashPolicy.GetRehashRequired((uint32_t)mnBucketCount, (uint32_t)mnElementCount, nElementAdd);
01880 
01881         if(bRehash.first)
01882             DoRehash(bRehash.second);
01883 
01884         for(; first != last; ++first)
01885         {
01886             #ifdef __MWERKS__ // The Metrowerks compiler has a bug.
01887                 insert(*first);
01888             #else
01889                 DoInsertValue(*first, integral_constant<bool, bU>());
01890             #endif
01891         }
01892     }
01893 
01894 
01895 
01896     template <typename K, typename V, typename A, typename EK, typename Eq,
01897               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01898     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01899     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(iterator i)
01900     {
01901         iterator iNext(i);
01902         ++iNext;
01903 
01904         node_type* pNode        =  i.mpNode;
01905         node_type* pNodeCurrent = *i.mpBucket;
01906 
01907         if(pNodeCurrent == pNode)
01908             *i.mpBucket = pNodeCurrent->mpNext;
01909         else
01910         {
01911             // We have a singly-linked list, so we have no choice but to
01912             // walk down it till we find the node before the node at 'i'.
01913             node_type* pNodeNext = pNodeCurrent->mpNext;
01914 
01915             while(pNodeNext != pNode)
01916             {
01917                 pNodeCurrent = pNodeNext;
01918                 pNodeNext    = pNodeCurrent->mpNext;
01919             }
01920 
01921             pNodeCurrent->mpNext = pNodeNext->mpNext;
01922         }
01923 
01924         DoFreeNode(pNode);
01925         --mnElementCount;
01926 
01927         return iNext;
01928     }
01929 
01930 
01931 
01932     template <typename K, typename V, typename A, typename EK, typename Eq,
01933               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01934     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::iterator
01935     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(iterator first, iterator last)
01936     {
01937         while(first != last)
01938             first = erase(first);
01939         return first;
01940     }
01941 
01942 
01943 
01944     template <typename K, typename V, typename A, typename EK, typename Eq,
01945               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01946     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reverse_iterator
01947     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(reverse_iterator position)
01948     {
01949         return reverse_iterator(erase((++position).base()));
01950     }
01951 
01952 
01953 
01954     template <typename K, typename V, typename A, typename EK, typename Eq,
01955               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01956     inline typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reverse_iterator
01957     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(reverse_iterator first, reverse_iterator last)
01958     {
01959         // Version which erases in order from first to last.
01960         // difference_type i(first.base() - last.base());
01961         // while(i--)
01962         //     first = erase(first);
01963         // return first;
01964 
01965         // Version which erases in order from last to first, but is slightly more efficient:
01966         return reverse_iterator(erase((++last).base(), (++first).base()));
01967     }
01968 
01969 
01970 
01971     template <typename K, typename V, typename A, typename EK, typename Eq,
01972               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
01973     typename hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::size_type
01974     hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::erase(const key_type& k)
01975     {
01976         // To do: Reimplement this function to do a single loop and not try to be
01977         // smart about element contiguity. The mechanism here is only a benefit if the
01978         // buckets are heavily overloaded; otherwise this mechanism may be slightly slower.
01979 
01980         const hash_code_t c = get_hash_code(k);
01981         const size_type   n = (size_type)bucket_index(k, c, (uint32_t)mnBucketCount);
01982         const size_type   nElementCountSaved = mnElementCount;
01983 
01984         node_type** pBucketArray = mpBucketArray + n;
01985 
01986         while(*pBucketArray && !compare(k, c, *pBucketArray))
01987             pBucketArray = &(*pBucketArray)->mpNext;
01988 
01989         while(*pBucketArray && compare(k, c, *pBucketArray))
01990         {
01991             node_type* const pNode = *pBucketArray;
01992             *pBucketArray = pNode->mpNext;
01993             DoFreeNode(pNode);
01994             --mnElementCount;
01995         }
01996 
01997         return nElementCountSaved - mnElementCount;
01998     }
01999 
02000 
02001 
02002     template <typename K, typename V, typename A, typename EK, typename Eq,
02003               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02004     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::clear()
02005     {
02006         DoFreeNodes(mpBucketArray, mnBucketCount);
02007         mnElementCount = 0;
02008     }
02009 
02010 
02011 
02012     template <typename K, typename V, typename A, typename EK, typename Eq,
02013               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02014     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::clear(bool clearBuckets)
02015     {
02016         DoFreeNodes(mpBucketArray, mnBucketCount);
02017         if(clearBuckets)
02018         {
02019             DoFreeBuckets(mpBucketArray, mnBucketCount);
02020             reset();
02021         }
02022         mnElementCount = 0;
02023     }
02024 
02025 
02026 
02027     template <typename K, typename V, typename A, typename EK, typename Eq,
02028               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02029     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::reset()
02030     {
02031         // The reset function is a special extension function which unilaterally
02032         // resets the container to an empty state without freeing the memory of
02033         // the contained objects. This is useful for very quickly tearing down a
02034         // container built into scratch memory.
02035         mnBucketCount  = 1;
02036 
02037         #ifdef _MSC_VER
02038             mpBucketArray = (node_type**)&gpEmptyBucketArray[0];
02039         #else
02040             void* p = &gpEmptyBucketArray[0];
02041             memcpy(&mpBucketArray, &p, sizeof(mpBucketArray)); // Other compilers implement strict aliasing and casting is thus unsafe.
02042         #endif
02043 
02044         mnElementCount = 0;
02045         mRehashPolicy.mnNextResize = 0;
02046     }
02047 
02048 
02049 
02050     template <typename K, typename V, typename A, typename EK, typename Eq,
02051               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02052     inline void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::rehash(size_type nBucketCount)
02053     {
02054         // Note that we unilaterally use the passed in bucket count; we do not attempt migrate it
02055         // up to the next prime number. We leave it at the user's discretion to do such a thing.
02056         DoRehash(nBucketCount);
02057     }
02058 
02059 
02060 
02061     template <typename K, typename V, typename A, typename EK, typename Eq,
02062               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02063     void hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::DoRehash(size_type nNewBucketCount)
02064     {
02065         node_type** const pBucketArray = DoAllocateBuckets(nNewBucketCount); // nNewBucketCount should always be >= 2.
02066 
02067         #if EASTL_EXCEPTIONS_ENABLED
02068             try
02069             {
02070         #endif
02071                 node_type* pNode;
02072 
02073                 for(size_type i = 0; i < mnBucketCount; ++i)
02074                 {
02075                     while((pNode = mpBucketArray[i]) != NULL) // Using '!=' disables compiler warnings.
02076                     {
02077                         const size_type nNewBucketIndex = (size_type)bucket_index(pNode, (uint32_t)nNewBucketCount);
02078 
02079                         mpBucketArray[i] = pNode->mpNext;
02080                         pNode->mpNext    = pBucketArray[nNewBucketIndex];
02081                         pBucketArray[nNewBucketIndex] = pNode;
02082                     }
02083                 }
02084 
02085                 DoFreeBuckets(mpBucketArray, mnBucketCount);
02086                 mnBucketCount = nNewBucketCount;
02087                 mpBucketArray = pBucketArray;
02088         #if EASTL_EXCEPTIONS_ENABLED
02089             }
02090             catch(...)
02091             {
02092                 // A failure here means that a hash function threw an exception.
02093                 // We can't restore the previous state without calling the hash
02094                 // function again, so the only sensible recovery is to delete everything.
02095                 DoFreeNodes(pBucketArray, nNewBucketCount);
02096                 DoFreeBuckets(pBucketArray, nNewBucketCount);
02097                 DoFreeNodes(mpBucketArray, mnBucketCount);
02098                 mnElementCount = 0;
02099                 throw;
02100             }
02101         #endif
02102     }
02103 
02104 
02105     template <typename K, typename V, typename A, typename EK, typename Eq,
02106               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02107     inline bool hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::validate() const
02108     {
02109         // Verify our empty bucket array is unmodified.
02110         if(gpEmptyBucketArray[0] != NULL)
02111             return false;
02112 
02113         if(gpEmptyBucketArray[1] != (void*)uintptr_t(~0))
02114             return false;
02115 
02116         // Verify that we have at least one bucket. Calculations can
02117         // trigger division by zero exceptions otherwise.
02118         if(mnBucketCount == 0)
02119             return false;
02120 
02121         // Verify that gpEmptyBucketArray is used correctly.
02122         // gpEmptyBucketArray is only used when initially empty.
02123         if((void**)mpBucketArray == &gpEmptyBucketArray[0])
02124         {
02125             if(mnElementCount) // gpEmptyBucketArray is used only for empty hash tables.
02126                 return false;
02127 
02128             if(mnBucketCount != 1) // gpEmptyBucketArray is used exactly an only for mnBucketCount == 1.
02129                 return false;
02130         }
02131         else
02132         {
02133             if(mnBucketCount < 2) // Small bucket counts *must* use gpEmptyBucketArray.
02134                 return false;
02135         }
02136 
02137         // Verify that the element count matches mnElementCount.
02138         size_type nElementCount = 0;
02139 
02140         for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
02141             ++nElementCount;
02142 
02143         if(nElementCount != mnElementCount)
02144             return false;
02145 
02146         // To do: Verify that individual elements are in the expected buckets.
02147 
02148         return true;
02149     }
02150 
02151 
02152     template <typename K, typename V, typename A, typename EK, typename Eq,
02153               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02154     int hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>::validate_iterator(const_iterator i) const
02155     {
02156         // To do: Come up with a more efficient mechanism of doing this.
02157 
02158         for(const_iterator temp = begin(), tempEnd = end(); temp != tempEnd; ++temp)
02159         {
02160             if(temp == i)
02161                 return (isf_valid | isf_current | isf_can_dereference);
02162         }
02163 
02164         if(i == end())
02165             return (isf_valid | isf_current);
02166 
02167         return isf_none;
02168     }
02169 
02170 
02171 
02173     // global operators
02175 
02176     template <typename K, typename V, typename A, typename EK, typename Eq,
02177               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02178     inline bool operator==(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02179                            const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02180     {
02181         return (a.size() == b.size()) && eastl::equal(a.begin(), a.end(), b.begin());
02182     }
02183 
02184 
02185     // Comparing hash tables for less-ness is an odd thing to do. We provide it for
02186     // completeness, though the user is advised to be wary of how they use this.
02187     template <typename K, typename V, typename A, typename EK, typename Eq,
02188               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02189     inline bool operator<(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02190                           const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02191     {
02192         // This requires hash table elements to support operator<. Since the hash table
02193         // doesn't compare elements via less (it does so via equals), we must use the
02194         // globally defined operator less for the elements.
02195         return eastl::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
02196     }
02197 
02198 
02199     template <typename K, typename V, typename A, typename EK, typename Eq,
02200               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02201     inline bool operator!=(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02202                            const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02203     {
02204         return !(a == b);
02205     }
02206 
02207 
02208     template <typename K, typename V, typename A, typename EK, typename Eq,
02209               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02210     inline bool operator>(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02211                           const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02212     {
02213         return b < a;
02214     }
02215 
02216 
02217     template <typename K, typename V, typename A, typename EK, typename Eq,
02218               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02219     inline bool operator<=(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02220                            const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02221     {
02222         return !(b < a);
02223     }
02224 
02225 
02226     template <typename K, typename V, typename A, typename EK, typename Eq,
02227               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02228     inline bool operator>=(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02229                            const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02230     {
02231         return !(a < b);
02232     }
02233 
02234 
02235     template <typename K, typename V, typename A, typename EK, typename Eq,
02236               typename H1, typename H2, typename H, typename RP, bool bC, bool bM, bool bU>
02237     inline void swap(const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& a,
02238                      const hashtable<K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU>& b)
02239     {
02240         a.swap(b);
02241     }
02242 
02243 
02244 } // namespace eastl
02245 
02246 
02247 #ifdef _MSC_VER
02248     #pragma warning(pop)
02249 #endif
02250 
02251 #endif // Header include guard
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines