| //===-- SplayTree.h - Splay Tree Implementation -----------------*- C++ -*-===// |
| // |
| // Automatic Pool Allocation |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements several splay tree classes. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include <memory> |
| #include <vector> |
| |
| #ifndef SUPPORT_SPLAYTREE_H |
| #define SUPPORT_SPLAYTREE_H |
| |
| template<typename dataTy> |
| struct range_tree_node { |
| range_tree_node(void* s, void* e) : left(0), right(0), start(s), end(e) {} |
| range_tree_node() : left(0), right(0), start(0), end(0) {} |
| template<class O> |
| void do_act(O& act) { act(start, end, data); } |
| range_tree_node* left; |
| range_tree_node* right; |
| void* start; |
| void* end; |
| dataTy data; |
| }; |
| |
| template<> |
| struct range_tree_node <void>{ |
| range_tree_node(void* s, void* e) : left(0), right(0), start(s), end(e) {} |
| range_tree_node() : left(0), right(0), start(0), end(0) {} |
| template<class O> |
| void do_act(O& act) { act(start, end); } |
| range_tree_node* left; |
| range_tree_node* right; |
| void* start; |
| void* end; |
| }; |
| |
| template<typename T, class _Alloc> |
| class RangeSplayTree { |
| public: |
| typedef range_tree_node<T> tree_node; |
| private: |
| typename _Alloc::template rebind<tree_node >::other __node_alloc; |
| |
| tree_node* Tree; |
| |
| tree_node* rotate_right(tree_node* p) { |
| tree_node* x = p->left; |
| p->left = x->right; |
| x->right = p; |
| return x; |
| } |
| |
| tree_node* rotate_left(tree_node* p) { |
| tree_node* x = p->right; |
| p->right = x->left; |
| x->left = p; |
| return x; |
| } |
| |
| bool key_lt(void* _key, tree_node* _t) { return _key < _t->start; }; |
| |
| bool key_gt(void* _key, tree_node* _t) { return _key > _t->end; }; |
| |
| /* This function by D. Sleator <sleator@cs.cmu.edu> */ |
| tree_node* splay (tree_node * t, void* key) { |
| tree_node N, *l, *r, *y; |
| if (t == 0) return t; |
| N.left = N.right = 0; |
| l = r = &N; |
| |
| while(1) { |
| if (key_lt(key, t)) { |
| if (t->left == 0) break; |
| if (key_lt(key, t->left)) { |
| y = t->left; /* rotate right */ |
| t->left = y->right; |
| y->right = t; |
| t = y; |
| if (t->left == 0) break; |
| } |
| r->left = t; /* link right */ |
| r = t; |
| t = t->left; |
| } else if (key_gt(key, t)) { |
| if (t->right == 0) break; |
| if (key_gt(key, t->right)) { |
| y = t->right; /* rotate left */ |
| t->right = y->left; |
| y->left = t; |
| t = y; |
| if (t->right == 0) break; |
| } |
| l->right = t; /* link left */ |
| l = t; |
| t = t->right; |
| } else { |
| break; |
| } |
| } |
| l->right = t->left; /* assemble */ |
| r->left = t->right; |
| t->left = N.right; |
| t->right = N.left; |
| return t; |
| } |
| |
| unsigned count_internal(tree_node* t) { |
| if (t) |
| return 1 + count_internal(t->left) + count_internal(t->right); |
| return 0; |
| } |
| |
| void __clear_internal(tree_node* tree) { |
| // |
| // If there is no node, then simply return. |
| // |
| if (!tree) return; |
| |
| // The set of elements yet to process |
| std::vector<tree_node *> stack; |
| stack.push_back (tree); |
| |
| // |
| // Begin deleting elements. |
| // |
| while (stack.size()) { |
| // |
| // Remove the last node of the tree. |
| // |
| tree_node * t = stack.back(); |
| stack.pop_back(); |
| |
| // |
| // Push on to the stack for later processing the children. |
| // |
| if (t->left) stack.push_back (t->left); |
| if (t->right) stack.push_back (t->right); |
| |
| // |
| // Delete the element. |
| // |
| __node_alloc.destroy(t); |
| __node_alloc.deallocate(t, 1); |
| } |
| } |
| |
| template<class O> |
| void __clear_internal(tree_node* t, O& act) { |
| if (!t) return; |
| __clear_internal(t->left); |
| __clear_internal(t->right); |
| t->do_act(act); |
| __node_alloc.destroy(t); |
| __node_alloc.deallocate(t, 1); |
| } |
| |
| public: |
| |
| explicit RangeSplayTree(const _Alloc& a) :__node_alloc(a), Tree(0) {} |
| ~RangeSplayTree() { __clear(); } |
| |
| tree_node* __insert(void* start, void* end) { |
| Tree = splay(Tree, start); |
| //If the key is already in, fail the insert |
| if (Tree && !key_lt(start, Tree) && !key_gt(start, Tree)) |
| return 0; |
| |
| tree_node* n = __node_alloc.allocate(1); |
| __node_alloc.construct(n, tree_node(start,end)); |
| if (Tree) { |
| if (key_lt(start, Tree)) { |
| n->left = Tree->left; |
| n->right = Tree; |
| Tree->left = 0; |
| } else { |
| n->right = Tree->right; |
| n->left = Tree; |
| Tree->right = 0; |
| } |
| } |
| Tree = n; |
| return Tree; |
| } |
| |
| bool __remove(void* key) { |
| if (!Tree) return false; |
| Tree = splay(Tree, key); |
| if (!key_lt(key, Tree) && !key_gt(key, Tree)) { |
| tree_node* x = 0; |
| if (!Tree->left) |
| x = Tree->right; |
| else { |
| x = splay(Tree->left, key); |
| x->right = Tree->right; |
| } |
| tree_node* y = Tree; |
| Tree = x; |
| __node_alloc.destroy(y); |
| __node_alloc.deallocate(y, 1); |
| return true; |
| } |
| return false; /* not there */ |
| } |
| |
| unsigned __count() { |
| return count_internal(Tree); |
| } |
| |
| void __clear() { |
| __clear_internal(Tree); |
| Tree = 0; |
| } |
| |
| template <class O> |
| void __clear(O& act) { |
| __clear_internal(Tree, act); |
| Tree = 0; |
| } |
| |
| tree_node* __find(void* key) { |
| if (!Tree) return 0; |
| Tree = splay(Tree, key); |
| if (!key_lt(key, Tree) && !key_gt(key, Tree)) { |
| return Tree; |
| } |
| return 0; |
| } |
| }; |
| |
| template<class Allocator = std::allocator<void> > |
| class RangeSplaySet |
| { |
| RangeSplayTree<void, Allocator> Tree; |
| |
| public: |
| explicit RangeSplaySet(const Allocator& A = Allocator() ) |
| : Tree(A) {} |
| |
| // |
| // Method: insert() |
| // |
| // Description: |
| // Insert an element into the splay set. |
| // |
| // Inputs: |
| // start - The first valid address of the object. |
| // end - The last valid address of the object. |
| // |
| // Return value: |
| // true - The insert succeeded. |
| // false - The insert failed. |
| // |
| bool insert(void* start, void* end) { |
| return 0 != Tree.__insert(start,end); |
| } |
| |
| bool remove(void* key) { |
| return Tree.__remove(key); |
| } |
| |
| unsigned count() { return Tree.__count(); } |
| |
| void clear() { Tree.__clear(); } |
| |
| template <class O> |
| void clear(O& act) { Tree.__clear(act); } |
| |
| bool find(void* key, void*& start, void*& end) { |
| range_tree_node<void>* t = Tree.__find(key); |
| if (!t) return false; |
| start = t->start; |
| end = t->end; |
| return true; |
| } |
| bool find(void* key) { |
| range_tree_node<void>* t = Tree.__find(key); |
| if (!t) return false; |
| return true; |
| } |
| }; |
| |
| template<typename T, class Allocator = std::allocator<T> > |
| class RangeSplayMap { |
| RangeSplayTree<T, Allocator> Tree; |
| |
| public: |
| explicit RangeSplayMap(const Allocator& A= Allocator() ) |
| : Tree(A) {} |
| |
| bool insert(void* start, void* end, const T& d) { |
| range_tree_node<T>* t = Tree.__insert(start,end); |
| if (t == 0) return false; |
| t->data = d; |
| return true; |
| } |
| |
| bool remove(void* key) { |
| return Tree.__remove(key); |
| } |
| |
| unsigned count() { return Tree.__count(); } |
| |
| void clear() { Tree.__clear(); } |
| |
| template <class O> |
| void clear(O& act) { Tree.__clear(act); } |
| |
| bool find(void* key, void*& start, void*& end, T& d) { |
| range_tree_node<T>* t = Tree.__find(key); |
| if (!t) return false; |
| start = t->start; |
| end = t->end; |
| d = t->data; |
| return true; |
| } |
| bool find(void* key) { |
| range_tree_node<T>* t = Tree.__find(key); |
| if (!t) return false; |
| return true; |
| } |
| }; |
| |
| #endif |