Migrate the IndexedDB backend from Blink to Chromium

To get the IDB backend off the (deprecated) WebKit thread, remove
intermediate proxying, and let us take advantage of base utilities,
we're moving the code from Blink to Chromium.

This patch is basically a glorified copy/paste of the Blink IDB
backend code, with Chromium coding style applied, WTF dependencies
replaced with STL and base/, redundant classes removed, etc. It
introduces some new temporary proxy classes
(content/browser/webidb*_impl.*) to allow us build both the old and
new backends.

The new backend is currently disabled by default. It can be enabled
using a new (and temporary) command line switch: --new-indexeddb Once
we've done some further cleanup and are confident that the new backend
is stable, and the bots have moved from DumpRenderTree to
content_shell, we'll switch to the new backend by default. Once that
has survived through a dev channel release, we'll delete the Blink
code and eliminate unnecessary proxy classes.

BUG=234278
R=alecflett@chromium.org, dgrogan@chromium.org, piman@chromium.org

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=202215

Review URL: https://codereview.chromium.org/15564008

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

12 files changed, 2501 insertions, 0 deletions

diff --git a/content/browser/indexed_db/leveldb/avltree.h b/content/browser/indexed_db/leveldb/avltree.h
new file mode 100644
index 0000000..104d69b
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/avltree.h
@@ -0,0 +1,979 @@
+// 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 m_data[i];
+  }
+  void set() {
+    for (unsigned i = 0; i < maxDepth; ++i)
+      m_data[i] = true;
+  }
+  void reset() {
+    for (unsigned i = 0; i < maxDepth; ++i)
+      m_data[i] = false;
+  }
+
+ private:
+  FixedArray<bool, maxDepth> m_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 search_least();
+  inline handle search_greatest();
+
+  inline handle remove(key k);
+
+  inline handle subst(handle new_node);
+
+  void purge() { abs.root = null(); }
+
+  bool is_empty() { 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 start_iter(AVLTree& tree, key k, SearchType st = EQUAL) {
+      // Mask of high bit in an int.
+      const int kMaskHighBit = (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 = cmp_k_n(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 ? get_lt(h) : get_gt(h);
+        if (h == null())
+          break;
+        branch[d] = cmp > 0;
+        path_h[d++] = h;
+      }
+    }
+
+    void start_iter_least(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 = get_lt(h);
+      }
+    }
+
+    void start_iter_greatest(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 = get_gt(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 = get_gt(**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 = get_lt(h);
+            if (h == null())
+              break;
+            branch[depth] = false;
+            path_h[depth++] = h;
+          }
+        }
+      }
+    }
+
+    void operator--() {
+      if (depth != ~0U) {
+        handle h = get_lt(**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 = get_gt(h);
+            if (h == null())
+              break;
+            branch[depth] = true;
+            path_h[depth++] = h;
+          }
+        }
+      }
+    }
+
+    void operator++(int) { ++(*this); }
+    void operator--(int) { --(*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 *).
+    handle path_h[maxDepth - 1];
+
+    int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
+    int cmp_n_n(handle h1, handle h2) {
+      return tree_->abs.compare_node_node(h1, h2);
+    }
+    handle get_lt(handle h) { return tree_->abs.get_less(h); }
+    handle get_gt(handle h) { return tree_->abs.get_greater(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++;
+        set_lt(child, null());
+        set_gt(child, null());
+        set_bf(child, 0);
+        set_gt(h, child);
+        set_lt(h, null());
+        set_bf(h, 1);
+      } else {  // num_sub == 1
+                // Build a subtree with one node.
+
+        h = *p;
+        p++;
+        set_lt(h, null());
+        set_gt(h, null());
+        set_bf(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 = get_gt(h);
+        set_gt(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
+          set_bf(h, 0);
+        } else {
+          // num_sub is a power of 2
+          set_bf(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++;
+      set_lt(h, child);
+
+      // Put h into stack of less parents.
+      set_gt(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 get_lt(handle h) { return abs.get_less(h); }
+  void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
+
+  handle get_gt(handle h) { return abs.get_greater(h); }
+  void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
+
+  int get_bf(handle h) { return abs.get_balance_factor(h); }
+  void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
+
+  int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
+  int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(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 (get_bf(bal_h) > 0) {
+      // "Greater than" subtree is deeper.
+
+      deep_h = get_gt(bal_h);
+
+      if (get_bf(deep_h) < 0) {
+        handle old_h = bal_h;
+        bal_h = get_lt(deep_h);
+
+        set_gt(old_h, get_lt(bal_h));
+        set_lt(deep_h, get_gt(bal_h));
+        set_lt(bal_h, old_h);
+        set_gt(bal_h, deep_h);
+
+        int bf = get_bf(bal_h);
+        if (bf != 0) {
+          if (bf > 0) {
+            set_bf(old_h, -1);
+            set_bf(deep_h, 0);
+          } else {
+            set_bf(deep_h, 1);
+            set_bf(old_h, 0);
+          }
+          set_bf(bal_h, 0);
+        } else {
+          set_bf(old_h, 0);
+          set_bf(deep_h, 0);
+        }
+      } else {
+        set_gt(bal_h, get_lt(deep_h));
+        set_lt(deep_h, bal_h);
+        if (get_bf(deep_h) == 0) {
+          set_bf(deep_h, -1);
+          set_bf(bal_h, 1);
+        } else {
+          set_bf(deep_h, 0);
+          set_bf(bal_h, 0);
+        }
+        bal_h = deep_h;
+      }
+    } else {
+      // "Less than" subtree is deeper.
+
+      deep_h = get_lt(bal_h);
+
+      if (get_bf(deep_h) > 0) {
+        handle old_h = bal_h;
+        bal_h = get_gt(deep_h);
+        set_lt(old_h, get_gt(bal_h));
+        set_gt(deep_h, get_lt(bal_h));
+        set_gt(bal_h, old_h);
+        set_lt(bal_h, deep_h);
+
+        int bf = get_bf(bal_h);
+        if (bf != 0) {
+          if (bf < 0) {
+            set_bf(old_h, 1);
+            set_bf(deep_h, 0);
+          } else {
+            set_bf(deep_h, -1);
+            set_bf(old_h, 0);
+          }
+          set_bf(bal_h, 0);
+        } else {
+          set_bf(old_h, 0);
+          set_bf(deep_h, 0);
+        }
+      } else {
+        set_lt(bal_h, get_gt(deep_h));
+        set_gt(deep_h, bal_h);
+        if (get_bf(deep_h) == 0) {
+          set_bf(deep_h, 1);
+          set_bf(bal_h, -1);
+        } else {
+          set_bf(deep_h, 0);
+          set_bf(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) {
+  set_lt(h, null());
+  set_gt(h, null());
+  set_bf(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 (get_bf(hh) != 0) {
+        unbal = hh;
+        parent_unbal = parent;
+        unbal_depth = depth;
+      }
+      cmp = cmp_n_n(h, hh);
+      if (cmp == 0) {
+        // Duplicate key.
+        return hh;
+      }
+      parent = hh;
+      hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
+      branch[depth++] = cmp > 0;
+    } while (hh != null());
+
+    //  Add node to insert as leaf of tree.
+    if (cmp < 0)
+      set_lt(parent, h);
+    else
+      set_gt(parent, h);
+
+    depth = unbal_depth;
+
+    if (unbal == null()) {
+      hh = abs.root;
+    } else {
+      cmp = branch[depth++] ? 1 : -1;
+      unbal_bf = get_bf(unbal);
+      if (cmp < 0)
+        unbal_bf--;
+      else  // cmp > 0
+        unbal_bf++;
+      hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
+      if ((unbal_bf != -2) && (unbal_bf != 2)) {
+        // No rebalancing of tree is necessary.
+        set_bf(unbal, unbal_bf);
+        unbal = null();
+      }
+    }
+
+    if (hh != null()) {
+      while (h != hh) {
+        cmp = branch[depth++] ? 1 : -1;
+        if (cmp < 0) {
+          set_bf(hh, -1);
+          hh = get_lt(hh);
+        } else {  // cmp > 0
+          set_bf(hh, 1);
+          hh = get_gt(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)
+          set_lt(parent_unbal, unbal);
+        else  // cmp > 0
+          set_gt(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 = (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 = cmp_k_n(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 ? get_lt(h) : get_gt(h);
+  }
+
+  return match_h;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search_least() {
+  handle h = abs.root, parent = null();
+
+  while (h != null()) {
+    parent = h;
+    h = get_lt(h);
+  }
+
+  return parent;
+}
+
+template <class Abstractor, unsigned maxDepth, class BSet>
+inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
+AVLTree<Abstractor, maxDepth, BSet>::search_greatest() {
+  handle h = abs.root, parent = null();
+
+  while (h != null()) {
+    parent = h;
+    h = get_gt(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 = cmp_k_n(k, h);
+    if (cmp == 0) {
+      // Found node to remove.
+      break;
+    }
+    parent = h;
+    h = cmp < 0 ? get_lt(h) : get_gt(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 (get_bf(h) < 0) {
+    child = get_lt(h);
+    branch[depth] = false;
+    cmp = -1;
+  } else {
+    child = get_gt(h);
+    branch[depth] = true;
+    cmp = 1;
+  }
+  depth++;
+
+  if (child != null()) {
+    cmp = -cmp;
+    do {
+      parent = h;
+      h = child;
+      if (cmp < 0) {
+        child = get_lt(h);
+        branch[depth] = false;
+      } else {
+        child = get_gt(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 ? get_lt(h) : get_gt(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) {
+    set_lt(parent, child);
+  } else {
+    set_gt(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.
+    set_lt(h, get_lt(rm));
+    set_gt(h, get_gt(rm));
+    set_bf(h, get_bf(rm));
+    if (parent_rm == null()) {
+      abs.root = h;
+    } else {
+      depth = rm_depth - 1;
+      if (branch[depth])
+        set_gt(parent_rm, h);
+      else
+        set_lt(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 = get_gt(h);
+        set_gt(h, parent);
+      } else {
+        child = get_lt(h);
+        set_lt(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 = get_bf(h);
+        if (cmp < 0)
+          bf++;
+        else  // cmp > 0
+          bf--;
+        if ((bf == -2) || (bf == 2)) {
+          h = balance(h);
+          bf = get_bf(h);
+        } else {
+          set_bf(h, bf);
+        }
+        reduced_depth = (bf == 0);
+      }
+      if (parent == null())
+        break;
+      child = h;
+      h = parent;
+      cmp = branch[--depth] ? 1 : -1;
+      if (cmp < 0) {
+        parent = get_lt(h);
+        set_lt(h, child);
+      } else {
+        parent = get_gt(h);
+        set_gt(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 = cmp_n_n(new_node, h);
+    if (cmp == 0) {
+      // Found the node to substitute new one for.
+      break;
+    }
+    last_cmp = cmp;
+    parent = h;
+    h = cmp < 0 ? get_lt(h) : get_gt(h);
+  }
+
+  // Copy tree housekeeping fields from node in tree to new node.
+  set_lt(new_node, get_lt(h));
+  set_gt(new_node, get_gt(h));
+  set_bf(new_node, get_bf(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)
+      set_lt(parent, new_node);
+    else
+      set_gt(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
new file mode 100644
index 0000000..8e67a63
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/fixed_array.h
@@ -0,0 +1,62 @@
+// 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 m_data[i];
+  }
+
+  const T& operator[](size_t i) const {
+#if defined(ADDRESS_SANITIZER)
+    CHECK(i < Size);
+#endif
+    return m_data[i];
+  }
+
+  T* data() { return m_data; }
+  size_t size() const { return Size; }
+
+ private:
+  T m_data[Size];
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_FIXED_ARRAY_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_comparator.h b/content/browser/indexed_db/leveldb/leveldb_comparator.h
new file mode 100644
index 0000000..920d97e
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_comparator.h
@@ -0,0 +1,24 @@
+// 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_COMPARATOR_H_
+#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_COMPARATOR_H_
+
+#include "base/string16.h"
+
+namespace content {
+
+class LevelDBSlice;
+
+class LevelDBComparator {
+ public:
+  virtual ~LevelDBComparator() {}
+
+  virtual int Compare(const LevelDBSlice& a, const LevelDBSlice& b) const = 0;
+  virtual const char* Name() const = 0;
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_COMPARATOR_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_database.cc b/content/browser/indexed_db/leveldb/leveldb_database.cc
new file mode 100644
index 0000000..0a8307c
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_database.cc
@@ -0,0 +1,361 @@
+// 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_database.h"
+
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/metrics/histogram.h"
+#include "base/string16.h"
+#include "base/sys_info.h"
+#include "base/utf_string_conversions.h"
+#include "content/browser/indexed_db/leveldb/leveldb_comparator.h"
+#include "content/browser/indexed_db/leveldb/leveldb_iterator.h"
+#include "content/browser/indexed_db/leveldb/leveldb_slice.h"
+#include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
+#include "third_party/leveldatabase/env_idb.h"
+#include "third_party/leveldatabase/src/helpers/memenv/memenv.h"
+#include "third_party/leveldatabase/src/include/leveldb/comparator.h"
+#include "third_party/leveldatabase/src/include/leveldb/db.h"
+#include "third_party/leveldatabase/src/include/leveldb/env.h"
+#include "third_party/leveldatabase/src/include/leveldb/slice.h"
+
+namespace content {
+
+static leveldb::Slice MakeSlice(const std::vector<char>& value) {
+  return leveldb::Slice(&*value.begin(), value.size());
+}
+
+static leveldb::Slice MakeSlice(const LevelDBSlice& s) {
+  return leveldb::Slice(s.begin(), s.end() - s.begin());
+}
+
+static LevelDBSlice MakeLevelDBSlice(const leveldb::Slice& s) {
+  return LevelDBSlice(s.data(), s.data() + s.size());
+}
+
+class ComparatorAdapter : public leveldb::Comparator {
+ public:
+  explicit ComparatorAdapter(const LevelDBComparator* comparator)
+      : comparator_(comparator) {}
+
+  virtual int Compare(const leveldb::Slice& a, const leveldb::Slice& b) const
+      OVERRIDE {
+    return comparator_->Compare(MakeLevelDBSlice(a), MakeLevelDBSlice(b));
+  }
+
+  virtual const char* Name() const OVERRIDE { return comparator_->Name(); }
+
+  // TODO(jsbell): Support the methods below in the future.
+  virtual void FindShortestSeparator(std::string* start,
+                                     const leveldb::Slice& limit) const
+      OVERRIDE {}
+  virtual void FindShortSuccessor(std::string* key) const OVERRIDE {}
+
+ private:
+  const LevelDBComparator* comparator_;
+};
+
+LevelDBSnapshot::LevelDBSnapshot(LevelDBDatabase* db)
+    : db_(db->db_.get()), snapshot_(db_->GetSnapshot()) {}
+
+LevelDBSnapshot::~LevelDBSnapshot() { db_->ReleaseSnapshot(snapshot_); }
+
+LevelDBDatabase::LevelDBDatabase() {}
+
+LevelDBDatabase::~LevelDBDatabase() {
+  // db_'s destructor uses comparator_adapter_; order of deletion is important.
+  db_.reset();
+  comparator_adapter_.reset();
+  env_.reset();
+}
+
+static leveldb::Status OpenDB(leveldb::Comparator* comparator,
+                              leveldb::Env* env,
+                              const base::FilePath& path,
+                              leveldb::DB** db) {
+  leveldb::Options options;
+  options.comparator = comparator;
+  options.create_if_missing = true;
+  options.paranoid_checks = true;
+
+  // Marking compression as explicitly off so snappy support can be
+  // compiled in for other leveldb clients without implicitly enabling
+  // it for IndexedDB. http://crbug.com/81384
+  options.compression = leveldb::kNoCompression;
+
+  // 20 max_open_files is the minimum LevelDB allows but its cache behaves
+  // poorly with less than 4 files per shard. As of this writing the latest
+  // leveldb (1.9) hardcodes 16 shards. See
+  // https://code.google.com/p/chromium/issues/detail?id=227313#c11
+  options.max_open_files = 80;
+  options.env = env;
+
+  // ChromiumEnv assumes UTF8, converts back to FilePath before using.
+  return leveldb::DB::Open(options, path.AsUTF8Unsafe(), db);
+}
+
+bool LevelDBDatabase::Destroy(const base::FilePath& file_name) {
+  leveldb::Options options;
+  options.env = leveldb::IDBEnv();
+  // ChromiumEnv assumes UTF8, converts back to FilePath before using.
+  const leveldb::Status s =
+      leveldb::DestroyDB(file_name.AsUTF8Unsafe(), options);
+  return s.ok();
+}
+
+static void HistogramFreeSpace(const char* type,
+                               const base::FilePath& file_name) {
+  string16 name = ASCIIToUTF16("WebCore.IndexedDB.LevelDB.Open") +
+                  ASCIIToUTF16(type) + ASCIIToUTF16("FreeDiskSpace");
+  int64 free_disk_space_in_k_bytes =
+      base::SysInfo::AmountOfFreeDiskSpace(file_name) / 1024;
+  if (free_disk_space_in_k_bytes < 0) {
+    base::Histogram::FactoryGet(
+        "WebCore.IndexedDB.LevelDB.FreeDiskSpaceFailure",
+        1,
+        2 /*boundary*/,
+        2 /*boundary*/ + 1,
+        base::HistogramBase::kUmaTargetedHistogramFlag)->Add(1 /*sample*/);
+    return;
+  }
+  int clamped_disk_space_k_bytes =
+      free_disk_space_in_k_bytes > INT_MAX ? INT_MAX
+                                           : free_disk_space_in_k_bytes;
+  const uint64 histogram_max = static_cast<uint64>(1e9);
+  COMPILE_ASSERT(histogram_max <= INT_MAX, histogram_max_too_big);
+  base::Histogram::FactoryGet(UTF16ToUTF8(name),
+                              1,
+                              histogram_max,
+                              11 /*buckets*/,
+                              base::HistogramBase::kUmaTargetedHistogramFlag)
+      ->Add(clamped_disk_space_k_bytes);
+}
+
+static void HistogramLevelDBError(const char* histogram_name,
+                                  const leveldb::Status& s) {
+  DCHECK(!s.ok());
+  enum {
+    LEVEL_DB_NOT_FOUND,
+    LEVEL_DB_CORRUPTION,
+    LEVEL_DB_IO_ERROR,
+    LEVEL_DB_OTHER,
+    LEVEL_DB_MAX_ERROR
+  };
+  int leveldb_error = LEVEL_DB_OTHER;
+  if (s.IsNotFound())
+    leveldb_error = LEVEL_DB_NOT_FOUND;
+  else if (s.IsCorruption())
+    leveldb_error = LEVEL_DB_CORRUPTION;
+  else if (s.IsIOError())
+    leveldb_error = LEVEL_DB_IO_ERROR;
+  base::Histogram::FactoryGet(histogram_name,
+                              1,
+                              LEVEL_DB_MAX_ERROR,
+                              LEVEL_DB_MAX_ERROR + 1,
+                              base::HistogramBase::kUmaTargetedHistogramFlag)
+      ->Add(leveldb_error);
+}
+
+scoped_ptr<LevelDBDatabase> LevelDBDatabase::Open(
+    const base::FilePath& file_name,
+    const LevelDBComparator* comparator) {
+  scoped_ptr<ComparatorAdapter> comparator_adapter(
+      new ComparatorAdapter(comparator));
+
+  leveldb::DB* db;
+  const leveldb::Status s =
+      OpenDB(comparator_adapter.get(), leveldb::IDBEnv(), file_name, &db);
+
+  if (!s.ok()) {
+    HistogramLevelDBError("WebCore.IndexedDB.LevelDBOpenErrors", s);
+    HistogramFreeSpace("Failure", file_name);
+
+    LOG(ERROR) << "Failed to open LevelDB database from "
+               << file_name.AsUTF8Unsafe() << "," << s.ToString();
+    return scoped_ptr<LevelDBDatabase>();
+  }
+
+  HistogramFreeSpace("Success", file_name);
+
+  scoped_ptr<LevelDBDatabase> result(new LevelDBDatabase);
+  result->db_ = make_scoped_ptr(db);
+  result->comparator_adapter_ = comparator_adapter.Pass();
+  result->comparator_ = comparator;
+
+  return result.Pass();
+}
+
+scoped_ptr<LevelDBDatabase> LevelDBDatabase::OpenInMemory(
+    const LevelDBComparator* comparator) {
+  scoped_ptr<ComparatorAdapter> comparator_adapter(
+      new ComparatorAdapter(comparator));
+  scoped_ptr<leveldb::Env> in_memory_env(leveldb::NewMemEnv(leveldb::IDBEnv()));
+
+  leveldb::DB* db;
+  const leveldb::Status s = OpenDB(
+      comparator_adapter.get(), in_memory_env.get(), base::FilePath(), &db);
+
+  if (!s.ok()) {
+    LOG(ERROR) << "Failed to open in-memory LevelDB database: " << s.ToString();
+    return scoped_ptr<LevelDBDatabase>();
+  }
+
+  scoped_ptr<LevelDBDatabase> result(new LevelDBDatabase);
+  result->env_ = in_memory_env.Pass();
+  result->db_ = make_scoped_ptr(db);
+  result->comparator_adapter_ = comparator_adapter.Pass();
+  result->comparator_ = comparator;
+
+  return result.Pass();
+}
+
+bool LevelDBDatabase::Put(const LevelDBSlice& key,
+                          const std::vector<char>& value) {
+  leveldb::WriteOptions write_options;
+  write_options.sync = true;
+
+  const leveldb::Status s =
+      db_->Put(write_options, MakeSlice(key), MakeSlice(value));
+  if (s.ok())
+    return true;
+  LOG(ERROR) << "LevelDB put failed: " << s.ToString();
+  return false;
+}
+
+bool LevelDBDatabase::Remove(const LevelDBSlice& key) {
+  leveldb::WriteOptions write_options;
+  write_options.sync = true;
+
+  const leveldb::Status s = db_->Delete(write_options, MakeSlice(key));
+  if (s.ok())
+    return true;
+  if (s.IsNotFound())
+    return false;
+  LOG(ERROR) << "LevelDB remove failed: " << s.ToString();
+  return false;
+}
+
+bool LevelDBDatabase::Get(const LevelDBSlice& key,
+                          std::vector<char>& value,
+                          bool& found,
+                          const LevelDBSnapshot* snapshot) {
+  found = false;
+  std::string result;
+  leveldb::ReadOptions read_options;
+  read_options.verify_checksums = true;  // TODO(jsbell): Disable this if the
+                                         // performance impact is too great.
+  read_options.snapshot = snapshot ? snapshot->snapshot_ : 0;
+
+  const leveldb::Status s = db_->Get(read_options, MakeSlice(key), &result);
+  if (s.ok()) {
+    found = true;
+    value.clear();
+    value.insert(value.end(), result.begin(), result.end());
+    return true;
+  }
+  if (s.IsNotFound())
+    return true;
+  LOG(ERROR) << "LevelDB get failed: " << s.ToString();
+  return false;
+}
+
+bool LevelDBDatabase::Write(LevelDBWriteBatch& write_batch) {
+  leveldb::WriteOptions write_options;
+  write_options.sync = true;
+
+  const leveldb::Status s =
+      db_->Write(write_options, write_batch.write_batch_.get());
+  if (s.ok())
+    return true;
+  HistogramLevelDBError("WebCore.IndexedDB.LevelDBWriteErrors", s);
+  LOG(ERROR) << "LevelDB write failed: " << s.ToString();
+  return false;
+}
+
+namespace {
+class IteratorImpl : public LevelDBIterator {
+ public:
+  virtual ~IteratorImpl() {}
+
+  virtual bool IsValid() const OVERRIDE;
+  virtual void SeekToLast() OVERRIDE;
+  virtual void Seek(const LevelDBSlice& target) OVERRIDE;
+  virtual void Next() OVERRIDE;
+  virtual void Prev() OVERRIDE;
+  virtual LevelDBSlice Key() const OVERRIDE;
+  virtual LevelDBSlice Value() const OVERRIDE;
+
+ private:
+  friend class content::LevelDBDatabase;
+  IteratorImpl(scoped_ptr<leveldb::Iterator> iterator);
+  void CheckStatus();
+
+  scoped_ptr<leveldb::Iterator> iterator_;
+};
+}
+
+IteratorImpl::IteratorImpl(scoped_ptr<leveldb::Iterator> it)
+    : iterator_(it.Pass()) {}
+
+void IteratorImpl::CheckStatus() {
+  const leveldb::Status s = iterator_->status();
+  if (!s.ok())
+    LOG(ERROR) << "LevelDB iterator error: " << s.ToString();
+}
+
+bool IteratorImpl::IsValid() const { return iterator_->Valid(); }
+
+void IteratorImpl::SeekToLast() {
+  iterator_->SeekToLast();
+  CheckStatus();
+}
+
+void IteratorImpl::Seek(const LevelDBSlice& target) {
+  iterator_->Seek(MakeSlice(target));
+  CheckStatus();
+}
+
+void IteratorImpl::Next() {
+  DCHECK(IsValid());
+  iterator_->Next();
+  CheckStatus();
+}
+
+void IteratorImpl::Prev() {
+  DCHECK(IsValid());
+  iterator_->Prev();
+  CheckStatus();
+}
+
+LevelDBSlice IteratorImpl::Key() const {
+  DCHECK(IsValid());
+  return MakeLevelDBSlice(iterator_->key());
+}
+
+LevelDBSlice IteratorImpl::Value() const {
+  DCHECK(IsValid());
+  return MakeLevelDBSlice(iterator_->value());
+}
+
+scoped_ptr<LevelDBIterator> LevelDBDatabase::CreateIterator(
+    const LevelDBSnapshot* snapshot) {
+  leveldb::ReadOptions read_options;
+  read_options.verify_checksums = true;  // TODO(jsbell): Disable this if the
+                                         // performance impact is too great.
+  read_options.snapshot = snapshot ? snapshot->snapshot_ : 0;
+  scoped_ptr<leveldb::Iterator> i(db_->NewIterator(read_options));
+  if (!i)  // TODO(jsbell): Double check if we actually need to check this.
+    return scoped_ptr<LevelDBIterator>();
+  return scoped_ptr<LevelDBIterator>(new IteratorImpl(i.Pass()));
+}
+
+const LevelDBComparator* LevelDBDatabase::Comparator() const {
+  return comparator_;
+}
+
+}  // namespace content
diff --git a/content/browser/indexed_db/leveldb/leveldb_database.h b/content/browser/indexed_db/leveldb/leveldb_database.h
new file mode 100644
index 0000000..0c7427b
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_database.h
@@ -0,0 +1,75 @@
+// 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_DATABASE_H_
+#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_DATABASE_H_
+
+#include <vector>
+
+#include "base/files/file_path.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/string16.h"
+#include "content/common/content_export.h"
+
+namespace leveldb {
+class Comparator;
+class DB;
+class Env;
+class Snapshot;
+}
+
+namespace content {
+
+class LevelDBComparator;
+class LevelDBDatabase;
+class LevelDBIterator;
+class LevelDBSlice;
+class LevelDBWriteBatch;
+
+class LevelDBSnapshot {
+ private:
+  friend class LevelDBDatabase;
+  friend class LevelDBTransaction;
+
+  explicit LevelDBSnapshot(LevelDBDatabase* db);
+  ~LevelDBSnapshot();
+
+  leveldb::DB* db_;
+  const leveldb::Snapshot* snapshot_;
+};
+
+class CONTENT_EXPORT LevelDBDatabase {
+ public:
+  static scoped_ptr<LevelDBDatabase> Open(const base::FilePath& file_name,
+                                          const LevelDBComparator* comparator);
+  static scoped_ptr<LevelDBDatabase> OpenInMemory(
+      const LevelDBComparator* comparator);
+  static bool Destroy(const base::FilePath& file_name);
+  virtual ~LevelDBDatabase();
+
+  bool Put(const LevelDBSlice& key, const std::vector<char>& value);
+  bool Remove(const LevelDBSlice& key);
+  virtual bool Get(const LevelDBSlice& key,
+                   std::vector<char>& value,
+                   bool& found,
+                   const LevelDBSnapshot* = 0);
+  bool Write(LevelDBWriteBatch& batch);
+  scoped_ptr<LevelDBIterator> CreateIterator(const LevelDBSnapshot* = 0);
+  const LevelDBComparator* Comparator() const;
+
+ protected:
+  LevelDBDatabase();
+
+ private:
+  friend class LevelDBSnapshot;
+
+  scoped_ptr<leveldb::Env> env_;
+  scoped_ptr<leveldb::Comparator> comparator_adapter_;
+  scoped_ptr<leveldb::DB> db_;
+  const LevelDBComparator* comparator_;
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_DATABASE_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_iterator.h b/content/browser/indexed_db/leveldb/leveldb_iterator.h
new file mode 100644
index 0000000..b78747f
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_iterator.h
@@ -0,0 +1,26 @@
+// 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_ITERATOR_H_
+#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_ITERATOR_H_
+
+#include "content/browser/indexed_db/leveldb/leveldb_slice.h"
+
+namespace content {
+
+class LevelDBIterator {
+ public:
+  virtual ~LevelDBIterator() {}
+  virtual bool IsValid() const = 0;
+  virtual void SeekToLast() = 0;
+  virtual void Seek(const LevelDBSlice& target) = 0;
+  virtual void Next() = 0;
+  virtual void Prev() = 0;
+  virtual LevelDBSlice Key() const = 0;
+  virtual LevelDBSlice Value() const = 0;
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_ITERATOR_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_slice.h b/content/browser/indexed_db/leveldb/leveldb_slice.h
new file mode 100644
index 0000000..3419c93
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_slice.h
@@ -0,0 +1,37 @@
+// 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_SLICE_H_
+#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_SLICE_H_
+
+#include <vector>
+
+#include "base/logging.h"
+
+namespace content {
+
+class LevelDBSlice {
+ public:
+  LevelDBSlice(const char* begin, const char* end) : begin_(begin), end_(end) {
+    DCHECK_GE(end_, begin_);
+  }
+
+  explicit LevelDBSlice(const std::vector<char>& v)
+      : begin_(&*v.begin()), end_(&*v.rbegin() + 1) {
+    DCHECK_GE(end_, begin_);
+  }
+
+  ~LevelDBSlice() {}
+
+  const char* begin() const { return begin_; }
+  const char* end() const { return end_; }
+
+ private:
+  const char* begin_;
+  const char* end_;
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_SLICE_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.cc b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
new file mode 100644
index 0000000..a8b3a3d
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_transaction.cc
@@ -0,0 +1,490 @@
+// 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 "content/browser/indexed_db/leveldb/leveldb_database.h"
+#include "content/browser/indexed_db/leveldb/leveldb_slice.h"
+#include "content/browser/indexed_db/leveldb/leveldb_write_batch.h"
+#include "third_party/leveldatabase/src/include/leveldb/db.h"
+
+namespace content {
+
+scoped_refptr<LevelDBTransaction> LevelDBTransaction::Create(
+    LevelDBDatabase* db) {
+  return make_scoped_refptr(new LevelDBTransaction(db));
+}
+
+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.start_iter_least(tree_);
+
+  std::vector<AVLTreeNode*> nodes;
+
+  while (*iterator) {
+    nodes.push_back(*iterator);
+    ++iterator;
+  }
+  tree_.purge();
+
+  for (size_t i = 0; i < nodes.size(); ++i)
+    delete nodes[i];
+}
+
+LevelDBTransaction::~LevelDBTransaction() { ClearTree(); }
+
+static void InitVector(const LevelDBSlice& slice, std::vector<char>* vector) {
+  vector->clear();
+  vector->insert(vector->end(), slice.begin(), slice.end());
+}
+
+void LevelDBTransaction::Set(const LevelDBSlice& key,
+                             const std::vector<char>& value,
+                             bool deleted) {
+  DCHECK(!finished_);
+  bool new_node = false;
+  AVLTreeNode* node = tree_.search(key);
+
+  if (!node) {
+    node = new AVLTreeNode;
+    InitVector(key, &node->key);
+    tree_.insert(node);
+    new_node = true;
+  }
+  node->value = value;
+  node->deleted = deleted;
+
+  if (new_node)
+    NotifyIteratorsOfTreeChange();
+}
+
+void LevelDBTransaction::Put(const LevelDBSlice& key,
+                             const std::vector<char>& value) {
+  Set(key, value, false);
+}
+
+void LevelDBTransaction::Remove(const LevelDBSlice& key) {
+  Set(key, std::vector<char>(), true);
+}
+
+bool LevelDBTransaction::Get(const LevelDBSlice& key,
+                             std::vector<char>& value,
+                             bool& found) {
+  found = false;
+  DCHECK(!finished_);
+  AVLTreeNode* node = tree_.search(key);
+
+  if (node) {
+    if (node->deleted)
+      return true;
+
+    value = node->value;
+    found = true;
+    return true;
+  }
+
+  bool ok = db_->Get(key, value, found, &snapshot_);
+  if (!ok) {
+    DCHECK(!found);
+    return false;
+  }
+  return true;
+}
+
+bool LevelDBTransaction::Commit() {
+  DCHECK(!finished_);
+
+  if (tree_.is_empty()) {
+    finished_ = true;
+    return true;
+  }
+
+  scoped_ptr<LevelDBWriteBatch> write_batch = LevelDBWriteBatch::Create();
+
+  TreeType::Iterator iterator;
+  iterator.start_iter_least(tree_);
+
+  while (*iterator) {
+    AVLTreeNode* node = *iterator;
+    if (!node->deleted)
+      write_batch->Put(LevelDBSlice(node->key), LevelDBSlice(node->value));
+    else
+      write_batch->Remove(LevelDBSlice(node->key));
+    ++iterator;
+  }
+
+  if (!db_->Write(*write_batch))
+    return false;
+
+  ClearTree();
+  finished_ = true;
+  return true;
+}
+
+void LevelDBTransaction::Rollback() {
+  DCHECK(!finished_);
+  finished_ = true;
+  ClearTree();
+}
+
+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));
+}
+
+bool LevelDBTransaction::TreeIterator::IsValid() const { return !!*iterator_; }
+
+void LevelDBTransaction::TreeIterator::SeekToLast() {
+  iterator_.start_iter_greatest(*tree_);
+  if (IsValid())
+    key_ = (*iterator_)->key;
+}
+
+void LevelDBTransaction::TreeIterator::Seek(const LevelDBSlice& target) {
+  iterator_.start_iter(*tree_, target, TreeType::EQUAL);
+  if (!IsValid())
+    iterator_.start_iter(*tree_, target, TreeType::GREATER);
+
+  if (IsValid())
+    key_ = (*iterator_)->key;
+}
+
+void LevelDBTransaction::TreeIterator::Next() {
+  DCHECK(IsValid());
+  ++iterator_;
+  if (IsValid()) {
+    DCHECK(transaction_->comparator_->Compare(LevelDBSlice((*iterator_)->key),
+                                              LevelDBSlice(key_)) >
+           0);
+    (void) transaction_;
+    key_ = (*iterator_)->key;
+  }
+}
+
+void LevelDBTransaction::TreeIterator::Prev() {
+  DCHECK(IsValid());
+  --iterator_;
+  if (IsValid()) {
+    DCHECK(tree_->abstractor().comparator_->Compare(
+               LevelDBSlice((*iterator_)->key), LevelDBSlice(key_)) <
+           0);
+    key_ = (*iterator_)->key;
+  }
+}
+
+LevelDBSlice LevelDBTransaction::TreeIterator::Key() const {
+  DCHECK(IsValid());
+  return LevelDBSlice(key_);
+}
+
+LevelDBSlice LevelDBTransaction::TreeIterator::Value() const {
+  DCHECK(IsValid());
+  DCHECK(!IsDeleted());
+  return LevelDBSlice((*iterator_)->value);
+}
+
+bool LevelDBTransaction::TreeIterator::IsDeleted() const {
+  DCHECK(IsValid());
+  return (*iterator_)->deleted;
+}
+
+void LevelDBTransaction::TreeIterator::Reset() {
+  DCHECK(IsValid());
+  iterator_.start_iter(*tree_, LevelDBSlice(key_), TreeType::EQUAL);
+  DCHECK(IsValid());
+}
+
+LevelDBTransaction::TreeIterator::~TreeIterator() {}
+
+LevelDBTransaction::TreeIterator::TreeIterator(LevelDBTransaction* transaction)
+    : tree_(&transaction->tree_), transaction_(transaction) {}
+
+scoped_ptr<LevelDBTransaction::TransactionIterator>
+LevelDBTransaction::TransactionIterator::Create(
+    scoped_refptr<LevelDBTransaction> transaction) {
+  return make_scoped_ptr(new TransactionIterator(transaction));
+}
+
+LevelDBTransaction::TransactionIterator::TransactionIterator(
+    scoped_refptr<LevelDBTransaction> transaction)
+    : transaction_(transaction),
+      comparator_(transaction_->comparator_),
+      tree_iterator_(TreeIterator::Create(transaction_.get())),
+      db_iterator_(transaction_->db_->CreateIterator(&transaction_->snapshot_)),
+      current_(0),
+      direction_(FORWARD),
+      tree_changed_(false) {
+  transaction_->RegisterIterator(this);
+}
+
+LevelDBTransaction::TransactionIterator::~TransactionIterator() {
+  transaction_->UnregisterIterator(this);
+}
+
+bool LevelDBTransaction::TransactionIterator::IsValid() const {
+  return !!current_;
+}
+
+void LevelDBTransaction::TransactionIterator::SeekToLast() {
+  tree_iterator_->SeekToLast();
+  db_iterator_->SeekToLast();
+  direction_ = REVERSE;
+
+  HandleConflictsAndDeletes();
+  SetCurrentIteratorToLargestKey();
+}
+
+void LevelDBTransaction::TransactionIterator::Seek(const LevelDBSlice& target) {
+  tree_iterator_->Seek(target);
+  db_iterator_->Seek(target);
+  direction_ = FORWARD;
+
+  HandleConflictsAndDeletes();
+  SetCurrentIteratorToSmallestKey();
+}
+
+void LevelDBTransaction::TransactionIterator::Next() {
+  DCHECK(IsValid());
+  if (tree_changed_)
+    RefreshTreeIterator();
+
+  if (direction_ != FORWARD) {
+    // Ensure the non-current iterator is positioned after Key().
+
+    LevelDBIterator* non_current =
+        (current_ == db_iterator_.get()) ? tree_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().
+
+    DCHECK(!non_current->IsValid() ||
+           comparator_->Compare(non_current->Key(), Key()) > 0);
+
+    direction_ = FORWARD;
+  }
+
+  current_->Next();
+  HandleConflictsAndDeletes();
+  SetCurrentIteratorToSmallestKey();
+}
+
+void LevelDBTransaction::TransactionIterator::Prev() {
+  DCHECK(IsValid());
+  if (tree_changed_)
+    RefreshTreeIterator();
+
+  if (direction_ != REVERSE) {
+    // Ensure the non-current iterator is positioned before Key().
+
+    LevelDBIterator* non_current =
+        (current_ == db_iterator_.get()) ? tree_iterator_.get()
+                                         : db_iterator_.get();
+
+    non_current->Seek(Key());
+    if (non_current->IsValid()) {
+      // Iterator is at first entry >= Key().
+      // Step back once to entry < key.
+      // This is why we don't check for the keys being the same before
+      // stepping, like we do in Next() above.
+      non_current->Prev();
+    } else {
+      non_current->SeekToLast();  // Iterator has no entries >= Key(). Position
+                                  // at last entry.
+    }
+    DCHECK(!non_current->IsValid() ||
+           comparator_->Compare(non_current->Key(), Key()) < 0);
+
+    direction_ = REVERSE;
+  }
+
+  current_->Prev();
+  HandleConflictsAndDeletes();
+  SetCurrentIteratorToLargestKey();
+}
+
+LevelDBSlice LevelDBTransaction::TransactionIterator::Key() const {
+  DCHECK(IsValid());
+  if (tree_changed_)
+    RefreshTreeIterator();
+  return current_->Key();
+}
+
+LevelDBSlice LevelDBTransaction::TransactionIterator::Value() const {
+  DCHECK(IsValid());
+  if (tree_changed_)
+    RefreshTreeIterator();
+  return current_->Value();
+}
+
+void LevelDBTransaction::TransactionIterator::TreeChanged() {
+  tree_changed_ = true;
+}
+
+void LevelDBTransaction::TransactionIterator::RefreshTreeIterator() const {
+  DCHECK(tree_changed_);
+
+  tree_changed_ = false;
+
+  if (tree_iterator_->IsValid() && tree_iterator_.get() == current_) {
+    tree_iterator_->Reset();
+    return;
+  }
+
+  if (db_iterator_->IsValid()) {
+
+    // There could be new nodes in the tree 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.
+    } 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();
+    }
+  }
+}
+
+bool LevelDBTransaction::TransactionIterator::TreeIteratorIsLower() const {
+  return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) < 0;
+}
+
+bool LevelDBTransaction::TransactionIterator::TreeIteratorIsHigher() const {
+  return comparator_->Compare(tree_iterator_->Key(), db_iterator_->Key()) > 0;
+}
+
+void LevelDBTransaction::TransactionIterator::HandleConflictsAndDeletes() {
+  bool loop = true;
+
+  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
+      // database iterator another step.
+      if (direction_ == FORWARD)
+        db_iterator_->Next();
+      else
+        db_iterator_->Prev();
+    }
+
+    // Skip over delete markers in the tree iterator until it catches up with
+    // the db iterator.
+    if (tree_iterator_->IsValid() && tree_iterator_->IsDeleted()) {
+      if (direction_ == FORWARD &&
+          (!db_iterator_->IsValid() || TreeIteratorIsLower())) {
+        tree_iterator_->Next();
+        loop = true;
+      } else if (direction_ == REVERSE &&
+                 (!db_iterator_->IsValid() || TreeIteratorIsHigher())) {
+        tree_iterator_->Prev();
+        loop = true;
+      }
+    }
+  }
+}
+
+void
+LevelDBTransaction::TransactionIterator::SetCurrentIteratorToSmallestKey() {
+  LevelDBIterator* smallest = 0;
+
+  if (tree_iterator_->IsValid())
+    smallest = tree_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;
+
+  if (tree_iterator_->IsValid())
+    largest = tree_iterator_.get();
+
+  if (db_iterator_->IsValid()) {
+    if (!largest ||
+        comparator_->Compare(db_iterator_->Key(), largest->Key()) > 0)
+      largest = db_iterator_.get();
+  }
+
+  current_ = largest;
+}
+
+void LevelDBTransaction::RegisterIterator(TransactionIterator* iterator) {
+  DCHECK(iterators_.find(iterator) == iterators_.end());
+  iterators_.insert(iterator);
+}
+
+void LevelDBTransaction::UnregisterIterator(TransactionIterator* iterator) {
+  DCHECK(iterators_.find(iterator) != iterators_.end());
+  iterators_.erase(iterator);
+}
+
+void LevelDBTransaction::NotifyIteratorsOfTreeChange() {
+  for (std::set<TransactionIterator*>::iterator i = iterators_.begin();
+       i != iterators_.end();
+       ++i) {
+    TransactionIterator* transaction_iterator = *i;
+    transaction_iterator->TreeChanged();
+  }
+}
+
+scoped_ptr<LevelDBWriteOnlyTransaction> LevelDBWriteOnlyTransaction::Create(
+    LevelDBDatabase* db) {
+  return make_scoped_ptr(new LevelDBWriteOnlyTransaction(db));
+}
+
+LevelDBWriteOnlyTransaction::LevelDBWriteOnlyTransaction(LevelDBDatabase* db)
+    : db_(db), write_batch_(LevelDBWriteBatch::Create()), finished_(false) {}
+
+LevelDBWriteOnlyTransaction::~LevelDBWriteOnlyTransaction() {
+  write_batch_->Clear();
+}
+
+void LevelDBWriteOnlyTransaction::Remove(const LevelDBSlice& key) {
+  DCHECK(!finished_);
+  write_batch_->Remove(key);
+}
+
+bool LevelDBWriteOnlyTransaction::Commit() {
+  DCHECK(!finished_);
+
+  if (!db_->Write(*write_batch_))
+    return false;
+
+  finished_ = true;
+  write_batch_->Clear();
+  return true;
+}
+
+}  // namespace content
diff --git a/content/browser/indexed_db/leveldb/leveldb_transaction.h b/content/browser/indexed_db/leveldb/leveldb_transaction.h
new file mode 100644
index 0000000..39d1a30
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_transaction.h
@@ -0,0 +1,179 @@
+// 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 <set>
+#include <vector>
+
+#include "base/memory/ref_counted.h"
+#include "base/memory/scoped_ptr.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"
+#include "content/browser/indexed_db/leveldb/leveldb_slice.h"
+
+namespace content {
+
+class LevelDBWriteBatch;
+
+class CONTENT_EXPORT LevelDBTransaction
+    : public base::RefCounted<LevelDBTransaction> {
+ public:
+  static scoped_refptr<LevelDBTransaction> Create(LevelDBDatabase* db);
+
+  void Put(const LevelDBSlice& key, const std::vector<char>& value);
+  void Remove(const LevelDBSlice& key);
+  bool Get(const LevelDBSlice& key, std::vector<char>& value, bool& found);
+  bool Commit();
+  void Rollback();
+
+  scoped_ptr<LevelDBIterator> CreateIterator();
+
+ private:
+  LevelDBTransaction(LevelDBDatabase* db);
+  virtual ~LevelDBTransaction();
+  friend class base::RefCounted<LevelDBTransaction>;
+
+  struct AVLTreeNode {
+    AVLTreeNode();
+    ~AVLTreeNode();
+    std::vector<char> key;
+    std::vector<char> 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 LevelDBSlice key;
+
+    handle get_less(handle h) { return h->less; }
+    void set_less(handle h, handle less) { h->less = less; }
+    handle get_greater(handle h) { return h->greater; }
+    void set_greater(handle h, handle greater) { h->greater = greater; }
+
+    int get_balance_factor(handle h) { return h->balance_factor; }
+    void set_balance_factor(handle h, int bf) { h->balance_factor = bf; }
+
+    int compare_key_key(const key& ka, const key& kb) {
+      return comparator_->Compare(ka, kb);
+    }
+    int compare_key_node(const key& k, handle h) {
+      return compare_key_key(k, key(h->key));
+    }
+    int compare_node_node(handle ha, handle hb) {
+      return compare_key_key(key(ha->key), key(hb->key));
+    }
+
+    static handle null() { return 0; }
+
+    const LevelDBComparator* comparator_;
+  };
+
+  typedef AVLTree<AVLTreeAbstractor> TreeType;
+
+  class TreeIterator : public LevelDBIterator {
+   public:
+    static scoped_ptr<TreeIterator> Create(LevelDBTransaction* transaction);
+    virtual ~TreeIterator();
+
+    virtual bool IsValid() const OVERRIDE;
+    virtual void SeekToLast() OVERRIDE;
+    virtual void Seek(const LevelDBSlice& slice) OVERRIDE;
+    virtual void Next() OVERRIDE;
+    virtual void Prev() OVERRIDE;
+    virtual LevelDBSlice Key() const OVERRIDE;
+    virtual LevelDBSlice Value() const OVERRIDE;
+    bool IsDeleted() const;
+    void Reset();
+
+   private:
+    TreeIterator(LevelDBTransaction* transaction);
+    mutable TreeType::Iterator iterator_;  // Dereferencing this is non-const.
+    TreeType* tree_;
+    LevelDBTransaction* transaction_;
+    std::vector<char> key_;
+  };
+
+  class TransactionIterator : public LevelDBIterator {
+   public:
+    virtual ~TransactionIterator();
+    static scoped_ptr<TransactionIterator> Create(
+        scoped_refptr<LevelDBTransaction> transaction);
+
+    virtual bool IsValid() const OVERRIDE;
+    virtual void SeekToLast() OVERRIDE;
+    virtual void Seek(const LevelDBSlice& target) OVERRIDE;
+    virtual void Next() OVERRIDE;
+    virtual void Prev() OVERRIDE;
+    virtual LevelDBSlice Key() const OVERRIDE;
+    virtual LevelDBSlice Value() const OVERRIDE;
+    void TreeChanged();
+
+   private:
+    TransactionIterator(scoped_refptr<LevelDBTransaction> transaction);
+    void HandleConflictsAndDeletes();
+    void SetCurrentIteratorToSmallestKey();
+    void SetCurrentIteratorToLargestKey();
+    void RefreshTreeIterator() const;
+    bool TreeIteratorIsLower() const;
+    bool TreeIteratorIsHigher() const;
+
+    scoped_refptr<LevelDBTransaction> transaction_;
+    const LevelDBComparator* comparator_;
+    mutable scoped_ptr<TreeIterator> tree_iterator_;
+    scoped_ptr<LevelDBIterator> db_iterator_;
+    LevelDBIterator* current_;
+
+    enum Direction {
+      FORWARD,
+      REVERSE
+    };
+    Direction direction_;
+    mutable bool tree_changed_;
+  };
+
+  void Set(const LevelDBSlice& key,
+           const std::vector<char>& value,
+           bool deleted);
+  void ClearTree();
+  void RegisterIterator(TransactionIterator* iterator);
+  void UnregisterIterator(TransactionIterator* iterator);
+  void NotifyIteratorsOfTreeChange();
+
+  LevelDBDatabase* db_;
+  const LevelDBSnapshot snapshot_;
+  const LevelDBComparator* comparator_;
+  TreeType tree_;
+  bool finished_;
+  std::set<TransactionIterator*> iterators_;
+};
+
+class LevelDBWriteOnlyTransaction {
+ public:
+  static scoped_ptr<LevelDBWriteOnlyTransaction> Create(LevelDBDatabase* db);
+
+  ~LevelDBWriteOnlyTransaction();
+  void Remove(const LevelDBSlice& key);
+  bool Commit();
+
+ private:
+  LevelDBWriteOnlyTransaction(LevelDBDatabase* db);
+
+  LevelDBDatabase* db_;
+  scoped_ptr<LevelDBWriteBatch> write_batch_;
+  bool finished_;
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_TRANSACTION_H_
diff --git a/content/browser/indexed_db/leveldb/leveldb_unittest.cc b/content/browser/indexed_db/leveldb/leveldb_unittest.cc
new file mode 100644
index 0000000..20960d3
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_unittest.cc
@@ -0,0 +1,193 @@
+// 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 <algorithm>
+#include <cstring>
+#include <vector>
+
+#include "base/files/file_path.h"
+#include "base/files/scoped_temp_dir.h"
+#include "base/platform_file.h"
+#include "base/string16.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"
+#include "content/browser/indexed_db/leveldb/leveldb_slice.h"
+#include "content/browser/indexed_db/leveldb/leveldb_transaction.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace content {
+
+namespace {
+
+class SimpleComparator : public LevelDBComparator {
+ public:
+  virtual int Compare(const LevelDBSlice& a, const LevelDBSlice& b) const
+      OVERRIDE {
+    size_t len = std::min(a.end() - a.begin(), b.end() - b.begin());
+    return memcmp(a.begin(), b.begin(), len);
+  }
+  virtual const char* Name() const OVERRIDE { return "temp_comparator"; }
+};
+
+std::vector<char> EncodeString(const std::string& s) {
+  std::vector<char> ret(s.size());
+  for (size_t i = 0; i < s.size(); ++i)
+    ret[i] = s[i];
+  return ret;
+}
+
+TEST(LevelDBDatabaseTest, CorruptionTest) {
+  base::ScopedTempDir temp_directory;
+  ASSERT_TRUE(temp_directory.CreateUniqueTempDir());
+
+  const std::vector<char> key = EncodeString("key");
+  const std::vector<char> put_value = EncodeString("value");
+  std::vector<char> got_value;
+  SimpleComparator comparator;
+
+  scoped_ptr<LevelDBDatabase> leveldb =
+      LevelDBDatabase::Open(temp_directory.path(), &comparator);
+  EXPECT_TRUE(leveldb);
+  bool success = leveldb->Put(LevelDBSlice(key), put_value);
+  EXPECT_TRUE(success);
+  leveldb.Pass();
+  EXPECT_FALSE(leveldb);
+
+  leveldb = LevelDBDatabase::Open(temp_directory.path(), &comparator);
+  EXPECT_TRUE(leveldb);
+  bool found = false;
+  success = leveldb->Get(LevelDBSlice(key), got_value, found);
+  EXPECT_TRUE(success);
+  EXPECT_TRUE(found);
+  EXPECT_EQ(put_value, got_value);
+  leveldb.Pass();
+  EXPECT_FALSE(leveldb);
+
+  base::FilePath file_path = temp_directory.path().AppendASCII("CURRENT");
+  base::PlatformFile handle = base::CreatePlatformFile(
+      file_path,
+      base::PLATFORM_FILE_OPEN | base::PLATFORM_FILE_WRITE,
+      NULL,
+      NULL);
+  base::TruncatePlatformFile(handle, 0);
+  base::ClosePlatformFile(handle);
+
+  leveldb = LevelDBDatabase::Open(temp_directory.path(), &comparator);
+  EXPECT_FALSE(leveldb);
+
+  bool destroyed = LevelDBDatabase::Destroy(temp_directory.path());
+  EXPECT_TRUE(destroyed);
+
+  leveldb = LevelDBDatabase::Open(temp_directory.path(), &comparator);
+  EXPECT_TRUE(leveldb);
+  success = leveldb->Get(LevelDBSlice(key), got_value, found);
+  EXPECT_TRUE(success);
+  EXPECT_FALSE(found);
+}
+
+TEST(LevelDBDatabaseTest, Transaction) {
+  base::ScopedTempDir temp_directory;
+  ASSERT_TRUE(temp_directory.CreateUniqueTempDir());
+
+  const std::vector<char> key = EncodeString("key");
+  std::vector<char> got_value;
+  SimpleComparator comparator;
+
+  scoped_ptr<LevelDBDatabase> leveldb =
+      LevelDBDatabase::Open(temp_directory.path(), &comparator);
+  EXPECT_TRUE(leveldb);
+
+  const std::vector<char> old_value = EncodeString("value");
+  bool success = leveldb->Put(LevelDBSlice(key), old_value);
+  EXPECT_TRUE(success);
+
+  scoped_refptr<LevelDBTransaction> transaction =
+      LevelDBTransaction::Create(leveldb.get());
+
+  const std::vector<char> new_value = EncodeString("new value");
+  success = leveldb->Put(LevelDBSlice(key), new_value);
+  EXPECT_TRUE(success);
+
+  bool found = false;
+  success = transaction->Get(LevelDBSlice(key), got_value, found);
+  EXPECT_TRUE(success);
+  EXPECT_TRUE(found);
+  EXPECT_EQ(
+      comparator.Compare(LevelDBSlice(got_value), LevelDBSlice(old_value)), 0);
+
+  found = false;
+  success = leveldb->Get(LevelDBSlice(key), got_value, found);
+  EXPECT_TRUE(success);
+  EXPECT_TRUE(found);
+  EXPECT_EQ(
+      comparator.Compare(LevelDBSlice(got_value), LevelDBSlice(new_value)), 0);
+
+  const std::vector<char> added_key = EncodeString("added key");
+  const std::vector<char> added_value = EncodeString("added value");
+  success = leveldb->Put(LevelDBSlice(added_key), added_value);
+  EXPECT_TRUE(success);
+
+  success = leveldb->Get(LevelDBSlice(added_key), got_value, found);
+  EXPECT_TRUE(success);
+  EXPECT_TRUE(found);
+  EXPECT_EQ(
+      comparator.Compare(LevelDBSlice(got_value), LevelDBSlice(added_value)),
+      0);
+
+  success = transaction->Get(LevelDBSlice(added_key), got_value, found);
+  EXPECT_TRUE(success);
+  EXPECT_FALSE(found);
+}
+
+TEST(LevelDBDatabaseTest, TransactionIterator) {
+  base::ScopedTempDir temp_directory;
+  ASSERT_TRUE(temp_directory.CreateUniqueTempDir());
+
+  const std::vector<char> start = EncodeString("");
+  const std::vector<char> key1 = EncodeString("key1");
+  const std::vector<char> value1 = EncodeString("value1");
+  const std::vector<char> key2 = EncodeString("key2");
+  const std::vector<char> value2 = EncodeString("value2");
+
+  SimpleComparator comparator;
+  bool success;
+
+  scoped_ptr<LevelDBDatabase> leveldb =
+      LevelDBDatabase::Open(temp_directory.path(), &comparator);
+  EXPECT_TRUE(leveldb);
+
+  success = leveldb->Put(LevelDBSlice(key1), value1);
+  EXPECT_TRUE(success);
+  success = leveldb->Put(LevelDBSlice(key2), value2);
+  EXPECT_TRUE(success);
+
+  scoped_refptr<LevelDBTransaction> transaction =
+      LevelDBTransaction::Create(leveldb.get());
+
+  success = leveldb->Remove(LevelDBSlice(key2));
+  EXPECT_TRUE(success);
+
+  scoped_ptr<LevelDBIterator> it = transaction->CreateIterator();
+
+  it->Seek(LevelDBSlice(start));
+
+  EXPECT_TRUE(it->IsValid());
+  EXPECT_EQ(comparator.Compare(LevelDBSlice(it->Key()), LevelDBSlice(key1)), 0);
+  EXPECT_EQ(comparator.Compare(it->Value(), LevelDBSlice(value1)), 0);
+
+  it->Next();
+
+  EXPECT_TRUE(it->IsValid());
+  EXPECT_EQ(comparator.Compare(it->Key(), LevelDBSlice(key2)), 0);
+  EXPECT_EQ(comparator.Compare(it->Value(), LevelDBSlice(value2)), 0);
+
+  it->Next();
+
+  EXPECT_FALSE(it->IsValid());
+}
+
+}  // namespace
+
+}  // namespace content
diff --git a/content/browser/indexed_db/leveldb/leveldb_write_batch.cc b/content/browser/indexed_db/leveldb/leveldb_write_batch.cc
new file mode 100644
index 0000000..b15c4fa
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_write_batch.cc
@@ -0,0 +1,37 @@
+// 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_write_batch.h"
+
+#include "content/browser/indexed_db/leveldb/leveldb_slice.h"
+#include "third_party/leveldatabase/src/include/leveldb/slice.h"
+#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
+
+namespace content {
+
+scoped_ptr<LevelDBWriteBatch> LevelDBWriteBatch::Create() {
+  return make_scoped_ptr(new LevelDBWriteBatch);
+}
+
+LevelDBWriteBatch::LevelDBWriteBatch()
+    : write_batch_(new leveldb::WriteBatch) {}
+
+LevelDBWriteBatch::~LevelDBWriteBatch() {}
+
+static leveldb::Slice MakeSlice(const LevelDBSlice& s) {
+  return leveldb::Slice(s.begin(), s.end() - s.begin());
+}
+
+void LevelDBWriteBatch::Put(const LevelDBSlice& key,
+                            const LevelDBSlice& value) {
+  write_batch_->Put(MakeSlice(key), MakeSlice(value));
+}
+
+void LevelDBWriteBatch::Remove(const LevelDBSlice& key) {
+  write_batch_->Delete(MakeSlice(key));
+}
+
+void LevelDBWriteBatch::Clear() { write_batch_->Clear(); }
+
+}  // namespace content
diff --git a/content/browser/indexed_db/leveldb/leveldb_write_batch.h b/content/browser/indexed_db/leveldb/leveldb_write_batch.h
new file mode 100644
index 0000000..2849687
--- /dev/null
+++ b/content/browser/indexed_db/leveldb/leveldb_write_batch.h
@@ -0,0 +1,38 @@
+// 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_WRITE_BATCH_H_
+#define CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_WRITE_BATCH_H_
+
+#include "base/memory/scoped_ptr.h"
+
+namespace leveldb {
+class WriteBatch;
+}
+
+namespace content {
+
+class LevelDBSlice;
+
+// Wrapper around leveldb::WriteBatch.
+// This class holds a collection of updates to apply atomically to a database.
+class LevelDBWriteBatch {
+ public:
+  static scoped_ptr<LevelDBWriteBatch> Create();
+  ~LevelDBWriteBatch();
+
+  void Put(const LevelDBSlice& key, const LevelDBSlice& value);
+  void Remove(const LevelDBSlice& key);  // Add remove operation to the batch.
+  void Clear();
+
+ private:
+  friend class LevelDBDatabase;
+  LevelDBWriteBatch();
+
+  scoped_ptr<leveldb::WriteBatch> write_batch_;
+};
+
+}  // namespace content
+
+#endif  // CONTENT_BROWSER_INDEXED_DB_LEVELDB_LEVELDB_WRITE_BATCH_H_