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 |