OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libitm/] [aatree.cc] - Blame information for rev 791

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 737 jeremybenn
/* 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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.