640 lines
18 KiB
Plaintext
640 lines
18 KiB
Plaintext
/* 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){
|
|
first = backing.erase(first.base_iterator());
|
|
}
|
|
}
|
|
|
|
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
|
|
|