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