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 |