| 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 394 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 405 return HashFunctions::Equal(a.value_, b.value_); | 405 return HashFunctions::Equal(a.value_, b.value_); |
| 406 } | 406 } |
| 407 template <typename IncomingValueType> | 407 template <typename IncomingValueType> |
| 408 static void Translate(Node& location, | 408 static void Translate(Node& location, |
| 409 IncomingValueType&& key, | 409 IncomingValueType&& key, |
| 410 NodeBase* anchor) { | 410 NodeBase* anchor) { |
| 411 anchor->InsertBefore(location); | 411 anchor->InsertBefore(location); |
| 412 location.value_ = std::forward<IncomingValueType>(key); | 412 location.value_ = std::forward<IncomingValueType>(key); |
| 413 } | 413 } |
| 414 | 414 |
| 415 // Empty (or deleted) slots have the m_next pointer set to null, but we | 415 // Empty (or deleted) slots have the next_ pointer set to null, but we |
| 416 // don't do anything to the other fields, which may contain junk. | 416 // don't do anything to the other fields, which may contain junk. |
| 417 // Therefore you can't compare a newly constructed empty value with a | 417 // Therefore you can't compare a newly constructed empty value with a |
| 418 // slot and get the right answer. | 418 // slot and get the right answer. |
| 419 static const bool safe_to_compare_to_empty_or_deleted = false; | 419 static const bool safe_to_compare_to_empty_or_deleted = false; |
| 420 }; | 420 }; |
| 421 | 421 |
| 422 template <typename Value, typename Allocator> | 422 template <typename Value, typename Allocator> |
| 423 struct LinkedHashSetExtractor { | 423 struct LinkedHashSetExtractor { |
| 424 STATIC_ONLY(LinkedHashSetExtractor); | 424 STATIC_ONLY(LinkedHashSetExtractor); |
| 425 static const Value& Extract(const LinkedHashSetNode<Value, Allocator>& node) { | 425 static const Value& Extract(const LinkedHashSetNode<Value, Allocator>& node) { |
| 426 return node.value_; | 426 return node.value_; |
| 427 } | 427 } |
| 428 }; | 428 }; |
| 429 | 429 |
| 430 template <typename Value, typename ValueTraitsArg, typename Allocator> | 430 template <typename Value, typename ValueTraitsArg, typename Allocator> |
| 431 struct LinkedHashSetTraits | 431 struct LinkedHashSetTraits |
| 432 : public SimpleClassHashTraits<LinkedHashSetNode<Value, Allocator>> { | 432 : public SimpleClassHashTraits<LinkedHashSetNode<Value, Allocator>> { |
| 433 STATIC_ONLY(LinkedHashSetTraits); | 433 STATIC_ONLY(LinkedHashSetTraits); |
| 434 typedef LinkedHashSetNode<Value, Allocator> Node; | 434 typedef LinkedHashSetNode<Value, Allocator> Node; |
| 435 typedef ValueTraitsArg ValueTraits; | 435 typedef ValueTraitsArg ValueTraits; |
| 436 | 436 |
| 437 // The slot is empty when the m_next field is zero so it's safe to zero | 437 // The slot is empty when the next_ field is zero so it's safe to zero |
| 438 // the backing. | 438 // the backing. |
| 439 static const bool kEmptyValueIsZero = true; | 439 static const bool kEmptyValueIsZero = true; |
| 440 | 440 |
| 441 static const bool kHasIsEmptyValueFunction = true; | 441 static const bool kHasIsEmptyValueFunction = true; |
| 442 static bool IsEmptyValue(const Node& node) { return !node.next_; } | 442 static bool IsEmptyValue(const Node& node) { return !node.next_; } |
| 443 | 443 |
| 444 static const int kDeletedValue = -1; | 444 static const int kDeletedValue = -1; |
| 445 | 445 |
| 446 static void ConstructDeletedValue(Node& slot, bool) { | 446 static void ConstructDeletedValue(Node& slot, bool) { |
| 447 slot.next_ = reinterpret_cast<Node*>(kDeletedValue); | 447 slot.next_ = reinterpret_cast<Node*>(kDeletedValue); |
| (...skipping 238 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 686 } | 686 } |
| 687 | 687 |
| 688 template <typename T, typename U, typename V, typename W> | 688 template <typename T, typename U, typename V, typename W> |
| 689 inline void LinkedHashSet<T, U, V, W>::Swap(LinkedHashSet& other) { | 689 inline void LinkedHashSet<T, U, V, W>::Swap(LinkedHashSet& other) { |
| 690 impl_.swap(other.impl_); | 690 impl_.swap(other.impl_); |
| 691 SwapAnchor(anchor_, other.anchor_); | 691 SwapAnchor(anchor_, other.anchor_); |
| 692 } | 692 } |
| 693 | 693 |
| 694 template <typename T, typename U, typename V, typename Allocator> | 694 template <typename T, typename U, typename V, typename Allocator> |
| 695 inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet() { | 695 inline LinkedHashSet<T, U, V, Allocator>::~LinkedHashSet() { |
| 696 // The destructor of m_anchor will implicitly be called here, which will | 696 // The destructor of anchor_ will implicitly be called here, which will |
| 697 // unlink the anchor from the collection. | 697 // unlink the anchor from the collection. |
| 698 } | 698 } |
| 699 | 699 |
| 700 template <typename T, typename U, typename V, typename W> | 700 template <typename T, typename U, typename V, typename W> |
| 701 inline T& LinkedHashSet<T, U, V, W>::front() { | 701 inline T& LinkedHashSet<T, U, V, W>::front() { |
| 702 DCHECK(!IsEmpty()); | 702 DCHECK(!IsEmpty()); |
| 703 return FirstNode()->value_; | 703 return FirstNode()->value_; |
| 704 } | 704 } |
| 705 | 705 |
| 706 template <typename T, typename U, typename V, typename W> | 706 template <typename T, typename U, typename V, typename W> |
| 707 inline const T& LinkedHashSet<T, U, V, W>::front() const { | 707 inline const T& LinkedHashSet<T, U, V, W>::front() const { |
| 708 DCHECK(!IsEmpty()); | 708 DCHECK(!IsEmpty()); |
| 709 return FirstNode()->m_value; | 709 return FirstNode()->value_; |
| 710 } | 710 } |
| 711 | 711 |
| 712 template <typename T, typename U, typename V, typename W> | 712 template <typename T, typename U, typename V, typename W> |
| 713 inline void LinkedHashSet<T, U, V, W>::RemoveFirst() { | 713 inline void LinkedHashSet<T, U, V, W>::RemoveFirst() { |
| 714 DCHECK(!IsEmpty()); | 714 DCHECK(!IsEmpty()); |
| 715 impl_.erase(static_cast<Node*>(anchor_.next_)); | 715 impl_.erase(static_cast<Node*>(anchor_.next_)); |
| 716 } | 716 } |
| 717 | 717 |
| 718 template <typename T, typename U, typename V, typename W> | 718 template <typename T, typename U, typename V, typename W> |
| 719 inline T& LinkedHashSet<T, U, V, W>::back() { | 719 inline T& LinkedHashSet<T, U, V, W>::back() { |
| 720 DCHECK(!IsEmpty()); | 720 DCHECK(!IsEmpty()); |
| 721 return LastNode()->value_; | 721 return LastNode()->value_; |
| 722 } | 722 } |
| 723 | 723 |
| 724 template <typename T, typename U, typename V, typename W> | 724 template <typename T, typename U, typename V, typename W> |
| 725 inline const T& LinkedHashSet<T, U, V, W>::back() const { | 725 inline const T& LinkedHashSet<T, U, V, W>::back() const { |
| 726 DCHECK(!IsEmpty()); | 726 DCHECK(!IsEmpty()); |
| 727 return LastNode()->m_value; | 727 return LastNode()->value_; |
| 728 } | 728 } |
| 729 | 729 |
| 730 template <typename T, typename U, typename V, typename W> | 730 template <typename T, typename U, typename V, typename W> |
| 731 inline void LinkedHashSet<T, U, V, W>::pop_back() { | 731 inline void LinkedHashSet<T, U, V, W>::pop_back() { |
| 732 DCHECK(!IsEmpty()); | 732 DCHECK(!IsEmpty()); |
| 733 impl_.erase(static_cast<Node*>(anchor_.prev_)); | 733 impl_.erase(static_cast<Node*>(anchor_.prev_)); |
| 734 } | 734 } |
| 735 | 735 |
| 736 template <typename T, typename U, typename V, typename W> | 736 template <typename T, typename U, typename V, typename W> |
| 737 inline typename LinkedHashSet<T, U, V, W>::iterator | 737 inline typename LinkedHashSet<T, U, V, W>::iterator |
| (...skipping 192 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 930 swap(static_cast<Base&>(a), static_cast<Base&>(b)); | 930 swap(static_cast<Base&>(a), static_cast<Base&>(b)); |
| 931 swap(a.value_, b.value_); | 931 swap(a.value_, b.value_); |
| 932 Allocator::LeaveGCForbiddenScope(); | 932 Allocator::LeaveGCForbiddenScope(); |
| 933 } | 933 } |
| 934 | 934 |
| 935 } // namespace WTF | 935 } // namespace WTF |
| 936 | 936 |
| 937 using WTF::LinkedHashSet; | 937 using WTF::LinkedHashSet; |
| 938 | 938 |
| 939 #endif /* WTF_LinkedHashSet_h */ | 939 #endif /* WTF_LinkedHashSet_h */ |
| OLD | NEW |