l4/pkg/cxx/lib/tl/include/avl_set

   1 // vi:ft=cpp
   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 /**
  34  * \internal
  35  * \ingroup cxx_api
  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 Bits::__Bst_iter_b<Node, Node_op>
  44 {
  45 private:
  46   /// Super-class type
  47   typedef Bits::__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 //  template<typename Key2>
  67   __Avl_set_iter(__Avl_set_iter<Node, typename Type_traits<Key>::Non_const_type, Node_op> const &o)
  68   : Base(o) {}
  69
  70   /**
  71    * \brief Dereference the iterator and get the item out of the tree.
  72    * \return A reference to the data stored in the AVL tree.
  73    */
  74   Key &operator * () const { return const_cast<Node*>(_n)->item; }
  75   /**
  76    * \brief Member access to the item the iterator points to.
  77    * \return A pointer to the item in the node.
  78    */
  79   Key *operator -> () const { return &const_cast<Node*>(_n)->item; }
  80   /**
  81    * \brief Set the iterator to the next element (pre increment).
  82    */
  83   __Avl_set_iter &operator ++ () { inc(); return *this; }
  84   /**
  85    * \brief Set the iterator to the next element (post increment).
  86    */
  87   __Avl_set_iter &operator ++ (int)
  88   { __Avl_set_iter tmp = *this; inc(); return tmp; }
  89
  90 };
  91
  92
  93 /**
  94  * \ingroup cxx_api
  95  * \brief AVL Tree for simple comapreable items.
  96  *
  97  * The AVL tree can store any kind of items where a partial order is defined.
  98  * The default relation is defined by the '<' operator.
  99  * \param Item The type of the items to be stored in the tree.
 100  * \param Compare The relation to define the partial order, default is
 101  *        to use operator '<'.
 102  * \param Alloc The allocator to use for the nodes of the AVL tree.
 103  */
 104 template< typename Item, class Compare = Lt_functor<Item>,
 105   template<typename A> class Alloc = New_allocator >
 106 class Avl_set
 107 {
 108 public:
 109   enum
 110   {
 111     E_noent =  2,
 112     E_exist = 17,
 113     E_nomem = 12,
 114     E_inval = 22
 115   };
 116   /// Type for the items contained in the tree.
 117   typedef Item Item_type;
 118   typedef typename Type_traits<Item>::Const_type Const_item_type;
 119   /// Type for the comparison functor.
 120   typedef Compare Item_compare;
 121
 122
 123 private:
 124
 125   /// Internal representation of a tree node.
 126   class _Node : public Avl_tree_node
 127   {
 128   public:
 129     /// The actual item stored in the node.
 130     Item_type  item;
 131
 132     _Node() : Avl_tree_node(), item() {}
 133
 134     _Node(Item_type const &item) : Avl_tree_node(), item(item) {}
 135   };
 136
 137   struct Get_key
 138   {
 139     typedef Item Key_type;
 140     static Key_type const &key_of(_Node const *n)
 141     { return n->item; }
 142   };
 143
 144 public:
 145   /**
 146    * \brief A smart pointer to a tree item.
 147    */
 148   class Node
 149   {
 150   private:
 151     struct No_type;
 152     friend class Avl_set<Item, Compare, Alloc>;
 153     _Node const *_n;
 154     explicit Node(_Node const *n) : _n(n) {}
 155
 156   public:
 157     /// Default construction for NIL pointer.
 158     Node() : _n(0) {}
 159
 160     /// Default assignment.
 161     Node &operator = (Node const &o) { _n = o._n; return *this; }
 162
 163     /// Dereference the pointer.
 164     Item const &operator * () { return _n->item; }
 165     /// Dereferenced member access.
 166     Item const *operator -> () { return &_n->item; }
 167
 168     /**
 169      * \brief Validity check.
 170      * \return false if the pointer is NIL, true if valid.
 171      */
 172     bool valid() const { return _n; }
 173
 174     /// Cast to a real item pointer.
 175     operator Item const * () { if (_n) return &_n->item; else return 0; }
 176   };
 177
 178   /// Type for the node allocator.
 179   typedef Alloc<_Node> Node_allocator;
 180
 181 private:
 182   typedef Avl_tree<_Node, Get_key, Compare> Tree;
 183   Tree _tree;
 184   /// The allocator for new nodes
 185   Node_allocator _alloc;
 186
 187   void operator = (Avl_set const &);
 188
 189   typedef typename Tree::Fwd_iter_ops Fwd;
 190   typedef typename Tree::Rev_iter_ops Rev;
 191
 192 public:
 193   typedef typename Type_traits<Item>::Param_type Item_param_type;
 194
 195   /// Forward iterator for the set.
 196   typedef __Avl_set_iter<_Node, Item_type, Fwd> Iterator;
 197   typedef Iterator iterator;
 198   /// Constant forward iterator for the set.
 199   typedef __Avl_set_iter<_Node, Const_item_type, Fwd> Const_iterator;
 200   typedef Const_iterator const_iterator;
 201   /// Backward iterator for the set.
 202   typedef __Avl_set_iter<_Node, Item_type, Rev> Rev_iterator;
 203   typedef Rev_iterator reverse_iterator;
 204   /// Constant backward iterator for the set.
 205   typedef __Avl_set_iter<_Node, Const_item_type, Rev> Const_rev_iterator;
 206   typedef Const_rev_iterator const_reverse_iterator;
 207
 208   /**
 209    * \brief Create a AVL-tree based set.
 210    * \param comp Comparison functor.
 211    * \param alloc Node allocator.
 212    *
 213    * Create an empty set (AVL-tree based).
 214    */
 215   explicit Avl_set(Node_allocator const &alloc = Node_allocator())
 216   : _tree(), _alloc(alloc)
 217   {}
 218
 219   /**
 220    * \brief Create a copy of an AVL-tree based set.
 221    * \param o The set to copy.
 222    */
 223   inline Avl_set(Avl_set const &o);
 224
 225   /**
 226    * \brief Insert an item into the set.
 227    * \param item The item to insert.
 228    * \return 0 on success, -1 on out of memory, and -2 if the element
 229    *         already exists in the set.
 230    *
 231    * Insert a new item into the set, each item can only be once in
 232    * the set.
 233    */
 234   cxx::Pair<Iterator, int> insert(Item_type const &item);
 235
 236   /**
 237    * \brief Remove an item from the set.
 238    * \param item The item to remove.
 239    * \return 0 on success, -3 if the item does not exist, and
 240    *         -4 on internal error.
 241    */
 242   int remove(Item_type const &item)
 243   {
 244     _Node *n = _tree.remove(item);
 245     if ((long)n == -E_inval)
 246       return -E_inval;
 247
 248     if (n)
 249       {
 250         n->~_Node();
 251         _alloc.free(n);
 252         return 0;
 253       }
 254
 255     return -E_noent;
 256   }
 257
 258   int erase(Item_type const &item)
 259   { return remove(item); }
 260
 261   /**
 262    * \brief Lookup a node equal to \a item.
 263    * \param item The value to search for.
 264    * \return A smart pointer to the element found, if no element found the
 265    *         pointer is NULL.
 266    */
 267   Node find_node(Item_type const &item) const
 268   { return Node(_tree.find_node(item)); }
 269
 270   /**
 271    * \brief Find the first node greater or equal to \a key.
 272    * \param key the key to look for.
 273    * \return The first node greater or equal to \a key.
 274    */
 275   Node lower_bound_node(Item_type const &key) const
 276   { return Node(_tree.lower_bound_node(key)); }
 277
 278
 279   /**
 280    * \brief Get the constant forward iterator for the first element in the set.
 281    * \return Constant forward iterator for the first element in the set.
 282    */
 283   Const_iterator begin() const { return _tree.begin(); }
 284   /**
 285    * \brief Get the end marker for the constant forward iterator.
 286    * \return The end marker for the constant forward iterator.
 287    */
 288   Const_iterator end() const   { return _tree.end(); }
 289
 290   /**
 291    * \brief Get the mutable forward iterator for the first element of the set.
 292    * \return The mutable forward iterator for the first element of the set.
 293    */
 294   Iterator begin() { return _tree.begin(); }
 295   /**
 296    * \brief Get the end marker for the mutable forward iterator.
 297    * \return The end marker for mutable forward iterator.
 298    */
 299   Iterator end()   { return _tree.end(); }
 300
 301   /**
 302    * \brief Get the constant backward iterator for the last element in the set.
 303    * \return The constant backward iterator for the last element in the set.
 304    */
 305   Const_rev_iterator rbegin() const { return _tree.rbegin(); }
 306   /**
 307    * \brief Get the end marker for the constant backward iterator.
 308    * \return The end marker for the constant backward iterator.
 309    */
 310   Const_rev_iterator rend() const   { return _tree.rend(); }
 311
 312   /**
 313    * \brief Get the mutable backward iterator for the last element of the set.
 314    * \return The mutable backward iterator for the last element of the set.
 315    */
 316   Rev_iterator rbegin() { return _tree.rbegin(); }
 317   /**
 318    * \brief Get the end marker for the mutable backward iterator.
 319    * \return The end marker for mutable backward iterator.
 320    */
 321   Rev_iterator rend()   { return _tree.rend(); }
 322
 323   Const_iterator find(Item_type const &item) const
 324   { return _tree.find(item); }
 325
 326
 327 };
 328
 329
 330 //----------------------------------------------------------------------------
 331 /* Implementation of AVL Tree */
 332
 333 /* Create a copy */
 334 template< typename Item, class Compare, template<typename A> class Alloc >
 335 Avl_set<Item,Compare,Alloc>::Avl_set(Avl_set const &o)
 336   : _tree(), _alloc(o._alloc)
 337 {
 338   for (Const_iterator i = o.begin(); i != o.end(); ++i)
 339     insert(*i);
 340 }
 341
 342 /* Insert new _Node. */
 343 template< typename Item, class Compare, template< typename A > class Alloc >
 344 Pair<typename Avl_set<Item,Compare,Alloc>::Iterator, int>
 345 Avl_set<Item,Compare,Alloc>::insert(Item const &item)
 346 {
 347   _Node *n = _alloc.alloc();
 348   if (!n)
 349     return cxx::pair(end(), -E_nomem);
 350
 351   new (n, Nothrow()) _Node(item);
 352   Pair<_Node *, bool> err = _tree.insert(n);
 353   if (!err.second)
 354     _alloc.free(n);
 355
 356   return cxx::pair(Iterator(typename Tree::Iterator(err.first, err.first)), err.second ? 0 : -E_exist);
 357 }
 358
 359 }
 360