src/content/browser/indexed_db/leveldb/leveldb_transaction.cc

   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