code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/platform/leveldb/LevelDBTransaction.cpp

   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 #include "LevelDBDatabase.h"
  30 #include "LevelDBSlice.h"
  31 #include "LevelDBWriteBatch.h"
  32
  33 #if ENABLE(INDEXED_DATABASE)
  34 #if ENABLE(LEVELDB)
  35
  36 namespace WebCore {
  37
  38 PassRefPtr<LevelDBTransaction> LevelDBTransaction::create(LevelDBDatabase* db)
  39 {
  40     return adoptRef(new LevelDBTransaction(db));
  41 }
  42
  43 LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
  44     : m_db(db)
  45     , m_comparator(db->comparator())
  46     , m_finished(false)
  47 {
  48     m_tree.abstractor().m_comparator = m_comparator;
  49 }
  50
  51 void LevelDBTransaction::clearTree()
  52 {
  53     TreeType::Iterator iterator;
  54     iterator.start_iter_least(m_tree);
  55
  56     Vector<AVLTreeNode*> nodes;
  57
  58     while (*iterator) {
  59         nodes.append(*iterator);
  60         ++iterator;
  61     }
  62     m_tree.purge();
  63
  64     for (size_t i = 0; i < nodes.size(); ++i)
  65         delete(nodes[i]);
  66 }
  67
  68 LevelDBTransaction::~LevelDBTransaction()
  69 {
  70     clearTree();
  71 }
  72
  73 static void initVector(const LevelDBSlice& slice, Vector<char>* vector)
  74 {
  75     vector->clear();
  76     vector->append(slice.begin(), slice.end() - slice.begin());
  77 }
  78
  79 bool LevelDBTransaction::set(const LevelDBSlice& key, const Vector<char>& value, bool deleted)
  80 {
  81     ASSERT(!m_finished);
  82     bool newNode = false;
  83     AVLTreeNode* node = m_tree.search(key);
  84
  85     if (!node) {
  86         node = new AVLTreeNode;
  87         initVector(key, &node->key);
  88         m_tree.insert(node);
  89         newNode = true;
  90     }
  91     node->value = value;
  92     node->deleted = deleted;
  93
  94     if (newNode)
  95         notifyIteratorsOfTreeChange();
  96     return true;
  97 }
  98
  99 bool LevelDBTransaction::put(const LevelDBSlice& key, const Vector<char>& value)
 100 {
 101     return set(key, value, false);
 102 }
 103
 104 bool LevelDBTransaction::remove(const LevelDBSlice& key)
 105 {
 106     return set(key, Vector<char>(), true);
 107 }
 108
 109 bool LevelDBTransaction::get(const LevelDBSlice& key, Vector<char>& value)
 110 {
 111     ASSERT(!m_finished);
 112     AVLTreeNode* node = m_tree.search(key);
 113
 114     if (node) {
 115         if (node->deleted)
 116             return false;
 117
 118         value = node->value;
 119         return true;
 120     }
 121
 122     return m_db->get(key, value);
 123 }
 124
 125 bool LevelDBTransaction::commit()
 126 {
 127     ASSERT(!m_finished);
 128     OwnPtr<LevelDBWriteBatch> writeBatch = LevelDBWriteBatch::create();
 129
 130     TreeType::Iterator iterator;
 131     iterator.start_iter_least(m_tree);
 132
 133     while (*iterator) {
 134         AVLTreeNode* node = *iterator;
 135         if (!node->deleted)
 136             writeBatch->put(node->key, node->value);
 137         else
 138             writeBatch->remove(node->key);
 139         ++iterator;
 140     }
 141
 142     if (!m_db->write(*writeBatch))
 143         return false;
 144
 145     clearTree();
 146     m_finished = true;
 147     return true;
 148 }
 149
 150 void LevelDBTransaction::rollback()
 151 {
 152     ASSERT(!m_finished);
 153     m_finished = true;
 154     clearTree();
 155 }
 156
 157 PassOwnPtr<LevelDBIterator> LevelDBTransaction::createIterator()
 158 {
 159     return TransactionIterator::create(this);
 160 }
 161
 162 PassOwnPtr<LevelDBTransaction::TreeIterator> LevelDBTransaction::TreeIterator::create(LevelDBTransaction* transaction)
 163 {
 164     return adoptPtr(new TreeIterator(transaction));
 165 }
 166
 167 bool LevelDBTransaction::TreeIterator::isValid() const
 168 {
 169     return *m_iterator;
 170 }
 171
 172 void LevelDBTransaction::TreeIterator::seekToLast()
 173 {
 174     m_iterator.start_iter_greatest(*m_tree);
 175     if (isValid())
 176         m_key = (*m_iterator)->key;
 177 }
 178
 179 void LevelDBTransaction::TreeIterator::seek(const LevelDBSlice& target)
 180 {
 181     m_iterator.start_iter(*m_tree, target, TreeType::EQUAL);
 182     if (!isValid())
 183         m_iterator.start_iter(*m_tree, target, TreeType::GREATER);
 184
 185     if (isValid())
 186         m_key = (*m_iterator)->key;
 187 }
 188
 189 void LevelDBTransaction::TreeIterator::next()
 190 {
 191     ASSERT(isValid());
 192     ++m_iterator;
 193     if (isValid()) {
 194         ASSERT(m_transaction->m_comparator->compare((*m_iterator)->key, m_key) > 0);
 195         m_key = (*m_iterator)->key;
 196     }
 197 }
 198
 199 void LevelDBTransaction::TreeIterator::prev()
 200 {
 201     ASSERT(isValid());
 202     --m_iterator;
 203     if (isValid()) {
 204         ASSERT(m_tree->abstractor().m_comparator->compare((*m_iterator)->key, m_key) < 0);
 205         m_key = (*m_iterator)->key;
 206     }
 207 }
 208
 209 LevelDBSlice LevelDBTransaction::TreeIterator::key() const
 210 {
 211     ASSERT(isValid());
 212     return m_key;
 213 }
 214
 215 LevelDBSlice LevelDBTransaction::TreeIterator::value() const
 216 {
 217     ASSERT(isValid());
 218     ASSERT(!isDeleted());
 219     return (*m_iterator)->value;
 220 }
 221
 222 bool LevelDBTransaction::TreeIterator::isDeleted() const
 223 {
 224     ASSERT(isValid());
 225     return (*m_iterator)->deleted;
 226 }
 227
 228 void LevelDBTransaction::TreeIterator::reset()
 229 {
 230     ASSERT(isValid());
 231     m_iterator.start_iter(*m_tree, m_key, TreeType::EQUAL);
 232     ASSERT(isValid());
 233 }
 234
 235 LevelDBTransaction::TreeIterator::~TreeIterator()
 236 {
 237 }
 238
 239 LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction)
 240     : m_tree(&transaction->m_tree)
 241     , m_transaction(transaction)
 242 {
 243 }
 244
 245 PassOwnPtr<LevelDBTransaction::TransactionIterator> LevelDBTransaction::TransactionIterator::create(PassRefPtr<LevelDBTransaction> transaction)
 246 {
 247     return adoptPtr(new TransactionIterator(transaction));
 248 }
 249
 250 LevelDBTransaction::TransactionIterator::TransactionIterator(PassRefPtr<LevelDBTransaction> transaction)
 251     : m_transaction(transaction)
 252     , m_comparator(m_transaction->m_comparator)
 253     , m_treeIterator(TreeIterator::create(m_transaction.get()))
 254     , m_dbIterator(m_transaction->m_db->createIterator())
 255     , m_current(0)
 256     , m_direction(kForward)
 257     , m_treeChanged(false)
 258 {
 259     m_transaction->registerIterator(this);
 260 }
 261
 262 LevelDBTransaction::TransactionIterator::~TransactionIterator()
 263 {
 264     m_transaction->unregisterIterator(this);
 265 }
 266
 267 bool LevelDBTransaction::TransactionIterator::isValid() const
 268 {
 269     return m_current;
 270 }
 271
 272 void LevelDBTransaction::TransactionIterator::seekToLast()
 273 {
 274     m_treeIterator->seekToLast();
 275     m_dbIterator->seekToLast();
 276     m_direction = kReverse;
 277
 278     handleConflictsAndDeletes();
 279     setCurrentIteratorToLargestKey();
 280 }
 281
 282 void LevelDBTransaction::TransactionIterator::seek(const LevelDBSlice& target)
 283 {
 284     m_treeIterator->seek(target);
 285     m_dbIterator->seek(target);
 286     m_direction = kForward;
 287
 288     handleConflictsAndDeletes();
 289     setCurrentIteratorToSmallestKey();
 290 }
 291
 292 void LevelDBTransaction::TransactionIterator::next()
 293 {
 294     ASSERT(isValid());
 295     if (m_treeChanged)
 296         refreshTreeIterator();
 297
 298     if (m_direction != kForward) {
 299         // Ensure the non-current iterator is positioned after key().
 300
 301         LevelDBIterator* nonCurrent = (m_current == m_dbIterator.get()) ? m_treeIterator.get() : m_dbIterator.get();
 302
 303         nonCurrent->seek(key());
 304         if (nonCurrent->isValid() && !m_comparator->compare(nonCurrent->key(), key()))
 305             nonCurrent->next(); // Take an extra step so the non-current key is strictly greater than key().
 306
 307         ASSERT(!nonCurrent->isValid() || m_comparator->compare(nonCurrent->key(), key()) > 0);
 308
 309         m_direction = kForward;
 310     }
 311
 312     m_current->next();
 313     handleConflictsAndDeletes();
 314     setCurrentIteratorToSmallestKey();
 315 }
 316
 317 void LevelDBTransaction::TransactionIterator::prev()
 318 {
 319     ASSERT(isValid());
 320     if (m_treeChanged)
 321         refreshTreeIterator();
 322
 323     if (m_direction != kReverse) {
 324         // Ensure the non-current iterator is positioned before key().
 325
 326         LevelDBIterator* nonCurrent = (m_current == m_dbIterator.get()) ? m_treeIterator.get() : m_dbIterator.get();
 327
 328         nonCurrent->seek(key());
 329         if (nonCurrent->isValid()) {
 330             // Iterator is at first entry >= key().
 331             // Step back once to entry < key.
 332             // This is why we don't check for the keys being the same before
 333             // stepping, like we do in next() above.
 334             nonCurrent->prev();
 335         } else
 336             nonCurrent->seekToLast(); // Iterator has no entries >= key(). Position at last entry.
 337
 338         ASSERT(!nonCurrent->isValid() || m_comparator->compare(nonCurrent->key(), key()) < 0);
 339
 340         m_direction = kReverse;
 341     }
 342
 343     m_current->prev();
 344     handleConflictsAndDeletes();
 345     setCurrentIteratorToLargestKey();
 346 }
 347
 348 LevelDBSlice LevelDBTransaction::TransactionIterator::key() const
 349 {
 350     ASSERT(isValid());
 351     if (m_treeChanged)
 352         refreshTreeIterator();
 353     return m_current->key();
 354 }
 355
 356 LevelDBSlice LevelDBTransaction::TransactionIterator::value() const
 357 {
 358     ASSERT(isValid());
 359     if (m_treeChanged)
 360         refreshTreeIterator();
 361     return m_current->value();
 362 }
 363
 364 void LevelDBTransaction::TransactionIterator::treeChanged()
 365 {
 366     m_treeChanged = true;
 367 }
 368
 369 void LevelDBTransaction::TransactionIterator::refreshTreeIterator() const
 370 {
 371     ASSERT(m_treeChanged);
 372
 373     if (m_treeIterator->isValid()) {
 374         m_treeIterator->reset();
 375         return;
 376     }
 377
 378     if (m_dbIterator->isValid()) {
 379         ASSERT(!m_treeIterator->isValid());
 380
 381         // There could be new nodes in the tree that we should iterate over.
 382
 383         if (m_direction == kForward) {
 384             // Try to seek tree iterator to something greater than the db iterator.
 385             m_treeIterator->seek(m_dbIterator->key());
 386             if (m_treeIterator->isValid() && !m_comparator->compare(m_treeIterator->key(), m_dbIterator->key()))
 387                 m_treeIterator->next(); // If equal, take another step so the tree iterator is strictly greater.
 388         } else {
 389             // If going backward, seek to a key less than the db iterator.
 390             ASSERT(m_direction == kReverse);
 391             m_treeIterator->seek(m_dbIterator->key());
 392             if (m_treeIterator->isValid())
 393                 m_treeIterator->prev();
 394         }
 395     }
 396
 397     m_treeChanged = false;
 398 }
 399
 400 void LevelDBTransaction::TransactionIterator::handleConflictsAndDeletes()
 401 {
 402     bool loop = true;
 403
 404     while (loop) {
 405         loop = false;
 406
 407         if (m_treeIterator->isValid() && m_dbIterator->isValid() && !m_comparator->compare(m_treeIterator->key(), m_dbIterator->key())) {
 408             // For equal keys, the tree iterator takes precedence, so move the database iterator another step.
 409             if (m_direction == kForward)
 410                 m_dbIterator->next();
 411             else
 412                 m_dbIterator->prev();
 413         }
 414
 415         if (m_treeIterator->isValid() && m_treeIterator->isDeleted()) {
 416             // If the tree iterator is on a delete marker, take another step.
 417             if (m_direction == kForward)
 418                 m_treeIterator->next();
 419             else
 420                 m_treeIterator->prev();
 421
 422             loop = true;
 423         }
 424     }
 425 }
 426
 427 void LevelDBTransaction::TransactionIterator::setCurrentIteratorToSmallestKey()
 428 {
 429     LevelDBIterator* smallest = 0;
 430
 431     if (m_treeIterator->isValid())
 432         smallest = m_treeIterator.get();
 433
 434     if (m_dbIterator->isValid()) {
 435         if (!smallest || m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0)
 436             smallest = m_dbIterator.get();
 437     }
 438
 439     m_current = smallest;
 440 }
 441
 442 void LevelDBTransaction::TransactionIterator::setCurrentIteratorToLargestKey()
 443 {
 444     LevelDBIterator* largest = 0;
 445
 446     if (m_treeIterator->isValid())
 447         largest = m_treeIterator.get();
 448
 449     if (m_dbIterator->isValid()) {
 450         if (!largest || m_comparator->compare(m_dbIterator->key(), largest->key()) > 0)
 451             largest = m_dbIterator.get();
 452     }
 453
 454     m_current = largest;
 455 }
 456
 457 void LevelDBTransaction::registerIterator(TransactionIterator* iterator)
 458 {
 459     ASSERT(!m_iterators.contains(iterator));
 460     m_iterators.add(iterator);
 461 }
 462
 463 void LevelDBTransaction::unregisterIterator(TransactionIterator* iterator)
 464 {
 465     ASSERT(m_iterators.contains(iterator));
 466     m_iterators.remove(iterator);
 467 }
 468
 469 void LevelDBTransaction::notifyIteratorsOfTreeChange()
 470 {
 471     for (HashSet<TransactionIterator*>::iterator i = m_iterators.begin(); i != m_iterators.end(); ++i) {
 472         TransactionIterator* transactionIterator = *i;
 473         transactionIterator->treeChanged();
 474     }
 475 }
 476
 477 } // namespace WebCore
 478
 479 #endif // ENABLE(LEVELDB)
 480 #endif // ENABLE(INDEXED_DATABASE)