avl_set

Go to the documentation of this file.

// vi:set ft=cpp: -*- Mode: C++ -*-
/*
 * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
 *               Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
 *     economic rights: Technische Universität Dresden (Germany)
 *
 * This file is part of TUD:OS and distributed under the terms of the
 * GNU General Public License 2.
 * Please see the COPYING-GPL-2 file for details.
 *
 * As a special exception, you may use this file as part of a free software
 * library without restriction.  Specifically, if other files instantiate
 * templates or use macros or inline functions from this file, or you compile
 * this file and link it with other files to produce an executable, this
 * file does not by itself cause the resulting executable to be covered by
 * the GNU General Public License.  This exception does not however
 * invalidate any other reasons why the executable file might be covered by
 * the GNU General Public License.
 */
 
#pragma once
 
#include <l4/cxx/std_alloc>
#include <l4/cxx/std_ops>
#include <l4/cxx/type_traits>
#include <l4/cxx/avl_tree>
 
struct Avl_set_tester;
 
namespace cxx {
namespace Bits {
template< typename Node, typename Key, typename Node_op >
class Avl_set_iter : public __Bst_iter_b<Node, Node_op>
{
private:
  typedef __Bst_iter_b<Node, Node_op> Base;
 
  typedef typename Type_traits<Key>::Non_const_type Non_const_key;
 
  typedef Avl_set_iter<Node, Non_const_key, Node_op> Non_const_iter;
 
  using Base::_n;
  using Base::_r;
  using Base::inc;
 
public:
  Avl_set_iter() = default;
 
  Avl_set_iter(Node const *t) : Base(t) {}
 
  Avl_set_iter(Base const &o) : Base(o) {}
 
  Avl_set_iter(Non_const_iter const &o)
  : Base(o) {}
 
  Avl_set_iter &operator = (Non_const_iter const &o)
  { Base::operator = (o); return *this; }
 
  Key &operator * () const { return const_cast<Node*>(_n)->item; }
  Key *operator -> () const { return &const_cast<Node*>(_n)->item; }
  Avl_set_iter &operator ++ () { inc(); return *this; }
  Avl_set_iter operator ++ (int)
  { Avl_set_iter tmp = *this; inc(); return tmp; }
 
};
 
template<typename KEY_TYPE>
struct Avl_set_get_key
{
  typedef KEY_TYPE Key_type;
  template<typename NODE>
  static Key_type const &key_of(NODE const *n)
  { return n->item; }
};
 
 
template< typename ITEM_TYPE, class COMPARE,
          template<typename A> class ALLOC,
          typename GET_KEY>
class Base_avl_set
{
  friend struct ::Avl_set_tester;
 
public:
  enum
  {
    E_noent =  2, 
    E_exist = 17, 
    E_nomem = 12, 
    E_inval = 22  
  };
  typedef ITEM_TYPE Item_type;
  typedef GET_KEY Get_key;
  typedef typename GET_KEY::Key_type Key_type;
  typedef typename Type_traits<Item_type>::Const_type Const_item_type;
  typedef COMPARE Item_compare;
 
private:
  class _Node : public Avl_tree_node
  {
  public:
    Item_type  item;
 
    _Node() = default;
 
    _Node(Item_type const &item) : Avl_tree_node(), item(item) {}
 
    template<typename ...ARGS>
    _Node(ARGS &&...args) : Avl_tree_node(), item(cxx::forward<ARGS>(args)...)
    {}
  };
 
public:
  class Node
  {
  private:
    struct No_type;
    friend class Base_avl_set<ITEM_TYPE, COMPARE, ALLOC, GET_KEY>;
    _Node const *_n;
    explicit Node(_Node const *n) : _n(n) {}
 
  public:
    Node() : _n(0) {}
 
    Item_type const &operator * () { return _n->item; }
    Item_type const *operator -> () { return &_n->item; }
 
    bool valid() const { return _n; }
 
    operator Item_type const * () { return _n ? &_n->item : 0; }
  };
 
  typedef ALLOC<_Node> Node_allocator;
 
private:
  typedef Avl_tree<_Node, GET_KEY, COMPARE> Tree;
  Tree _tree;
  Node_allocator _alloc;
 
  Base_avl_set &operator = (Base_avl_set const &) = delete;
 
  typedef typename Tree::Fwd_iter_ops Fwd;
  typedef typename Tree::Rev_iter_ops Rev;
 
public:
  typedef typename Type_traits<Item_type>::Param_type Item_param_type;
 
  typedef Avl_set_iter<_Node, Item_type, Fwd> Iterator;
  typedef Iterator iterator;
  typedef Avl_set_iter<_Node, Const_item_type, Fwd> Const_iterator;
  typedef Const_iterator const_iterator;
  typedef Avl_set_iter<_Node, Item_type, Rev> Rev_iterator;
  typedef Rev_iterator reverse_iterator;
  typedef Avl_set_iter<_Node, Const_item_type, Rev> Const_rev_iterator;
  typedef Const_rev_iterator const_reverse_iterator;
 
  explicit Base_avl_set(Node_allocator const &alloc = Node_allocator()) 
  : _tree(), _alloc(alloc)
  {}
 
  ~Base_avl_set()
  {
    _tree.remove_all([this](_Node *n)
                     {
                       n->~_Node();
                       _alloc.free(n);
                     });
  }
 
  inline Base_avl_set(Base_avl_set const &o);
 
  cxx::Pair<Iterator, int> insert(Item_type const &item);
 
  template<typename... Args>
  cxx::Pair<Iterator, int> emplace(Args&&... args);
 
  int remove(Key_type const &item)
  {
    _Node *n = _tree.remove(item);
 
    if (n)
      {
        n->~_Node();
  _alloc.free(n);
  return 0;
      }
 
    return -E_noent;
  }
 
  int erase(Key_type const &item)
  { return remove(item); }
 
  Node find_node(Key_type const &item) const
  { return Node(_tree.find_node(item)); }
 
  Node lower_bound_node(Key_type const &key) const
  { return Node(_tree.lower_bound_node(key)); }
 
  Node lower_bound_node(Key_type &&key) const
  { return Node(_tree.lower_bound_node(key)); }
 
  Const_iterator begin() const { return _tree.begin(); }
  Const_iterator end() const   { return _tree.end(); }
  
  Iterator begin() { return _tree.begin(); }
  Iterator end()   { return _tree.end(); }
 
  Const_rev_iterator rbegin() const { return _tree.rbegin(); }
  Const_rev_iterator rend() const   { return _tree.rend(); }
 
  Rev_iterator rbegin() { return _tree.rbegin(); }
  Rev_iterator rend()   { return _tree.rend(); }
 
  Const_iterator find(Key_type const &item) const
  { return _tree.find(item); }
 
#ifdef __DEBUG_L4_AVL
  bool rec_dump(bool print)
  {
    return _tree.rec_dump(print);
  }
#endif
};
 
 
//----------------------------------------------------------------------------
/* Implementation of AVL Tree */
 
/* Create a copy */
template< typename Item, class Compare, template<typename A> class Alloc, typename KEY_TYPE>
Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::Base_avl_set(Base_avl_set const &o)
  : _tree(), _alloc(o._alloc)
{
  for (Const_iterator i = o.begin(); i != o.end(); ++i)
    insert(*i);
}
 
/* Insert new _Node. */
template< typename Item, class Compare, template< typename A > class Alloc, typename KEY_TYPE>
Pair<typename Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::Iterator, int>
Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::insert(Item const &item)
{
  _Node *n = _alloc.alloc();
  if (!n)
    return cxx::pair(end(), -E_nomem);
 
  new (n, Nothrow()) _Node(item);
  Pair<_Node *, bool> err = _tree.insert(n);
  if (!err.second)
    {
      n->~_Node();
      _alloc.free(n);
    }
 
  return cxx::pair(Iterator(typename Tree::Iterator(err.first, err.first)), err.second ? 0 : -E_exist);
}
 
/* In-place insert new _Node. */
template< typename Item, class Compare, template< typename A > class Alloc, typename KEY_TYPE>
template<typename... Args>
Pair<typename Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::Iterator, int>
Base_avl_set<Item,Compare,Alloc,KEY_TYPE>::emplace(Args&&... args)
{
  _Node *n = _alloc.alloc();
  if (!n)
    return cxx::pair(end(), -E_nomem);
 
  new (n, Nothrow()) _Node(cxx::forward<Args>(args)...);
  Pair<_Node *, bool> err = _tree.insert(n);
  if (!err.second)
    {
      n->~_Node();
      _alloc.free(n);
    }
 
  return cxx::pair(Iterator(typename Tree::Iterator(err.first, err.first)), err.second ? 0 : -E_exist);
}
 
} // namespace Bits
 
template< typename ITEM_TYPE, class COMPARE = Lt_functor<ITEM_TYPE>,
          template<typename A> class ALLOC = New_allocator>
class Avl_set :
  public Bits::Base_avl_set<ITEM_TYPE, COMPARE, ALLOC,
                            Bits::Avl_set_get_key<ITEM_TYPE> >
{
private:
  typedef Bits::Base_avl_set<ITEM_TYPE, COMPARE, ALLOC,
                             Bits::Avl_set_get_key<ITEM_TYPE> > Base;
 
public:
  typedef typename Base::Node_allocator Node_allocator;
  Avl_set() = default;
  Avl_set(Node_allocator const &alloc)
  : Base(alloc)
  {}
};
 
} // namespace cxx