1/* 2 * Copyright (C) 2013, 2014 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' 14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS 17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 23 * THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#ifndef CollectionIndexCache_h 27#define CollectionIndexCache_h 28 29#include <wtf/Vector.h> 30 31namespace WebCore { 32 33void reportExtraMemoryCostForCollectionIndexCache(size_t); 34 35template <class Collection, class Iterator> 36class CollectionIndexCache { 37public: 38 explicit CollectionIndexCache(const Collection&); 39 40 typedef typename std::iterator_traits<Iterator>::value_type NodeType; 41 42 unsigned nodeCount(const Collection&); 43 NodeType* nodeAt(const Collection&, unsigned index); 44 45 bool hasValidCache(const Collection& collection) const { return m_current != collection.collectionEnd() || m_nodeCountValid || m_listValid; } 46 void invalidate(const Collection&); 47 size_t memoryCost() { return m_cachedList.capacity() * sizeof(NodeType*); } 48 49private: 50 unsigned computeNodeCountUpdatingListCache(const Collection&); 51 NodeType* traverseBackwardTo(const Collection&, unsigned); 52 NodeType* traverseForwardTo(const Collection&, unsigned); 53 54 Iterator m_current; 55 unsigned m_currentIndex; 56 unsigned m_nodeCount; 57 Vector<NodeType*> m_cachedList; 58 bool m_nodeCountValid : 1; 59 bool m_listValid : 1; 60}; 61 62template <class Collection, class Iterator> 63inline CollectionIndexCache<Collection, Iterator>::CollectionIndexCache(const Collection& collection) 64 : m_current(collection.collectionEnd()) 65 , m_currentIndex(0) 66 , m_nodeCount(0) 67 , m_nodeCountValid(false) 68 , m_listValid(false) 69{ 70} 71 72template <class Collection, class Iterator> 73inline unsigned CollectionIndexCache<Collection, Iterator>::nodeCount(const Collection& collection) 74{ 75 if (!m_nodeCountValid) { 76 if (!hasValidCache(collection)) 77 collection.willValidateIndexCache(); 78 m_nodeCount = computeNodeCountUpdatingListCache(collection); 79 m_nodeCountValid = true; 80 } 81 82 return m_nodeCount; 83} 84 85template <class Collection, class Iterator> 86unsigned CollectionIndexCache<Collection, Iterator>::computeNodeCountUpdatingListCache(const Collection& collection) 87{ 88 auto current = collection.collectionBegin(); 89 auto end = collection.collectionEnd(); 90 if (current == end) 91 return 0; 92 93 unsigned oldCapacity = m_cachedList.capacity(); 94 while (current != end) { 95 m_cachedList.append(&*current); 96 unsigned traversed; 97 collection.collectionTraverseForward(current, 1, traversed); 98 ASSERT(traversed == (current != end ? 1 : 0)); 99 } 100 m_listValid = true; 101 102 if (unsigned capacityDifference = m_cachedList.capacity() - oldCapacity) 103 reportExtraMemoryCostForCollectionIndexCache(capacityDifference * sizeof(NodeType*)); 104 105 return m_cachedList.size(); 106} 107 108template <class Collection, class Iterator> 109inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseBackwardTo(const Collection& collection, unsigned index) 110{ 111 ASSERT(m_current != collection.collectionEnd()); 112 ASSERT(index < m_currentIndex); 113 114 bool firstIsCloser = index < m_currentIndex - index; 115 if (firstIsCloser || !collection.collectionCanTraverseBackward()) { 116 m_current = collection.collectionBegin(); 117 m_currentIndex = 0; 118 if (index) 119 collection.collectionTraverseForward(m_current, index, m_currentIndex); 120 ASSERT(m_current != collection.collectionEnd()); 121 return &*m_current; 122 } 123 124 collection.collectionTraverseBackward(m_current, m_currentIndex - index); 125 m_currentIndex = index; 126 127 ASSERT(m_current != collection.collectionEnd()); 128 return &*m_current; 129} 130 131template <class Collection, class Iterator> 132inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::traverseForwardTo(const Collection& collection, unsigned index) 133{ 134 ASSERT(m_current != collection.collectionEnd()); 135 ASSERT(index > m_currentIndex); 136 ASSERT(!m_nodeCountValid || index < m_nodeCount); 137 138 bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index - m_currentIndex; 139 if (lastIsCloser && collection.collectionCanTraverseBackward()) { 140 ASSERT(hasValidCache(collection)); 141 m_current = collection.collectionLast(); 142 if (index < m_nodeCount - 1) 143 collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1); 144 m_currentIndex = index; 145 ASSERT(m_current != collection.collectionEnd()); 146 return &*m_current; 147 } 148 149 if (!hasValidCache(collection)) 150 collection.willValidateIndexCache(); 151 152 unsigned traversedCount; 153 collection.collectionTraverseForward(m_current, index - m_currentIndex, traversedCount); 154 m_currentIndex = m_currentIndex + traversedCount; 155 156 if (m_current == collection.collectionEnd()) { 157 ASSERT(m_currentIndex < index); 158 // Failed to find the index but at least we now know the size. 159 m_nodeCount = m_currentIndex + 1; 160 m_nodeCountValid = true; 161 return nullptr; 162 } 163 ASSERT(hasValidCache(collection)); 164 return &*m_current; 165} 166 167template <class Collection, class Iterator> 168inline typename CollectionIndexCache<Collection, Iterator>::NodeType* CollectionIndexCache<Collection, Iterator>::nodeAt(const Collection& collection, unsigned index) 169{ 170 if (m_nodeCountValid && index >= m_nodeCount) 171 return nullptr; 172 173 if (m_listValid) 174 return m_cachedList[index]; 175 176 auto end = collection.collectionEnd(); 177 if (m_current != end) { 178 if (index > m_currentIndex) 179 return traverseForwardTo(collection, index); 180 if (index < m_currentIndex) 181 return traverseBackwardTo(collection, index); 182 return &*m_current; 183 } 184 185 bool lastIsCloser = m_nodeCountValid && m_nodeCount - index < index; 186 if (lastIsCloser && collection.collectionCanTraverseBackward()) { 187 ASSERT(hasValidCache(collection)); 188 m_current = collection.collectionLast(); 189 if (index < m_nodeCount - 1) 190 collection.collectionTraverseBackward(m_current, m_nodeCount - index - 1); 191 m_currentIndex = index; 192 ASSERT(m_current != end); 193 return &*m_current; 194 } 195 196 if (!hasValidCache(collection)) 197 collection.willValidateIndexCache(); 198 199 m_current = collection.collectionBegin(); 200 m_currentIndex = 0; 201 if (index && m_current != end) { 202 collection.collectionTraverseForward(m_current, index, m_currentIndex); 203 ASSERT(m_current != end || m_currentIndex < index); 204 } 205 if (m_current == end) { 206 // Failed to find the index but at least we now know the size. 207 m_nodeCount = m_currentIndex + 1; 208 m_nodeCountValid = true; 209 return nullptr; 210 } 211 ASSERT(hasValidCache(collection)); 212 return &*m_current; 213} 214 215template <class Collection, class Iterator> 216void CollectionIndexCache<Collection, Iterator>::invalidate(const Collection& collection) 217{ 218 m_current = collection.collectionEnd(); 219 m_nodeCountValid = false; 220 m_listValid = false; 221 m_cachedList.shrink(0); 222} 223 224 225} 226 227#endif 228