| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. |
| 3 * Copyright (C) 2008 David Levin <levin@chromium.org> | 3 * Copyright (C) 2008 David Levin <levin@chromium.org> |
| 4 * | 4 * |
| 5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
| 6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
| 7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
| 8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
| 9 * | 9 * |
| 10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
| 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABIL
ITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public L
icense for more details. | 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABIL
ITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public L
icense for more details. |
| 12 * | 12 * |
| 13 * You should have received a copy of the GNU Library General Public License | 13 * You should have received a copy of the GNU Library General Public License |
| 14 * along with this library; see the file COPYING.LIB. If not, write to | 14 * along with this library; see the file COPYING.LIB. If not, write to |
| 15 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | 15 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
| 16 * Boston, MA 02110-1301, USA. | 16 * Boston, MA 02110-1301, USA. |
| 17 * | 17 * |
| 18 */ | 18 */ |
| 19 | 19 |
| 20 #ifndef WTF_HashTable_h | 20 #ifndef WTF_HashTable_h |
| 21 #define WTF_HashTable_h | 21 #define WTF_HashTable_h |
| 22 | 22 |
| 23 #include "wtf/Alignment.h" | 23 #include "wtf/Alignment.h" |
| 24 #include "wtf/Allocator.h" | 24 #include "wtf/Allocator.h" |
| 25 #include "wtf/Assertions.h" | 25 #include "wtf/Assertions.h" |
| 26 #include "wtf/ConditionalDestructor.h" | 26 #include "wtf/ConditionalDestructor.h" |
| 27 #include "wtf/HashTraits.h" | 27 #include "wtf/HashTraits.h" |
| 28 #include "wtf/PtrUtil.h" | |
| 29 #include "wtf/allocator/PartitionAllocator.h" | 28 #include "wtf/allocator/PartitionAllocator.h" |
| 30 #include <memory> | |
| 31 | 29 |
| 32 #define DUMP_HASHTABLE_STATS 0 | 30 #define DUMP_HASHTABLE_STATS 0 |
| 33 #define DUMP_HASHTABLE_STATS_PER_TABLE 0 | 31 #define DUMP_HASHTABLE_STATS_PER_TABLE 0 |
| 34 | 32 |
| 35 #if DUMP_HASHTABLE_STATS_PER_TABLE | 33 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 36 #include "wtf/DataLog.h" | 34 #include "wtf/DataLog.h" |
| 37 #endif | 35 #endif |
| 38 | 36 |
| 39 #if DUMP_HASHTABLE_STATS | 37 #if DUMP_HASHTABLE_STATS |
| 40 #if DUMP_HASHTABLE_STATS_PER_TABLE | 38 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| (...skipping 533 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 574 unsigned m_queueFlag:1; | 572 unsigned m_queueFlag:1; |
| 575 unsigned m_accessForbidden:1; | 573 unsigned m_accessForbidden:1; |
| 576 unsigned m_modifications; | 574 unsigned m_modifications; |
| 577 #else | 575 #else |
| 578 unsigned m_deletedCount:31; | 576 unsigned m_deletedCount:31; |
| 579 unsigned m_queueFlag:1; | 577 unsigned m_queueFlag:1; |
| 580 #endif | 578 #endif |
| 581 | 579 |
| 582 #if DUMP_HASHTABLE_STATS_PER_TABLE | 580 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 583 public: | 581 public: |
| 584 mutable std::unique_ptr<Stats> m_stats; | 582 mutable OwnPtr<Stats> m_stats; |
| 585 #endif | 583 #endif |
| 586 | 584 |
| 587 template <WeakHandlingFlag x, typename T, typename U, typename V, typename W
, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelpe
r; | 585 template <WeakHandlingFlag x, typename T, typename U, typename V, typename W
, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelpe
r; |
| 588 template <typename T, typename U, typename V, typename W> friend class Linke
dHashSet; | 586 template <typename T, typename U, typename V, typename W> friend class Linke
dHashSet; |
| 589 }; | 587 }; |
| 590 | 588 |
| 591 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 589 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
| 592 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Alloca
tor>::HashTable() | 590 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Alloca
tor>::HashTable() |
| 593 : m_table(nullptr) | 591 : m_table(nullptr) |
| 594 , m_tableSize(0) | 592 , m_tableSize(0) |
| 595 , m_keyCount(0) | 593 , m_keyCount(0) |
| 596 , m_deletedCount(0) | 594 , m_deletedCount(0) |
| 597 , m_queueFlag(false) | 595 , m_queueFlag(false) |
| 598 #if ENABLE(ASSERT) | 596 #if ENABLE(ASSERT) |
| 599 , m_accessForbidden(false) | 597 , m_accessForbidden(false) |
| 600 , m_modifications(0) | 598 , m_modifications(0) |
| 601 #endif | 599 #endif |
| 602 #if DUMP_HASHTABLE_STATS_PER_TABLE | 600 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 603 , m_stats(wrapUnique(new Stats)) | 601 , m_stats(adoptPtr(new Stats)) |
| 604 #endif | 602 #endif |
| 605 { | 603 { |
| 606 static_assert(Allocator::isGarbageCollected || (!IsPointerToGarbageCollected
Type<Key>::value && !IsPointerToGarbageCollectedType<Value>::value), "Cannot put
raw pointers to garbage-collected classes into an off-heap collection."); | 604 static_assert(Allocator::isGarbageCollected || (!IsPointerToGarbageCollected
Type<Key>::value && !IsPointerToGarbageCollectedType<Value>::value), "Cannot put
raw pointers to garbage-collected classes into an off-heap collection."); |
| 607 } | 605 } |
| 608 | 606 |
| 609 inline unsigned doubleHash(unsigned key) | 607 inline unsigned doubleHash(unsigned key) |
| 610 { | 608 { |
| 611 key = ~key + (key >> 23); | 609 key = ~key + (key >> 23); |
| 612 key ^= (key << 12); | 610 key ^= (key << 12); |
| 613 key ^= (key >> 7); | 611 key ^= (key >> 7); |
| (...skipping 616 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1230 : m_table(nullptr) | 1228 : m_table(nullptr) |
| 1231 , m_tableSize(0) | 1229 , m_tableSize(0) |
| 1232 , m_keyCount(0) | 1230 , m_keyCount(0) |
| 1233 , m_deletedCount(0) | 1231 , m_deletedCount(0) |
| 1234 , m_queueFlag(false) | 1232 , m_queueFlag(false) |
| 1235 #if ENABLE(ASSERT) | 1233 #if ENABLE(ASSERT) |
| 1236 , m_accessForbidden(false) | 1234 , m_accessForbidden(false) |
| 1237 , m_modifications(0) | 1235 , m_modifications(0) |
| 1238 #endif | 1236 #endif |
| 1239 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1237 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1240 , m_stats(wrapUnique(new Stats(*other.m_stats))) | 1238 , m_stats(adoptPtr(new Stats(*other.m_stats))) |
| 1241 #endif | 1239 #endif |
| 1242 { | 1240 { |
| 1243 // Copy the hash table the dumb way, by adding each element to the new | 1241 // Copy the hash table the dumb way, by adding each element to the new |
| 1244 // table. It might be more efficient to copy the table slots, but it's not | 1242 // table. It might be more efficient to copy the table slots, but it's not |
| 1245 // clear that efficiency is needed. | 1243 // clear that efficiency is needed. |
| 1246 const_iterator end = other.end(); | 1244 const_iterator end = other.end(); |
| 1247 for (const_iterator it = other.begin(); it != end; ++it) | 1245 for (const_iterator it = other.begin(); it != end; ++it) |
| 1248 add(*it); | 1246 add(*it); |
| 1249 } | 1247 } |
| 1250 | 1248 |
| 1251 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 1249 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
| 1252 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::H
ashTable(HashTable&& other) | 1250 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::H
ashTable(HashTable&& other) |
| 1253 : m_table(nullptr) | 1251 : m_table(nullptr) |
| 1254 , m_tableSize(0) | 1252 , m_tableSize(0) |
| 1255 , m_keyCount(0) | 1253 , m_keyCount(0) |
| 1256 , m_deletedCount(0) | 1254 , m_deletedCount(0) |
| 1257 , m_queueFlag(false) | 1255 , m_queueFlag(false) |
| 1258 #if ENABLE(ASSERT) | 1256 #if ENABLE(ASSERT) |
| 1259 , m_accessForbidden(false) | 1257 , m_accessForbidden(false) |
| 1260 , m_modifications(0) | 1258 , m_modifications(0) |
| 1261 #endif | 1259 #endif |
| 1262 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1260 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1263 , m_stats(wrapUnique(new Stats(*other.m_stats))) | 1261 , m_stats(adoptPtr(new Stats(*other.m_stats))) |
| 1264 #endif | 1262 #endif |
| 1265 { | 1263 { |
| 1266 swap(other); | 1264 swap(other); |
| 1267 } | 1265 } |
| 1268 | 1266 |
| 1269 | 1267 |
| 1270 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 1268 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
| 1271 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocato
r>::swap(HashTable& other) | 1269 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocato
r>::swap(HashTable& other) |
| 1272 { | 1270 { |
| 1273 ASSERT(!m_accessForbidden); | 1271 ASSERT(!m_accessForbidden); |
| (...skipping 263 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1537 CollectionIterator end(toBeRemoved.end()); | 1535 CollectionIterator end(toBeRemoved.end()); |
| 1538 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 1536 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
| 1539 collection.remove(*it); | 1537 collection.remove(*it); |
| 1540 } | 1538 } |
| 1541 | 1539 |
| 1542 } // namespace WTF | 1540 } // namespace WTF |
| 1543 | 1541 |
| 1544 #include "wtf/HashIterators.h" | 1542 #include "wtf/HashIterators.h" |
| 1545 | 1543 |
| 1546 #endif // WTF_HashTable_h | 1544 #endif // WTF_HashTable_h |
| OLD | NEW |