| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights |
| 3 * reserved. | 3 * reserved. |
| 4 * Copyright (C) 2008 David Levin <levin@chromium.org> | 4 * Copyright (C) 2008 David Levin <levin@chromium.org> |
| 5 * | 5 * |
| 6 * This library is free software; you can redistribute it and/or | 6 * This library is free software; you can redistribute it and/or |
| 7 * modify it under the terms of the GNU Library General Public | 7 * modify it under the terms of the GNU Library General Public |
| 8 * License as published by the Free Software Foundation; either | 8 * License as published by the Free Software Foundation; either |
| 9 * version 2 of the License, or (at your option) any later version. | 9 * version 2 of the License, or (at your option) any later version. |
| 10 * | 10 * |
| (...skipping 276 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 287 while (m_position != m_endPosition && | 287 while (m_position != m_endPosition && |
| 288 HashTableType::isEmptyOrDeletedBucket(*m_position)) | 288 HashTableType::isEmptyOrDeletedBucket(*m_position)) |
| 289 ++m_position; | 289 ++m_position; |
| 290 } | 290 } |
| 291 | 291 |
| 292 HashTableConstIterator(PointerType position, | 292 HashTableConstIterator(PointerType position, |
| 293 PointerType endPosition, | 293 PointerType endPosition, |
| 294 const HashTableType* container) | 294 const HashTableType* container) |
| 295 : m_position(position), | 295 : m_position(position), |
| 296 m_endPosition(endPosition) | 296 m_endPosition(endPosition) |
| 297 #if ENABLE(ASSERT) | 297 #if DCHECK_IS_ON() |
| 298 , | 298 , |
| 299 m_container(container), | 299 m_container(container), |
| 300 m_containerModifications(container->modifications()) | 300 m_containerModifications(container->modifications()) |
| 301 #endif | 301 #endif |
| 302 { | 302 { |
| 303 skipEmptyBuckets(); | 303 skipEmptyBuckets(); |
| 304 } | 304 } |
| 305 | 305 |
| 306 HashTableConstIterator(PointerType position, | 306 HashTableConstIterator(PointerType position, |
| 307 PointerType endPosition, | 307 PointerType endPosition, |
| 308 const HashTableType* container, | 308 const HashTableType* container, |
| 309 HashItemKnownGoodTag) | 309 HashItemKnownGoodTag) |
| 310 : m_position(position), | 310 : m_position(position), |
| 311 m_endPosition(endPosition) | 311 m_endPosition(endPosition) |
| 312 #if ENABLE(ASSERT) | 312 #if DCHECK_IS_ON() |
| 313 , | 313 , |
| 314 m_container(container), | 314 m_container(container), |
| 315 m_containerModifications(container->modifications()) | 315 m_containerModifications(container->modifications()) |
| 316 #endif | 316 #endif |
| 317 { | 317 { |
| 318 ASSERT(m_containerModifications == m_container->modifications()); | 318 #if DCHECK_IS_ON() |
| 319 DCHECK_EQ(m_containerModifications, m_container->modifications()); |
| 320 #endif |
| 319 } | 321 } |
| 320 | 322 |
| 321 void checkModifications() const { | 323 void checkModifications() const { |
| 324 #if DCHECK_IS_ON() |
| 322 // HashTable and collections that build on it do not support | 325 // HashTable and collections that build on it do not support |
| 323 // modifications while there is an iterator in use. The exception is | 326 // modifications while there is an iterator in use. The exception is |
| 324 // ListHashSet, which has its own iterators that tolerate modification | 327 // ListHashSet, which has its own iterators that tolerate modification |
| 325 // of the underlying set. | 328 // of the underlying set. |
| 326 ASSERT(m_containerModifications == m_container->modifications()); | 329 DCHECK_EQ(m_containerModifications, m_container->modifications()); |
| 327 ASSERT(!m_container->accessForbidden()); | 330 DCHECK(!m_container->accessForbidden()); |
| 331 #endif |
| 328 } | 332 } |
| 329 | 333 |
| 330 public: | 334 public: |
| 331 HashTableConstIterator() {} | 335 HashTableConstIterator() {} |
| 332 | 336 |
| 333 GetType get() const { | 337 GetType get() const { |
| 334 checkModifications(); | 338 checkModifications(); |
| 335 return m_position; | 339 return m_position; |
| 336 } | 340 } |
| 337 typename Traits::IteratorConstReferenceType operator*() const { | 341 typename Traits::IteratorConstReferenceType operator*() const { |
| 338 return Traits::getToReferenceConstConversion(get()); | 342 return Traits::getToReferenceConstConversion(get()); |
| 339 } | 343 } |
| 340 GetType operator->() const { return get(); } | 344 GetType operator->() const { return get(); } |
| 341 | 345 |
| 342 const_iterator& operator++() { | 346 const_iterator& operator++() { |
| 343 ASSERT(m_position != m_endPosition); | 347 DCHECK_NE(m_position, m_endPosition); |
| 344 checkModifications(); | 348 checkModifications(); |
| 345 ++m_position; | 349 ++m_position; |
| 346 skipEmptyBuckets(); | 350 skipEmptyBuckets(); |
| 347 return *this; | 351 return *this; |
| 348 } | 352 } |
| 349 | 353 |
| 350 // postfix ++ intentionally omitted | 354 // postfix ++ intentionally omitted |
| 351 | 355 |
| 352 // Comparison. | 356 // Comparison. |
| 353 bool operator==(const const_iterator& other) const { | 357 bool operator==(const const_iterator& other) const { |
| (...skipping 13 matching lines...) Expand all Loading... |
| 367 if (m_position == m_endPosition) | 371 if (m_position == m_endPosition) |
| 368 return stream << "iterator representing <end>"; | 372 return stream << "iterator representing <end>"; |
| 369 // TODO(tkent): Change |m_position| to |*m_position| to show the | 373 // TODO(tkent): Change |m_position| to |*m_position| to show the |
| 370 // pointed object. It requires a lot of new stream printer functions. | 374 // pointed object. It requires a lot of new stream printer functions. |
| 371 return stream << "iterator pointing to " << m_position; | 375 return stream << "iterator pointing to " << m_position; |
| 372 } | 376 } |
| 373 | 377 |
| 374 private: | 378 private: |
| 375 PointerType m_position; | 379 PointerType m_position; |
| 376 PointerType m_endPosition; | 380 PointerType m_endPosition; |
| 377 #if ENABLE(ASSERT) | 381 #if DCHECK_IS_ON() |
| 378 const HashTableType* m_container; | 382 const HashTableType* m_container; |
| 379 int64_t m_containerModifications; | 383 int64_t m_containerModifications; |
| 380 #endif | 384 #endif |
| 381 }; | 385 }; |
| 382 | 386 |
| 383 template <typename Key, | 387 template <typename Key, |
| 384 typename Value, | 388 typename Value, |
| 385 typename Extractor, | 389 typename Extractor, |
| 386 typename Hash, | 390 typename Hash, |
| 387 typename Traits, | 391 typename Traits, |
| (...skipping 285 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 673 typedef Key KeyType; | 677 typedef Key KeyType; |
| 674 typedef typename KeyTraits::PeekInType KeyPeekInType; | 678 typedef typename KeyTraits::PeekInType KeyPeekInType; |
| 675 typedef Value ValueType; | 679 typedef Value ValueType; |
| 676 typedef Extractor ExtractorType; | 680 typedef Extractor ExtractorType; |
| 677 typedef KeyTraits KeyTraitsType; | 681 typedef KeyTraits KeyTraitsType; |
| 678 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; | 682 typedef IdentityHashTranslator<HashFunctions> IdentityTranslatorType; |
| 679 typedef HashTableAddResult<HashTable, ValueType> AddResult; | 683 typedef HashTableAddResult<HashTable, ValueType> AddResult; |
| 680 | 684 |
| 681 HashTable(); | 685 HashTable(); |
| 682 void finalize() { | 686 void finalize() { |
| 683 ASSERT(!Allocator::isGarbageCollected); | 687 DCHECK(!Allocator::isGarbageCollected); |
| 684 if (LIKELY(!m_table)) | 688 if (LIKELY(!m_table)) |
| 685 return; | 689 return; |
| 686 ASSERT(!m_accessForbidden); | 690 enterAccessForbiddenScope(); |
| 687 #if ENABLE(ASSERT) | |
| 688 m_accessForbidden = true; | |
| 689 #endif | |
| 690 deleteAllBucketsAndDeallocate(m_table, m_tableSize); | 691 deleteAllBucketsAndDeallocate(m_table, m_tableSize); |
| 691 #if ENABLE(ASSERT) | 692 leaveAccessForbiddenScope(); |
| 692 m_accessForbidden = false; | |
| 693 #endif | |
| 694 m_table = nullptr; | 693 m_table = nullptr; |
| 695 } | 694 } |
| 696 | 695 |
| 697 HashTable(const HashTable&); | 696 HashTable(const HashTable&); |
| 698 HashTable(HashTable&&); | 697 HashTable(HashTable&&); |
| 699 void swap(HashTable&); | 698 void swap(HashTable&); |
| 700 HashTable& operator=(const HashTable&); | 699 HashTable& operator=(const HashTable&); |
| 701 HashTable& operator=(HashTable&&); | 700 HashTable& operator=(HashTable&&); |
| 702 | 701 |
| 703 // When the hash table is empty, just return the same iterator for end as | 702 // When the hash table is empty, just return the same iterator for end as |
| 704 // for begin. This is more efficient because we don't have to skip all the | 703 // for begin. This is more efficient because we don't have to skip all the |
| 705 // empty and deleted buckets, and iterating an empty table is a common case | 704 // empty and deleted buckets, and iterating an empty table is a common case |
| 706 // that's worth optimizing. | 705 // that's worth optimizing. |
| 707 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); } | 706 iterator begin() { return isEmpty() ? end() : makeIterator(m_table); } |
| 708 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } | 707 iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); } |
| 709 const_iterator begin() const { | 708 const_iterator begin() const { |
| 710 return isEmpty() ? end() : makeConstIterator(m_table); | 709 return isEmpty() ? end() : makeConstIterator(m_table); |
| 711 } | 710 } |
| 712 const_iterator end() const { | 711 const_iterator end() const { |
| 713 return makeKnownGoodConstIterator(m_table + m_tableSize); | 712 return makeKnownGoodConstIterator(m_table + m_tableSize); |
| 714 } | 713 } |
| 715 | 714 |
| 716 unsigned size() const { | 715 unsigned size() const { |
| 717 ASSERT(!m_accessForbidden); | 716 DCHECK(!accessForbidden()); |
| 718 return m_keyCount; | 717 return m_keyCount; |
| 719 } | 718 } |
| 720 unsigned capacity() const { | 719 unsigned capacity() const { |
| 721 ASSERT(!m_accessForbidden); | 720 DCHECK(!accessForbidden()); |
| 722 return m_tableSize; | 721 return m_tableSize; |
| 723 } | 722 } |
| 724 bool isEmpty() const { | 723 bool isEmpty() const { |
| 725 ASSERT(!m_accessForbidden); | 724 DCHECK(!accessForbidden()); |
| 726 return !m_keyCount; | 725 return !m_keyCount; |
| 727 } | 726 } |
| 728 | 727 |
| 729 void reserveCapacityForSize(unsigned size); | 728 void reserveCapacityForSize(unsigned size); |
| 730 | 729 |
| 731 template <typename IncomingValueType> | 730 template <typename IncomingValueType> |
| 732 AddResult add(IncomingValueType&& value) { | 731 AddResult add(IncomingValueType&& value) { |
| 733 return add<IdentityTranslatorType>(Extractor::extract(value), | 732 return add<IdentityTranslatorType>(Extractor::extract(value), |
| 734 std::forward<IncomingValueType>(value)); | 733 std::forward<IncomingValueType>(value)); |
| 735 } | 734 } |
| (...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 777 return lookup<IdentityTranslatorType, KeyPeekInType>(key); | 776 return lookup<IdentityTranslatorType, KeyPeekInType>(key); |
| 778 } | 777 } |
| 779 template <typename HashTranslator, typename T> | 778 template <typename HashTranslator, typename T> |
| 780 ValueType* lookup(const T&); | 779 ValueType* lookup(const T&); |
| 781 template <typename HashTranslator, typename T> | 780 template <typename HashTranslator, typename T> |
| 782 const ValueType* lookup(const T&) const; | 781 const ValueType* lookup(const T&) const; |
| 783 | 782 |
| 784 template <typename VisitorDispatcher> | 783 template <typename VisitorDispatcher> |
| 785 void trace(VisitorDispatcher); | 784 void trace(VisitorDispatcher); |
| 786 | 785 |
| 787 #if ENABLE(ASSERT) | 786 #if DCHECK_IS_ON() |
| 787 void enterAccessForbiddenScope() { |
| 788 DCHECK(!m_accessForbidden); |
| 789 m_accessForbidden = true; |
| 790 } |
| 791 void leaveAccessForbiddenScope() { m_accessForbidden = false; } |
| 788 bool accessForbidden() const { return m_accessForbidden; } | 792 bool accessForbidden() const { return m_accessForbidden; } |
| 789 int64_t modifications() const { return m_modifications; } | 793 int64_t modifications() const { return m_modifications; } |
| 790 void registerModification() { m_modifications++; } | 794 void registerModification() { m_modifications++; } |
| 791 // HashTable and collections that build on it do not support modifications | 795 // HashTable and collections that build on it do not support modifications |
| 792 // while there is an iterator in use. The exception is ListHashSet, which | 796 // while there is an iterator in use. The exception is ListHashSet, which |
| 793 // has its own iterators that tolerate modification of the underlying set. | 797 // has its own iterators that tolerate modification of the underlying set. |
| 794 void checkModifications(int64_t mods) const { | 798 void checkModifications(int64_t mods) const { |
| 795 ASSERT(mods == m_modifications); | 799 DCHECK_EQ(mods, m_modifications); |
| 796 } | 800 } |
| 797 #else | 801 #else |
| 802 void enterAccessForbiddenScope() {} |
| 803 void leaveAccessForbiddenScope() {} |
| 804 bool accessForbidden() const { return false; } |
| 798 int64_t modifications() const { return 0; } | 805 int64_t modifications() const { return 0; } |
| 799 void registerModification() {} | 806 void registerModification() {} |
| 800 void checkModifications(int64_t mods) const {} | 807 void checkModifications(int64_t mods) const {} |
| 801 #endif | 808 #endif |
| 802 | 809 |
| 803 private: | 810 private: |
| 804 static ValueType* allocateTable(unsigned size); | 811 static ValueType* allocateTable(unsigned size); |
| 805 static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size); | 812 static void deleteAllBucketsAndDeallocate(ValueType* table, unsigned size); |
| 806 | 813 |
| 807 typedef std::pair<ValueType*, bool> LookupType; | 814 typedef std::pair<ValueType*, bool> LookupType; |
| (...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 863 } | 870 } |
| 864 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { | 871 const_iterator makeKnownGoodConstIterator(ValueType* pos) const { |
| 865 return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); | 872 return const_iterator(pos, m_table + m_tableSize, this, HashItemKnownGood); |
| 866 } | 873 } |
| 867 | 874 |
| 868 static const unsigned m_maxLoad = 2; | 875 static const unsigned m_maxLoad = 2; |
| 869 static const unsigned m_minLoad = 6; | 876 static const unsigned m_minLoad = 6; |
| 870 | 877 |
| 871 unsigned tableSizeMask() const { | 878 unsigned tableSizeMask() const { |
| 872 size_t mask = m_tableSize - 1; | 879 size_t mask = m_tableSize - 1; |
| 873 ASSERT((mask & m_tableSize) == 0); | 880 DCHECK_EQ((mask & m_tableSize), 0u); |
| 874 return mask; | 881 return mask; |
| 875 } | 882 } |
| 876 | 883 |
| 877 void setEnqueued() { m_queueFlag = true; } | 884 void setEnqueued() { m_queueFlag = true; } |
| 878 void clearEnqueued() { m_queueFlag = false; } | 885 void clearEnqueued() { m_queueFlag = false; } |
| 879 bool enqueued() { return m_queueFlag; } | 886 bool enqueued() { return m_queueFlag; } |
| 880 | 887 |
| 881 ValueType* m_table; | 888 ValueType* m_table; |
| 882 unsigned m_tableSize; | 889 unsigned m_tableSize; |
| 883 unsigned m_keyCount; | 890 unsigned m_keyCount; |
| 884 #if ENABLE(ASSERT) | 891 #if DCHECK_IS_ON() |
| 885 unsigned m_deletedCount : 30; | 892 unsigned m_deletedCount : 30; |
| 886 unsigned m_queueFlag : 1; | 893 unsigned m_queueFlag : 1; |
| 887 unsigned m_accessForbidden : 1; | 894 unsigned m_accessForbidden : 1; |
| 888 unsigned m_modifications; | 895 unsigned m_modifications; |
| 889 #else | 896 #else |
| 890 unsigned m_deletedCount : 31; | 897 unsigned m_deletedCount : 31; |
| 891 unsigned m_queueFlag : 1; | 898 unsigned m_queueFlag : 1; |
| 892 #endif | 899 #endif |
| 893 | 900 |
| 894 #if DUMP_HASHTABLE_STATS_PER_TABLE | 901 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| (...skipping 29 matching lines...) Expand all Loading... |
| 924 Extractor, | 931 Extractor, |
| 925 HashFunctions, | 932 HashFunctions, |
| 926 Traits, | 933 Traits, |
| 927 KeyTraits, | 934 KeyTraits, |
| 928 Allocator>::HashTable() | 935 Allocator>::HashTable() |
| 929 : m_table(nullptr), | 936 : m_table(nullptr), |
| 930 m_tableSize(0), | 937 m_tableSize(0), |
| 931 m_keyCount(0), | 938 m_keyCount(0), |
| 932 m_deletedCount(0), | 939 m_deletedCount(0), |
| 933 m_queueFlag(false) | 940 m_queueFlag(false) |
| 934 #if ENABLE(ASSERT) | 941 #if DCHECK_IS_ON() |
| 935 , | 942 , |
| 936 m_accessForbidden(false), | 943 m_accessForbidden(false), |
| 937 m_modifications(0) | 944 m_modifications(0) |
| 938 #endif | 945 #endif |
| 939 #if DUMP_HASHTABLE_STATS_PER_TABLE | 946 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 940 , | 947 , |
| 941 m_stats(nullptr) | 948 m_stats(nullptr) |
| 942 #endif | 949 #endif |
| 943 { | 950 { |
| 944 static_assert(Allocator::isGarbageCollected || | 951 static_assert(Allocator::isGarbageCollected || |
| (...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1008 typename Value, | 1015 typename Value, |
| 1009 typename Extractor, | 1016 typename Extractor, |
| 1010 typename HashFunctions, | 1017 typename HashFunctions, |
| 1011 typename Traits, | 1018 typename Traits, |
| 1012 typename KeyTraits, | 1019 typename KeyTraits, |
| 1013 typename Allocator> | 1020 typename Allocator> |
| 1014 template <typename HashTranslator, typename T> | 1021 template <typename HashTranslator, typename T> |
| 1015 inline const Value* | 1022 inline const Value* |
| 1016 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1023 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1017 lookup(const T& key) const { | 1024 lookup(const T& key) const { |
| 1018 ASSERT(!m_accessForbidden); | 1025 DCHECK(!accessForbidden()); |
| 1019 ASSERT((HashTableKeyChecker< | 1026 DCHECK((HashTableKeyChecker< |
| 1020 HashTranslator, KeyTraits, | 1027 HashTranslator, KeyTraits, |
| 1021 HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key))); | 1028 HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key))); |
| 1022 const ValueType* table = m_table; | 1029 const ValueType* table = m_table; |
| 1023 if (!table) | 1030 if (!table) |
| 1024 return nullptr; | 1031 return nullptr; |
| 1025 | 1032 |
| 1026 size_t k = 0; | 1033 size_t k = 0; |
| 1027 size_t sizeMask = tableSizeMask(); | 1034 size_t sizeMask = tableSizeMask(); |
| 1028 unsigned h = HashTranslator::hash(key); | 1035 unsigned h = HashTranslator::hash(key); |
| 1029 size_t i = h & sizeMask; | 1036 size_t i = h & sizeMask; |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1064 template <typename HashTranslator, typename T> | 1071 template <typename HashTranslator, typename T> |
| 1065 inline typename HashTable<Key, | 1072 inline typename HashTable<Key, |
| 1066 Value, | 1073 Value, |
| 1067 Extractor, | 1074 Extractor, |
| 1068 HashFunctions, | 1075 HashFunctions, |
| 1069 Traits, | 1076 Traits, |
| 1070 KeyTraits, | 1077 KeyTraits, |
| 1071 Allocator>::LookupType | 1078 Allocator>::LookupType |
| 1072 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1079 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1073 lookupForWriting(const T& key) { | 1080 lookupForWriting(const T& key) { |
| 1074 ASSERT(!m_accessForbidden); | 1081 DCHECK(!accessForbidden()); |
| 1075 ASSERT(m_table); | 1082 DCHECK(m_table); |
| 1076 registerModification(); | 1083 registerModification(); |
| 1077 | 1084 |
| 1078 ValueType* table = m_table; | 1085 ValueType* table = m_table; |
| 1079 size_t k = 0; | 1086 size_t k = 0; |
| 1080 size_t sizeMask = tableSizeMask(); | 1087 size_t sizeMask = tableSizeMask(); |
| 1081 unsigned h = HashTranslator::hash(key); | 1088 unsigned h = HashTranslator::hash(key); |
| 1082 size_t i = h & sizeMask; | 1089 size_t i = h & sizeMask; |
| 1083 | 1090 |
| 1084 UPDATE_ACCESS_COUNTS(); | 1091 UPDATE_ACCESS_COUNTS(); |
| 1085 | 1092 |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1120 template <typename HashTranslator, typename T> | 1127 template <typename HashTranslator, typename T> |
| 1121 inline typename HashTable<Key, | 1128 inline typename HashTable<Key, |
| 1122 Value, | 1129 Value, |
| 1123 Extractor, | 1130 Extractor, |
| 1124 HashFunctions, | 1131 HashFunctions, |
| 1125 Traits, | 1132 Traits, |
| 1126 KeyTraits, | 1133 KeyTraits, |
| 1127 Allocator>::FullLookupType | 1134 Allocator>::FullLookupType |
| 1128 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1135 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1129 fullLookupForWriting(const T& key) { | 1136 fullLookupForWriting(const T& key) { |
| 1130 ASSERT(!m_accessForbidden); | 1137 DCHECK(!accessForbidden()); |
| 1131 ASSERT(m_table); | 1138 DCHECK(m_table); |
| 1132 registerModification(); | 1139 registerModification(); |
| 1133 | 1140 |
| 1134 ValueType* table = m_table; | 1141 ValueType* table = m_table; |
| 1135 size_t k = 0; | 1142 size_t k = 0; |
| 1136 size_t sizeMask = tableSizeMask(); | 1143 size_t sizeMask = tableSizeMask(); |
| 1137 unsigned h = HashTranslator::hash(key); | 1144 unsigned h = HashTranslator::hash(key); |
| 1138 size_t i = h & sizeMask; | 1145 size_t i = h & sizeMask; |
| 1139 | 1146 |
| 1140 UPDATE_ACCESS_COUNTS(); | 1147 UPDATE_ACCESS_COUNTS(); |
| 1141 | 1148 |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1215 template <typename HashTranslator, typename T, typename Extra> | 1222 template <typename HashTranslator, typename T, typename Extra> |
| 1216 typename HashTable<Key, | 1223 typename HashTable<Key, |
| 1217 Value, | 1224 Value, |
| 1218 Extractor, | 1225 Extractor, |
| 1219 HashFunctions, | 1226 HashFunctions, |
| 1220 Traits, | 1227 Traits, |
| 1221 KeyTraits, | 1228 KeyTraits, |
| 1222 Allocator>::AddResult | 1229 Allocator>::AddResult |
| 1223 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1230 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1224 add(T&& key, Extra&& extra) { | 1231 add(T&& key, Extra&& extra) { |
| 1225 ASSERT(!m_accessForbidden); | 1232 DCHECK(!accessForbidden()); |
| 1226 ASSERT(Allocator::isAllocationAllowed()); | 1233 DCHECK(Allocator::isAllocationAllowed()); |
| 1227 if (!m_table) | 1234 if (!m_table) |
| 1228 expand(); | 1235 expand(); |
| 1229 | 1236 |
| 1230 ASSERT(m_table); | 1237 DCHECK(m_table); |
| 1231 | 1238 |
| 1232 ValueType* table = m_table; | 1239 ValueType* table = m_table; |
| 1233 size_t k = 0; | 1240 size_t k = 0; |
| 1234 size_t sizeMask = tableSizeMask(); | 1241 size_t sizeMask = tableSizeMask(); |
| 1235 unsigned h = HashTranslator::hash(key); | 1242 unsigned h = HashTranslator::hash(key); |
| 1236 size_t i = h & sizeMask; | 1243 size_t i = h & sizeMask; |
| 1237 | 1244 |
| 1238 UPDATE_ACCESS_COUNTS(); | 1245 UPDATE_ACCESS_COUNTS(); |
| 1239 | 1246 |
| 1240 ValueType* deletedEntry = nullptr; | 1247 ValueType* deletedEntry = nullptr; |
| (...skipping 27 matching lines...) Expand all Loading... |
| 1268 if (deletedEntry) { | 1275 if (deletedEntry) { |
| 1269 // Overwrite any data left over from last use, using placement new or | 1276 // Overwrite any data left over from last use, using placement new or |
| 1270 // memset. | 1277 // memset. |
| 1271 initializeBucket(*deletedEntry); | 1278 initializeBucket(*deletedEntry); |
| 1272 entry = deletedEntry; | 1279 entry = deletedEntry; |
| 1273 --m_deletedCount; | 1280 --m_deletedCount; |
| 1274 } | 1281 } |
| 1275 | 1282 |
| 1276 HashTranslator::translate(*entry, std::forward<T>(key), | 1283 HashTranslator::translate(*entry, std::forward<T>(key), |
| 1277 std::forward<Extra>(extra)); | 1284 std::forward<Extra>(extra)); |
| 1278 ASSERT(!isEmptyOrDeletedBucket(*entry)); | 1285 DCHECK(!isEmptyOrDeletedBucket(*entry)); |
| 1279 | 1286 |
| 1280 ++m_keyCount; | 1287 ++m_keyCount; |
| 1281 | 1288 |
| 1282 if (shouldExpand()) { | 1289 if (shouldExpand()) { |
| 1283 entry = expand(entry); | 1290 entry = expand(entry); |
| 1284 } else if (Traits::weakHandlingFlag == WeakHandlingInCollections && | 1291 } else if (Traits::weakHandlingFlag == WeakHandlingInCollections && |
| 1285 shouldShrink()) { | 1292 shouldShrink()) { |
| 1286 // When weak hash tables are processed by the garbage collector, | 1293 // When weak hash tables are processed by the garbage collector, |
| 1287 // elements with no other strong references to them will have their | 1294 // elements with no other strong references to them will have their |
| 1288 // table entries cleared. But no shrinking of the backing store is | 1295 // table entries cleared. But no shrinking of the backing store is |
| (...skipping 22 matching lines...) Expand all Loading... |
| 1311 template <typename HashTranslator, typename T, typename Extra> | 1318 template <typename HashTranslator, typename T, typename Extra> |
| 1312 typename HashTable<Key, | 1319 typename HashTable<Key, |
| 1313 Value, | 1320 Value, |
| 1314 Extractor, | 1321 Extractor, |
| 1315 HashFunctions, | 1322 HashFunctions, |
| 1316 Traits, | 1323 Traits, |
| 1317 KeyTraits, | 1324 KeyTraits, |
| 1318 Allocator>::AddResult | 1325 Allocator>::AddResult |
| 1319 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1326 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1320 addPassingHashCode(T&& key, Extra&& extra) { | 1327 addPassingHashCode(T&& key, Extra&& extra) { |
| 1321 ASSERT(!m_accessForbidden); | 1328 DCHECK(!accessForbidden()); |
| 1322 ASSERT(Allocator::isAllocationAllowed()); | 1329 DCHECK(Allocator::isAllocationAllowed()); |
| 1323 if (!m_table) | 1330 if (!m_table) |
| 1324 expand(); | 1331 expand(); |
| 1325 | 1332 |
| 1326 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); | 1333 FullLookupType lookupResult = fullLookupForWriting<HashTranslator>(key); |
| 1327 | 1334 |
| 1328 ValueType* entry = lookupResult.first.first; | 1335 ValueType* entry = lookupResult.first.first; |
| 1329 bool found = lookupResult.first.second; | 1336 bool found = lookupResult.first.second; |
| 1330 unsigned h = lookupResult.second; | 1337 unsigned h = lookupResult.second; |
| 1331 | 1338 |
| 1332 if (found) | 1339 if (found) |
| 1333 return AddResult(this, entry, false); | 1340 return AddResult(this, entry, false); |
| 1334 | 1341 |
| 1335 registerModification(); | 1342 registerModification(); |
| 1336 | 1343 |
| 1337 if (isDeletedBucket(*entry)) { | 1344 if (isDeletedBucket(*entry)) { |
| 1338 initializeBucket(*entry); | 1345 initializeBucket(*entry); |
| 1339 --m_deletedCount; | 1346 --m_deletedCount; |
| 1340 } | 1347 } |
| 1341 | 1348 |
| 1342 HashTranslator::translate(*entry, std::forward<T>(key), | 1349 HashTranslator::translate(*entry, std::forward<T>(key), |
| 1343 std::forward<Extra>(extra), h); | 1350 std::forward<Extra>(extra), h); |
| 1344 ASSERT(!isEmptyOrDeletedBucket(*entry)); | 1351 DCHECK(!isEmptyOrDeletedBucket(*entry)); |
| 1345 | 1352 |
| 1346 ++m_keyCount; | 1353 ++m_keyCount; |
| 1347 if (shouldExpand()) | 1354 if (shouldExpand()) |
| 1348 entry = expand(entry); | 1355 entry = expand(entry); |
| 1349 | 1356 |
| 1350 return AddResult(this, entry, true); | 1357 return AddResult(this, entry, true); |
| 1351 } | 1358 } |
| 1352 | 1359 |
| 1353 template <typename Key, | 1360 template <typename Key, |
| 1354 typename Value, | 1361 typename Value, |
| 1355 typename Extractor, | 1362 typename Extractor, |
| 1356 typename HashFunctions, | 1363 typename HashFunctions, |
| 1357 typename Traits, | 1364 typename Traits, |
| 1358 typename KeyTraits, | 1365 typename KeyTraits, |
| 1359 typename Allocator> | 1366 typename Allocator> |
| 1360 Value* | 1367 Value* |
| 1361 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1368 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1362 reinsert(ValueType&& entry) { | 1369 reinsert(ValueType&& entry) { |
| 1363 ASSERT(m_table); | 1370 DCHECK(m_table); |
| 1364 registerModification(); | 1371 registerModification(); |
| 1365 ASSERT(!lookupForWriting(Extractor::extract(entry)).second); | 1372 DCHECK(!lookupForWriting(Extractor::extract(entry)).second); |
| 1366 ASSERT( | 1373 DCHECK( |
| 1367 !isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); | 1374 !isDeletedBucket(*(lookupForWriting(Extractor::extract(entry)).first))); |
| 1368 #if DUMP_HASHTABLE_STATS | 1375 #if DUMP_HASHTABLE_STATS |
| 1369 atomicIncrement(&HashTableStats::instance().numReinserts); | 1376 atomicIncrement(&HashTableStats::instance().numReinserts); |
| 1370 #endif | 1377 #endif |
| 1371 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1378 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1372 ++m_stats->numReinserts; | 1379 ++m_stats->numReinserts; |
| 1373 #endif | 1380 #endif |
| 1374 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first; | 1381 Value* newEntry = lookupForWriting(Extractor::extract(entry)).first; |
| 1375 Mover<ValueType, Allocator, | 1382 Mover<ValueType, Allocator, |
| 1376 Traits::template NeedsToForbidGCOnMove<>::value>::move(std::move(entry), | 1383 Traits::template NeedsToForbidGCOnMove<>::value>::move(std::move(entry), |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1460 KeyTraits, | 1467 KeyTraits, |
| 1461 Allocator>::remove(ValueType* pos) { | 1468 Allocator>::remove(ValueType* pos) { |
| 1462 registerModification(); | 1469 registerModification(); |
| 1463 #if DUMP_HASHTABLE_STATS | 1470 #if DUMP_HASHTABLE_STATS |
| 1464 atomicIncrement(&HashTableStats::instance().numRemoves); | 1471 atomicIncrement(&HashTableStats::instance().numRemoves); |
| 1465 #endif | 1472 #endif |
| 1466 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1473 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1467 ++m_stats->numRemoves; | 1474 ++m_stats->numRemoves; |
| 1468 #endif | 1475 #endif |
| 1469 | 1476 |
| 1470 ASSERT(!m_accessForbidden); | 1477 enterAccessForbiddenScope(); |
| 1471 #if ENABLE(ASSERT) | |
| 1472 m_accessForbidden = true; | |
| 1473 #endif | |
| 1474 deleteBucket(*pos); | 1478 deleteBucket(*pos); |
| 1475 #if ENABLE(ASSERT) | 1479 leaveAccessForbiddenScope(); |
| 1476 m_accessForbidden = false; | |
| 1477 #endif | |
| 1478 ++m_deletedCount; | 1480 ++m_deletedCount; |
| 1479 --m_keyCount; | 1481 --m_keyCount; |
| 1480 | 1482 |
| 1481 if (shouldShrink()) | 1483 if (shouldShrink()) |
| 1482 shrink(); | 1484 shrink(); |
| 1483 } | 1485 } |
| 1484 | 1486 |
| 1485 template <typename Key, | 1487 template <typename Key, |
| 1486 typename Value, | 1488 typename Value, |
| 1487 typename Extractor, | 1489 typename Extractor, |
| (...skipping 142 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1630 typename Value, | 1632 typename Value, |
| 1631 typename Extractor, | 1633 typename Extractor, |
| 1632 typename HashFunctions, | 1634 typename HashFunctions, |
| 1633 typename Traits, | 1635 typename Traits, |
| 1634 typename KeyTraits, | 1636 typename KeyTraits, |
| 1635 typename Allocator> | 1637 typename Allocator> |
| 1636 Value* | 1638 Value* |
| 1637 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1639 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1638 expandBuffer(unsigned newTableSize, Value* entry, bool& success) { | 1640 expandBuffer(unsigned newTableSize, Value* entry, bool& success) { |
| 1639 success = false; | 1641 success = false; |
| 1640 ASSERT(m_tableSize < newTableSize); | 1642 DCHECK_LT(m_tableSize, newTableSize); |
| 1641 if (!Allocator::expandHashTableBacking(m_table, | 1643 if (!Allocator::expandHashTableBacking(m_table, |
| 1642 newTableSize * sizeof(ValueType))) | 1644 newTableSize * sizeof(ValueType))) |
| 1643 return nullptr; | 1645 return nullptr; |
| 1644 | 1646 |
| 1645 success = true; | 1647 success = true; |
| 1646 | 1648 |
| 1647 Value* newEntry = nullptr; | 1649 Value* newEntry = nullptr; |
| 1648 unsigned oldTableSize = m_tableSize; | 1650 unsigned oldTableSize = m_tableSize; |
| 1649 ValueType* originalTable = m_table; | 1651 ValueType* originalTable = m_table; |
| 1650 | 1652 |
| 1651 ValueType* temporaryTable = allocateTable(oldTableSize); | 1653 ValueType* temporaryTable = allocateTable(oldTableSize); |
| 1652 for (unsigned i = 0; i < oldTableSize; i++) { | 1654 for (unsigned i = 0; i < oldTableSize; i++) { |
| 1653 if (&m_table[i] == entry) | 1655 if (&m_table[i] == entry) |
| 1654 newEntry = &temporaryTable[i]; | 1656 newEntry = &temporaryTable[i]; |
| 1655 if (isEmptyOrDeletedBucket(m_table[i])) { | 1657 if (isEmptyOrDeletedBucket(m_table[i])) { |
| 1656 ASSERT(&m_table[i] != entry); | 1658 DCHECK_NE(&m_table[i], entry); |
| 1657 if (Traits::emptyValueIsZero) { | 1659 if (Traits::emptyValueIsZero) { |
| 1658 memset(&temporaryTable[i], 0, sizeof(ValueType)); | 1660 memset(&temporaryTable[i], 0, sizeof(ValueType)); |
| 1659 } else { | 1661 } else { |
| 1660 initializeBucket(temporaryTable[i]); | 1662 initializeBucket(temporaryTable[i]); |
| 1661 } | 1663 } |
| 1662 } else { | 1664 } else { |
| 1663 Mover<ValueType, Allocator, | 1665 Mover<ValueType, Allocator, |
| 1664 Traits::template NeedsToForbidGCOnMove<>::value>:: | 1666 Traits::template NeedsToForbidGCOnMove<>::value>:: |
| 1665 move(std::move(m_table[i]), temporaryTable[i]); | 1667 move(std::move(m_table[i]), temporaryTable[i]); |
| 1666 } | 1668 } |
| 1667 } | 1669 } |
| 1668 m_table = temporaryTable; | 1670 m_table = temporaryTable; |
| 1669 | 1671 |
| 1670 if (Traits::emptyValueIsZero) { | 1672 if (Traits::emptyValueIsZero) { |
| 1671 memset(originalTable, 0, newTableSize * sizeof(ValueType)); | 1673 memset(originalTable, 0, newTableSize * sizeof(ValueType)); |
| 1672 } else { | 1674 } else { |
| 1673 for (unsigned i = 0; i < newTableSize; i++) | 1675 for (unsigned i = 0; i < newTableSize; i++) |
| 1674 initializeBucket(originalTable[i]); | 1676 initializeBucket(originalTable[i]); |
| 1675 } | 1677 } |
| 1676 newEntry = rehashTo(originalTable, newTableSize, newEntry); | 1678 newEntry = rehashTo(originalTable, newTableSize, newEntry); |
| 1677 | 1679 |
| 1678 ASSERT(!m_accessForbidden); | 1680 enterAccessForbiddenScope(); |
| 1679 #if ENABLE(ASSERT) | |
| 1680 m_accessForbidden = true; | |
| 1681 #endif | |
| 1682 deleteAllBucketsAndDeallocate(temporaryTable, oldTableSize); | 1681 deleteAllBucketsAndDeallocate(temporaryTable, oldTableSize); |
| 1683 #if ENABLE(ASSERT) | 1682 leaveAccessForbiddenScope(); |
| 1684 m_accessForbidden = false; | |
| 1685 #endif | |
| 1686 | 1683 |
| 1687 return newEntry; | 1684 return newEntry; |
| 1688 } | 1685 } |
| 1689 | 1686 |
| 1690 template <typename Key, | 1687 template <typename Key, |
| 1691 typename Value, | 1688 typename Value, |
| 1692 typename Extractor, | 1689 typename Extractor, |
| 1693 typename HashFunctions, | 1690 typename HashFunctions, |
| 1694 typename Traits, | 1691 typename Traits, |
| 1695 typename KeyTraits, | 1692 typename KeyTraits, |
| (...skipping 13 matching lines...) Expand all Loading... |
| 1709 if (oldTableSize != 0) | 1706 if (oldTableSize != 0) |
| 1710 ++m_stats->numRehashes; | 1707 ++m_stats->numRehashes; |
| 1711 #endif | 1708 #endif |
| 1712 | 1709 |
| 1713 m_table = newTable; | 1710 m_table = newTable; |
| 1714 m_tableSize = newTableSize; | 1711 m_tableSize = newTableSize; |
| 1715 | 1712 |
| 1716 Value* newEntry = nullptr; | 1713 Value* newEntry = nullptr; |
| 1717 for (unsigned i = 0; i != oldTableSize; ++i) { | 1714 for (unsigned i = 0; i != oldTableSize; ++i) { |
| 1718 if (isEmptyOrDeletedBucket(oldTable[i])) { | 1715 if (isEmptyOrDeletedBucket(oldTable[i])) { |
| 1719 ASSERT(&oldTable[i] != entry); | 1716 DCHECK_NE(&oldTable[i], entry); |
| 1720 continue; | 1717 continue; |
| 1721 } | 1718 } |
| 1722 Value* reinsertedEntry = reinsert(std::move(oldTable[i])); | 1719 Value* reinsertedEntry = reinsert(std::move(oldTable[i])); |
| 1723 if (&oldTable[i] == entry) { | 1720 if (&oldTable[i] == entry) { |
| 1724 ASSERT(!newEntry); | 1721 DCHECK(!newEntry); |
| 1725 newEntry = reinsertedEntry; | 1722 newEntry = reinsertedEntry; |
| 1726 } | 1723 } |
| 1727 } | 1724 } |
| 1728 | 1725 |
| 1729 m_deletedCount = 0; | 1726 m_deletedCount = 0; |
| 1730 | 1727 |
| 1731 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1728 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1732 if (!m_stats) | 1729 if (!m_stats) |
| 1733 m_stats = HashTableStatsPtr<Allocator>::create(); | 1730 m_stats = HashTableStatsPtr<Allocator>::create(); |
| 1734 #endif | 1731 #endif |
| (...skipping 30 matching lines...) Expand all Loading... |
| 1765 if (Allocator::isGarbageCollected && newTableSize > oldTableSize) { | 1762 if (Allocator::isGarbageCollected && newTableSize > oldTableSize) { |
| 1766 bool success; | 1763 bool success; |
| 1767 Value* newEntry = expandBuffer(newTableSize, entry, success); | 1764 Value* newEntry = expandBuffer(newTableSize, entry, success); |
| 1768 if (success) | 1765 if (success) |
| 1769 return newEntry; | 1766 return newEntry; |
| 1770 } | 1767 } |
| 1771 | 1768 |
| 1772 ValueType* newTable = allocateTable(newTableSize); | 1769 ValueType* newTable = allocateTable(newTableSize); |
| 1773 Value* newEntry = rehashTo(newTable, newTableSize, entry); | 1770 Value* newEntry = rehashTo(newTable, newTableSize, entry); |
| 1774 | 1771 |
| 1775 ASSERT(!m_accessForbidden); | 1772 enterAccessForbiddenScope(); |
| 1776 #if ENABLE(ASSERT) | |
| 1777 m_accessForbidden = true; | |
| 1778 #endif | |
| 1779 deleteAllBucketsAndDeallocate(oldTable, oldTableSize); | 1773 deleteAllBucketsAndDeallocate(oldTable, oldTableSize); |
| 1780 #if ENABLE(ASSERT) | 1774 leaveAccessForbiddenScope(); |
| 1781 m_accessForbidden = false; | |
| 1782 #endif | |
| 1783 | 1775 |
| 1784 return newEntry; | 1776 return newEntry; |
| 1785 } | 1777 } |
| 1786 | 1778 |
| 1787 template <typename Key, | 1779 template <typename Key, |
| 1788 typename Value, | 1780 typename Value, |
| 1789 typename Extractor, | 1781 typename Extractor, |
| 1790 typename HashFunctions, | 1782 typename HashFunctions, |
| 1791 typename Traits, | 1783 typename Traits, |
| 1792 typename KeyTraits, | 1784 typename KeyTraits, |
| 1793 typename Allocator> | 1785 typename Allocator> |
| 1794 void HashTable<Key, | 1786 void HashTable<Key, |
| 1795 Value, | 1787 Value, |
| 1796 Extractor, | 1788 Extractor, |
| 1797 HashFunctions, | 1789 HashFunctions, |
| 1798 Traits, | 1790 Traits, |
| 1799 KeyTraits, | 1791 KeyTraits, |
| 1800 Allocator>::clear() { | 1792 Allocator>::clear() { |
| 1801 registerModification(); | 1793 registerModification(); |
| 1802 if (!m_table) | 1794 if (!m_table) |
| 1803 return; | 1795 return; |
| 1804 | 1796 |
| 1805 ASSERT(!m_accessForbidden); | 1797 enterAccessForbiddenScope(); |
| 1806 #if ENABLE(ASSERT) | |
| 1807 m_accessForbidden = true; | |
| 1808 #endif | |
| 1809 deleteAllBucketsAndDeallocate(m_table, m_tableSize); | 1798 deleteAllBucketsAndDeallocate(m_table, m_tableSize); |
| 1810 #if ENABLE(ASSERT) | 1799 leaveAccessForbiddenScope(); |
| 1811 m_accessForbidden = false; | |
| 1812 #endif | |
| 1813 m_table = nullptr; | 1800 m_table = nullptr; |
| 1814 m_tableSize = 0; | 1801 m_tableSize = 0; |
| 1815 m_keyCount = 0; | 1802 m_keyCount = 0; |
| 1816 } | 1803 } |
| 1817 | 1804 |
| 1818 template <typename Key, | 1805 template <typename Key, |
| 1819 typename Value, | 1806 typename Value, |
| 1820 typename Extractor, | 1807 typename Extractor, |
| 1821 typename HashFunctions, | 1808 typename HashFunctions, |
| 1822 typename Traits, | 1809 typename Traits, |
| 1823 typename KeyTraits, | 1810 typename KeyTraits, |
| 1824 typename Allocator> | 1811 typename Allocator> |
| 1825 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1812 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1826 HashTable(const HashTable& other) | 1813 HashTable(const HashTable& other) |
| 1827 : m_table(nullptr), | 1814 : m_table(nullptr), |
| 1828 m_tableSize(0), | 1815 m_tableSize(0), |
| 1829 m_keyCount(0), | 1816 m_keyCount(0), |
| 1830 m_deletedCount(0), | 1817 m_deletedCount(0), |
| 1831 m_queueFlag(false) | 1818 m_queueFlag(false) |
| 1832 #if ENABLE(ASSERT) | 1819 #if DCHECK_IS_ON() |
| 1833 , | 1820 , |
| 1834 m_accessForbidden(false), | 1821 m_accessForbidden(false), |
| 1835 m_modifications(0) | 1822 m_modifications(0) |
| 1836 #endif | 1823 #endif |
| 1837 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1824 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1838 , | 1825 , |
| 1839 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats)) | 1826 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats)) |
| 1840 #endif | 1827 #endif |
| 1841 { | 1828 { |
| 1842 // Copy the hash table the dumb way, by adding each element to the new | 1829 // Copy the hash table the dumb way, by adding each element to the new |
| (...skipping 11 matching lines...) Expand all Loading... |
| 1854 typename Traits, | 1841 typename Traits, |
| 1855 typename KeyTraits, | 1842 typename KeyTraits, |
| 1856 typename Allocator> | 1843 typename Allocator> |
| 1857 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: | 1844 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>:: |
| 1858 HashTable(HashTable&& other) | 1845 HashTable(HashTable&& other) |
| 1859 : m_table(nullptr), | 1846 : m_table(nullptr), |
| 1860 m_tableSize(0), | 1847 m_tableSize(0), |
| 1861 m_keyCount(0), | 1848 m_keyCount(0), |
| 1862 m_deletedCount(0), | 1849 m_deletedCount(0), |
| 1863 m_queueFlag(false) | 1850 m_queueFlag(false) |
| 1864 #if ENABLE(ASSERT) | 1851 #if DCHECK_IS_ON() |
| 1865 , | 1852 , |
| 1866 m_accessForbidden(false), | 1853 m_accessForbidden(false), |
| 1867 m_modifications(0) | 1854 m_modifications(0) |
| 1868 #endif | 1855 #endif |
| 1869 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1856 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1870 , | 1857 , |
| 1871 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats)) | 1858 m_stats(HashTableStatsPtr<Allocator>::copy(other.m_stats)) |
| 1872 #endif | 1859 #endif |
| 1873 { | 1860 { |
| 1874 swap(other); | 1861 swap(other); |
| 1875 } | 1862 } |
| 1876 | 1863 |
| 1877 template <typename Key, | 1864 template <typename Key, |
| 1878 typename Value, | 1865 typename Value, |
| 1879 typename Extractor, | 1866 typename Extractor, |
| 1880 typename HashFunctions, | 1867 typename HashFunctions, |
| 1881 typename Traits, | 1868 typename Traits, |
| 1882 typename KeyTraits, | 1869 typename KeyTraits, |
| 1883 typename Allocator> | 1870 typename Allocator> |
| 1884 void HashTable<Key, | 1871 void HashTable<Key, |
| 1885 Value, | 1872 Value, |
| 1886 Extractor, | 1873 Extractor, |
| 1887 HashFunctions, | 1874 HashFunctions, |
| 1888 Traits, | 1875 Traits, |
| 1889 KeyTraits, | 1876 KeyTraits, |
| 1890 Allocator>::swap(HashTable& other) { | 1877 Allocator>::swap(HashTable& other) { |
| 1891 ASSERT(!m_accessForbidden); | 1878 DCHECK(!accessForbidden()); |
| 1892 std::swap(m_table, other.m_table); | 1879 std::swap(m_table, other.m_table); |
| 1893 std::swap(m_tableSize, other.m_tableSize); | 1880 std::swap(m_tableSize, other.m_tableSize); |
| 1894 std::swap(m_keyCount, other.m_keyCount); | 1881 std::swap(m_keyCount, other.m_keyCount); |
| 1895 // std::swap does not work for bit fields. | 1882 // std::swap does not work for bit fields. |
| 1896 unsigned deleted = m_deletedCount; | 1883 unsigned deleted = m_deletedCount; |
| 1897 m_deletedCount = other.m_deletedCount; | 1884 m_deletedCount = other.m_deletedCount; |
| 1898 other.m_deletedCount = deleted; | 1885 other.m_deletedCount = deleted; |
| 1899 ASSERT(!m_queueFlag); | 1886 DCHECK(!m_queueFlag); |
| 1900 ASSERT(!other.m_queueFlag); | 1887 DCHECK(!other.m_queueFlag); |
| 1901 | 1888 |
| 1902 #if ENABLE(ASSERT) | 1889 #if DCHECK_IS_ON() |
| 1903 std::swap(m_modifications, other.m_modifications); | 1890 std::swap(m_modifications, other.m_modifications); |
| 1904 #endif | 1891 #endif |
| 1905 | 1892 |
| 1906 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1893 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1907 HashTableStatsPtr<Allocator>::swap(m_stats, other.m_stats); | 1894 HashTableStatsPtr<Allocator>::swap(m_stats, other.m_stats); |
| 1908 #endif | 1895 #endif |
| 1909 } | 1896 } |
| 1910 | 1897 |
| 1911 template <typename Key, | 1898 template <typename Key, |
| 1912 typename Value, | 1899 typename Value, |
| (...skipping 111 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2024 // because that would cause allocation during GC. | 2011 // because that would cause allocation during GC. |
| 2025 } | 2012 } |
| 2026 } | 2013 } |
| 2027 } | 2014 } |
| 2028 } | 2015 } |
| 2029 | 2016 |
| 2030 // Called repeatedly for tables that have both weak and strong pointers. | 2017 // Called repeatedly for tables that have both weak and strong pointers. |
| 2031 static void ephemeronIteration(typename Allocator::Visitor* visitor, | 2018 static void ephemeronIteration(typename Allocator::Visitor* visitor, |
| 2032 void* closure) { | 2019 void* closure) { |
| 2033 HashTableType* table = reinterpret_cast<HashTableType*>(closure); | 2020 HashTableType* table = reinterpret_cast<HashTableType*>(closure); |
| 2034 ASSERT(table->m_table); | 2021 DCHECK(table->m_table); |
| 2035 // Check the hash table for elements that we now know will not be | 2022 // Check the hash table for elements that we now know will not be |
| 2036 // removed by weak processing. Those elements need to have their strong | 2023 // removed by weak processing. Those elements need to have their strong |
| 2037 // pointers traced. | 2024 // pointers traced. |
| 2038 for (ValueType* element = table->m_table + table->m_tableSize - 1; | 2025 for (ValueType* element = table->m_table + table->m_tableSize - 1; |
| 2039 element >= table->m_table; element--) { | 2026 element >= table->m_table; element--) { |
| 2040 if (!HashTableType::isEmptyOrDeletedBucket(*element)) | 2027 if (!HashTableType::isEmptyOrDeletedBucket(*element)) |
| 2041 TraceInCollectionTrait<WeakHandlingInCollections, WeakPointersActWeak, | 2028 TraceInCollectionTrait<WeakHandlingInCollections, WeakPointersActWeak, |
| 2042 ValueType, Traits>::trace(visitor, *element); | 2029 ValueType, Traits>::trace(visitor, *element); |
| 2043 } | 2030 } |
| 2044 } | 2031 } |
| 2045 | 2032 |
| 2046 // Called when the ephemeron iteration is done and before running the per | 2033 // Called when the ephemeron iteration is done and before running the per |
| 2047 // thread weak processing. It is guaranteed to be called before any thread | 2034 // thread weak processing. It is guaranteed to be called before any thread |
| 2048 // is resumed. | 2035 // is resumed. |
| 2049 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, | 2036 static void ephemeronIterationDone(typename Allocator::Visitor* visitor, |
| 2050 void* closure) { | 2037 void* closure) { |
| 2051 HashTableType* table = reinterpret_cast<HashTableType*>(closure); | 2038 HashTableType* table = reinterpret_cast<HashTableType*>(closure); |
| 2052 ASSERT(Allocator::weakTableRegistered(visitor, table)); | 2039 #if DCHECK_IS_ON() |
| 2040 DCHECK(Allocator::weakTableRegistered(visitor, table)); |
| 2041 #endif |
| 2053 table->clearEnqueued(); | 2042 table->clearEnqueued(); |
| 2054 } | 2043 } |
| 2055 }; | 2044 }; |
| 2056 | 2045 |
| 2057 template <typename Key, | 2046 template <typename Key, |
| 2058 typename Value, | 2047 typename Value, |
| 2059 typename Extractor, | 2048 typename Extractor, |
| 2060 typename HashFunctions, | 2049 typename HashFunctions, |
| 2061 typename Traits, | 2050 typename Traits, |
| 2062 typename KeyTraits, | 2051 typename KeyTraits, |
| (...skipping 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2111 // by the visitor. | 2100 // by the visitor. |
| 2112 Allocator::registerBackingStoreReference(visitor, &m_table); | 2101 Allocator::registerBackingStoreReference(visitor, &m_table); |
| 2113 if (!IsTraceableInCollectionTrait<Traits>::value) | 2102 if (!IsTraceableInCollectionTrait<Traits>::value) |
| 2114 return; | 2103 return; |
| 2115 if (Traits::weakHandlingFlag == WeakHandlingInCollections) { | 2104 if (Traits::weakHandlingFlag == WeakHandlingInCollections) { |
| 2116 // If we have both strong and weak pointers in the collection then | 2105 // If we have both strong and weak pointers in the collection then |
| 2117 // we queue up the collection for fixed point iteration a la | 2106 // we queue up the collection for fixed point iteration a la |
| 2118 // Ephemerons: | 2107 // Ephemerons: |
| 2119 // http://dl.acm.org/citation.cfm?doid=263698.263733 - see also | 2108 // http://dl.acm.org/citation.cfm?doid=263698.263733 - see also |
| 2120 // http://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak | 2109 // http://www.jucs.org/jucs_14_21/eliminating_cycles_in_weak |
| 2121 ASSERT(!enqueued() || Allocator::weakTableRegistered(visitor, this)); | 2110 #if DCHECK_IS_ON() |
| 2111 DCHECK(!enqueued() || Allocator::weakTableRegistered(visitor, this)); |
| 2112 #endif |
| 2122 if (!enqueued()) { | 2113 if (!enqueued()) { |
| 2123 Allocator::registerWeakTable( | 2114 Allocator::registerWeakTable( |
| 2124 visitor, this, | 2115 visitor, this, |
| 2125 WeakProcessingHashTableHelper< | 2116 WeakProcessingHashTableHelper< |
| 2126 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, | 2117 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, |
| 2127 Traits, KeyTraits, Allocator>::ephemeronIteration, | 2118 Traits, KeyTraits, Allocator>::ephemeronIteration, |
| 2128 WeakProcessingHashTableHelper< | 2119 WeakProcessingHashTableHelper< |
| 2129 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, | 2120 Traits::weakHandlingFlag, Key, Value, Extractor, HashFunctions, |
| 2130 Traits, KeyTraits, Allocator>::ephemeronIterationDone); | 2121 Traits, KeyTraits, Allocator>::ephemeronIterationDone); |
| 2131 setEnqueued(); | 2122 setEnqueued(); |
| (...skipping 146 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 2278 CollectionIterator end(toBeRemoved.end()); | 2269 CollectionIterator end(toBeRemoved.end()); |
| 2279 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 2270 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
| 2280 collection.remove(*it); | 2271 collection.remove(*it); |
| 2281 } | 2272 } |
| 2282 | 2273 |
| 2283 } // namespace WTF | 2274 } // namespace WTF |
| 2284 | 2275 |
| 2285 #include "wtf/HashIterators.h" | 2276 #include "wtf/HashIterators.h" |
| 2286 | 2277 |
| 2287 #endif // WTF_HashTable_h | 2278 #endif // WTF_HashTable_h |
| OLD | NEW |