diff options
Diffstat (limited to 'src/lib/splaytree.C')
-rw-r--r-- | src/lib/splaytree.C | 514 |
1 files changed, 514 insertions, 0 deletions
diff --git a/src/lib/splaytree.C b/src/lib/splaytree.C new file mode 100644 index 000000000..3ce271344 --- /dev/null +++ b/src/lib/splaytree.C @@ -0,0 +1,514 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/lib/splaytree.C $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#include <util/impl/splaytree.H> +#include <builtins.h> + +/** @file splaytree.C + * Implementation of the Util::__Util_SplayTree_Impl::SplayTree class. + */ + +namespace Util +{ + namespace __Util_SplayTree_Impl + { + + SplayTree::SplayTree(SplayTree::comparator comp, + SplayTree::copier copy, + SplayTree::deleter del) : + compare_functor(comp), + copy_functor(copy), + delete_functor(del) + { + } + + SplayTree::SplayTree(const SplayTree& t) + { + (*this) = t; + } + + SplayTree::~SplayTree() + { + this->clear(); + } + + SplayTree& SplayTree::operator=(const SplayTree& t) + { + this->clear(); + + compare_functor = t.compare_functor; + copy_functor = t.copy_functor; + delete_functor = t.delete_functor; + + insert_range(t.front(), NULL); + if (likely(NULL != header.child[LEFT])) + { + splay(header.child[LEFT]); + } + + return *this; + } + + void SplayTree::insert(node* n) + { + if (unlikely(header.parent == NULL)) // First element. + { + header.parent = header.child[LEFT] = header.child[RIGHT] = n; + n->parent = n->child[LEFT] = n->child[RIGHT] = NULL; + } + else // Not first element. + { + // Find place to insert node and insert it. + node* insert_location = header.parent; + __find(insert_location, n); + __insert(insert_location, n); + + // Fix up header nodes. + header.child[LEFT] = leftmost(header.child[LEFT]); + header.child[RIGHT] = rightmost(header.child[RIGHT]); + + // Splay new node. + splay(n); + } + + // Increment size count. + (header_n()->data_T())++; + } + + void SplayTree::insert_range(const node* n1, const node* n2) + { + while(n1 != n2) + { + insert(copy_functor(n1)); + n1 = successor(n1); + } + } + + void SplayTree::remove(node* n) + { + // Fix up left-most and right-most node pointers if deleting + // them. We'll fix up the root in the node removal itself. + if (unlikely(header.child[LEFT] == n)) + { + header.child[LEFT] = successor(n); + } + if (unlikely(header.child[RIGHT] == n)) + { + header.child[RIGHT] = predecessor(n); + } + + // Decrement size count. + (header_n()->data_T())--; + + // Find node to splice out of the tree. + // If n has one or no child, splice itself out, otherwise the + // successor. + node* y = ((!n->child[LEFT]) || (!n->child[RIGHT])) ? + n : successor(n); + + // Find the subtree of y and link it with y's parent. + node* x = y->child[LEFT] ? y->child[LEFT] : y->child[RIGHT]; + if (likely(NULL != x)) + { + x->parent = y->parent; + } + if (unlikely(!y->parent)) + { + // Fix root. + header.parent = x; + } + else + { + y->parent->child[direction(y->parent, y)] = x; + } + + // Replace n with y. + if (likely(y != n)) + { + y->parent = n->parent; + if (y->parent) + { + y->parent->child[direction(y->parent, n)] = y; + } + + y->child[LEFT] = n->child[LEFT]; + if (y->child[LEFT]) + { + y->child[LEFT]->parent = y; + } + + y->child[RIGHT] = n->child[RIGHT]; + if (y->child[RIGHT]) + { + y->child[RIGHT]->parent = y; + } + + // Splay y up to the root. + splay(y); + } + } + + bool SplayTree::find_hint(node* n, node*& hint) const + { + if (unlikely(NULL == header.parent)) + { + return false; + } + + hint = header.parent; + + bool found = __find(hint, n); + + // Splay hint up the tree to make future searches quicker. + if (likely(NULL != hint)) + { + splay(hint); + } + + return found; + } + + void SplayTree::clear() + { + node* n = front(); + while(n) + { + node* temp = n; + n = successor(n); + remove(temp); + delete_functor(temp); + } + } + + void SplayTree::swap(SplayTree& tree) + { + node temp(header); + header = tree.header; + tree.header = temp; + } + + bool SplayTree::insert_by_value(const void** v, node*& n) + { + n = find_by_value(v); + + if (unlikely(NULL != n)) + { + return false; + } + else + { + n = copy_functor(node::convertToNode(v)); + insert(n); + return true; + } + } + + size_t SplayTree::remove_by_value(const void** v) + { + if (unlikely(NULL == header.parent)) + { + return 0; + } + + node* v_node = header.parent; + if (likely(__find(v_node, node::convertToNode(v)))) + { + remove(v_node); + delete_functor(v_node); + return 1; + } + return 0; + } + + bool SplayTree::find_hint_by_value(const void** v, node*& hint) const + { + return find_hint(node::convertToNode(v), hint); + } + + SplayTree::node* SplayTree::find_by_value(const void** v) const + { + node* n = NULL; + if (find_hint_by_value(v, n)) + { + return n; + } + else + { + return NULL; + } + } + + SplayTree::node* SplayTree::lower_bound_by_value(const void** v) const + { + node* n = NULL; + node* v_n = node::convertToNode(v); + + if (find_hint(v_n, n) || (NULL == n)) + { + return n; + } + else + { + if (-1 == compare_functor(this, n, v_n)) + { + return successor(n); + } + else + { + return n; + } + } + } + + SplayTree::node* SplayTree::upper_bound_by_value(const void** v) const + { + node* n = NULL; + node* v_n = node::convertToNode(v); + + if (find_hint(v_n, n)) + { + return successor(n); + } + else if (NULL == n) + { + return NULL; + } + else + { + if (-1 == compare_functor(this, n, v_n)) + { + return successor(n); + } + else + { + return n; + } + } + } + + + const SplayTree::node* SplayTree::predecessor(const node* n) const + { + // If left child, predecessor is just the largest of the left + // subtree. + if (likely(NULL != n->child[LEFT])) + { + return rightmost(n->child[LEFT]); + } + + // Else, need to work up the tree to find predecessor. + const node* y = n->parent; + while ((NULL != y) && (n == y->child[LEFT])) + { + n = y; + y = y->parent; + } + + return y; + } + + const SplayTree::node* SplayTree::successor(const node* n) const + { + // If right child, predecessor is just the smallest of the right + // subtree. + if (likely(NULL != n->child[RIGHT])) + { + return leftmost(n->child[RIGHT]); + } + + // Else, need to work up the tree to find successor. + const node* y = n->parent; + while ((NULL != y) && (n == y->child[RIGHT])) + { + n = y; + y = y->parent; + } + + return y; + } + + void SplayTree::rotate(node* n, DIRECTION d) const + { + // Get parent node. + node* p = n->parent; + + // Link n's d-subtree into p. + p->child[!d] = n->child[d]; + if (likely(NULL != n->child[d])) + { + n->child[d]->parent = p; + } + + // Link p's parent to n. + n->parent = p->parent; + if (unlikely(!p->parent)) + { + header.parent = n; + } + else + { + p->parent->child[direction(p->parent, p)] = n; + } + + // Put p onto d-subtree of n. + p->parent = n; + n->child[d] = p; + + } + + void SplayTree::splay(node* n) const + { + // There are three splay operations. "zig", "zig-zig" and + // "zig-zag" based on the shape of the links between child, parent + // and grand-parent. + + if (unlikely(!n->parent)) // This is the root node already. + { + return; + } + + if (unlikely(!n->parent->parent)) // "zig" since no grand-parent. + { + // Rotate n into parent's location. + rotate(n, !direction(n->parent, n)); + } + else if (direction(n->parent, n) == + direction(n->parent->parent, n->parent)) // "zig-zig" + { + // Rotate parent into grand-parent first, then rotate + // n into parent. + rotate(n->parent, !direction(n->parent->parent, n->parent)); + rotate(n, !direction(n->parent, n)); + + // Continue splay. + splay(n); + } + else // "zig-zag" + { + // Rotate n into parent, then n into grand-parent. + rotate(n, !direction(n->parent, n)); + // Note: grand-parent is now parent due to first rotate. + rotate(n, !direction(n->parent, n)); + + // Continue splay. + splay(n); + } + } + + + void SplayTree::__insert(node* t, node* n) + { + node*& child = (0 > (*compare_functor)(this, n, t)) ? + t->child[LEFT] : t->child[RIGHT]; + + if (likely(NULL == child)) // Assumption is the subtree hint is + // correct, so this should be NULL. + { + // Link node into "child" slot. + child = n; + n->parent = t; + } + else + { + // Subtree hint was wrong, recurse tree. + __insert(n, child); + } + } + + bool SplayTree::__find(node*& t, node* n) const + { + int compare = (*compare_functor)(this, n, t); + + if (unlikely(compare == 0)) // Node matches, return true. + { + return true; + } + + node* child = (0 > compare) ? t->child[LEFT] : t->child[RIGHT]; + + if (unlikely(NULL == child)) // No more children, no match. + { + return false; + } + else // Recurse to child. + { + t = child; + return __find(t, n); + } + } + + void Iterator::increment() + { + if (NULL == node) + { + node = tree->front(); // This causes "begin() == ++end()" but + // is necessary so that --rend() becomes + // a reverse iterator to begin(). + } + else + { + node = tree->successor(node); + } + }; + + void Iterator::decrement() + { + if (NULL == node) + { + node = tree->back(); + } + else + { + node = tree->predecessor(node); + } + } + + void ConstIterator::increment() + { + if (NULL == node) + { + node = tree->front(); // This causes "begin() == ++end()" but + // is necessary so that --rend() becomes + // a reverse iterator to begin(). + } + else + { + node = tree->successor(node); + } + } + + void ConstIterator::decrement() + { + if (NULL == node) + { + node = tree->back(); + } + else + { + node = tree->predecessor(node); + } + } + + + }; +}; |