1 /* Copyright (C) 2009-2023 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 #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