text: /* Copyright (C) 2009-2019 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
  