|
145
|
1 /* Copyright (C) 2009-2020 Free Software Foundation, Inc.
|
|
111
|
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 #ifndef LIBITM_AATREE_H
|
|
|
29 #define LIBITM_AATREE_H 1
|
|
|
30
|
|
|
31 namespace GTM HIDDEN {
|
|
|
32
|
|
|
33 template<typename KEY> class aa_tree_key;
|
|
|
34
|
|
|
35 class aa_node_base
|
|
|
36 {
|
|
|
37 public:
|
|
|
38 static const bool L = false;
|
|
|
39 static const bool R = true;
|
|
|
40
|
|
|
41 private:
|
|
|
42 typedef unsigned int level_type;
|
|
|
43
|
|
|
44 aa_node_base *m_link[2];
|
|
|
45 level_type m_level;
|
|
|
46
|
|
|
47 static const aa_node_base s_nil;
|
|
|
48
|
|
|
49 public:
|
|
|
50 aa_node_base(level_type l = 1)
|
|
|
51 : m_link { const_cast<aa_node_base *>(&s_nil),
|
|
|
52 const_cast<aa_node_base *>(&s_nil) },
|
|
|
53 m_level(l)
|
|
|
54 { }
|
|
|
55
|
|
|
56 bool is_nil() const { return this == &s_nil; }
|
|
|
57
|
|
|
58 aa_node_base * link(bool d) { return m_link[d]; }
|
|
|
59 void set_link(bool d, aa_node_base *val) { m_link[d] = val; }
|
|
|
60
|
|
|
61 aa_node_base *skew();
|
|
|
62 aa_node_base *split();
|
|
|
63 void decrease_level();
|
|
|
64
|
|
|
65 static void *operator new (size_t s) { return xmalloc (s); }
|
|
|
66 static void operator delete (void *p) { free (p); }
|
|
|
67 };
|
|
|
68
|
|
|
69 template<typename KEY>
|
|
|
70 struct aa_node_key : public aa_node_base
|
|
|
71 {
|
|
|
72 typedef aa_node_base base;
|
|
|
73
|
|
|
74 KEY key;
|
|
|
75
|
|
|
76 explicit aa_node_key(KEY k) : key(k) { }
|
|
|
77
|
|
|
78 aa_node_key * link(bool d)
|
|
|
79 {
|
|
|
80 return static_cast<aa_node_key *>(base::link(d));
|
|
|
81 }
|
|
|
82
|
|
|
83 aa_node_key *skew() { return static_cast<aa_node_key *>(base::skew()); }
|
|
|
84 aa_node_key *split() { return static_cast<aa_node_key *>(base::split()); }
|
|
|
85 };
|
|
|
86
|
|
|
87 template<typename KEY, typename DATA>
|
|
|
88 struct aa_node : public aa_node_key<KEY>
|
|
|
89 {
|
|
|
90 typedef aa_node_key<KEY> base;
|
|
|
91
|
|
|
92 DATA data;
|
|
|
93
|
|
|
94 explicit aa_node(KEY k) : base(k) { }
|
|
|
95
|
|
|
96 aa_node * link(bool d)
|
|
|
97 {
|
|
|
98 return static_cast<aa_node *>(base::link(d));
|
|
|
99 }
|
|
|
100 };
|
|
|
101
|
|
|
102 template<typename KEY>
|
|
|
103 class aa_tree_key
|
|
|
104 {
|
|
|
105 public:
|
|
|
106 typedef aa_node_key<KEY> node;
|
|
|
107 typedef node *node_ptr;
|
|
|
108
|
|
|
109 protected:
|
|
|
110 node_ptr m_tree;
|
|
|
111
|
|
|
112 protected:
|
|
|
113 aa_tree_key() : m_tree(0) { }
|
|
|
114
|
|
|
115 node_ptr find(KEY k) const;
|
|
|
116
|
|
|
117 static node_ptr insert_1 (node_ptr t, node_ptr n);
|
|
|
118 void insert(node_ptr n);
|
|
|
119
|
|
|
120 static node_ptr erase_1 (node_ptr t, KEY k, node_ptr *pfree);
|
|
|
121 node_ptr erase(KEY k);
|
|
|
122 };
|
|
|
123
|
|
|
124 extern template class aa_tree_key<uintptr_t>;
|
|
|
125
|
|
|
126 template<typename KEY, typename DATA>
|
|
|
127 class aa_tree : public aa_tree_key<KEY>
|
|
|
128 {
|
|
|
129 public:
|
|
|
130 typedef aa_tree_key<KEY> base;
|
|
|
131 typedef aa_node<KEY, DATA> node;
|
|
|
132 typedef node *node_ptr;
|
|
|
133
|
|
|
134 typedef void (*trav_callback)(KEY, DATA *, void *);
|
|
|
135
|
|
|
136 private:
|
|
|
137 static void clear_1 (node_ptr);
|
|
|
138 static void traverse_1 (node_ptr, trav_callback, void *);
|
|
|
139
|
|
|
140 public:
|
|
|
141 aa_tree() = default;
|
|
|
142 ~aa_tree() { clear(); }
|
|
|
143
|
|
|
144 static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; }
|
|
|
145
|
|
|
146 DATA *find(KEY k) const
|
|
|
147 {
|
|
|
148 node_ptr n = static_cast<node_ptr>(base::find (k));
|
|
|
149 return n ? &n->data : 0;
|
|
|
150 }
|
|
|
151
|
|
|
152 DATA *insert(KEY k)
|
|
|
153 {
|
|
|
154 node_ptr n = new node(k);
|
|
|
155 base::insert(n);
|
|
|
156 return &n->data;
|
|
|
157 }
|
|
|
158
|
|
|
159 void erase(KEY k)
|
|
|
160 {
|
|
|
161 node_ptr n = static_cast<node_ptr>(base::erase (k));
|
|
|
162 delete n;
|
|
|
163 }
|
|
|
164
|
|
|
165 node_ptr remove(KEY k, DATA** data)
|
|
|
166 {
|
|
|
167 node_ptr n = static_cast<node_ptr>(base::erase (k));
|
|
|
168 *data = (n ? &n->data : 0);
|
|
|
169 return n;
|
|
|
170 }
|
|
|
171
|
|
|
172 void clear()
|
|
|
173 {
|
|
|
174 node_ptr n = static_cast<node_ptr>(this->m_tree);
|
|
|
175 if (n)
|
|
|
176 {
|
|
|
177 this->m_tree = 0;
|
|
|
178 clear_1 (n);
|
|
|
179 }
|
|
|
180 }
|
|
|
181
|
|
|
182 void traverse (trav_callback cb, void *cb_data)
|
|
|
183 {
|
|
|
184 node_ptr t = static_cast<node_ptr>(this->m_tree);
|
|
|
185 if (t != 0)
|
|
|
186 traverse_1 (t, cb, cb_data);
|
|
|
187 }
|
|
|
188 };
|
|
|
189
|
|
|
190
|
|
|
191 template<typename KEY, typename DATA>
|
|
|
192 void
|
|
|
193 aa_tree<KEY, DATA>::clear_1 (node_ptr t)
|
|
|
194 {
|
|
|
195 if (t->is_nil())
|
|
|
196 return;
|
|
|
197 clear_1 (t->link(node::L));
|
|
|
198 clear_1 (t->link(node::R));
|
|
|
199 delete t;
|
|
|
200 }
|
|
|
201
|
|
|
202 template<typename KEY, typename DATA>
|
|
|
203 void
|
|
|
204 aa_tree<KEY, DATA>::traverse_1 (node_ptr t, trav_callback cb, void *cb_data)
|
|
|
205 {
|
|
|
206 if (t->is_nil())
|
|
|
207 return;
|
|
|
208 cb (t->key, &t->data, cb_data);
|
|
|
209 traverse_1 (t->link(node::L), cb, cb_data);
|
|
|
210 traverse_1 (t->link(node::R), cb, cb_data);
|
|
|
211 }
|
|
|
212
|
|
|
213 } // namespace GTM
|
|
|
214
|
|
|
215 #endif // LIBITM_AATREE_H
|
