]>
gcc.gnu.org Git - gcc.git/blob - libitm/aatree.h
1 /* Copyright (C) 2009-2014 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
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
;
38 static const bool L
= false;
39 static const bool R
= true;
42 typedef unsigned int level_type
;
44 aa_node_base
*m_link
[2];
47 static const aa_node_base s_nil
;
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
) },
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
; }
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
;
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
;
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
>
106 typedef aa_node_key
<KEY
> node
;
107 typedef node
*node_ptr
;
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
>
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 *);
137 static void clear_1 (node_ptr
);
138 static void traverse_1 (node_ptr
, trav_callback
, void *);
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;
154 node_ptr n
= new node(k
);
161 node_ptr n
= static_cast<node_ptr
>(base::erase (k
));
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);
174 node_ptr n
= static_cast<node_ptr
>(this->m_tree
);
182 void traverse (trav_callback cb
, void *cb_data
)
184 node_ptr t
= static_cast<node_ptr
>(this->m_tree
);
186 traverse_1 (t
, cb
, cb_data
);
191 template<typename KEY
, typename DATA
>
193 aa_tree
<KEY
, DATA
>::clear_1 (node_ptr t
)
197 clear_1 (t
->link(node::L
));
198 clear_1 (t
->link(node::R
));
202 template<typename KEY
, typename DATA
>
204 aa_tree
<KEY
, DATA
>::traverse_1 (node_ptr t
, trav_callback cb
, void *cb_data
)
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
);
215 #endif // LIBITM_AATREE_H
This page took 0.045163 seconds and 5 git commands to generate.