L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
avl_set
Go to the documentation of this file.
1// vi:set ft=cpp: -*- Mode: C++ -*-
6/*
7 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
8 * Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
9 * economic rights: Technische Universität Dresden (Germany)
10 *
11 * This file is part of TUD:OS and distributed under the terms of the
12 * GNU General Public License 2.
13 * Please see the COPYING-GPL-2 file for details.
14 *
15 * As a special exception, you may use this file as part of a free software
16 * library without restriction. Specifically, if other files instantiate
17 * templates or use macros or inline functions from this file, or you compile
18 * this file and link it with other files to produce an executable, this
19 * file does not by itself cause the resulting executable to be covered by
20 * the GNU General Public License. This exception does not however
21 * invalidate any other reasons why the executable file might be covered by
22 * the GNU General Public License.
23 */
24
25#pragma once
26
27#include <l4/cxx/std_alloc>
28#include <l4/cxx/std_ops>
29#include <l4/cxx/type_traits>
30#include <l4/cxx/avl_tree>
31
32struct Avl_set_tester;
33
34namespace cxx {
35namespace Bits {
44template< typename Node, typename Key, typename Node_op >
45class Avl_set_iter : public __Bst_iter_b<Node, Node_op>
46{
47private:
49 typedef __Bst_iter_b<Node, Node_op> Base;
50
52 typedef typename Type_traits<Key>::Non_const_type Non_const_key;
53
55 typedef Avl_set_iter<Node, Non_const_key, Node_op> Non_const_iter;
56
57 using Base::_n;
58 using Base::_r;
59 using Base::inc;
60
61public:
63 Avl_set_iter() = default;
64
69 Avl_set_iter(Node const *t) : Base(t) {}
70
75 Avl_set_iter(Base const &o) : Base(o) {}
76
78 Avl_set_iter(Non_const_iter const &o)
79 : Base(o) {}
80
82 Avl_set_iter &operator = (Non_const_iter const &o)
83 { Base::operator = (o); return *this; }
84
89 Key &operator * () const { return const_cast<Node*>(_n)->item; }
94 Key *operator -> () const { return &const_cast<Node*>(_n)->item; }
98 Avl_set_iter &operator ++ () { inc(); return *this; }
102 Avl_set_iter operator ++ (int)
103 { Avl_set_iter tmp = *this; inc(); return tmp; }
104
105};
106
108template<typename KEY_TYPE>
110{
111 typedef KEY_TYPE Key_type;
112 template<typename NODE>
113 static Key_type const &key_of(NODE const *n)
114 { return n->item; }
115};
116
117
130template< typename ITEM_TYPE, class COMPARE,
131 template<typename A> class ALLOC,
132 typename GET_KEY>
134{
135 friend struct ::Avl_set_tester;
136
137public:
144 enum
145 {
147 E_exist = 17,
148 E_nomem = 12,
149 E_inval = 22
150 };
152 typedef ITEM_TYPE Item_type;
154 typedef GET_KEY Get_key;
156 typedef typename GET_KEY::Key_type Key_type;
158 typedef typename Type_traits<Item_type>::Const_type Const_item_type;
160 typedef COMPARE Item_compare;
161
162private:
164 class _Node : public Avl_tree_node
165 {
166 public:
168 Item_type item;
169
170 _Node() = default;
171
172 _Node(Item_type const &item) : Avl_tree_node(), item(item) {}
173
174 template<typename ...ARGS>
175 _Node(ARGS &&...args) : Avl_tree_node(), item(cxx::forward<ARGS>(args)...)
176 {}
177 };
178
179public:
183 class Node
184 {
185 private:
186 struct No_type;
187 friend class Base_avl_set<ITEM_TYPE, COMPARE, ALLOC, GET_KEY>;
188 _Node const *_n;
189 explicit Node(_Node const *n) : _n(n) {}
190
191 public:
193 Node() : _n(0) {}
194
200 Item_type const &operator * () { return _n->item; }
206 Item_type const *operator -> () { return &_n->item; }
207
212 bool valid() const { return _n; }
213
215 operator Item_type const * () { return _n ? &_n->item : 0; }
216 };
217
219 typedef ALLOC<_Node> Node_allocator;
220
221private:
223 Tree _tree;
225 Node_allocator _alloc;
226
227 Base_avl_set &operator = (Base_avl_set const &) = delete;
228
229 typedef typename Tree::Fwd_iter_ops Fwd;
230 typedef typename Tree::Rev_iter_ops Rev;
231
232public:
233 typedef typename Type_traits<Item_type>::Param_type Item_param_type;
234
236 typedef Avl_set_iter<_Node, Item_type, Fwd> Iterator;
237 typedef Iterator iterator;
239 typedef Avl_set_iter<_Node, Const_item_type, Fwd> Const_iterator;
240 typedef Const_iterator const_iterator;
242 typedef Avl_set_iter<_Node, Item_type, Rev> Rev_iterator;
243 typedef Rev_iterator reverse_iterator;
245 typedef Avl_set_iter<_Node, Const_item_type, Rev> Const_rev_iterator;
246 typedef Const_rev_iterator const_reverse_iterator;
247
254 explicit Base_avl_set(Node_allocator const &alloc = Node_allocator())
255 : _tree(), _alloc(alloc)
256 {}
257
259 {
260 _tree.remove_all([this](_Node *n)
261 {
262 n->~_Node();
263 _alloc.free(n);
264 });
265 }
266
274 inline Base_avl_set(Base_avl_set const &o);
275
294
295 template<typename... Args>
296 cxx::Pair<Iterator, int> emplace(Args&&... args);
297
306 int remove(Key_type const &item)
307 {
308 _Node *n = _tree.remove(item);
309
310 if (n)
311 {
312 n->~_Node();
313 _alloc.free(n);
314 return 0;
315 }
316
317 return -E_noent;
318 }
319
324 int erase(Key_type const &item)
325 { return remove(item); }
326
335 Node find_node(Key_type const &item) const
336 { return Node(_tree.find_node(item)); }
337
347 { return Node(_tree.lower_bound_node(key)); }
348
349 Node lower_bound_node(Key_type &&key) const
350 { return Node(_tree.lower_bound_node(key)); }
351
356 Const_iterator begin() const { return _tree.begin(); }
361 Const_iterator end() const { return _tree.end(); }
362
367 Iterator begin() { return _tree.begin(); }
372 Iterator end() { return _tree.end(); }
373
378 Const_rev_iterator rbegin() const { return _tree.rbegin(); }
383 Const_rev_iterator rend() const { return _tree.rend(); }
384
389 Rev_iterator rbegin() { return _tree.rbegin(); }
394 Rev_iterator rend() { return _tree.rend(); }
395
396 Const_iterator find(Key_type const &item) const
397 { return _tree.find(item); }
398
399#ifdef __DEBUG_L4_AVL
400 bool rec_dump(bool print)
401 {
402 return _tree.rec_dump(print);
403 }
404#endif
405};
406
407
408//----------------------------------------------------------------------------
409/* Implementation of AVL Tree */
410
411/* Create a copy */
412template< typename Item, class Compare, template<typename A> class Alloc, typename KEY_TYPE>
414 : _tree(), _alloc(o._alloc)
415{
416 for (Const_iterator i = o.begin(); i != o.end(); ++i)
417 insert(*i);
418}
419
420/* Insert new _Node. */
421template< typename Item, class Compare, template< typename A > class Alloc, typename KEY_TYPE>
424{
425 _Node *n = _alloc.alloc();
426 if (!n)
427 return cxx::pair(end(), -E_nomem);
428
429 new (n, Nothrow()) _Node(item);
430 Pair<_Node *, bool> err = _tree.insert(n);
431 if (!err.second)
432 {
433 n->~_Node();
434 _alloc.free(n);
435 }
436
437 return cxx::pair(Iterator(typename Tree::Iterator(err.first, err.first)), err.second ? 0 : -E_exist);
438}
439
440/* In-place insert new _Node. */
441template< typename Item, class Compare, template< typename A > class Alloc, typename KEY_TYPE>
442template<typename... Args>
445{
446 _Node *n = _alloc.alloc();
447 if (!n)
448 return cxx::pair(end(), -E_nomem);
449
450 new (n, Nothrow()) _Node(cxx::forward<Args>(args)...);
451 Pair<_Node *, bool> err = _tree.insert(n);
452 if (!err.second)
453 {
454 n->~_Node();
455 _alloc.free(n);
456 }
457
458 return cxx::pair(Iterator(typename Tree::Iterator(err.first, err.first)), err.second ? 0 : -E_exist);
459}
460
461} // namespace Bits
462
474template< typename ITEM_TYPE, class COMPARE = Lt_functor<ITEM_TYPE>,
475 template<typename A> class ALLOC = New_allocator>
476class Avl_set :
477 public Bits::Base_avl_set<ITEM_TYPE, COMPARE, ALLOC,
478 Bits::Avl_set_get_key<ITEM_TYPE> >
479{
480private:
481 typedef Bits::Base_avl_set<ITEM_TYPE, COMPARE, ALLOC,
483
484public:
485 typedef typename Base::Node_allocator Node_allocator;
486 Avl_set() = default;
487 Avl_set(Node_allocator const &alloc)
488 : Base(alloc)
489 {}
490};
491
492} // namespace cxx
AVL tree.
AVL set for simple compareable items.
Definition avl_set:479
Node of an AVL tree.
Definition avl_tree:41
Avl_tree_node()=default
Create an uninitialized node, this is what you should do.
A generic AVL tree.
Definition avl_tree:112
Pair< Node *, bool > insert(Node *new_node)
Insert a new node into this AVL tree.
Definition avl_tree:231
Node * remove(Key_param_type key)
Remove the node with key from the tree.
Definition avl_tree:293
A smart pointer to a tree item.
Definition avl_set:184
bool valid() const
Validity check.
Definition avl_set:212
Item_type const * operator->()
Dereferenced member access.
Definition avl_set:206
Node()
Default construction for NIL pointer.
Definition avl_set:193
Item_type const & operator*()
Dereference the pointer.
Definition avl_set:200
Internal: AVL set with internally managed nodes.
Definition avl_set:134
Avl_set_iter< _Node, Item_type, Fwd > Iterator
Forward iterator for the set.
Definition avl_set:236
Node find_node(Key_type const &item) const
Lookup a node equal to item.
Definition avl_set:335
Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
Backward iterator for the set.
Definition avl_set:242
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition avl_set:378
Iterator end()
Get the end marker for the mutable forward iterator.
Definition avl_set:372
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
Definition avl_set:389
GET_KEY::Key_type Key_type
Type of the sort key used for the items.
Definition avl_set:156
ITEM_TYPE Item_type
Type for the items store in the set.
Definition avl_set:152
int remove(Key_type const &item)
Remove an item from the set.
Definition avl_set:306
COMPARE Item_compare
Type for the comparison functor.
Definition avl_set:160
Base_avl_set(Node_allocator const &alloc=Node_allocator())
Create a AVL-tree based set.
Definition avl_set:254
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition avl_set:361
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition avl_set:383
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition avl_set:356
ALLOC< _Node > Node_allocator
Type for the node allocator.
Definition avl_set:219
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Definition avl_set:394
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Definition avl_set:367
Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
Constant backward iterator for the set.
Definition avl_set:245
GET_KEY Get_key
Key-getter type to derive the sort key of an internal node.
Definition avl_set:154
cxx::Pair< Iterator, int > insert(Item_type const &item)
Insert an item into the set.
Definition avl_set:423
Type_traits< Item_type >::Const_type Const_item_type
Type used for const items within the set.
Definition avl_set:158
int erase(Key_type const &item)
Erase the item with the given key.
Definition avl_set:324
Base_avl_set(Base_avl_set const &o)
Create a copy of an AVL-tree based set.
Definition avl_set:413
@ E_noent
Item does not exist.
Definition avl_set:146
@ E_nomem
Memory allocation failed.
Definition avl_set:148
@ E_exist
Item exists already.
Definition avl_set:147
@ E_inval
Internal error.
Definition avl_set:149
Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
Constant forward iterator for the set.
Definition avl_set:239
Node lower_bound_node(Key_type const &key) const
Find the first node greater or equal to key.
Definition avl_set:346
Node * lower_bound_node(Key_param_type key) const
Find the first node with a key not less than the given key.
Definition bst.h:296
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition bst.h:210
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition bst.h:205
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Definition bst.h:77
Node * find_node(Key_param_type key) const
find the node with the given key.
Definition bst.h:280
Const_iterator find(Key_param_type key) const
find the node with the given key.
Definition bst.h:316
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:262
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition bst.h:188
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Definition bst.h:75
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition bst.h:183
Helper type to distinguish the oeprator new version that does not throw exceptions.
Definition std_alloc:30
Our C++ library.
Definition arith:22
Internal, key-getter for Avl_set nodes.
Definition avl_set:110
Pair of two values.
Definition pair:39
Second second
Second value.
Definition pair:48
First first
First value.
Definition pair:46