Daily bump.
[official-gcc.git] / libitm / aatree.h
bloba93928f4dfd03ef1622ab7f4673636c094313be7
1 /* Copyright (C) 2009-2017 Free Software Foundation, Inc.
2 Contributed by Richard Henderson <rth@redhat.com>.
4 This file is part of the GNU Transactional Memory Library (libitm).
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.
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.
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.
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/>. */
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. */
28 #ifndef LIBITM_AATREE_H
29 #define LIBITM_AATREE_H 1
31 namespace GTM HIDDEN {
33 template<typename KEY> class aa_tree_key;
35 class aa_node_base
37 public:
38 static const bool L = false;
39 static const bool R = true;
41 private:
42 typedef unsigned int level_type;
44 aa_node_base *m_link[2];
45 level_type m_level;
47 static const aa_node_base s_nil;
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 { }
56 bool is_nil() const { return this == &s_nil; }
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; }
61 aa_node_base *skew();
62 aa_node_base *split();
63 void decrease_level();
65 static void *operator new (size_t s) { return xmalloc (s); }
66 static void operator delete (void *p) { free (p); }
69 template<typename KEY>
70 struct aa_node_key : public aa_node_base
72 typedef aa_node_base base;
74 KEY key;
76 explicit aa_node_key(KEY k) : key(k) { }
78 aa_node_key * link(bool d)
80 return static_cast<aa_node_key *>(base::link(d));
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()); }
87 template<typename KEY, typename DATA>
88 struct aa_node : public aa_node_key<KEY>
90 typedef aa_node_key<KEY> base;
92 DATA data;
94 explicit aa_node(KEY k) : base(k) { }
96 aa_node * link(bool d)
98 return static_cast<aa_node *>(base::link(d));
102 template<typename KEY>
103 class aa_tree_key
105 public:
106 typedef aa_node_key<KEY> node;
107 typedef node *node_ptr;
109 protected:
110 node_ptr m_tree;
112 protected:
113 aa_tree_key() : m_tree(0) { }
115 node_ptr find(KEY k) const;
117 static node_ptr insert_1 (node_ptr t, node_ptr n);
118 void insert(node_ptr n);
120 static node_ptr erase_1 (node_ptr t, KEY k, node_ptr *pfree);
121 node_ptr erase(KEY k);
124 extern template class aa_tree_key<uintptr_t>;
126 template<typename KEY, typename DATA>
127 class aa_tree : public aa_tree_key<KEY>
129 public:
130 typedef aa_tree_key<KEY> base;
131 typedef aa_node<KEY, DATA> node;
132 typedef node *node_ptr;
134 typedef void (*trav_callback)(KEY, DATA *, void *);
136 private:
137 static void clear_1 (node_ptr);
138 static void traverse_1 (node_ptr, trav_callback, void *);
140 public:
141 aa_tree() = default;
142 ~aa_tree() { clear(); }
144 static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; }
146 DATA *find(KEY k) const
148 node_ptr n = static_cast<node_ptr>(base::find (k));
149 return n ? &n->data : 0;
152 DATA *insert(KEY k)
154 node_ptr n = new node(k);
155 base::insert(n);
156 return &n->data;
159 void erase(KEY k)
161 node_ptr n = static_cast<node_ptr>(base::erase (k));
162 delete n;
165 node_ptr remove(KEY k, DATA** data)
167 node_ptr n = static_cast<node_ptr>(base::erase (k));
168 *data = (n ? &n->data : 0);
169 return n;
172 void clear()
174 node_ptr n = static_cast<node_ptr>(this->m_tree);
175 if (n)
177 this->m_tree = 0;
178 clear_1 (n);
182 void traverse (trav_callback cb, void *cb_data)
184 node_ptr t = static_cast<node_ptr>(this->m_tree);
185 if (t != 0)
186 traverse_1 (t, cb, cb_data);
191 template<typename KEY, typename DATA>
192 void
193 aa_tree<KEY, DATA>::clear_1 (node_ptr t)
195 if (t->is_nil())
196 return;
197 clear_1 (t->link(node::L));
198 clear_1 (t->link(node::R));
199 delete t;
202 template<typename KEY, typename DATA>
203 void
204 aa_tree<KEY, DATA>::traverse_1 (node_ptr t, trav_callback cb, void *cb_data)
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);
213 } // namespace GTM
215 #endif // LIBITM_AATREE_H