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

content/browser/indexed_db/leveldb/leveldb_transaction.h

 // 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.
 
 #ifndef CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_TRANSACTION_H_
 #define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_TRANSACTION_H_
 
 #include <map>
 #include <memory>
 #include <set>
 #include <string>
 
 #include "base/gtest_prod_util.h"
 #include "base/macros.h"
 #include "base/memory/ref_counted.h"
 #include "base/strings/string_piece.h"
 #include "content/browser/indexed_db/leveldb/leveldb_comparator.h"
 #include "content/browser/indexed_db/leveldb/leveldb_database.h"
 #include "content/browser/indexed_db/leveldb/leveldb_iterator.h"
 
 namespace content {
 
+class LevelDBTransactionRangeTest;
 class LevelDBWriteBatch;
 

[dmurph, 2017/03/01 20:06:35]

Because this took me a while to understand:

Can you add documentation describing what the TransactionIterator vs
DataIterator is? To me it looks like DataIterator is for data that is
temporarily in the transaction, and TransactionIterator is actually reading
things from leveldb?

[jsbell, 2017/03/01 22:45:25]

Done - feedback welcome!

 class CONTENT_EXPORT LevelDBTransaction
     : public base::RefCounted<LevelDBTransaction> {
  public:
   void Put(const base::StringPiece& key, std::string* value);
 
-  // Returns true if this operation performs a change, where the value wasn't
-  // already deleted.
-  bool Remove(const base::StringPiece& key);
+  void Remove(const base::StringPiece& key);
+
+  leveldb::Status RemoveRange(const base::StringPiece& begin,
+                              const base::StringPiece& end,
+                              bool upper_open);
+
   virtual leveldb::Status Get(const base::StringPiece& key,
                               std::string* value,
                               bool* found);
   virtual leveldb::Status Commit();
   void Rollback();
 
   std::unique_ptr<LevelDBIterator> CreateIterator();
 
  protected:
   virtual ~LevelDBTransaction();
   explicit LevelDBTransaction(LevelDBDatabase* db);
   friend class IndexedDBClassFactory;
 
  private:
   friend class base::RefCounted<LevelDBTransaction>;
-  FRIEND_TEST_ALL_PREFIXES(LevelDBDatabaseTest, Transaction);
-  FRIEND_TEST_ALL_PREFIXES(LevelDBDatabaseTest, TransactionCommitTest);
-  FRIEND_TEST_ALL_PREFIXES(LevelDBDatabaseTest, TransactionIterator);
+  friend class content::LevelDBTransactionRangeTest;
+  FRIEND_TEST_ALL_PREFIXES(LevelDBTransactionTest, GetAndPut);
+  FRIEND_TEST_ALL_PREFIXES(LevelDBTransactionTest, Commit);
+  FRIEND_TEST_ALL_PREFIXES(LevelDBTransactionTest, Iterator);
 
   struct Record {
     Record();
     ~Record();
     std::string key;
     std::string value;
-    bool deleted;
+    bool deleted = false;
   };
 
   class Comparator {
    public:
     explicit Comparator(const LevelDBComparator* comparator)
         : comparator_(comparator) {}
     bool operator()(const base::StringPiece& a,
                     const base::StringPiece& b) const {
       return comparator_->Compare(a, b) < 0;
     }
@@ skipping 13 matching lines @@
 
     bool IsValid() const override;
     leveldb::Status SeekToLast() override;
     leveldb::Status Seek(const base::StringPiece& slice) override;
     leveldb::Status Next() override;
     leveldb::Status Prev() override;
     base::StringPiece Key() const override;
     base::StringPiece Value() const override;
     bool IsDeleted() const;
 
+    // Mark the current record as deleted.
+    void Delete();
+
    private:
     explicit DataIterator(LevelDBTransaction* transaction);
     DataType* data_;
     DataType::iterator iterator_;
 
     DISALLOW_COPY_AND_ASSIGN(DataIterator);
   };
 
   class TransactionIterator : public LevelDBIterator {
    public:
     ~TransactionIterator() override;
     static std::unique_ptr<TransactionIterator> Create(
         scoped_refptr<LevelDBTransaction> transaction);
 
     bool IsValid() const override;
     leveldb::Status SeekToLast() override;
     leveldb::Status Seek(const base::StringPiece& target) override;
     leveldb::Status Next() override;
     leveldb::Status Prev() override;
     base::StringPiece Key() const override;
     base::StringPiece Value() const override;
     void DataChanged();
 
+    // If the current iterator is the data iterator, mark the record as
+    // deleted and return true. Otherwise return false - the caller may want
+    // to insert a deletion record.
+    bool DeleteData();

[dmurph, 2017/03/01 20:06:35]

Better name? "MaybeDeleteOnDataIterator"?

[jsbell, 2017/03/01 22:45:25]

I realized I could pull the non-DataIterator case in here so I did that,
simplifying the logic here. PTAL?

+
    private:
     enum Direction { FORWARD, REVERSE };
 
     explicit TransactionIterator(scoped_refptr<LevelDBTransaction> transaction);
     void HandleConflictsAndDeletes();
     void SetCurrentIteratorToSmallestKey();
     void SetCurrentIteratorToLargestKey();
     void RefreshDataIterator() const;
     bool DataIteratorIsLower() const;
     bool DataIteratorIsHigher() const;
 
     scoped_refptr<LevelDBTransaction> transaction_;
     const LevelDBComparator* comparator_;
     mutable std::unique_ptr<DataIterator> data_iterator_;
     std::unique_ptr<LevelDBIterator> db_iterator_;
-    LevelDBIterator* current_;
+    LevelDBIterator* current_ = nullptr;
 
-    Direction direction_;
-    mutable bool data_changed_;
+    Direction direction_ = FORWARD;
+    mutable bool data_changed_ = false;
 
     DISALLOW_COPY_AND_ASSIGN(TransactionIterator);
   };
-  // Returns true if the key was originally marked deleted, false otherwise.
-  bool Set(const base::StringPiece& key, std::string* value, bool deleted);
+
+  void Set(const base::StringPiece& key, std::string* value, bool deleted);
   void RegisterIterator(TransactionIterator* iterator);
   void UnregisterIterator(TransactionIterator* iterator);
   void NotifyIterators();
 
   LevelDBDatabase* db_;
   const LevelDBSnapshot snapshot_;
   const LevelDBComparator* comparator_;
   Comparator data_comparator_;
   DataType data_;
-  bool finished_;
+  bool finished_ = false;
   std::set<TransactionIterator*> iterators_;
 
   DISALLOW_COPY_AND_ASSIGN(LevelDBTransaction);
 };
 
 // Reads go straight to the database, ignoring any writes cached in
 // write_batch_, and writes are write-through, without consolidation.
 class LevelDBDirectTransaction {
  public:
   static std::unique_ptr<LevelDBDirectTransaction> Create(LevelDBDatabase* db);
 
   ~LevelDBDirectTransaction();
   void Put(const base::StringPiece& key, const std::string* value);
   leveldb::Status Get(const base::StringPiece& key,
                       std::string* value,
                       bool* found);
   void Remove(const base::StringPiece& key);
   leveldb::Status Commit();
 
  private:
   explicit LevelDBDirectTransaction(LevelDBDatabase* db);
 
   LevelDBDatabase* db_;
   std::unique_ptr<LevelDBWriteBatch> write_batch_;
-  bool finished_;
+  bool finished_ = false;
 
   DISALLOW_COPY_AND_ASSIGN(LevelDBDirectTransaction);
 };
 
 }  // namespace content
 
 #endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_TRANSACTION_H_