Merge from transactional-memory branch.

From-SVN: r181154

1 files changed, 215 insertions, 0 deletions

diff --git a/libitm/aatree.h b/libitm/aatree.h
new file mode 100644
index 0000000..a4de8da
--- /dev/null
+++ b/libitm/aatree.h
@@ -0,0 +1,215 @@
+/* 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