IndexedDB: Replace transaction's AVLTree with std::map

content/browser/indexed_db/leveldb/leveldb_transaction.h

Index: content/browser/indexed_db/leveldb/leveldb_transaction.h
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.h b/content/browser/indexed_db/leveldb/leveldb_transaction.h
index 83b4763edc1dcb1abf0db458d3fa07983c430606..2da68ba3518fa396438a7796bb70a788af058a27 100644
--- a/content/browser/indexed_db/leveldb/leveldb_transaction.h
+++ b/content/browser/indexed_db/leveldb/leveldb_transaction.h
@@ -5,14 +5,13 @@
 #ifndef CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_TRANSACTION_H_
 #define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_TRANSACTION_H_
 
+#include <map>
 #include <set>
 #include <string>
-#include <vector>
 
 #include "base/memory/ref_counted.h"
 #include "base/memory/scoped_ptr.h"
 #include "base/strings/string_piece.h"
-#include "content/browser/indexed_db/leveldb/avltree.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"
@@ -38,48 +37,26 @@ class CONTENT_EXPORT LevelDBTransaction
   virtual ~LevelDBTransaction();
   friend class base::RefCounted<LevelDBTransaction>;
 
-  struct AVLTreeNode {
-    AVLTreeNode();
-    ~AVLTreeNode();
-    std::string key;
+  struct TreeNode {
+    TreeNode();
+    ~TreeNode();
     std::string value;
     bool deleted;
-
-    AVLTreeNode* less;
-    AVLTreeNode* greater;
-    int balance_factor;
-    DISALLOW_COPY_AND_ASSIGN(AVLTreeNode);
   };
 
-  struct AVLTreeAbstractor {
-    typedef AVLTreeNode* handle;
-    typedef size_t size;
-    typedef base::StringPiece key;
-
-    handle GetLess(handle h) { return h->less; }
-    void SetLess(handle h, handle less) { h->less = less; }
-    handle GetGreater(handle h) { return h->greater; }
-    void SetGreater(handle h, handle greater) { h->greater = greater; }
-
-    int GetBalanceFactor(handle h) { return h->balance_factor; }
-    void SetBalanceFactor(handle h, int bf) { h->balance_factor = bf; }
-
-    int CompareKeyKey(const key& ka, const key& kb) {
-      return comparator_->Compare(ka, kb);
-    }
-    int CompareKeyNode(const key& k, handle h) {
-      return CompareKeyKey(k, h->key);
-    }
-    int CompareNodeNode(handle ha, handle hb) {
-      return CompareKeyKey(ha->key, hb->key);
+  class TreeComparator {

[ericu, 2013/09/10 01:00:41]

How about removing the word "Tree" everywhere?

[jsbell, 2013/09/10 17:00:06]

Yeah, I suppose once the names are changed at all it doesn't help to keep the
old scheme.

+   public:
+    explicit TreeComparator(const LevelDBComparator* comparator)
+        : comparator_(comparator) {}
+    bool operator()(const std::string& a, const std::string& b) const {
+      return comparator_->Compare(a, b) < 0;
     }
 
-    static handle Null() { return 0; }
-
+   private:
     const LevelDBComparator* comparator_;
   };
 
-  typedef AVLTree<AVLTreeAbstractor> TreeType;
+  typedef std::map<std::string, TreeNode*, TreeComparator> TreeType;
 
   class TreeIterator : public LevelDBIterator {
    public:
@@ -98,8 +75,8 @@ class CONTENT_EXPORT LevelDBTransaction
 
    private:
     explicit TreeIterator(LevelDBTransaction* transaction);
-    mutable TreeType::Iterator iterator_;  // Dereferencing this is non-const.
     TreeType* tree_;
+    TreeType::iterator iterator_;
     LevelDBTransaction* transaction_;
     std::string key_;
   };
@@ -151,6 +128,7 @@ class CONTENT_EXPORT LevelDBTransaction
   LevelDBDatabase* db_;
   const LevelDBSnapshot snapshot_;
   const LevelDBComparator* comparator_;
+  TreeComparator tree_comparator_;
   TreeType tree_;
   bool finished_;
   std::set<TransactionIterator*> iterators_;