| /* |
| * Copyright (C) 2013 Apple Inc. All rights reserved. |
| * Copyright (C) 2014 Samsung Electronics. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above |
| * copyright notice, this list of conditions and the following disclaimer |
| * in the documentation and/or other materials provided with the |
| * distribution. |
| * * Neither the name of Google Inc. nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #ifndef THIRD_PARTY_BLINK_RENDERER_CORE_DOM_COLLECTION_INDEX_CACHE_H_ |
| #define THIRD_PARTY_BLINK_RENDERER_CORE_DOM_COLLECTION_INDEX_CACHE_H_ |
| |
| #include "third_party/blink/renderer/platform/heap/handle.h" |
| |
| namespace blink { |
| |
| template <typename Collection, typename NodeType> |
| class CollectionIndexCache { |
| DISALLOW_NEW(); |
| |
| public: |
| CollectionIndexCache(); |
| |
| bool IsEmpty(const Collection& collection) { |
| if (IsCachedNodeCountValid()) |
| return !CachedNodeCount(); |
| if (CachedNode()) |
| return false; |
| return !NodeAt(collection, 0); |
| } |
| bool HasExactlyOneNode(const Collection& collection) { |
| if (IsCachedNodeCountValid()) |
| return CachedNodeCount() == 1; |
| if (CachedNode()) |
| return !CachedNodeIndex() && !NodeAt(collection, 1); |
| return NodeAt(collection, 0) && !NodeAt(collection, 1); |
| } |
| |
| unsigned NodeCount(const Collection&); |
| NodeType* NodeAt(const Collection&, unsigned index); |
| |
| void Invalidate(); |
| |
| void NodeInserted(); |
| void NodeRemoved(); |
| |
| virtual void Trace(Visitor* visitor) { visitor->Trace(current_node_); } |
| |
| protected: |
| ALWAYS_INLINE NodeType* CachedNode() const { return current_node_; } |
| ALWAYS_INLINE unsigned CachedNodeIndex() const { |
| DCHECK(CachedNode()); |
| return cached_node_index_; |
| } |
| ALWAYS_INLINE void SetCachedNode(NodeType* node, unsigned index) { |
| DCHECK(node); |
| current_node_ = node; |
| cached_node_index_ = index; |
| } |
| |
| ALWAYS_INLINE bool IsCachedNodeCountValid() const { |
| return is_length_cache_valid_; |
| } |
| ALWAYS_INLINE unsigned CachedNodeCount() const { return cached_node_count_; } |
| ALWAYS_INLINE void SetCachedNodeCount(unsigned length) { |
| cached_node_count_ = length; |
| is_length_cache_valid_ = true; |
| } |
| |
| private: |
| NodeType* NodeBeforeCachedNode(const Collection&, unsigned index); |
| NodeType* NodeAfterCachedNode(const Collection&, unsigned index); |
| |
| Member<NodeType> current_node_; |
| unsigned cached_node_count_; |
| unsigned cached_node_index_ : 31; |
| unsigned is_length_cache_valid_ : 1; |
| }; |
| |
| template <typename Collection, typename NodeType> |
| CollectionIndexCache<Collection, NodeType>::CollectionIndexCache() |
| : current_node_(nullptr), |
| cached_node_count_(0), |
| cached_node_index_(0), |
| is_length_cache_valid_(false) {} |
| |
| template <typename Collection, typename NodeType> |
| void CollectionIndexCache<Collection, NodeType>::Invalidate() { |
| current_node_ = nullptr; |
| is_length_cache_valid_ = false; |
| } |
| |
| template <typename Collection, typename NodeType> |
| void CollectionIndexCache<Collection, NodeType>::NodeInserted() { |
| cached_node_count_++; |
| current_node_ = nullptr; |
| } |
| |
| template <typename Collection, typename NodeType> |
| void CollectionIndexCache<Collection, NodeType>::NodeRemoved() { |
| cached_node_count_--; |
| current_node_ = nullptr; |
| } |
| |
| template <typename Collection, typename NodeType> |
| inline unsigned CollectionIndexCache<Collection, NodeType>::NodeCount( |
| const Collection& collection) { |
| if (IsCachedNodeCountValid()) |
| return CachedNodeCount(); |
| |
| NodeAt(collection, UINT_MAX); |
| DCHECK(IsCachedNodeCountValid()); |
| |
| return CachedNodeCount(); |
| } |
| |
| template <typename Collection, typename NodeType> |
| inline NodeType* CollectionIndexCache<Collection, NodeType>::NodeAt( |
| const Collection& collection, |
| unsigned index) { |
| if (IsCachedNodeCountValid() && index >= CachedNodeCount()) |
| return nullptr; |
| |
| if (CachedNode()) { |
| if (index > CachedNodeIndex()) |
| return NodeAfterCachedNode(collection, index); |
| if (index < CachedNodeIndex()) |
| return NodeBeforeCachedNode(collection, index); |
| return CachedNode(); |
| } |
| |
| // No valid cache yet, let's find the first matching element. |
| NodeType* first_node = collection.TraverseToFirst(); |
| if (!first_node) { |
| // The collection is empty. |
| SetCachedNodeCount(0); |
| return nullptr; |
| } |
| SetCachedNode(first_node, 0); |
| return index ? NodeAfterCachedNode(collection, index) : first_node; |
| } |
| |
| template <typename Collection, typename NodeType> |
| inline NodeType* |
| CollectionIndexCache<Collection, NodeType>::NodeBeforeCachedNode( |
| const Collection& collection, |
| unsigned index) { |
| DCHECK(CachedNode()); // Cache should be valid. |
| unsigned current_index = CachedNodeIndex(); |
| DCHECK_GT(current_index, index); |
| |
| // Determine if we should traverse from the beginning of the collection |
| // instead of the cached node. |
| bool first_is_closer = index < current_index - index; |
| if (first_is_closer || !collection.CanTraverseBackward()) { |
| NodeType* first_node = collection.TraverseToFirst(); |
| DCHECK(first_node); |
| SetCachedNode(first_node, 0); |
| return index ? NodeAfterCachedNode(collection, index) : first_node; |
| } |
| |
| // Backward traversal from the cached node to the requested index. |
| DCHECK(collection.CanTraverseBackward()); |
| NodeType* current_node = |
| collection.TraverseBackwardToOffset(index, *CachedNode(), current_index); |
| DCHECK(current_node); |
| SetCachedNode(current_node, current_index); |
| return current_node; |
| } |
| |
| template <typename Collection, typename NodeType> |
| inline NodeType* |
| CollectionIndexCache<Collection, NodeType>::NodeAfterCachedNode( |
| const Collection& collection, |
| unsigned index) { |
| DCHECK(CachedNode()); // Cache should be valid. |
| unsigned current_index = CachedNodeIndex(); |
| DCHECK_LT(current_index, index); |
| |
| // Determine if we should traverse from the end of the collection instead of |
| // the cached node. |
| bool last_is_closer = IsCachedNodeCountValid() && |
| CachedNodeCount() - index < index - current_index; |
| if (last_is_closer && collection.CanTraverseBackward()) { |
| NodeType* last_item = collection.TraverseToLast(); |
| DCHECK(last_item); |
| SetCachedNode(last_item, CachedNodeCount() - 1); |
| if (index < CachedNodeCount() - 1) |
| return NodeBeforeCachedNode(collection, index); |
| return last_item; |
| } |
| |
| // Forward traversal from the cached node to the requested index. |
| NodeType* current_node = |
| collection.TraverseForwardToOffset(index, *CachedNode(), current_index); |
| if (!current_node) { |
| // Did not find the node. On plus side, we now know the length. |
| if (IsCachedNodeCountValid()) |
| DCHECK_EQ(current_index + 1, CachedNodeCount()); |
| SetCachedNodeCount(current_index + 1); |
| return nullptr; |
| } |
| SetCachedNode(current_node, current_index); |
| return current_node; |
| } |
| |
| } // namespace blink |
| |
| #endif // THIRD_PARTY_BLINK_RENDERER_CORE_DOM_COLLECTION_INDEX_CACHE_H_ |