1/*
2 * Copyright (C) 2015 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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "IndexValueStore.h"
28
29#if ENABLE(INDEXED_DATABASE)
30
31#include "IDBError.h"
32#include "IDBKeyRangeData.h"
33#include "Logging.h"
34#include "MemoryIndex.h"
35#include <wtf/text/StringBuilder.h>
36
37namespace WebCore {
38namespace IDBServer {
39
40IndexValueStore::IndexValueStore(bool unique)
41 : m_unique(unique)
42{
43}
44
45const IDBKeyData* IndexValueStore::lowestValueForKey(const IDBKeyData& key) const
46{
47 const auto& entry = m_records.get(key);
48 if (!entry)
49 return nullptr;
50
51 return entry->getLowest();
52}
53
54Vector<IDBKeyData> IndexValueStore::allValuesForKey(const IDBKeyData& key, uint32_t limit) const
55{
56 const auto& entry = m_records.get(key);
57 if (!entry)
58 return { };
59
60 Vector<IDBKeyData> results;
61 for (auto iterator = entry->begin(); results.size() < limit && iterator.isValid(); ++iterator)
62 results.append(iterator.key());
63
64 return results;
65}
66
67uint64_t IndexValueStore::countForKey(const IDBKeyData& key) const
68{
69 const auto& entry = m_records.get(key);
70 if (!entry)
71 return 0;
72
73 return entry->getCount();
74}
75
76bool IndexValueStore::contains(const IDBKeyData& key) const
77{
78 const auto& entry = m_records.get(key);
79 if (!entry)
80 return false;
81
82 ASSERT(entry->getCount());
83
84 return true;
85}
86
87IDBError IndexValueStore::addRecord(const IDBKeyData& indexKey, const IDBKeyData& valueKey)
88{
89 auto result = m_records.add(indexKey, nullptr);
90
91 if (!result.isNewEntry && m_unique)
92 return IDBError(ConstraintError);
93
94 if (result.isNewEntry)
95 result.iterator->value = std::make_unique<IndexValueEntry>(m_unique);
96
97 result.iterator->value->addKey(valueKey);
98 m_orderedKeys.insert(indexKey);
99
100 return IDBError { };
101}
102
103void IndexValueStore::removeRecord(const IDBKeyData& indexKey, const IDBKeyData& valueKey)
104{
105 auto iterator = m_records.find(indexKey);
106 if (!iterator->value)
107 return;
108
109 if (iterator->value->removeKey(valueKey))
110 m_records.remove(iterator);
111}
112
113void IndexValueStore::removeEntriesWithValueKey(MemoryIndex& index, const IDBKeyData& valueKey)
114{
115 Vector<IDBKeyData> entryKeysToRemove;
116 entryKeysToRemove.reserveInitialCapacity(m_records.size());
117
118 for (auto& entry : m_records) {
119 if (entry.value->removeKey(valueKey))
120 index.notifyCursorsOfValueChange(entry.key, valueKey);
121 if (!entry.value->getCount())
122 entryKeysToRemove.uncheckedAppend(entry.key);
123 }
124
125 for (auto& entry : entryKeysToRemove) {
126 m_orderedKeys.erase(entry);
127 m_records.remove(entry);
128 }
129}
130
131IDBKeyData IndexValueStore::lowestKeyWithRecordInRange(const IDBKeyRangeData& range) const
132{
133 LOG(IndexedDB, "IndexValueStore::lowestKeyWithRecordInRange - %s", range.loggingString().utf8().data());
134
135 if (range.isExactlyOneKey())
136 return m_records.contains(range.lowerKey) ? range.lowerKey : IDBKeyData();
137
138 auto iterator = lowestIteratorInRange(range);
139 if (iterator == m_orderedKeys.end())
140 return { };
141
142 return *iterator;
143}
144
145IDBKeyDataSet::iterator IndexValueStore::lowestIteratorInRange(const IDBKeyRangeData& range) const
146{
147 auto lowestInRange = m_orderedKeys.lower_bound(range.lowerKey);
148
149 if (lowestInRange == m_orderedKeys.end())
150 return lowestInRange;
151
152 if (range.lowerOpen && *lowestInRange == range.lowerKey) {
153 ++lowestInRange;
154
155 if (lowestInRange == m_orderedKeys.end())
156 return lowestInRange;
157 }
158
159 if (!range.upperKey.isNull()) {
160 if (lowestInRange->compare(range.upperKey) > 0)
161 return m_orderedKeys.end();
162 if (range.upperOpen && *lowestInRange == range.upperKey)
163 return m_orderedKeys.end();
164 }
165
166 return lowestInRange;
167}
168
169IDBKeyDataSet::reverse_iterator IndexValueStore::highestReverseIteratorInRange(const IDBKeyRangeData& range) const
170{
171 auto highestInRange = IDBKeyDataSet::reverse_iterator(m_orderedKeys.upper_bound(range.upperKey));
172
173 if (highestInRange == m_orderedKeys.rend())
174 return highestInRange;
175
176 if (range.upperOpen && *highestInRange == range.upperKey) {
177 ++highestInRange;
178
179 if (highestInRange == m_orderedKeys.rend())
180 return highestInRange;
181 }
182
183 if (!range.lowerKey.isNull()) {
184 if (highestInRange->compare(range.lowerKey) < 0)
185 return m_orderedKeys.rend();
186 if (range.lowerOpen && *highestInRange == range.lowerKey)
187 return m_orderedKeys.rend();
188 }
189
190 return highestInRange;
191}
192
193IndexValueStore::Iterator IndexValueStore::find(const IDBKeyData& key, bool open)
194{
195 IDBKeyRangeData range;
196 if (!key.isNull())
197 range.lowerKey = key;
198 else
199 range.lowerKey = IDBKeyData::minimum();
200 range.lowerOpen = open;
201
202 auto iterator = lowestIteratorInRange(range);
203 if (iterator == m_orderedKeys.end())
204 return { };
205
206 auto record = m_records.get(*iterator);
207 ASSERT(record);
208
209 auto primaryIterator = record->begin();
210 ASSERT(primaryIterator.isValid());
211 return { *this, iterator, primaryIterator };
212}
213
214IndexValueStore::Iterator IndexValueStore::find(const IDBKeyData& key, const IDBKeyData& primaryKey)
215{
216 ASSERT(!key.isNull());
217 ASSERT(!primaryKey.isNull());
218
219 IDBKeyRangeData range;
220 range.lowerKey = key;
221 range.lowerOpen = false;
222
223 auto iterator = lowestIteratorInRange(range);
224 if (iterator == m_orderedKeys.end())
225 return { };
226
227 auto record = m_records.get(*iterator);
228 ASSERT(record);
229
230 // If the main record iterator is not equal to the key we were looking for,
231 // we know the primary key record should be the first.
232 if (*iterator != key) {
233 auto primaryIterator = record->begin();
234 ASSERT(primaryIterator.isValid());
235
236 return { *this, iterator, primaryIterator };
237 }
238
239 auto primaryIterator = record->find(primaryKey);
240 if (primaryIterator.isValid())
241 return { *this, iterator, primaryIterator };
242
243 // If we didn't find a primary key iterator in this entry,
244 // we need to move on to start of the next record.
245 iterator++;
246 if (iterator == m_orderedKeys.end())
247 return { };
248
249 record = m_records.get(*iterator);
250 ASSERT(record);
251
252 primaryIterator = record->begin();
253 ASSERT(primaryIterator.isValid());
254
255 return { *this, iterator, primaryIterator };
256}
257
258IndexValueStore::Iterator IndexValueStore::reverseFind(const IDBKeyData& key, CursorDuplicity duplicity, bool open)
259{
260 IDBKeyRangeData range;
261 if (!key.isNull())
262 range.upperKey = key;
263 else
264 range.upperKey = IDBKeyData::maximum();
265 range.upperOpen = open;
266
267 auto iterator = highestReverseIteratorInRange(range);
268 if (iterator == m_orderedKeys.rend())
269 return { };
270
271 auto record = m_records.get(*iterator);
272 ASSERT(record);
273
274 auto primaryIterator = record->reverseBegin(duplicity);
275 ASSERT(primaryIterator.isValid());
276 return { *this, duplicity, iterator, primaryIterator };
277}
278
279IndexValueStore::Iterator IndexValueStore::reverseFind(const IDBKeyData& key, const IDBKeyData& primaryKey, CursorDuplicity duplicity)
280{
281 ASSERT(!key.isNull());
282 ASSERT(!primaryKey.isNull());
283
284 IDBKeyRangeData range;
285 range.upperKey = key;
286 range.upperOpen = false;
287
288 auto iterator = highestReverseIteratorInRange(range);
289 if (iterator == m_orderedKeys.rend())
290 return { };
291
292 auto record = m_records.get(*iterator);
293 ASSERT(record);
294
295 auto primaryIterator = record->reverseFind(primaryKey, duplicity);
296 if (primaryIterator.isValid())
297 return { *this, duplicity, iterator, primaryIterator };
298
299 // If we didn't find a primary key iterator in this entry,
300 // we need to move on to start of the next record.
301 iterator++;
302 if (iterator == m_orderedKeys.rend())
303 return { };
304
305 record = m_records.get(*iterator);
306 ASSERT(record);
307
308 primaryIterator = record->reverseBegin(duplicity);
309 ASSERT(primaryIterator.isValid());
310
311 return { *this, duplicity, iterator, primaryIterator };
312}
313
314
315IndexValueStore::Iterator::Iterator(IndexValueStore& store, IDBKeyDataSet::iterator iterator, IndexValueEntry::Iterator primaryIterator)
316 : m_store(&store)
317 , m_forwardIterator(iterator)
318 , m_primaryKeyIterator(primaryIterator)
319{
320}
321
322IndexValueStore::Iterator::Iterator(IndexValueStore& store, CursorDuplicity duplicity, IDBKeyDataSet::reverse_iterator iterator, IndexValueEntry::Iterator primaryIterator)
323 : m_store(&store)
324 , m_forward(false)
325 , m_duplicity(duplicity)
326 , m_reverseIterator(iterator)
327 , m_primaryKeyIterator(primaryIterator)
328{
329}
330
331IndexValueStore::Iterator& IndexValueStore::Iterator::nextIndexEntry()
332{
333 if (!m_store)
334 return *this;
335
336 if (m_forward) {
337 ++m_forwardIterator;
338 if (m_forwardIterator == m_store->m_orderedKeys.end()) {
339 invalidate();
340 return *this;
341 }
342
343 auto* entry = m_store->m_records.get(*m_forwardIterator);
344 ASSERT(entry);
345
346 m_primaryKeyIterator = entry->begin();
347 ASSERT(m_primaryKeyIterator.isValid());
348 } else {
349 ++m_reverseIterator;
350 if (m_reverseIterator == m_store->m_orderedKeys.rend()) {
351 invalidate();
352 return *this;
353 }
354
355 auto* entry = m_store->m_records.get(*m_reverseIterator);
356 ASSERT(entry);
357
358 m_primaryKeyIterator = entry->reverseBegin(m_duplicity);
359 ASSERT(m_primaryKeyIterator.isValid());
360 }
361
362 return *this;
363}
364
365IndexValueStore::Iterator& IndexValueStore::Iterator::operator++()
366{
367 if (!isValid())
368 return *this;
369
370 ++m_primaryKeyIterator;
371 if (m_primaryKeyIterator.isValid())
372 return *this;
373
374 // Ran out of primary key records, so move the main index iterator.
375 return nextIndexEntry();
376}
377
378void IndexValueStore::Iterator::invalidate()
379{
380 m_store = nullptr;
381 m_primaryKeyIterator.invalidate();
382}
383
384bool IndexValueStore::Iterator::isValid()
385{
386 return m_store && m_primaryKeyIterator.isValid();
387}
388
389const IDBKeyData& IndexValueStore::Iterator::key()
390{
391 ASSERT(isValid());
392 return m_forward ? *m_forwardIterator : *m_reverseIterator;
393}
394
395const IDBKeyData& IndexValueStore::Iterator::primaryKey()
396{
397 ASSERT(isValid());
398 return m_primaryKeyIterator.key();
399}
400
401#if !LOG_DISABLED
402String IndexValueStore::loggingString() const
403{
404 StringBuilder builder;
405 for (auto& key : m_orderedKeys) {
406 builder.appendLiteral("Key: ");
407 builder.append(key.loggingString());
408 builder.appendLiteral(" Entry has ");
409 builder.appendNumber(m_records.get(key)->getCount());
410 builder.appendLiteral(" entries");
411 }
412 return builder.toString();
413}
414#endif
415
416} // namespace IDBServer
417} // namespace WebCore
418
419#endif // ENABLE(INDEXED_DATABASE)
420