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