Loading...
Searching...
No Matches
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:
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
avl_tree
AVL tree.
cxx::Avl_tree_node
Node of an AVL tree.
Definition avl_tree:30
cxx::Avl_tree_node::Avl_tree_node
Avl_tree_node()=default
Create an uninitialized node, this is what you should do.
cxx::Avl_tree
A generic AVL tree.
Definition avl_tree:101
cxx::Avl_tree::insert
Pair< Node *, bool > insert(Node *new_node)
Insert a new node into this AVL tree.
Definition avl_tree:220
cxx::Avl_tree< _Node, GET_KEY, COMPARE >::Iterator
Bst::Iterator Iterator
Definition avl_tree:130
cxx::Bits::Base_avl_set::Node::valid
bool valid() const
Validity check.
Definition avl_set:201
cxx::Bits::Base_avl_set::Node::operator->
Item_type const * operator->()
Dereferenced member access.
Definition avl_set:195
cxx::Bits::Base_avl_set::Node::Node
Node()
Default construction for NIL pointer.
Definition avl_set:182
cxx::Bits::Base_avl_set::Node::operator*
Item_type const & operator*()
Dereference the pointer.
Definition avl_set:189
cxx::Bits::Base_avl_set
Internal: AVL set with internally managed nodes.
Definition avl_set:123
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Iterator
Avl_set_iter< _Node, Item_type, Fwd > Iterator
Definition avl_set:225
cxx::Bits::Base_avl_set::find_node
Node find_node(Key_type const &item) const
Lookup a node equal to item.
Definition avl_set:324
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Rev_iterator
Avl_set_iter< _Node, Item_type, Rev > Rev_iterator
Definition avl_set:231
cxx::Bits::Base_avl_set::rbegin
Const_rev_iterator rbegin() const
Get the constant backward iterator for the last element in the set.
Definition avl_set:367
cxx::Bits::Base_avl_set::end
Iterator end()
Get the end marker for the mutable forward iterator.
Definition avl_set:361
cxx::Bits::Base_avl_set::rbegin
Rev_iterator rbegin()
Get the mutable backward iterator for the last element of the set.
Definition avl_set:378
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Key_type
Bits::Avl_map_get_key< KEY_TYPE >::Key_type Key_type
Definition avl_set:145
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Item_type
Local_item_type Item_type
Definition avl_set:141
cxx::Bits::Base_avl_set::remove
int remove(Key_type const &item)
Remove an item from the set.
Definition avl_set:295
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Item_compare
COMPARE Item_compare
Definition avl_set:149
cxx::Bits::Base_avl_set::Base_avl_set
Base_avl_set(Node_allocator const &alloc=Node_allocator())
Create a AVL-tree based set.
Definition avl_set:243
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::E_noent
@ E_noent
Definition avl_set:135
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::E_nomem
@ E_nomem
Definition avl_set:137
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::E_exist
@ E_exist
Definition avl_set:136
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::E_inval
@ E_inval
Definition avl_set:138
cxx::Bits::Base_avl_set::end
Const_iterator end() const
Get the end marker for the constant forward iterator.
Definition avl_set:350
cxx::Bits::Base_avl_set::rend
Const_rev_iterator rend() const
Get the end marker for the constant backward iterator.
Definition avl_set:372
cxx::Bits::Base_avl_set::begin
Const_iterator begin() const
Get the constant forward iterator for the first element in the set.
Definition avl_set:345
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Node_allocator
ALLOC< _Node > Node_allocator
Definition avl_set:208
cxx::Bits::Base_avl_set::rend
Rev_iterator rend()
Get the end marker for the mutable backward iterator.
Definition avl_set:383
cxx::Bits::Base_avl_set::begin
Iterator begin()
Get the mutable forward iterator for the first element of the set.
Definition avl_set:356
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Const_rev_iterator
Avl_set_iter< _Node, Const_item_type, Rev > Const_rev_iterator
Definition avl_set:234
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Get_key
Bits::Avl_map_get_key< KEY_TYPE > Get_key
Definition avl_set:143
cxx::Bits::Base_avl_set::insert
cxx::Pair< Iterator, int > insert(Item_type const &item)
Insert an item into the set.
Definition avl_set:412
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Const_item_type
Type_traits< Item_type >::Const_type Const_item_type
Definition avl_set:147
cxx::Bits::Base_avl_set::erase
int erase(Key_type const &item)
Erase the item with the given key.
Definition avl_set:313
cxx::Bits::Base_avl_set::Base_avl_set
Base_avl_set(Base_avl_set const &o)
Create a copy of an AVL-tree based set.
Definition avl_set:402
cxx::Bits::Base_avl_set< Local_item_type, COMPARE< KEY_TYPE >, ALLOC, Bits::Avl_map_get_key< KEY_TYPE > >::Const_iterator
Avl_set_iter< _Node, Const_item_type, Fwd > Const_iterator
Definition avl_set:228
cxx::Bits::Base_avl_set::lower_bound_node
Node lower_bound_node(Key_type const &key) const
Find the first node greater or equal to key.
Definition avl_set:335
cxx::Bits::Bst::lower_bound_node
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:285
cxx::Bits::Bst::Rev_iter_ops
Rev Rev_iter_ops
Helper for building reverse iterators for different wrapper classes.
Definition bst.h:66
cxx::Bits::Bst::find
Const_iterator find(Key_param_type key) const
find the node with the given key.
Definition bst.h:305
cxx::Bits::Bst::remove_all
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:251
cxx::Bits::Bst::Fwd_iter_ops
Fwd Fwd_iter_ops
Helper for building forward iterators for different wrapper classes.
Definition bst.h:64
cxx::New_allocator
Standard allocator based on operator new () .
Definition std_alloc:57
cxx::Nothrow
Helper type to distinguish the operator new version that does not throw exceptions.
Definition std_alloc:19
cxx::Bits
Internal helpers for the cxx package.
Definition avl_map:21
cxx
Our C++ library.
Definition arith:11
cxx::Bits::Avl_set_get_key
Internal, key-getter for Avl_set nodes.
Definition avl_set:99
cxx::Pair
Pair of two values.
Definition pair:28
cxx::Pair::second
Second second
Second value.
Definition pair:37
cxx::Pair::first
First first
First value.
Definition pair:35