OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights |
3 * reserved. | 3 * reserved. |
4 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> | 4 * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com> |
5 * | 5 * |
6 * This library is free software; you can redistribute it and/or | 6 * This library is free software; you can redistribute it and/or |
7 * modify it under the terms of the GNU Library General Public | 7 * modify it under the terms of the GNU Library General Public |
8 * License as published by the Free Software Foundation; either | 8 * License as published by the Free Software Foundation; either |
9 * version 2 of the License, or (at your option) any later version. | 9 * version 2 of the License, or (at your option) any later version. |
10 * | 10 * |
(...skipping 248 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
259 | 259 |
260 // ListHashSetNode has this base class to hold the members because the MSVC | 260 // ListHashSetNode has this base class to hold the members because the MSVC |
261 // compiler otherwise gets into circular template dependencies when trying to do | 261 // compiler otherwise gets into circular template dependencies when trying to do |
262 // sizeof on a node. | 262 // sizeof on a node. |
263 template <typename ValueArg> | 263 template <typename ValueArg> |
264 class ListHashSetNodeBase { | 264 class ListHashSetNodeBase { |
265 DISALLOW_NEW(); | 265 DISALLOW_NEW(); |
266 | 266 |
267 protected: | 267 protected: |
268 template <typename U> | 268 template <typename U> |
269 explicit ListHashSetNodeBase(U&& value) | 269 explicit ListHashSetNodeBase(U&& value) : m_value(std::forward<U>(value)) {} |
270 : m_value(std::forward<U>(value)), | |
271 m_prev(nullptr), | |
272 m_next(nullptr) | |
273 #if ENABLE(ASSERT) | |
274 , | |
275 m_isAllocated(true) | |
276 #endif | |
277 { | |
278 } | |
279 | 270 |
280 public: | 271 public: |
281 ValueArg m_value; | 272 ValueArg m_value; |
282 ListHashSetNodeBase* m_prev; | 273 ListHashSetNodeBase* m_prev = nullptr; |
283 ListHashSetNodeBase* m_next; | 274 ListHashSetNodeBase* m_next = nullptr; |
284 #if ENABLE(ASSERT) | 275 #if DCHECK_IS_ON() |
285 bool m_isAllocated; | 276 bool m_isAllocated = true; |
286 #endif | 277 #endif |
287 }; | 278 }; |
288 | 279 |
289 // This allocator is only used for non-Heap ListHashSets. | 280 // This allocator is only used for non-Heap ListHashSets. |
290 template <typename ValueArg, size_t inlineCapacity> | 281 template <typename ValueArg, size_t inlineCapacity> |
291 struct ListHashSetAllocator : public PartitionAllocator { | 282 struct ListHashSetAllocator : public PartitionAllocator { |
292 typedef PartitionAllocator TableAllocator; | 283 typedef PartitionAllocator TableAllocator; |
293 typedef ListHashSetNode<ValueArg, ListHashSetAllocator> Node; | 284 typedef ListHashSetNode<ValueArg, ListHashSetAllocator> Node; |
294 typedef ListHashSetNodeBase<ValueArg> NodeBase; | 285 typedef ListHashSetNodeBase<ValueArg> NodeBase; |
295 | 286 |
(...skipping 10 matching lines...) Expand all Loading... |
306 void releaseAllocator() { | 297 void releaseAllocator() { |
307 delete m_allocator; | 298 delete m_allocator; |
308 m_allocator = nullptr; | 299 m_allocator = nullptr; |
309 } | 300 } |
310 | 301 |
311 void swap(AllocatorProvider& other) { | 302 void swap(AllocatorProvider& other) { |
312 std::swap(m_allocator, other.m_allocator); | 303 std::swap(m_allocator, other.m_allocator); |
313 } | 304 } |
314 | 305 |
315 void deallocate(Node* node) const { | 306 void deallocate(Node* node) const { |
316 ASSERT(m_allocator); | 307 DCHECK(m_allocator); |
317 m_allocator->deallocate(node); | 308 m_allocator->deallocate(node); |
318 } | 309 } |
319 | 310 |
320 ListHashSetAllocator* get() const { | 311 ListHashSetAllocator* get() const { |
321 ASSERT(m_allocator); | 312 DCHECK(m_allocator); |
322 return m_allocator; | 313 return m_allocator; |
323 } | 314 } |
324 | 315 |
325 private: | 316 private: |
326 // Not using std::unique_ptr as this pointer should be deleted at | 317 // Not using std::unique_ptr as this pointer should be deleted at |
327 // releaseAllocator() method rather than at destructor. | 318 // releaseAllocator() method rather than at destructor. |
328 ListHashSetAllocator* m_allocator; | 319 ListHashSetAllocator* m_allocator; |
329 }; | 320 }; |
330 | 321 |
331 ListHashSetAllocator() | 322 ListHashSetAllocator() |
332 : m_freeList(pool()), m_isDoneWithInitialFreeList(false) { | 323 : m_freeList(pool()), m_isDoneWithInitialFreeList(false) { |
333 memset(m_pool.buffer, 0, sizeof(m_pool.buffer)); | 324 memset(m_pool.buffer, 0, sizeof(m_pool.buffer)); |
334 } | 325 } |
335 | 326 |
336 Node* allocateNode() { | 327 Node* allocateNode() { |
337 Node* result = m_freeList; | 328 Node* result = m_freeList; |
338 | 329 |
339 if (!result) | 330 if (!result) |
340 return static_cast<Node*>(WTF::Partitions::fastMalloc( | 331 return static_cast<Node*>(WTF::Partitions::fastMalloc( |
341 sizeof(NodeBase), WTF_HEAP_PROFILER_TYPE_NAME(Node))); | 332 sizeof(NodeBase), WTF_HEAP_PROFILER_TYPE_NAME(Node))); |
342 | 333 |
343 ASSERT(!result->m_isAllocated); | 334 #if DCHECK_IS_ON() |
| 335 DCHECK(!result->m_isAllocated); |
| 336 #endif |
344 | 337 |
345 Node* next = result->next(); | 338 Node* next = result->next(); |
346 ASSERT(!next || !next->m_isAllocated); | 339 #if DCHECK_IS_ON() |
| 340 DCHECK(!next || !next->m_isAllocated); |
| 341 #endif |
347 if (!next && !m_isDoneWithInitialFreeList) { | 342 if (!next && !m_isDoneWithInitialFreeList) { |
348 next = result + 1; | 343 next = result + 1; |
349 if (next == pastPool()) { | 344 if (next == pastPool()) { |
350 m_isDoneWithInitialFreeList = true; | 345 m_isDoneWithInitialFreeList = true; |
351 next = nullptr; | 346 next = nullptr; |
352 } else { | 347 } else { |
353 ASSERT(inPool(next)); | 348 DCHECK(inPool(next)); |
354 ASSERT(!next->m_isAllocated); | 349 #if DCHECK_IS_ON() |
| 350 DCHECK(!next->m_isAllocated); |
| 351 #endif |
355 } | 352 } |
356 } | 353 } |
357 m_freeList = next; | 354 m_freeList = next; |
358 | 355 |
359 return result; | 356 return result; |
360 } | 357 } |
361 | 358 |
362 void deallocate(Node* node) { | 359 void deallocate(Node* node) { |
363 if (inPool(node)) { | 360 if (inPool(node)) { |
364 #if ENABLE(ASSERT) | 361 #if DCHECK_IS_ON() |
365 node->m_isAllocated = false; | 362 node->m_isAllocated = false; |
366 #endif | 363 #endif |
367 node->m_next = m_freeList; | 364 node->m_next = m_freeList; |
368 m_freeList = node; | 365 m_freeList = node; |
369 return; | 366 return; |
370 } | 367 } |
371 | 368 |
372 WTF::Partitions::fastFree(node); | 369 WTF::Partitions::fastFree(node); |
373 } | 370 } |
374 | 371 |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
411 return allocator->allocateNode(); | 408 return allocator->allocateNode(); |
412 } | 409 } |
413 | 410 |
414 void setWasAlreadyDestructed() { | 411 void setWasAlreadyDestructed() { |
415 if (NodeAllocator::isGarbageCollected && | 412 if (NodeAllocator::isGarbageCollected && |
416 !IsTriviallyDestructible<ValueArg>::value) | 413 !IsTriviallyDestructible<ValueArg>::value) |
417 this->m_prev = unlinkedNodePointer(); | 414 this->m_prev = unlinkedNodePointer(); |
418 } | 415 } |
419 | 416 |
420 bool wasAlreadyDestructed() const { | 417 bool wasAlreadyDestructed() const { |
421 ASSERT(NodeAllocator::isGarbageCollected); | 418 DCHECK(NodeAllocator::isGarbageCollected); |
422 return this->m_prev == unlinkedNodePointer(); | 419 return this->m_prev == unlinkedNodePointer(); |
423 } | 420 } |
424 | 421 |
425 static void finalize(void* pointer) { | 422 static void finalize(void* pointer) { |
426 // No need to waste time calling finalize if it's not needed. | 423 // No need to waste time calling finalize if it's not needed. |
427 ASSERT(!IsTriviallyDestructible<ValueArg>::value); | 424 DCHECK(!IsTriviallyDestructible<ValueArg>::value); |
428 ListHashSetNode* self = reinterpret_cast_ptr<ListHashSetNode*>(pointer); | 425 ListHashSetNode* self = reinterpret_cast_ptr<ListHashSetNode*>(pointer); |
429 | 426 |
430 // Check whether this node was already destructed before being unlinked | 427 // Check whether this node was already destructed before being unlinked |
431 // from the collection. | 428 // from the collection. |
432 if (self->wasAlreadyDestructed()) | 429 if (self->wasAlreadyDestructed()) |
433 return; | 430 return; |
434 | 431 |
435 self->m_value.~ValueArg(); | 432 self->m_value.~ValueArg(); |
436 } | 433 } |
437 void finalizeGarbageCollectedObject() { finalize(this); } | 434 void finalizeGarbageCollectedObject() { finalize(this); } |
(...skipping 126 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
564 : m_set(set), m_position(position) {} | 561 : m_set(set), m_position(position) {} |
565 | 562 |
566 public: | 563 public: |
567 ListHashSetConstIterator() {} | 564 ListHashSetConstIterator() {} |
568 | 565 |
569 PointerType get() const { return &m_position->m_value; } | 566 PointerType get() const { return &m_position->m_value; } |
570 ReferenceType operator*() const { return *get(); } | 567 ReferenceType operator*() const { return *get(); } |
571 PointerType operator->() const { return get(); } | 568 PointerType operator->() const { return get(); } |
572 | 569 |
573 ListHashSetConstIterator& operator++() { | 570 ListHashSetConstIterator& operator++() { |
574 ASSERT(m_position != 0); | 571 DCHECK(m_position); |
575 m_position = m_position->next(); | 572 m_position = m_position->next(); |
576 return *this; | 573 return *this; |
577 } | 574 } |
578 | 575 |
579 ListHashSetConstIterator& operator--() { | 576 ListHashSetConstIterator& operator--() { |
580 ASSERT(m_position != m_set->m_head); | 577 DCHECK_NE(m_position, m_set->m_head); |
581 if (!m_position) | 578 if (!m_position) |
582 m_position = m_set->m_tail; | 579 m_position = m_set->m_tail; |
583 else | 580 else |
584 m_position = m_position->prev(); | 581 m_position = m_position->prev(); |
585 return *this; | 582 return *this; |
586 } | 583 } |
587 | 584 |
588 // Postfix ++ and -- intentionally omitted. | 585 // Postfix ++ and -- intentionally omitted. |
589 | 586 |
590 // Comparison. | 587 // Comparison. |
(...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
675 : m_set(set), m_position(position) {} | 672 : m_set(set), m_position(position) {} |
676 | 673 |
677 public: | 674 public: |
678 ListHashSetConstReverseIterator() {} | 675 ListHashSetConstReverseIterator() {} |
679 | 676 |
680 PointerType get() const { return &m_position->m_value; } | 677 PointerType get() const { return &m_position->m_value; } |
681 ReferenceType operator*() const { return *get(); } | 678 ReferenceType operator*() const { return *get(); } |
682 PointerType operator->() const { return get(); } | 679 PointerType operator->() const { return get(); } |
683 | 680 |
684 ListHashSetConstReverseIterator& operator++() { | 681 ListHashSetConstReverseIterator& operator++() { |
685 ASSERT(m_position != 0); | 682 DCHECK(m_position); |
686 m_position = m_position->prev(); | 683 m_position = m_position->prev(); |
687 return *this; | 684 return *this; |
688 } | 685 } |
689 | 686 |
690 ListHashSetConstReverseIterator& operator--() { | 687 ListHashSetConstReverseIterator& operator--() { |
691 ASSERT(m_position != m_set->m_tail); | 688 DCHECK_NE(m_position, m_set->m_tail); |
692 if (!m_position) | 689 if (!m_position) |
693 m_position = m_set->m_head; | 690 m_position = m_set->m_head; |
694 else | 691 else |
695 m_position = m_position->next(); | 692 m_position = m_position->next(); |
696 return *this; | 693 return *this; |
697 } | 694 } |
698 | 695 |
699 // Postfix ++ and -- intentionally omitted. | 696 // Postfix ++ and -- intentionally omitted. |
700 | 697 |
701 // Comparison. | 698 // Comparison. |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
784 template <typename T, size_t inlineCapacity, typename U, typename V> | 781 template <typename T, size_t inlineCapacity, typename U, typename V> |
785 inline void ListHashSet<T, inlineCapacity, U, V>::finalize() { | 782 inline void ListHashSet<T, inlineCapacity, U, V>::finalize() { |
786 static_assert(!Allocator::isGarbageCollected, | 783 static_assert(!Allocator::isGarbageCollected, |
787 "heap allocated ListHashSet should never call finalize()"); | 784 "heap allocated ListHashSet should never call finalize()"); |
788 deleteAllNodes(); | 785 deleteAllNodes(); |
789 m_allocatorProvider.releaseAllocator(); | 786 m_allocatorProvider.releaseAllocator(); |
790 } | 787 } |
791 | 788 |
792 template <typename T, size_t inlineCapacity, typename U, typename V> | 789 template <typename T, size_t inlineCapacity, typename U, typename V> |
793 inline T& ListHashSet<T, inlineCapacity, U, V>::first() { | 790 inline T& ListHashSet<T, inlineCapacity, U, V>::first() { |
794 ASSERT(!isEmpty()); | 791 DCHECK(!isEmpty()); |
795 return m_head->m_value; | 792 return m_head->m_value; |
796 } | 793 } |
797 | 794 |
798 template <typename T, size_t inlineCapacity, typename U, typename V> | 795 template <typename T, size_t inlineCapacity, typename U, typename V> |
799 inline void ListHashSet<T, inlineCapacity, U, V>::removeFirst() { | 796 inline void ListHashSet<T, inlineCapacity, U, V>::removeFirst() { |
800 ASSERT(!isEmpty()); | 797 DCHECK(!isEmpty()); |
801 m_impl.remove(m_head); | 798 m_impl.remove(m_head); |
802 unlinkAndDelete(m_head); | 799 unlinkAndDelete(m_head); |
803 } | 800 } |
804 | 801 |
805 template <typename T, size_t inlineCapacity, typename U, typename V> | 802 template <typename T, size_t inlineCapacity, typename U, typename V> |
806 inline const T& ListHashSet<T, inlineCapacity, U, V>::first() const { | 803 inline const T& ListHashSet<T, inlineCapacity, U, V>::first() const { |
807 ASSERT(!isEmpty()); | 804 DCHECK(!isEmpty()); |
808 return m_head->m_value; | 805 return m_head->m_value; |
809 } | 806 } |
810 | 807 |
811 template <typename T, size_t inlineCapacity, typename U, typename V> | 808 template <typename T, size_t inlineCapacity, typename U, typename V> |
812 inline T& ListHashSet<T, inlineCapacity, U, V>::last() { | 809 inline T& ListHashSet<T, inlineCapacity, U, V>::last() { |
813 ASSERT(!isEmpty()); | 810 DCHECK(!isEmpty()); |
814 return m_tail->m_value; | 811 return m_tail->m_value; |
815 } | 812 } |
816 | 813 |
817 template <typename T, size_t inlineCapacity, typename U, typename V> | 814 template <typename T, size_t inlineCapacity, typename U, typename V> |
818 inline const T& ListHashSet<T, inlineCapacity, U, V>::last() const { | 815 inline const T& ListHashSet<T, inlineCapacity, U, V>::last() const { |
819 ASSERT(!isEmpty()); | 816 DCHECK(!isEmpty()); |
820 return m_tail->m_value; | 817 return m_tail->m_value; |
821 } | 818 } |
822 | 819 |
823 template <typename T, size_t inlineCapacity, typename U, typename V> | 820 template <typename T, size_t inlineCapacity, typename U, typename V> |
824 inline void ListHashSet<T, inlineCapacity, U, V>::removeLast() { | 821 inline void ListHashSet<T, inlineCapacity, U, V>::removeLast() { |
825 ASSERT(!isEmpty()); | 822 DCHECK(!isEmpty()); |
826 m_impl.remove(m_tail); | 823 m_impl.remove(m_tail); |
827 unlinkAndDelete(m_tail); | 824 unlinkAndDelete(m_tail); |
828 } | 825 } |
829 | 826 |
830 template <typename T, size_t inlineCapacity, typename U, typename V> | 827 template <typename T, size_t inlineCapacity, typename U, typename V> |
831 inline typename ListHashSet<T, inlineCapacity, U, V>::iterator | 828 inline typename ListHashSet<T, inlineCapacity, U, V>::iterator |
832 ListHashSet<T, inlineCapacity, U, V>::find(ValuePeekInType value) { | 829 ListHashSet<T, inlineCapacity, U, V>::find(ValuePeekInType value) { |
833 ImplTypeIterator it = m_impl.template find<BaseTranslator>(value); | 830 ImplTypeIterator it = m_impl.template find<BaseTranslator>(value); |
834 if (it == m_impl.end()) | 831 if (it == m_impl.end()) |
835 return end(); | 832 return end(); |
(...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1002 } | 999 } |
1003 | 1000 |
1004 template <typename T, size_t inlineCapacity, typename U, typename V> | 1001 template <typename T, size_t inlineCapacity, typename U, typename V> |
1005 auto ListHashSet<T, inlineCapacity, U, V>::take(ValuePeekInType value) | 1002 auto ListHashSet<T, inlineCapacity, U, V>::take(ValuePeekInType value) |
1006 -> ValueType { | 1003 -> ValueType { |
1007 return take(find(value)); | 1004 return take(find(value)); |
1008 } | 1005 } |
1009 | 1006 |
1010 template <typename T, size_t inlineCapacity, typename U, typename V> | 1007 template <typename T, size_t inlineCapacity, typename U, typename V> |
1011 auto ListHashSet<T, inlineCapacity, U, V>::takeFirst() -> ValueType { | 1008 auto ListHashSet<T, inlineCapacity, U, V>::takeFirst() -> ValueType { |
1012 ASSERT(!isEmpty()); | 1009 DCHECK(!isEmpty()); |
1013 m_impl.remove(m_head); | 1010 m_impl.remove(m_head); |
1014 ValueType result = std::move(m_head->m_value); | 1011 ValueType result = std::move(m_head->m_value); |
1015 unlinkAndDelete(m_head); | 1012 unlinkAndDelete(m_head); |
1016 | 1013 |
1017 return result; | 1014 return result; |
1018 } | 1015 } |
1019 | 1016 |
1020 template <typename T, size_t inlineCapacity, typename U, typename Allocator> | 1017 template <typename T, size_t inlineCapacity, typename U, typename Allocator> |
1021 void ListHashSet<T, inlineCapacity, U, Allocator>::unlink(Node* node) { | 1018 void ListHashSet<T, inlineCapacity, U, Allocator>::unlink(Node* node) { |
1022 if (!node->m_prev) { | 1019 if (!node->m_prev) { |
1023 ASSERT(node == m_head); | 1020 DCHECK_EQ(node, m_head); |
1024 m_head = node->next(); | 1021 m_head = node->next(); |
1025 } else { | 1022 } else { |
1026 ASSERT(node != m_head); | 1023 DCHECK_NE(node, m_head); |
1027 node->m_prev->m_next = node->m_next; | 1024 node->m_prev->m_next = node->m_next; |
1028 } | 1025 } |
1029 | 1026 |
1030 if (!node->m_next) { | 1027 if (!node->m_next) { |
1031 ASSERT(node == m_tail); | 1028 DCHECK_EQ(node, m_tail); |
1032 m_tail = node->prev(); | 1029 m_tail = node->prev(); |
1033 } else { | 1030 } else { |
1034 ASSERT(node != m_tail); | 1031 DCHECK_NE(node, m_tail); |
1035 node->m_next->m_prev = node->m_prev; | 1032 node->m_next->m_prev = node->m_prev; |
1036 } | 1033 } |
1037 } | 1034 } |
1038 | 1035 |
1039 template <typename T, size_t inlineCapacity, typename U, typename V> | 1036 template <typename T, size_t inlineCapacity, typename U, typename V> |
1040 void ListHashSet<T, inlineCapacity, U, V>::unlinkAndDelete(Node* node) { | 1037 void ListHashSet<T, inlineCapacity, U, V>::unlinkAndDelete(Node* node) { |
1041 unlink(node); | 1038 unlink(node); |
1042 node->destroy(this->getAllocator()); | 1039 node->destroy(this->getAllocator()); |
1043 } | 1040 } |
1044 | 1041 |
1045 template <typename T, size_t inlineCapacity, typename U, typename V> | 1042 template <typename T, size_t inlineCapacity, typename U, typename V> |
1046 void ListHashSet<T, inlineCapacity, U, V>::appendNode(Node* node) { | 1043 void ListHashSet<T, inlineCapacity, U, V>::appendNode(Node* node) { |
1047 node->m_prev = m_tail; | 1044 node->m_prev = m_tail; |
1048 node->m_next = nullptr; | 1045 node->m_next = nullptr; |
1049 | 1046 |
1050 if (m_tail) { | 1047 if (m_tail) { |
1051 ASSERT(m_head); | 1048 DCHECK(m_head); |
1052 m_tail->m_next = node; | 1049 m_tail->m_next = node; |
1053 } else { | 1050 } else { |
1054 ASSERT(!m_head); | 1051 DCHECK(!m_head); |
1055 m_head = node; | 1052 m_head = node; |
1056 } | 1053 } |
1057 | 1054 |
1058 m_tail = node; | 1055 m_tail = node; |
1059 } | 1056 } |
1060 | 1057 |
1061 template <typename T, size_t inlineCapacity, typename U, typename V> | 1058 template <typename T, size_t inlineCapacity, typename U, typename V> |
1062 void ListHashSet<T, inlineCapacity, U, V>::prependNode(Node* node) { | 1059 void ListHashSet<T, inlineCapacity, U, V>::prependNode(Node* node) { |
1063 node->m_prev = nullptr; | 1060 node->m_prev = nullptr; |
1064 node->m_next = m_head; | 1061 node->m_next = m_head; |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1107 // through the HashTable. That includes m_head and m_tail so we do not have | 1104 // through the HashTable. That includes m_head and m_tail so we do not have |
1108 // to explicitly trace them here. | 1105 // to explicitly trace them here. |
1109 m_impl.trace(visitor); | 1106 m_impl.trace(visitor); |
1110 } | 1107 } |
1111 | 1108 |
1112 } // namespace WTF | 1109 } // namespace WTF |
1113 | 1110 |
1114 using WTF::ListHashSet; | 1111 using WTF::ListHashSet; |
1115 | 1112 |
1116 #endif // WTF_ListHashSet_h | 1113 #endif // WTF_ListHashSet_h |
OLD | NEW |