1/*
2 * Copyright (C) 2011 Google 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 *
8 * 1.  Redistributions of source code must retain the above copyright
9 *     notice, this list of conditions and the following disclaimer.
10 * 2.  Redistributions in binary form must reproduce the above copyright
11 *     notice, this list of conditions and the following disclaimer in the
12 *     documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "LevelDBTransaction.h"
28
29#if ENABLE(INDEXED_DATABASE)
30#if USE(LEVELDB)
31
32#include "LevelDBDatabase.h"
33#include "LevelDBSlice.h"
34#include "LevelDBWriteBatch.h"
35#include <leveldb/db.h>
36
37namespace WebCore {
38
39PassRefPtr<LevelDBTransaction> LevelDBTransaction::create(LevelDBDatabase* db)
40{
41    return adoptRef(new LevelDBTransaction(db));
42}
43
44LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
45    : m_db(db)
46    , m_snapshot(db)
47    , m_comparator(db->comparator())
48    , m_finished(false)
49{
50    m_tree.abstractor().m_comparator = m_comparator;
51}
52
53void LevelDBTransaction::clearTree()
54{
55    TreeType::Iterator iterator;
56    iterator.start_iter_least(m_tree);
57
58    Vector<AVLTreeNode*> nodes;
59
60    while (*iterator) {
61        nodes.append(*iterator);
62        ++iterator;
63    }
64    m_tree.purge();
65
66    for (size_t i = 0; i < nodes.size(); ++i)
67        delete(nodes[i]);
68}
69
70LevelDBTransaction::~LevelDBTransaction()
71{
72    clearTree();
73}
74
75static void initVector(const LevelDBSlice& slice, Vector<char>* vector)
76{
77    vector->clear();
78    vector->append(slice.begin(), slice.end() - slice.begin());
79}
80
81void LevelDBTransaction::set(const LevelDBSlice& key, const Vector<char>& value, bool deleted)
82{
83    ASSERT(!m_finished);
84    bool newNode = false;
85    AVLTreeNode* node = m_tree.search(key);
86
87    if (!node) {
88        node = new AVLTreeNode;
89        initVector(key, &node->key);
90        m_tree.insert(node);
91        newNode = true;
92    }
93    node->value = value;
94    node->deleted = deleted;
95
96    if (newNode)
97        notifyIteratorsOfTreeChange();
98}
99
100void LevelDBTransaction::put(const LevelDBSlice& key, const Vector<char>& value)
101{
102    set(key, value, false);
103}
104
105void LevelDBTransaction::remove(const LevelDBSlice& key)
106{
107    set(key, Vector<char>(), true);
108}
109
110bool LevelDBTransaction::safeGet(const LevelDBSlice& key, Vector<char>& value, bool& found)
111{
112    found = false;
113    ASSERT(!m_finished);
114    AVLTreeNode* node = m_tree.search(key);
115
116    if (node) {
117        if (node->deleted)
118            return true;
119
120        value = node->value;
121        found = true;
122        return true;
123    }
124
125    bool ok = m_db->safeGet(key, value, found, &m_snapshot);
126    if (!ok) {
127        ASSERT(!found);
128        return false;
129    }
130    return true;
131}
132
133bool LevelDBTransaction::commit()
134{
135    ASSERT(!m_finished);
136
137    if (m_tree.is_empty()) {
138        m_finished = true;
139        return true;
140    }
141
142    std::unique_ptr<LevelDBWriteBatch> writeBatch = std::make_unique<LevelDBWriteBatch>();
143
144    TreeType::Iterator iterator;
145    iterator.start_iter_least(m_tree);
146
147    while (*iterator) {
148        AVLTreeNode* node = *iterator;
149        if (!node->deleted)
150            writeBatch->put(node->key, node->value);
151        else
152            writeBatch->remove(node->key);
153        ++iterator;
154    }
155
156    if (!m_db->write(*writeBatch))
157        return false;
158
159    clearTree();
160    m_finished = true;
161    return true;
162}
163
164void LevelDBTransaction::rollback()
165{
166    ASSERT(!m_finished);
167    m_finished = true;
168    clearTree();
169}
170
171std::unique_ptr<LevelDBIterator> LevelDBTransaction::createIterator()
172{
173    return std::make_unique<TransactionIterator>(this);
174}
175
176bool LevelDBTransaction::TreeIterator::isValid() const
177{
178    return *m_iterator;
179}
180
181void LevelDBTransaction::TreeIterator::seekToLast()
182{
183    m_iterator.start_iter_greatest(*m_tree);
184    if (isValid())
185        m_key = (*m_iterator)->key;
186}
187
188void LevelDBTransaction::TreeIterator::seek(const LevelDBSlice& target)
189{
190    m_iterator.start_iter(*m_tree, target, TreeType::EQUAL);
191    if (!isValid())
192        m_iterator.start_iter(*m_tree, target, TreeType::GREATER);
193
194    if (isValid())
195        m_key = (*m_iterator)->key;
196}
197
198void LevelDBTransaction::TreeIterator::next()
199{
200    ASSERT(isValid());
201    ++m_iterator;
202    if (isValid()) {
203        ASSERT(m_transaction->m_comparator->compare((*m_iterator)->key, m_key) > 0);
204        (void)m_transaction;
205        m_key = (*m_iterator)->key;
206    }
207}
208
209void LevelDBTransaction::TreeIterator::prev()
210{
211    ASSERT(isValid());
212    --m_iterator;
213    if (isValid()) {
214        ASSERT(m_tree->abstractor().m_comparator->compare((*m_iterator)->key, m_key) < 0);
215        m_key = (*m_iterator)->key;
216    }
217}
218
219LevelDBSlice LevelDBTransaction::TreeIterator::key() const
220{
221    ASSERT(isValid());
222    return m_key;
223}
224
225LevelDBSlice LevelDBTransaction::TreeIterator::value() const
226{
227    ASSERT(isValid());
228    ASSERT(!isDeleted());
229    return (*m_iterator)->value;
230}
231
232bool LevelDBTransaction::TreeIterator::isDeleted() const
233{
234    ASSERT(isValid());
235    return (*m_iterator)->deleted;
236}
237
238void LevelDBTransaction::TreeIterator::reset()
239{
240    ASSERT(isValid());
241    m_iterator.start_iter(*m_tree, m_key, TreeType::EQUAL);
242    ASSERT(isValid());
243}
244
245LevelDBTransaction::TreeIterator::~TreeIterator()
246{
247}
248
249LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction)
250    : m_tree(&transaction->m_tree)
251    , m_transaction(transaction)
252{
253}
254
255LevelDBTransaction::TransactionIterator::TransactionIterator(PassRefPtr<LevelDBTransaction> transaction)
256    : m_transaction(transaction)
257    , m_comparator(m_transaction->m_comparator)
258    , m_treeIterator(std::make_unique<TreeIterator>((m_transaction.get())))
259    , m_dbIterator(m_transaction->m_db->createIterator(&m_transaction->m_snapshot))
260    , m_current(0)
261    , m_direction(kForward)
262    , m_treeChanged(false)
263{
264    m_transaction->registerIterator(this);
265}
266
267LevelDBTransaction::TransactionIterator::~TransactionIterator()
268{
269    m_transaction->unregisterIterator(this);
270}
271
272bool LevelDBTransaction::TransactionIterator::isValid() const
273{
274    return m_current;
275}
276
277void LevelDBTransaction::TransactionIterator::seekToLast()
278{
279    m_treeIterator->seekToLast();
280    m_dbIterator->seekToLast();
281    m_direction = kReverse;
282
283    handleConflictsAndDeletes();
284    setCurrentIteratorToLargestKey();
285}
286
287void LevelDBTransaction::TransactionIterator::seek(const LevelDBSlice& target)
288{
289    m_treeIterator->seek(target);
290    m_dbIterator->seek(target);
291    m_direction = kForward;
292
293    handleConflictsAndDeletes();
294    setCurrentIteratorToSmallestKey();
295}
296
297void LevelDBTransaction::TransactionIterator::next()
298{
299    ASSERT(isValid());
300    if (m_treeChanged)
301        refreshTreeIterator();
302
303    if (m_direction != kForward) {
304        // Ensure the non-current iterator is positioned after key().
305
306        LevelDBIterator* nonCurrent = (m_current == m_dbIterator.get()) ? m_treeIterator.get() : m_dbIterator.get();
307
308        nonCurrent->seek(key());
309        if (nonCurrent->isValid() && !m_comparator->compare(nonCurrent->key(), key()))
310            nonCurrent->next(); // Take an extra step so the non-current key is strictly greater than key().
311
312        ASSERT(!nonCurrent->isValid() || m_comparator->compare(nonCurrent->key(), key()) > 0);
313
314        m_direction = kForward;
315    }
316
317    m_current->next();
318    handleConflictsAndDeletes();
319    setCurrentIteratorToSmallestKey();
320}
321
322void LevelDBTransaction::TransactionIterator::prev()
323{
324    ASSERT(isValid());
325    if (m_treeChanged)
326        refreshTreeIterator();
327
328    if (m_direction != kReverse) {
329        // Ensure the non-current iterator is positioned before key().
330
331        LevelDBIterator* nonCurrent = (m_current == m_dbIterator.get()) ? m_treeIterator.get() : m_dbIterator.get();
332
333        nonCurrent->seek(key());
334        if (nonCurrent->isValid()) {
335            // Iterator is at first entry >= key().
336            // Step back once to entry < key.
337            // This is why we don't check for the keys being the same before
338            // stepping, like we do in next() above.
339            nonCurrent->prev();
340        } else
341            nonCurrent->seekToLast(); // Iterator has no entries >= key(). Position at last entry.
342
343        ASSERT(!nonCurrent->isValid() || m_comparator->compare(nonCurrent->key(), key()) < 0);
344
345        m_direction = kReverse;
346    }
347
348    m_current->prev();
349    handleConflictsAndDeletes();
350    setCurrentIteratorToLargestKey();
351}
352
353LevelDBSlice LevelDBTransaction::TransactionIterator::key() const
354{
355    ASSERT(isValid());
356    if (m_treeChanged)
357        refreshTreeIterator();
358    return m_current->key();
359}
360
361LevelDBSlice LevelDBTransaction::TransactionIterator::value() const
362{
363    ASSERT(isValid());
364    if (m_treeChanged)
365        refreshTreeIterator();
366    return m_current->value();
367}
368
369void LevelDBTransaction::TransactionIterator::treeChanged()
370{
371    m_treeChanged = true;
372}
373
374void LevelDBTransaction::TransactionIterator::refreshTreeIterator() const
375{
376    ASSERT(m_treeChanged);
377
378    m_treeChanged = false;
379
380    if (m_treeIterator->isValid() && m_treeIterator.get() == m_current) {
381        m_treeIterator->reset();
382        return;
383    }
384
385    if (m_dbIterator->isValid()) {
386
387        // There could be new nodes in the tree that we should iterate over.
388
389        if (m_direction == kForward) {
390            // Try to seek tree iterator to something greater than the db iterator.
391            m_treeIterator->seek(m_dbIterator->key());
392            if (m_treeIterator->isValid() && !m_comparator->compare(m_treeIterator->key(), m_dbIterator->key()))
393                m_treeIterator->next(); // If equal, take another step so the tree iterator is strictly greater.
394        } else {
395            // If going backward, seek to a key less than the db iterator.
396            ASSERT(m_direction == kReverse);
397            m_treeIterator->seek(m_dbIterator->key());
398            if (m_treeIterator->isValid())
399                m_treeIterator->prev();
400        }
401    }
402}
403
404bool LevelDBTransaction::TransactionIterator::treeIteratorIsLower() const
405{
406    return m_comparator->compare(m_treeIterator->key(), m_dbIterator->key()) < 0;
407}
408
409bool LevelDBTransaction::TransactionIterator::treeIteratorIsHigher() const
410{
411    return m_comparator->compare(m_treeIterator->key(), m_dbIterator->key()) > 0;
412}
413
414void LevelDBTransaction::TransactionIterator::handleConflictsAndDeletes()
415{
416    bool loop = true;
417
418    while (loop) {
419        loop = false;
420
421        if (m_treeIterator->isValid() && m_dbIterator->isValid() && !m_comparator->compare(m_treeIterator->key(), m_dbIterator->key())) {
422            // For equal keys, the tree iterator takes precedence, so move the database iterator another step.
423            if (m_direction == kForward)
424                m_dbIterator->next();
425            else
426                m_dbIterator->prev();
427        }
428
429        // Skip over delete markers in the tree iterator until it catches up with the db iterator.
430        if (m_treeIterator->isValid() && m_treeIterator->isDeleted()) {
431            if (m_direction == kForward && (!m_dbIterator->isValid() || treeIteratorIsLower())) {
432                m_treeIterator->next();
433                loop = true;
434            } else if (m_direction == kReverse && (!m_dbIterator->isValid() || treeIteratorIsHigher())) {
435                m_treeIterator->prev();
436                loop = true;
437            }
438        }
439    }
440}
441
442void LevelDBTransaction::TransactionIterator::setCurrentIteratorToSmallestKey()
443{
444    LevelDBIterator* smallest = 0;
445
446    if (m_treeIterator->isValid())
447        smallest = m_treeIterator.get();
448
449    if (m_dbIterator->isValid()) {
450        if (!smallest || m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0)
451            smallest = m_dbIterator.get();
452    }
453
454    m_current = smallest;
455}
456
457void LevelDBTransaction::TransactionIterator::setCurrentIteratorToLargestKey()
458{
459    LevelDBIterator* largest = 0;
460
461    if (m_treeIterator->isValid())
462        largest = m_treeIterator.get();
463
464    if (m_dbIterator->isValid()) {
465        if (!largest || m_comparator->compare(m_dbIterator->key(), largest->key()) > 0)
466            largest = m_dbIterator.get();
467    }
468
469    m_current = largest;
470}
471
472void LevelDBTransaction::registerIterator(TransactionIterator* iterator)
473{
474    ASSERT(!m_iterators.contains(iterator));
475    m_iterators.add(iterator);
476}
477
478void LevelDBTransaction::unregisterIterator(TransactionIterator* iterator)
479{
480    ASSERT(m_iterators.contains(iterator));
481    m_iterators.remove(iterator);
482}
483
484void LevelDBTransaction::notifyIteratorsOfTreeChange()
485{
486    for (HashSet<TransactionIterator*>::iterator i = m_iterators.begin(); i != m_iterators.end(); ++i) {
487        TransactionIterator* transactionIterator = *i;
488        transactionIterator->treeChanged();
489    }
490}
491
492LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db)
493    : m_db(db)
494    , m_writeBatch(std::make_unique<LevelDBWriteBatch>())
495    , m_finished(false)
496{
497}
498
499LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction()
500{
501    m_writeBatch->clear();
502}
503
504void LevelDBWriteOnlyTransaction::remove(const LevelDBSlice& key)
505{
506    ASSERT(!m_finished);
507    m_writeBatch->remove(key);
508}
509
510bool LevelDBWriteOnlyTransaction::commit()
511{
512    ASSERT(!m_finished);
513
514    if (!m_db->write(*m_writeBatch))
515        return false;
516
517    m_finished = true;
518    m_writeBatch->clear();
519    return true;
520}
521
522} // namespace WebCore
523
524#endif // USE(LEVELDB)
525#endif // ENABLE(INDEXED_DATABASE)
526