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

content/browser/indexed_db/leveldb/leveldb_transaction.cc

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "content/browser/indexed_db/leveldb/leveldb_transaction.h"
 
 #include "base/logging.h"
 #include "base/memory/ptr_util.h"
 #include "base/metrics/histogram_macros.h"
 #include "base/time/time.h"
 #include "content/browser/indexed_db/indexed_db_tracing.h"
 #include "content/browser/indexed_db/leveldb/leveldb_database.h"
 #include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
 #include "third_party/leveldatabase/src/include/leveldb/db.h"
 
 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)
     : db_(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_);
   DataType::iterator it = data_.find(key);
 
   if (it == data_.end()) {
     std::unique_ptr<Record> record = base::MakeUnique<Record>();
     record->key.assign(key.begin(), key.end() - key.begin());
     record->value.swap(*value);
     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,
                                         std::string* value,
                                         bool* found) {
   *found = false;
   DCHECK(!finished_);
   std::string string_key(key.begin(), key.end() - key.begin());
   DataType::const_iterator it = data_.find(string_key);
 
@@ skipping 100 matching lines @@
   DCHECK(IsValid());
   DCHECK(!IsDeleted());
   return iterator_->second->value;
 }
 
 bool LevelDBTransaction::DataIterator::IsDeleted() const {
   DCHECK(IsValid());
   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)
     : data_(&transaction->data_),
       iterator_(data_->end()) {}
 
 std::unique_ptr<LevelDBTransaction::TransactionIterator>
 LevelDBTransaction::TransactionIterator::Create(
     scoped_refptr<LevelDBTransaction> transaction) {
   return base::WrapUnique(new TransactionIterator(transaction));
 }
 
 LevelDBTransaction::TransactionIterator::TransactionIterator(
     scoped_refptr<LevelDBTransaction> transaction)
     : 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);
 }
 
 LevelDBTransaction::TransactionIterator::~TransactionIterator() {
   transaction_->UnregisterIterator(this);
 }
 
 bool LevelDBTransaction::TransactionIterator::IsValid() const {
   return !!current_;
 }
@@ skipping 112 matching lines @@
   DCHECK(IsValid());
   if (data_changed_)
     RefreshDataIterator();
   return current_->Value();
 }
 
 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_);
 
   data_changed_ = false;
 
   if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
     return;
   }
 
   if (db_iterator_->IsValid()) {
@@ skipping 52 matching lines @@
                  (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
         data_iterator_->Prev();
         loop = true;
       }
     }
   }
 }
 
 void
 LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
-  LevelDBIterator* smallest = 0;
+  LevelDBIterator* smallest = nullptr;
 
   if (data_iterator_->IsValid())
     smallest = data_iterator_.get();
 
   if (db_iterator_->IsValid()) {
     if (!smallest ||
         comparator_->Compare(db_iterator_->Key(), smallest->Key()) < 0)
       smallest = db_iterator_.get();
   }
 
   current_ = smallest;
 }
 
 void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
-  LevelDBIterator* largest = 0;
+  LevelDBIterator* largest = nullptr;
 
   if (data_iterator_->IsValid())
     largest = data_iterator_.get();
 
   if (db_iterator_->IsValid()) {
     if (!largest ||
         comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
       largest = db_iterator_.get();
   }
 
@@ skipping 14 matching lines @@
   for (auto* transaction_iterator : iterators_)
     transaction_iterator->DataChanged();
 }
 
 std::unique_ptr<LevelDBDirectTransaction> LevelDBDirectTransaction::Create(
     LevelDBDatabase* db) {
   return base::WrapUnique(new LevelDBDirectTransaction(db));
 }
 
 LevelDBDirectTransaction::LevelDBDirectTransaction(LevelDBDatabase* db)
-    : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
+    : db_(db), write_batch_(LevelDBWriteBatch::Create()) {}
 
 LevelDBDirectTransaction::~LevelDBDirectTransaction() {
   write_batch_->Clear();
 }
 
 void LevelDBDirectTransaction::Put(const StringPiece& key,
                                    const std::string* value) {
   DCHECK(!finished_);
   write_batch_->Put(key, *value);
 }
@@ skipping 20 matching lines @@
 
   leveldb::Status s = db_->Write(*write_batch_);
   if (s.ok()) {
     finished_ = true;
     write_batch_->Clear();
   }
   return s;
 }
 
 }  // namespace content