Subversion Repositories openrisc

/* 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