URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libitm/] [aatree.h] - Rev 757
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. */ #ifndef LIBITM_AATREE_H #define LIBITM_AATREE_H 1 namespace GTM HIDDEN { template<typename KEY> class aa_tree_key; class aa_node_base { public: static const bool L = false; static const bool R = true; private: typedef unsigned int level_type; aa_node_base *m_link[2]; level_type m_level; static const aa_node_base s_nil; public: aa_node_base(level_type l = 1) : m_link { const_cast<aa_node_base *>(&s_nil), const_cast<aa_node_base *>(&s_nil) }, m_level(l) { } bool is_nil() const { return this == &s_nil; } aa_node_base * link(bool d) { return m_link[d]; } void set_link(bool d, aa_node_base *val) { m_link[d] = val; } aa_node_base *skew(); aa_node_base *split(); void decrease_level(); static void *operator new (size_t s) { return xmalloc (s); } static void operator delete (void *p) { free (p); } }; template<typename KEY> struct aa_node_key : public aa_node_base { typedef aa_node_base base; KEY key; explicit aa_node_key(KEY k) : key(k) { } aa_node_key * link(bool d) { return static_cast<aa_node_key *>(base::link(d)); } aa_node_key *skew() { return static_cast<aa_node_key *>(base::skew()); } aa_node_key *split() { return static_cast<aa_node_key *>(base::split()); } }; template<typename KEY, typename DATA> struct aa_node : public aa_node_key<KEY> { typedef aa_node_key<KEY> base; DATA data; explicit aa_node(KEY k) : base(k) { } aa_node * link(bool d) { return static_cast<aa_node *>(base::link(d)); } }; template<typename KEY> class aa_tree_key { public: typedef aa_node_key<KEY> node; typedef node *node_ptr; protected: node_ptr m_tree; protected: aa_tree_key() : m_tree(0) { } node_ptr find(KEY k) const; static node_ptr insert_1 (node_ptr t, node_ptr n); void insert(node_ptr n); static node_ptr erase_1 (node_ptr t, KEY k, node_ptr *pfree); node_ptr erase(KEY k); }; extern template class aa_tree_key<uintptr_t>; template<typename KEY, typename DATA> class aa_tree : public aa_tree_key<KEY> { public: typedef aa_tree_key<KEY> base; typedef aa_node<KEY, DATA> node; typedef node *node_ptr; typedef void (*trav_callback)(KEY, DATA *, void *); private: static void clear_1 (node_ptr); static void traverse_1 (node_ptr, trav_callback, void *); public: aa_tree() = default; ~aa_tree() { clear(); } static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; } DATA *find(KEY k) const { node_ptr n = static_cast<node_ptr>(base::find (k)); return n ? &n->data : 0; } DATA *insert(KEY k) { node_ptr n = new node(k); base::insert(n); return &n->data; } void erase(KEY k) { node_ptr n = static_cast<node_ptr>(base::erase (k)); delete n; } node_ptr remove(KEY k, DATA** data) { node_ptr n = static_cast<node_ptr>(base::erase (k)); *data = (n ? &n->data : 0); return n; } void clear() { node_ptr n = static_cast<node_ptr>(this->m_tree); if (n) { this->m_tree = 0; clear_1 (n); } } void traverse (trav_callback cb, void *cb_data) { node_ptr t = static_cast<node_ptr>(this->m_tree); if (t != 0) traverse_1 (t, cb, cb_data); } }; template<typename KEY, typename DATA> void aa_tree<KEY, DATA>::clear_1 (node_ptr t) { if (t->is_nil()) return; clear_1 (t->link(node::L)); clear_1 (t->link(node::R)); delete t; } template<typename KEY, typename DATA> void aa_tree<KEY, DATA>::traverse_1 (node_ptr t, trav_callback cb, void *cb_data) { if (t->is_nil()) return; cb (t->key, &t->data, cb_data); traverse_1 (t->link(node::L), cb, cb_data); traverse_1 (t->link(node::R), cb, cb_data); } } // namespace GTM #endif // LIBITM_AATREE_H
Go to most recent revision | Compare with Previous | Blame | View Log