1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/LibOVR/Src/Kernel/OVR_Hash.h	Wed Jan 14 06:51:16 2015 +0200
     1.3 @@ -0,0 +1,1305 @@
     1.4 +/************************************************************************************
     1.5 +
     1.6 +PublicHeader:   None
     1.7 +Filename    :   OVR_Hash.h
     1.8 +Content     :   Template hash-table/set implementation
     1.9 +Created     :   September 19, 2012
    1.10 +Notes       : 
    1.11 +
    1.12 +Copyright   :   Copyright 2014 Oculus VR, LLC All Rights reserved.
    1.13 +
    1.14 +Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
    1.15 +you may not use the Oculus VR Rift SDK except in compliance with the License, 
    1.16 +which is provided at the time of installation or download, or which 
    1.17 +otherwise accompanies this software in either electronic or hard copy form.
    1.18 +
    1.19 +You may obtain a copy of the License at
    1.20 +
    1.21 +http://www.oculusvr.com/licenses/LICENSE-3.2 
    1.22 +
    1.23 +Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
    1.24 +distributed under the License is distributed on an "AS IS" BASIS,
    1.25 +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    1.26 +See the License for the specific language governing permissions and
    1.27 +limitations under the License.
    1.28 +
    1.29 +************************************************************************************/
    1.30 +
    1.31 +#ifndef OVR_Hash_h
    1.32 +#define OVR_Hash_h
    1.33 +
    1.34 +#include "OVR_ContainerAllocator.h"
    1.35 +#include "OVR_Alg.h"
    1.36 +
    1.37 +// 'new' operator is redefined/used in this file.
    1.38 +#undef new
    1.39 +
    1.40 +namespace OVR {
    1.41 +
    1.42 +//-----------------------------------------------------------------------------------
    1.43 +// ***** Hash Table Implementation
    1.44 +
    1.45 +// HastSet and Hash.
    1.46 +//
    1.47 +// Hash table, linear probing, internal chaining.  One  interesting/nice thing
    1.48 +// about this implementation is that the table itself is a flat chunk of memory
    1.49 +// containing no pointers, only relative indices. If the key and value types
    1.50 +// of the Hash contain no pointers, then the Hash can be serialized using raw IO.
    1.51 +//
    1.52 +// Never shrinks, unless you explicitly Clear() it.  Expands on
    1.53 +// demand, though.  For best results, if you know roughly how big your
    1.54 +// table will be, default it to that size when you create it.
    1.55 +//
    1.56 +// Key usability feature:
    1.57 +//
    1.58 +//   1. Allows node hash values to either be cached or not.
    1.59 +//
    1.60 +//   2. Allows for alternative keys with methods such as GetAlt(). Handy
    1.61 +//      if you need to search nodes by their components; no need to create
    1.62 +//      temporary nodes.
    1.63 +//
    1.64 +
    1.65 +
    1.66 +// *** Hash functors:
    1.67 +//
    1.68 +//  IdentityHash  - use when the key is already a good hash
    1.69 +//  HFixedSizeHash - general hash based on object's in-memory representation.
    1.70 +
    1.71 +
    1.72 +// Hash is just the input value; can use this for integer-indexed hash tables.
    1.73 +template<class C>
    1.74 +class IdentityHash
    1.75 +{
    1.76 +public:
    1.77 +    size_t operator()(const C& data) const
    1.78 +    { return (size_t) data; }
    1.79 +};
    1.80 +
    1.81 +// Computes a hash of an object's representation.
    1.82 +template<class C>
    1.83 +class FixedSizeHash
    1.84 +{
    1.85 +public:
    1.86 +    // Alternative: "sdbm" hash function, suggested at same web page
    1.87 +    // above, http::/www.cs.yorku.ca/~oz/hash.html
    1.88 +    // This is somewhat slower then Bernstein, but it works way better than the above
    1.89 +    // hash function for hashing large numbers of 32-bit ints.
    1.90 +    static OVR_FORCE_INLINE size_t SDBM_Hash(const void* data_in, size_t size, size_t seed = 5381)     
    1.91 +    {
    1.92 +        const uint8_t* data = (const uint8_t*) data_in;
    1.93 +        size_t       h = seed;
    1.94 +        while (size-- > 0)
    1.95 +        {
    1.96 +            #ifndef __clang_analyzer__ // It mistakenly thinks data is garbage.
    1.97 +            h = (h << 16) + (h << 6) - h + (size_t)data[size];
    1.98 +            #endif
    1.99 +        }   
   1.100 +        return h;
   1.101 +    }
   1.102 +
   1.103 +    size_t operator()(const C& data) const
   1.104 +    {
   1.105 +        const unsigned char*  p = (const unsigned char*) &data;
   1.106 +        const size_t size = sizeof(C);
   1.107 +
   1.108 +        return SDBM_Hash(p, size);
   1.109 +    }
   1.110 +};
   1.111 +
   1.112 +
   1.113 +
   1.114 +// *** HashsetEntry Entry types. 
   1.115 +
   1.116 +// Compact hash table Entry type that re-computes hash keys during hash traversal.
   1.117 +// Good to use if the hash function is cheap or the hash value is already cached in C.
   1.118 +template<class C, class HashF>
   1.119 +class HashsetEntry
   1.120 +{
   1.121 +public:
   1.122 +    // Internal chaining for collisions.
   1.123 +    intptr_t    NextInChain;
   1.124 +    C           Value;
   1.125 +
   1.126 +    HashsetEntry()
   1.127 +        : NextInChain(-2) { }
   1.128 +    HashsetEntry(const HashsetEntry& e)
   1.129 +        : NextInChain(e.NextInChain), Value(e.Value) { }
   1.130 +    HashsetEntry(const C& key, intptr_t next)
   1.131 +        : NextInChain(next), Value(key) { }
   1.132 +
   1.133 +    bool    IsEmpty() const          { return NextInChain == -2;  }
   1.134 +    bool    IsEndOfChain() const     { return NextInChain == -1;  }
   1.135 +
   1.136 +    // Cached hash value access - can be optimized bu storing hash locally.
   1.137 +    // Mask value only needs to be used if SetCachedHash is not implemented.
   1.138 +    size_t  GetCachedHash(size_t maskValue) const  { return HashF()(Value) & maskValue; }
   1.139 +    void    SetCachedHash(size_t)                  {}
   1.140 +
   1.141 +    void    Clear()
   1.142 +    {        
   1.143 +        Value.~C(); // placement delete
   1.144 +        NextInChain = -2;
   1.145 +    }
   1.146 +    // Free is only used from dtor of hash; Clear is used during regular operations:
   1.147 +    // assignment, hash reallocations, value reassignments, so on.
   1.148 +    void    Free() { Clear(); }
   1.149 +};
   1.150 +
   1.151 +// Hash table Entry type that caches the Entry hash value for nodes, so that it
   1.152 +// does not need to be re-computed during access.
   1.153 +template<class C, class HashF>
   1.154 +class HashsetCachedEntry
   1.155 +{
   1.156 +public:
   1.157 +    // Internal chaining for collisions.
   1.158 +    intptr_t    NextInChain;
   1.159 +    size_t      HashValue;
   1.160 +    C           Value;
   1.161 +
   1.162 +    HashsetCachedEntry()
   1.163 +        : NextInChain(-2) { }
   1.164 +    HashsetCachedEntry(const HashsetCachedEntry& e)
   1.165 +        : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
   1.166 +    HashsetCachedEntry(const C& key, intptr_t next)
   1.167 +        : NextInChain(next), Value(key) { }
   1.168 +
   1.169 +    bool    IsEmpty() const          { return NextInChain == -2;  }
   1.170 +    bool    IsEndOfChain() const     { return NextInChain == -1;  }
   1.171 +
   1.172 +    // Cached hash value access - can be optimized bu storing hash locally.
   1.173 +    // Mask value only needs to be used if SetCachedHash is not implemented.
   1.174 +    size_t  GetCachedHash(size_t maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
   1.175 +    void    SetCachedHash(size_t hashValue)        { HashValue = hashValue; }
   1.176 +
   1.177 +    void    Clear()
   1.178 +    {
   1.179 +        Value.~C();
   1.180 +        NextInChain = -2;
   1.181 +    }
   1.182 +    // Free is only used from dtor of hash; Clear is used during regular operations:
   1.183 +    // assignment, hash reallocations, value reassignments, so on.
   1.184 +    void    Free() { Clear(); }
   1.185 +};
   1.186 +
   1.187 +
   1.188 +//-----------------------------------------------------------------------------------
   1.189 +// *** HashSet implementation - relies on either cached or regular entries.
   1.190 +//
   1.191 +// Use: Entry = HashsetCachedEntry<C, HashF> if hashes are expensive to
   1.192 +//              compute and thus need caching in entries.
   1.193 +//      Entry = HashsetEntry<C, HashF> if hashes are already externally cached.
   1.194 +//
   1.195 +template<class C, class HashF = FixedSizeHash<C>,
   1.196 +         class AltHashF = HashF, 
   1.197 +         class Allocator = ContainerAllocator<C>,
   1.198 +         class Entry = HashsetCachedEntry<C, HashF> >
   1.199 +class HashSetBase
   1.200 +{
   1.201 +    enum { HashMinSize = 8 };
   1.202 +
   1.203 +public:
   1.204 +    OVR_MEMORY_REDEFINE_NEW(HashSetBase)
   1.205 +
   1.206 +    typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry>    SelfType;
   1.207 +
   1.208 +    HashSetBase() : pTable(NULL)                       {   }
   1.209 +    HashSetBase(int sizeHint) : pTable(NULL)           { SetCapacity(this, sizeHint);  }
   1.210 +    HashSetBase(const SelfType& src) : pTable(NULL)    { Assign(this, src); }
   1.211 +
   1.212 +    ~HashSetBase()                                     
   1.213 +    { 
   1.214 +        if (pTable)
   1.215 +        {
   1.216 +            // Delete the entries.
   1.217 +            for (size_t i = 0, n = pTable->SizeMask; i <= n; i++)
   1.218 +            {
   1.219 +                Entry*  e = &E(i);
   1.220 +                if (!e->IsEmpty())             
   1.221 +                    e->Free();
   1.222 +            }            
   1.223 +
   1.224 +            Allocator::Free(pTable);
   1.225 +            pTable = NULL;
   1.226 +        }
   1.227 +    }
   1.228 +
   1.229 +
   1.230 +    void Assign(const SelfType& src)
   1.231 +    {
   1.232 +        Clear();
   1.233 +        if (src.IsEmpty() == false)
   1.234 +        {
   1.235 +            SetCapacity(src.GetSize());
   1.236 +
   1.237 +            for (ConstIterator it = src.Begin(); it != src.End(); ++it)
   1.238 +            {
   1.239 +                Add(*it);
   1.240 +            }
   1.241 +        }
   1.242 +    }
   1.243 +
   1.244 +
   1.245 +    // Remove all entries from the HashSet table.
   1.246 +    void Clear() 
   1.247 +    {
   1.248 +        if (pTable)
   1.249 +        {
   1.250 +            // Delete the entries.
   1.251 +            for (size_t i = 0, n = pTable->SizeMask; i <= n; i++)
   1.252 +            {
   1.253 +                Entry*  e = &E(i);
   1.254 +                if (!e->IsEmpty())             
   1.255 +                    e->Clear();
   1.256 +            }            
   1.257 +                
   1.258 +            Allocator::Free(pTable);
   1.259 +            pTable = NULL;
   1.260 +        }
   1.261 +    }
   1.262 +
   1.263 +    // Returns true if the HashSet is empty.
   1.264 +    bool IsEmpty() const
   1.265 +    {
   1.266 +        return pTable == NULL || pTable->EntryCount == 0;
   1.267 +    }
   1.268 +
   1.269 +
   1.270 +    // Set a new or existing value under the key, to the value.
   1.271 +    // Pass a different class of 'key' so that assignment reference object
   1.272 +    // can be passed instead of the actual object.
   1.273 +    template<class CRef>
   1.274 +    void Set(const CRef& key)
   1.275 +    {
   1.276 +        size_t hashValue = HashF()(key);
   1.277 +        intptr_t  index     = (intptr_t)-1;
   1.278 +
   1.279 +        if (pTable != NULL)
   1.280 +            index = findIndexCore(key, hashValue & pTable->SizeMask);
   1.281 +
   1.282 +        if (index >= 0)
   1.283 +        {            
   1.284 +            E(index).Value = key;
   1.285 +        }
   1.286 +        else
   1.287 +        {
   1.288 +            // Entry under key doesn't exist.
   1.289 +            add(key, hashValue);
   1.290 +        }
   1.291 +    }
   1.292 +
   1.293 +    template<class CRef>
   1.294 +    inline void Add(const CRef& key)
   1.295 +    {
   1.296 +        size_t hashValue = HashF()(key);
   1.297 +        add(key, hashValue);
   1.298 +    }
   1.299 +
   1.300 +    // Remove by alternative key.
   1.301 +    template<class K>
   1.302 +    void RemoveAlt(const K& key)
   1.303 +    {   
   1.304 +        if (pTable == NULL)
   1.305 +            return;
   1.306 +
   1.307 +        size_t   hashValue = AltHashF()(key);
   1.308 +        intptr_t index     = hashValue & pTable->SizeMask;
   1.309 +
   1.310 +        Entry*  e = &E(index);
   1.311 +
   1.312 +        // If empty node or occupied by collider, we have nothing to remove.
   1.313 +        if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != (size_t)index))
   1.314 +            return;        
   1.315 +
   1.316 +        // Save index
   1.317 +        intptr_t naturalIndex = index;
   1.318 +        intptr_t prevIndex    = -1;
   1.319 +
   1.320 +        while ((e->GetCachedHash(pTable->SizeMask) != (size_t)naturalIndex) || !(e->Value == key))
   1.321 +        {
   1.322 +            // Keep looking through the chain.
   1.323 +            prevIndex   = index;
   1.324 +            index       = e->NextInChain;
   1.325 +            if (index == -1)
   1.326 +                return; // End of chain, item not found
   1.327 +            e = &E(index);
   1.328 +        }
   1.329 +
   1.330 +        // Found it - our item is at index
   1.331 +        if (naturalIndex == index)
   1.332 +        {
   1.333 +            // If we have a follower, move it to us
   1.334 +            if (!e->IsEndOfChain())
   1.335 +            {               
   1.336 +                Entry*  enext = &E(e->NextInChain);
   1.337 +                e->Clear();
   1.338 +                new (e) Entry(*enext);
   1.339 +                // Point us to the follower's cell that will be cleared
   1.340 +                e = enext;
   1.341 +            }
   1.342 +        }
   1.343 +        else
   1.344 +        {
   1.345 +            // We are not at natural index, so deal with the prev items next index
   1.346 +            E(prevIndex).NextInChain = e->NextInChain;
   1.347 +        }
   1.348 +
   1.349 +        // Clear us, of the follower cell that was moved.
   1.350 +        e->Clear();
   1.351 +        pTable->EntryCount --;
   1.352 +        // Should we check the size to condense hash? ...
   1.353 +    }
   1.354 +
   1.355 +    // Remove by main key.
   1.356 +    template<class CRef>
   1.357 +    void Remove(const CRef& key)
   1.358 +    {
   1.359 +        RemoveAlt(key);
   1.360 +    }
   1.361 +
   1.362 +    // Retrieve the pointer to a value under the given key.
   1.363 +    //  - If there's no value under the key, then return NULL.    
   1.364 +    //  - If there is a value, return the pointer.    
   1.365 +    template<class K>
   1.366 +    C* Get(const K& key)
   1.367 +    {
   1.368 +        intptr_t index = findIndex(key);
   1.369 +        if (index >= 0)        
   1.370 +            return &E(index).Value;        
   1.371 +        return 0;
   1.372 +    }   
   1.373 +
   1.374 +    template<class K>
   1.375 +    const C* Get(const K& key) const
   1.376 +    {
   1.377 +        intptr_t index = findIndex(key);
   1.378 +        if (index >= 0)        
   1.379 +            return &E(index).Value;        
   1.380 +        return 0;
   1.381 +    }
   1.382 +
   1.383 +    // Alternative key versions of Get. Used by Hash.
   1.384 +    template<class K>
   1.385 +    const C* GetAlt(const K& key) const
   1.386 +    {
   1.387 +        intptr_t index = findIndexAlt(key);
   1.388 +        if (index >= 0)        
   1.389 +            return &E(index).Value;
   1.390 +        return 0;
   1.391 +    }
   1.392 +
   1.393 +    template<class K>
   1.394 +    C* GetAlt(const K& key)
   1.395 +    {
   1.396 +        intptr_t index = findIndexAlt(key);
   1.397 +        if (index >= 0)        
   1.398 +            return &E(index).Value;
   1.399 +        return 0;
   1.400 +    }   
   1.401 +
   1.402 +    template<class K>
   1.403 +    bool GetAlt(const K& key, C* pval) const
   1.404 +    {
   1.405 +        intptr_t index = findIndexAlt(key);
   1.406 +        if (index >= 0)
   1.407 +        {
   1.408 +            if (pval)
   1.409 +                *pval = E(index).Value;
   1.410 +            return true;
   1.411 +        }
   1.412 +        return false;
   1.413 +    }
   1.414 +
   1.415 +
   1.416 +    size_t GetSize() const
   1.417 +    {
   1.418 +        return pTable == NULL ? 0 : (size_t)pTable->EntryCount;
   1.419 +    }
   1.420 +	int GetSizeI() const { return (int)GetSize(); }
   1.421 +
   1.422 +
   1.423 +    // Resize the HashSet table to fit one more Entry.  Often this
   1.424 +    // doesn't involve any action.
   1.425 +    void CheckExpand()
   1.426 +    {
   1.427 +        if (pTable == NULL)
   1.428 +        {
   1.429 +            // Initial creation of table.  Make a minimum-sized table.
   1.430 +            setRawCapacity(HashMinSize);
   1.431 +        }
   1.432 +        else if (pTable->EntryCount * 5 > (pTable->SizeMask + 1) * 4)
   1.433 +        {
   1.434 +            // pTable is more than 5/4 ths full.  Expand.
   1.435 +            setRawCapacity((pTable->SizeMask + 1) * 2);
   1.436 +        }
   1.437 +    }
   1.438 +
   1.439 +    // Hint the bucket count to >= n.
   1.440 +    void Resize(size_t n)    
   1.441 +    {
   1.442 +        // Not really sure what this means in relation to
   1.443 +        // STLport's hash_map... they say they "increase the
   1.444 +        // bucket count to at least n" -- but does that mean
   1.445 +        // their real capacity after Resize(n) is more like
   1.446 +        // n*2 (since they do linked-list chaining within
   1.447 +        // buckets?).
   1.448 +        SetCapacity(n);
   1.449 +    }
   1.450 +
   1.451 +    // Size the HashSet so that it can comfortably contain the given
   1.452 +    // number of elements.  If the HashSet already contains more
   1.453 +    // elements than newSize, then this may be a no-op.
   1.454 +    void SetCapacity(size_t newSize)
   1.455 +    {
   1.456 +        size_t newRawSize = (newSize * 5) / 4;
   1.457 +        if (newRawSize <= GetSize())
   1.458 +            return;
   1.459 +        setRawCapacity(newRawSize);
   1.460 +    }
   1.461 +
   1.462 +    // Disable inappropriate 'operator ->' warning on MSVC6.
   1.463 +#ifdef OVR_CC_MSVC
   1.464 +#if (OVR_CC_MSVC < 1300)
   1.465 +# pragma warning(disable : 4284)
   1.466 +#endif
   1.467 +#endif
   1.468 +
   1.469 +    // Iterator API, like STL.
   1.470 +    struct ConstIterator
   1.471 +    {   
   1.472 +        const C&    operator * () const
   1.473 +        {            
   1.474 +            OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask);
   1.475 +            return pHash->E(Index).Value;
   1.476 +        }
   1.477 +
   1.478 +        const C*    operator -> () const
   1.479 +        {
   1.480 +            OVR_ASSERT(Index >= 0 && Index <= (intptr_t)pHash->pTable->SizeMask);
   1.481 +            return &pHash->E(Index).Value;
   1.482 +        }
   1.483 +
   1.484 +        void    operator ++ ()
   1.485 +        {
   1.486 +            // Find next non-empty Entry.
   1.487 +            if (Index <= (intptr_t)pHash->pTable->SizeMask)
   1.488 +            {
   1.489 +                Index++;
   1.490 +                while ((size_t)Index <= pHash->pTable->SizeMask &&
   1.491 +                    pHash->E(Index).IsEmpty())
   1.492 +                {
   1.493 +                    Index++;
   1.494 +                }
   1.495 +            }
   1.496 +        }
   1.497 +
   1.498 +        bool    operator == (const ConstIterator& it) const
   1.499 +        {
   1.500 +            if (IsEnd() && it.IsEnd())
   1.501 +            {
   1.502 +                return true;
   1.503 +            }
   1.504 +            else
   1.505 +            {
   1.506 +                return (pHash == it.pHash) && (Index == it.Index);
   1.507 +            }
   1.508 +        }
   1.509 +
   1.510 +        bool    operator != (const ConstIterator& it) const
   1.511 +        {
   1.512 +            return ! (*this == it);
   1.513 +        }
   1.514 +
   1.515 +
   1.516 +        bool    IsEnd() const
   1.517 +        {
   1.518 +            return (pHash == NULL) || 
   1.519 +                (pHash->pTable == NULL) || 
   1.520 +                (Index > (intptr_t)pHash->pTable->SizeMask);
   1.521 +        }
   1.522 +
   1.523 +        ConstIterator()
   1.524 +            : pHash(NULL), Index(0)
   1.525 +        { }
   1.526 +
   1.527 +    public:
   1.528 +        // Constructor was intentionally made public to allow create
   1.529 +        // iterator with arbitrary index.
   1.530 +        ConstIterator(const SelfType* h, intptr_t index)
   1.531 +            : pHash(h), Index(index)
   1.532 +        { }
   1.533 +
   1.534 +        const SelfType* GetContainer() const
   1.535 +        {
   1.536 +            return pHash;
   1.537 +        }
   1.538 +        intptr_t GetIndex() const
   1.539 +        {
   1.540 +            return Index;
   1.541 +        }
   1.542 +
   1.543 +    protected:
   1.544 +        friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
   1.545 +
   1.546 +        const SelfType* pHash;
   1.547 +        intptr_t        Index;
   1.548 +    };
   1.549 +
   1.550 +    friend struct ConstIterator;
   1.551 +
   1.552 +
   1.553 +    // Non-const Iterator; Get most of it from ConstIterator.
   1.554 +    struct Iterator : public ConstIterator
   1.555 +    {      
   1.556 +        // Allow non-const access to entries.
   1.557 +        C&  operator*() const
   1.558 +        {            
   1.559 +            OVR_ASSERT((ConstIterator::pHash) && ConstIterator::pHash->pTable && (ConstIterator::Index >= 0) && (ConstIterator::Index <= (intptr_t)ConstIterator::pHash->pTable->SizeMask));
   1.560 +            return const_cast<SelfType*>(ConstIterator::pHash)->E(ConstIterator::Index).Value;
   1.561 +        }    
   1.562 +
   1.563 +        C*  operator->() const 
   1.564 +        {
   1.565 +            return &(operator*());
   1.566 +        }
   1.567 +
   1.568 +        Iterator()
   1.569 +            : ConstIterator(NULL, 0)
   1.570 +        { }
   1.571 +
   1.572 +        // Removes current element from Hash
   1.573 +        void Remove()
   1.574 +        {
   1.575 +            RemoveAlt(operator*());
   1.576 +        }
   1.577 +
   1.578 +        template <class K>
   1.579 +        void RemoveAlt(const K& key)
   1.580 +        {
   1.581 +            SelfType*   phash = const_cast<SelfType*>(ConstIterator::pHash);
   1.582 +            //Entry*      ee = &phash->E(ConstIterator::Index);
   1.583 +            //const C&    key = ee->Value;
   1.584 +
   1.585 +            size_t      hashValue = AltHashF()(key);
   1.586 +            intptr_t    index     = hashValue & phash->pTable->SizeMask;
   1.587 +
   1.588 +            Entry*      e = &phash->E(index);
   1.589 +
   1.590 +            // If empty node or occupied by collider, we have nothing to remove.
   1.591 +            if (e->IsEmpty() || (e->GetCachedHash(phash->pTable->SizeMask) != (size_t)index))
   1.592 +                return;        
   1.593 +
   1.594 +            // Save index
   1.595 +            intptr_t   naturalIndex = index;
   1.596 +            intptr_t   prevIndex    = -1;
   1.597 +
   1.598 +            while ((e->GetCachedHash(phash->pTable->SizeMask) != (size_t)naturalIndex) || !(e->Value == key))
   1.599 +            {
   1.600 +                // Keep looking through the chain.
   1.601 +                prevIndex   = index;
   1.602 +                index       = e->NextInChain;
   1.603 +                if (index == -1)
   1.604 +                    return; // End of chain, item not found
   1.605 +                e = &phash->E(index);
   1.606 +            }
   1.607 +
   1.608 +            if (index == (intptr_t)ConstIterator::Index)
   1.609 +            {
   1.610 +                // Found it - our item is at index
   1.611 +                if (naturalIndex == index)
   1.612 +                {
   1.613 +                    // If we have a follower, move it to us
   1.614 +                    if (!e->IsEndOfChain())
   1.615 +                    {               
   1.616 +                        Entry*  enext = &phash->E(e->NextInChain);
   1.617 +                        e->Clear();
   1.618 +                        new (e) Entry(*enext);
   1.619 +                        // Point us to the follower's cell that will be cleared
   1.620 +                        e = enext;
   1.621 +                        --ConstIterator::Index;
   1.622 +                    }
   1.623 +                }
   1.624 +                else
   1.625 +                {
   1.626 +                    // We are not at natural index, so deal with the prev items next index
   1.627 +                    phash->E(prevIndex).NextInChain = e->NextInChain;
   1.628 +                }
   1.629 +
   1.630 +                // Clear us, of the follower cell that was moved.
   1.631 +                e->Clear();
   1.632 +                phash->pTable->EntryCount --;
   1.633 +            }
   1.634 +            else 
   1.635 +                OVR_ASSERT(0); //?
   1.636 +        }
   1.637 +
   1.638 +    private:
   1.639 +        friend class HashSetBase<C, HashF, AltHashF, Allocator, Entry>;
   1.640 +
   1.641 +        Iterator(SelfType* h, intptr_t i0)
   1.642 +            : ConstIterator(h, i0)
   1.643 +        { }
   1.644 +    };
   1.645 +
   1.646 +    friend struct Iterator;
   1.647 +
   1.648 +    Iterator    Begin()
   1.649 +    {
   1.650 +        if (pTable == 0)
   1.651 +            return Iterator(NULL, 0);
   1.652 +
   1.653 +        // Scan till we hit the First valid Entry.
   1.654 +        size_t i0 = 0;
   1.655 +        while (i0 <= pTable->SizeMask && E(i0).IsEmpty())
   1.656 +        {
   1.657 +            i0++;
   1.658 +        }
   1.659 +        return Iterator(this, i0);
   1.660 +    }
   1.661 +    Iterator        End()           { return Iterator(NULL, 0); }
   1.662 +
   1.663 +    ConstIterator   Begin() const   { return const_cast<SelfType*>(this)->Begin();     }
   1.664 +    ConstIterator   End() const     { return const_cast<SelfType*>(this)->End();   }
   1.665 +
   1.666 +    template<class K>
   1.667 +    Iterator Find(const K& key)
   1.668 +    {
   1.669 +        intptr_t index = findIndex(key);
   1.670 +        if (index >= 0)        
   1.671 +            return Iterator(this, index);        
   1.672 +        return Iterator(NULL, 0);
   1.673 +    }
   1.674 +
   1.675 +    template<class K>
   1.676 +    Iterator FindAlt(const K& key)
   1.677 +    {
   1.678 +        intptr_t index = findIndexAlt(key);
   1.679 +        if (index >= 0)        
   1.680 +            return Iterator(this, index);        
   1.681 +        return Iterator(NULL, 0);
   1.682 +    }
   1.683 +
   1.684 +    template<class K>
   1.685 +    ConstIterator Find(const K& key) const       { return const_cast<SelfType*>(this)->Find(key); }
   1.686 +
   1.687 +    template<class K>
   1.688 +    ConstIterator FindAlt(const K& key) const    { return const_cast<SelfType*>(this)->FindAlt(key); }
   1.689 +
   1.690 +private:
   1.691 +    // Find the index of the matching Entry.  If no match, then return -1.
   1.692 +    template<class K>
   1.693 +    intptr_t findIndex(const K& key) const
   1.694 +    {
   1.695 +        if (pTable == NULL)
   1.696 +            return -1;
   1.697 +        size_t hashValue = HashF()(key) & pTable->SizeMask;
   1.698 +        return findIndexCore(key, hashValue);
   1.699 +    }
   1.700 +
   1.701 +    template<class K>
   1.702 +    intptr_t findIndexAlt(const K& key) const
   1.703 +    {
   1.704 +        if (pTable == NULL)
   1.705 +            return -1;
   1.706 +        size_t hashValue = AltHashF()(key) & pTable->SizeMask;
   1.707 +        return findIndexCore(key, hashValue);
   1.708 +    }
   1.709 +
   1.710 +    // Find the index of the matching Entry.  If no match, then return -1.
   1.711 +    template<class K>
   1.712 +    intptr_t findIndexCore(const K& key, size_t hashValue) const
   1.713 +    {
   1.714 +        // Table must exist.
   1.715 +        OVR_ASSERT(pTable != 0);
   1.716 +        // Hash key must be 'and-ed' by the caller.
   1.717 +        OVR_ASSERT((hashValue & ~pTable->SizeMask) == 0);
   1.718 +
   1.719 +        size_t          index = hashValue;
   1.720 +        const Entry*    e     = &E(index);
   1.721 +
   1.722 +        // If empty or occupied by a collider, not found.
   1.723 +        if (e->IsEmpty() || (e->GetCachedHash(pTable->SizeMask) != index))
   1.724 +            return -1;
   1.725 +
   1.726 +        while(1)
   1.727 +        {
   1.728 +            OVR_ASSERT(e->GetCachedHash(pTable->SizeMask) == hashValue);
   1.729 +
   1.730 +            if (e->GetCachedHash(pTable->SizeMask) == hashValue && e->Value == key)
   1.731 +            {
   1.732 +                // Found it.
   1.733 +                return index;
   1.734 +            }
   1.735 +            // Values can not be equal at this point.
   1.736 +            // That would mean that the hash key for the same value differs.
   1.737 +            OVR_ASSERT(!(e->Value == key));
   1.738 +
   1.739 +            // Keep looking through the chain.
   1.740 +            index = e->NextInChain;
   1.741 +            if (index == (size_t)-1)
   1.742 +                break; // end of chain
   1.743 +
   1.744 +            e = &E(index);
   1.745 +            OVR_ASSERT(!e->IsEmpty());
   1.746 +        }
   1.747 +        return -1;
   1.748 +    }
   1.749 +
   1.750 +
   1.751 +    // Add a new value to the HashSet table, under the specified key.
   1.752 +    template<class CRef>
   1.753 +    void add(const CRef& key, size_t hashValue)
   1.754 +    {
   1.755 +        CheckExpand();
   1.756 +        hashValue &= pTable->SizeMask;
   1.757 +
   1.758 +        pTable->EntryCount++;
   1.759 +
   1.760 +        intptr_t   index        = hashValue;
   1.761 +        Entry*  naturalEntry = &(E(index));
   1.762 +
   1.763 +        if (naturalEntry->IsEmpty())
   1.764 +        {
   1.765 +            // Put the new Entry in.
   1.766 +            new (naturalEntry) Entry(key, -1);
   1.767 +        }
   1.768 +        else
   1.769 +        {
   1.770 +            // Find a blank spot.
   1.771 +            intptr_t blankIndex = index;
   1.772 +            do {
   1.773 +                blankIndex = (blankIndex + 1) & pTable->SizeMask;
   1.774 +            } while(!E(blankIndex).IsEmpty());
   1.775 +
   1.776 +            Entry*  blankEntry = &E(blankIndex);
   1.777 +
   1.778 +            if (naturalEntry->GetCachedHash(pTable->SizeMask) == (size_t)index)
   1.779 +            {
   1.780 +                // Collision.  Link into this chain.
   1.781 +
   1.782 +                // Move existing list head.
   1.783 +                new (blankEntry) Entry(*naturalEntry);    // placement new, copy ctor
   1.784 +
   1.785 +                // Put the new info in the natural Entry.
   1.786 +                naturalEntry->Value       = key;
   1.787 +                naturalEntry->NextInChain = blankIndex;
   1.788 +            }
   1.789 +            else
   1.790 +            {
   1.791 +                // Existing Entry does not naturally
   1.792 +                // belong in this slot.  Existing
   1.793 +                // Entry must be moved.
   1.794 +
   1.795 +                // Find natural location of collided element (i.e. root of chain)
   1.796 +                intptr_t collidedIndex = naturalEntry->GetCachedHash(pTable->SizeMask);
   1.797 +                OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)pTable->SizeMask);
   1.798 +                for (;;)
   1.799 +                {
   1.800 +                    Entry*  e = &E(collidedIndex);
   1.801 +                    if (e->NextInChain == index)
   1.802 +                    {
   1.803 +                        // Here's where we need to splice.
   1.804 +                        new (blankEntry) Entry(*naturalEntry);
   1.805 +                        e->NextInChain = blankIndex;
   1.806 +                        break;
   1.807 +                    }
   1.808 +                    collidedIndex = e->NextInChain;
   1.809 +                    OVR_ASSERT(collidedIndex >= 0 && collidedIndex <= (intptr_t)pTable->SizeMask);
   1.810 +                }
   1.811 +
   1.812 +                // Put the new data in the natural Entry.
   1.813 +                naturalEntry->Value       = key;
   1.814 +                naturalEntry->NextInChain = -1;                
   1.815 +            }            
   1.816 +        }
   1.817 +
   1.818 +        // Record hash value: has effect only if cached node is used.
   1.819 +        naturalEntry->SetCachedHash(hashValue);
   1.820 +    }
   1.821 +
   1.822 +    // Index access helpers.
   1.823 +    Entry& E(size_t index)
   1.824 +    {
   1.825 +        // Must have pTable and access needs to be within bounds.
   1.826 +        OVR_ASSERT(index <= pTable->SizeMask);
   1.827 +        return *(((Entry*) (pTable + 1)) + index);
   1.828 +    }
   1.829 +    const Entry& E(size_t index) const
   1.830 +    {        
   1.831 +        OVR_ASSERT(index <= pTable->SizeMask);
   1.832 +        return *(((Entry*) (pTable + 1)) + index);
   1.833 +    }
   1.834 +
   1.835 +
   1.836 +    // Resize the HashSet table to the given size (Rehash the
   1.837 +    // contents of the current table).  The arg is the number of
   1.838 +    // HashSet table entries, not the number of elements we should
   1.839 +    // actually contain (which will be less than this).
   1.840 +    void    setRawCapacity(size_t newSize)    
   1.841 +    {
   1.842 +        if (newSize == 0)
   1.843 +        {
   1.844 +            // Special case.
   1.845 +            Clear();
   1.846 +            return;
   1.847 +        }
   1.848 +
   1.849 +        // Minimum size; don't incur rehashing cost when expanding
   1.850 +        // very small tables. Not that we perform this check before 
   1.851 +        // 'log2f' call to avoid fp exception with newSize == 1.
   1.852 +        if (newSize < HashMinSize)        
   1.853 +            newSize = HashMinSize;       
   1.854 +        else
   1.855 +        {
   1.856 +            // Force newSize to be a power of two.
   1.857 +            int bits = Alg::UpperBit(newSize-1) + 1; // Chop( Log2f((float)(newSize-1)) + 1);
   1.858 +            OVR_ASSERT((size_t(1) << bits) >= newSize);
   1.859 +            newSize = size_t(1) << bits;
   1.860 +        }
   1.861 +
   1.862 +        SelfType  newHash;
   1.863 +        newHash.pTable = (TableType*)
   1.864 +            Allocator::Alloc(                
   1.865 +                sizeof(TableType) + sizeof(Entry) * newSize);
   1.866 +        // Need to do something on alloc failure!
   1.867 +        OVR_ASSERT(newHash.pTable);
   1.868 +
   1.869 +        newHash.pTable->EntryCount = 0;
   1.870 +        newHash.pTable->SizeMask = newSize - 1;
   1.871 +        size_t i, n;
   1.872 +
   1.873 +        // Mark all entries as empty.
   1.874 +        for (i = 0; i < newSize; i++)
   1.875 +            newHash.E(i).NextInChain = -2;
   1.876 +
   1.877 +        // Copy stuff to newHash
   1.878 +        if (pTable)
   1.879 +        {            
   1.880 +            for (i = 0, n = pTable->SizeMask; i <= n; i++)
   1.881 +            {
   1.882 +                Entry*  e = &E(i);
   1.883 +                if (e->IsEmpty() == false)
   1.884 +                {
   1.885 +                    // Insert old Entry into new HashSet.
   1.886 +                    newHash.Add(e->Value);
   1.887 +                    // placement delete of old element
   1.888 +                    e->Clear();
   1.889 +                }
   1.890 +            }
   1.891 +
   1.892 +            // Delete our old data buffer.
   1.893 +            Allocator::Free(pTable);
   1.894 +        }
   1.895 +
   1.896 +        // Steal newHash's data.
   1.897 +        pTable = newHash.pTable;
   1.898 +        newHash.pTable = NULL;
   1.899 +    }
   1.900 +
   1.901 +    struct TableType
   1.902 +    {
   1.903 +        size_t EntryCount;
   1.904 +        size_t SizeMask;
   1.905 +        // Entry array follows this structure
   1.906 +        // in memory.
   1.907 +    };
   1.908 +    TableType*  pTable;
   1.909 +};
   1.910 +
   1.911 +
   1.912 +
   1.913 +//-----------------------------------------------------------------------------------
   1.914 +template<class C, class HashF = FixedSizeHash<C>,
   1.915 +         class AltHashF = HashF, 
   1.916 +         class Allocator = ContainerAllocator<C>,
   1.917 +         class Entry = HashsetCachedEntry<C, HashF> >
   1.918 +class HashSet : public HashSetBase<C, HashF, AltHashF, Allocator, Entry>
   1.919 +{
   1.920 +public:
   1.921 +    typedef HashSetBase<C, HashF, AltHashF, Allocator, Entry> BaseType;
   1.922 +    typedef HashSet<C, HashF, AltHashF, Allocator, Entry>     SelfType;
   1.923 +
   1.924 +    HashSet()                                      {   }
   1.925 +    HashSet(int sizeHint) : BaseType(sizeHint)     {   }
   1.926 +    HashSet(const SelfType& src) : BaseType(src)   {   }
   1.927 +    ~HashSet()                                     {   }
   1.928 +
   1.929 +    void operator = (const SelfType& src)   { BaseType::Assign(src); }
   1.930 +
   1.931 +    // Set a new or existing value under the key, to the value.
   1.932 +    // Pass a different class of 'key' so that assignment reference object
   1.933 +    // can be passed instead of the actual object.
   1.934 +    template<class CRef>
   1.935 +    void Set(const CRef& key)
   1.936 +    {
   1.937 +        BaseType::Set(key);
   1.938 +    }
   1.939 +
   1.940 +    template<class CRef>
   1.941 +    inline void Add(const CRef& key)
   1.942 +    {
   1.943 +        BaseType::Add(key);
   1.944 +    }
   1.945 +
   1.946 +    // Hint the bucket count to >= n.
   1.947 +    void Resize(size_t n)    
   1.948 +    {
   1.949 +        BaseType::SetCapacity(n);
   1.950 +    }
   1.951 +
   1.952 +    // Size the HashSet so that it can comfortably contain the given
   1.953 +    // number of elements.  If the HashSet already contains more
   1.954 +    // elements than newSize, then this may be a no-op.
   1.955 +    void SetCapacity(size_t newSize)
   1.956 +    {
   1.957 +        BaseType::SetCapacity(newSize);
   1.958 +    }
   1.959 +
   1.960 +};
   1.961 +
   1.962 +// HashSet with uncached hash code; declared for convenience.
   1.963 +template<class C, class HashF = FixedSizeHash<C>,
   1.964 +                  class AltHashF = HashF,
   1.965 +                  class Allocator = ContainerAllocator<C> >
   1.966 +class HashSetUncached : public HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> >
   1.967 +{
   1.968 +public:
   1.969 +    
   1.970 +    typedef HashSetUncached<C, HashF, AltHashF, Allocator>                  SelfType;
   1.971 +    typedef HashSet<C, HashF, AltHashF, Allocator, HashsetEntry<C, HashF> > BaseType;
   1.972 +
   1.973 +    // Delegated constructors.
   1.974 +    HashSetUncached()                                        { }
   1.975 +    HashSetUncached(int sizeHint) : BaseType(sizeHint)       { }
   1.976 +    HashSetUncached(const SelfType& src) : BaseType(src)     { }
   1.977 +    ~HashSetUncached()                                       { }
   1.978 +    
   1.979 +    void    operator = (const SelfType& src)
   1.980 +    {
   1.981 +        BaseType::operator = (src);
   1.982 +    }
   1.983 +};
   1.984 +
   1.985 +
   1.986 +//-----------------------------------------------------------------------------------
   1.987 +// ***** Hash hash table implementation
   1.988 +
   1.989 +// Node for Hash - necessary so that Hash can delegate its implementation
   1.990 +// to HashSet.
   1.991 +template<class C, class U, class HashF>
   1.992 +struct HashNode
   1.993 +{
   1.994 +    typedef HashNode<C, U, HashF>   SelfType;
   1.995 +    typedef C                       FirstType;
   1.996 +    typedef U                       SecondType;
   1.997 +
   1.998 +    C   First;
   1.999 +    U   Second;
  1.1000 +
  1.1001 +    // NodeRef is used to allow passing of elements into HashSet
  1.1002 +    // without using a temporary object.
  1.1003 +    struct NodeRef
  1.1004 +    {
  1.1005 +        const C*   pFirst;
  1.1006 +        const U*   pSecond;
  1.1007 +
  1.1008 +        NodeRef(const C& f, const U& s) : pFirst(&f), pSecond(&s) { }
  1.1009 +        NodeRef(const NodeRef& src)     : pFirst(src.pFirst), pSecond(src.pSecond) { }
  1.1010 +
  1.1011 +        // Enable computation of ghash_node_hashf.
  1.1012 +        inline size_t GetHash() const            { return HashF()(*pFirst); } 
  1.1013 +        // Necessary conversion to allow HashNode::operator == to work.
  1.1014 +        operator const C& () const              { return *pFirst; }
  1.1015 +    };
  1.1016 +
  1.1017 +    // Note: No default constructor is necessary.
  1.1018 +     HashNode(const HashNode& src) : First(src.First), Second(src.Second)    { }
  1.1019 +     HashNode(const NodeRef& src) : First(*src.pFirst), Second(*src.pSecond)  { }
  1.1020 +    void operator = (const NodeRef& src)  { First  = *src.pFirst; Second = *src.pSecond; }
  1.1021 +
  1.1022 +    template<class K>
  1.1023 +    bool operator == (const K& src) const   { return (First == src); }
  1.1024 +
  1.1025 +    template<class K>
  1.1026 +    static size_t CalcHash(const K& data)   { return HashF()(data); }
  1.1027 +    inline size_t GetHash() const           { return HashF()(First); }
  1.1028 +
  1.1029 +    // Hash functors used with this node. A separate functor is used for alternative
  1.1030 +    // key lookup so that it does not need to access the '.First' element.    
  1.1031 +    struct NodeHashF
  1.1032 +    {    
  1.1033 +        template<class K>
  1.1034 +        size_t operator()(const K& data) const { return data.GetHash(); } 
  1.1035 +    };    
  1.1036 +    struct NodeAltHashF
  1.1037 +    {
  1.1038 +        template<class K>
  1.1039 +        size_t operator()(const K& data) const { return HashNode<C,U,HashF>::CalcHash(data); }
  1.1040 +    };
  1.1041 +};
  1.1042 +
  1.1043 +
  1.1044 +
  1.1045 +// **** Extra hashset_entry types to allow NodeRef construction.
  1.1046 +
  1.1047 +// The big difference between the below types and the ones used in hash_set is that
  1.1048 +// these allow initializing the node with 'typename C::NodeRef& keyRef', which
  1.1049 +// is critical to avoid temporary node allocation on stack when using placement new.
  1.1050 +
  1.1051 +// Compact hash table Entry type that re-computes hash keys during hash traversal.
  1.1052 +// Good to use if the hash function is cheap or the hash value is already cached in C.
  1.1053 +template<class C, class HashF>
  1.1054 +class HashsetNodeEntry
  1.1055 +{
  1.1056 +public:
  1.1057 +    // Internal chaining for collisions.
  1.1058 +    intptr_t NextInChain;
  1.1059 +    C     Value;
  1.1060 +
  1.1061 +    HashsetNodeEntry()
  1.1062 +        : NextInChain(-2) { }
  1.1063 +    HashsetNodeEntry(const HashsetNodeEntry& e)
  1.1064 +        : NextInChain(e.NextInChain), Value(e.Value) { }
  1.1065 +    HashsetNodeEntry(const C& key, intptr_t next)
  1.1066 +        : NextInChain(next), Value(key) { }    
  1.1067 +    HashsetNodeEntry(const typename C::NodeRef& keyRef, intptr_t next)
  1.1068 +        : NextInChain(next), Value(keyRef) { }
  1.1069 +
  1.1070 +    bool    IsEmpty() const             { return NextInChain == -2;  }
  1.1071 +    bool    IsEndOfChain() const        { return NextInChain == -1;  }
  1.1072 +    size_t  GetCachedHash(size_t maskValue) const  { return HashF()(Value) & maskValue; }
  1.1073 +    void    SetCachedHash(size_t hashValue)        { OVR_UNUSED(hashValue); }
  1.1074 +
  1.1075 +    void    Clear()
  1.1076 +    {        
  1.1077 +        Value.~C(); // placement delete
  1.1078 +        NextInChain = -2;
  1.1079 +    }
  1.1080 +    // Free is only used from dtor of hash; Clear is used during regular operations:
  1.1081 +    // assignment, hash reallocations, value reassignments, so on.
  1.1082 +    void    Free() { Clear(); }
  1.1083 +};
  1.1084 +
  1.1085 +// Hash table Entry type that caches the Entry hash value for nodes, so that it
  1.1086 +// does not need to be re-computed during access.
  1.1087 +template<class C, class HashF>
  1.1088 +class HashsetCachedNodeEntry
  1.1089 +{
  1.1090 +public:
  1.1091 +    // Internal chaining for collisions.
  1.1092 +    intptr_t NextInChain;
  1.1093 +    size_t HashValue;
  1.1094 +    C     Value;
  1.1095 +
  1.1096 +    HashsetCachedNodeEntry()
  1.1097 +        : NextInChain(-2) { }
  1.1098 +    HashsetCachedNodeEntry(const HashsetCachedNodeEntry& e)
  1.1099 +        : NextInChain(e.NextInChain), HashValue(e.HashValue), Value(e.Value) { }
  1.1100 +    HashsetCachedNodeEntry(const C& key, intptr_t next)
  1.1101 +        : NextInChain(next), Value(key) { }
  1.1102 +    HashsetCachedNodeEntry(const typename C::NodeRef& keyRef, intptr_t next)
  1.1103 +        : NextInChain(next), Value(keyRef) { }
  1.1104 +
  1.1105 +    bool    IsEmpty() const            { return NextInChain == -2;  }
  1.1106 +    bool    IsEndOfChain() const       { return NextInChain == -1;  }
  1.1107 +    size_t  GetCachedHash(size_t maskValue) const  { OVR_UNUSED(maskValue); return HashValue; }
  1.1108 +    void    SetCachedHash(size_t hashValue)        { HashValue = hashValue; }
  1.1109 +
  1.1110 +    void    Clear()
  1.1111 +    {
  1.1112 +        Value.~C();
  1.1113 +        NextInChain = -2;
  1.1114 +    }
  1.1115 +    // Free is only used from dtor of hash; Clear is used during regular operations:
  1.1116 +    // assignment, hash reallocations, value reassignments, so on.
  1.1117 +    void    Free() { Clear(); }
  1.1118 +};
  1.1119 +
  1.1120 +
  1.1121 +//-----------------------------------------------------------------------------------
  1.1122 +template<class C, class U,
  1.1123 +         class HashF = FixedSizeHash<C>,
  1.1124 +         class Allocator = ContainerAllocator<C>,
  1.1125 +         class HashNode = OVR::HashNode<C,U,HashF>,
  1.1126 +         class Entry = HashsetCachedNodeEntry<HashNode, typename HashNode::NodeHashF>,
  1.1127 +         class Container =  HashSet<HashNode, typename HashNode::NodeHashF,
  1.1128 +             typename HashNode::NodeAltHashF, Allocator,
  1.1129 +             Entry> >
  1.1130 +class Hash
  1.1131 +{
  1.1132 +public:
  1.1133 +    OVR_MEMORY_REDEFINE_NEW(Hash)
  1.1134 +
  1.1135 +    // Types used for hash_set.
  1.1136 +    typedef U                                                           ValueType;
  1.1137 +    typedef Hash<C, U, HashF, Allocator, HashNode, Entry, Container>    SelfType;
  1.1138 +
  1.1139 +    // Actual hash table itself, implemented as hash_set.
  1.1140 +    Container   mHash;
  1.1141 +
  1.1142 +public:
  1.1143 +    Hash()     {  }
  1.1144 +    Hash(int sizeHint) : mHash(sizeHint)                        { }
  1.1145 +    Hash(const SelfType& src) : mHash(src.mHash)                { }
  1.1146 +    ~Hash()                                                     { }
  1.1147 +
  1.1148 +    void    operator = (const SelfType& src)    { mHash = src.mHash; }
  1.1149 +
  1.1150 +    // Remove all entries from the Hash table.
  1.1151 +    inline void    Clear() { mHash.Clear(); }
  1.1152 +    // Returns true if the Hash is empty.
  1.1153 +    inline bool    IsEmpty() const { return mHash.IsEmpty(); }
  1.1154 +
  1.1155 +    // Access (set).
  1.1156 +    inline void    Set(const C& key, const U& value)
  1.1157 +    {
  1.1158 +        typename HashNode::NodeRef e(key, value);
  1.1159 +        mHash.Set(e);
  1.1160 +    }
  1.1161 +    inline void    Add(const C& key, const U& value)
  1.1162 +    {
  1.1163 +        typename HashNode::NodeRef e(key, value);
  1.1164 +        mHash.Add(e);
  1.1165 +    }
  1.1166 +
  1.1167 +    // Removes an element by clearing its Entry.
  1.1168 +    inline void     Remove(const C& key)
  1.1169 +    {   
  1.1170 +        mHash.RemoveAlt(key);
  1.1171 +    }
  1.1172 +    template<class K>
  1.1173 +    inline void     RemoveAlt(const K& key)
  1.1174 +    {   
  1.1175 +        mHash.RemoveAlt(key);
  1.1176 +    }
  1.1177 +
  1.1178 +    // Retrieve the value under the given key.    
  1.1179 +    //  - If there's no value under the key, then return false and leave *pvalue alone.
  1.1180 +    //  - If there is a value, return true, and Set *Pvalue to the Entry's value.
  1.1181 +    //  - If value == NULL, return true or false according to the presence of the key.    
  1.1182 +    bool    Get(const C& key, U* pvalue) const   
  1.1183 +    {
  1.1184 +        const HashNode* p = mHash.GetAlt(key);
  1.1185 +        if (p)
  1.1186 +        {
  1.1187 +            if (pvalue)
  1.1188 +                *pvalue = p->Second;
  1.1189 +            return true;
  1.1190 +        }
  1.1191 +        return false;
  1.1192 +    }
  1.1193 +
  1.1194 +    template<class K>
  1.1195 +    bool    GetAlt(const K& key, U* pvalue) const   
  1.1196 +    {
  1.1197 +        const HashNode* p = mHash.GetAlt(key);
  1.1198 +        if (p)
  1.1199 +        {
  1.1200 +            if (pvalue)
  1.1201 +                *pvalue = p->Second;
  1.1202 +            return true;
  1.1203 +        }
  1.1204 +        return false;
  1.1205 +    }
  1.1206 +
  1.1207 +    // Retrieve the pointer to a value under the given key.    
  1.1208 +    //  - If there's no value under the key, then return NULL.    
  1.1209 +    //  - If there is a value, return the pointer.    
  1.1210 +    inline U*  Get(const C& key)
  1.1211 +    {
  1.1212 +        HashNode* p = mHash.GetAlt(key);
  1.1213 +        return p ? &p->Second : 0;
  1.1214 +    }
  1.1215 +    inline const U* Get(const C& key) const
  1.1216 +    {
  1.1217 +        const HashNode* p = mHash.GetAlt(key);
  1.1218 +        return p ? &p->Second : 0;
  1.1219 +    }
  1.1220 +
  1.1221 +    template<class K>
  1.1222 +    inline U*  GetAlt(const K& key)
  1.1223 +    {
  1.1224 +        HashNode* p = mHash.GetAlt(key);
  1.1225 +        return p ? &p->Second : 0;
  1.1226 +    }
  1.1227 +    template<class K>
  1.1228 +    inline const U* GetAlt(const K& key) const
  1.1229 +    {
  1.1230 +        const HashNode* p = mHash.GetAlt(key);
  1.1231 +        return p ? &p->Second : 0;
  1.1232 +    }
  1.1233 +
  1.1234 +    // Sizing methods - delegate to Hash.
  1.1235 +    inline size_t  GetSize() const              { return mHash.GetSize(); }    
  1.1236 +	inline int     GetSizeI() const             { return (int)GetSize(); }
  1.1237 +	inline void    Resize(size_t n)              { mHash.Resize(n); }
  1.1238 +    inline void    SetCapacity(size_t newSize)   { mHash.SetCapacity(newSize); }
  1.1239 +
  1.1240 +    // Iterator API, like STL.
  1.1241 +    typedef typename Container::ConstIterator   ConstIterator;
  1.1242 +    typedef typename Container::Iterator        Iterator;
  1.1243 +
  1.1244 +    inline Iterator        Begin()              { return mHash.Begin(); }
  1.1245 +    inline Iterator        End()                { return mHash.End(); }
  1.1246 +    inline ConstIterator   Begin() const        { return mHash.Begin(); }
  1.1247 +    inline ConstIterator   End() const          { return mHash.End();   }
  1.1248 +
  1.1249 +    Iterator        Find(const C& key)          { return mHash.FindAlt(key);  }
  1.1250 +    ConstIterator   Find(const C& key) const    { return mHash.FindAlt(key);  }
  1.1251 +
  1.1252 +    template<class K>
  1.1253 +    Iterator        FindAlt(const K& key)       { return mHash.FindAlt(key);  }
  1.1254 +    template<class K>
  1.1255 +    ConstIterator   FindAlt(const K& key) const { return mHash.FindAlt(key);  }
  1.1256 +};
  1.1257 +
  1.1258 +
  1.1259 +
  1.1260 +// Hash with uncached hash code; declared for convenience.
  1.1261 +template<class C, class U, class HashF = FixedSizeHash<C>, class Allocator = ContainerAllocator<C> >
  1.1262 +class HashUncached
  1.1263 +    : public Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
  1.1264 +                   HashsetNodeEntry<HashNode<C,U,HashF>, typename HashNode<C,U,HashF>::NodeHashF> >
  1.1265 +{
  1.1266 +public:
  1.1267 +    typedef HashUncached<C, U, HashF, Allocator>                SelfType;
  1.1268 +    typedef Hash<C, U, HashF, Allocator, HashNode<C,U,HashF>,
  1.1269 +                 HashsetNodeEntry<HashNode<C,U,HashF>,
  1.1270 +                 typename HashNode<C,U,HashF>::NodeHashF> >     BaseType;
  1.1271 +
  1.1272 +    // Delegated constructors.
  1.1273 +    HashUncached()                                        { }
  1.1274 +    HashUncached(int sizeHint) : BaseType(sizeHint)       { }
  1.1275 +    HashUncached(const SelfType& src) : BaseType(src)     { }
  1.1276 +    ~HashUncached()                                       { }
  1.1277 +    void operator = (const SelfType& src)                 { BaseType::operator = (src); }
  1.1278 +};
  1.1279 +
  1.1280 +
  1.1281 +
  1.1282 +// And identity hash in which keys serve as hash value. Can be uncached,
  1.1283 +// since hash computation is assumed cheap.
  1.1284 +template<class C, class U, class Allocator = ContainerAllocator<C>, class HashF = IdentityHash<C> >
  1.1285 +class HashIdentity
  1.1286 +    : public HashUncached<C, U, HashF, Allocator>
  1.1287 +{
  1.1288 +public:
  1.1289 +    typedef HashIdentity<C, U, Allocator, HashF> SelfType;
  1.1290 +    typedef HashUncached<C, U, HashF, Allocator> BaseType;
  1.1291 +
  1.1292 +    // Delegated constructors.
  1.1293 +    HashIdentity()                                        { }
  1.1294 +    HashIdentity(int sizeHint) : BaseType(sizeHint)       { }
  1.1295 +    HashIdentity(const SelfType& src) : BaseType(src)     { }
  1.1296 +    ~HashIdentity()                                       { }
  1.1297 +    void operator = (const SelfType& src)                 { BaseType::operator = (src); }
  1.1298 +};
  1.1299 +
  1.1300 +
  1.1301 +} // OVR
  1.1302 +
  1.1303 +
  1.1304 +#ifdef OVR_DEFINE_NEW
  1.1305 +#define new OVR_DEFINE_NEW
  1.1306 +#endif
  1.1307 +
  1.1308 +#endif