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 void LevelDBTransaction::DataIterator::SeekToLast() {
 134   iterator_ = data_->end();
 135   if (iterator_ != data_->begin())
 136     --iterator_;
 137 }
 138
 139 void LevelDBTransaction::DataIterator::Seek(const StringPiece& target) {
 140   iterator_ = data_->lower_bound(target);
 141 }
 142
 143 void LevelDBTransaction::DataIterator::Next() {
 144   DCHECK(IsValid());
 145   ++iterator_;
 146 }
 147
 148 void LevelDBTransaction::DataIterator::Prev() {
 149   DCHECK(IsValid());
 150   if (iterator_ != data_->begin())
 151     --iterator_;
 152   else
 153     iterator_ = data_->end();
 154 }
 155
 156 StringPiece LevelDBTransaction::DataIterator::Key() const {
 157   DCHECK(IsValid());
 158   return iterator_->first;
 159 }
 160
 161 StringPiece LevelDBTransaction::DataIterator::Value() const {
 162   DCHECK(IsValid());
 163   DCHECK(!IsDeleted());
 164   return iterator_->second->value;
 165 }
 166
 167 bool LevelDBTransaction::DataIterator::IsDeleted() const {
 168   DCHECK(IsValid());
 169   return iterator_->second->deleted;
 170 }
 171
 172 LevelDBTransaction::DataIterator::~DataIterator() {}
 173
 174 LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
 175     : data_(&transaction->data_),
 176       iterator_(data_->end()) {}
 177
 178 scoped_ptr<LevelDBTransaction::TransactionIterator>
 179 LevelDBTransaction::TransactionIterator::Create(
 180     scoped_refptr<LevelDBTransaction> transaction) {
 181   return make_scoped_ptr(new TransactionIterator(transaction));
 182 }
 183
 184 LevelDBTransaction::TransactionIterator::TransactionIterator(
 185     scoped_refptr<LevelDBTransaction> transaction)
 186     : transaction_(transaction),
 187       comparator_(transaction_->comparator_),
 188       data_iterator_(DataIterator::Create(transaction_.get())),
 189       db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
 190       current_(0),
 191       direction_(FORWARD),
 192       data_changed_(false) {
 193   transaction_->RegisterIterator(this);
 194 }
 195
 196 LevelDBTransaction::TransactionIterator::~TransactionIterator() {
 197   transaction_->UnregisterIterator(this);
 198 }
 199
 200 bool LevelDBTransaction::TransactionIterator::IsValid() const {
 201   return !!current_;
 202 }
 203
 204 void LevelDBTransaction::TransactionIterator::SeekToLast() {
 205   data_iterator_->SeekToLast();
 206   db_iterator_->SeekToLast();
 207   direction_ = REVERSE;
 208
 209   HandleConflictsAndDeletes();
 210   SetCurrentIteratorToLargestKey();
 211 }
 212
 213 void LevelDBTransaction::TransactionIterator::Seek(const StringPiece& target) {
 214   data_iterator_->Seek(target);
 215   db_iterator_->Seek(target);
 216   direction_ = FORWARD;
 217
 218   HandleConflictsAndDeletes();
 219   SetCurrentIteratorToSmallestKey();
 220 }
 221
 222 void LevelDBTransaction::TransactionIterator::Next() {
 223   DCHECK(IsValid());
 224   if (data_changed_)
 225     RefreshDataIterator();
 226
 227   if (direction_ != FORWARD) {
 228     // Ensure the non-current iterator is positioned after Key().
 229
 230     LevelDBIterator* non_current = (current_ == db_iterator_.get())
 231                                        ? data_iterator_.get()
 232                                        : db_iterator_.get();
 233
 234     non_current->Seek(Key());
 235     if (non_current->IsValid() &&
 236         !comparator_->Compare(non_current->Key(), Key())) {
 237       // Take an extra step so the non-current key is
 238       // strictly greater than Key().
 239       non_current->Next();
 240     }
 241     DCHECK(!non_current->IsValid() ||
 242            comparator_->Compare(non_current->Key(), Key()) > 0);
 243
 244     direction_ = FORWARD;
 245   }
 246
 247   current_->Next();
 248   HandleConflictsAndDeletes();
 249   SetCurrentIteratorToSmallestKey();
 250 }
 251
 252 void LevelDBTransaction::TransactionIterator::Prev() {
 253   DCHECK(IsValid());
 254   if (data_changed_)
 255     RefreshDataIterator();
 256
 257   if (direction_ != REVERSE) {
 258     // Ensure the non-current iterator is positioned before Key().
 259
 260     LevelDBIterator* non_current = (current_ == db_iterator_.get())
 261                                        ? data_iterator_.get()
 262                                        : db_iterator_.get();
 263
 264     non_current->Seek(Key());
 265     if (non_current->IsValid()) {
 266       // Iterator is at first entry >= Key().
 267       // Step back once to entry < key.
 268       // This is why we don't check for the keys being the same before
 269       // stepping, like we do in Next() above.
 270       non_current->Prev();
 271     } else {
 272       // Iterator has no entries >= Key(). Position at last entry.
 273       non_current->SeekToLast();
 274     }
 275     DCHECK(!non_current->IsValid() ||
 276            comparator_->Compare(non_current->Key(), Key()) < 0);
 277
 278     direction_ = REVERSE;
 279   }
 280
 281   current_->Prev();
 282   HandleConflictsAndDeletes();
 283   SetCurrentIteratorToLargestKey();
 284 }
 285
 286 StringPiece LevelDBTransaction::TransactionIterator::Key() const {
 287   DCHECK(IsValid());
 288   if (data_changed_)
 289     RefreshDataIterator();
 290   return current_->Key();
 291 }
 292
 293 StringPiece LevelDBTransaction::TransactionIterator::Value() const {
 294   DCHECK(IsValid());
 295   if (data_changed_)
 296     RefreshDataIterator();
 297   return current_->Value();
 298 }
 299
 300 void LevelDBTransaction::TransactionIterator::DataChanged() {
 301   data_changed_ = true;
 302 }
 303
 304 void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const {
 305   DCHECK(data_changed_);
 306
 307   data_changed_ = false;
 308
 309   if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
 310     return;
 311   }
 312
 313   if (db_iterator_->IsValid()) {
 314     // There could be new records in data that we should iterate over.
 315
 316     if (direction_ == FORWARD) {
 317       // Try to seek data iterator to something greater than the db iterator.
 318       data_iterator_->Seek(db_iterator_->Key());
 319       if (data_iterator_->IsValid() &&
 320           !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
 321         // If equal, take another step so the data iterator is strictly greater.
 322         data_iterator_->Next();
 323       }
 324     } else {
 325       // If going backward, seek to a key less than the db iterator.
 326       DCHECK_EQ(REVERSE, direction_);
 327       data_iterator_->Seek(db_iterator_->Key());
 328       if (data_iterator_->IsValid())
 329         data_iterator_->Prev();
 330     }
 331   }
 332 }
 333
 334 bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const {
 335   return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0;
 336 }
 337
 338 bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const {
 339   return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0;
 340 }
 341
 342 void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
 343   bool loop = true;
 344
 345   while (loop) {
 346     loop = false;
 347
 348     if (data_iterator_->IsValid() && db_iterator_->IsValid() &&
 349         !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
 350       // For equal keys, the data iterator takes precedence, so move the
 351       // database iterator another step.
 352       if (direction_ == FORWARD)
 353         db_iterator_->Next();
 354       else
 355         db_iterator_->Prev();
 356     }
 357
 358     // Skip over delete markers in the data iterator until it catches up with
 359     // the db iterator.
 360     if (data_iterator_->IsValid() && data_iterator_->IsDeleted()) {
 361       if (direction_ == FORWARD &&
 362           (!db_iterator_->IsValid() || DataIteratorIsLower())) {
 363         data_iterator_->Next();
 364         loop = true;
 365       } else if (direction_ == REVERSE &&
 366                  (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
 367         data_iterator_->Prev();
 368         loop = true;
 369       }
 370     }
 371   }
 372 }
 373
 374 void
 375 LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
 376   LevelDBIterator* smallest = 0;
 377
 378   if (data_iterator_->IsValid())
 379     smallest = data_iterator_.get();
 380
 381   if (db_iterator_->IsValid()) {
 382     if (!smallest ||
 383         comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
 384       smallest = db_iterator_.get();
 385   }
 386
 387   current_ = smallest;
 388 }
 389
 390 void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
 391   LevelDBIterator* largest = 0;
 392
 393   if (data_iterator_->IsValid())
 394     largest = data_iterator_.get();
 395
 396   if (db_iterator_->IsValid()) {
 397     if (!largest ||
 398         comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
 399       largest = db_iterator_.get();
 400   }
 401
 402   current_ = largest;
 403 }
 404
 405 void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) {
 406   DCHECK(iterators_.find(iterator) == iterators_.end());
 407   iterators_.insert(iterator);
 408 }
 409
 410 void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
 411   DCHECK(iterators_.find(iterator) != iterators_.end());
 412   iterators_.erase(iterator);
 413 }
 414
 415 void LevelDBTransaction::NotifyIterators() {
 416   for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
 417        i != iterators_.end();
 418        ++i) {
 419     TransactionIterator* transaction_iterator = *i;
 420     transaction_iterator->DataChanged();
 421   }
 422 }
 423
 424 scoped_ptr<LevelDBWriteOnlyTransaction> LevelDBWriteOnlyTransaction::Create(
 425     LevelDBDatabase* db) {
 426   return make_scoped_ptr(new LevelDBWriteOnlyTransaction(db));
 427 }
 428
 429 LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db)
 430     : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
 431
 432 LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction() {
 433   write_batch_->Clear();
 434 }
 435
 436 void LevelDBWriteOnlyTransaction::Remove(const StringPiece& key) {
 437   DCHECK(!finished_);
 438   write_batch_->Remove(key);
 439 }
 440
 441 leveldb::Status LevelDBWriteOnlyTransaction::Commit() {
 442   DCHECK(!finished_);
 443
 444   leveldb::Status s = db_->Write(*write_batch_);
 445   if (s.ok()) {
 446     finished_ = true;
 447     write_batch_->Clear();
 448   }
 449   return s;
 450 }
 451
 452 }  // namespace content