git.cworth.org Git - vogl/blob - src/voglcore/vogl_rh_hash_map.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_rh_hash_map.h
  28 //
  29 // Notes:
  30 // stl-like hash map/hash set, with predictable performance across platforms/compilers/C run-times libs/etc.
  31 //
  32 // Robin Hood hashing, open addressing, hashtable contains pointers to keys/values, backshifting on erasures.
  33 // No support for items with duplicate keys (use vogl::map instead).
  34 #pragma once
  35
  36 #include "vogl_core.h"
  37 #include "vogl_hash.h"
  38 #include "vogl_data_stream_serializer.h"
  39 #include "vogl_object_pool.h"
  40
  41 namespace vogl
  42 {
  43     template <typename T>
  44     class heap_allocator
  45     {
  46     public:
  47         heap_allocator()
  48         {
  49         }
  50
  51         void clear()
  52         {
  53         }
  54
  55         void swap(heap_allocator &other)
  56         {
  57             VOGL_NOTE_UNUSED(other);
  58         }
  59
  60         bool is_valid_ptr(void *p) const
  61         {
  62             return (p != NULL) && (reinterpret_cast<uintptr_t>(p) & (VOGL_MIN_ALLOC_ALIGNMENT - 1)) == 0;
  63         }
  64
  65         T *alloc_no_construction()
  66         {
  67             return static_cast<T *>(vogl_malloc(sizeof(T)));
  68         }
  69
  70         void destroy_no_destruction(void *p)
  71         {
  72             vogl_free(p);
  73         }
  74     };
  75
  76     template <typename T>
  77     class pool_allocator
  78     {
  79         object_pool<T> m_pool;
  80
  81     public:
  82         pool_allocator()
  83         {
  84         }
  85
  86         void clear()
  87         {
  88             m_pool.clear();
  89         }
  90
  91         void swap(pool_allocator &other)
  92         {
  93             m_pool.swap(other.m_pool);
  94         }
  95
  96         bool is_valid_ptr(const T *p) const
  97         {
  98             return m_pool.is_valid_ptr(p);
  99         }
 100
 101         T *alloc_no_construction()
 102         {
 103             return m_pool.alloc_no_construction();
 104         }
 105
 106         void destroy_no_destruction(T *p)
 107         {
 108             m_pool.destroy_no_destruction(p);
 109         }
 110     };
 111
 112     // See vogl_types.h for the default hash function and more alternatives.
 113
 114     // With default template options the type should define operator size_t() (for hashing) and operator== (for equality).
 115     // The Key and Value objects are stored contiguously in the hash table, and will move on rehashing.
 116     // Iterators are invalidated on rehashing or erasing.
 117     // The Hasher and Equals objects must be bitwise movable (i.e. using memcpy).
 118     template <typename Key, typename Value = empty_type, typename Hasher = hasher<Key>, typename Equals = equal_to<Key>, typename Allocator = pool_allocator<std::pair<Key, Value> > >
 119     class rh_hash_map
 120     {
 121         friend class iterator;
 122         friend class const_iterator;
 123
 124         enum
 125         {
 126             cMinHashSize = 4U
 127         };
 128
 129     public:
 130         typedef rh_hash_map<Key, Value, Hasher, Equals> rh_hash_map_type;
 131         typedef std::pair<Key, Value> value_type;
 132         typedef Key key_type;
 133         typedef Value referent_type;
 134         typedef Hasher hasher_type;
 135         typedef Equals equals_type;
 136         typedef Allocator allocator_type;
 137
 138         rh_hash_map()
 139             : m_hash_shift(32),
 140               m_num_valid(0),
 141               m_grow_threshold(0)
 142         {
 143         }
 144
 145         rh_hash_map(const rh_hash_map &other)
 146             : m_hash_shift(32),
 147               m_num_valid(0),
 148               m_grow_threshold(0)
 149         {
 150             *this = other;
 151         }
 152
 153         rh_hash_map &operator=(const rh_hash_map &other)
 154         {
 155             if (this == &other)
 156                 return *this;
 157
 158             clear();
 159
 160             m_values.resize(other.m_values.size());
 161
 162             m_hash_shift = other.m_hash_shift;
 163             m_grow_threshold = other.m_grow_threshold;
 164             m_num_valid = other.m_num_valid;
 165             m_hasher = other.m_hasher;
 166             m_equals = other.m_equals;
 167
 168             const hash_entry *pSrc_entry = other.m_values.get_ptr();
 169
 170             hash_entry *pDst_entry = m_values.get_ptr();
 171             hash_entry *pDst_entry_end = m_values.end();
 172
 173             while (pDst_entry != pDst_entry_end)
 174             {
 175                 if (pSrc_entry->m_pValue)
 176                 {
 177                     pDst_entry->m_pValue = construct_value_type(pSrc_entry->m_pValue->first, pSrc_entry->m_pValue->second);
 178                     pDst_entry->m_hash = pSrc_entry->m_hash;
 179                 }
 180                 else
 181                 {
 182                     memset(pDst_entry, 0, sizeof(hash_entry));
 183                 }
 184
 185                 ++pSrc_entry;
 186                 ++pDst_entry;
 187             }
 188
 189             return *this;
 190         }
 191
 192         inline ~rh_hash_map()
 193         {
 194             clear();
 195         }
 196
 197         const Equals &get_equals() const
 198         {
 199             return m_equals;
 200         }
 201         Equals &get_equals()
 202         {
 203             return m_equals;
 204         }
 205
 206         void set_equals(const Equals &equals)
 207         {
 208             m_equals = equals;
 209         }
 210
 211         const Hasher &get_hasher() const
 212         {
 213             return m_hasher;
 214         }
 215         Hasher &get_hasher()
 216         {
 217             return m_hasher;
 218         }
 219
 220         void set_hasher(const Hasher &hasher)
 221         {
 222             m_hasher = hasher;
 223         }
 224
 225         const allocator_type &get_allocator() const
 226         {
 227             return m_allocator;
 228         }
 229         allocator_type &get_allocator()
 230         {
 231             return m_allocator;
 232         }
 233
 234         void set_allocator(const allocator_type &alloc)
 235         {
 236             m_allocator = alloc;
 237         }
 238
 239         // erases container, but doesn't free the allocated memory block
 240         inline void reset()
 241         {
 242             uint num_remaining = m_num_valid;
 243             if (!num_remaining)
 244                 return;
 245
 246             hash_entry *p = m_values.begin();
 247             hash_entry *p_end = m_values.end();
 248
 249             while (p != p_end)
 250             {
 251                 if (p->m_pValue)
 252                 {
 253                     delete_value_type(p->m_pValue);
 254                     p->m_pValue = NULL;
 255
 256                     --num_remaining;
 257                     if (!num_remaining)
 258                         break;
 259                 }
 260
 261                 ++p;
 262             }
 263
 264             m_num_valid = 0;
 265         }
 266
 267         inline void clear()
 268         {
 269             hash_entry *p = m_values.begin();
 270             hash_entry *p_end = m_values.end();
 271
 272             uint num_remaining = m_num_valid;
 273             while (p != p_end)
 274             {
 275                 value_type *pValue = p->m_pValue;
 276                 if (pValue)
 277                 {
 278                     scalar_type<Key>::destruct(&pValue->first);
 279                     scalar_type<Value>::destruct(&pValue->second);
 280
 281                     --num_remaining;
 282                     if (!num_remaining)
 283                         break;
 284                 }
 285
 286                 ++p;
 287             }
 288
 289             m_values.clear_no_destruction();
 290
 291             m_hash_shift = 32;
 292             m_grow_threshold = 0;
 293             m_num_valid = 0;
 294
 295             m_allocator.clear();
 296         }
 297
 298         // Returns the number of active items in the container.
 299         inline uint size() const
 300         {
 301             return m_num_valid;
 302         }
 303
 304         // Returns the size of the hash table.
 305         inline uint get_table_size() const
 306         {
 307             return m_values.size();
 308         }
 309
 310         inline bool is_empty() const
 311         {
 312             return !m_num_valid;
 313         }
 314
 315         // Before insertion, when the size() == get_grow_threshold() the container will rehash (double in size).
 316         inline uint get_grow_threshold() const
 317         {
 318             return m_grow_threshold;
 319         }
 320
 321         inline bool will_rehash_on_next_insertion() const
 322         {
 323             return m_num_valid >= m_grow_threshold;
 324         }
 325
 326         inline void reserve(uint new_capacity)
 327         {
 328             if (!new_capacity)
 329                 return;
 330
 331             uint new_hash_size = new_capacity;
 332
 333             new_hash_size = new_hash_size * 2U;
 334
 335             if (!math::is_power_of_2(new_hash_size))
 336                 new_hash_size = math::next_pow2(new_hash_size);
 337
 338             new_hash_size = math::maximum<uint>(cMinHashSize, new_hash_size);
 339
 340             if (new_hash_size > m_values.size())
 341                 rehash(new_hash_size);
 342         }
 343
 344         class const_iterator;
 345
 346         class iterator
 347         {
 348             friend class rh_hash_map<Key, Value, Hasher, Equals>;
 349             friend class rh_hash_map<Key, Value, Hasher, Equals>::const_iterator;
 350
 351         public:
 352             inline iterator()
 353                 : m_pTable(NULL), m_index(0)
 354             {
 355             }
 356             inline iterator(rh_hash_map_type &table, uint index)
 357                 : m_pTable(&table), m_index(index)
 358             {
 359             }
 360             inline iterator(const iterator &other)
 361                 : m_pTable(other.m_pTable), m_index(other.m_index)
 362             {
 363             }
 364
 365             inline iterator &operator=(const iterator &other)
 366             {
 367                 m_pTable = other.m_pTable;
 368                 m_index = other.m_index;
 369                 return *this;
 370             }
 371
 372             // post-increment
 373             inline iterator operator++(int)
 374             {
 375                 iterator result(*this);
 376                 ++*this;
 377                 return result;
 378             }
 379
 380             // pre-increment
 381             inline iterator &operator++()
 382             {
 383                 probe();
 384                 return *this;
 385             }
 386
 387             inline value_type &operator*() const
 388             {
 389                 return *get_cur();
 390             }
 391             inline value_type *operator->() const
 392             {
 393                 return get_cur();
 394             }
 395
 396             inline bool operator==(const iterator &b) const
 397             {
 398                 return (m_pTable == b.m_pTable) && (m_index == b.m_index);
 399             }
 400             inline bool operator!=(const iterator &b) const
 401             {
 402                 return !(*this == b);
 403             }
 404             inline bool operator==(const const_iterator &b) const
 405             {
 406                 return (m_pTable == b.m_pTable) && (m_index == b.m_index);
 407             }
 408             inline bool operator!=(const const_iterator &b) const
 409             {
 410                 return !(*this == b);
 411             }
 412
 413             inline uint get_index() const
 414             {
 415                 return m_index;
 416             }
 417
 418         private:
 419             rh_hash_map_type *m_pTable;
 420             uint m_index;
 421
 422             inline value_type *get_cur() const
 423             {
 424                 VOGL_ASSERT(m_pTable && (m_index < m_pTable->m_values.size()));
 425                 VOGL_ASSERT(m_pTable->m_values[m_index].m_pValue != NULL);
 426                 return m_pTable->m_values[m_index].m_pValue;
 427             }
 428
 429             inline void probe()
 430             {
 431                 VOGL_ASSERT(m_pTable);
 432                 m_index = m_pTable->find_next(m_index);
 433             }
 434         };
 435
 436         class const_iterator
 437         {
 438             friend class rh_hash_map<Key, Value, Hasher, Equals>;
 439             friend class rh_hash_map<Key, Value, Hasher, Equals>::iterator;
 440
 441         public:
 442             inline const_iterator()
 443                 : m_pTable(NULL), m_index(0)
 444             {
 445             }
 446             inline const_iterator(const rh_hash_map_type &table, uint index)
 447                 : m_pTable(&table), m_index(index)
 448             {
 449             }
 450             inline const_iterator(const iterator &other)
 451                 : m_pTable(other.m_pTable), m_index(other.m_index)
 452             {
 453             }
 454             inline const_iterator(const const_iterator &other)
 455                 : m_pTable(other.m_pTable), m_index(other.m_index)
 456             {
 457             }
 458
 459             inline const_iterator &operator=(const const_iterator &other)
 460             {
 461                 m_pTable = other.m_pTable;
 462                 m_index = other.m_index;
 463                 return *this;
 464             }
 465
 466             inline const_iterator &operator=(const iterator &other)
 467             {
 468                 m_pTable = other.m_pTable;
 469                 m_index = other.m_index;
 470                 return *this;
 471             }
 472
 473             // post-increment
 474             inline const_iterator operator++(int)
 475             {
 476                 const_iterator result(*this);
 477                 ++*this;
 478                 return result;
 479             }
 480
 481             // pre-increment
 482             inline const_iterator &operator++()
 483             {
 484                 probe();
 485                 return *this;
 486             }
 487
 488             inline const value_type &operator*() const
 489             {
 490                 return *get_cur();
 491             }
 492             inline const value_type *operator->() const
 493             {
 494                 return get_cur();
 495             }
 496
 497             inline bool operator==(const const_iterator &b) const
 498             {
 499                 return (m_pTable == b.m_pTable) && (m_index == b.m_index);
 500             }
 501             inline bool operator!=(const const_iterator &b) const
 502             {
 503                 return !(*this == b);
 504             }
 505             inline bool operator==(const iterator &b) const
 506             {
 507                 return (m_pTable == b.m_pTable) && (m_index == b.m_index);
 508             }
 509             inline bool operator!=(const iterator &b) const
 510             {
 511                 return !(*this == b);
 512             }
 513
 514             inline uint get_index() const
 515             {
 516                 return m_index;
 517             }
 518
 519         private:
 520             const rh_hash_map_type *m_pTable;
 521             uint m_index;
 522
 523             inline const value_type *get_cur() const
 524             {
 525                 VOGL_ASSERT(m_pTable && (m_index < m_pTable->m_values.size()));
 526                 VOGL_ASSERT(m_pTable->m_values[m_index].m_pValue != NULL);
 527                 return m_pTable->m_values[m_index].m_pValue;
 528             }
 529
 530             inline void probe()
 531             {
 532                 VOGL_ASSERT(m_pTable);
 533                 m_index = m_pTable->find_next(m_index);
 534             }
 535         };
 536
 537         inline const_iterator begin() const
 538         {
 539             if (!m_num_valid)
 540                 return end();
 541
 542             return const_iterator(*this, find_next(-1));
 543         }
 544
 545         inline const_iterator end() const
 546         {
 547             return const_iterator(*this, m_values.size());
 548         }
 549
 550         inline iterator begin()
 551         {
 552             if (!m_num_valid)
 553                 return end();
 554
 555             return iterator(*this, find_next(-1));
 556         }
 557
 558         inline iterator end()
 559         {
 560             return iterator(*this, m_values.size());
 561         }
 562
 563         // insert_result.first will always point to inserted key/value (or the already existing key/value).
 564         // insert_result.second will be true if a new key/value was inserted, or false if the key already existed (in which case first will point to the already existing value).
 565         // insert() may grow the container. After growing, any iterators (and indices) will be invalid.
 566         typedef std::pair<iterator, bool> insert_result;
 567
 568         inline insert_result insert(const Key &k, const Value &v = Value())
 569         {
 570             insert_result result;
 571             if (!insert_no_grow(result, k, v))
 572             {
 573                 grow();
 574
 575                 // This must succeed.
 576                 if (!insert_no_grow(result, k, v))
 577                 {
 578                     VOGL_FAIL("insert() failed");
 579                 }
 580             }
 581
 582             return result;
 583         }
 584
 585         inline insert_result insert(const value_type &v)
 586         {
 587             return insert(v.first, v.second);
 588         }
 589
 590         inline bool insert_no_grow(insert_result &result, const Key &k, const Value &v = Value())
 591         {
 592             if ((!m_values.size()) || (m_num_valid >= m_grow_threshold))
 593                 return false;
 594
 595             value_type *pValue = NULL;
 596             uint hash = hash_key(k);
 597             uint index_init = hash >> m_hash_shift;
 598
 599             const uint size = m_values.size();
 600
 601             uint index_current = index_init & (size - 1);
 602             uint probe_current = 0;
 603             while (true)
 604             {
 605                 hash_entry *pEntry = &m_values[index_current];
 606
 607                 if (!pEntry->m_pValue)
 608                 {
 609                     if (!pValue)
 610                     {
 611                         pValue = construct_value_type(k, v);
 612
 613                         ++m_num_valid;
 614                         VOGL_ASSERT(m_num_valid <= size);
 615
 616                         result.first = iterator(*this, index_current);
 617                         result.second = true;
 618                     }
 619
 620                     pEntry->m_pValue = pValue;
 621                     pEntry->m_hash = hash;
 622                     break;
 623                 }
 624
 625                 if ((!pValue) && (m_equals(pEntry->m_pValue->first, k)))
 626                 {
 627                     result.first = iterator(*this, index_current);
 628                     result.second = false;
 629                     break;
 630                 }
 631
 632                 uint probe_distance = calc_distance(index_current);
 633                 if (probe_current > probe_distance)
 634                 {
 635                     if (!pValue)
 636                     {
 637                         pValue = construct_value_type(k, v);
 638
 639                         ++m_num_valid;
 640                         VOGL_ASSERT(m_num_valid <= size);
 641
 642                         result.first = iterator(*this, index_current);
 643                         result.second = true;
 644                     }
 645
 646                     value_type *pTemp_value = pEntry->m_pValue;
 647                     uint temp_hash = pEntry->m_hash;
 648
 649                     pEntry->m_pValue = pValue;
 650                     pEntry->m_hash = hash;
 651
 652                     pValue = pTemp_value;
 653                     hash = temp_hash;
 654
 655                     probe_current = probe_distance;
 656                 }
 657
 658                 if (++index_current == size)
 659                     index_current = 0;
 660
 661                 ++probe_current;
 662             }
 663
 664             return true;
 665         }
 666
 667         inline Value &operator[](const Key &key)
 668         {
 669             return (insert(key).first)->second;
 670         }
 671
 672         // Returns const ref to value if key is found, otherwise returns the default.
 673         inline const Value &value(const Key &key, const Value &def = Value()) const
 674         {
 675             const_iterator it(find(key));
 676             if (it != end())
 677                 return it->second;
 678             return def;
 679         }
 680
 681         // Returns index if found, or index==size() if not found.
 682         uint find_index(const Key &k) const
 683         {
 684             uint hash = hash_key(k);
 685             uint index_init = hash >> m_hash_shift;
 686
 687             const uint size = m_values.size();
 688
 689             for (uint i = 0; i < size; ++i)
 690             {
 691                 uint index_current = (index_init + i) & (size - 1);
 692                 const hash_entry *pEntry = &m_values[index_current];
 693
 694                 if (!pEntry->m_pValue)
 695                     break;
 696
 697                 uint probe_distance = calc_distance(index_current);
 698                 if (i > probe_distance)
 699                     break;
 700
 701                 if ((hash == pEntry->m_hash) && (m_equals(pEntry->m_pValue->first, k)))
 702                     return index_current;
 703             }
 704
 705             return size;
 706         }
 707
 708         inline const_iterator find(const Key &k) const
 709         {
 710             return const_iterator(*this, find_index(k));
 711         }
 712
 713         inline iterator find(const Key &k)
 714         {
 715             return iterator(*this, find_index(k));
 716         }
 717
 718         inline Value *find_value(const Key &key)
 719         {
 720             uint index = find_index(key);
 721             if (index == m_values.size())
 722                 return NULL;
 723             return &(m_values[index].m_pEntry->second);
 724         }
 725
 726         inline const Value *find_value(const Key &key) const
 727         {
 728             uint index = find_index(key);
 729             if (index == m_values.size())
 730                 return NULL;
 731             return &(m_values[index].m_pEntry->second);
 732         }
 733
 734         inline bool contains(const Key &key) const
 735         {
 736             return find_index(key) != m_values.size();
 737         }
 738
 739         // All active iterators become invalid after erase().
 740         inline bool erase(const Key &k)
 741         {
 742             if (!m_num_valid)
 743                 return false;
 744
 745             uint hash = hash_key(k);
 746             uint index_init = hash >> m_hash_shift;
 747
 748             uint index_current = 0;
 749
 750             const uint size = m_values.size();
 751
 752             for (uint i = 0; i < size; ++i)
 753             {
 754                 index_current = (index_init + i) & (size - 1);
 755                 hash_entry *pEntry = &m_values[index_current];
 756
 757                 if (!pEntry->m_pValue)
 758                     return false;
 759
 760                 uint probe_distance = calc_distance(index_current);
 761                 if (i > probe_distance)
 762                     return false;
 763
 764                 if ((hash == pEntry->m_hash) && (m_equals(pEntry->m_pValue->first, k)))
 765                 {
 766                     delete_value_type(pEntry->m_pValue);
 767                     --m_num_valid;
 768
 769                     break;
 770                 }
 771             }
 772
 773             for (uint i = 1; i < size; ++i)
 774             {
 775                 uint prev = (index_current + i - 1) & (size - 1);
 776                 uint idx = (index_current + i) & (size - 1);
 777
 778                 if (!m_values[idx].m_pValue)
 779                 {
 780                     m_values[prev].m_pValue = NULL;
 781                     break;
 782                 }
 783
 784                 uint dist = calc_distance(idx);
 785                 if (!dist)
 786                 {
 787                     m_values[prev].m_pValue = NULL;
 788                     break;
 789                 }
 790
 791                 m_values[prev].m_pValue = m_values[idx].m_pValue;
 792                 m_values[prev].m_hash = m_values[idx].m_hash;
 793             }
 794
 795             return true;
 796         }
 797
 798         inline bool erase(const iterator &it)
 799         {
 800             uint index_current = it.m_index;
 801             if ((index_current >= m_values.size()) || (!m_values[index_current].m_pValue))
 802             {
 803                 VOGL_ASSERT_ALWAYS;
 804                 return false;
 805             }
 806
 807             const uint size = m_values.size();
 808
 809             delete_value_type(m_values[index_current].m_pValue);
 810             --m_num_valid;
 811
 812             for (uint i = 1; i < size; ++i)
 813             {
 814                 uint prev = (index_current + i - 1) & (size - 1);
 815                 uint idx = (index_current + i) & (size - 1);
 816
 817                 if (!m_values[idx].m_pValue)
 818                 {
 819                     m_values[prev].m_pValue = NULL;
 820                     break;
 821                 }
 822
 823                 uint dist = calc_distance(idx);
 824                 if (!dist)
 825                 {
 826                     m_values[prev].m_pValue = NULL;
 827                     break;
 828                 }
 829
 830                 m_values[prev].m_pValue = m_values[idx].m_pValue;
 831                 m_values[prev].m_hash = m_values[idx].m_hash;
 832             }
 833
 834             return true;
 835         }
 836
 837         inline void swap(rh_hash_map_type &other)
 838         {
 839             m_values.swap(other.m_values);
 840             utils::swap(m_hash_shift, other.m_hash_shift);
 841             utils::swap(m_num_valid, other.m_num_valid);
 842             utils::swap(m_grow_threshold, other.m_grow_threshold);
 843             utils::swap(m_hasher, other.m_hasher);
 844             utils::swap(m_equals, other.m_equals);
 845             m_allocator.swap(other.m_allocator);
 846         }
 847
 848         // Obviously, this method is very slow! It scans the entire hash table.
 849         inline const_iterator search_table_for_value(const Value &val) const
 850         {
 851             for (const_iterator it = begin(); it != end(); ++it)
 852                 if (it->second == val)
 853                     return it;
 854             return end();
 855         }
 856
 857         // Obviously, this method is very slow! It scans the entire hash table.
 858         inline iterator search_table_for_value(const Value &val)
 859         {
 860             for (iterator it = begin(); it != end(); ++it)
 861                 if (it->second == val)
 862                     return it;
 863             return end();
 864         }
 865
 866         // Obviously, this method is very slow! It scans the entire hash table.
 867         inline uint search_table_for_value_get_count(const Value &val) const
 868         {
 869             uint count = 0;
 870             for (const_iterator it = begin(); it != end(); ++it)
 871                 if (it->second == val)
 872                     ++count;
 873             return count;
 874         }
 875
 876         bool operator==(const rh_hash_map &other) const
 877         {
 878             if (this == &other)
 879                 return true;
 880
 881             if (size() != other.size())
 882                 return false;
 883
 884             for (const_iterator it = begin(); it != end(); ++it)
 885             {
 886                 const_iterator other_it(other.find(it->first));
 887                 if (other_it == other.end())
 888                     return false;
 889
 890                 if (!(it->second == other_it->second))
 891                     return false;
 892             }
 893
 894             return true;
 895         }
 896
 897         bool operator!=(const rh_hash_map &other) const
 898         {
 899             return !(*this == other);
 900         }
 901
 902         bool check_failure() const
 903         {
 904             return false;
 905         }
 906
 907         bool check() const
 908         {
 909             if (!m_values.size())
 910             {
 911                 if (m_hash_shift != 32)
 912                     return check_failure();
 913                 if (m_num_valid)
 914                     return check_failure();
 915                 if (m_grow_threshold)
 916                     return check_failure();
 917                 return true;
 918             }
 919
 920             if (m_hash_shift != (32U - math::floor_log2i(m_values.size())))
 921                 return check_failure();
 922
 923             uint total_found = 0;
 924             uint max_dist = 0;
 925             for (uint i = 0; i < m_values.size(); i++)
 926             {
 927                 if (m_values[i].m_pValue)
 928                 {
 929                     if (!m_allocator.is_valid_ptr(m_values[i].m_pValue))
 930                         return check_failure();
 931
 932                     uint actual_hash = hash_key(m_values[i].m_pValue->first);
 933                     if (m_values[i].m_hash != actual_hash)
 934                         return check_failure();
 935
 936                     uint dist = calc_distance(i);
 937                     max_dist = math::maximum<uint>(max_dist, dist);
 938
 939                     uint k = find_index(m_values[i].m_pValue->first);
 940                     if (k != i)
 941                         return check_failure();
 942
 943                     ++total_found;
 944                 }
 945             }
 946
 947             if (total_found != m_num_valid)
 948                 return check_failure();
 949
 950             return true;
 951         }
 952
 953         // Direct hash table low-level manipulation
 954
 955         // index can be retrieved from a iterator by calling get_index()
 956         inline bool is_valid_index(uint index) const
 957         {
 958             return (index < m_values.size()) && (m_values[index].m_pValue != NULL);
 959         }
 960
 961         inline const value_type &value_type_at_index(uint index) const
 962         {
 963             return *m_values[index].m_pValue;
 964         }
 965
 966         inline const Key &key_at_index(uint index) const
 967         {
 968             return m_values[index].m_pValue->first;
 969         }
 970
 971         inline const Value &value_at_index(uint index) const
 972         {
 973             return m_values[index].m_pValue->second;
 974         }
 975
 976         inline Value &value_at_index(uint index)
 977         {
 978             return m_values[index].m_pValue->second;
 979         }
 980
 981     private:
 982         struct hash_entry
 983         {
 984             value_type *m_pValue;
 985             uint32 m_hash;
 986         };
 987
 988         typedef vogl::vector<hash_entry> hash_entry_vec;
 989
 990         hash_entry_vec m_values;
 991
 992         uint m_hash_shift;
 993
 994         uint m_num_valid;
 995
 996         uint m_grow_threshold;
 997
 998         Hasher m_hasher;
 999         Equals m_equals;
1000
1001         allocator_type m_allocator;
1002
1003         value_type *construct_value_type(const Key &k, const Value &v)
1004         {
1005             //value_type *p = static_cast<value_type *>(vogl_malloc(sizeof(value_type)));
1006             value_type *p = m_allocator.alloc_no_construction();
1007
1008             if (VOGL_IS_BITWISE_COPYABLE(Key))
1009                 memcpy(&p->first, &k, sizeof(Key));
1010             else
1011                 scalar_type<Key>::construct(&p->first, k);
1012
1013             if (VOGL_IS_BITWISE_COPYABLE(Value))
1014                 memcpy(&p->second, &v, sizeof(Value));
1015             else
1016                 scalar_type<Value>::construct(&p->second, v);
1017
1018             return p;
1019         }
1020
1021         void delete_value_type(value_type *p)
1022         {
1023             scalar_type<Key>::destruct(&p->first);
1024             scalar_type<Value>::destruct(&p->second);
1025
1026             //vogl_free(p);
1027             m_allocator.destroy_no_destruction(p);
1028         }
1029
1030         inline uint32 calc_distance(uint32 index_stored) const
1031         {
1032             VOGL_ASSERT(m_values[index_stored].m_pValue);
1033
1034             uint32 initial_index = m_values[index_stored].m_hash >> m_hash_shift;
1035             VOGL_ASSERT((index_stored < m_values.size()) && (initial_index < m_values.size()));
1036
1037             uint32 distance = index_stored - initial_index;
1038             if (initial_index > index_stored)
1039                 distance += m_values.size();
1040
1041             return distance;
1042         }
1043
1044         inline uint hash_key(const Key &k) const
1045         {
1046             VOGL_ASSERT((1U << (32U - m_hash_shift)) == m_values.size());
1047
1048             uint hash = static_cast<uint>(m_hasher(k));
1049
1050             // Fibonacci hashing
1051             return 2654435769U * hash;
1052         }
1053
1054         inline void grow()
1055         {
1056             if (m_values.size() >= 0x80000000UL)
1057             {
1058                 // FIXME: This case (ginormous arrays on x64) will die.
1059                 VOGL_ASSERT_ALWAYS;
1060                 return;
1061             }
1062
1063             rehash(math::maximum<uint>(cMinHashSize, m_values.size() * 2U));
1064         }
1065
1066         inline void move_into_container(hash_entry *pEntry_to_move)
1067         {
1068             ++m_num_valid;
1069             VOGL_ASSERT(m_num_valid <= m_values.size());
1070
1071             value_type *pValue = pEntry_to_move->m_pValue;
1072             uint hash = pEntry_to_move->m_hash;
1073
1074             uint index_init = hash >> m_hash_shift;
1075             uint probe_current = 0;
1076
1077             const uint size = m_values.size();
1078
1079             uint i;
1080             for (i = 0; i < size; ++i, ++probe_current)
1081             {
1082                 uint index_current = (index_init + i) & (m_values.size() - 1);
1083                 hash_entry *pEntry = &m_values[index_current];
1084
1085                 if (!pEntry->m_pValue)
1086                 {
1087                     pEntry->m_pValue = pValue;
1088                     pEntry->m_hash = hash;
1089                     break;
1090                 }
1091
1092                 uint probe_distance = calc_distance(index_current);
1093                 if (probe_current > probe_distance)
1094                 {
1095                     value_type *pTemp_value = pEntry->m_pValue;
1096                     uint temp_hash = pEntry->m_hash;
1097
1098                     pEntry->m_pValue = pValue;
1099                     pEntry->m_hash = hash;
1100
1101                     pValue = pTemp_value;
1102                     hash = temp_hash;
1103
1104                     probe_current = probe_distance;
1105                 }
1106             }
1107
1108             VOGL_ASSERT(i != size);
1109         }
1110
1111         inline void rehash(uint new_hash_size)
1112         {
1113             VOGL_ASSERT(new_hash_size >= m_num_valid);
1114             VOGL_ASSERT(math::is_power_of_2(new_hash_size));
1115
1116             if ((new_hash_size < m_num_valid) || (new_hash_size == m_values.size()))
1117                 return;
1118
1119             rh_hash_map new_map;
1120
1121             new_map.m_values.resize(new_hash_size);
1122             memset(new_map.m_values.get_ptr(), 0, new_map.m_values.size_in_bytes());
1123
1124             new_map.m_hash_shift = 32U - math::floor_log2i(new_hash_size);
1125             VOGL_ASSERT(new_hash_size == (1U << (32U - new_map.m_hash_shift)));
1126             new_map.m_grow_threshold = UINT_MAX;
1127
1128             // Move items from old array into new array
1129             hash_entry *pNode = reinterpret_cast<hash_entry *>(m_values.begin());
1130             hash_entry *pNode_end = pNode + m_values.size();
1131
1132             while (pNode != pNode_end)
1133             {
1134                 if (pNode->m_pValue)
1135                 {
1136                     new_map.move_into_container(pNode);
1137
1138                     if (new_map.m_num_valid == m_num_valid)
1139                         break;
1140                 }
1141
1142                 pNode++;
1143             }
1144
1145             // 80% load factor.
1146             new_map.m_grow_threshold = (new_hash_size * 4) / 5;
1147
1148             // Clear old array
1149             m_values.clear_no_destruction();
1150             m_hash_shift = 32;
1151
1152             swap(new_map);
1153         }
1154
1155         inline uint find_next(uint index) const
1156         {
1157             if (++index >= m_values.size())
1158                 return index;
1159
1160             const hash_entry *pEntry = &m_values[index];
1161             const hash_entry *pLast_entry = m_values.end();
1162
1163             for (;;)
1164             {
1165                 if ((pEntry->m_pValue) || (++pEntry == pLast_entry))
1166                     break;
1167             }
1168
1169             return static_cast<uint>(pEntry - m_values.begin());
1170         }
1171     };
1172
1173     bool rh_hash_map_test();
1174
1175 } // namespace vogl
1176
1177 namespace std
1178 {
1179     template <typename Key, typename Value, typename Hasher, typename Equals, typename Allocator>
1180     inline void swap(vogl::rh_hash_map<Key, Value, Hasher, Equals, Allocator> &a, vogl::rh_hash_map<Key, Value, Hasher, Equals, Allocator> &b)
1181     {
1182         a.swap(b);
1183     }
1184 }