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)
 *
 * License: see LICENSE.spdx (in this directory or the directories above)
 */
 
#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:
    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;
 
  typedef typename Tree::Fwd_iter_ops Fwd;
  typedef typename Tree::Rev_iter_ops Rev;

  void deep_copy(Base_avl_set const &o)
  {
    for (Const_iterator i = o.begin(); i != o.end(); ++i)
      insert(*i);
  }
 
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()
  { clear(); }

  Base_avl_set(Base_avl_set const &o,
               Node_allocator const &alloc = Node_allocator())
    : _tree(), _alloc(alloc)
  { deep_copy(o); }

  Base_avl_set &operator = (Base_avl_set const &o)
  {
    if (this != &o)
      {
        clear();
        deep_copy(o);
      }
 
    return *this;
  }

  cxx::Pair<Iterator, int> insert(Item_type const &item);

  template<typename... Args>
  cxx::Pair<Iterator, int> emplace(Args&&... args);

  void clear() noexcept
  {
    _tree.remove_all([this](_Node *n)
                     {
                       n->~_Node();
                       _alloc.free(n);
                     });
  }

  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 */
 
/* 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, template<typename T> class COMPARE = Lt_functor,
         template<typename A> class ALLOC = New_allocator>
class Avl_set :
  public Bits::Base_avl_set<ITEM_TYPE, COMPARE<ITEM_TYPE>, ALLOC,
                            Bits::Avl_set_get_key<ITEM_TYPE>>
{
private:
  typedef Bits::Base_avl_set<ITEM_TYPE, COMPARE<ITEM_TYPE>, 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