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

content/browser/indexed_db/leveldb/avltree.h

Index: content/browser/indexed_db/leveldb/avltree.h
diff --git a/content/browser/indexed_db/leveldb/avltree.h b/content/browser/indexed_db/leveldb/avltree.h
deleted file mode 100644
index 91df04868c74796ef4eefc6952853b83a47e4988..0000000000000000000000000000000000000000
--- 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_