aatree.h

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