/* Copyright (C) 2007 Garrett A. Kajmowicz
This file is part of the uClibc++ Library.
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#include<memory>
#include<utility>
#include<iterator>
#include<functional>
#include<list>
#ifndef __STD_HEADER_ASSOCIATIVE_BASE
#define __STD_HEADER_ASSOCIATIVE_BASE
#pragma GCC visibility push(default)
namespace std{
/*
* The basic premise here is that most of the code used by map, multimap, set and
* multiset is really common. There are a number of interface additions, and
* considerations about how to address multiple entries with the same key.
* The goal is that the tree/storage code should be here, and managing
* single or multiple counts will be left to subclasses.
* Yes, inheritence for the purpose of code sharing is usually a bad idea.
* However, since our goal is to reduce the total amount of code written
* and the overall binary size, this seems to be the best approach possible.
*/
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __base_associative;
template<class ValueType, class Compare, class Allocator> class _associative_iter;
template<class ValueType, class Compare, class Allocator> class _associative_citer;
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __single_associative;
template<class Key, class ValueType, class Compare = less<Key>, class Allocator = allocator<ValueType> > class __multi_associative;
template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __base_associative{
protected:
public:
typedef Key key_type;
typedef ValueType value_type;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef __base_associative<Key, ValueType, Compare, Allocator> associative_type;
typedef _associative_iter<value_type, Compare, Allocator> iterator;
typedef _associative_citer<value_type, Compare, Allocator> const_iterator;
typedef typename std::reverse_iterator<iterator> reverse_iterator;
typedef typename std::reverse_iterator<const_iterator> const_reverse_iterator;
explicit __base_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
: c(comp), value_to_key(v_to_k) { }
protected:
__base_associative(const associative_type& x)
: c(x.c), backing(x.backing), value_to_key(x.value_to_key) { }
public:
~__base_associative(){
}
bool empty() const{
return backing.empty();
}
size_type size() const{
return backing.size();
}
size_type max_size() const{
return backing.max_size();
}
iterator begin(){
return iterator(backing.begin());
}
const_iterator begin() const{
return const_iterator(backing.begin());
}
iterator end() {
return iterator(backing.end());
}
const_iterator end() const{
return const_iterator(backing.end());
}
reverse_iterator rbegin(){
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const{
return const_reverse_iterator(end());
}
reverse_iterator rend(){
return reverse_iterator(begin());
}
const_reverse_iterator rend() const{
return const_reverse_iterator(begin());
}
iterator lower_bound(const key_type &x);
const_iterator lower_bound(const key_type &x) const;
iterator upper_bound(const key_type &x);
const_iterator upper_bound(const key_type &x) const;
pair<iterator,iterator> equal_range(const key_type& x){
pair<iterator, iterator> retval;
retval.first = lower_bound(x);
retval.second = retval.first;
while(retval.second != end() && !c(x, value_to_key(*retval.second))){
++retval.second;
}
return retval;
}
pair<const_iterator,const_iterator> equal_range(const key_type& x) const{
pair<const_iterator, const_iterator> retval;
retval.first = lower_bound(x);
retval.second = retval.first;
while(retval.second != end() && !c(x, value_to_key(*retval.second))){
++retval.second;
}
return retval;
}
iterator find(const key_type& x){
iterator retval = lower_bound(x);
if(retval == end()){
return retval;
}
if(c(x, value_to_key(*retval))){
return end();
}
return retval;
}
const_iterator find(const key_type& x) const{
const_iterator retval = lower_bound(x);
if(retval == end()){
return retval;
}
if(c(x, value_to_key(*retval))){
return end();
}
return retval;
}
size_type count(const key_type& x) const{
size_type retval(0);
const_iterator first = lower_bound(x);
while(first != end() && !c(x, value_to_key(*first))){
++retval;
++first;
}
return retval;
}
void clear(){
backing.clear();
}
void erase(iterator pos){
backing.erase(pos.base_iterator());
}
size_type erase(const key_type& x){
size_type count(0);
iterator start = lower_bound(x);
iterator end = upper_bound(x);
while(start != end){
start = backing.erase(start.base_iterator());
++count;
}
return count;
}
void erase(iterator first, iterator last){
while(first != last){
backing.erase(first.base_iterator());
++first;
}
}
key_compare key_comp() const{
return c;
}
__base_associative &operator=(const __base_associative & x){
c = x.c;
backing = x.backing;
value_to_key = x.value_to_key;
return *this;
}
bool operator==(const __base_associative & x){
return x.backing == backing;
}
bool operator!=(const __base_associative & x){
return !(x.backing == backing);
}
protected:
void swap(__base_associative & x);
Compare c;
std::list<value_type> backing;
const key_type (*value_to_key)(const value_type);
};
/*
* Tree iterators for the base associative class
*/
template<class ValueType, class Compare, class Allocator> class _associative_citer
: public std::iterator<
bidirectional_iterator_tag,
ValueType,
typename Allocator::difference_type,
ValueType*,
ValueType&
>
{
protected:
typedef std::list<ValueType> listtype;
typename listtype::const_iterator base_iter;
friend class _associative_iter<ValueType, Compare, Allocator>;
public:
_associative_citer() { }
_associative_citer(const _associative_citer & m)
: base_iter(m.base_iter) { }
_associative_citer(const typename listtype::const_iterator & m)
: base_iter(m) { }
~_associative_citer() { }
ValueType operator*() const{
return *base_iter;
}
const ValueType * operator->() const{
return &(*base_iter);
}
_associative_citer & operator=(const _associative_citer & m){
base_iter = m.base_iter;
return *this;
}
bool operator==(const _associative_citer & m) const{
return m.base_iter == base_iter;
}
bool operator!=(const _associative_citer & m) const{
return m.base_iter != base_iter;
}
_associative_citer & operator++(){
++base_iter;
return *this;
}
_associative_citer operator++(int){
//The following approach ensures that we only need to
//provide code for ++ in one place (above)
_associative_citer temp(base_iter);
++base_iter;
return temp;
}
_associative_citer & operator--(){
--base_iter;
return *this;
}
_associative_citer operator--(int){
//The following approach ensures that we only need to
//provide code for -- in one place (above)
_associative_citer temp(base_iter);
--base_iter;
return temp;
}
//This is an implementation-defined function designed to make internals work correctly
typename listtype::const_iterator base_iterator(){
return base_iter;
}
};
template<class ValueType, class Compare, class Allocator> class _associative_iter
: public std::iterator<
bidirectional_iterator_tag,
ValueType,
typename Allocator::difference_type,
ValueType*,
ValueType&
>
{
protected:
typedef std::list<ValueType> listtype;
typename listtype::iterator base_iter;
typedef _associative_citer<ValueType, Compare, Allocator> __associative_citer;
public:
_associative_iter() { }
_associative_iter(const _associative_iter & m)
: base_iter(m.base_iter) { }
_associative_iter(const typename listtype::iterator & m)
: base_iter(m) { }
~_associative_iter() { }
const ValueType & operator*() const{
return *base_iter;
}
ValueType & operator*(){
return *base_iter;
}
ValueType * operator->(){
return &(*base_iter);
}
const ValueType * operator->() const{
return &(*base_iter);
}
_associative_iter & operator=(const _associative_iter & m){
base_iter = m.base_iter;
return *this;
}
bool operator==(const _associative_iter & m) const{
return m.base_iter == base_iter;
}
bool operator==(const __associative_citer & m) const{
return m.base_iter == base_iter;
}
bool operator!=(const _associative_iter & m) const{
return m.base_iter != base_iter;
}
bool operator!=(const __associative_citer & m) const{
return m.base_iter != base_iter;
}
_associative_iter & operator++(){
++base_iter;
return *this;
}
_associative_iter operator++(int){
//The following approach ensures that we only need to
//provide code for ++ in one place (above)
_associative_iter temp(base_iter);
++base_iter;
return temp;
}
_associative_iter & operator--(){
--base_iter;
return *this;
}
_associative_iter operator--(int){
//The following approach ensures that we only need to
//provide code for -- in one place (above)
_associative_iter temp(base_iter);
--base_iter;
return temp;
}
operator __associative_citer() const{
return __associative_citer(base_iter);
}
typename listtype::iterator base_iterator(){
return base_iter;
}
const typename listtype::iterator base_iterator() const{
return base_iter;
}
};
// The lower_bound code is really crappy linear search. However, it is a dead
// simple implementation (easy to audit). It can also be easily replaced.
template <class Key, class ValueType, class Compare, class Allocator>
typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x)
{
iterator retval = begin();
while(retval != end() && c(value_to_key(*retval), x)){
++retval;
}
return retval;
}
template <class Key, class ValueType, class Compare, class Allocator>
typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
__base_associative<Key, ValueType, Compare, Allocator>::lower_bound(const key_type &x) const
{
const_iterator retval = begin();
while(retval != end() && c(value_to_key(*retval), x)){
++retval;
}
return retval;
}
// Upper bound search is linear from the point of lower_bound. This is likely the best solution
// in all but the most pathological of cases.
template <class Key, class ValueType, class Compare, class Allocator>
typename __base_associative<Key, ValueType, Compare, Allocator>::iterator
__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x)
{
iterator retval = lower_bound(x);
while(retval != end() && !c(x, value_to_key(*retval))){
++retval;
}
return retval;
}
template <class Key, class ValueType, class Compare, class Allocator>
typename __base_associative<Key, ValueType, Compare, Allocator>::const_iterator
__base_associative<Key, ValueType, Compare, Allocator>::upper_bound(const key_type &x) const
{
const_iterator retval = begin();
while(retval != end() && !c(x, value_to_key(*retval))){
++retval;
}
return retval;
}
template <class Key, class ValueType, class Compare, class Allocator>
void __base_associative<Key, ValueType, Compare, Allocator>::swap(__base_associative<Key, ValueType, Compare, Allocator>& m)
{
Compare n = c;
c = m.c;
m.c = n;
m.backing.swap(backing);
}
template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __single_associative :
public __base_associative<Key, ValueType, Compare, Allocator>
{
protected:
typedef __base_associative<Key, ValueType, Compare, Allocator> base;
using base::backing;
using base::c;
public:
typedef typename base::key_type key_type;
typedef typename base::value_type value_type;
typedef typename base::key_compare key_compare;
typedef typename base::allocator_type allocator_type;
typedef typename base::reference reference;
typedef typename base::const_reference const_reference;
typedef typename base::iterator iterator;
typedef typename base::const_iterator const_iterator;
typedef typename base::size_type size_type;
typedef typename base::difference_type difference_type;
typedef typename base::pointer pointer;
typedef typename base::const_pointer const_pointer;
typedef typename base::reverse_iterator reverse_iterator;
typedef typename base::const_reverse_iterator const_reverse_iterator;
using base::begin;
using base::end;
using base::rbegin;
using base::rend;
using base::empty;
using base::size;
using base::max_size;
using base::find;
using base::count;
using base::lower_bound;
using base::upper_bound;
using base::equal_range;
using base::operator=;
using base::operator==;
using base::operator!=;
explicit __single_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
: base(comp, A, v_to_k) { }
template <class InputIterator> __single_associative(
InputIterator first,
InputIterator last,
const Compare& comp,
const Allocator& A,
const key_type (*v_to_k)(const value_type)
) : base(comp, A, v_to_k) {
insert(first, last);
}
pair<iterator, bool> insert(const value_type& x){
pair<iterator, bool> retval;
iterator location = lower_bound(this->value_to_key(x));
retval.second = true;
//Empty list or need to insert at end
if(end() == location){
backing.push_back(x);
retval.first = --(end());
return retval;
}
//Something in the list
if(c(this->value_to_key(x), this->value_to_key(*location))){
location = backing.insert(location.base_iterator(), x);
retval.first = location;
}else{
retval.second = false;
retval.first = location;
}
return retval;
}
iterator insert(iterator position, const value_type& x){
// FIXME - this is cheating and probably should be more efficient since we are
// now log(n) to find for inserts
return insert(x).first;
}
template <class InputIterator> void insert(InputIterator first, InputIterator last){
while(first != last){
insert(*first);
++first;
}
}
};
template<class Key, class ValueType, class Compare, class Allocator> class _UCXXEXPORT __multi_associative :
public __base_associative<Key, ValueType, Compare, Allocator>
{
protected:
typedef __base_associative<Key, ValueType, Compare, Allocator> base;
using base::backing;
using base::c;
public:
typedef typename base::key_type key_type;
typedef typename base::value_type value_type;
typedef typename base::key_compare key_compare;
typedef typename base::allocator_type allocator_type;
typedef typename base::reference reference;
typedef typename base::const_reference const_reference;
typedef typename base::iterator iterator;
typedef typename base::const_iterator const_iterator;
typedef typename base::size_type size_type;
typedef typename base::difference_type difference_type;
typedef typename base::pointer pointer;
typedef typename base::const_pointer const_pointer;
typedef typename base::reverse_iterator reverse_iterator;
typedef typename base::const_reverse_iterator const_reverse_iterator;
using base::begin;
using base::end;
using base::rbegin;
using base::rend;
using base::empty;
using base::size;
using base::max_size;
using base::find;
using base::count;
using base::lower_bound;
using base::upper_bound;
using base::equal_range;
using base::operator=;
using base::operator==;
explicit __multi_associative(const Compare& comp, const Allocator& A, const key_type (*v_to_k)(const value_type))
: base(comp, A, v_to_k) { }
template <class InputIterator> __multi_associative(
InputIterator first,
InputIterator last,
const Compare& comp,
const Allocator& A,
const key_type (*v_to_k)(const value_type)
) : base(comp, A, v_to_k) {
insert(first, last);
}
iterator insert(const value_type& x){
iterator location = lower_bound(this->value_to_key(x));
if(location == begin()){
backing.push_front(x);
location = begin();
}else{
location = backing.insert(location.base_iterator(), x);
}
return location;
}
iterator insert(iterator position, const value_type& x){
// FIXME - this is cheating and probably should be more efficient since we are
// now log(n) to find for inserts
return insert(x);
}
template <class InputIterator> void insert(InputIterator first, InputIterator last){
while(first != last){
insert(*first);
++first;
}
}
};
}
#pragma GCC visibility pop
#endif //__STD_HEADER_ASSOCIATIVE_BASE