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.

#include "libitm_i.h"

namespace GTM HIDDEN {

// The code for rebalancing the tree is greatly simplified by never

// having to check for null pointers.  Instead, leaf node links point

// to this node, NIL, which points to itself.

const aa_node_base aa_node_base::s_nil(0);

// Remove left horizontal links.  Swap the pointers of horizontal left links.

aa_node_base *

aa_node_base::skew ()

{

  aa_node_base *l = this->link(L);

  if (this->m_level != 0 && l->m_level == this->m_level)

    {

      this->set_link(L, l->link(R));

      l->set_link(R, this);

      return l;

    }

  return this;

}

// Remove consecutive horizontal links.  Take the middle node,

// elevate it, and return it.

aa_node_base *

aa_node_base::split ()

{

  aa_node_base *r = this->link(R);

  if (this->m_level != 0 && r->link(R)->m_level == this->m_level)

    {

      this->set_link(R, r->link(L));

      r->set_link(L, this);

      r->m_level += 1;

      return r;

    }

  return this;

}

// Decrease the level of THIS to be one more than the level of its children.

void

aa_node_base::decrease_level ()

{

  aa_node_base *l = this->link(L);

  aa_node_base *r = this->link(R);

  level_type llev = l->m_level;

  level_type rlev = r->m_level;

  level_type should_be = (llev < rlev ? llev : rlev) + 1;

  if (should_be < this->m_level)

    {

      this->m_level = should_be;

      if (should_be < rlev)

        r->m_level = should_be;

    }

}

// Find and return the node in the tree with key K.

template<typename KEY>

typename aa_tree_key<KEY>::node_ptr

aa_tree_key<KEY>::find(KEY k) const

{

  node_ptr t = m_tree;

  if (t != 0)

    do

      {

        if (t->key == k)

          return t;

        t = t->link(k > t->key);

      }

    while (!t->is_nil());

  return 0;

}

// Insert N into T and rebalance.  Return the new balanced tree.

template<typename KEY>

typename aa_tree_key<KEY>::node_ptr

aa_tree_key<KEY>::insert_1 (node_ptr t, node_ptr n)

{

  bool dir = n->key > t->key;

  node_ptr c = t->link(dir);

  // Insert the node, recursively.

  if (c->is_nil())

    c = n;

  else

    c = insert_1 (c, n);

  t->set_link(dir, c);

  // Rebalance the tree, as needed.

  t = t->skew();

  t = t->split();

  return t;

}

template<typename KEY>

void

aa_tree_key<KEY>::insert(node_ptr n)

{

  if (m_tree == 0)

    m_tree = n;

  else

    m_tree = insert_1 (m_tree, n);

}

// Delete K from T and rebalance.  Return the new balanced tree.

template<typename KEY>

typename aa_tree_key<KEY>::node_ptr

aa_tree_key<KEY>::erase_1 (node_ptr t, KEY k, node_ptr *pfree)

{

  node_ptr r;

  bool dir;

  // If this is the node we're looking for, delete it.  Else recurse.

  if (k == t->key)

    {

      node_ptr l, sub, end;

      l = t->link(node::L);

      r = t->link(node::R);

      if (pfree)

        *pfree = t;

      // If this is a leaf node, simply remove the node.  Otherwise,

      // we have to find either a predecessor or a successor node to

      // replace this one.

      if (l->is_nil())

        {

          if (r->is_nil())

            return r;

          sub = r, dir = node::L;

        }

      else

        sub = l, dir = node::R;

      // Find the successor or predecessor.

      for (end = sub; !end->link(dir)->is_nil(); end = end->link(dir))

        continue;

      // Remove it (but don't free) from the subtree.

      sub = erase_1 (sub, end->key, 0);

      // Replace T with the successor we just extracted.

      end->set_link(!dir, sub);

      t = end;

    }

  else

    {

      dir = k > t->key;

      t->set_link(dir, erase_1 (t->link(dir), k, pfree));

    }

  // Rebalance the tree.

  t->decrease_level();

  t = t->skew();

  r = t->link(node::R)->skew();

  t->set_link(node::R, r);

  r->set_link(node::R, r->link(node::R)->skew());

  t = t->split ();

  t->set_link(node::R, t->link(node::R)->split());

  return t;

}

template<typename KEY>

typename aa_tree_key<KEY>::node_ptr

aa_tree_key<KEY>::erase (KEY k)

{

  node_ptr t = m_tree;

  if (t == 0)

    return 0;

  node_ptr do_free = 0;

  t = erase_1 (t, k, &do_free);

  if (t->is_nil())

    t = 0;

  m_tree = t;

  return do_free;

}

// Instantiate key classes.

template class aa_tree_key<uintptr_t>;

} // namespace GTM