--- /dev/null
+/* 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
OSDN Git Service
