summaryrefslogtreecommitdiff
path: root/chromium/content/browser/indexed_db/leveldb/avltree.h
diff options
context:
space:
mode:
Diffstat (limited to 'chromium/content/browser/indexed_db/leveldb/avltree.h')
-rw-r--r--chromium/content/browser/indexed_db/leveldb/avltree.h977
1 files changed, 0 insertions, 977 deletions
diff --git a/chromium/content/browser/indexed_db/leveldb/avltree.h b/chromium/content/browser/indexed_db/leveldb/avltree.h
deleted file mode 100644
index 91df04868c7..00000000000
--- a/chromium/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_
View Lorry Controller Status