libitm/aatree.cc

   1 /* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU Transactional Memory Library (libitm).
   5
   6    Libitm is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
  12    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14    more details.
  15
  16    Under Section 7 of GPL version 3, you are granted additional
  17    permissions described in the GCC Runtime Library Exception, version
  18    3.1, as published by the Free Software Foundation.
  19
  20    You should have received a copy of the GNU General Public License and
  21    a copy of the GCC Runtime Library Exception along with this program;
  22    see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23    <http://www.gnu.org/licenses/>.  */
  24
  25 // Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an
  26 // integer key, and data attached to the node via flexible array member.
  27
  28 #include "libitm_i.h"
  29
  30 namespace GTM HIDDEN {
  31
  32 // The code for rebalancing the tree is greatly simplified by never
  33 // having to check for null pointers.  Instead, leaf node links point
  34 // to this node, NIL, which points to itself.
  35 const aa_node_base aa_node_base::s_nil(0);
  36
  37
  38 // Remove left horizontal links.  Swap the pointers of horizontal left links.
  39
  40 aa_node_base *
  41 aa_node_base::skew ()
  42 {
  43   aa_node_base *l = this->link(L);
  44   if (this->m_level != 0 && l->m_level == this->m_level)
  45     {
  46       this->set_link(L, l->link(R));
  47       l->set_link(R, this);
  48       return l;
  49     }
  50   return this;
  51 }
  52
  53
  54 // Remove consecutive horizontal links.  Take the middle node,
  55 // elevate it, and return it.
  56
  57 aa_node_base *
  58 aa_node_base::split ()
  59 {
  60   aa_node_base *r = this->link(R);
  61   if (this->m_level != 0 && r->link(R)->m_level == this->m_level)
  62     {
  63       this->set_link(R, r->link(L));
  64       r->set_link(L, this);
  65       r->m_level += 1;
  66       return r;
  67     }
  68   return this;
  69 }
  70
  71 // Decrease the level of THIS to be one more than the level of its children.
  72
  73 void
  74 aa_node_base::decrease_level ()
  75 {
  76   aa_node_base *l = this->link(L);
  77   aa_node_base *r = this->link(R);
  78   level_type llev = l->m_level;
  79   level_type rlev = r->m_level;
  80   level_type should_be = (llev < rlev ? llev : rlev) + 1;
  81
  82   if (should_be < this->m_level)
  83     {
  84       this->m_level = should_be;
  85       if (should_be < rlev)
  86         r->m_level = should_be;
  87     }
  88 }
  89
  90 // Find and return the node in the tree with key K.
  91
  92 template<typename KEY>
  93 typename aa_tree_key<KEY>::node_ptr
  94 aa_tree_key<KEY>::find(KEY k) const
  95 {
  96   node_ptr t = m_tree;
  97   if (t != 0)
  98     do
  99       {
 100         if (t->key == k)
 101           return t;
 102         t = t->link(k > t->key);
 103       }
 104     while (!t->is_nil());
 105   return 0;
 106 }
 107
 108 // Insert N into T and rebalance.  Return the new balanced tree.
 109
 110 template<typename KEY>
 111 typename aa_tree_key<KEY>::node_ptr
 112 aa_tree_key<KEY>::insert_1 (node_ptr t, node_ptr n)
 113 {
 114   bool dir = n->key > t->key;
 115   node_ptr c = t->link(dir);
 116
 117   // Insert the node, recursively.
 118   if (c->is_nil())
 119     c = n;
 120   else
 121     c = insert_1 (c, n);
 122   t->set_link(dir, c);
 123
 124   // Rebalance the tree, as needed.
 125   t = t->skew();
 126   t = t->split();
 127
 128   return t;
 129 }
 130
 131 template<typename KEY>
 132 void
 133 aa_tree_key<KEY>::insert(node_ptr n)
 134 {
 135   if (m_tree == 0)
 136     m_tree = n;
 137   else
 138     m_tree = insert_1 (m_tree, n);
 139 }
 140
 141 // Delete K from T and rebalance.  Return the new balanced tree.
 142
 143 template<typename KEY>
 144 typename aa_tree_key<KEY>::node_ptr
 145 aa_tree_key<KEY>::erase_1 (node_ptr t, KEY k, node_ptr *pfree)
 146 {
 147   node_ptr r;
 148   bool dir;
 149
 150   // If this is the node we're looking for, delete it.  Else recurse.
 151   if (k == t->key)
 152     {
 153       node_ptr l, sub, end;
 154
 155       l = t->link(node::L);
 156       r = t->link(node::R);
 157
 158       if (pfree)
 159         *pfree = t;
 160
 161       // If this is a leaf node, simply remove the node.  Otherwise,
 162       // we have to find either a predecessor or a successor node to
 163       // replace this one.
 164       if (l->is_nil())
 165         {
 166           if (r->is_nil())
 167             return r;
 168           sub = r, dir = node::L;
 169         }
 170       else
 171         sub = l, dir = node::R;
 172
 173       // Find the successor or predecessor.
 174       for (end = sub; !end->link(dir)->is_nil(); end = end->link(dir))
 175         continue;
 176
 177       // Remove it (but don't free) from the subtree.
 178       sub = erase_1 (sub, end->key, 0);
 179
 180       // Replace T with the successor we just extracted.
 181       end->set_link(!dir, sub);
 182       t = end;
 183     }
 184   else
 185     {
 186       dir = k > t->key;
 187       t->set_link(dir, erase_1 (t->link(dir), k, pfree));
 188     }
 189
 190   // Rebalance the tree.
 191   t->decrease_level();
 192   t = t->skew();
 193   r = t->link(node::R)->skew();
 194   t->set_link(node::R, r);
 195   r->set_link(node::R, r->link(node::R)->skew());
 196   t = t->split ();
 197   t->set_link(node::R, t->link(node::R)->split());
 198
 199   return t;
 200 }
 201
 202 template<typename KEY>
 203 typename aa_tree_key<KEY>::node_ptr
 204 aa_tree_key<KEY>::erase (KEY k)
 205 {
 206   node_ptr t = m_tree;
 207   if (t == 0)
 208     return 0;
 209
 210   node_ptr do_free = 0;
 211   t = erase_1 (t, k, &do_free);
 212   if (t->is_nil())
 213     t = 0;
 214   m_tree = t;
 215   return do_free;
 216 }
 217
 218 // Instantiate key classes.
 219
 220 template class aa_tree_key<uintptr_t>;
 221
 222 } // namespace GTM