L4Re - L4 Runtime Environment
avl_set
Go to the documentation of this file.
1 // vi:set ft=cpp: -*- Mode: C++ -*-
2 /**
3  * \file
4  * \brief AVL set
5  */
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 
32 namespace cxx {
33 namespace Bits {
34 /**
35  * \internal
36  * \brief Generic iterator for the AVL-tree based set.
37  * \param Cmp the type of the comparison functor.
38  * \param Node the type of a node.
39  * \param Key the type of the item stored in a node.
40  * \param Node_op the type used to determine the direction of the iterator.
41  */
42 template< typename Node, typename Key, typename Node_op >
43 class Avl_set_iter : public __Bst_iter_b<Node, Node_op>
44 {
45 private:
46  /// Super-class type
47  typedef __Bst_iter_b<Node, Node_op> Base;
48 
49  using Base::_n;
50  using Base::_r;
51  using Base::inc;
52 
53 public:
54  /// Create an invalid iterator (end marker)
55  Avl_set_iter() {}
56 
57  /**
58  * \brief Create an iterator for the given tree.
59  * \param t the root node of the tree to iterate.
60  * \param cmp the conmparison functor for tree elements.
61  */
62  Avl_set_iter(Node const *t) : Base(t) {}
63 
64  Avl_set_iter(Base const &o) : Base(o) {}
65 
66  Avl_set_iter(Avl_set_iter<Node, typename Type_traits<Key>::Non_const_type, Node_op> const &o)
67  : Base(o) {}
68 
69  /**
70  * \brief Dereference the iterator and get the item out of the tree.
71  * \return A reference to the data stored in the AVL tree.
72  */
73  Key &operator * () const { return const_cast<Node*>(_n)->item; }
74  /**
75  * \brief Member access to the item the iterator points to.
76  * \return A pointer to the item in the node.
77  */
78  Key *operator -> () const { return &const_cast<Node*>(_n)->item; }
79  /**
80  * \brief Set the iterator to the next element (pre increment).
81  */
82  Avl_set_iter &operator ++ () { inc(); return *this; }
83  /**
84  * \brief Set the iterator to the next element (post increment).
85  */
86  Avl_set_iter &operator ++ (int)
87  { Avl_set_iter tmp = *this; inc(); return tmp; }
88 
89 };
90 
91 /// Internal, key-getter for Avl_set nodes.
92 template<typename KEY_TYPE>
93 struct Avl_set_get_key
94 {
95  typedef KEY_TYPE Key_type;
96  template<typename NODE>
97  static Key_type const &key_of(NODE const *n)
98  { return n->item; }
99 };
100 
101 
102 /**
103  * Internal: AVL set with internally managed nodes.
104  *
105  * Use Avl_set, Avl_map, or Avl_tree in applications.
106  *
107  * \tparam ITEM_TYPE The type of the items to be stored in the set.
108  * \tparam COMPARE The relation to define the partial order, default is
109  * to use operator '<'.
110  * \tparam ALLOC The allocator to use for the nodes of the AVL set.
111  * \tparam GET_KEY Sort-key getter (must provide the `Key_type` and
112  * sort-key for an item (of `ITEM_TYPE`).
113  */
114 template< typename ITEM_TYPE, class COMPARE,
115  template<typename A> class ALLOC,
116  typename GET_KEY>
117 class Base_avl_set
118 {
119 public:
120  /**
121  * Return status constants.
122  *
123  * These constants are compatible with the L4 error codes, see
124  * #l4_error_code_t.
125  */
126  enum
127  {
128  E_noent = 2, ///< Item does not exist.
129  E_exist = 17, ///< Item exists already.
130  E_nomem = 12, ///< Memory allocation failed.
131  E_inval = 22 ///< Internal error.
132  };
133  /// Type for the items store in the set
134  typedef ITEM_TYPE Item_type;
135  /// Key-getter type to derive the sort key of an internal node.
136  typedef GET_KEY Get_key;
137  /// Type of the sort key used for the items
138  typedef typename GET_KEY::Key_type Key_type;
139  /// Type used for const items within the set
140  typedef typename Type_traits<Item_type>::Const_type Const_item_type;
141  /// Type for the comparison functor.
142  typedef COMPARE Item_compare;
143 
144 private:
145  /// Internal representation of a tree node.
146  class _Node : public Avl_tree_node
147  {
148  public:
149  /// The actual item stored in the node.
150  Item_type item;
151 
152  _Node() : Avl_tree_node(), item() {}
153 
154  _Node(Item_type const &item) : Avl_tree_node(), item(item) {}
155  };
156 
157 public:
158  /**
159  * \brief A smart pointer to a tree item.
160  */
161  class Node
162  {
163  private:
164  struct No_type;
165  friend class Base_avl_set<ITEM_TYPE, COMPARE, ALLOC, GET_KEY>;
166  _Node const *_n;
167  explicit Node(_Node const *n) : _n(n) {}
168 
169  public:
170  /// Default construction for NIL pointer.
171  Node() : _n(0) {}
172 
173  /// Default assignment.
174  Node &operator = (Node const &o) { _n = o._n; return *this; }
175 
176  /**
177  * Dereference the pointer.
178  *
179  * \pre Node is valid.
180  */
181  Item_type const &operator * () { return _n->item; }
182  /**
183  * Dereferenced member access.
184  *
185  * \pre Node is valid.
186  */
187  Item_type const *operator -> () { return &_n->item; }
188 
189  /**
190  * \brief Validity check.
191  * \return false if the pointer is NIL, true if valid.
192  */
193  bool valid() const { return _n; }
194 
195  /// Cast to a real item pointer.
196  operator Item_type const * () { if (_n) return &_n->item; else return 0; }
197  };
198 
199  /// Type for the node allocator.
200  typedef ALLOC<_Node> Node_allocator;
201 
202 private:
203  typedef Avl_tree<_Node, GET_KEY, COMPARE> Tree;
204  Tree _tree;
205  /// The allocator for new nodes
206  Node_allocator _alloc;
207 
208  Base_avl_set &operator = (Base_avl_set const &) = delete;
209 
210  typedef typename Tree::Fwd_iter_ops Fwd;
211  typedef typename Tree::Rev_iter_ops Rev;
212 
213 public:
214  typedef typename Type_traits<Item_type>::Param_type Item_param_type;
215 
216  /// Forward iterator for the set.
217  typedef Avl_set_iter<_Node, Item_type, Fwd> Iterator;
218  typedef Iterator iterator;
219  /// Constant forward iterator for the set.
220  typedef Avl_set_iter<_Node, Const_item_type, Fwd> Const_iterator;
221  typedef Const_iterator const_iterator;
222  /// Backward iterator for the set.
223  typedef Avl_set_iter<_Node, Item_type, Rev> Rev_iterator;
224  typedef Rev_iterator reverse_iterator;
225  /// Constant backward iterator for the set.
226  typedef Avl_set_iter<_Node, Const_item_type, Rev> Const_rev_iterator;
227  typedef Const_rev_iterator const_reverse_iterator;
228 
229  /**
230  * \brief Create a AVL-tree based set.
231  * \param alloc Node allocator.
232  *
233  * Create an empty set (AVL-tree based).
234  */
235  explicit Base_avl_set(Node_allocator const &alloc = Node_allocator())
236  : _tree(), _alloc(alloc)
237  {}
238 
239  ~Base_avl_set()
240  {
241  _tree.remove_all([this](_Node *n)
242  {
243  n->~_Node();
244  _alloc.free(n);
245  });
246  }
247 
248  /**
249  * Create a copy of an AVL-tree based set.
250  *
251  * \param o The set to copy.
252  *
253  * Creates a deep copy of the set with all its items.
254  */
255  inline Base_avl_set(Base_avl_set const &o);
256 
257  /**
258  * Insert an item into the set.
259  *
260  * \param item The item to insert.
261  *
262  * \return A pair of iterator (`first`) and return value (`second`).
263  * `second` will be 0 if the element was inserted into the set
264  * and `-#E_exist` if the element was already in the set and
265  * the set was therefore not updated.
266  * In both cases, `first` contains an iterator that points to
267  * the element.
268  * `second` may also be `-#E_nomem` when memory for the node
269  * could not be allocated. `first` is then invalid.
270  *
271  * Insert a new item into the set, each item can only be once in
272  * the set.
273  */
274  cxx::Pair<Iterator, int> insert(Item_type const &item);
275 
276  /**
277  * Remove an item from the set.
278  *
279  * \param item The item to remove.
280  *
281  * \retval 0 Success
282  * \retval -E_noent Item does not exist
283  * \retval -E_inval Internal error
284  */
285  int remove(Key_type const &item)
286  {
287  _Node *n = _tree.remove(item);
288  if ((long)n == -E_inval)
289  return -E_inval;
290 
291  if (n)
292  {
293  n->~_Node();
294  _alloc.free(n);
295  return 0;
296  }
297 
298  return -E_noent;
299  }
300 
301  /**
302  * Erase the item with the given key.
303  * \param item The key of the item to remove.
304  */
305  int erase(Key_type const &item)
306  { return remove(item); }
307 
308  /**
309  * Lookup a node equal to `item`.
310  *
311  * \param item The value to search for.
312  *
313  * \return A smart pointer to the element found.
314  * If no element was found the smart pointer will be invalid.
315  */
316  Node find_node(Key_type const &item) const
317  { return Node(_tree.find_node(item)); }
318 
319  /**
320  * Find the first node greater or equal to `key`.
321  *
322  * \param key Minimum key to look for.
323  *
324  * \return Smart pointer to the first node greater or equal to `key`.
325  * Will be invalid if no such element was found.
326  */
327  Node lower_bound_node(Key_type const &key) const
328  { return Node(_tree.lower_bound_node(key)); }
329 
330  Node lower_bound_node(Key_type &&key) const
331  { return Node(_tree.lower_bound_node(key)); }
332 
333  /**
334  * \brief Get the constant forward iterator for the first element in the set.
335  * \return Constant forward iterator for the first element in the set.
336  */
337  Const_iterator begin() const { return _tree.begin(); }
338  /**
339  * \brief Get the end marker for the constant forward iterator.
340  * \return The end marker for the constant forward iterator.
341  */
342  Const_iterator end() const { return _tree.end(); }
343 
344  /**
345  * \brief Get the mutable forward iterator for the first element of the set.
346  * \return The mutable forward iterator for the first element of the set.
347  */
348  Iterator begin() { return _tree.begin(); }
349  /**
350  * \brief Get the end marker for the mutable forward iterator.
351  * \return The end marker for mutable forward iterator.
352  */
353  Iterator end() { return _tree.end(); }
354 
355  /**
356  * \brief Get the constant backward iterator for the last element in the set.
357  * \return The constant backward iterator for the last element in the set.
358  */
359  Const_rev_iterator rbegin() const { return _tree.rbegin(); }
360  /**
361  * \brief Get the end marker for the constant backward iterator.
362  * \return The end marker for the constant backward iterator.
363  */
364  Const_rev_iterator rend() const { return _tree.rend(); }
365 
366  /**
367  * \brief Get the mutable backward iterator for the last element of the set.
368  * \return The mutable backward iterator for the last element of the set.
369  */
370  Rev_iterator rbegin() { return _tree.rbegin(); }
371  /**
372  * \brief Get the end marker for the mutable backward iterator.
373  * \return The end marker for mutable backward iterator.
374  */
375  Rev_iterator rend() { return _tree.rend(); }
376 
377  Const_iterator find(Key_type const &item) const
378  { return _tree.find(item); }
379 };
380 
381 
382 //----------------------------------------------------------------------------
383 /* Implementation of AVL Tree */
384 
385 /* Create a copy */
386 template< typename Item, class Compare, template<typename A> class Alloc, typename KEY_TYPE>
387 Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::Base_avl_set(Base_avl_set const &o)
388  : _tree(), _alloc(o._alloc)
389 {
390  for (Const_iterator i = o.begin(); i != o.end(); ++i)
391  insert(*i);
392 }
393 
394 /* Insert new _Node. */
395 template< typename Item, class Compare, template< typename A > class Alloc, typename KEY_TYPE>
396 Pair<typename Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::Iterator, int>
397 Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::insert(Item const &item)
398 {
399  _Node *n = _alloc.alloc();
400  if (!n)
401  return cxx::pair(end(), -E_nomem);
402 
403  new (n, Nothrow()) _Node(item);
404  Pair<_Node *, bool> err = _tree.insert(n);
405  if (!err.second)
406  {
407  n->~_Node();
408  _alloc.free(n);
409  }
410 
411  return cxx::pair(Iterator(typename Tree::Iterator(err.first, err.first)), err.second ? 0 : -E_exist);
412 }
413 
414 } // namespace Bits
415 
416 /**
417  * \brief AVL set for simple compareable items.
418  *
419  * The AVL set can store any kind of items where a partial order is defined.
420  * The default relation is defined by the '<' operator.
421  *
422  * \tparam ITEM_TYPE The type of the items to be stored in the set.
423  * \tparam COMPARE The relation to define the partial order, default is
424  * to use operator '<'.
425  * \tparam ALLOC The allocator to use for the nodes of the AVL set.
426  */
427 template< typename ITEM_TYPE, class COMPARE = Lt_functor<ITEM_TYPE>,
428  template<typename A> class ALLOC = New_allocator>
429 class Avl_set :
430  public Bits::Base_avl_set<ITEM_TYPE, COMPARE, ALLOC,
431  Bits::Avl_set_get_key<ITEM_TYPE> >
432 {
433 private:
434  typedef Bits::Base_avl_set<ITEM_TYPE, COMPARE, ALLOC,
435  Bits::Avl_set_get_key<ITEM_TYPE> > Base;
436 
437 public:
438  typedef typename Base::Node_allocator Node_allocator;
439  Avl_set() = default;
440  Avl_set(Node_allocator const &alloc)
441  : Base(alloc)
442  {}
443 };
444 
445 } // namespace cxx