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