IndexedDB: Optimize range deletion operations (e.g. clearing a store)

content/browser/indexed_db/leveldb/leveldb_transaction.cc

Index: content/browser/indexed_db/leveldb/leveldb_transaction.cc
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.cc b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
index 016e7dea72b90ed23f1247f28813119d1f615f56..1722549384aeec3bb98b4a0d8afc4ac75507d778 100644
--- a/content/browser/indexed_db/leveldb/leveldb_transaction.cc
+++ b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
@@ -15,6 +15,20 @@
 
 using base::StringPiece;
 
+namespace {
+
+// Tests if the given key is before the end of a range, which
+// may have an open (exclusive) or closed (inclusive) bound.
+bool IsKeyBeforeEndOfRange(const content::LevelDBComparator* comparator,
+                           const StringPiece& key,
+                           const StringPiece& end,
+                           bool open) {
+  return (open ? comparator->Compare(key, end) < 0
+               : comparator->Compare(key, end) <= 0);
+}
+
+}  // namespace
+
 namespace content {
 
 LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
@@ -22,15 +36,14 @@ LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
       snapshot_(db),
       comparator_(db->Comparator()),
       data_comparator_(comparator_),
-      data_(data_comparator_),
-      finished_(false) {}
+      data_(data_comparator_) {}
 
-LevelDBTransaction::Record::Record() : deleted(false) {}
+LevelDBTransaction::Record::Record() {}
 LevelDBTransaction::Record::~Record() {}
 
 LevelDBTransaction::~LevelDBTransaction() {}
 
-bool LevelDBTransaction::Set(const StringPiece& key,
+void LevelDBTransaction::Set(const StringPiece& key,
                              std::string* value,
                              bool deleted) {
   DCHECK(!finished_);
@@ -43,21 +56,41 @@ bool LevelDBTransaction::Set(const StringPiece& key,
     record->deleted = deleted;
     data_[record->key] = std::move(record);
     NotifyIterators();
-    return false;
+    return;
   }
-  bool replaced_deleted_value = it->second->deleted;
   it->second->value.swap(*value);
   it->second->deleted = deleted;
-  return replaced_deleted_value;
 }
 
 void LevelDBTransaction::Put(const StringPiece& key, std::string* value) {
   Set(key, value, false);
 }
 
-bool LevelDBTransaction::Remove(const StringPiece& key) {
+void LevelDBTransaction::Remove(const StringPiece& key) {
   std::string empty;
-  return !Set(key, &empty, true);
+  Set(key, &empty, true);
+}
+
+leveldb::Status LevelDBTransaction::RemoveRange(const StringPiece& begin,
+                                                const StringPiece& end,
+                                                bool upper_open) {
+  leveldb::Status s;
+  bool dirty = false;
+  {
+    // Scope this iterator so it is deleted before other iterators are
+    // notified.
+    std::unique_ptr<TransactionIterator> it = TransactionIterator::Create(this);
+    for (s = it->Seek(begin);
+         s.ok() && it->IsValid() &&
+         IsKeyBeforeEndOfRange(comparator_, it->Key(), end, upper_open);
+         s = it->Next()) {
+      it->Delete();
+      dirty = true;
+    }
+  }
+  if (dirty)
+    NotifyIterators();
+  return s;
 }
 
 leveldb::Status LevelDBTransaction::Get(const StringPiece& key,
@@ -178,6 +211,12 @@ bool LevelDBTransaction::DataIterator::IsDeleted() const {
   return iterator_->second->deleted;
 }
 
+void LevelDBTransaction::DataIterator::Delete() {
+  DCHECK(IsValid());
+  iterator_->second->deleted = true;
+  iterator_->second->value.clear();
+}
+
 LevelDBTransaction::DataIterator::~DataIterator() {}
 
 LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
@@ -195,10 +234,8 @@ LevelDBTransaction::TransactionIterator::TransactionIterator(
     : transaction_(transaction),
       comparator_(transaction_->comparator_),
       data_iterator_(DataIterator::Create(transaction_.get())),
-      db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
-      current_(0),
-      direction_(FORWARD),
-      data_changed_(false) {
+      db_iterator_(
+          transaction_->db_->CreateIterator(&transaction_->snapshot_)) {
   transaction_->RegisterIterator(this);
 }
 
@@ -331,6 +368,18 @@ void LevelDBTransaction::TransactionIterator::DataChanged() {
   data_changed_ = true;
 }
 
+void LevelDBTransaction::TransactionIterator::Delete() {
+  DCHECK(IsValid());
+  if (current_ == data_iterator_.get()) {
+    data_iterator_->Delete();
+  } else {
+    std::unique_ptr<Record> record = base::MakeUnique<Record>();
+    record->key = Key().as_string();
+    record->deleted = true;
+    transaction_->data_[record->key] = std::move(record);
+  }
+}
+
 void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const {
   DCHECK(data_changed_);
 
@@ -403,7 +452,7 @@ void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
 
 void
 LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
-  LevelDBIterator* smallest = 0;
+  LevelDBIterator* smallest = nullptr;
 
   if (data_iterator_->IsValid())
     smallest = data_iterator_.get();
@@ -418,7 +467,7 @@ LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
 }
 
 void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
-  LevelDBIterator* largest = 0;
+  LevelDBIterator* largest = nullptr;
 
   if (data_iterator_->IsValid())
     largest = data_iterator_.get();
@@ -453,7 +502,7 @@ std::unique_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create(
 }
 
 LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db)
-    : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
+    : db_(db), write_batch_(LevelDBWriteBatch::Create()) {}
 
 LevelDBDirectTransaction::~LevelDBDirectTransaction() {
   write_batch_->Clear();