URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libitm/] [aatree.cc] - Rev 771
Go to most recent revision | Compare with Previous | Blame | View Log
/* Copyright (C) 2009, 2011 Free Software Foundation, Inc. Contributed by Richard Henderson <rth@redhat.com>. This file is part of the GNU Transactional Memory Library (libitm). Libitm is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. Libitm is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. Under Section 7 of GPL version 3, you are granted additional permissions described in the GCC Runtime Library Exception, version 3.1, as published by the Free Software Foundation. You should have received a copy of the GNU General Public License and a copy of the GCC Runtime Library Exception along with this program; see the files COPYING3 and COPYING.RUNTIME respectively. If not, see <http://www.gnu.org/licenses/>. */ // Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an // integer key, and data attached to the node via flexible array member. #include "libitm_i.h" namespace GTM HIDDEN { // The code for rebalancing the tree is greatly simplified by never // having to check for null pointers. Instead, leaf node links point // to this node, NIL, which points to itself. const aa_node_base aa_node_base::s_nil(0); // Remove left horizontal links. Swap the pointers of horizontal left links. aa_node_base * aa_node_base::skew () { aa_node_base *l = this->link(L); if (this->m_level != 0 && l->m_level == this->m_level) { this->set_link(L, l->link(R)); l->set_link(R, this); return l; } return this; } // Remove consecutive horizontal links. Take the middle node, // elevate it, and return it. aa_node_base * aa_node_base::split () { aa_node_base *r = this->link(R); if (this->m_level != 0 && r->link(R)->m_level == this->m_level) { this->set_link(R, r->link(L)); r->set_link(L, this); r->m_level += 1; return r; } return this; } // Decrease the level of THIS to be one more than the level of its children. void aa_node_base::decrease_level () { aa_node_base *l = this->link(L); aa_node_base *r = this->link(R); level_type llev = l->m_level; level_type rlev = r->m_level; level_type should_be = (llev < rlev ? llev : rlev) + 1; if (should_be < this->m_level) { this->m_level = should_be; if (should_be < rlev) r->m_level = should_be; } } // Find and return the node in the tree with key K. template<typename KEY> typename aa_tree_key<KEY>::node_ptr aa_tree_key<KEY>::find(KEY k) const { node_ptr t = m_tree; if (t != 0) do { if (t->key == k) return t; t = t->link(k > t->key); } while (!t->is_nil()); return 0; } // Insert N into T and rebalance. Return the new balanced tree. template<typename KEY> typename aa_tree_key<KEY>::node_ptr aa_tree_key<KEY>::insert_1 (node_ptr t, node_ptr n) { bool dir = n->key > t->key; node_ptr c = t->link(dir); // Insert the node, recursively. if (c->is_nil()) c = n; else c = insert_1 (c, n); t->set_link(dir, c); // Rebalance the tree, as needed. t = t->skew(); t = t->split(); return t; } template<typename KEY> void aa_tree_key<KEY>::insert(node_ptr n) { if (m_tree == 0) m_tree = n; else m_tree = insert_1 (m_tree, n); } // Delete K from T and rebalance. Return the new balanced tree. template<typename KEY> typename aa_tree_key<KEY>::node_ptr aa_tree_key<KEY>::erase_1 (node_ptr t, KEY k, node_ptr *pfree) { node_ptr r; bool dir; // If this is the node we're looking for, delete it. Else recurse. if (k == t->key) { node_ptr l, sub, end; l = t->link(node::L); r = t->link(node::R); if (pfree) *pfree = t; // If this is a leaf node, simply remove the node. Otherwise, // we have to find either a predecessor or a successor node to // replace this one. if (l->is_nil()) { if (r->is_nil()) return r; sub = r, dir = node::L; } else sub = l, dir = node::R; // Find the successor or predecessor. for (end = sub; !end->link(dir)->is_nil(); end = end->link(dir)) continue; // Remove it (but don't free) from the subtree. sub = erase_1 (sub, end->key, 0); // Replace T with the successor we just extracted. end->set_link(!dir, sub); t = end; } else { dir = k > t->key; t->set_link(dir, erase_1 (t->link(dir), k, pfree)); } // Rebalance the tree. t->decrease_level(); t = t->skew(); r = t->link(node::R)->skew(); t->set_link(node::R, r); r->set_link(node::R, r->link(node::R)->skew()); t = t->split (); t->set_link(node::R, t->link(node::R)->split()); return t; } template<typename KEY> typename aa_tree_key<KEY>::node_ptr aa_tree_key<KEY>::erase (KEY k) { node_ptr t = m_tree; if (t == 0) return 0; node_ptr do_free = 0; t = erase_1 (t, k, &do_free); if (t->is_nil()) t = 0; m_tree = t; return do_free; } // Instantiate key classes. template class aa_tree_key<uintptr_t>; } // namespace GTM
Go to most recent revision | Compare with Previous | Blame | View Log