| 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" |
| 28 #include "wtf/allocator/PartitionAllocator.h" | 29 #include "wtf/allocator/PartitionAllocator.h" |
| 30 #include <memory> |
| 29 | 31 |
| 30 #define DUMP_HASHTABLE_STATS 0 | 32 #define DUMP_HASHTABLE_STATS 0 |
| 31 #define DUMP_HASHTABLE_STATS_PER_TABLE 0 | 33 #define DUMP_HASHTABLE_STATS_PER_TABLE 0 |
| 32 | 34 |
| 33 #if DUMP_HASHTABLE_STATS_PER_TABLE | 35 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 34 #include "wtf/DataLog.h" | 36 #include "wtf/DataLog.h" |
| 35 #endif | 37 #endif |
| 36 | 38 |
| 37 #if DUMP_HASHTABLE_STATS | 39 #if DUMP_HASHTABLE_STATS |
| 38 #if DUMP_HASHTABLE_STATS_PER_TABLE | 40 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| (...skipping 533 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 572 unsigned m_queueFlag:1; | 574 unsigned m_queueFlag:1; |
| 573 unsigned m_accessForbidden:1; | 575 unsigned m_accessForbidden:1; |
| 574 unsigned m_modifications; | 576 unsigned m_modifications; |
| 575 #else | 577 #else |
| 576 unsigned m_deletedCount:31; | 578 unsigned m_deletedCount:31; |
| 577 unsigned m_queueFlag:1; | 579 unsigned m_queueFlag:1; |
| 578 #endif | 580 #endif |
| 579 | 581 |
| 580 #if DUMP_HASHTABLE_STATS_PER_TABLE | 582 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 581 public: | 583 public: |
| 582 mutable OwnPtr<Stats> m_stats; | 584 mutable std::unique_ptr<Stats> m_stats; |
| 583 #endif | 585 #endif |
| 584 | 586 |
| 585 template <WeakHandlingFlag x, typename T, typename U, typename V, typename W
, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelpe
r; | 587 template <WeakHandlingFlag x, typename T, typename U, typename V, typename W
, typename X, typename Y, typename Z> friend struct WeakProcessingHashTableHelpe
r; |
| 586 template <typename T, typename U, typename V, typename W> friend class Linke
dHashSet; | 588 template <typename T, typename U, typename V, typename W> friend class Linke
dHashSet; |
| 587 }; | 589 }; |
| 588 | 590 |
| 589 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 591 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
| 590 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Alloca
tor>::HashTable() | 592 inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Alloca
tor>::HashTable() |
| 591 : m_table(nullptr) | 593 : m_table(nullptr) |
| 592 , m_tableSize(0) | 594 , m_tableSize(0) |
| 593 , m_keyCount(0) | 595 , m_keyCount(0) |
| 594 , m_deletedCount(0) | 596 , m_deletedCount(0) |
| 595 , m_queueFlag(false) | 597 , m_queueFlag(false) |
| 596 #if ENABLE(ASSERT) | 598 #if ENABLE(ASSERT) |
| 597 , m_accessForbidden(false) | 599 , m_accessForbidden(false) |
| 598 , m_modifications(0) | 600 , m_modifications(0) |
| 599 #endif | 601 #endif |
| 600 #if DUMP_HASHTABLE_STATS_PER_TABLE | 602 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 601 , m_stats(adoptPtr(new Stats)) | 603 , m_stats(wrapUnique(new Stats)) |
| 602 #endif | 604 #endif |
| 603 { | 605 { |
| 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."); | 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."); |
| 605 } | 607 } |
| 606 | 608 |
| 607 inline unsigned doubleHash(unsigned key) | 609 inline unsigned doubleHash(unsigned key) |
| 608 { | 610 { |
| 609 key = ~key + (key >> 23); | 611 key = ~key + (key >> 23); |
| 610 key ^= (key << 12); | 612 key ^= (key << 12); |
| 611 key ^= (key >> 7); | 613 key ^= (key >> 7); |
| (...skipping 616 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1228 : m_table(nullptr) | 1230 : m_table(nullptr) |
| 1229 , m_tableSize(0) | 1231 , m_tableSize(0) |
| 1230 , m_keyCount(0) | 1232 , m_keyCount(0) |
| 1231 , m_deletedCount(0) | 1233 , m_deletedCount(0) |
| 1232 , m_queueFlag(false) | 1234 , m_queueFlag(false) |
| 1233 #if ENABLE(ASSERT) | 1235 #if ENABLE(ASSERT) |
| 1234 , m_accessForbidden(false) | 1236 , m_accessForbidden(false) |
| 1235 , m_modifications(0) | 1237 , m_modifications(0) |
| 1236 #endif | 1238 #endif |
| 1237 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1239 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1238 , m_stats(adoptPtr(new Stats(*other.m_stats))) | 1240 , m_stats(wrapUnique(new Stats(*other.m_stats))) |
| 1239 #endif | 1241 #endif |
| 1240 { | 1242 { |
| 1241 // Copy the hash table the dumb way, by adding each element to the new | 1243 // Copy the hash table the dumb way, by adding each element to the new |
| 1242 // table. It might be more efficient to copy the table slots, but it's not | 1244 // table. It might be more efficient to copy the table slots, but it's not |
| 1243 // clear that efficiency is needed. | 1245 // clear that efficiency is needed. |
| 1244 const_iterator end = other.end(); | 1246 const_iterator end = other.end(); |
| 1245 for (const_iterator it = other.begin(); it != end; ++it) | 1247 for (const_iterator it = other.begin(); it != end; ++it) |
| 1246 add(*it); | 1248 add(*it); |
| 1247 } | 1249 } |
| 1248 | 1250 |
| 1249 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 1251 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
| 1250 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::H
ashTable(HashTable&& other) | 1252 HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::H
ashTable(HashTable&& other) |
| 1251 : m_table(nullptr) | 1253 : m_table(nullptr) |
| 1252 , m_tableSize(0) | 1254 , m_tableSize(0) |
| 1253 , m_keyCount(0) | 1255 , m_keyCount(0) |
| 1254 , m_deletedCount(0) | 1256 , m_deletedCount(0) |
| 1255 , m_queueFlag(false) | 1257 , m_queueFlag(false) |
| 1256 #if ENABLE(ASSERT) | 1258 #if ENABLE(ASSERT) |
| 1257 , m_accessForbidden(false) | 1259 , m_accessForbidden(false) |
| 1258 , m_modifications(0) | 1260 , m_modifications(0) |
| 1259 #endif | 1261 #endif |
| 1260 #if DUMP_HASHTABLE_STATS_PER_TABLE | 1262 #if DUMP_HASHTABLE_STATS_PER_TABLE |
| 1261 , m_stats(adoptPtr(new Stats(*other.m_stats))) | 1263 , m_stats(wrapUnique(new Stats(*other.m_stats))) |
| 1262 #endif | 1264 #endif |
| 1263 { | 1265 { |
| 1264 swap(other); | 1266 swap(other); |
| 1265 } | 1267 } |
| 1266 | 1268 |
| 1267 | 1269 |
| 1268 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> | 1270 template <typename Key, typename Value, typename Extractor, typename HashFunctio
ns, typename Traits, typename KeyTraits, typename Allocator> |
| 1269 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocato
r>::swap(HashTable& other) | 1271 void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocato
r>::swap(HashTable& other) |
| 1270 { | 1272 { |
| 1271 ASSERT(!m_accessForbidden); | 1273 ASSERT(!m_accessForbidden); |
| (...skipping 263 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1535 CollectionIterator end(toBeRemoved.end()); | 1537 CollectionIterator end(toBeRemoved.end()); |
| 1536 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) | 1538 for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it) |
| 1537 collection.remove(*it); | 1539 collection.remove(*it); |
| 1538 } | 1540 } |
| 1539 | 1541 |
| 1540 } // namespace WTF | 1542 } // namespace WTF |
| 1541 | 1543 |
| 1542 #include "wtf/HashIterators.h" | 1544 #include "wtf/HashIterators.h" |
| 1543 | 1545 |
| 1544 #endif // WTF_HashTable_h | 1546 #endif // WTF_HashTable_h |
| OLD | NEW |