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 |