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

When porting the transaction back-end from Blink we brought
along an AVLTree implementation for the in-memory key/value
store for transactions. Replace this with a std::map since
it provides similar performance guarantees (red-black tree)
and we like to delete code.

TBR=jam@chromium.org
R=alecflett@chromium.org

Review URL: https://chromiumcodereview.appspot.com/17462005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@223493 0039d316-1c4b-4281-b951-d872f2087c98

6 files changed, 200 insertions, 1240 deletions

diff --git a/content/browser/indexed_db/leveldb/avltree.h b/content/browser/indexed_db/leveldb/avltree.h
deleted file mode 100644
index 91df048..0000000
--- a/content/browser/indexed_db/leveldb/avltree.h
+++ /dev/null
@@ -1,977 +0,0 @@
-// 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.
-
-/*
- * Copyright (C) 2008 Apple Inc. All rights reserved.
- *
- * Based on Abstract AVL Tree Template v1.5 by Walt Karas
- * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- *
- * 1.  Redistributions of source code must retain the above copyright
- *     notice, this list of conditions and the following disclaimer.
- * 2.  Redistributions in binary form must reproduce the above copyright
- *     notice, this list of conditions and the following disclaimer in the
- *     documentation and/or other materials provided with the distribution.
- * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
- *     its contributors may be used to endorse or promote products derived
- *     from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef CONTENT_BROWSER_INDEXED_DB_LEVELDB_AVLTREE_H_
-#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_AVLTREE_H_
-
-#include "base/logging.h"
-#include "content/browser/indexed_db/leveldb/fixed_array.h"
-
-namespace content {
-
-// Here is the reference class for BSet.
-//
-// class BSet
-//   {
-//   public:
-//
-//     class ANY_bitref
-//       {
-//       public:
-//         operator bool ();
-//         void operator = (bool b);
-//       };
-//
-//     // Does not have to initialize bits.
-//     BSet();
-//
-//     // Must return a valid value for index when 0 <= index < maxDepth
-//     ANY_bitref operator [] (unsigned index);
-//
-//     // Set all bits to 1.
-//     void Set();
-//
-//     // Set all bits to 0.
-//     void Reset();
-//   };
-
-template <unsigned maxDepth>
-class AVLTreeDefaultBSet {
- public:
-  bool& operator[](unsigned i) {
-#if defined(ADDRESS_SANITIZER)
-    CHECK(i < maxDepth);
-#endif
-    return data_[i];
-  }
-  void Set() {
-    for (unsigned i = 0; i < maxDepth; ++i)
-      data_[i] = true;
-  }
-  void Reset() {
-    for (unsigned i = 0; i < maxDepth; ++i)
-      data_[i] = false;
-  }
-
- private:
-  FixedArray<bool, maxDepth> data_;
-};
-
-// How to determine maxDepth:
-// d  Minimum number of nodes
-// 2  2
-// 3  4
-// 4  7
-// 5  12
-// 6  20
-// 7  33
-// 8  54
-// 9  88
-// 10 143
-// 11 232
-// 12 376
-// 13 609
-// 14 986
-// 15 1,596
-// 16 2,583
-// 17 4,180
-// 18 6,764
-// 19 10,945
-// 20 17,710
-// 21 28,656
-// 22 46,367
-// 23 75,024
-// 24 121,392
-// 25 196,417
-// 26 317,810
-// 27 514,228
-// 28 832,039
-// 29 1,346,268
-// 30 2,178,308
-// 31 3,524,577
-// 32 5,702,886
-// 33 9,227,464
-// 34 14,930,351
-// 35 24,157,816
-// 36 39,088,168
-// 37 63,245,985
-// 38 102,334,154
-// 39 165,580,140
-// 40 267,914,295
-// 41 433,494,436
-// 42 701,408,732
-// 43 1,134,903,169
-// 44 1,836,311,902
-// 45 2,971,215,072
-//
-// E.g., if, in a particular instantiation, the maximum number of nodes in a
-// tree instance is 1,000,000, the maximum depth should be 28.
-// You pick 28 because MN(28) is 832,039, which is less than or equal to
-// 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000.
-
-template <class Abstractor,
-          unsigned maxDepth = 32,
-          class BSet = AVLTreeDefaultBSet<maxDepth> >
-class AVLTree {
- public:
-  typedef typename Abstractor::key key;
-  typedef typename Abstractor::handle handle;
-  typedef typename Abstractor::size size;
-
-  enum SearchType {
-    EQUAL = 1,
-    LESS = 2,
-    GREATER = 4,
-    LESS_EQUAL = EQUAL | LESS,
-    GREATER_EQUAL = EQUAL | GREATER
-  };
-
-  Abstractor& abstractor() { return abs_; }
-
-  inline handle Insert(handle h);
-
-  inline handle Search(key k, SearchType st = EQUAL);
-  inline handle SearchLeast();
-  inline handle SearchGreatest();
-
-  inline handle Remove(key k);
-
-  inline handle Subst(handle new_node);
-
-  void Purge() { abs_.root = Null(); }
-
-  bool IsEmpty() { return abs_.root == Null(); }
-
-  AVLTree() { abs_.root = Null(); }
-
-  class Iterator {
-   public:
-    // Initialize depth to invalid value, to indicate iterator is
-    // invalid.   (Depth is zero-base.)
-    Iterator() { depth_ = ~0U; }
-
-    void StartIter(AVLTree* tree, key k, SearchType st = EQUAL) {
-      // Mask of high bit in an int.
-      const int kMaskHighBit = static_cast<int>(~((~(unsigned)0) >> 1));
-
-      // Save the tree that we're going to iterate through in a
-      // member variable.
-      tree_ = tree;
-
-      int cmp, target_cmp;
-      handle h = tree_->abs_.root;
-      unsigned d = 0;
-
-      depth_ = ~0U;
-
-      if (h == Null()) {
-        // Tree is empty.
-        return;
-      }
-
-      if (st & LESS) {
-        // Key can be greater than key of starting node.
-        target_cmp = 1;
-      } else if (st & GREATER) {
-        // Key can be less than key of starting node.
-        target_cmp = -1;
-      } else {
-        // Key must be same as key of starting node.
-        target_cmp = 0;
-      }
-
-      for (;;) {
-        cmp = CmpKN(k, h);
-        if (cmp == 0) {
-          if (st & EQUAL) {
-            // Equal node was sought and found as starting node.
-            depth_ = d;
-            break;
-          }
-          cmp = -target_cmp;
-        } else if (target_cmp != 0) {
-          if (!((cmp ^ target_cmp) & kMaskHighBit)) {
-            // cmp and target_cmp are both negative or both positive.
-            depth_ = d;
-          }
-        }
-        h = cmp < 0 ? GetLT(h) : GetGT(h);
-        if (h == Null())
-          break;
-        branch_[d] = cmp > 0;
-        path_h_[d++] = h;
-      }
-    }
-
-    void StartIterLeast(AVLTree* tree) {
-      tree_ = tree;
-
-      handle h = tree_->abs_.root;
-
-      depth_ = ~0U;
-
-      branch_.Reset();
-
-      while (h != Null()) {
-        if (depth_ != ~0U)
-          path_h_[depth_] = h;
-        depth_++;
-        h = GetLT(h);
-      }
-    }
-
-    void StartIterGreatest(AVLTree* tree) {
-      tree_ = tree;
-
-      handle h = tree_->abs_.root;
-
-      depth_ = ~0U;
-
-      branch_.Set();
-
-      while (h != Null()) {
-        if (depth_ != ~0U)
-          path_h_[depth_] = h;
-        depth_++;
-        h = GetGT(h);
-      }
-    }
-
-    handle operator*() {
-      if (depth_ == ~0U)
-        return Null();
-
-      return depth_ == 0 ? tree_->abs_.root : path_h_[depth_ - 1];
-    }
-
-    void operator++() {
-      if (depth_ != ~0U) {
-        handle h = GetGT(**this);
-        if (h == Null()) {
-          do {
-            if (depth_ == 0) {
-              depth_ = ~0U;
-              break;
-            }
-            depth_--;
-          } while (branch_[depth_]);
-        } else {
-          branch_[depth_] = true;
-          path_h_[depth_++] = h;
-          for (;;) {
-            h = GetLT(h);
-            if (h == Null())
-              break;
-            branch_[depth_] = false;
-            path_h_[depth_++] = h;
-          }
-        }
-      }
-    }
-
-    void operator--() {
-      if (depth_ != ~0U) {
-        handle h = GetLT(**this);
-        if (h == Null()) {
-          do {
-            if (depth_ == 0) {
-              depth_ = ~0U;
-              break;
-            }
-            depth_--;
-          } while (!branch_[depth_]);
-        } else {
-          branch_[depth_] = false;
-          path_h_[depth_++] = h;
-          for (;;) {
-            h = GetGT(h);
-            if (h == Null())
-              break;
-            branch_[depth_] = true;
-            path_h_[depth_++] = h;
-          }
-        }
-      }
-    }
-
-    void operator++(int /*ignored*/) { ++(*this); }
-    void operator--(int /*ignored*/) { --(*this); }
-
-   protected:
-    // Tree being iterated over.
-    AVLTree* tree_;
-
-    // Records a path into the tree.  If branch_[n] is true, indicates
-    // take greater branch from the nth node in the path, otherwise
-    // take the less branch.  branch_[0] gives branch from root, and
-    // so on.
-    BSet branch_;
-
-    // Zero-based depth of path into tree.
-    unsigned depth_;
-
-    // Handles of nodes in path from root to current node (returned by *).
-    static const size_t kPathSize = maxDepth - 1;
-    handle path_h_[kPathSize];
-
-    int CmpKN(key k, handle h) { return tree_->abs_.CompareKeyNode(k, h); }
-    int CmpNN(handle h1, handle h2) {
-      return tree_->abs_.CompareNodeNode(h1, h2);
-    }
-    handle GetLT(handle h) { return tree_->abs_.GetLess(h); }
-    handle GetGT(handle h) { return tree_->abs_.GetGreater(h); }
-    handle Null() { return tree_->abs_.Null(); }
-  };
-
-  template <typename fwd_iter>
-  bool Build(fwd_iter p, size num_nodes) {
-    if (num_nodes == 0) {
-      abs_.root = Null();
-      return true;
-    }
-
-    // Gives path to subtree being built.  If branch[N] is false, branch
-    // less from the node at depth N, if true branch greater.
-    BSet branch;
-
-    // If rem[N] is true, then for the current subtree at depth N, it's
-    // greater subtree has one more node than it's less subtree.
-    BSet rem;
-
-    // Depth of root node of current subtree.
-    unsigned depth = 0;
-
-    // Number of nodes in current subtree.
-    size num_sub = num_nodes;
-
-    // The algorithm relies on a stack of nodes whose less subtree has
-    // been built, but whose right subtree has not yet been built.  The
-    // stack is implemented as linked list.  The nodes are linked
-    // together by having the "greater" handle of a node set to the
-    // next node in the list.  "less_parent" is the handle of the first
-    // node in the list.
-    handle less_parent = Null();
-
-    // h is root of current subtree, child is one of its children.
-    handle h, child;
-
-    for (;;) {
-      while (num_sub > 2) {
-        // Subtract one for root of subtree.
-        num_sub--;
-        rem[depth] = !!(num_sub & 1);
-        branch[depth++] = false;
-        num_sub >>= 1;
-      }
-
-      if (num_sub == 2) {
-        // Build a subtree with two nodes, slanting to greater.
-        // I arbitrarily chose to always have the extra node in the
-        // greater subtree when there is an odd number of nodes to
-        // split between the two subtrees.
-
-        h = *p;
-        p++;
-        child = *p;
-        p++;
-        SetLT(child, Null());
-        SetGT(child, Null());
-        SetBF(child, 0);
-        SetGT(h, child);
-        SetLT(h, Null());
-        SetBF(h, 1);
-      } else {  // num_sub == 1
-                // Build a subtree with one node.
-
-        h = *p;
-        p++;
-        SetLT(h, Null());
-        SetGT(h, Null());
-        SetBF(h, 0);
-      }
-
-      while (depth) {
-        depth--;
-        if (!branch[depth]) {
-          // We've completed a less subtree.
-          break;
-        }
-
-        // We've completed a greater subtree, so attach it to
-        // its parent (that is less than it).  We pop the parent
-        // off the stack of less parents.
-        child = h;
-        h = less_parent;
-        less_parent = GetGT(h);
-        SetGT(h, child);
-        // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
-        num_sub <<= 1;
-        num_sub += 1 - rem[depth];
-        if (num_sub & (num_sub - 1)) {
-          // num_sub is not a power of 2
-          SetBF(h, 0);
-        } else {
-          // num_sub is a power of 2
-          SetBF(h, 1);
-        }
-      }
-
-      if (num_sub == num_nodes) {
-        // We've completed the full tree.
-        break;
-      }
-
-      // The subtree we've completed is the less subtree of the
-      // next node in the sequence.
-
-      child = h;
-      h = *p;
-      p++;
-      SetLT(h, child);
-
-      // Put h into stack of less parents.
-      SetGT(h, less_parent);
-      less_parent = h;
-
-      // Proceed to creating greater than subtree of h.
-      branch[depth] = true;
-      num_sub += rem[depth++];
-    }  // end for (;;)
-
-    abs_.root = h;
-
-    return true;
-  }
-
- protected:
-  friend class Iterator;
-
-  // Create a class whose sole purpose is to take advantage of
-  // the "empty member" optimization.
-  struct abs_plus_root : public Abstractor {
-    // The handle of the root element in the AVL tree.
-    handle root;
-  };
-
-  abs_plus_root abs_;
-
-  handle GetLT(handle h) { return abs_.GetLess(h); }
-  void SetLT(handle h, handle lh) { abs_.SetLess(h, lh); }
-
-  handle GetGT(handle h) { return abs_.GetGreater(h); }
-  void SetGT(handle h, handle gh) { abs_.SetGreater(h, gh); }
-
-  int GetBF(handle h) { return abs_.GetBalanceFactor(h); }
-  void SetBF(handle h, int bf) { abs_.SetBalanceFactor(h, bf); }
-
-  int CmpKN(key k, handle h) { return abs_.CompareKeyNode(k, h); }
-  int CmpNN(handle h1, handle h2) { return abs_.CompareNodeNode(h1, h2); }
-
-  handle Null() { return abs_.Null(); }
-
- private:
-  // Balances subtree, returns handle of root node of subtree
-  // after balancing.
-  handle Balance(handle bal_h) {
-    handle deep_h;
-
-    // Either the "greater than" or the "less than" subtree of
-    // this node has to be 2 levels deeper (or else it wouldn't
-    // need balancing).
-
-    if (GetBF(bal_h) > 0) {
-      // "Greater than" subtree is deeper.
-
-      deep_h = GetGT(bal_h);
-
-      if (GetBF(deep_h) < 0) {
-        handle old_h = bal_h;
-        bal_h = GetLT(deep_h);
-
-        SetGT(old_h, GetLT(bal_h));
-        SetLT(deep_h, GetGT(bal_h));
-        SetLT(bal_h, old_h);
-        SetGT(bal_h, deep_h);
-
-        int bf = GetBF(bal_h);
-        if (bf != 0) {
-          if (bf > 0) {
-            SetBF(old_h, -1);
-            SetBF(deep_h, 0);
-          } else {
-            SetBF(deep_h, 1);
-            SetBF(old_h, 0);
-          }
-          SetBF(bal_h, 0);
-        } else {
-          SetBF(old_h, 0);
-          SetBF(deep_h, 0);
-        }
-      } else {
-        SetGT(bal_h, GetLT(deep_h));
-        SetLT(deep_h, bal_h);
-        if (GetBF(deep_h) == 0) {
-          SetBF(deep_h, -1);
-          SetBF(bal_h, 1);
-        } else {
-          SetBF(deep_h, 0);
-          SetBF(bal_h, 0);
-        }
-        bal_h = deep_h;
-      }
-    } else {
-      // "Less than" subtree is deeper.
-
-      deep_h = GetLT(bal_h);
-
-      if (GetBF(deep_h) > 0) {
-        handle old_h = bal_h;
-        bal_h = GetGT(deep_h);
-        SetLT(old_h, GetGT(bal_h));
-        SetGT(deep_h, GetLT(bal_h));
-        SetGT(bal_h, old_h);
-        SetLT(bal_h, deep_h);
-
-        int bf = GetBF(bal_h);
-        if (bf != 0) {
-          if (bf < 0) {
-            SetBF(old_h, 1);
-            SetBF(deep_h, 0);
-          } else {
-            SetBF(deep_h, -1);
-            SetBF(old_h, 0);
-          }
-          SetBF(bal_h, 0);
-        } else {
-          SetBF(old_h, 0);
-          SetBF(deep_h, 0);
-        }
-      } else {
-        SetLT(bal_h, GetGT(deep_h));
-        SetGT(deep_h, bal_h);
-        if (GetBF(deep_h) == 0) {
-          SetBF(deep_h, 1);
-          SetBF(bal_h, -1);
-        } else {
-          SetBF(deep_h, 0);
-          SetBF(bal_h, 0);
-        }
-        bal_h = deep_h;
-      }
-    }
-
-    return bal_h;
-  }
-};
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::Insert(handle h) {
-  SetLT(h, Null());
-  SetGT(h, Null());
-  SetBF(h, 0);
-
-  if (abs_.root == Null()) {
-    abs_.root = h;
-  } else {
-    // Last unbalanced node encountered in search for insertion point.
-    handle unbal = Null();
-    // Parent of last unbalanced node.
-    handle parent_unbal = Null();
-    // Balance factor of last unbalanced node.
-    int unbal_bf;
-
-    // Zero-based depth in tree.
-    unsigned depth = 0, unbal_depth = 0;
-
-    // Records a path into the tree.  If branch[n] is true, indicates
-    // take greater branch from the nth node in the path, otherwise
-    // take the less branch.  branch[0] gives branch from root, and
-    // so on.
-    BSet branch;
-
-    handle hh = abs_.root;
-    handle parent = Null();
-    int cmp;
-
-    do {
-      if (GetBF(hh) != 0) {
-        unbal = hh;
-        parent_unbal = parent;
-        unbal_depth = depth;
-      }
-      cmp = CmpNN(h, hh);
-      if (cmp == 0) {
-        // Duplicate key.
-        return hh;
-      }
-      parent = hh;
-      hh = cmp < 0 ? GetLT(hh) : GetGT(hh);
-      branch[depth++] = cmp > 0;
-    } while (hh != Null());
-
-    //  Add node to insert as leaf of tree.
-    if (cmp < 0)
-      SetLT(parent, h);
-    else
-      SetGT(parent, h);
-
-    depth = unbal_depth;
-
-    if (unbal == Null()) {
-      hh = abs_.root;
-    } else {
-      cmp = branch[depth++] ? 1 : -1;
-      unbal_bf = GetBF(unbal);
-      if (cmp < 0)
-        unbal_bf--;
-      else  // cmp > 0
-        unbal_bf++;
-      hh = cmp < 0 ? GetLT(unbal) : GetGT(unbal);
-      if ((unbal_bf != -2) && (unbal_bf != 2)) {
-        // No rebalancing of tree is necessary.
-        SetBF(unbal, unbal_bf);
-        unbal = Null();
-      }
-    }
-
-    if (hh != Null()) {
-      while (h != hh) {
-        cmp = branch[depth++] ? 1 : -1;
-        if (cmp < 0) {
-          SetBF(hh, -1);
-          hh = GetLT(hh);
-        } else {  // cmp > 0
-          SetBF(hh, 1);
-          hh = GetGT(hh);
-        }
-      }
-    }
-
-    if (unbal != Null()) {
-      unbal = Balance(unbal);
-      if (parent_unbal == Null()) {
-        abs_.root = unbal;
-      } else {
-        depth = unbal_depth - 1;
-        cmp = branch[depth] ? 1 : -1;
-        if (cmp < 0)
-          SetLT(parent_unbal, unbal);
-        else  // cmp > 0
-          SetGT(parent_unbal, unbal);
-      }
-    }
-  }
-
-  return h;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::Search(
-    key k,
-    typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st) {
-  const int kMaskHighBit = static_cast<int>(~((~(unsigned)0) >> 1));
-
-  int cmp, target_cmp;
-  handle match_h = Null();
-  handle h = abs_.root;
-
-  if (st & LESS)
-    target_cmp = 1;
-  else if (st & GREATER)
-    target_cmp = -1;
-  else
-    target_cmp = 0;
-
-  while (h != Null()) {
-    cmp = CmpKN(k, h);
-    if (cmp == 0) {
-      if (st & EQUAL) {
-        match_h = h;
-        break;
-      }
-      cmp = -target_cmp;
-    } else if (target_cmp != 0) {
-      if (!((cmp ^ target_cmp) & kMaskHighBit)) {
-        // cmp and target_cmp are both positive or both negative.
-        match_h = h;
-      }
-    }
-    h = cmp < 0 ? GetLT(h) : GetGT(h);
-  }
-
-  return match_h;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::SearchLeast() {
-  handle h = abs_.root, parent = Null();
-
-  while (h != Null()) {
-    parent = h;
-    h = GetLT(h);
-  }
-
-  return parent;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::SearchGreatest() {
-  handle h = abs_.root, parent = Null();
-
-  while (h != Null()) {
-    parent = h;
-    h = GetGT(h);
-  }
-
-  return parent;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::Remove(key k) {
-  // Zero-based depth in tree.
-  unsigned depth = 0, rm_depth;
-
-  // Records a path into the tree.  If branch[n] is true, indicates
-  // take greater branch from the nth node in the path, otherwise
-  // take the less branch.  branch[0] gives branch from root, and
-  // so on.
-  BSet branch;
-
-  handle h = abs_.root;
-  handle parent = Null(), child;
-  int cmp, cmp_shortened_sub_with_path = 0;
-
-  for (;;) {
-    if (h == Null()) {
-      // No node in tree with given key.
-      return Null();
-    }
-    cmp = CmpKN(k, h);
-    if (cmp == 0) {
-      // Found node to remove.
-      break;
-    }
-    parent = h;
-    h = cmp < 0 ? GetLT(h) : GetGT(h);
-    branch[depth++] = cmp > 0;
-    cmp_shortened_sub_with_path = cmp;
-  }
-  handle rm = h;
-  handle parent_rm = parent;
-  rm_depth = depth;
-
-  // If the node to remove is not a leaf node, we need to get a
-  // leaf node, or a node with a single leaf as its child, to put
-  // in the place of the node to remove.  We will get the greatest
-  // node in the less subtree (of the node to remove), or the least
-  // node in the greater subtree.  We take the leaf node from the
-  // deeper subtree, if there is one.
-
-  if (GetBF(h) < 0) {
-    child = GetLT(h);
-    branch[depth] = false;
-    cmp = -1;
-  } else {
-    child = GetGT(h);
-    branch[depth] = true;
-    cmp = 1;
-  }
-  depth++;
-
-  if (child != Null()) {
-    cmp = -cmp;
-    do {
-      parent = h;
-      h = child;
-      if (cmp < 0) {
-        child = GetLT(h);
-        branch[depth] = false;
-      } else {
-        child = GetGT(h);
-        branch[depth] = true;
-      }
-      depth++;
-    } while (child != Null());
-
-    if (parent == rm) {
-      // Only went through do loop once.  Deleted node will be replaced
-      // in the tree structure by one of its immediate children.
-      cmp_shortened_sub_with_path = -cmp;
-    } else {
-      cmp_shortened_sub_with_path = cmp;
-    }
-
-    // Get the handle of the opposite child, which may not be null.
-    child = cmp > 0 ? GetLT(h) : GetGT(h);
-  }
-
-  if (parent == Null()) {
-    // There were only 1 or 2 nodes in this tree.
-    abs_.root = child;
-  } else if (cmp_shortened_sub_with_path < 0) {
-    SetLT(parent, child);
-  } else {
-    SetGT(parent, child);
-  }
-
-  // "path" is the parent of the subtree being eliminated or reduced
-  // from a depth of 2 to 1.  If "path" is the node to be removed, we
-  // set path to the node we're about to poke into the position of the
-  // node to be removed.
-  handle path = parent == rm ? h : parent;
-
-  if (h != rm) {
-    // Poke in the replacement for the node to be removed.
-    SetLT(h, GetLT(rm));
-    SetGT(h, GetGT(rm));
-    SetBF(h, GetBF(rm));
-    if (parent_rm == Null()) {
-      abs_.root = h;
-    } else {
-      depth = rm_depth - 1;
-      if (branch[depth])
-        SetGT(parent_rm, h);
-      else
-        SetLT(parent_rm, h);
-    }
-  }
-
-  if (path != Null()) {
-    // Create a temporary linked list from the parent of the path node
-    // to the root node.
-    h = abs_.root;
-    parent = Null();
-    depth = 0;
-    while (h != path) {
-      if (branch[depth++]) {
-        child = GetGT(h);
-        SetGT(h, parent);
-      } else {
-        child = GetLT(h);
-        SetLT(h, parent);
-      }
-      parent = h;
-      h = child;
-    }
-
-    // Climb from the path node to the root node using the linked
-    // list, restoring the tree structure and rebalancing as necessary.
-    bool reduced_depth = true;
-    int bf;
-    cmp = cmp_shortened_sub_with_path;
-    for (;;) {
-      if (reduced_depth) {
-        bf = GetBF(h);
-        if (cmp < 0)
-          bf++;
-        else  // cmp > 0
-          bf--;
-        if ((bf == -2) || (bf == 2)) {
-          h = Balance(h);
-          bf = GetBF(h);
-        } else {
-          SetBF(h, bf);
-        }
-        reduced_depth = (bf == 0);
-      }
-      if (parent == Null())
-        break;
-      child = h;
-      h = parent;
-      cmp = branch[--depth] ? 1 : -1;
-      if (cmp < 0) {
-        parent = GetLT(h);
-        SetLT(h, child);
-      } else {
-        parent = GetGT(h);
-        SetGT(h, child);
-      }
-    }
-    abs_.root = h;
-  }
-
-  return rm;
-}
-
-template <class Abstractor, unsigned maxDepth, class BSet>
-inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
-AVLTree<Abstractor, maxDepth, BSet>::Subst(handle new_node) {
-  handle h = abs_.root;
-  handle parent = Null();
-  int cmp, last_cmp;
-
-  // Search for node already in tree with same key.
-  for (;;) {
-    if (h == Null()) {
-      // No node in tree with same key as new node.
-      return Null();
-    }
-    cmp = CmpNN(new_node, h);
-    if (cmp == 0) {
-      // Found the node to substitute new one for.
-      break;
-    }
-    last_cmp = cmp;
-    parent = h;
-    h = cmp < 0 ? GetLT(h) : GetGT(h);
-  }
-
-  // Copy tree housekeeping fields from node in tree to new node.
-  SetLT(new_node, GetLT(h));
-  SetGT(new_node, GetGT(h));
-  SetBF(new_node, GetBF(h));
-
-  if (parent == Null()) {
-    // New node is also new root.
-    abs_.root = new_node;
-  } else {
-    // Make parent point to new node.
-    if (last_cmp < 0)
-      SetLT(parent, new_node);
-    else
-      SetGT(parent, new_node);
-  }
-
-  return h;
-}
-
-}  // namespace content
-
-#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_AVLTREE_H_
diff --git a/content/browser/indexed_db/leveldb/fixed_array.h b/content/browser/indexed_db/leveldb/fixed_array.h
deleted file mode 100644
index cef4397..0000000
--- a/content/browser/indexed_db/leveldb/fixed_array.h
+++ /dev/null
@@ -1,63 +0,0 @@
-// 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.
-
-/*
- * Copyright (C) 2010 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
- * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
- * THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef CONTENT_BROWSER_INDEXED_DB_LEVELDB_FIXED_ARRAY_H_
-#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_FIXED_ARRAY_H_
-
-#include "base/logging.h"
-
-namespace content {
-
-template <typename T, size_t Size>
-class FixedArray {
- public:
-  T& operator[](size_t i) {
-#if defined(ADDRESS_SANITIZER)
-    CHECK(i < Size);
-#endif
-    return data_[i];
-  }
-
-  const T& operator[](size_t i) const {
-#if defined(ADDRESS_SANITIZER)
-    CHECK(i < Size);
-#endif
-    return data_[i];
-  }
-
-  T* data() { return data_; }
-  size_t size() const { return Size; }
-
- private:
-  T data_[Size];
-};
-
-}  // namespace content
-
-#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_FIXED_ARRAY_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_database.h b/content/browser/indexed_db/leveldb/leveldb_database.h
index 1efeefa..5732ac4 100644
--- a/content/browser/indexed_db/leveldb/leveldb_database.h
+++ b/content/browser/indexed_db/leveldb/leveldb_database.h
@@ -6,7 +6,6 @@
 #define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_DATABASE_H_
 
 #include <string>
-#include <vector>
 
 #include "base/files/file_path.h"
 #include "base/memory/scoped_ptr.h"
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.cc b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
index 5388d44..0c36194 100644
--- a/content/browser/indexed_db/leveldb/leveldb_transaction.cc
+++ b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
@@ -14,49 +14,43 @@ using base::StringPiece;
 namespace content {
 
 LevelDBTransaction::LevelDBTransaction(LevelDBDatabase* db)
-    : db_(db), snapshot_(db), comparator_(db->Comparator()), finished_(false) {
-  tree_.abstractor().comparator_ = comparator_;
-}
-
-LevelDBTransaction::AVLTreeNode::AVLTreeNode() {}
-LevelDBTransaction::AVLTreeNode::~AVLTreeNode() {}
-
-void LevelDBTransaction::ClearTree() {
-  TreeType::Iterator iterator;
-  iterator.StartIterLeast(&tree_);
-
-  std::vector<AVLTreeNode*> nodes;
-
-  while (*iterator) {
-    nodes.push_back(*iterator);
-    ++iterator;
+    : db_(db),
+      snapshot_(db),
+      comparator_(db->Comparator()),
+      data_comparator_(comparator_),
+      data_(data_comparator_),
+      finished_(false) {}
+
+LevelDBTransaction::Record::Record() : deleted(false) {}
+LevelDBTransaction::Record::~Record() {}
+
+void LevelDBTransaction::Clear() {
+  for (DataType::iterator it = data_.begin(); it != data_.end(); ++it) {
+    delete it->second;
   }
-  tree_.Purge();
-
-  for (size_t i = 0; i < nodes.size(); ++i)
-    delete nodes[i];
+  data_.clear();
 }
 
-LevelDBTransaction::~LevelDBTransaction() { ClearTree(); }
+LevelDBTransaction::~LevelDBTransaction() { Clear(); }
 
 void LevelDBTransaction::Set(const StringPiece& key,
                              std::string* value,
                              bool deleted) {
   DCHECK(!finished_);
-  bool new_node = false;
-  AVLTreeNode* node = tree_.Search(key);
-
-  if (!node) {
-    node = new AVLTreeNode;
-    node->key = key.as_string();
-    tree_.Insert(node);
-    new_node = true;
+  DataType::iterator it = data_.find(key);
+
+  if (it == data_.end()) {
+    Record* record = new Record();
+    record->key.assign(key.begin(), key.end() - key.begin());
+    record->value.swap(*value);
+    record->deleted = deleted;
+    data_[record->key] = record;
+    NotifyIterators();
+    return;
   }
-  node->value.swap(*value);
-  node->deleted = deleted;
 
-  if (new_node)
-    NotifyIteratorsOfTreeChange();
+  it->second->value.swap(*value);
+  it->second->deleted = deleted;
 }
 
 void LevelDBTransaction::Put(const StringPiece& key, std::string* value) {
@@ -73,13 +67,14 @@ bool LevelDBTransaction::Get(const StringPiece& key,
                              bool* found) {
   *found = false;
   DCHECK(!finished_);
-  AVLTreeNode* node = tree_.Search(key);
+  std::string string_key(key.begin(), key.end() - key.begin());
+  DataType::const_iterator it = data_.find(string_key);
 
-  if (node) {
-    if (node->deleted)
+  if (it != data_.end()) {
+    if (it->second->deleted)
       return true;
 
-    *value = node->value;
+    *value = it->second->value;
     *found = true;
     return true;
   }
@@ -95,29 +90,25 @@ bool LevelDBTransaction::Get(const StringPiece& key,
 bool LevelDBTransaction::Commit() {
   DCHECK(!finished_);
 
-  if (tree_.IsEmpty()) {
+  if (data_.empty()) {
     finished_ = true;
     return true;
   }
 
   scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();
 
-  TreeType::Iterator iterator;
-  iterator.StartIterLeast(&tree_);
-
-  while (*iterator) {
-    AVLTreeNode* node = *iterator;
-    if (!node->deleted)
-      write_batch->Put(node->key, node->value);
+  for (DataType::iterator iterator = data_.begin(); iterator != data_.end();
+       ++iterator) {
+    if (!iterator->second->deleted)
+      write_batch->Put(iterator->first, iterator->second->value);
     else
-      write_batch->Remove(node->key);
-    ++iterator;
+      write_batch->Remove(iterator->first);
   }
 
   if (!db_->Write(*write_batch))
     return false;
 
-  ClearTree();
+  Clear();
   finished_ = true;
   return true;
 }
@@ -125,80 +116,66 @@ bool LevelDBTransaction::Commit() {
 void LevelDBTransaction::Rollback() {
   DCHECK(!finished_);
   finished_ = true;
-  ClearTree();
+  Clear();
 }
 
 scoped_ptr<LevelDBIterator> LevelDBTransaction::CreateIterator() {
   return TransactionIterator::Create(this).PassAs<LevelDBIterator>();
 }
 
-scoped_ptr<LevelDBTransaction::TreeIterator>
-LevelDBTransaction::TreeIterator::Create(LevelDBTransaction* transaction) {
-  return make_scoped_ptr(new TreeIterator(transaction));
+scoped_ptr<LevelDBTransaction::DataIterator>
+LevelDBTransaction::DataIterator::Create(LevelDBTransaction* transaction) {
+  return make_scoped_ptr(new DataIterator(transaction));
 }
 
-bool LevelDBTransaction::TreeIterator::IsValid() const { return !!*iterator_; }
-
-void LevelDBTransaction::TreeIterator::SeekToLast() {
-  iterator_.StartIterGreatest(tree_);
-  if (IsValid())
-    key_ = (*iterator_)->key;
+bool LevelDBTransaction::DataIterator::IsValid() const {
+  return iterator_ != data_->end();
 }
 
-void LevelDBTransaction::TreeIterator::Seek(const StringPiece& target) {
-  iterator_.StartIter(tree_, target, TreeType::EQUAL);
-  if (!IsValid())
-    iterator_.StartIter(tree_, target, TreeType::GREATER);
+void LevelDBTransaction::DataIterator::SeekToLast() {
+  iterator_ = data_->end();
+  if (iterator_ != data_->begin())
+    --iterator_;
+}
 
-  if (IsValid())
-    key_ = (*iterator_)->key;
+void LevelDBTransaction::DataIterator::Seek(const StringPiece& target) {
+  iterator_ = data_->lower_bound(target);
 }
 
-void LevelDBTransaction::TreeIterator::Next() {
+void LevelDBTransaction::DataIterator::Next() {
   DCHECK(IsValid());
   ++iterator_;
-  if (IsValid()) {
-    DCHECK_GE(transaction_->comparator_->Compare((*iterator_)->key, key_), 0);
-    key_ = (*iterator_)->key;
-  }
 }
 
-void LevelDBTransaction::TreeIterator::Prev() {
+void LevelDBTransaction::DataIterator::Prev() {
   DCHECK(IsValid());
-  --iterator_;
-  if (IsValid()) {
-    DCHECK_LT(tree_->abstractor().comparator_->Compare((*iterator_)->key, key_),
-              0);
-    key_ = (*iterator_)->key;
-  }
+  if (iterator_ != data_->begin())
+    --iterator_;
+  else
+    iterator_ = data_->end();
 }
 
-StringPiece LevelDBTransaction::TreeIterator::Key() const {
+StringPiece LevelDBTransaction::DataIterator::Key() const {
   DCHECK(IsValid());
-  return key_;
+  return iterator_->first;
 }
 
-StringPiece LevelDBTransaction::TreeIterator::Value() const {
+StringPiece LevelDBTransaction::DataIterator::Value() const {
   DCHECK(IsValid());
   DCHECK(!IsDeleted());
-  return (*iterator_)->value;
+  return iterator_->second->value;
 }
 
-bool LevelDBTransaction::TreeIterator::IsDeleted() const {
+bool LevelDBTransaction::DataIterator::IsDeleted() const {
   DCHECK(IsValid());
-  return (*iterator_)->deleted;
+  return iterator_->second->deleted;
 }
 
-void LevelDBTransaction::TreeIterator::Reset() {
-  DCHECK(IsValid());
-  iterator_.StartIter(tree_, key_, TreeType::EQUAL);
-  DCHECK(IsValid());
-}
+LevelDBTransaction::DataIterator::~DataIterator() {}
 
-LevelDBTransaction::TreeIterator::~TreeIterator() {}
-
-LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction)
-    : tree_(&transaction->tree_), transaction_(transaction) {}
+LevelDBTransaction::DataIterator::DataIterator(LevelDBTransaction* transaction)
+    : data_(&transaction->data_),
+      iterator_(data_->end()) {}
 
 scoped_ptr<LevelDBTransaction::TransactionIterator>
 LevelDBTransaction::TransactionIterator::Create(
@@ -210,11 +187,11 @@ LevelDBTransaction::TransactionIterator::TransactionIterator(
     scoped_refptr<LevelDBTransaction> transaction)
     : transaction_(transaction),
       comparator_(transaction_->comparator_),
-      tree_iterator_(TreeIterator::Create(transaction_.get())),
+      data_iterator_(DataIterator::Create(transaction_.get())),
       db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
       current_(0),
       direction_(FORWARD),
-      tree_changed_(false) {
+      data_changed_(false) {
   transaction_->RegisterIterator(this);
 }
 
@@ -227,7 +204,7 @@ bool LevelDBTransaction::TransactionIterator::IsValid() const {
 }
 
 void LevelDBTransaction::TransactionIterator::SeekToLast() {
-  tree_iterator_->SeekToLast();
+  data_iterator_->SeekToLast();
   db_iterator_->SeekToLast();
   direction_ = REVERSE;
 
@@ -236,7 +213,7 @@ void LevelDBTransaction::TransactionIterator::SeekToLast() {
 }
 
 void LevelDBTransaction::TransactionIterator::Seek(const StringPiece& target) {
-  tree_iterator_->Seek(target);
+  data_iterator_->Seek(target);
   db_iterator_->Seek(target);
   direction_ = FORWARD;
 
@@ -246,22 +223,23 @@ void LevelDBTransaction::TransactionIterator::Seek(const StringPiece& target) {
 
 void LevelDBTransaction::TransactionIterator::Next() {
   DCHECK(IsValid());
-  if (tree_changed_)
-    RefreshTreeIterator();
+  if (data_changed_)
+    RefreshDataIterator();
 
   if (direction_ != FORWARD) {
     // Ensure the non-current iterator is positioned after Key().
 
     LevelDBIterator* non_current = (current_ == db_iterator_.get())
-                                       ? tree_iterator_.get()
+                                       ? data_iterator_.get()
                                        : db_iterator_.get();
 
     non_current->Seek(Key());
     if (non_current->IsValid() &&
-        !comparator_->Compare(non_current->Key(), Key()))
-      non_current->Next();  // Take an extra step so the non-current key is
-                            // strictly greater than Key().
-
+        !comparator_->Compare(non_current->Key(), Key())) {
+      // Take an extra step so the non-current key is
+      // strictly greater than Key().
+      non_current->Next();
+    }
     DCHECK(!non_current->IsValid() ||
            comparator_->Compare(non_current->Key(), Key()) > 0);
 
@@ -275,14 +253,14 @@ void LevelDBTransaction::TransactionIterator::Next() {
 
 void LevelDBTransaction::TransactionIterator::Prev() {
   DCHECK(IsValid());
-  if (tree_changed_)
-    RefreshTreeIterator();
+  if (data_changed_)
+    RefreshDataIterator();
 
   if (direction_ != REVERSE) {
     // Ensure the non-current iterator is positioned before Key().
 
     LevelDBIterator* non_current = (current_ == db_iterator_.get())
-                                       ? tree_iterator_.get()
+                                       ? data_iterator_.get()
                                        : db_iterator_.get();
 
     non_current->Seek(Key());
@@ -293,8 +271,8 @@ void LevelDBTransaction::TransactionIterator::Prev() {
       // stepping, like we do in Next() above.
       non_current->Prev();
     } else {
-      non_current->SeekToLast();  // Iterator has no entries >= Key(). Position
-                                  // at last entry.
+      // Iterator has no entries >= Key(). Position at last entry.
+      non_current->SeekToLast();
     }
     DCHECK(!non_current->IsValid() ||
            comparator_->Compare(non_current->Key(), Key()) < 0);
@@ -309,58 +287,58 @@ void LevelDBTransaction::TransactionIterator::Prev() {
 
 StringPiece LevelDBTransaction::TransactionIterator::Key() const {
   DCHECK(IsValid());
-  if (tree_changed_)
-    RefreshTreeIterator();
+  if (data_changed_)
+    RefreshDataIterator();
   return current_->Key();
 }
 
 StringPiece LevelDBTransaction::TransactionIterator::Value() const {
   DCHECK(IsValid());
-  if (tree_changed_)
-    RefreshTreeIterator();
+  if (data_changed_)
+    RefreshDataIterator();
   return current_->Value();
 }
 
-void LevelDBTransaction::TransactionIterator::TreeChanged() {
-  tree_changed_ = true;
+void LevelDBTransaction::TransactionIterator::DataChanged() {
+  data_changed_ = true;
 }
 
-void LevelDBTransaction::TransactionIterator::RefreshTreeIterator() const {
-  DCHECK(tree_changed_);
+void LevelDBTransaction::TransactionIterator::RefreshDataIterator() const {
+  DCHECK(data_changed_);
 
-  tree_changed_ = false;
+  data_changed_ = false;
 
-  if (tree_iterator_->IsValid() && tree_iterator_.get() == current_) {
-    tree_iterator_->Reset();
+  if (data_iterator_->IsValid() && data_iterator_.get() == current_) {
     return;
   }
 
   if (db_iterator_->IsValid()) {
-    // There could be new nodes in the tree that we should iterate over.
+    // There could be new records in data that we should iterate over.
 
     if (direction_ == FORWARD) {
-      // Try to seek tree iterator to something greater than the db iterator.
-      tree_iterator_->Seek(db_iterator_->Key());
-      if (tree_iterator_->IsValid() &&
-          !comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()))
-        tree_iterator_->Next();  // If equal, take another step so the tree
-                                 // iterator is strictly greater.
+      // Try to seek data iterator to something greater than the db iterator.
+      data_iterator_->Seek(db_iterator_->Key());
+      if (data_iterator_->IsValid() &&
+          !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
+        // If equal, take another step so the data iterator is strictly greater.
+        data_iterator_->Next();
+      }
     } else {
       // If going backward, seek to a key less than the db iterator.
       DCHECK_EQ(REVERSE, direction_);
-      tree_iterator_->Seek(db_iterator_->Key());
-      if (tree_iterator_->IsValid())
-        tree_iterator_->Prev();
+      data_iterator_->Seek(db_iterator_->Key());
+      if (data_iterator_->IsValid())
+        data_iterator_->Prev();
     }
   }
 }
 
-bool LevelDBTransaction::TransactionIterator::TreeIteratorIsLower() const {
-  return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) < 0;
+bool LevelDBTransaction::TransactionIterator::DataIteratorIsLower() const {
+  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) < 0;
 }
 
-bool LevelDBTransaction::TransactionIterator::TreeIteratorIsHigher() const {
-  return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) > 0;
+bool LevelDBTransaction::TransactionIterator::DataIteratorIsHigher() const {
+  return comparator_->Compare(data_iterator_->Key(), db_iterator_->Key()) > 0;
 }
 
 void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
@@ -369,9 +347,9 @@ void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
   while (loop) {
     loop = false;
 
-    if (tree_iterator_->IsValid() && db_iterator_->IsValid() &&
-        !comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key())) {
-      // For equal keys, the tree iterator takes precedence, so move the
+    if (data_iterator_->IsValid() && db_iterator_->IsValid() &&
+        !comparator_->Compare(data_iterator_->Key(), db_iterator_->Key())) {
+      // For equal keys, the data iterator takes precedence, so move the
       // database iterator another step.
       if (direction_ == FORWARD)
         db_iterator_->Next();
@@ -379,16 +357,16 @@ void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
         db_iterator_->Prev();
     }
 
-    // Skip over delete markers in the tree iterator until it catches up with
+    // Skip over delete markers in the data iterator until it catches up with
     // the db iterator.
-    if (tree_iterator_->IsValid() && tree_iterator_->IsDeleted()) {
+    if (data_iterator_->IsValid() && data_iterator_->IsDeleted()) {
       if (direction_ == FORWARD &&
-          (!db_iterator_->IsValid() || TreeIteratorIsLower())) {
-        tree_iterator_->Next();
+          (!db_iterator_->IsValid() || DataIteratorIsLower())) {
+        data_iterator_->Next();
         loop = true;
       } else if (direction_ == REVERSE &&
-                 (!db_iterator_->IsValid() || TreeIteratorIsHigher())) {
-        tree_iterator_->Prev();
+                 (!db_iterator_->IsValid() || DataIteratorIsHigher())) {
+        data_iterator_->Prev();
         loop = true;
       }
     }
@@ -399,8 +377,8 @@ void
 LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
   LevelDBIterator* smallest = 0;
 
-  if (tree_iterator_->IsValid())
-    smallest = tree_iterator_.get();
+  if (data_iterator_->IsValid())
+    smallest = data_iterator_.get();
 
   if (db_iterator_->IsValid()) {
     if (!smallest ||
@@ -414,8 +392,8 @@ LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
 void LevelDBTransaction::TransactionIterator::SetCurrentIteratorToLargestKey() {
   LevelDBIterator* largest = 0;
 
-  if (tree_iterator_->IsValid())
-    largest = tree_iterator_.get();
+  if (data_iterator_->IsValid())
+    largest = data_iterator_.get();
 
   if (db_iterator_->IsValid()) {
     if (!largest ||
@@ -436,12 +414,12 @@ void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
   iterators_.erase(iterator);
 }
 
-void LevelDBTransaction::NotifyIteratorsOfTreeChange() {
+void LevelDBTransaction::NotifyIterators() {
   for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
        i != iterators_.end();
        ++i) {
     TransactionIterator* transaction_iterator = *i;
-    transaction_iterator->TreeChanged();
+    transaction_iterator->DataChanged();
   }
 }
 
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.h b/content/browser/indexed_db/leveldb/leveldb_transaction.h
index 83b4763..b7b5d64d 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,53 +37,33 @@ class CONTENT_EXPORT LevelDBTransaction
   virtual ~LevelDBTransaction();
   friend class base::RefCounted<LevelDBTransaction>;
 
-  struct AVLTreeNode {
-    AVLTreeNode();
-    ~AVLTreeNode();
+  struct Record {
+    Record();
+    ~Record();
     std::string key;
     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 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;
     }
 
-    static handle Null() { return 0; }
-
+   private:
     const LevelDBComparator* comparator_;
   };
 
-  typedef AVLTree<AVLTreeAbstractor> TreeType;
+  typedef std::map<base::StringPiece, Record*, Comparator> DataType;
 
-  class TreeIterator : public LevelDBIterator {
+  class DataIterator : public LevelDBIterator {
    public:
-    static scoped_ptr<TreeIterator> Create(LevelDBTransaction* transaction);
-    virtual ~TreeIterator();
+    static scoped_ptr<DataIterator> Create(LevelDBTransaction* transaction);
+    virtual ~DataIterator();
 
     virtual bool IsValid() const OVERRIDE;
     virtual void SeekToLast() OVERRIDE;
@@ -94,14 +73,11 @@ class CONTENT_EXPORT LevelDBTransaction
     virtual base::StringPiece Key() const OVERRIDE;
     virtual base::StringPiece Value() const OVERRIDE;
     bool IsDeleted() const;
-    void Reset();
 
    private:
-    explicit TreeIterator(LevelDBTransaction* transaction);
-    mutable TreeType::Iterator iterator_;  // Dereferencing this is non-const.
-    TreeType* tree_;
-    LevelDBTransaction* transaction_;
-    std::string key_;
+    explicit DataIterator(LevelDBTransaction* transaction);
+    DataType* data_;
+    DataType::iterator iterator_;
   };
 
   class TransactionIterator : public LevelDBIterator {
@@ -117,20 +93,20 @@ class CONTENT_EXPORT LevelDBTransaction
     virtual void Prev() OVERRIDE;
     virtual base::StringPiece Key() const OVERRIDE;
     virtual base::StringPiece Value() const OVERRIDE;
-    void TreeChanged();
+    void DataChanged();
 
    private:
     explicit TransactionIterator(scoped_refptr<LevelDBTransaction> transaction);
     void HandleConflictsAndDeletes();
     void SetCurrentIteratorToSmallestKey();
     void SetCurrentIteratorToLargestKey();
-    void RefreshTreeIterator() const;
-    bool TreeIteratorIsLower() const;
-    bool TreeIteratorIsHigher() const;
+    void RefreshDataIterator() const;
+    bool DataIteratorIsLower() const;
+    bool DataIteratorIsHigher() const;
 
     scoped_refptr<LevelDBTransaction> transaction_;
     const LevelDBComparator* comparator_;
-    mutable scoped_ptr<TreeIterator> tree_iterator_;
+    mutable scoped_ptr<DataIterator> data_iterator_;
     scoped_ptr<LevelDBIterator> db_iterator_;
     LevelDBIterator* current_;
 
@@ -139,19 +115,20 @@ class CONTENT_EXPORT LevelDBTransaction
       REVERSE
     };
     Direction direction_;
-    mutable bool tree_changed_;
+    mutable bool data_changed_;
   };
 
   void Set(const base::StringPiece& key, std::string* value, bool deleted);
-  void ClearTree();
+  void Clear();
   void RegisterIterator(TransactionIterator* iterator);
   void UnregisterIterator(TransactionIterator* iterator);
-  void NotifyIteratorsOfTreeChange();
+  void NotifyIterators();
 
   LevelDBDatabase* db_;
   const LevelDBSnapshot snapshot_;
   const LevelDBComparator* comparator_;
-  TreeType tree_;
+  Comparator data_comparator_;
+  DataType data_;
   bool finished_;
   std::set<TransactionIterator*> iterators_;
 };
diff --git a/content/browser/indexed_db/leveldb/leveldb_unittest.cc b/content/browser/indexed_db/leveldb/leveldb_unittest.cc
index 9ce0664..de506c5 100644
--- a/content/browser/indexed_db/leveldb/leveldb_unittest.cc
+++ b/content/browser/indexed_db/leveldb/leveldb_unittest.cc
@@ -197,6 +197,52 @@ TEST(LevelDBDatabaseTest, TransactionIterator) {
   EXPECT_FALSE(it->IsValid());
 }
 
+TEST(LevelDBDatabaseTest, TransactionCommitTest) {
+  base::ScopedTempDir temp_directory;
+  ASSERT_TRUE(temp_directory.CreateUniqueTempDir());
+
+  const std::string key1("key1");
+  const std::string key2("key2");
+  const std::string value1("value1");
+  const std::string value2("value2");
+  const std::string value3("value3");
+
+  std::string put_value;
+  std::string got_value;
+  SimpleComparator comparator;
+  bool success;
+  bool found;
+
+  scoped_ptr<LevelDBDatabase> leveldb;
+  LevelDBDatabase::Open(temp_directory.path(), &comparator, &leveldb);
+  EXPECT_TRUE(leveldb);
+
+  scoped_refptr<LevelDBTransaction> transaction =
+      new LevelDBTransaction(leveldb.get());
+
+  put_value = value1;
+  transaction->Put(key1, &put_value);
+
+  put_value = value2;
+  transaction->Put(key2, &put_value);
+
+  put_value = value3;
+  transaction->Put(key2, &put_value);
+
+  success = transaction->Commit();
+  EXPECT_TRUE(success);
+
+  success = leveldb->Get(key1, &got_value, &found);
+  EXPECT_TRUE(success);
+  EXPECT_TRUE(found);
+  EXPECT_EQ(value1, got_value);
+
+  success = leveldb->Get(key2, &got_value, &found);
+  EXPECT_TRUE(success);
+  EXPECT_TRUE(found);
+  EXPECT_EQ(value3, got_value);
+}
+
 }  // namespace
 
 }  // namespace content