Home | History | Annotate | Download | only in leveldb 
      1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "content/browser/indexed_db/leveldb/leveldb_transaction.h"
      6 
      7 #include "base/logging.h"
      8 #include "content/browser/indexed_db/leveldb/leveldb_database.h"
      9 #include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
     10 #include "third_party/leveldatabase/src/include/leveldb/db.h"
     11 
     12 using base::StringPiece;
     13 
     14 namespace content {
     15 
     16 LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
     17     : db_(db), snapshot_(db), comparator_(db->Comparator()), finished_(false) {
     18   tree_.abstractor().comparator_ = comparator_;
     19 }
     20 
     21 LevelDBTransaction::AVLTreeNode::AVLTreeNode() {}
     22 LevelDBTransaction::AVLTreeNode::~AVLTreeNode() {}
     23 
     24 void LevelDBTransaction::ClearTree() {
     25   TreeType::Iterator iterator;
     26   iterator.StartIterLeast(&tree_);
     27 
     28   std::vector<AVLTreeNode*> nodes;
     29 
     30   while (*iterator) {
     31     nodes.push_back(*iterator);
     32     ++iterator;
     33   }
     34   tree_.Purge();
     35 
     36   for (size_t i = 0; i < nodes.size(); ++i)
     37     delete nodes[i];
     38 }
     39 
     40 LevelDBTransaction::~LevelDBTransaction() { ClearTree(); }
     41 
     42 void LevelDBTransaction::Set(const StringPiece& key,
     43                              std::string* value,
     44                              bool deleted) {
     45   DCHECK(!finished_);
     46   bool new_node = false;
     47   AVLTreeNode* node = tree_.Search(key);
     48 
     49   if (!node) {
     50     node = new AVLTreeNode;
     51     node->key = key.as_string();
     52     tree_.Insert(node);
     53     new_node = true;
     54   }
     55   node->value.swap(*value);
     56   node->deleted = deleted;
     57 
     58   if (new_node)
     59     NotifyIteratorsOfTreeChange();
     60 }
     61 
     62 void LevelDBTransaction::Put(const StringPiece& key, std::string* value) {
     63   Set(key, value, false);
     64 }
     65 
     66 void LevelDBTransaction::Remove(const StringPiece& key) {
     67   std::string empty;
     68   Set(key, &empty, true);
     69 }
     70 
     71 bool LevelDBTransaction::Get(const StringPiece& key,
     72                              std::string* value,
     73                              bool* found) {
     74   *found = false;
     75   DCHECK(!finished_);
     76   AVLTreeNode* node = tree_.Search(key);
     77 
     78   if (node) {
     79     if (node->deleted)
     80       return true;
     81 
     82     *value = node->value;
     83     *found = true;
     84     return true;
     85   }
     86 
     87   bool ok = db_->Get(key, value, found, &snapshot_);
     88   if (!ok) {
     89     DCHECK(!*found);
     90     return false;
     91   }
     92   return true;
     93 }
     94 
     95 bool LevelDBTransaction::Commit() {
     96   DCHECK(!finished_);
     97 
     98   if (tree_.IsEmpty()) {
     99     finished_ = true;
    100     return true;
    101   }
    102 
    103   scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();
    104 
    105   TreeType::Iterator iterator;
    106   iterator.StartIterLeast(&tree_);
    107 
    108   while (*iterator) {
    109     AVLTreeNode* node = *iterator;
    110     if (!node->deleted)
    111       write_batch->Put(node->key, node->value);
    112     else
    113       write_batch->Remove(node->key);
    114     ++iterator;
    115   }
    116 
    117   if (!db_->Write(*write_batch))
    118     return false;
    119 
    120   ClearTree();
    121   finished_ = true;
    122   return true;
    123 }
    124 
    125 void LevelDBTransaction::Rollback() {
    126   DCHECK(!finished_);
    127   finished_ = true;
    128   ClearTree();
    129 }
    130 
    131 scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() {
    132   return TransactionIterator::Create(this).PassAs<LevelDBIterator>();
    133 }
    134 
    135 scoped_ptr<LevelDBTransaction::TreeIterator>
    136 LevelDBTransaction::TreeIterator::Create(LevelDBTransaction* transaction) {
    137   return make_scoped_ptr(new TreeIterator(transaction));
    138 }
    139 
    140 bool LevelDBTransaction::TreeIterator::IsValid() const { return !!*iterator_; }
    141 
    142 void LevelDBTransaction::TreeIterator::SeekToLast() {
    143   iterator_.StartIterGreatest(tree_);
    144   if (IsValid())
    145     key_ = (*iterator_)->key;
    146 }
    147 
    148 void LevelDBTransaction::TreeIterator::Seek(const StringPiece& target) {
    149   iterator_.StartIter(tree_, target, TreeType::EQUAL);
    150   if (!IsValid())
    151     iterator_.StartIter(tree_, target, TreeType::GREATER);
    152 
    153   if (IsValid())
    154     key_ = (*iterator_)->key;
    155 }
    156 
    157 void LevelDBTransaction::TreeIterator::Next() {
    158   DCHECK(IsValid());
    159   ++iterator_;
    160   if (IsValid()) {
    161     DCHECK_GE(transaction_->comparator_->Compare((*iterator_)->key, key_), 0);
    162     key_ = (*iterator_)->key;
    163   }
    164 }
    165 
    166 void LevelDBTransaction::TreeIterator::Prev() {
    167   DCHECK(IsValid());
    168   --iterator_;
    169   if (IsValid()) {
    170     DCHECK_LT(tree_->abstractor().comparator_->Compare((*iterator_)->key, key_),
    171               0);
    172     key_ = (*iterator_)->key;
    173   }
    174 }
    175 
    176 StringPiece LevelDBTransaction::TreeIterator::Key() const {
    177   DCHECK(IsValid());
    178   return key_;
    179 }
    180 
    181 StringPiece LevelDBTransaction::TreeIterator::Value() const {
    182   DCHECK(IsValid());
    183   DCHECK(!IsDeleted());
    184   return (*iterator_)->value;
    185 }
    186 
    187 bool LevelDBTransaction::TreeIterator::IsDeleted() const {
    188   DCHECK(IsValid());
    189   return (*iterator_)->deleted;
    190 }
    191 
    192 void LevelDBTransaction::TreeIterator::Reset() {
    193   DCHECK(IsValid());
    194   iterator_.StartIter(tree_, key_, TreeType::EQUAL);
    195   DCHECK(IsValid());
    196 }
    197 
    198 LevelDBTransaction::TreeIterator::~TreeIterator() {}
    199 
    200 LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction)
    201     : tree_(&transaction->tree_), transaction_(transaction) {}
    202 
    203 scoped_ptr<LevelDBTransaction::TransactionIterator>
    204 LevelDBTransaction::TransactionIterator::Create(
    205     scoped_refptr<LevelDBTransaction> transaction) {
    206   return make_scoped_ptr(new TransactionIterator(transaction));
    207 }
    208 
    209 LevelDBTransaction::TransactionIterator::TransactionIterator(
    210     scoped_refptr<LevelDBTransaction> transaction)
    211     : transaction_(transaction),
    212       comparator_(transaction_->comparator_),
    213       tree_iterator_(TreeIterator::Create(transaction_.get())),
    214       db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
    215       current_(0),
    216       direction_(FORWARD),
    217       tree_changed_(false) {
    218   transaction_->RegisterIterator(this);
    219 }
    220 
    221 LevelDBTransaction::TransactionIterator::~TransactionIterator() {
    222   transaction_->UnregisterIterator(this);
    223 }
    224 
    225 bool LevelDBTransaction::TransactionIterator::IsValid() const {
    226   return !!current_;
    227 }
    228 
    229 void LevelDBTransaction::TransactionIterator::SeekToLast() {
    230   tree_iterator_->SeekToLast();
    231   db_iterator_->SeekToLast();
    232   direction_ = REVERSE;
    233 
    234   HandleConflictsAndDeletes();
    235   SetCurrentIteratorToLargestKey();
    236 }
    237 
    238 void LevelDBTransaction::TransactionIterator::Seek(const StringPiece& target) {
    239   tree_iterator_->Seek(target);
    240   db_iterator_->Seek(target);
    241   direction_ = FORWARD;
    242 
    243   HandleConflictsAndDeletes();
    244   SetCurrentIteratorToSmallestKey();
    245 }
    246 
    247 void LevelDBTransaction::TransactionIterator::Next() {
    248   DCHECK(IsValid());
    249   if (tree_changed_)
    250     RefreshTreeIterator();
    251 
    252   if (direction_ != FORWARD) {
    253     // Ensure the non-current iterator is positioned after Key().
    254 
    255     LevelDBIterator* non_current = (current_ == db_iterator_.get())
    256                                        ? tree_iterator_.get()
    257                                        : db_iterator_.get();
    258 
    259     non_current->Seek(Key());
    260     if (non_current->IsValid() &&
    261         !comparator_->Compare(non_current->Key(), Key()))
    262       non_current->Next();  // Take an extra step so the non-current key is
    263                             // strictly greater than Key().
    264 
    265     DCHECK(!non_current->IsValid() ||
    266            comparator_->Compare(non_current->Key(), Key()) > 0);
    267 
    268     direction_ = FORWARD;
    269   }
    270 
    271   current_->Next();
    272   HandleConflictsAndDeletes();
    273   SetCurrentIteratorToSmallestKey();
    274 }
    275 
    276 void LevelDBTransaction::TransactionIterator::Prev() {
    277   DCHECK(IsValid());
    278   if (tree_changed_)
    279     RefreshTreeIterator();
    280 
    281   if (direction_ != REVERSE) {
    282     // Ensure the non-current iterator is positioned before Key().
    283 
    284     LevelDBIterator* non_current = (current_ == db_iterator_.get())
    285                                        ? tree_iterator_.get()
    286                                        : db_iterator_.get();
    287 
    288     non_current->Seek(Key());
    289     if (non_current->IsValid()) {
    290       // Iterator is at first entry >= Key().
    291       // Step back once to entry < key.
    292       // This is why we don't check for the keys being the same before
    293       // stepping, like we do in Next() above.
    294       non_current->Prev();
    295     } else {
    296       non_current->SeekToLast();  // Iterator has no entries >= Key(). Position
    297                                   // at last entry.
    298     }
    299     DCHECK(!non_current->IsValid() ||
    300            comparator_->Compare(non_current->Key(), Key()) < 0);
    301 
    302     direction_ = REVERSE;
    303   }
    304 
    305   current_->Prev();
    306   HandleConflictsAndDeletes();
    307   SetCurrentIteratorToLargestKey();
    308 }
    309 
    310 StringPiece LevelDBTransaction::TransactionIterator::Key() const {
    311   DCHECK(IsValid());
    312   if (tree_changed_)
    313     RefreshTreeIterator();
    314   return current_->Key();
    315 }
    316 
    317 StringPiece LevelDBTransaction::TransactionIterator::Value() const {
    318   DCHECK(IsValid());
    319   if (tree_changed_)
    320     RefreshTreeIterator();
    321   return current_->Value();
    322 }
    323 
    324 void LevelDBTransaction::TransactionIterator::TreeChanged() {
    325   tree_changed_ = true;
    326 }
    327 
    328 void LevelDBTransaction::TransactionIterator::RefreshTreeIterator() const {
    329   DCHECK(tree_changed_);
    330 
    331   tree_changed_ = false;
    332 
    333   if (tree_iterator_->IsValid() && tree_iterator_.get() == current_) {
    334     tree_iterator_->Reset();
    335     return;
    336   }
    337 
    338   if (db_iterator_->IsValid()) {
    339     // There could be new nodes in the tree that we should iterate over.
    340 
    341     if (direction_ == FORWARD) {
    342       // Try to seek tree iterator to something greater than the db iterator.
    343       tree_iterator_->Seek(db_iterator_->Key());
    344       if (tree_iterator_->IsValid() &&
    345           !comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()))
    346         tree_iterator_->Next();  // If equal, take another step so the tree
    347                                  // iterator is strictly greater.
    348     } else {
    349       // If going backward, seek to a key less than the db iterator.
    350       DCHECK_EQ(REVERSE, direction_);
    351       tree_iterator_->Seek(db_iterator_->Key());
    352       if (tree_iterator_->IsValid())
    353         tree_iterator_->Prev();
    354     }
    355   }
    356 }
    357 
    358 bool LevelDBTransaction::TransactionIterator::TreeIteratorIsLower() const {
    359   return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) < 0;
    360 }
    361 
    362 bool LevelDBTransaction::TransactionIterator::TreeIteratorIsHigher() const {
    363   return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) > 0;
    364 }
    365 
    366 void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
    367   bool loop = true;
    368 
    369   while (loop) {
    370     loop = false;
    371 
    372     if (tree_iterator_->IsValid() && db_iterator_->IsValid() &&
    373         !comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key())) {
    374       // For equal keys, the tree iterator takes precedence, so move the
    375       // database iterator another step.
    376       if (direction_ == FORWARD)
    377         db_iterator_->Next();
    378       else
    379         db_iterator_->Prev();
    380     }
    381 
    382     // Skip over delete markers in the tree iterator until it catches up with
    383     // the db iterator.
    384     if (tree_iterator_->IsValid() && tree_iterator_->IsDeleted()) {
    385       if (direction_ == FORWARD &&
    386           (!db_iterator_->IsValid() || TreeIteratorIsLower())) {
    387         tree_iterator_->Next();
    388         loop = true;
    389       } else if (direction_ == REVERSE &&
    390                  (!db_iterator_->IsValid() || TreeIteratorIsHigher())) {
    391         tree_iterator_->Prev();
    392         loop = true;
    393       }
    394     }
    395   }
    396 }
    397 
    398 void
    399 LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
    400   LevelDBIterator* smallest = 0;
    401 
    402   if (tree_iterator_->IsValid())
    403     smallest = tree_iterator_.get();
    404 
    405   if (db_iterator_->IsValid()) {
    406     if (!smallest ||
    407         comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
    408       smallest = db_iterator_.get();
    409   }
    410 
    411   current_ = smallest;
    412 }
    413 
    414 void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
    415   LevelDBIterator* largest = 0;
    416 
    417   if (tree_iterator_->IsValid())
    418     largest = tree_iterator_.get();
    419 
    420   if (db_iterator_->IsValid()) {
    421     if (!largest ||
    422         comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
    423       largest = db_iterator_.get();
    424   }
    425 
    426   current_ = largest;
    427 }
    428 
    429 void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) {
    430   DCHECK(iterators_.find(iterator) == iterators_.end());
    431   iterators_.insert(iterator);
    432 }
    433 
    434 void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
    435   DCHECK(iterators_.find(iterator) != iterators_.end());
    436   iterators_.erase(iterator);
    437 }
    438 
    439 void LevelDBTransaction::NotifyIteratorsOfTreeChange() {
    440   for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
    441        i != iterators_.end();
    442        ++i) {
    443     TransactionIterator* transaction_iterator = *i;
    444     transaction_iterator->TreeChanged();
    445   }
    446 }
    447 
    448 scoped_ptr<LevelDBWriteOnlyTransaction> LevelDBWriteOnlyTransaction::Create(
    449     LevelDBDatabase* db) {
    450   return make_scoped_ptr(new LevelDBWriteOnlyTransaction(db));
    451 }
    452 
    453 LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db)
    454     : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
    455 
    456 LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction() {
    457   write_batch_->Clear();
    458 }
    459 
    460 void LevelDBWriteOnlyTransaction::Remove(const StringPiece& key) {
    461   DCHECK(!finished_);
    462   write_batch_->Remove(key);
    463 }
    464 
    465 bool LevelDBWriteOnlyTransaction::Commit() {
    466   DCHECK(!finished_);
    467 
    468   if (!db_->Write(*write_batch_))
    469     return false;
    470 
    471   finished_ = true;
    472   write_batch_->Clear();
    473   return true;
    474 }
    475 
    476 }  // namespace content
    477