| 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) 2011, Benjamin Poulain <ikipou@gmail.com> | 3 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> |
| 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 | 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 13 * Library General Public License for more details. | 13 * Library General Public License for more details. |
| 14 * | 14 * |
| 15 * You should have received a copy of the GNU Library General Public License | 15 * You should have received a copy of the GNU Library General Public License |
| 16 * along with this library; see the file COPYING.LIB. If not, write to | 16 * along with this library; see the file COPYING.LIB. If not, write to |
| 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
| 18 * Boston, MA 02110-1301, USA. | 18 * Boston, MA 02110-1301, USA. |
| 19 * | 19 * |
| 20 */ | 20 */ |
| 21 | 21 |
| 22 #ifndef WTF_ListHashSet_h | 22 #ifndef WTF_ListHashSet_h |
| 23 #define WTF_ListHashSet_h | 23 #define WTF_ListHashSet_h |
| 24 | 24 |
| 25 #include "wtf/DefaultAllocator.h" | |
| 26 #include "wtf/HashSet.h" | 25 #include "wtf/HashSet.h" |
| 27 #include "wtf/OwnPtr.h" | 26 #include "wtf/OwnPtr.h" |
| 27 #include "wtf/PartitionAllocator.h" |
| 28 #include "wtf/PassOwnPtr.h" | 28 #include "wtf/PassOwnPtr.h" |
| 29 | 29 |
| 30 namespace WTF { | 30 namespace WTF { |
| 31 | 31 |
| 32 // ListHashSet: Just like HashSet, this class provides a Set interface - a | 32 // ListHashSet: Just like HashSet, this class provides a Set interface - a |
| 33 // collection of unique objects with O(1) insertion, removal and test for | 33 // collection of unique objects with O(1) insertion, removal and test for |
| 34 // containership. However, it also has an order - iterating it will always give | 34 // containership. However, it also has an order - iterating it will always give |
| 35 // back values in the order in which they are added. | 35 // back values in the order in which they are added. |
| 36 | 36 |
| 37 // Unlike iteration of most WTF Hash data structures, iteration is guaranteed | 37 // Unlike iteration of most WTF Hash data structures, iteration is guaranteed |
| (...skipping 181 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 219 ValueArg m_value; | 219 ValueArg m_value; |
| 220 ListHashSetNodeBase* m_prev; | 220 ListHashSetNodeBase* m_prev; |
| 221 ListHashSetNodeBase* m_next; | 221 ListHashSetNodeBase* m_next; |
| 222 #if ENABLE(ASSERT) | 222 #if ENABLE(ASSERT) |
| 223 bool m_isAllocated; | 223 bool m_isAllocated; |
| 224 #endif | 224 #endif |
| 225 }; | 225 }; |
| 226 | 226 |
| 227 // This allocator is only used for non-Heap ListHashSets. | 227 // This allocator is only used for non-Heap ListHashSets. |
| 228 template <typename ValueArg, size_t inlineCapacity> | 228 template <typename ValueArg, size_t inlineCapacity> |
| 229 struct ListHashSetAllocator : public DefaultAllocator { | 229 struct ListHashSetAllocator : public PartitionAllocator { |
| 230 typedef DefaultAllocator TableAllocator; | 230 typedef PartitionAllocator TableAllocator; |
| 231 typedef ListHashSetNode<ValueArg, ListHashSetAllocator> Node; | 231 typedef ListHashSetNode<ValueArg, ListHashSetAllocator> Node; |
| 232 typedef ListHashSetNodeBase<ValueArg> NodeBase; | 232 typedef ListHashSetNodeBase<ValueArg> NodeBase; |
| 233 | 233 |
| 234 class AllocatorProvider { | 234 class AllocatorProvider { |
| 235 public: | 235 public: |
| 236 AllocatorProvider() : m_allocator(nullptr) {} | 236 AllocatorProvider() : m_allocator(nullptr) {} |
| 237 void createAllocatorIfNeeded() | 237 void createAllocatorIfNeeded() |
| 238 { | 238 { |
| 239 if (!m_allocator) | 239 if (!m_allocator) |
| 240 m_allocator = new ListHashSetAllocator; | 240 m_allocator = new ListHashSetAllocator; |
| (...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 314 } | 314 } |
| 315 | 315 |
| 316 WTF::Partitions::fastFree(node); | 316 WTF::Partitions::fastFree(node); |
| 317 } | 317 } |
| 318 | 318 |
| 319 bool inPool(Node* node) | 319 bool inPool(Node* node) |
| 320 { | 320 { |
| 321 return node >= pool() && node < pastPool(); | 321 return node >= pool() && node < pastPool(); |
| 322 } | 322 } |
| 323 | 323 |
| 324 static void traceValue(typename DefaultAllocator::Visitor* visitor, Node* no
de) {} | 324 static void traceValue(typename PartitionAllocator::Visitor* visitor, Node*
node) {} |
| 325 | 325 |
| 326 private: | 326 private: |
| 327 Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.buffer); } | 327 Node* pool() { return reinterpret_cast_ptr<Node*>(m_pool.buffer); } |
| 328 Node* pastPool() { return pool() + m_poolSize; } | 328 Node* pastPool() { return pool() + m_poolSize; } |
| 329 | 329 |
| 330 Node* m_freeList; | 330 Node* m_freeList; |
| 331 bool m_isDoneWithInitialFreeList; | 331 bool m_isDoneWithInitialFreeList; |
| 332 #if defined(MEMORY_SANITIZER_INITIAL_SIZE) | 332 #if defined(MEMORY_SANITIZER_INITIAL_SIZE) |
| 333 // The allocation pool for nodes is one big chunk that ASAN has no insight | 333 // The allocation pool for nodes is one big chunk that ASAN has no insight |
| 334 // into, so it can cloak errors. Make it as small as possible to force nodes | 334 // into, so it can cloak errors. Make it as small as possible to force nodes |
| (...skipping 671 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1006 struct NeedsTracing<ListHashSet<T, U, V>> { | 1006 struct NeedsTracing<ListHashSet<T, U, V>> { |
| 1007 static const bool value = false; | 1007 static const bool value = false; |
| 1008 }; | 1008 }; |
| 1009 #endif | 1009 #endif |
| 1010 | 1010 |
| 1011 } // namespace WTF | 1011 } // namespace WTF |
| 1012 | 1012 |
| 1013 using WTF::ListHashSet; | 1013 using WTF::ListHashSet; |
| 1014 | 1014 |
| 1015 #endif // WTF_ListHashSet_h | 1015 #endif // WTF_ListHashSet_h |
| OLD | NEW |