/contrib/media/updf/include/ext/bvector |
---|
0,0 → 1,46 |
/* |
* |
* Copyright (c) 1994 |
* Hewlett-Packard Company |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Hewlett-Packard Company makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
* |
* Copyright (c) 1996 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
*/ |
#ifndef __SGI_STL_BVECTOR_H |
#define __SGI_STL_BVECTOR_H |
#include <bits/std_vector.h> |
#include <ext/stl_bvector.h> |
#ifdef __STL_USE_NAMESPACES |
using __STD::bit_vector; |
#endif /* __STL_USE_NAMESPACES */ |
#endif /* __SGI_STL_BVECTOR_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/hash_map |
---|
0,0 → 1,407 |
/* |
* Copyright (c) 1996 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
* |
* Copyright (c) 1994 |
* Hewlett-Packard Company |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Hewlett-Packard Company makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#ifndef __SGI_STL_INTERNAL_HASH_MAP_H |
#define __SGI_STL_INTERNAL_HASH_MAP_H |
#include <ext/stl_hashtable.h> |
#include <bits/concept_check.h> |
namespace std |
{ |
// Forward declaration of equality operator; needed for friend declaration. |
template <class _Key, class _Tp, |
class _HashFcn = hash<_Key>, |
class _EqualKey = equal_to<_Key>, |
class _Alloc = allocator<_Tp> > |
class hash_map; |
template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> |
inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&, |
const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&); |
template <class _Key, class _Tp, class _HashFcn, class _EqualKey, |
class _Alloc> |
class hash_map |
{ |
private: |
typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, |
_Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; |
_Ht _M_ht; |
public: |
typedef typename _Ht::key_type key_type; |
typedef _Tp data_type; |
typedef _Tp mapped_type; |
typedef typename _Ht::value_type value_type; |
typedef typename _Ht::hasher hasher; |
typedef typename _Ht::key_equal key_equal; |
typedef typename _Ht::size_type size_type; |
typedef typename _Ht::difference_type difference_type; |
typedef typename _Ht::pointer pointer; |
typedef typename _Ht::const_pointer const_pointer; |
typedef typename _Ht::reference reference; |
typedef typename _Ht::const_reference const_reference; |
typedef typename _Ht::iterator iterator; |
typedef typename _Ht::const_iterator const_iterator; |
typedef typename _Ht::allocator_type allocator_type; |
hasher hash_funct() const { return _M_ht.hash_funct(); } |
key_equal key_eq() const { return _M_ht.key_eq(); } |
allocator_type get_allocator() const { return _M_ht.get_allocator(); } |
public: |
hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} |
explicit hash_map(size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) {} |
hash_map(size_type __n, const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) {} |
hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) {} |
template <class _InputIterator> |
hash_map(_InputIterator __f, _InputIterator __l) |
: _M_ht(100, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_unique(__f, __l); } |
template <class _InputIterator> |
hash_map(_InputIterator __f, _InputIterator __l, size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_unique(__f, __l); } |
template <class _InputIterator> |
hash_map(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) |
{ _M_ht.insert_unique(__f, __l); } |
template <class _InputIterator> |
hash_map(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) |
{ _M_ht.insert_unique(__f, __l); } |
public: |
size_type size() const { return _M_ht.size(); } |
size_type max_size() const { return _M_ht.max_size(); } |
bool empty() const { return _M_ht.empty(); } |
void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } |
template <class _K1, class _T1, class _HF, class _EqK, class _Al> |
friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, |
const hash_map<_K1, _T1, _HF, _EqK, _Al>&); |
iterator begin() { return _M_ht.begin(); } |
iterator end() { return _M_ht.end(); } |
const_iterator begin() const { return _M_ht.begin(); } |
const_iterator end() const { return _M_ht.end(); } |
public: |
pair<iterator,bool> insert(const value_type& __obj) |
{ return _M_ht.insert_unique(__obj); } |
template <class _InputIterator> |
void insert(_InputIterator __f, _InputIterator __l) |
{ _M_ht.insert_unique(__f,__l); } |
pair<iterator,bool> insert_noresize(const value_type& __obj) |
{ return _M_ht.insert_unique_noresize(__obj); } |
iterator find(const key_type& __key) { return _M_ht.find(__key); } |
const_iterator find(const key_type& __key) const |
{ return _M_ht.find(__key); } |
_Tp& operator[](const key_type& __key) { |
return _M_ht.find_or_insert(value_type(__key, _Tp())).second; |
} |
size_type count(const key_type& __key) const { return _M_ht.count(__key); } |
pair<iterator, iterator> equal_range(const key_type& __key) |
{ return _M_ht.equal_range(__key); } |
pair<const_iterator, const_iterator> |
equal_range(const key_type& __key) const |
{ return _M_ht.equal_range(__key); } |
size_type erase(const key_type& __key) {return _M_ht.erase(__key); } |
void erase(iterator __it) { _M_ht.erase(__it); } |
void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } |
void clear() { _M_ht.clear(); } |
void resize(size_type __hint) { _M_ht.resize(__hint); } |
size_type bucket_count() const { return _M_ht.bucket_count(); } |
size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } |
size_type elems_in_bucket(size_type __n) const |
{ return _M_ht.elems_in_bucket(__n); } |
}; |
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> |
inline bool |
operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) |
{ |
return __hm1._M_ht == __hm2._M_ht; |
} |
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> |
inline bool |
operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) { |
return !(__hm1 == __hm2); |
} |
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> |
inline void |
swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) |
{ |
__hm1.swap(__hm2); |
} |
// Forward declaration of equality operator; needed for friend declaration. |
template <class _Key, class _Tp, |
class _HashFcn = hash<_Key>, |
class _EqualKey = equal_to<_Key>, |
class _Alloc = allocator<_Tp> > |
class hash_multimap; |
template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> |
inline bool |
operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, |
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); |
template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc> |
class hash_multimap |
{ |
// concept requirements |
__glibcpp_class_requires(_Key, _SGIAssignableConcept); |
__glibcpp_class_requires(_Tp, _SGIAssignableConcept); |
__glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept); |
__glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept); |
private: |
typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, |
_Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> |
_Ht; |
_Ht _M_ht; |
public: |
typedef typename _Ht::key_type key_type; |
typedef _Tp data_type; |
typedef _Tp mapped_type; |
typedef typename _Ht::value_type value_type; |
typedef typename _Ht::hasher hasher; |
typedef typename _Ht::key_equal key_equal; |
typedef typename _Ht::size_type size_type; |
typedef typename _Ht::difference_type difference_type; |
typedef typename _Ht::pointer pointer; |
typedef typename _Ht::const_pointer const_pointer; |
typedef typename _Ht::reference reference; |
typedef typename _Ht::const_reference const_reference; |
typedef typename _Ht::iterator iterator; |
typedef typename _Ht::const_iterator const_iterator; |
typedef typename _Ht::allocator_type allocator_type; |
hasher hash_funct() const { return _M_ht.hash_funct(); } |
key_equal key_eq() const { return _M_ht.key_eq(); } |
allocator_type get_allocator() const { return _M_ht.get_allocator(); } |
public: |
hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} |
explicit hash_multimap(size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) {} |
hash_multimap(size_type __n, const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) {} |
hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) {} |
template <class _InputIterator> |
hash_multimap(_InputIterator __f, _InputIterator __l) |
: _M_ht(100, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_equal(__f, __l); } |
template <class _InputIterator> |
hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_equal(__f, __l); } |
template <class _InputIterator> |
hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) |
{ _M_ht.insert_equal(__f, __l); } |
template <class _InputIterator> |
hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) |
{ _M_ht.insert_equal(__f, __l); } |
public: |
size_type size() const { return _M_ht.size(); } |
size_type max_size() const { return _M_ht.max_size(); } |
bool empty() const { return _M_ht.empty(); } |
void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } |
template <class _K1, class _T1, class _HF, class _EqK, class _Al> |
friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, |
const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); |
iterator begin() { return _M_ht.begin(); } |
iterator end() { return _M_ht.end(); } |
const_iterator begin() const { return _M_ht.begin(); } |
const_iterator end() const { return _M_ht.end(); } |
public: |
iterator insert(const value_type& __obj) |
{ return _M_ht.insert_equal(__obj); } |
template <class _InputIterator> |
void insert(_InputIterator __f, _InputIterator __l) |
{ _M_ht.insert_equal(__f,__l); } |
iterator insert_noresize(const value_type& __obj) |
{ return _M_ht.insert_equal_noresize(__obj); } |
iterator find(const key_type& __key) { return _M_ht.find(__key); } |
const_iterator find(const key_type& __key) const |
{ return _M_ht.find(__key); } |
size_type count(const key_type& __key) const { return _M_ht.count(__key); } |
pair<iterator, iterator> equal_range(const key_type& __key) |
{ return _M_ht.equal_range(__key); } |
pair<const_iterator, const_iterator> |
equal_range(const key_type& __key) const |
{ return _M_ht.equal_range(__key); } |
size_type erase(const key_type& __key) {return _M_ht.erase(__key); } |
void erase(iterator __it) { _M_ht.erase(__it); } |
void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } |
void clear() { _M_ht.clear(); } |
public: |
void resize(size_type __hint) { _M_ht.resize(__hint); } |
size_type bucket_count() const { return _M_ht.bucket_count(); } |
size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } |
size_type elems_in_bucket(size_type __n) const |
{ return _M_ht.elems_in_bucket(__n); } |
}; |
template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> |
inline bool |
operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, |
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) |
{ |
return __hm1._M_ht == __hm2._M_ht; |
} |
template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> |
inline bool |
operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, |
const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) { |
return !(__hm1 == __hm2); |
} |
template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> |
inline void |
swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, |
hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) |
{ |
__hm1.swap(__hm2); |
} |
// Specialization of insert_iterator so that it will work for hash_map |
// and hash_multimap. |
template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> |
class insert_iterator<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { |
protected: |
typedef hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; |
_Container* container; |
public: |
typedef _Container container_type; |
typedef output_iterator_tag iterator_category; |
typedef void value_type; |
typedef void difference_type; |
typedef void pointer; |
typedef void reference; |
insert_iterator(_Container& __x) : container(&__x) {} |
insert_iterator(_Container& __x, typename _Container::iterator) |
: container(&__x) {} |
insert_iterator<_Container>& |
operator=(const typename _Container::value_type& __value) { |
container->insert(__value); |
return *this; |
} |
insert_iterator<_Container>& operator*() { return *this; } |
insert_iterator<_Container>& operator++() { return *this; } |
insert_iterator<_Container>& operator++(int) { return *this; } |
}; |
template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> |
class insert_iterator<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { |
protected: |
typedef hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; |
_Container* container; |
typename _Container::iterator iter; |
public: |
typedef _Container container_type; |
typedef output_iterator_tag iterator_category; |
typedef void value_type; |
typedef void difference_type; |
typedef void pointer; |
typedef void reference; |
insert_iterator(_Container& __x) : container(&__x) {} |
insert_iterator(_Container& __x, typename _Container::iterator) |
: container(&__x) {} |
insert_iterator<_Container>& |
operator=(const typename _Container::value_type& __value) { |
container->insert(__value); |
return *this; |
} |
insert_iterator<_Container>& operator*() { return *this; } |
insert_iterator<_Container>& operator++() { return *this; } |
insert_iterator<_Container>& operator++(int) { return *this; } |
}; |
} // namespace std |
#endif /* __SGI_STL_INTERNAL_HASH_MAP_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/hash_set |
---|
0,0 → 1,396 |
/* |
* Copyright (c) 1996 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
* |
* Copyright (c) 1994 |
* Hewlett-Packard Company |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Hewlett-Packard Company makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#ifndef __SGI_STL_INTERNAL_HASH_SET_H |
#define __SGI_STL_INTERNAL_HASH_SET_H |
#include <ext/stl_hashtable.h> |
#include <bits/concept_check.h> |
namespace std |
{ |
// Forward declaration of equality operator; needed for friend declaration. |
template <class _Value, |
class _HashFcn = hash<_Value>, |
class _EqualKey = equal_to<_Value>, |
class _Alloc = allocator<_Value> > |
class hash_set; |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
inline bool |
operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, |
const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2); |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
class hash_set |
{ |
// concept requirements |
__glibcpp_class_requires(_Value, _SGIAssignableConcept); |
__glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); |
__glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); |
private: |
typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, |
_EqualKey, _Alloc> _Ht; |
_Ht _M_ht; |
public: |
typedef typename _Ht::key_type key_type; |
typedef typename _Ht::value_type value_type; |
typedef typename _Ht::hasher hasher; |
typedef typename _Ht::key_equal key_equal; |
typedef typename _Ht::size_type size_type; |
typedef typename _Ht::difference_type difference_type; |
typedef typename _Ht::const_pointer pointer; |
typedef typename _Ht::const_pointer const_pointer; |
typedef typename _Ht::const_reference reference; |
typedef typename _Ht::const_reference const_reference; |
typedef typename _Ht::const_iterator iterator; |
typedef typename _Ht::const_iterator const_iterator; |
typedef typename _Ht::allocator_type allocator_type; |
hasher hash_funct() const { return _M_ht.hash_funct(); } |
key_equal key_eq() const { return _M_ht.key_eq(); } |
allocator_type get_allocator() const { return _M_ht.get_allocator(); } |
public: |
hash_set() |
: _M_ht(100, hasher(), key_equal(), allocator_type()) {} |
explicit hash_set(size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) {} |
hash_set(size_type __n, const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) {} |
hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) {} |
template <class _InputIterator> |
hash_set(_InputIterator __f, _InputIterator __l) |
: _M_ht(100, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_unique(__f, __l); } |
template <class _InputIterator> |
hash_set(_InputIterator __f, _InputIterator __l, size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_unique(__f, __l); } |
template <class _InputIterator> |
hash_set(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) |
{ _M_ht.insert_unique(__f, __l); } |
template <class _InputIterator> |
hash_set(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) |
{ _M_ht.insert_unique(__f, __l); } |
public: |
size_type size() const { return _M_ht.size(); } |
size_type max_size() const { return _M_ht.max_size(); } |
bool empty() const { return _M_ht.empty(); } |
void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); } |
template <class _Val, class _HF, class _EqK, class _Al> |
friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&, |
const hash_set<_Val, _HF, _EqK, _Al>&); |
iterator begin() const { return _M_ht.begin(); } |
iterator end() const { return _M_ht.end(); } |
public: |
pair<iterator, bool> insert(const value_type& __obj) |
{ |
pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); |
return pair<iterator,bool>(__p.first, __p.second); |
} |
template <class _InputIterator> |
void insert(_InputIterator __f, _InputIterator __l) |
{ _M_ht.insert_unique(__f,__l); } |
pair<iterator, bool> insert_noresize(const value_type& __obj) |
{ |
pair<typename _Ht::iterator, bool> __p = |
_M_ht.insert_unique_noresize(__obj); |
return pair<iterator, bool>(__p.first, __p.second); |
} |
iterator find(const key_type& __key) const { return _M_ht.find(__key); } |
size_type count(const key_type& __key) const { return _M_ht.count(__key); } |
pair<iterator, iterator> equal_range(const key_type& __key) const |
{ return _M_ht.equal_range(__key); } |
size_type erase(const key_type& __key) {return _M_ht.erase(__key); } |
void erase(iterator __it) { _M_ht.erase(__it); } |
void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } |
void clear() { _M_ht.clear(); } |
public: |
void resize(size_type __hint) { _M_ht.resize(__hint); } |
size_type bucket_count() const { return _M_ht.bucket_count(); } |
size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } |
size_type elems_in_bucket(size_type __n) const |
{ return _M_ht.elems_in_bucket(__n); } |
}; |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
inline bool |
operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, |
const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) |
{ |
return __hs1._M_ht == __hs2._M_ht; |
} |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
inline bool |
operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, |
const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) { |
return !(__hs1 == __hs2); |
} |
template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> |
inline void |
swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, |
hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) |
{ |
__hs1.swap(__hs2); |
} |
template <class _Value, |
class _HashFcn = hash<_Value>, |
class _EqualKey = equal_to<_Value>, |
class _Alloc = allocator<_Value> > |
class hash_multiset; |
template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> |
inline bool |
operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, |
const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2); |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
class hash_multiset |
{ |
// concept requirements |
__glibcpp_class_requires(_Value, _SGIAssignableConcept); |
__glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); |
__glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); |
private: |
typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, |
_EqualKey, _Alloc> _Ht; |
_Ht _M_ht; |
public: |
typedef typename _Ht::key_type key_type; |
typedef typename _Ht::value_type value_type; |
typedef typename _Ht::hasher hasher; |
typedef typename _Ht::key_equal key_equal; |
typedef typename _Ht::size_type size_type; |
typedef typename _Ht::difference_type difference_type; |
typedef typename _Ht::const_pointer pointer; |
typedef typename _Ht::const_pointer const_pointer; |
typedef typename _Ht::const_reference reference; |
typedef typename _Ht::const_reference const_reference; |
typedef typename _Ht::const_iterator iterator; |
typedef typename _Ht::const_iterator const_iterator; |
typedef typename _Ht::allocator_type allocator_type; |
hasher hash_funct() const { return _M_ht.hash_funct(); } |
key_equal key_eq() const { return _M_ht.key_eq(); } |
allocator_type get_allocator() const { return _M_ht.get_allocator(); } |
public: |
hash_multiset() |
: _M_ht(100, hasher(), key_equal(), allocator_type()) {} |
explicit hash_multiset(size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) {} |
hash_multiset(size_type __n, const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) {} |
hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) {} |
template <class _InputIterator> |
hash_multiset(_InputIterator __f, _InputIterator __l) |
: _M_ht(100, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_equal(__f, __l); } |
template <class _InputIterator> |
hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) |
: _M_ht(__n, hasher(), key_equal(), allocator_type()) |
{ _M_ht.insert_equal(__f, __l); } |
template <class _InputIterator> |
hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf) |
: _M_ht(__n, __hf, key_equal(), allocator_type()) |
{ _M_ht.insert_equal(__f, __l); } |
template <class _InputIterator> |
hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, |
const hasher& __hf, const key_equal& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_ht(__n, __hf, __eql, __a) |
{ _M_ht.insert_equal(__f, __l); } |
public: |
size_type size() const { return _M_ht.size(); } |
size_type max_size() const { return _M_ht.max_size(); } |
bool empty() const { return _M_ht.empty(); } |
void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); } |
template <class _Val, class _HF, class _EqK, class _Al> |
friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&, |
const hash_multiset<_Val, _HF, _EqK, _Al>&); |
iterator begin() const { return _M_ht.begin(); } |
iterator end() const { return _M_ht.end(); } |
public: |
iterator insert(const value_type& __obj) |
{ return _M_ht.insert_equal(__obj); } |
template <class _InputIterator> |
void insert(_InputIterator __f, _InputIterator __l) |
{ _M_ht.insert_equal(__f,__l); } |
iterator insert_noresize(const value_type& __obj) |
{ return _M_ht.insert_equal_noresize(__obj); } |
iterator find(const key_type& __key) const { return _M_ht.find(__key); } |
size_type count(const key_type& __key) const { return _M_ht.count(__key); } |
pair<iterator, iterator> equal_range(const key_type& __key) const |
{ return _M_ht.equal_range(__key); } |
size_type erase(const key_type& __key) {return _M_ht.erase(__key); } |
void erase(iterator __it) { _M_ht.erase(__it); } |
void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } |
void clear() { _M_ht.clear(); } |
public: |
void resize(size_type __hint) { _M_ht.resize(__hint); } |
size_type bucket_count() const { return _M_ht.bucket_count(); } |
size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } |
size_type elems_in_bucket(size_type __n) const |
{ return _M_ht.elems_in_bucket(__n); } |
}; |
template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> |
inline bool |
operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, |
const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) |
{ |
return __hs1._M_ht == __hs2._M_ht; |
} |
template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> |
inline bool |
operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, |
const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { |
return !(__hs1 == __hs2); |
} |
template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> |
inline void |
swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, |
hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { |
__hs1.swap(__hs2); |
} |
// Specialization of insert_iterator so that it will work for hash_set |
// and hash_multiset. |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
class insert_iterator<hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > { |
protected: |
typedef hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; |
_Container* container; |
public: |
typedef _Container container_type; |
typedef output_iterator_tag iterator_category; |
typedef void value_type; |
typedef void difference_type; |
typedef void pointer; |
typedef void reference; |
insert_iterator(_Container& __x) : container(&__x) {} |
insert_iterator(_Container& __x, typename _Container::iterator) |
: container(&__x) {} |
insert_iterator<_Container>& |
operator=(const typename _Container::value_type& __value) { |
container->insert(__value); |
return *this; |
} |
insert_iterator<_Container>& operator*() { return *this; } |
insert_iterator<_Container>& operator++() { return *this; } |
insert_iterator<_Container>& operator++(int) { return *this; } |
}; |
template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> |
class insert_iterator<hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { |
protected: |
typedef hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; |
_Container* container; |
typename _Container::iterator iter; |
public: |
typedef _Container container_type; |
typedef output_iterator_tag iterator_category; |
typedef void value_type; |
typedef void difference_type; |
typedef void pointer; |
typedef void reference; |
insert_iterator(_Container& __x) : container(&__x) {} |
insert_iterator(_Container& __x, typename _Container::iterator) |
: container(&__x) {} |
insert_iterator<_Container>& |
operator=(const typename _Container::value_type& __value) { |
container->insert(__value); |
return *this; |
} |
insert_iterator<_Container>& operator*() { return *this; } |
insert_iterator<_Container>& operator++() { return *this; } |
insert_iterator<_Container>& operator++(int) { return *this; } |
}; |
} // namespace std |
#endif /* __SGI_STL_INTERNAL_HASH_SET_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/rope |
---|
0,0 → 1,32 |
/* |
* Copyright (c) 1997 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
*/ |
#ifndef __SGI_STL_ROPE |
#define __SGI_STL_ROPE |
#include <bits/stl_algobase.h> |
#include <bits/stl_tempbuf.h> |
#include <bits/stl_algo.h> |
#include <bits/stl_function.h> |
#include <bits/stl_numeric.h> |
#include <bits/stl_alloc.h> |
#include <bits/stl_construct.h> |
#include <bits/stl_uninitialized.h> |
#include <ext/stl_hash_fun.h> |
#include <ext/stl_rope.h> |
#endif /* __SGI_STL_ROPE */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/ropeimpl.h |
---|
0,0 → 1,1509 |
/* |
* Copyright (c) 1997 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#include <bits/std_cstdio.h> |
#include <bits/std_iostream.h> |
#ifdef __STL_USE_EXCEPTIONS |
# include <bits/std_stdexcept.h> |
#endif |
namespace std |
{ |
// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf |
// if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. |
// Results in a valid buf_ptr if the iterator can be legitimately |
// dereferenced. |
template <class _CharT, class _Alloc> |
void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( |
_Rope_iterator_base<_CharT,_Alloc>& __x) |
{ |
const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; |
size_t __leaf_pos = __x._M_leaf_pos; |
size_t __pos = __x._M_current_pos; |
switch(__leaf->_M_tag) { |
case _RopeRep::_S_leaf: |
__x._M_buf_start = |
((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data; |
__x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); |
__x._M_buf_end = __x._M_buf_start + __leaf->_M_size; |
break; |
case _RopeRep::_S_function: |
case _RopeRep::_S_substringfn: |
{ |
size_t __len = _S_iterator_buf_len; |
size_t __buf_start_pos = __leaf_pos; |
size_t __leaf_end = __leaf_pos + __leaf->_M_size; |
char_producer<_CharT>* __fn = |
((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn; |
if (__buf_start_pos + __len <= __pos) { |
__buf_start_pos = __pos - __len/4; |
if (__buf_start_pos + __len > __leaf_end) { |
__buf_start_pos = __leaf_end - __len; |
} |
} |
if (__buf_start_pos + __len > __leaf_end) { |
__len = __leaf_end - __buf_start_pos; |
} |
(*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); |
__x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); |
__x._M_buf_start = __x._M_tmp_buf; |
__x._M_buf_end = __x._M_tmp_buf + __len; |
} |
break; |
default: |
__stl_assert(0); |
} |
} |
// Set path and buffer inside a rope iterator. We assume that |
// pos and root are already set. |
template <class _CharT, class _Alloc> |
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache |
(_Rope_iterator_base<_CharT,_Alloc>& __x) |
{ |
const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1]; |
const _RopeRep* __curr_rope; |
int __curr_depth = -1; /* index into path */ |
size_t __curr_start_pos = 0; |
size_t __pos = __x._M_current_pos; |
unsigned char __dirns = 0; // Bit vector marking right turns in the path |
__stl_assert(__pos <= __x._M_root->_M_size); |
if (__pos >= __x._M_root->_M_size) { |
__x._M_buf_ptr = 0; |
return; |
} |
__curr_rope = __x._M_root; |
if (0 != __curr_rope->_M_c_string) { |
/* Treat the root as a leaf. */ |
__x._M_buf_start = __curr_rope->_M_c_string; |
__x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; |
__x._M_buf_ptr = __curr_rope->_M_c_string + __pos; |
__x._M_path_end[0] = __curr_rope; |
__x._M_leaf_index = 0; |
__x._M_leaf_pos = 0; |
return; |
} |
for(;;) { |
++__curr_depth; |
__stl_assert(__curr_depth <= _RopeRep::_S_max_rope_depth); |
__path[__curr_depth] = __curr_rope; |
switch(__curr_rope->_M_tag) { |
case _RopeRep::_S_leaf: |
case _RopeRep::_S_function: |
case _RopeRep::_S_substringfn: |
__x._M_leaf_pos = __curr_start_pos; |
goto done; |
case _RopeRep::_S_concat: |
{ |
_Rope_RopeConcatenation<_CharT,_Alloc>* __c = |
(_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope; |
_RopeRep* __left = __c->_M_left; |
size_t __left_len = __left->_M_size; |
__dirns <<= 1; |
if (__pos >= __curr_start_pos + __left_len) { |
__dirns |= 1; |
__curr_rope = __c->_M_right; |
__curr_start_pos += __left_len; |
} else { |
__curr_rope = __left; |
} |
} |
break; |
} |
} |
done: |
// Copy last section of path into _M_path_end. |
{ |
int __i = -1; |
int __j = __curr_depth + 1 - _S_path_cache_len; |
if (__j < 0) __j = 0; |
while (__j <= __curr_depth) { |
__x._M_path_end[++__i] = __path[__j++]; |
} |
__x._M_leaf_index = __i; |
} |
__x._M_path_directions = __dirns; |
_S_setbuf(__x); |
} |
// Specialized version of the above. Assumes that |
// the path cache is valid for the previous position. |
template <class _CharT, class _Alloc> |
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr |
(_Rope_iterator_base<_CharT,_Alloc>& __x) |
{ |
int __current_index = __x._M_leaf_index; |
const _RopeRep* __current_node = __x._M_path_end[__current_index]; |
size_t __len = __current_node->_M_size; |
size_t __node_start_pos = __x._M_leaf_pos; |
unsigned char __dirns = __x._M_path_directions; |
_Rope_RopeConcatenation<_CharT,_Alloc>* __c; |
__stl_assert(__x._M_current_pos <= __x._M_root->_M_size); |
if (__x._M_current_pos - __node_start_pos < __len) { |
/* More stuff in this leaf, we just didn't cache it. */ |
_S_setbuf(__x); |
return; |
} |
__stl_assert(__node_start_pos + __len == __x._M_current_pos); |
// node_start_pos is starting position of last_node. |
while (--__current_index >= 0) { |
if (!(__dirns & 1) /* Path turned left */) |
break; |
__current_node = __x._M_path_end[__current_index]; |
__c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node; |
// Otherwise we were in the right child. Thus we should pop |
// the concatenation node. |
__node_start_pos -= __c->_M_left->_M_size; |
__dirns >>= 1; |
} |
if (__current_index < 0) { |
// We underflowed the cache. Punt. |
_S_setcache(__x); |
return; |
} |
__current_node = __x._M_path_end[__current_index]; |
__c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node; |
// current_node is a concatenation node. We are positioned on the first |
// character in its right child. |
// node_start_pos is starting position of current_node. |
__node_start_pos += __c->_M_left->_M_size; |
__current_node = __c->_M_right; |
__x._M_path_end[++__current_index] = __current_node; |
__dirns |= 1; |
while (_RopeRep::_S_concat == __current_node->_M_tag) { |
++__current_index; |
if (_S_path_cache_len == __current_index) { |
int __i; |
for (__i = 0; __i < _S_path_cache_len-1; __i++) { |
__x._M_path_end[__i] = __x._M_path_end[__i+1]; |
} |
--__current_index; |
} |
__current_node = |
((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left; |
__x._M_path_end[__current_index] = __current_node; |
__dirns <<= 1; |
// node_start_pos is unchanged. |
} |
__x._M_leaf_index = __current_index; |
__x._M_leaf_pos = __node_start_pos; |
__x._M_path_directions = __dirns; |
_S_setbuf(__x); |
} |
template <class _CharT, class _Alloc> |
void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) { |
_M_current_pos += __n; |
if (0 != _M_buf_ptr) { |
size_t __chars_left = _M_buf_end - _M_buf_ptr; |
if (__chars_left > __n) { |
_M_buf_ptr += __n; |
} else if (__chars_left == __n) { |
_M_buf_ptr += __n; |
_S_setcache_for_incr(*this); |
} else { |
_M_buf_ptr = 0; |
} |
} |
} |
template <class _CharT, class _Alloc> |
void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) { |
if (0 != _M_buf_ptr) { |
size_t __chars_left = _M_buf_ptr - _M_buf_start; |
if (__chars_left >= __n) { |
_M_buf_ptr -= __n; |
} else { |
_M_buf_ptr = 0; |
} |
} |
_M_current_pos -= __n; |
} |
template <class _CharT, class _Alloc> |
void _Rope_iterator<_CharT,_Alloc>::_M_check() { |
if (_M_root_rope->_M_tree_ptr != _M_root) { |
// _Rope was modified. Get things fixed up. |
_RopeRep::_S_unref(_M_root); |
_M_root = _M_root_rope->_M_tree_ptr; |
_RopeRep::_S_ref(_M_root); |
_M_buf_ptr = 0; |
} |
} |
template <class _CharT, class _Alloc> |
inline |
_Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator( |
const _Rope_iterator<_CharT,_Alloc>& __x) |
: _Rope_iterator_base<_CharT,_Alloc>(__x) |
{ } |
template <class _CharT, class _Alloc> |
inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator( |
rope<_CharT,_Alloc>& __r, size_t __pos) |
: _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), |
_M_root_rope(&__r) |
{ |
_RopeRep::_S_ref(_M_root); |
} |
template <class _CharT, class _Alloc> |
inline size_t |
rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s) |
{ |
const _CharT* __p = __s; |
while (!_S_is0(*__p)) { ++__p; } |
return (__p - __s); |
} |
#ifndef __GC |
template <class _CharT, class _Alloc> |
inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string() |
{ |
_CharT* __cstr = _M_c_string; |
if (0 != __cstr) { |
size_t __size = _M_size + 1; |
destroy(__cstr, __cstr + __size); |
_Data_deallocate(__cstr, __size); |
} |
} |
template <class _CharT, class _Alloc> |
inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s, |
size_t __n, |
allocator_type __a) |
{ |
if (!_S_is_basic_char_type((_CharT*)0)) { |
destroy(__s, __s + __n); |
} |
// This has to be a static member, so this gets a bit messy |
__a.deallocate( |
__s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n)); |
} |
// There are several reasons for not doing this with virtual destructors |
// and a class specific delete operator: |
// - A class specific delete operator can't easily get access to |
// allocator instances if we need them. |
// - Any virtual function would need a 4 or byte vtable pointer; |
// this only requires a one byte tag per object. |
template <class _CharT, class _Alloc> |
void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree() |
{ |
switch(_M_tag) { |
case _S_leaf: |
{ |
_Rope_RopeLeaf<_CharT,_Alloc>* __l |
= (_Rope_RopeLeaf<_CharT,_Alloc>*)this; |
__l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf(); |
_L_deallocate(__l, 1); |
break; |
} |
case _S_concat: |
{ |
_Rope_RopeConcatenation<_CharT,_Alloc>* __c |
= (_Rope_RopeConcatenation<_CharT,_Alloc>*)this; |
__c->_Rope_RopeConcatenation<_CharT,_Alloc>:: |
~_Rope_RopeConcatenation(); |
_C_deallocate(__c, 1); |
break; |
} |
case _S_function: |
{ |
_Rope_RopeFunction<_CharT,_Alloc>* __f |
= (_Rope_RopeFunction<_CharT,_Alloc>*)this; |
__f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction(); |
_F_deallocate(__f, 1); |
break; |
} |
case _S_substringfn: |
{ |
_Rope_RopeSubstring<_CharT,_Alloc>* __ss = |
(_Rope_RopeSubstring<_CharT,_Alloc>*)this; |
__ss->_Rope_RopeSubstring<_CharT,_Alloc>:: |
~_Rope_RopeSubstring(); |
_S_deallocate(__ss, 1); |
break; |
} |
} |
} |
#else |
template <class _CharT, class _Alloc> |
inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string |
(const _CharT*, size_t, allocator_type) |
{} |
#endif |
// Concatenate a C string onto a leaf rope by copying the rope data. |
// Used for short ropes. |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeLeaf* |
rope<_CharT,_Alloc>::_S_leaf_concat_char_iter |
(_RopeLeaf* __r, const _CharT* __iter, size_t __len) |
{ |
size_t __old_len = __r->_M_size; |
_CharT* __new_data = (_CharT*) |
_Data_allocate(_S_rounded_up_size(__old_len + __len)); |
_RopeLeaf* __result; |
uninitialized_copy_n(__r->_M_data, __old_len, __new_data); |
uninitialized_copy_n(__iter, __len, __new_data + __old_len); |
_S_cond_store_eos(__new_data[__old_len + __len]); |
__STL_TRY { |
__result = _S_new_RopeLeaf(__new_data, __old_len + __len, |
__r->get_allocator()); |
} |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, |
__r->get_allocator())); |
return __result; |
} |
#ifndef __GC |
// As above, but it's OK to clobber original if refcount is 1 |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeLeaf* |
rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter |
(_RopeLeaf* __r, const _CharT* __iter, size_t __len) |
{ |
__stl_assert(__r->_M_ref_count >= 1); |
if (__r->_M_ref_count > 1) |
return _S_leaf_concat_char_iter(__r, __iter, __len); |
size_t __old_len = __r->_M_size; |
if (_S_allocated_capacity(__old_len) >= __old_len + __len) { |
// The space has been partially initialized for the standard |
// character types. But that doesn't matter for those types. |
uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); |
if (_S_is_basic_char_type((_CharT*)0)) { |
_S_cond_store_eos(__r->_M_data[__old_len + __len]); |
__stl_assert(__r->_M_c_string == __r->_M_data); |
} else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) { |
__r->_M_free_c_string(); |
__r->_M_c_string = 0; |
} |
__r->_M_size = __old_len + __len; |
__stl_assert(__r->_M_ref_count == 1); |
__r->_M_ref_count = 2; |
return __r; |
} else { |
_RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); |
__stl_assert(__result->_M_ref_count == 1); |
return __result; |
} |
} |
#endif |
// Assumes left and right are not 0. |
// Does not increment (nor decrement on exception) child reference counts. |
// Result has ref count 1. |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeRep* |
rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right) |
{ |
_RopeConcatenation* __result = |
_S_new_RopeConcatenation(__left, __right, __left->get_allocator()); |
size_t __depth = __result->_M_depth; |
__stl_assert(__left->get_allocator() == __right->get_allocator()); |
if (__depth > 20 && (__result->_M_size < 1000 || |
__depth > _RopeRep::_S_max_rope_depth)) { |
_RopeRep* __balanced; |
__STL_TRY { |
__balanced = _S_balance(__result); |
# ifndef __GC |
if (__result != __balanced) { |
__stl_assert(1 == __result->_M_ref_count |
&& 1 == __balanced->_M_ref_count); |
} |
# endif |
__result->_M_unref_nonnil(); |
} |
__STL_UNWIND((_C_deallocate(__result,1))); |
// In case of exception, we need to deallocate |
// otherwise dangling result node. But caller |
// still owns its children. Thus unref is |
// inappropriate. |
return __balanced; |
} else { |
return __result; |
} |
} |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter |
(_RopeRep* __r, const _CharT*__s, size_t __slen) |
{ |
_RopeRep* __result; |
if (0 == __slen) { |
_S_ref(__r); |
return __r; |
} |
if (0 == __r) |
return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, |
__r->get_allocator()); |
if (_RopeRep::_S_leaf == __r->_M_tag && |
__r->_M_size + __slen <= _S_copy_max) { |
__result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); |
# ifndef __GC |
__stl_assert(1 == __result->_M_ref_count); |
# endif |
return __result; |
} |
if (_RopeRep::_S_concat == __r->_M_tag |
&& _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) { |
_RopeLeaf* __right = |
(_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); |
if (__right->_M_size + __slen <= _S_copy_max) { |
_RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; |
_RopeRep* __nright = |
_S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); |
__left->_M_ref_nonnil(); |
__STL_TRY { |
__result = _S_tree_concat(__left, __nright); |
} |
__STL_UNWIND(_S_unref(__left); _S_unref(__nright)); |
# ifndef __GC |
__stl_assert(1 == __result->_M_ref_count); |
# endif |
return __result; |
} |
} |
_RopeRep* __nright = |
__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); |
__STL_TRY { |
__r->_M_ref_nonnil(); |
__result = _S_tree_concat(__r, __nright); |
} |
__STL_UNWIND(_S_unref(__r); _S_unref(__nright)); |
# ifndef __GC |
__stl_assert(1 == __result->_M_ref_count); |
# endif |
return __result; |
} |
#ifndef __GC |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeRep* |
rope<_CharT,_Alloc>::_S_destr_concat_char_iter( |
_RopeRep* __r, const _CharT* __s, size_t __slen) |
{ |
_RopeRep* __result; |
if (0 == __r) |
return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, |
__r->get_allocator()); |
size_t __count = __r->_M_ref_count; |
size_t __orig_size = __r->_M_size; |
__stl_assert(__count >= 1); |
if (__count > 1) return _S_concat_char_iter(__r, __s, __slen); |
if (0 == __slen) { |
__r->_M_ref_count = 2; // One more than before |
return __r; |
} |
if (__orig_size + __slen <= _S_copy_max && |
_RopeRep::_S_leaf == __r->_M_tag) { |
__result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); |
return __result; |
} |
if (_RopeRep::_S_concat == __r->_M_tag) { |
_RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right); |
if (_RopeRep::_S_leaf == __right->_M_tag |
&& __right->_M_size + __slen <= _S_copy_max) { |
_RopeRep* __new_right = |
_S_destr_leaf_concat_char_iter(__right, __s, __slen); |
if (__right == __new_right) { |
__stl_assert(__new_right->_M_ref_count == 2); |
__new_right->_M_ref_count = 1; |
} else { |
__stl_assert(__new_right->_M_ref_count >= 1); |
__right->_M_unref_nonnil(); |
} |
__stl_assert(__r->_M_ref_count == 1); |
__r->_M_ref_count = 2; // One more than before. |
((_RopeConcatenation*)__r)->_M_right = __new_right; |
__r->_M_size = __orig_size + __slen; |
if (0 != __r->_M_c_string) { |
__r->_M_free_c_string(); |
__r->_M_c_string = 0; |
} |
return __r; |
} |
} |
_RopeRep* __right = |
__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); |
__r->_M_ref_nonnil(); |
__STL_TRY { |
__result = _S_tree_concat(__r, __right); |
} |
__STL_UNWIND(_S_unref(__r); _S_unref(__right)) |
__stl_assert(1 == __result->_M_ref_count); |
return __result; |
} |
#endif /* !__GC */ |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeRep* |
rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right) |
{ |
if (0 == __left) { |
_S_ref(__right); |
return __right; |
} |
if (0 == __right) { |
__left->_M_ref_nonnil(); |
return __left; |
} |
if (_RopeRep::_S_leaf == __right->_M_tag) { |
if (_RopeRep::_S_leaf == __left->_M_tag) { |
if (__right->_M_size + __left->_M_size <= _S_copy_max) { |
return _S_leaf_concat_char_iter((_RopeLeaf*)__left, |
((_RopeLeaf*)__right)->_M_data, |
__right->_M_size); |
} |
} else if (_RopeRep::_S_concat == __left->_M_tag |
&& _RopeRep::_S_leaf == |
((_RopeConcatenation*)__left)->_M_right->_M_tag) { |
_RopeLeaf* __leftright = |
(_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); |
if (__leftright->_M_size + __right->_M_size <= _S_copy_max) { |
_RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; |
_RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, |
((_RopeLeaf*)__right)->_M_data, |
__right->_M_size); |
__leftleft->_M_ref_nonnil(); |
__STL_TRY { |
return(_S_tree_concat(__leftleft, __rest)); |
} |
__STL_UNWIND(_S_unref(__leftleft); _S_unref(__rest)) |
} |
} |
} |
__left->_M_ref_nonnil(); |
__right->_M_ref_nonnil(); |
__STL_TRY { |
return(_S_tree_concat(__left, __right)); |
} |
__STL_UNWIND(_S_unref(__left); _S_unref(__right)); |
} |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeRep* |
rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base, |
size_t __start, size_t __endp1) |
{ |
if (0 == __base) return 0; |
size_t __len = __base->_M_size; |
size_t __adj_endp1; |
const size_t __lazy_threshold = 128; |
if (__endp1 >= __len) { |
if (0 == __start) { |
__base->_M_ref_nonnil(); |
return __base; |
} else { |
__adj_endp1 = __len; |
} |
} else { |
__adj_endp1 = __endp1; |
} |
switch(__base->_M_tag) { |
case _RopeRep::_S_concat: |
{ |
_RopeConcatenation* __c = (_RopeConcatenation*)__base; |
_RopeRep* __left = __c->_M_left; |
_RopeRep* __right = __c->_M_right; |
size_t __left_len = __left->_M_size; |
_RopeRep* __result; |
if (__adj_endp1 <= __left_len) { |
return _S_substring(__left, __start, __endp1); |
} else if (__start >= __left_len) { |
return _S_substring(__right, __start - __left_len, |
__adj_endp1 - __left_len); |
} |
_Self_destruct_ptr __left_result( |
_S_substring(__left, __start, __left_len)); |
_Self_destruct_ptr __right_result( |
_S_substring(__right, 0, __endp1 - __left_len)); |
__result = _S_concat(__left_result, __right_result); |
# ifndef __GC |
__stl_assert(1 == __result->_M_ref_count); |
# endif |
return __result; |
} |
case _RopeRep::_S_leaf: |
{ |
_RopeLeaf* __l = (_RopeLeaf*)__base; |
_RopeLeaf* __result; |
size_t __result_len; |
if (__start >= __adj_endp1) return 0; |
__result_len = __adj_endp1 - __start; |
if (__result_len > __lazy_threshold) goto lazy; |
# ifdef __GC |
const _CharT* __section = __l->_M_data + __start; |
__result = _S_new_RopeLeaf(__section, __result_len, |
__base->get_allocator()); |
__result->_M_c_string = 0; // Not eos terminated. |
# else |
// We should sometimes create substring node instead. |
__result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR( |
__l->_M_data + __start, __result_len, |
__base->get_allocator()); |
# endif |
return __result; |
} |
case _RopeRep::_S_substringfn: |
// Avoid introducing multiple layers of substring nodes. |
{ |
_RopeSubstring* __old = (_RopeSubstring*)__base; |
size_t __result_len; |
if (__start >= __adj_endp1) return 0; |
__result_len = __adj_endp1 - __start; |
if (__result_len > __lazy_threshold) { |
_RopeSubstring* __result = |
_S_new_RopeSubstring(__old->_M_base, |
__start + __old->_M_start, |
__adj_endp1 - __start, |
__base->get_allocator()); |
return __result; |
} // *** else fall through: *** |
} |
case _RopeRep::_S_function: |
{ |
_RopeFunction* __f = (_RopeFunction*)__base; |
_CharT* __section; |
size_t __result_len; |
if (__start >= __adj_endp1) return 0; |
__result_len = __adj_endp1 - __start; |
if (__result_len > __lazy_threshold) goto lazy; |
__section = (_CharT*) |
_Data_allocate(_S_rounded_up_size(__result_len)); |
__STL_TRY { |
(*(__f->_M_fn))(__start, __result_len, __section); |
} |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING( |
__section, __result_len, __base->get_allocator())); |
_S_cond_store_eos(__section[__result_len]); |
return _S_new_RopeLeaf(__section, __result_len, |
__base->get_allocator()); |
} |
} |
/*NOTREACHED*/ |
__stl_assert(false); |
lazy: |
{ |
// Create substring node. |
return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, |
__base->get_allocator()); |
} |
} |
template<class _CharT> |
class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> { |
private: |
_CharT* _M_buf_ptr; |
public: |
_Rope_flatten_char_consumer(_CharT* __buffer) { |
_M_buf_ptr = __buffer; |
}; |
~_Rope_flatten_char_consumer() {} |
bool operator() (const _CharT* __leaf, size_t __n) { |
uninitialized_copy_n(__leaf, __n, _M_buf_ptr); |
_M_buf_ptr += __n; |
return true; |
} |
}; |
template<class _CharT> |
class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> { |
private: |
_CharT _M_pattern; |
public: |
size_t _M_count; // Number of nonmatching characters |
_Rope_find_char_char_consumer(_CharT __p) |
: _M_pattern(__p), _M_count(0) {} |
~_Rope_find_char_char_consumer() {} |
bool operator() (const _CharT* __leaf, size_t __n) { |
size_t __i; |
for (__i = 0; __i < __n; __i++) { |
if (__leaf[__i] == _M_pattern) { |
_M_count += __i; return false; |
} |
} |
_M_count += __n; return true; |
} |
}; |
template<class _CharT, class _Traits> |
// Here _CharT is both the stream and rope character type. |
class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> { |
private: |
typedef basic_ostream<_CharT,_Traits> _Insert_ostream; |
_Insert_ostream& _M_o; |
public: |
_Rope_insert_char_consumer(_Insert_ostream& __writer) |
: _M_o(__writer) {}; |
~_Rope_insert_char_consumer() { }; |
// Caller is presumed to own the ostream |
bool operator() (const _CharT* __leaf, size_t __n); |
// Returns true to continue traversal. |
}; |
template<class _CharT, class _Traits> |
bool _Rope_insert_char_consumer<_CharT, _Traits>::operator() |
(const _CharT* __leaf, size_t __n) |
{ |
size_t __i; |
// We assume that formatting is set up correctly for each element. |
for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]); |
return true; |
} |
template <class _CharT, class _Alloc> |
bool rope<_CharT, _Alloc>::_S_apply_to_pieces( |
_Rope_char_consumer<_CharT>& __c, |
const _RopeRep* __r, |
size_t __begin, size_t __end) |
{ |
if (0 == __r) return true; |
switch(__r->_M_tag) { |
case _RopeRep::_S_concat: |
{ |
_RopeConcatenation* __conc = (_RopeConcatenation*)__r; |
_RopeRep* __left = __conc->_M_left; |
size_t __left_len = __left->_M_size; |
if (__begin < __left_len) { |
size_t __left_end = min(__left_len, __end); |
if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) |
return false; |
} |
if (__end > __left_len) { |
_RopeRep* __right = __conc->_M_right; |
size_t __right_start = max(__left_len, __begin); |
if (!_S_apply_to_pieces(__c, __right, |
__right_start - __left_len, |
__end - __left_len)) { |
return false; |
} |
} |
} |
return true; |
case _RopeRep::_S_leaf: |
{ |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
return __c(__l->_M_data + __begin, __end - __begin); |
} |
case _RopeRep::_S_function: |
case _RopeRep::_S_substringfn: |
{ |
_RopeFunction* __f = (_RopeFunction*)__r; |
size_t __len = __end - __begin; |
bool __result; |
_CharT* __buffer = |
(_CharT*)alloc::allocate(__len * sizeof(_CharT)); |
__STL_TRY { |
(*(__f->_M_fn))(__begin, __len, __buffer); |
__result = __c(__buffer, __len); |
alloc::deallocate(__buffer, __len * sizeof(_CharT)); |
} |
__STL_UNWIND((alloc::deallocate(__buffer, |
__len * sizeof(_CharT)))) |
return __result; |
} |
default: |
__stl_assert(false); |
/*NOTREACHED*/ |
return false; |
} |
} |
template<class _CharT, class _Traits> |
inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) |
{ |
char __f = __o.fill(); |
size_t __i; |
for (__i = 0; __i < __n; __i++) __o.put(__f); |
} |
template <class _CharT> inline bool _Rope_is_simple(_CharT*) { return false; } |
inline bool _Rope_is_simple(char*) { return true; } |
inline bool _Rope_is_simple(wchar_t*) { return true; } |
template<class _CharT, class _Traits, class _Alloc> |
basic_ostream<_CharT, _Traits>& operator<< (basic_ostream<_CharT, _Traits>& __o, |
const rope<_CharT, _Alloc>& __r) |
{ |
size_t __w = __o.width(); |
bool __left = bool(__o.flags() & ios::left); |
size_t __pad_len; |
size_t __rope_len = __r.size(); |
_Rope_insert_char_consumer<_CharT, _Traits> __c(__o); |
bool __is_simple = _Rope_is_simple((_CharT*)0); |
if (__rope_len < __w) { |
__pad_len = __w - __rope_len; |
} else { |
__pad_len = 0; |
} |
if (!__is_simple) __o.width(__w/__rope_len); |
__STL_TRY { |
if (__is_simple && !__left && __pad_len > 0) { |
_Rope_fill(__o, __pad_len); |
} |
__r.apply_to_pieces(0, __r.size(), __c); |
if (__is_simple && __left && __pad_len > 0) { |
_Rope_fill(__o, __pad_len); |
} |
if (!__is_simple) |
__o.width(__w); |
} |
__STL_UNWIND(if (!__is_simple) __o.width(__w)) |
return __o; |
} |
template <class _CharT, class _Alloc> |
_CharT* |
rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, |
size_t __start, size_t __len, |
_CharT* __buffer) |
{ |
_Rope_flatten_char_consumer<_CharT> __c(__buffer); |
_S_apply_to_pieces(__c, __r, __start, __start + __len); |
return(__buffer + __len); |
} |
template <class _CharT, class _Alloc> |
size_t |
rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const |
{ |
_Rope_find_char_char_consumer<_CharT> __c(__pattern); |
_S_apply_to_pieces(__c, _M_tree_ptr, __start, size()); |
size_type __result_pos = __start + __c._M_count; |
# ifndef __STL_OLD_ROPE_SEMANTICS |
if (__result_pos == size()) __result_pos = npos; |
# endif |
return __result_pos; |
} |
template <class _CharT, class _Alloc> |
_CharT* |
rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer) |
{ |
if (0 == __r) return __buffer; |
switch(__r->_M_tag) { |
case _RopeRep::_S_concat: |
{ |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
_RopeRep* __left = __c->_M_left; |
_RopeRep* __right = __c->_M_right; |
_CharT* __rest = _S_flatten(__left, __buffer); |
return _S_flatten(__right, __rest); |
} |
case _RopeRep::_S_leaf: |
{ |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
return copy_n(__l->_M_data, __l->_M_size, __buffer).second; |
} |
case _RopeRep::_S_function: |
case _RopeRep::_S_substringfn: |
// We dont yet do anything with substring nodes. |
// This needs to be fixed before ropefiles will work well. |
{ |
_RopeFunction* __f = (_RopeFunction*)__r; |
(*(__f->_M_fn))(0, __f->_M_size, __buffer); |
return __buffer + __f->_M_size; |
} |
default: |
__stl_assert(false); |
/*NOTREACHED*/ |
return 0; |
} |
} |
// This needs work for _CharT != char |
template <class _CharT, class _Alloc> |
void |
rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent) |
{ |
for (int __i = 0; __i < __indent; __i++) putchar(' '); |
if (0 == __r) { |
printf("NULL\n"); return; |
} |
if (_RopeRep::_S_concat == __r->_M_tag) { |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
_RopeRep* __left = __c->_M_left; |
_RopeRep* __right = __c->_M_right; |
# ifdef __GC |
printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", |
__r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not"); |
# else |
printf("Concatenation %p (rc = %ld, depth = %d, " |
"len = %ld, %s balanced)\n", |
__r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, |
__r->_M_is_balanced? "" : "not"); |
# endif |
_S_dump(__left, __indent + 2); |
_S_dump(__right, __indent + 2); |
return; |
} else { |
char* __kind; |
switch (__r->_M_tag) { |
case _RopeRep::_S_leaf: |
__kind = "Leaf"; |
break; |
case _RopeRep::_S_function: |
__kind = "Function"; |
break; |
case _RopeRep::_S_substringfn: |
__kind = "Function representing substring"; |
break; |
default: |
__kind = "(corrupted kind field!)"; |
} |
# ifdef __GC |
printf("%s %p (depth = %d, len = %ld) ", |
__kind, __r, __r->_M_depth, __r->_M_size); |
# else |
printf("%s %p (rc = %ld, depth = %d, len = %ld) ", |
__kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); |
# endif |
if (_S_is_one_byte_char_type((_CharT*)0)) { |
const int __max_len = 40; |
_Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); |
_CharT __buffer[__max_len + 1]; |
bool __too_big = __r->_M_size > __prefix->_M_size; |
_S_flatten(__prefix, __buffer); |
__buffer[__prefix->_M_size] = _S_eos((_CharT*)0); |
printf("%s%s\n", |
(char*)__buffer, __too_big? "...\n" : "\n"); |
} else { |
printf("\n"); |
} |
} |
} |
template <class _CharT, class _Alloc> |
const unsigned long |
rope<_CharT,_Alloc>::_S_min_len[ |
_Rope_RopeRep<_CharT,_Alloc>::_S_max_rope_depth + 1] = { |
/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, |
/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, |
/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, |
/* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, |
/* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, |
/* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, |
/* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, |
/* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, |
/* 39 */165580141, /* 40 */267914296, /* 41 */433494437, |
/* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, |
/* 45 */2971215073u }; |
// These are Fibonacci numbers < 2**32. |
template <class _CharT, class _Alloc> |
rope<_CharT,_Alloc>::_RopeRep* |
rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r) |
{ |
_RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1]; |
_RopeRep* __result = 0; |
int __i; |
// Invariant: |
// The concatenation of forest in descending order is equal to __r. |
// __forest[__i]._M_size >= _S_min_len[__i] |
// __forest[__i]._M_depth = __i |
// References from forest are included in refcount. |
for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) |
__forest[__i] = 0; |
__STL_TRY { |
_S_add_to_forest(__r, __forest); |
for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) |
if (0 != __forest[__i]) { |
# ifndef __GC |
_Self_destruct_ptr __old(__result); |
# endif |
__result = _S_concat(__forest[__i], __result); |
__forest[__i]->_M_unref_nonnil(); |
# if !defined(__GC) && defined(__STL_USE_EXCEPTIONS) |
__forest[__i] = 0; |
# endif |
} |
} |
__STL_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; __i++) |
_S_unref(__forest[__i])) |
if (__result->_M_depth > _RopeRep::_S_max_rope_depth) { |
# ifdef __STL_USE_EXCEPTIONS |
__STL_THROW(length_error("rope too long")); |
# else |
abort(); |
# endif |
} |
return(__result); |
} |
template <class _CharT, class _Alloc> |
void |
rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) |
{ |
if (__r->_M_is_balanced) { |
_S_add_leaf_to_forest(__r, __forest); |
return; |
} |
__stl_assert(__r->_M_tag == _RopeRep::_S_concat); |
{ |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
_S_add_to_forest(__c->_M_left, __forest); |
_S_add_to_forest(__c->_M_right, __forest); |
} |
} |
template <class _CharT, class _Alloc> |
void |
rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) |
{ |
_RopeRep* __insertee; // included in refcount |
_RopeRep* __too_tiny = 0; // included in refcount |
int __i; // forest[0..__i-1] is empty |
size_t __s = __r->_M_size; |
for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) { |
if (0 != __forest[__i]) { |
# ifndef __GC |
_Self_destruct_ptr __old(__too_tiny); |
# endif |
__too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny); |
__forest[__i]->_M_unref_nonnil(); |
__forest[__i] = 0; |
} |
} |
{ |
# ifndef __GC |
_Self_destruct_ptr __old(__too_tiny); |
# endif |
__insertee = _S_concat_and_set_balanced(__too_tiny, __r); |
} |
// Too_tiny dead, and no longer included in refcount. |
// Insertee is live and included. |
__stl_assert(_S_is_almost_balanced(__insertee)); |
__stl_assert(__insertee->_M_depth <= __r->_M_depth + 1); |
for (;; ++__i) { |
if (0 != __forest[__i]) { |
# ifndef __GC |
_Self_destruct_ptr __old(__insertee); |
# endif |
__insertee = _S_concat_and_set_balanced(__forest[__i], __insertee); |
__forest[__i]->_M_unref_nonnil(); |
__forest[__i] = 0; |
__stl_assert(_S_is_almost_balanced(__insertee)); |
} |
__stl_assert(_S_min_len[__i] <= __insertee->_M_size); |
__stl_assert(__forest[__i] == 0); |
if (__i == _RopeRep::_S_max_rope_depth || |
__insertee->_M_size < _S_min_len[__i+1]) { |
__forest[__i] = __insertee; |
// refcount is OK since __insertee is now dead. |
return; |
} |
} |
} |
template <class _CharT, class _Alloc> |
_CharT |
rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i) |
{ |
__GC_CONST _CharT* __cstr = __r->_M_c_string; |
__stl_assert(__i < __r->_M_size); |
if (0 != __cstr) return __cstr[__i]; |
for(;;) { |
switch(__r->_M_tag) { |
case _RopeRep::_S_concat: |
{ |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
_RopeRep* __left = __c->_M_left; |
size_t __left_len = __left->_M_size; |
if (__i >= __left_len) { |
__i -= __left_len; |
__r = __c->_M_right; |
} else { |
__r = __left; |
} |
} |
break; |
case _RopeRep::_S_leaf: |
{ |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
return __l->_M_data[__i]; |
} |
case _RopeRep::_S_function: |
case _RopeRep::_S_substringfn: |
{ |
_RopeFunction* __f = (_RopeFunction*)__r; |
_CharT __result; |
(*(__f->_M_fn))(__i, 1, &__result); |
return __result; |
} |
} |
} |
} |
# ifndef __GC |
// Return a uniquely referenced character slot for the given |
// position, or 0 if that's not possible. |
template <class _CharT, class _Alloc> |
_CharT* |
rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i) |
{ |
_RopeRep* __clrstack[_RopeRep::_S_max_rope_depth]; |
size_t __csptr = 0; |
for(;;) { |
if (__r->_M_ref_count > 1) return 0; |
switch(__r->_M_tag) { |
case _RopeRep::_S_concat: |
{ |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
_RopeRep* __left = __c->_M_left; |
size_t __left_len = __left->_M_size; |
if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c; |
if (__i >= __left_len) { |
__i -= __left_len; |
__r = __c->_M_right; |
} else { |
__r = __left; |
} |
} |
break; |
case _RopeRep::_S_leaf: |
{ |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) |
__clrstack[__csptr++] = __l; |
while (__csptr > 0) { |
-- __csptr; |
_RopeRep* __d = __clrstack[__csptr]; |
__d->_M_free_c_string(); |
__d->_M_c_string = 0; |
} |
return __l->_M_data + __i; |
} |
case _RopeRep::_S_function: |
case _RopeRep::_S_substringfn: |
return 0; |
} |
} |
} |
# endif /* __GC */ |
// The following could be implemented trivially using |
// lexicographical_compare_3way. |
// We do a little more work to avoid dealing with rope iterators for |
// flat strings. |
template <class _CharT, class _Alloc> |
int |
rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left, |
const _RopeRep* __right) |
{ |
size_t __left_len; |
size_t __right_len; |
if (0 == __right) return 0 != __left; |
if (0 == __left) return -1; |
__left_len = __left->_M_size; |
__right_len = __right->_M_size; |
if (_RopeRep::_S_leaf == __left->_M_tag) { |
_RopeLeaf* __l = (_RopeLeaf*) __left; |
if (_RopeRep::_S_leaf == __right->_M_tag) { |
_RopeLeaf* __r = (_RopeLeaf*) __right; |
return lexicographical_compare_3way( |
__l->_M_data, __l->_M_data + __left_len, |
__r->_M_data, __r->_M_data + __right_len); |
} else { |
const_iterator __rstart(__right, 0); |
const_iterator __rend(__right, __right_len); |
return lexicographical_compare_3way( |
__l->_M_data, __l->_M_data + __left_len, |
__rstart, __rend); |
} |
} else { |
const_iterator __lstart(__left, 0); |
const_iterator __lend(__left, __left_len); |
if (_RopeRep::_S_leaf == __right->_M_tag) { |
_RopeLeaf* __r = (_RopeLeaf*) __right; |
return lexicographical_compare_3way( |
__lstart, __lend, |
__r->_M_data, __r->_M_data + __right_len); |
} else { |
const_iterator __rstart(__right, 0); |
const_iterator __rend(__right, __right_len); |
return lexicographical_compare_3way( |
__lstart, __lend, |
__rstart, __rend); |
} |
} |
} |
// Assignment to reference proxies. |
template <class _CharT, class _Alloc> |
_Rope_char_ref_proxy<_CharT, _Alloc>& |
_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) { |
_RopeRep* __old = _M_root->_M_tree_ptr; |
# ifndef __GC |
// First check for the case in which everything is uniquely |
// referenced. In that case we can do this destructively. |
_CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); |
if (0 != __ptr) { |
*__ptr = __c; |
return *this; |
} |
# endif |
_Self_destruct_ptr __left( |
_My_rope::_S_substring(__old, 0, _M_pos)); |
_Self_destruct_ptr __right( |
_My_rope::_S_substring(__old, _M_pos+1, __old->_M_size)); |
_Self_destruct_ptr __result_left( |
_My_rope::_S_destr_concat_char_iter(__left, &__c, 1)); |
# ifndef __GC |
__stl_assert(__left == __result_left || 1 == __result_left->_M_ref_count); |
# endif |
_RopeRep* __result = |
_My_rope::_S_concat(__result_left, __right); |
# ifndef __GC |
__stl_assert(1 <= __result->_M_ref_count); |
_RopeRep::_S_unref(__old); |
# endif |
_M_root->_M_tree_ptr = __result; |
return *this; |
} |
template <class _CharT, class _Alloc> |
inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const |
{ |
if (_M_current_valid) { |
return _M_current; |
} else { |
return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); |
} |
} |
template <class _CharT, class _Alloc> |
_Rope_char_ptr_proxy<_CharT, _Alloc> |
_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const { |
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); |
} |
template <class _CharT, class _Alloc> |
rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c, |
const allocator_type& __a) |
: _Base(__a) |
{ |
rope<_CharT,_Alloc> __result; |
const size_t __exponentiate_threshold = 32; |
size_t __exponent; |
size_t __rest; |
_CharT* __rest_buffer; |
_RopeRep* __remainder; |
rope<_CharT,_Alloc> __remainder_rope; |
if (0 == __n) |
return; |
__exponent = __n / __exponentiate_threshold; |
__rest = __n % __exponentiate_threshold; |
if (0 == __rest) { |
__remainder = 0; |
} else { |
__rest_buffer = _Data_allocate(_S_rounded_up_size(__rest)); |
uninitialized_fill_n(__rest_buffer, __rest, __c); |
_S_cond_store_eos(__rest_buffer[__rest]); |
__STL_TRY { |
__remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); |
} |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a)) |
} |
__remainder_rope._M_tree_ptr = __remainder; |
if (__exponent != 0) { |
_CharT* __base_buffer = |
_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); |
_RopeLeaf* __base_leaf; |
rope __base_rope; |
uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c); |
_S_cond_store_eos(__base_buffer[__exponentiate_threshold]); |
__STL_TRY { |
__base_leaf = _S_new_RopeLeaf(__base_buffer, |
__exponentiate_threshold, __a); |
} |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__base_buffer, |
__exponentiate_threshold, __a)) |
__base_rope._M_tree_ptr = __base_leaf; |
if (1 == __exponent) { |
__result = __base_rope; |
# ifndef __GC |
__stl_assert(2 == __result._M_tree_ptr->_M_ref_count); |
// One each for base_rope and __result |
# endif |
} else { |
__result = power(__base_rope, __exponent, |
_Rope_Concat_fn<_CharT,_Alloc>()); |
} |
if (0 != __remainder) { |
__result += __remainder_rope; |
} |
} else { |
__result = __remainder_rope; |
} |
_M_tree_ptr = __result._M_tree_ptr; |
_M_tree_ptr->_M_ref_nonnil(); |
} |
template<class _CharT, class _Alloc> |
_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1]; |
template<class _CharT, class _Alloc> |
const _CharT* rope<_CharT,_Alloc>::c_str() const { |
if (0 == _M_tree_ptr) { |
_S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, |
// but probably fast. |
return _S_empty_c_str; |
} |
__GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string; |
if (0 != __old_c_string) return(__old_c_string); |
size_t __s = size(); |
_CharT* __result = _Data_allocate(__s + 1); |
_S_flatten(_M_tree_ptr, __result); |
__result[__s] = _S_eos((_CharT*)0); |
# ifdef __GC |
_M_tree_ptr->_M_c_string = __result; |
# else |
if ((__old_c_string = (__GC_CONST _CharT*) |
_Atomic_swap((unsigned long *)(&(_M_tree_ptr->_M_c_string)), |
(unsigned long)__result)) != 0) { |
// It must have been added in the interim. Hence it had to have been |
// separately allocated. Deallocate the old copy, since we just |
// replaced it. |
destroy(__old_c_string, __old_c_string + __s + 1); |
_Data_deallocate(__old_c_string, __s + 1); |
} |
# endif |
return(__result); |
} |
template<class _CharT, class _Alloc> |
const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() { |
if (0 == _M_tree_ptr) { |
_S_empty_c_str[0] = _S_eos((_CharT*)0); |
return _S_empty_c_str; |
} |
__GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string; |
if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && 0 != __old_c_string) { |
return(__old_c_string); |
} |
size_t __s = size(); |
_CharT* __result = _Data_allocate(_S_rounded_up_size(__s)); |
_S_flatten(_M_tree_ptr, __result); |
__result[__s] = _S_eos((_CharT*)0); |
_M_tree_ptr->_M_unref_nonnil(); |
_M_tree_ptr = _S_new_RopeLeaf(__result, __s, get_allocator()); |
return(__result); |
} |
// Algorithm specializations. More should be added. |
template<class _Rope_iterator> // was templated on CharT and Alloc |
void // VC++ workaround |
_Rope_rotate(_Rope_iterator __first, |
_Rope_iterator __middle, |
_Rope_iterator __last) |
{ |
typedef typename _Rope_iterator::value_type _CharT; |
typedef typename _Rope_iterator::_allocator_type _Alloc; |
__stl_assert(__first.container() == __middle.container() |
&& __middle.container() == __last.container()); |
rope<_CharT,_Alloc>& __r(__first.container()); |
rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index()); |
rope<_CharT,_Alloc> __suffix = |
__r.substr(__last.index(), __r.size() - __last.index()); |
rope<_CharT,_Alloc> __part1 = |
__r.substr(__middle.index(), __last.index() - __middle.index()); |
rope<_CharT,_Alloc> __part2 = |
__r.substr(__first.index(), __middle.index() - __first.index()); |
__r = __prefix; |
__r += __part1; |
__r += __part2; |
__r += __suffix; |
} |
#if !defined(__GNUC__) |
// Appears to confuse g++ |
inline void rotate(_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __first, |
_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __middle, |
_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __last) { |
_Rope_rotate(__first, __middle, __last); |
} |
#endif |
# if 0 |
// Probably not useful for several reasons: |
// - for SGIs 7.1 compiler and probably some others, |
// this forces lots of rope<wchar_t, ...> instantiations, creating a |
// code bloat and compile time problem. (Fixed in 7.2.) |
// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive |
// for unicode strings. Unsigned short may be a better character |
// type. |
inline void rotate( |
_Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first, |
_Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle, |
_Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last) { |
_Rope_rotate(__first, __middle, __last); |
} |
# endif |
} // namespace std |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/slist |
---|
0,0 → 1,903 |
/* |
* Copyright (c) 1997 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#ifndef __SGI_STL_INTERNAL_SLIST_H |
#define __SGI_STL_INTERNAL_SLIST_H |
#include <bits/stl_algobase.h> |
#include <bits/stl_alloc.h> |
#include <bits/stl_construct.h> |
#include <bits/stl_uninitialized.h> |
#include <bits/concept_check.h> |
namespace std |
{ |
struct _Slist_node_base |
{ |
_Slist_node_base* _M_next; |
}; |
inline _Slist_node_base* |
__slist_make_link(_Slist_node_base* __prev_node, |
_Slist_node_base* __new_node) |
{ |
__new_node->_M_next = __prev_node->_M_next; |
__prev_node->_M_next = __new_node; |
return __new_node; |
} |
inline _Slist_node_base* |
__slist_previous(_Slist_node_base* __head, |
const _Slist_node_base* __node) |
{ |
while (__head && __head->_M_next != __node) |
__head = __head->_M_next; |
return __head; |
} |
inline const _Slist_node_base* |
__slist_previous(const _Slist_node_base* __head, |
const _Slist_node_base* __node) |
{ |
while (__head && __head->_M_next != __node) |
__head = __head->_M_next; |
return __head; |
} |
inline void __slist_splice_after(_Slist_node_base* __pos, |
_Slist_node_base* __before_first, |
_Slist_node_base* __before_last) |
{ |
if (__pos != __before_first && __pos != __before_last) { |
_Slist_node_base* __first = __before_first->_M_next; |
_Slist_node_base* __after = __pos->_M_next; |
__before_first->_M_next = __before_last->_M_next; |
__pos->_M_next = __first; |
__before_last->_M_next = __after; |
} |
} |
inline void |
__slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) |
{ |
_Slist_node_base* __before_last = __slist_previous(__head, 0); |
if (__before_last != __head) { |
_Slist_node_base* __after = __pos->_M_next; |
__pos->_M_next = __head->_M_next; |
__head->_M_next = 0; |
__before_last->_M_next = __after; |
} |
} |
inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node) |
{ |
_Slist_node_base* __result = __node; |
__node = __node->_M_next; |
__result->_M_next = 0; |
while(__node) { |
_Slist_node_base* __next = __node->_M_next; |
__node->_M_next = __result; |
__result = __node; |
__node = __next; |
} |
return __result; |
} |
inline size_t __slist_size(_Slist_node_base* __node) |
{ |
size_t __result = 0; |
for ( ; __node != 0; __node = __node->_M_next) |
++__result; |
return __result; |
} |
template <class _Tp> |
struct _Slist_node : public _Slist_node_base |
{ |
_Tp _M_data; |
}; |
struct _Slist_iterator_base |
{ |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
typedef forward_iterator_tag iterator_category; |
_Slist_node_base* _M_node; |
_Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {} |
void _M_incr() { _M_node = _M_node->_M_next; } |
bool operator==(const _Slist_iterator_base& __x) const { |
return _M_node == __x._M_node; |
} |
bool operator!=(const _Slist_iterator_base& __x) const { |
return _M_node != __x._M_node; |
} |
}; |
template <class _Tp, class _Ref, class _Ptr> |
struct _Slist_iterator : public _Slist_iterator_base |
{ |
typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; |
typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; |
typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; |
typedef _Tp value_type; |
typedef _Ptr pointer; |
typedef _Ref reference; |
typedef _Slist_node<_Tp> _Node; |
_Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {} |
_Slist_iterator() : _Slist_iterator_base(0) {} |
_Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {} |
reference operator*() const { return ((_Node*) _M_node)->_M_data; } |
pointer operator->() const { return &(operator*()); } |
_Self& operator++() |
{ |
_M_incr(); |
return *this; |
} |
_Self operator++(int) |
{ |
_Self __tmp = *this; |
_M_incr(); |
return __tmp; |
} |
}; |
// Base class that encapsulates details of allocators. Three cases: |
// an ordinary standard-conforming allocator, a standard-conforming |
// allocator with no non-static data, and an SGI-style allocator. |
// This complexity is necessary only because we're worrying about backward |
// compatibility and because we want to avoid wasting storage on an |
// allocator instance if it isn't necessary. |
// Base for general standard-conforming allocators. |
template <class _Tp, class _Allocator, bool _IsStatic> |
class _Slist_alloc_base { |
public: |
typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return _M_node_allocator; } |
_Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {} |
protected: |
_Slist_node<_Tp>* _M_get_node() |
{ return _M_node_allocator.allocate(1); } |
void _M_put_node(_Slist_node<_Tp>* __p) |
{ _M_node_allocator.deallocate(__p, 1); } |
protected: |
typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type |
_M_node_allocator; |
_Slist_node_base _M_head; |
}; |
// Specialization for instanceless allocators. |
template <class _Tp, class _Allocator> |
class _Slist_alloc_base<_Tp,_Allocator, true> { |
public: |
typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return allocator_type(); } |
_Slist_alloc_base(const allocator_type&) {} |
protected: |
typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type |
_Alloc_type; |
_Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } |
void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } |
protected: |
_Slist_node_base _M_head; |
}; |
template <class _Tp, class _Alloc> |
struct _Slist_base |
: public _Slist_alloc_base<_Tp, _Alloc, |
_Alloc_traits<_Tp, _Alloc>::_S_instanceless> |
{ |
typedef _Slist_alloc_base<_Tp, _Alloc, |
_Alloc_traits<_Tp, _Alloc>::_S_instanceless> |
_Base; |
typedef typename _Base::allocator_type allocator_type; |
_Slist_base(const allocator_type& __a) |
: _Base(__a) { this->_M_head._M_next = 0; } |
~_Slist_base() { _M_erase_after(&this->_M_head, 0); } |
protected: |
_Slist_node_base* _M_erase_after(_Slist_node_base* __pos) |
{ |
_Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); |
_Slist_node_base* __next_next = __next->_M_next; |
__pos->_M_next = __next_next; |
destroy(&__next->_M_data); |
_M_put_node(__next); |
return __next_next; |
} |
_Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); |
}; |
template <class _Tp, class _Alloc> |
_Slist_node_base* |
_Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, |
_Slist_node_base* __last_node) { |
_Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); |
while (__cur != __last_node) { |
_Slist_node<_Tp>* __tmp = __cur; |
__cur = (_Slist_node<_Tp>*) __cur->_M_next; |
destroy(&__tmp->_M_data); |
_M_put_node(__tmp); |
} |
__before_first->_M_next = __last_node; |
return __last_node; |
} |
template <class _Tp, class _Alloc = allocator<_Tp> > |
class slist : private _Slist_base<_Tp,_Alloc> |
{ |
// concept requirements |
__glibcpp_class_requires(_Tp, _SGIAssignableConcept); |
private: |
typedef _Slist_base<_Tp,_Alloc> _Base; |
public: |
typedef _Tp value_type; |
typedef value_type* pointer; |
typedef const value_type* const_pointer; |
typedef value_type& reference; |
typedef const value_type& const_reference; |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; |
typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; |
typedef typename _Base::allocator_type allocator_type; |
allocator_type get_allocator() const { return _Base::get_allocator(); } |
private: |
typedef _Slist_node<_Tp> _Node; |
typedef _Slist_node_base _Node_base; |
typedef _Slist_iterator_base _Iterator_base; |
_Node* _M_create_node(const value_type& __x) { |
_Node* __node = this->_M_get_node(); |
__STL_TRY { |
construct(&__node->_M_data, __x); |
__node->_M_next = 0; |
} |
__STL_UNWIND(this->_M_put_node(__node)); |
return __node; |
} |
_Node* _M_create_node() { |
_Node* __node = this->_M_get_node(); |
__STL_TRY { |
construct(&__node->_M_data); |
__node->_M_next = 0; |
} |
__STL_UNWIND(this->_M_put_node(__node)); |
return __node; |
} |
public: |
explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {} |
slist(size_type __n, const value_type& __x, |
const allocator_type& __a = allocator_type()) : _Base(__a) |
{ _M_insert_after_fill(&this->_M_head, __n, __x); } |
explicit slist(size_type __n) : _Base(allocator_type()) |
{ _M_insert_after_fill(&this->_M_head, __n, value_type()); } |
// We don't need any dispatching tricks here, because _M_insert_after_range |
// already does them. |
template <class _InputIterator> |
slist(_InputIterator __first, _InputIterator __last, |
const allocator_type& __a = allocator_type()) : _Base(__a) |
{ _M_insert_after_range(&this->_M_head, __first, __last); } |
slist(const slist& __x) : _Base(__x.get_allocator()) |
{ _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } |
slist& operator= (const slist& __x); |
~slist() {} |
public: |
// assign(), a generalized assignment member function. Two |
// versions: one that takes a count, and one that takes a range. |
// The range version is a member template, so we dispatch on whether |
// or not the type is an integer. |
void assign(size_type __n, const _Tp& __val) |
{ _M_fill_assign(__n, __val); } |
void _M_fill_assign(size_type __n, const _Tp& __val); |
template <class _InputIterator> |
void assign(_InputIterator __first, _InputIterator __last) { |
typedef typename _Is_integer<_InputIterator>::_Integral _Integral; |
_M_assign_dispatch(__first, __last, _Integral()); |
} |
template <class _Integer> |
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) |
{ _M_fill_assign((size_type) __n, (_Tp) __val); } |
template <class _InputIterator> |
void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, |
__false_type); |
public: |
iterator begin() { return iterator((_Node*)this->_M_head._M_next); } |
const_iterator begin() const |
{ return const_iterator((_Node*)this->_M_head._M_next);} |
iterator end() { return iterator(0); } |
const_iterator end() const { return const_iterator(0); } |
// Experimental new feature: before_begin() returns a |
// non-dereferenceable iterator that, when incremented, yields |
// begin(). This iterator may be used as the argument to |
// insert_after, erase_after, etc. Note that even for an empty |
// slist, before_begin() is not the same iterator as end(). It |
// is always necessary to increment before_begin() at least once to |
// obtain end(). |
iterator before_begin() { return iterator((_Node*) &this->_M_head); } |
const_iterator before_begin() const |
{ return const_iterator((_Node*) &this->_M_head); } |
size_type size() const { return __slist_size(this->_M_head._M_next); } |
size_type max_size() const { return size_type(-1); } |
bool empty() const { return this->_M_head._M_next == 0; } |
void swap(slist& __x) |
{ std::swap(this->_M_head._M_next, __x._M_head._M_next); } |
public: |
reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; } |
const_reference front() const |
{ return ((_Node*) this->_M_head._M_next)->_M_data; } |
void push_front(const value_type& __x) { |
__slist_make_link(&this->_M_head, _M_create_node(__x)); |
} |
void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); } |
void pop_front() { |
_Node* __node = (_Node*) this->_M_head._M_next; |
this->_M_head._M_next = __node->_M_next; |
destroy(&__node->_M_data); |
this->_M_put_node(__node); |
} |
iterator previous(const_iterator __pos) { |
return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node)); |
} |
const_iterator previous(const_iterator __pos) const { |
return const_iterator((_Node*) __slist_previous(&this->_M_head, |
__pos._M_node)); |
} |
private: |
_Node* _M_insert_after(_Node_base* __pos, const value_type& __x) { |
return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); |
} |
_Node* _M_insert_after(_Node_base* __pos) { |
return (_Node*) (__slist_make_link(__pos, _M_create_node())); |
} |
void _M_insert_after_fill(_Node_base* __pos, |
size_type __n, const value_type& __x) { |
for (size_type __i = 0; __i < __n; ++__i) |
__pos = __slist_make_link(__pos, _M_create_node(__x)); |
} |
// Check whether it's an integral type. If so, it's not an iterator. |
template <class _InIter> |
void _M_insert_after_range(_Node_base* __pos, |
_InIter __first, _InIter __last) { |
typedef typename _Is_integer<_InIter>::_Integral _Integral; |
_M_insert_after_range(__pos, __first, __last, _Integral()); |
} |
template <class _Integer> |
void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, |
__true_type) { |
_M_insert_after_fill(__pos, __n, __x); |
} |
template <class _InIter> |
void _M_insert_after_range(_Node_base* __pos, |
_InIter __first, _InIter __last, |
__false_type) { |
while (__first != __last) { |
__pos = __slist_make_link(__pos, _M_create_node(*__first)); |
++__first; |
} |
} |
public: |
iterator insert_after(iterator __pos, const value_type& __x) { |
return iterator(_M_insert_after(__pos._M_node, __x)); |
} |
iterator insert_after(iterator __pos) { |
return insert_after(__pos, value_type()); |
} |
void insert_after(iterator __pos, size_type __n, const value_type& __x) { |
_M_insert_after_fill(__pos._M_node, __n, __x); |
} |
// We don't need any dispatching tricks here, because _M_insert_after_range |
// already does them. |
template <class _InIter> |
void insert_after(iterator __pos, _InIter __first, _InIter __last) { |
_M_insert_after_range(__pos._M_node, __first, __last); |
} |
iterator insert(iterator __pos, const value_type& __x) { |
return iterator(_M_insert_after(__slist_previous(&this->_M_head, |
__pos._M_node), |
__x)); |
} |
iterator insert(iterator __pos) { |
return iterator(_M_insert_after(__slist_previous(&this->_M_head, |
__pos._M_node), |
value_type())); |
} |
void insert(iterator __pos, size_type __n, const value_type& __x) { |
_M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), |
__n, __x); |
} |
// We don't need any dispatching tricks here, because _M_insert_after_range |
// already does them. |
template <class _InIter> |
void insert(iterator __pos, _InIter __first, _InIter __last) { |
_M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), |
__first, __last); |
} |
public: |
iterator erase_after(iterator __pos) { |
return iterator((_Node*) this->_M_erase_after(__pos._M_node)); |
} |
iterator erase_after(iterator __before_first, iterator __last) { |
return iterator((_Node*) this->_M_erase_after(__before_first._M_node, |
__last._M_node)); |
} |
iterator erase(iterator __pos) { |
return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, |
__pos._M_node)); |
} |
iterator erase(iterator __first, iterator __last) { |
return (_Node*) this->_M_erase_after( |
__slist_previous(&this->_M_head, __first._M_node), __last._M_node); |
} |
void resize(size_type new_size, const _Tp& __x); |
void resize(size_type new_size) { resize(new_size, _Tp()); } |
void clear() { this->_M_erase_after(&this->_M_head, 0); } |
public: |
// Moves the range [__before_first + 1, __before_last + 1) to *this, |
// inserting it immediately after __pos. This is constant time. |
void splice_after(iterator __pos, |
iterator __before_first, iterator __before_last) |
{ |
if (__before_first != __before_last) |
__slist_splice_after(__pos._M_node, __before_first._M_node, |
__before_last._M_node); |
} |
// Moves the element that follows __prev to *this, inserting it immediately |
// after __pos. This is constant time. |
void splice_after(iterator __pos, iterator __prev) |
{ |
__slist_splice_after(__pos._M_node, |
__prev._M_node, __prev._M_node->_M_next); |
} |
// Removes all of the elements from the list __x to *this, inserting |
// them immediately after __pos. __x must not be *this. Complexity: |
// linear in __x.size(). |
void splice_after(iterator __pos, slist& __x) |
{ |
__slist_splice_after(__pos._M_node, &__x._M_head); |
} |
// Linear in distance(begin(), __pos), and linear in __x.size(). |
void splice(iterator __pos, slist& __x) { |
if (__x._M_head._M_next) |
__slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), |
&__x._M_head, __slist_previous(&__x._M_head, 0)); |
} |
// Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). |
void splice(iterator __pos, slist& __x, iterator __i) { |
__slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), |
__slist_previous(&__x._M_head, __i._M_node), |
__i._M_node); |
} |
// Linear in distance(begin(), __pos), in distance(__x.begin(), __first), |
// and in distance(__first, __last). |
void splice(iterator __pos, slist& __x, iterator __first, iterator __last) |
{ |
if (__first != __last) |
__slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), |
__slist_previous(&__x._M_head, __first._M_node), |
__slist_previous(__first._M_node, __last._M_node)); |
} |
public: |
void reverse() { |
if (this->_M_head._M_next) |
this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); |
} |
void remove(const _Tp& __val); |
void unique(); |
void merge(slist& __x); |
void sort(); |
template <class _Predicate> |
void remove_if(_Predicate __pred); |
template <class _BinaryPredicate> |
void unique(_BinaryPredicate __pred); |
template <class _StrictWeakOrdering> |
void merge(slist&, _StrictWeakOrdering); |
template <class _StrictWeakOrdering> |
void sort(_StrictWeakOrdering __comp); |
}; |
template <class _Tp, class _Alloc> |
slist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) |
{ |
if (&__x != this) { |
_Node_base* __p1 = &this->_M_head; |
_Node* __n1 = (_Node*) this->_M_head._M_next; |
const _Node* __n2 = (const _Node*) __x._M_head._M_next; |
while (__n1 && __n2) { |
__n1->_M_data = __n2->_M_data; |
__p1 = __n1; |
__n1 = (_Node*) __n1->_M_next; |
__n2 = (const _Node*) __n2->_M_next; |
} |
if (__n2 == 0) |
this->_M_erase_after(__p1, 0); |
else |
_M_insert_after_range(__p1, const_iterator((_Node*)__n2), |
const_iterator(0)); |
} |
return *this; |
} |
template <class _Tp, class _Alloc> |
void slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { |
_Node_base* __prev = &this->_M_head; |
_Node* __node = (_Node*) this->_M_head._M_next; |
for ( ; __node != 0 && __n > 0 ; --__n) { |
__node->_M_data = __val; |
__prev = __node; |
__node = (_Node*) __node->_M_next; |
} |
if (__n > 0) |
_M_insert_after_fill(__prev, __n, __val); |
else |
this->_M_erase_after(__prev, 0); |
} |
template <class _Tp, class _Alloc> template <class _InputIter> |
void |
slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, |
__false_type) |
{ |
_Node_base* __prev = &this->_M_head; |
_Node* __node = (_Node*) this->_M_head._M_next; |
while (__node != 0 && __first != __last) { |
__node->_M_data = *__first; |
__prev = __node; |
__node = (_Node*) __node->_M_next; |
++__first; |
} |
if (__first != __last) |
_M_insert_after_range(__prev, __first, __last); |
else |
this->_M_erase_after(__prev, 0); |
} |
template <class _Tp, class _Alloc> |
inline bool |
operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) |
{ |
typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; |
const_iterator __end1 = _SL1.end(); |
const_iterator __end2 = _SL2.end(); |
const_iterator __i1 = _SL1.begin(); |
const_iterator __i2 = _SL2.begin(); |
while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { |
++__i1; |
++__i2; |
} |
return __i1 == __end1 && __i2 == __end2; |
} |
template <class _Tp, class _Alloc> |
inline bool |
operator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) |
{ |
return lexicographical_compare(_SL1.begin(), _SL1.end(), |
_SL2.begin(), _SL2.end()); |
} |
template <class _Tp, class _Alloc> |
inline bool |
operator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { |
return !(_SL1 == _SL2); |
} |
template <class _Tp, class _Alloc> |
inline bool |
operator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { |
return _SL2 < _SL1; |
} |
template <class _Tp, class _Alloc> |
inline bool |
operator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { |
return !(_SL2 < _SL1); |
} |
template <class _Tp, class _Alloc> |
inline bool |
operator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { |
return !(_SL1 < _SL2); |
} |
template <class _Tp, class _Alloc> |
inline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) { |
__x.swap(__y); |
} |
template <class _Tp, class _Alloc> |
void slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) |
{ |
_Node_base* __cur = &this->_M_head; |
while (__cur->_M_next != 0 && __len > 0) { |
--__len; |
__cur = __cur->_M_next; |
} |
if (__cur->_M_next) |
this->_M_erase_after(__cur, 0); |
else |
_M_insert_after_fill(__cur, __len, __x); |
} |
template <class _Tp, class _Alloc> |
void slist<_Tp,_Alloc>::remove(const _Tp& __val) |
{ |
_Node_base* __cur = &this->_M_head; |
while (__cur && __cur->_M_next) { |
if (((_Node*) __cur->_M_next)->_M_data == __val) |
this->_M_erase_after(__cur); |
else |
__cur = __cur->_M_next; |
} |
} |
template <class _Tp, class _Alloc> |
void slist<_Tp,_Alloc>::unique() |
{ |
_Node_base* __cur = this->_M_head._M_next; |
if (__cur) { |
while (__cur->_M_next) { |
if (((_Node*)__cur)->_M_data == |
((_Node*)(__cur->_M_next))->_M_data) |
this->_M_erase_after(__cur); |
else |
__cur = __cur->_M_next; |
} |
} |
} |
template <class _Tp, class _Alloc> |
void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) |
{ |
_Node_base* __n1 = &this->_M_head; |
while (__n1->_M_next && __x._M_head._M_next) { |
if (((_Node*) __x._M_head._M_next)->_M_data < |
((_Node*) __n1->_M_next)->_M_data) |
__slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); |
__n1 = __n1->_M_next; |
} |
if (__x._M_head._M_next) { |
__n1->_M_next = __x._M_head._M_next; |
__x._M_head._M_next = 0; |
} |
} |
template <class _Tp, class _Alloc> |
void slist<_Tp,_Alloc>::sort() |
{ |
if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { |
slist __carry; |
slist __counter[64]; |
int __fill = 0; |
while (!empty()) { |
__slist_splice_after(&__carry._M_head, |
&this->_M_head, this->_M_head._M_next); |
int __i = 0; |
while (__i < __fill && !__counter[__i].empty()) { |
__counter[__i].merge(__carry); |
__carry.swap(__counter[__i]); |
++__i; |
} |
__carry.swap(__counter[__i]); |
if (__i == __fill) |
++__fill; |
} |
for (int __i = 1; __i < __fill; ++__i) |
__counter[__i].merge(__counter[__i-1]); |
this->swap(__counter[__fill-1]); |
} |
} |
template <class _Tp, class _Alloc> |
template <class _Predicate> |
void slist<_Tp,_Alloc>::remove_if(_Predicate __pred) |
{ |
_Node_base* __cur = &this->_M_head; |
while (__cur->_M_next) { |
if (__pred(((_Node*) __cur->_M_next)->_M_data)) |
this->_M_erase_after(__cur); |
else |
__cur = __cur->_M_next; |
} |
} |
template <class _Tp, class _Alloc> template <class _BinaryPredicate> |
void slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred) |
{ |
_Node* __cur = (_Node*) this->_M_head._M_next; |
if (__cur) { |
while (__cur->_M_next) { |
if (__pred(((_Node*)__cur)->_M_data, |
((_Node*)(__cur->_M_next))->_M_data)) |
this->_M_erase_after(__cur); |
else |
__cur = (_Node*) __cur->_M_next; |
} |
} |
} |
template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> |
void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x, |
_StrictWeakOrdering __comp) |
{ |
_Node_base* __n1 = &this->_M_head; |
while (__n1->_M_next && __x._M_head._M_next) { |
if (__comp(((_Node*) __x._M_head._M_next)->_M_data, |
((_Node*) __n1->_M_next)->_M_data)) |
__slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); |
__n1 = __n1->_M_next; |
} |
if (__x._M_head._M_next) { |
__n1->_M_next = __x._M_head._M_next; |
__x._M_head._M_next = 0; |
} |
} |
template <class _Tp, class _Alloc> template <class _StrictWeakOrdering> |
void slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp) |
{ |
if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { |
slist __carry; |
slist __counter[64]; |
int __fill = 0; |
while (!empty()) { |
__slist_splice_after(&__carry._M_head, |
&this->_M_head, this->_M_head._M_next); |
int __i = 0; |
while (__i < __fill && !__counter[__i].empty()) { |
__counter[__i].merge(__carry, __comp); |
__carry.swap(__counter[__i]); |
++__i; |
} |
__carry.swap(__counter[__i]); |
if (__i == __fill) |
++__fill; |
} |
for (int __i = 1; __i < __fill; ++__i) |
__counter[__i].merge(__counter[__i-1], __comp); |
this->swap(__counter[__fill-1]); |
} |
} |
// Specialization of insert_iterator so that insertions will be constant |
// time rather than linear time. |
template <class _Tp, class _Alloc> |
class insert_iterator<slist<_Tp, _Alloc> > { |
protected: |
typedef slist<_Tp, _Alloc> _Container; |
_Container* container; |
typename _Container::iterator iter; |
public: |
typedef _Container container_type; |
typedef output_iterator_tag iterator_category; |
typedef void value_type; |
typedef void difference_type; |
typedef void pointer; |
typedef void reference; |
insert_iterator(_Container& __x, typename _Container::iterator __i) |
: container(&__x) { |
if (__i == __x.begin()) |
iter = __x.before_begin(); |
else |
iter = __x.previous(__i); |
} |
insert_iterator<_Container>& |
operator=(const typename _Container::value_type& __value) { |
iter = container->insert_after(iter, __value); |
return *this; |
} |
insert_iterator<_Container>& operator*() { return *this; } |
insert_iterator<_Container>& operator++() { return *this; } |
insert_iterator<_Container>& operator++(int) { return *this; } |
}; |
} // namespace std |
#endif /* __SGI_STL_INTERNAL_SLIST_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/stl_bvector.h |
---|
0,0 → 1,896 |
/* |
* |
* Copyright (c) 1994 |
* Hewlett-Packard Company |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Hewlett-Packard Company makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
* |
* Copyright (c) 1996-1999 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#ifndef __SGI_STL_INTERNAL_BVECTOR_H |
#define __SGI_STL_INTERNAL_BVECTOR_H |
__STL_BEGIN_NAMESPACE |
static const int __WORD_BIT = int(CHAR_BIT*sizeof(unsigned int)); |
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) |
#pragma set woff 1174 |
#pragma set woff 1375 |
#endif |
struct _Bit_reference { |
unsigned int* _M_p; |
unsigned int _M_mask; |
_Bit_reference(unsigned int* __x, unsigned int __y) |
: _M_p(__x), _M_mask(__y) {} |
public: |
_Bit_reference() : _M_p(0), _M_mask(0) {} |
operator bool() const { return !(!(*_M_p & _M_mask)); } |
_Bit_reference& operator=(bool __x) |
{ |
if (__x) *_M_p |= _M_mask; |
else *_M_p &= ~_M_mask; |
return *this; |
} |
_Bit_reference& operator=(const _Bit_reference& __x) |
{ return *this = bool(__x); } |
bool operator==(const _Bit_reference& __x) const |
{ return bool(*this) == bool(__x); } |
bool operator<(const _Bit_reference& __x) const { |
return !bool(*this) && bool(__x); |
} |
void flip() { *_M_p ^= _M_mask; } |
}; |
inline void swap(_Bit_reference __x, _Bit_reference __y) |
{ |
bool __tmp = __x; |
__x = __y; |
__y = __tmp; |
} |
struct _Bit_iterator_base : public random_access_iterator<bool, ptrdiff_t> |
{ |
unsigned int* _M_p; |
unsigned int _M_offset; |
_Bit_iterator_base(unsigned int* __x, unsigned int __y) |
: _M_p(__x), _M_offset(__y) {} |
void _M_bump_up() { |
if (_M_offset++ == __WORD_BIT - 1) { |
_M_offset = 0; |
++_M_p; |
} |
} |
void _M_bump_down() { |
if (_M_offset-- == 0) { |
_M_offset = __WORD_BIT - 1; |
--_M_p; |
} |
} |
void _M_incr(ptrdiff_t __i) { |
difference_type __n = __i + _M_offset; |
_M_p += __n / __WORD_BIT; |
__n = __n % __WORD_BIT; |
if (__n < 0) { |
_M_offset = (unsigned int) __n + __WORD_BIT; |
--_M_p; |
} else |
_M_offset = (unsigned int) __n; |
} |
bool operator==(const _Bit_iterator_base& __i) const { |
return _M_p == __i._M_p && _M_offset == __i._M_offset; |
} |
bool operator<(const _Bit_iterator_base& __i) const { |
return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset); |
} |
bool operator!=(const _Bit_iterator_base& __i) const { |
return !(*this == __i); |
} |
bool operator>(const _Bit_iterator_base& __i) const { |
return __i < *this; |
} |
bool operator<=(const _Bit_iterator_base& __i) const { |
return !(__i < *this); |
} |
bool operator>=(const _Bit_iterator_base& __i) const { |
return !(*this < __i); |
} |
}; |
inline ptrdiff_t |
operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) { |
return __WORD_BIT * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset; |
} |
struct _Bit_iterator : public _Bit_iterator_base |
{ |
typedef _Bit_reference reference; |
typedef _Bit_reference* pointer; |
typedef _Bit_iterator iterator; |
_Bit_iterator() : _Bit_iterator_base(0, 0) {} |
_Bit_iterator(unsigned int* __x, unsigned int __y) |
: _Bit_iterator_base(__x, __y) {} |
reference operator*() const { return reference(_M_p, 1U << _M_offset); } |
iterator& operator++() { |
_M_bump_up(); |
return *this; |
} |
iterator operator++(int) { |
iterator __tmp = *this; |
_M_bump_up(); |
return __tmp; |
} |
iterator& operator--() { |
_M_bump_down(); |
return *this; |
} |
iterator operator--(int) { |
iterator __tmp = *this; |
_M_bump_down(); |
return __tmp; |
} |
iterator& operator+=(difference_type __i) { |
_M_incr(__i); |
return *this; |
} |
iterator& operator-=(difference_type __i) { |
*this += -__i; |
return *this; |
} |
iterator operator+(difference_type __i) const { |
iterator __tmp = *this; |
return __tmp += __i; |
} |
iterator operator-(difference_type __i) const { |
iterator __tmp = *this; |
return __tmp -= __i; |
} |
reference operator[](difference_type __i) { return *(*this + __i); } |
}; |
inline _Bit_iterator |
operator+(ptrdiff_t __n, const _Bit_iterator& __x) { return __x + __n; } |
struct _Bit_const_iterator : public _Bit_iterator_base |
{ |
typedef bool reference; |
typedef bool const_reference; |
typedef const bool* pointer; |
typedef _Bit_const_iterator const_iterator; |
_Bit_const_iterator() : _Bit_iterator_base(0, 0) {} |
_Bit_const_iterator(unsigned int* __x, unsigned int __y) |
: _Bit_iterator_base(__x, __y) {} |
_Bit_const_iterator(const _Bit_iterator& __x) |
: _Bit_iterator_base(__x._M_p, __x._M_offset) {} |
const_reference operator*() const { |
return _Bit_reference(_M_p, 1U << _M_offset); |
} |
const_iterator& operator++() { |
_M_bump_up(); |
return *this; |
} |
const_iterator operator++(int) { |
const_iterator __tmp = *this; |
_M_bump_up(); |
return __tmp; |
} |
const_iterator& operator--() { |
_M_bump_down(); |
return *this; |
} |
const_iterator operator--(int) { |
const_iterator __tmp = *this; |
_M_bump_down(); |
return __tmp; |
} |
const_iterator& operator+=(difference_type __i) { |
_M_incr(__i); |
return *this; |
} |
const_iterator& operator-=(difference_type __i) { |
*this += -__i; |
return *this; |
} |
const_iterator operator+(difference_type __i) const { |
const_iterator __tmp = *this; |
return __tmp += __i; |
} |
const_iterator operator-(difference_type __i) const { |
const_iterator __tmp = *this; |
return __tmp -= __i; |
} |
const_reference operator[](difference_type __i) { |
return *(*this + __i); |
} |
}; |
inline _Bit_const_iterator |
operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) { return __x + __n; } |
// Bit-vector base class, which encapsulates the difference between |
// old SGI-style allocators and standard-conforming allocators. |
#ifdef __STL_USE_STD_ALLOCATORS |
// Base class for ordinary allocators. |
template <class _Allocator, bool __is_static> |
class _Bvector_alloc_base { |
public: |
typedef typename _Alloc_traits<bool, _Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return _M_data_allocator; } |
_Bvector_alloc_base(const allocator_type& __a) |
: _M_data_allocator(__a), _M_start(), _M_finish(), _M_end_of_storage(0) {} |
protected: |
unsigned int* _M_bit_alloc(size_t __n) |
{ return _M_data_allocator.allocate((__n + __WORD_BIT - 1)/__WORD_BIT); } |
void _M_deallocate() { |
if (_M_start._M_p) |
_M_data_allocator.deallocate(_M_start._M_p, |
_M_end_of_storage - _M_start._M_p); |
} |
typename _Alloc_traits<unsigned int, _Allocator>::allocator_type |
_M_data_allocator; |
_Bit_iterator _M_start; |
_Bit_iterator _M_finish; |
unsigned int* _M_end_of_storage; |
}; |
// Specialization for instanceless allocators. |
template <class _Allocator> |
class _Bvector_alloc_base<_Allocator, true> { |
public: |
typedef typename _Alloc_traits<bool, _Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return allocator_type(); } |
_Bvector_alloc_base(const allocator_type&) |
: _M_start(), _M_finish(), _M_end_of_storage(0) {} |
protected: |
typedef typename _Alloc_traits<unsigned int, _Allocator>::_Alloc_type |
_Alloc_type; |
unsigned int* _M_bit_alloc(size_t __n) |
{ return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); } |
void _M_deallocate() { |
if (_M_start._M_p) |
_Alloc_type::deallocate(_M_start._M_p, |
_M_end_of_storage - _M_start._M_p); |
} |
_Bit_iterator _M_start; |
_Bit_iterator _M_finish; |
unsigned int* _M_end_of_storage; |
}; |
template <class _Alloc> |
class _Bvector_base |
: public _Bvector_alloc_base<_Alloc, |
_Alloc_traits<bool, _Alloc>::_S_instanceless> |
{ |
typedef _Bvector_alloc_base<_Alloc, |
_Alloc_traits<bool, _Alloc>::_S_instanceless> |
_Base; |
public: |
typedef typename _Base::allocator_type allocator_type; |
_Bvector_base(const allocator_type& __a) : _Base(__a) {} |
~_Bvector_base() { _Base::_M_deallocate(); } |
}; |
#else /* __STL_USE_STD_ALLOCATORS */ |
template <class _Alloc> |
class _Bvector_base |
{ |
public: |
typedef _Alloc allocator_type; |
allocator_type get_allocator() const { return allocator_type(); } |
_Bvector_base(const allocator_type&) |
: _M_start(), _M_finish(), _M_end_of_storage(0) {} |
~_Bvector_base() { _M_deallocate(); } |
protected: |
typedef simple_alloc<unsigned int, _Alloc> _Alloc_type; |
unsigned int* _M_bit_alloc(size_t __n) |
{ return _Alloc_type::allocate((__n + __WORD_BIT - 1)/__WORD_BIT); } |
void _M_deallocate() { |
if (_M_start._M_p) |
_Alloc_type::deallocate(_M_start._M_p, |
_M_end_of_storage - _M_start._M_p); |
} |
_Bit_iterator _M_start; |
_Bit_iterator _M_finish; |
unsigned int* _M_end_of_storage; |
}; |
#endif /* __STL_USE_STD_ALLOCATORS */ |
// The next few lines are confusing. What we're doing is declaring a |
// partial specialization of vector<T, Alloc> if we have the necessary |
// compiler support. Otherwise, we define a class bit_vector which uses |
// the default allocator. |
#if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NO_BOOL) |
# define __SGI_STL_VECBOOL_TEMPLATE |
# define __BVECTOR vector<bool, _Alloc> |
# define __VECTOR vector |
# define __BVECTOR_BASE _Bvector_base<_Alloc> |
# define __BVECTOR_TMPL_LIST template <class _Alloc> |
__STL_END_NAMESPACE |
# include <bits/stl_vector.h> |
__STL_BEGIN_NAMESPACE |
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */ |
# undef __SGI_STL_VECBOOL_TEMPLATE |
# define __BVECTOR bit_vector |
# define __VECTOR bit_vector |
# define __BVECTOR_BASE _Bvector_base<__STL_DEFAULT_ALLOCATOR(bool) > |
# define __BVECTOR_TMPL_LIST |
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION && !__STL_NO_BOOL */ |
__BVECTOR_TMPL_LIST |
class __BVECTOR : public __BVECTOR_BASE |
{ |
public: |
typedef bool value_type; |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
typedef _Bit_reference reference; |
typedef bool const_reference; |
typedef _Bit_reference* pointer; |
typedef const bool* const_pointer; |
typedef _Bit_iterator iterator; |
typedef _Bit_const_iterator const_iterator; |
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION |
typedef reverse_iterator<const_iterator> const_reverse_iterator; |
typedef reverse_iterator<iterator> reverse_iterator; |
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
typedef reverse_iterator<const_iterator, value_type, const_reference, |
difference_type> const_reverse_iterator; |
typedef reverse_iterator<iterator, value_type, reference, difference_type> |
reverse_iterator; |
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
typedef typename __BVECTOR_BASE::allocator_type allocator_type; |
allocator_type get_allocator() const { |
return __BVECTOR_BASE::get_allocator(); |
} |
protected: |
#ifdef __STL_USE_NAMESPACES |
using __BVECTOR_BASE::_M_bit_alloc; |
using __BVECTOR_BASE::_M_deallocate; |
using __BVECTOR_BASE::_M_start; |
using __BVECTOR_BASE::_M_finish; |
using __BVECTOR_BASE::_M_end_of_storage; |
#endif /* __STL_USE_NAMESPACES */ |
protected: |
void _M_initialize(size_type __n) { |
unsigned int* __q = _M_bit_alloc(__n); |
_M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT; |
_M_start = iterator(__q, 0); |
_M_finish = _M_start + difference_type(__n); |
} |
void _M_insert_aux(iterator __position, bool __x) { |
if (_M_finish._M_p != _M_end_of_storage) { |
copy_backward(__position, _M_finish, _M_finish + 1); |
*__position = __x; |
++_M_finish; |
} |
else { |
size_type __len = size() ? 2 * size() : __WORD_BIT; |
unsigned int* __q = _M_bit_alloc(__len); |
iterator __i = copy(begin(), __position, iterator(__q, 0)); |
*__i++ = __x; |
_M_finish = copy(__position, end(), __i); |
_M_deallocate(); |
_M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; |
_M_start = iterator(__q, 0); |
} |
} |
#ifdef __STL_MEMBER_TEMPLATES |
template <class _InputIterator> |
void _M_initialize_range(_InputIterator __first, _InputIterator __last, |
input_iterator_tag) { |
_M_start = iterator(); |
_M_finish = iterator(); |
_M_end_of_storage = 0; |
for ( ; __first != __last; ++__first) |
push_back(*__first); |
} |
template <class _ForwardIterator> |
void _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, |
forward_iterator_tag) { |
size_type __n = 0; |
distance(__first, __last, __n); |
_M_initialize(__n); |
copy(__first, __last, _M_start); |
} |
template <class _InputIterator> |
void _M_insert_range(iterator __pos, |
_InputIterator __first, _InputIterator __last, |
input_iterator_tag) { |
for ( ; __first != __last; ++__first) { |
__pos = insert(__pos, *__first); |
++__pos; |
} |
} |
template <class _ForwardIterator> |
void _M_insert_range(iterator __position, |
_ForwardIterator __first, _ForwardIterator __last, |
forward_iterator_tag) { |
if (__first != __last) { |
size_type __n = 0; |
distance(__first, __last, __n); |
if (capacity() - size() >= __n) { |
copy_backward(__position, end(), _M_finish + difference_type(__n)); |
copy(__first, __last, __position); |
_M_finish += difference_type(__n); |
} |
else { |
size_type __len = size() + max(size(), __n); |
unsigned int* __q = _M_bit_alloc(__len); |
iterator __i = copy(begin(), __position, iterator(__q, 0)); |
__i = copy(__first, __last, __i); |
_M_finish = copy(__position, end(), __i); |
_M_deallocate(); |
_M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; |
_M_start = iterator(__q, 0); |
} |
} |
} |
#endif /* __STL_MEMBER_TEMPLATES */ |
public: |
iterator begin() { return _M_start; } |
const_iterator begin() const { return _M_start; } |
iterator end() { return _M_finish; } |
const_iterator end() const { return _M_finish; } |
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()); |
} |
size_type size() const { return size_type(end() - begin()); } |
size_type max_size() const { return size_type(-1); } |
size_type capacity() const { |
return size_type(const_iterator(_M_end_of_storage, 0) - begin()); |
} |
bool empty() const { return begin() == end(); } |
reference operator[](size_type __n) |
{ return *(begin() + difference_type(__n)); } |
const_reference operator[](size_type __n) const |
{ return *(begin() + difference_type(__n)); } |
#ifdef __STL_THROW_RANGE_ERRORS |
void _M_range_check(size_type __n) const { |
if (__n >= this->size()) |
__throw_range_error("vector<bool>"); |
} |
reference at(size_type __n) |
{ _M_range_check(__n); return (*this)[__n]; } |
const_reference at(size_type __n) const |
{ _M_range_check(__n); return (*this)[__n]; } |
#endif /* __STL_THROW_RANGE_ERRORS */ |
explicit __VECTOR(const allocator_type& __a = allocator_type()) |
: __BVECTOR_BASE(__a) {} |
__VECTOR(size_type __n, bool __value, |
const allocator_type& __a = allocator_type()) |
: __BVECTOR_BASE(__a) |
{ |
_M_initialize(__n); |
fill(_M_start._M_p, _M_end_of_storage, __value ? ~0 : 0); |
} |
explicit __VECTOR(size_type __n) |
: __BVECTOR_BASE(allocator_type()) |
{ |
_M_initialize(__n); |
fill(_M_start._M_p, _M_end_of_storage, 0); |
} |
__VECTOR(const __VECTOR& __x) : __BVECTOR_BASE(__x.get_allocator()) { |
_M_initialize(__x.size()); |
copy(__x.begin(), __x.end(), _M_start); |
} |
#ifdef __STL_MEMBER_TEMPLATES |
// Check whether it's an integral type. If so, it's not an iterator. |
template <class _Integer> |
void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { |
_M_initialize(__n); |
fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); |
} |
template <class _InputIterator> |
void _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |
__false_type) { |
_M_initialize_range(__first, __last, __ITERATOR_CATEGORY(__first)); |
} |
template <class _InputIterator> |
__VECTOR(_InputIterator __first, _InputIterator __last, |
const allocator_type& __a = allocator_type()) |
: __BVECTOR_BASE(__a) |
{ |
typedef typename _Is_integer<_InputIterator>::_Integral _Integral; |
_M_initialize_dispatch(__first, __last, _Integral()); |
} |
#else /* __STL_MEMBER_TEMPLATES */ |
__VECTOR(const_iterator __first, const_iterator __last, |
const allocator_type& __a = allocator_type()) |
: __BVECTOR_BASE(__a) |
{ |
size_type __n = 0; |
distance(__first, __last, __n); |
_M_initialize(__n); |
copy(__first, __last, _M_start); |
} |
__VECTOR(const bool* __first, const bool* __last, |
const allocator_type& __a = allocator_type()) |
: __BVECTOR_BASE(__a) |
{ |
size_type __n = 0; |
distance(__first, __last, __n); |
_M_initialize(__n); |
copy(__first, __last, _M_start); |
} |
#endif /* __STL_MEMBER_TEMPLATES */ |
~__VECTOR() { } |
__VECTOR& operator=(const __VECTOR& __x) { |
if (&__x == this) return *this; |
if (__x.size() > capacity()) { |
_M_deallocate(); |
_M_initialize(__x.size()); |
} |
copy(__x.begin(), __x.end(), begin()); |
_M_finish = begin() + difference_type(__x.size()); |
return *this; |
} |
// assign(), a generalized assignment member function. Two |
// versions: one that takes a count, and one that takes a range. |
// The range version is a member template, so we dispatch on whether |
// or not the type is an integer. |
void _M_fill_assign(size_t __n, bool __x) { |
if (__n > size()) { |
fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); |
insert(end(), __n - size(), __x); |
} |
else { |
erase(begin() + __n, end()); |
fill(_M_start._M_p, _M_end_of_storage, __x ? ~0 : 0); |
} |
} |
void assign(size_t __n, bool __x) { _M_fill_assign(__n, __x); } |
#ifdef __STL_MEMBER_TEMPLATES |
template <class _InputIterator> |
void assign(_InputIterator __first, _InputIterator __last) { |
typedef typename _Is_integer<_InputIterator>::_Integral _Integral; |
_M_assign_dispatch(__first, __last, _Integral()); |
} |
template <class _Integer> |
void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) |
{ _M_fill_assign((size_t) __n, (bool) __val); } |
template <class _InputIter> |
void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type) |
{ _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); } |
template <class _InputIterator> |
void _M_assign_aux(_InputIterator __first, _InputIterator __last, |
input_iterator_tag) { |
iterator __cur = begin(); |
for ( ; __first != __last && __cur != end(); ++__cur, ++__first) |
*__cur = *__first; |
if (__first == __last) |
erase(__cur, end()); |
else |
insert(end(), __first, __last); |
} |
template <class _ForwardIterator> |
void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
forward_iterator_tag) { |
size_type __len = 0; |
distance(__first, __last, __len); |
if (__len < size()) |
erase(copy(__first, __last, begin()), end()); |
else { |
_ForwardIterator __mid = __first; |
advance(__mid, size()); |
copy(__first, __mid, begin()); |
insert(end(), __mid, __last); |
} |
} |
#endif /* __STL_MEMBER_TEMPLATES */ |
void reserve(size_type __n) { |
if (capacity() < __n) { |
unsigned int* __q = _M_bit_alloc(__n); |
_M_finish = copy(begin(), end(), iterator(__q, 0)); |
_M_deallocate(); |
_M_start = iterator(__q, 0); |
_M_end_of_storage = __q + (__n + __WORD_BIT - 1)/__WORD_BIT; |
} |
} |
reference front() { return *begin(); } |
const_reference front() const { return *begin(); } |
reference back() { return *(end() - 1); } |
const_reference back() const { return *(end() - 1); } |
void push_back(bool __x) { |
if (_M_finish._M_p != _M_end_of_storage) |
*_M_finish++ = __x; |
else |
_M_insert_aux(end(), __x); |
} |
void swap(__BVECTOR& __x) { |
__STD::swap(_M_start, __x._M_start); |
__STD::swap(_M_finish, __x._M_finish); |
__STD::swap(_M_end_of_storage, __x._M_end_of_storage); |
} |
iterator insert(iterator __position, bool __x = bool()) { |
difference_type __n = __position - begin(); |
if (_M_finish._M_p != _M_end_of_storage && __position == end()) |
*_M_finish++ = __x; |
else |
_M_insert_aux(__position, __x); |
return begin() + __n; |
} |
#ifdef __STL_MEMBER_TEMPLATES |
// Check whether it's an integral type. If so, it's not an iterator. |
template <class _Integer> |
void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, |
__true_type) { |
_M_fill_insert(__pos, __n, __x); |
} |
template <class _InputIterator> |
void _M_insert_dispatch(iterator __pos, |
_InputIterator __first, _InputIterator __last, |
__false_type) { |
_M_insert_range(__pos, __first, __last, __ITERATOR_CATEGORY(__first)); |
} |
template <class _InputIterator> |
void insert(iterator __position, |
_InputIterator __first, _InputIterator __last) { |
typedef typename _Is_integer<_InputIterator>::_Integral _Integral; |
_M_insert_dispatch(__position, __first, __last, _Integral()); |
} |
#else /* __STL_MEMBER_TEMPLATES */ |
void insert(iterator __position, |
const_iterator __first, const_iterator __last) { |
if (__first == __last) return; |
size_type __n = 0; |
distance(__first, __last, __n); |
if (capacity() - size() >= __n) { |
copy_backward(__position, end(), _M_finish + __n); |
copy(__first, __last, __position); |
_M_finish += __n; |
} |
else { |
size_type __len = size() + max(size(), __n); |
unsigned int* __q = _M_bit_alloc(__len); |
iterator __i = copy(begin(), __position, iterator(__q, 0)); |
__i = copy(__first, __last, __i); |
_M_finish = copy(__position, end(), __i); |
_M_deallocate(); |
_M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; |
_M_start = iterator(__q, 0); |
} |
} |
void insert(iterator __position, const bool* __first, const bool* __last) { |
if (__first == __last) return; |
size_type __n = 0; |
distance(__first, __last, __n); |
if (capacity() - size() >= __n) { |
copy_backward(__position, end(), _M_finish + __n); |
copy(__first, __last, __position); |
_M_finish += __n; |
} |
else { |
size_type __len = size() + max(size(), __n); |
unsigned int* __q = _M_bit_alloc(__len); |
iterator __i = copy(begin(), __position, iterator(__q, 0)); |
__i = copy(__first, __last, __i); |
_M_finish = copy(__position, end(), __i); |
_M_deallocate(); |
_M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; |
_M_start = iterator(__q, 0); |
} |
} |
#endif /* __STL_MEMBER_TEMPLATES */ |
void _M_fill_insert(iterator __position, size_type __n, bool __x) { |
if (__n == 0) return; |
if (capacity() - size() >= __n) { |
copy_backward(__position, end(), _M_finish + difference_type(__n)); |
fill(__position, __position + difference_type(__n), __x); |
_M_finish += difference_type(__n); |
} |
else { |
size_type __len = size() + max(size(), __n); |
unsigned int* __q = _M_bit_alloc(__len); |
iterator __i = copy(begin(), __position, iterator(__q, 0)); |
fill_n(__i, __n, __x); |
_M_finish = copy(__position, end(), __i + difference_type(__n)); |
_M_deallocate(); |
_M_end_of_storage = __q + (__len + __WORD_BIT - 1)/__WORD_BIT; |
_M_start = iterator(__q, 0); |
} |
} |
void insert(iterator __position, size_type __n, bool __x) { |
_M_fill_insert(__position, __n, __x); |
} |
void pop_back() { --_M_finish; } |
iterator erase(iterator __position) { |
if (__position + 1 != end()) |
copy(__position + 1, end(), __position); |
--_M_finish; |
return __position; |
} |
iterator erase(iterator __first, iterator __last) { |
_M_finish = copy(__last, end(), __first); |
return __first; |
} |
void resize(size_type __new_size, bool __x = bool()) { |
if (__new_size < size()) |
erase(begin() + difference_type(__new_size), end()); |
else |
insert(end(), __new_size - size(), __x); |
} |
void flip() { |
for (unsigned int* __p = _M_start._M_p; __p != _M_end_of_storage; ++__p) |
*__p = ~*__p; |
} |
void clear() { erase(begin(), end()); } |
}; |
#ifdef __SGI_STL_VECBOOL_TEMPLATE |
// This typedef is non-standard. It is provided for backward compatibility. |
typedef vector<bool, alloc> bit_vector; |
#else /* __SGI_STL_VECBOOL_TEMPLATE */ |
inline void swap(bit_vector& __x, bit_vector& __y) { |
__x.swap(__y); |
} |
inline bool |
operator==(const bit_vector& __x, const bit_vector& __y) |
{ |
return (__x.size() == __y.size() && |
equal(__x.begin(), __x.end(), __y.begin())); |
} |
inline bool |
operator!=(const bit_vector& __x, const bit_vector& __y) |
{ |
return !(__x == __y); |
} |
inline bool |
operator<(const bit_vector& __x, const bit_vector& __y) |
{ |
return lexicographical_compare(__x.begin(), __x.end(), |
__y.begin(), __y.end()); |
} |
inline bool operator>(const bit_vector& __x, const bit_vector& __y) |
{ |
return __y < __x; |
} |
inline bool operator<=(const bit_vector& __x, const bit_vector& __y) |
{ |
return !(__y < __x); |
} |
inline bool operator>=(const bit_vector& __x, const bit_vector& __y) |
{ |
return !(__x < __y); |
} |
#endif /* __SGI_STL_VECBOOL_TEMPLATE */ |
#undef __SGI_STL_VECBOOL_TEMPLATE |
#undef __BVECTOR |
#undef __VECTOR |
#undef __BVECTOR_BASE |
#undef __BVECTOR_TMPL_LIST |
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) |
#pragma reset woff 1174 |
#pragma reset woff 1375 |
#endif |
__STL_END_NAMESPACE |
#endif /* __SGI_STL_INTERNAL_BVECTOR_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/stl_hash_fun.h |
---|
0,0 → 1,94 |
/* |
* Copyright (c) 1996-1998 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
* |
* Copyright (c) 1994 |
* Hewlett-Packard Company |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Hewlett-Packard Company makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#ifndef _CPP_BITS_STL_HASH_FUN_H |
#define _CPP_BITS_STL_HASH_FUN_H 1 |
#include <bits/std_cstddef.h> |
namespace std |
{ |
template <class _Key> struct hash { }; |
inline size_t __stl_hash_string(const char* __s) |
{ |
unsigned long __h = 0; |
for ( ; *__s; ++__s) |
__h = 5*__h + *__s; |
return size_t(__h); |
} |
template<> struct hash<char*> |
{ |
size_t operator()(const char* __s) const { return __stl_hash_string(__s); } |
}; |
template<> struct hash<const char*> |
{ |
size_t operator()(const char* __s) const { return __stl_hash_string(__s); } |
}; |
template<> struct hash<char> { |
size_t operator()(char __x) const { return __x; } |
}; |
template<> struct hash<unsigned char> { |
size_t operator()(unsigned char __x) const { return __x; } |
}; |
template<> struct hash<signed char> { |
size_t operator()(unsigned char __x) const { return __x; } |
}; |
template<> struct hash<short> { |
size_t operator()(short __x) const { return __x; } |
}; |
template<> struct hash<unsigned short> { |
size_t operator()(unsigned short __x) const { return __x; } |
}; |
template<> struct hash<int> { |
size_t operator()(int __x) const { return __x; } |
}; |
template<> struct hash<unsigned int> { |
size_t operator()(unsigned int __x) const { return __x; } |
}; |
template<> struct hash<long> { |
size_t operator()(long __x) const { return __x; } |
}; |
template<> struct hash<unsigned long> { |
size_t operator()(unsigned long __x) const { return __x; } |
}; |
} // namespace std |
#endif /* _CPP_BITS_STL_HASH_FUN_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/stl_hashtable.h |
---|
0,0 → 1,937 |
/* |
* Copyright (c) 1996,1997 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
* |
* Copyright (c) 1994 |
* Hewlett-Packard Company |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Hewlett-Packard Company makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
#ifndef __SGI_STL_INTERNAL_HASHTABLE_H |
#define __SGI_STL_INTERNAL_HASHTABLE_H |
// Hashtable class, used to implement the hashed associative containers |
// hash_set, hash_map, hash_multiset, and hash_multimap. |
#include <bits/stl_algobase.h> |
#include <bits/stl_alloc.h> |
#include <bits/stl_construct.h> |
#include <bits/stl_tempbuf.h> |
#include <bits/stl_algo.h> |
#include <bits/stl_uninitialized.h> |
#include <bits/stl_function.h> |
#include <bits/stl_vector.h> |
#include <ext/stl_hash_fun.h> |
namespace std |
{ |
template <class _Val> |
struct _Hashtable_node |
{ |
_Hashtable_node* _M_next; |
_Val _M_val; |
}; |
template <class _Val, class _Key, class _HashFcn, |
class _ExtractKey, class _EqualKey, class _Alloc = alloc> |
class hashtable; |
template <class _Val, class _Key, class _HashFcn, |
class _ExtractKey, class _EqualKey, class _Alloc> |
struct _Hashtable_iterator; |
template <class _Val, class _Key, class _HashFcn, |
class _ExtractKey, class _EqualKey, class _Alloc> |
struct _Hashtable_const_iterator; |
template <class _Val, class _Key, class _HashFcn, |
class _ExtractKey, class _EqualKey, class _Alloc> |
struct _Hashtable_iterator { |
typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> |
_Hashtable; |
typedef _Hashtable_iterator<_Val, _Key, _HashFcn, |
_ExtractKey, _EqualKey, _Alloc> |
iterator; |
typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, |
_ExtractKey, _EqualKey, _Alloc> |
const_iterator; |
typedef _Hashtable_node<_Val> _Node; |
typedef forward_iterator_tag iterator_category; |
typedef _Val value_type; |
typedef ptrdiff_t difference_type; |
typedef size_t size_type; |
typedef _Val& reference; |
typedef _Val* pointer; |
_Node* _M_cur; |
_Hashtable* _M_ht; |
_Hashtable_iterator(_Node* __n, _Hashtable* __tab) |
: _M_cur(__n), _M_ht(__tab) {} |
_Hashtable_iterator() {} |
reference operator*() const { return _M_cur->_M_val; } |
pointer operator->() const { return &(operator*()); } |
iterator& operator++(); |
iterator operator++(int); |
bool operator==(const iterator& __it) const |
{ return _M_cur == __it._M_cur; } |
bool operator!=(const iterator& __it) const |
{ return _M_cur != __it._M_cur; } |
}; |
template <class _Val, class _Key, class _HashFcn, |
class _ExtractKey, class _EqualKey, class _Alloc> |
struct _Hashtable_const_iterator { |
typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> |
_Hashtable; |
typedef _Hashtable_iterator<_Val,_Key,_HashFcn, |
_ExtractKey,_EqualKey,_Alloc> |
iterator; |
typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, |
_ExtractKey, _EqualKey, _Alloc> |
const_iterator; |
typedef _Hashtable_node<_Val> _Node; |
typedef forward_iterator_tag iterator_category; |
typedef _Val value_type; |
typedef ptrdiff_t difference_type; |
typedef size_t size_type; |
typedef const _Val& reference; |
typedef const _Val* pointer; |
const _Node* _M_cur; |
const _Hashtable* _M_ht; |
_Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) |
: _M_cur(__n), _M_ht(__tab) {} |
_Hashtable_const_iterator() {} |
_Hashtable_const_iterator(const iterator& __it) |
: _M_cur(__it._M_cur), _M_ht(__it._M_ht) {} |
reference operator*() const { return _M_cur->_M_val; } |
pointer operator->() const { return &(operator*()); } |
const_iterator& operator++(); |
const_iterator operator++(int); |
bool operator==(const const_iterator& __it) const |
{ return _M_cur == __it._M_cur; } |
bool operator!=(const const_iterator& __it) const |
{ return _M_cur != __it._M_cur; } |
}; |
// Note: assumes long is at least 32 bits. |
enum { __stl_num_primes = 28 }; |
static const unsigned long __stl_prime_list[__stl_num_primes] = |
{ |
53ul, 97ul, 193ul, 389ul, 769ul, |
1543ul, 3079ul, 6151ul, 12289ul, 24593ul, |
49157ul, 98317ul, 196613ul, 393241ul, 786433ul, |
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, |
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, |
1610612741ul, 3221225473ul, 4294967291ul |
}; |
inline unsigned long __stl_next_prime(unsigned long __n) |
{ |
const unsigned long* __first = __stl_prime_list; |
const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes; |
const unsigned long* pos = lower_bound(__first, __last, __n); |
return pos == __last ? *(__last - 1) : *pos; |
} |
// Forward declaration of operator==. |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
class hashtable; |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, |
const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2); |
// Hashtables handle allocators a bit differently than other containers |
// do. If we're using standard-conforming allocators, then a hashtable |
// unconditionally has a member variable to hold its allocator, even if |
// it so happens that all instances of the allocator type are identical. |
// This is because, for hashtables, this extra storage is negligible. |
// Additionally, a base class wouldn't serve any other purposes; it |
// wouldn't, for example, simplify the exception-handling code. |
template <class _Val, class _Key, class _HashFcn, |
class _ExtractKey, class _EqualKey, class _Alloc> |
class hashtable { |
public: |
typedef _Key key_type; |
typedef _Val value_type; |
typedef _HashFcn hasher; |
typedef _EqualKey key_equal; |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
typedef value_type* pointer; |
typedef const value_type* const_pointer; |
typedef value_type& reference; |
typedef const value_type& const_reference; |
hasher hash_funct() const { return _M_hash; } |
key_equal key_eq() const { return _M_equals; } |
private: |
typedef _Hashtable_node<_Val> _Node; |
public: |
typedef typename _Alloc_traits<_Val,_Alloc>::allocator_type allocator_type; |
allocator_type get_allocator() const { return _M_node_allocator; } |
private: |
typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator; |
_Node* _M_get_node() { return _M_node_allocator.allocate(1); } |
void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); } |
private: |
hasher _M_hash; |
key_equal _M_equals; |
_ExtractKey _M_get_key; |
vector<_Node*,_Alloc> _M_buckets; |
size_type _M_num_elements; |
public: |
typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> |
iterator; |
typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey, |
_Alloc> |
const_iterator; |
friend struct |
_Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; |
friend struct |
_Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; |
public: |
hashtable(size_type __n, |
const _HashFcn& __hf, |
const _EqualKey& __eql, |
const _ExtractKey& __ext, |
const allocator_type& __a = allocator_type()) |
: _M_node_allocator(__a), |
_M_hash(__hf), |
_M_equals(__eql), |
_M_get_key(__ext), |
_M_buckets(__a), |
_M_num_elements(0) |
{ |
_M_initialize_buckets(__n); |
} |
hashtable(size_type __n, |
const _HashFcn& __hf, |
const _EqualKey& __eql, |
const allocator_type& __a = allocator_type()) |
: _M_node_allocator(__a), |
_M_hash(__hf), |
_M_equals(__eql), |
_M_get_key(_ExtractKey()), |
_M_buckets(__a), |
_M_num_elements(0) |
{ |
_M_initialize_buckets(__n); |
} |
hashtable(const hashtable& __ht) |
: _M_node_allocator(__ht.get_allocator()), |
_M_hash(__ht._M_hash), |
_M_equals(__ht._M_equals), |
_M_get_key(__ht._M_get_key), |
_M_buckets(__ht.get_allocator()), |
_M_num_elements(0) |
{ |
_M_copy_from(__ht); |
} |
hashtable& operator= (const hashtable& __ht) |
{ |
if (&__ht != this) { |
clear(); |
_M_hash = __ht._M_hash; |
_M_equals = __ht._M_equals; |
_M_get_key = __ht._M_get_key; |
_M_copy_from(__ht); |
} |
return *this; |
} |
~hashtable() { clear(); } |
size_type size() const { return _M_num_elements; } |
size_type max_size() const { return size_type(-1); } |
bool empty() const { return size() == 0; } |
void swap(hashtable& __ht) |
{ |
std::swap(_M_hash, __ht._M_hash); |
std::swap(_M_equals, __ht._M_equals); |
std::swap(_M_get_key, __ht._M_get_key); |
_M_buckets.swap(__ht._M_buckets); |
std::swap(_M_num_elements, __ht._M_num_elements); |
} |
iterator begin() |
{ |
for (size_type __n = 0; __n < _M_buckets.size(); ++__n) |
if (_M_buckets[__n]) |
return iterator(_M_buckets[__n], this); |
return end(); |
} |
iterator end() { return iterator(0, this); } |
const_iterator begin() const |
{ |
for (size_type __n = 0; __n < _M_buckets.size(); ++__n) |
if (_M_buckets[__n]) |
return const_iterator(_M_buckets[__n], this); |
return end(); |
} |
const_iterator end() const { return const_iterator(0, this); } |
template <class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al> |
friend bool operator== (const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, |
const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); |
public: |
size_type bucket_count() const { return _M_buckets.size(); } |
size_type max_bucket_count() const |
{ return __stl_prime_list[(int)__stl_num_primes - 1]; } |
size_type elems_in_bucket(size_type __bucket) const |
{ |
size_type __result = 0; |
for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next) |
__result += 1; |
return __result; |
} |
pair<iterator, bool> insert_unique(const value_type& __obj) |
{ |
resize(_M_num_elements + 1); |
return insert_unique_noresize(__obj); |
} |
iterator insert_equal(const value_type& __obj) |
{ |
resize(_M_num_elements + 1); |
return insert_equal_noresize(__obj); |
} |
pair<iterator, bool> insert_unique_noresize(const value_type& __obj); |
iterator insert_equal_noresize(const value_type& __obj); |
template <class _InputIterator> |
void insert_unique(_InputIterator __f, _InputIterator __l) |
{ |
insert_unique(__f, __l, __iterator_category(__f)); |
} |
template <class _InputIterator> |
void insert_equal(_InputIterator __f, _InputIterator __l) |
{ |
insert_equal(__f, __l, __iterator_category(__f)); |
} |
template <class _InputIterator> |
void insert_unique(_InputIterator __f, _InputIterator __l, |
input_iterator_tag) |
{ |
for ( ; __f != __l; ++__f) |
insert_unique(*__f); |
} |
template <class _InputIterator> |
void insert_equal(_InputIterator __f, _InputIterator __l, |
input_iterator_tag) |
{ |
for ( ; __f != __l; ++__f) |
insert_equal(*__f); |
} |
template <class _ForwardIterator> |
void insert_unique(_ForwardIterator __f, _ForwardIterator __l, |
forward_iterator_tag) |
{ |
size_type __n = 0; |
distance(__f, __l, __n); |
resize(_M_num_elements + __n); |
for ( ; __n > 0; --__n, ++__f) |
insert_unique_noresize(*__f); |
} |
template <class _ForwardIterator> |
void insert_equal(_ForwardIterator __f, _ForwardIterator __l, |
forward_iterator_tag) |
{ |
size_type __n = 0; |
distance(__f, __l, __n); |
resize(_M_num_elements + __n); |
for ( ; __n > 0; --__n, ++__f) |
insert_equal_noresize(*__f); |
} |
reference find_or_insert(const value_type& __obj); |
iterator find(const key_type& __key) |
{ |
size_type __n = _M_bkt_num_key(__key); |
_Node* __first; |
for ( __first = _M_buckets[__n]; |
__first && !_M_equals(_M_get_key(__first->_M_val), __key); |
__first = __first->_M_next) |
{} |
return iterator(__first, this); |
} |
const_iterator find(const key_type& __key) const |
{ |
size_type __n = _M_bkt_num_key(__key); |
const _Node* __first; |
for ( __first = _M_buckets[__n]; |
__first && !_M_equals(_M_get_key(__first->_M_val), __key); |
__first = __first->_M_next) |
{} |
return const_iterator(__first, this); |
} |
size_type count(const key_type& __key) const |
{ |
const size_type __n = _M_bkt_num_key(__key); |
size_type __result = 0; |
for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next) |
if (_M_equals(_M_get_key(__cur->_M_val), __key)) |
++__result; |
return __result; |
} |
pair<iterator, iterator> |
equal_range(const key_type& __key); |
pair<const_iterator, const_iterator> |
equal_range(const key_type& __key) const; |
size_type erase(const key_type& __key); |
void erase(const iterator& __it); |
void erase(iterator __first, iterator __last); |
void erase(const const_iterator& __it); |
void erase(const_iterator __first, const_iterator __last); |
void resize(size_type __num_elements_hint); |
void clear(); |
private: |
size_type _M_next_size(size_type __n) const |
{ return __stl_next_prime(__n); } |
void _M_initialize_buckets(size_type __n) |
{ |
const size_type __n_buckets = _M_next_size(__n); |
_M_buckets.reserve(__n_buckets); |
_M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); |
_M_num_elements = 0; |
} |
size_type _M_bkt_num_key(const key_type& __key) const |
{ |
return _M_bkt_num_key(__key, _M_buckets.size()); |
} |
size_type _M_bkt_num(const value_type& __obj) const |
{ |
return _M_bkt_num_key(_M_get_key(__obj)); |
} |
size_type _M_bkt_num_key(const key_type& __key, size_t __n) const |
{ |
return _M_hash(__key) % __n; |
} |
size_type _M_bkt_num(const value_type& __obj, size_t __n) const |
{ |
return _M_bkt_num_key(_M_get_key(__obj), __n); |
} |
_Node* _M_new_node(const value_type& __obj) |
{ |
_Node* __n = _M_get_node(); |
__n->_M_next = 0; |
__STL_TRY { |
construct(&__n->_M_val, __obj); |
return __n; |
} |
__STL_UNWIND(_M_put_node(__n)); |
} |
void _M_delete_node(_Node* __n) |
{ |
destroy(&__n->_M_val); |
_M_put_node(__n); |
} |
void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); |
void _M_erase_bucket(const size_type __n, _Node* __last); |
void _M_copy_from(const hashtable& __ht); |
}; |
template <class _Val, class _Key, class _HF, class _ExK, class _EqK, |
class _All> |
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& |
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() |
{ |
const _Node* __old = _M_cur; |
_M_cur = _M_cur->_M_next; |
if (!_M_cur) { |
size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); |
while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) |
_M_cur = _M_ht->_M_buckets[__bucket]; |
} |
return *this; |
} |
template <class _Val, class _Key, class _HF, class _ExK, class _EqK, |
class _All> |
inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> |
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) |
{ |
iterator __tmp = *this; |
++*this; |
return __tmp; |
} |
template <class _Val, class _Key, class _HF, class _ExK, class _EqK, |
class _All> |
_Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& |
_Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() |
{ |
const _Node* __old = _M_cur; |
_M_cur = _M_cur->_M_next; |
if (!_M_cur) { |
size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); |
while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) |
_M_cur = _M_ht->_M_buckets[__bucket]; |
} |
return *this; |
} |
template <class _Val, class _Key, class _HF, class _ExK, class _EqK, |
class _All> |
inline _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> |
_Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) |
{ |
const_iterator __tmp = *this; |
++*this; |
return __tmp; |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, |
const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) |
{ |
typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node; |
if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) |
return false; |
for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) { |
_Node* __cur1 = __ht1._M_buckets[__n]; |
_Node* __cur2 = __ht2._M_buckets[__n]; |
for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val; |
__cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) |
{} |
if (__cur1 || __cur2) |
return false; |
} |
return true; |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
inline bool operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, |
const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) { |
return !(__ht1 == __ht2); |
} |
template <class _Val, class _Key, class _HF, class _Extract, class _EqKey, |
class _All> |
inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, |
hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) { |
__ht1.swap(__ht2); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool> |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::insert_unique_noresize(const value_type& __obj) |
{ |
const size_type __n = _M_bkt_num(__obj); |
_Node* __first = _M_buckets[__n]; |
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
return pair<iterator, bool>(iterator(__cur, this), false); |
_Node* __tmp = _M_new_node(__obj); |
__tmp->_M_next = __first; |
_M_buckets[__n] = __tmp; |
++_M_num_elements; |
return pair<iterator, bool>(iterator(__tmp, this), true); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::insert_equal_noresize(const value_type& __obj) |
{ |
const size_type __n = _M_bkt_num(__obj); |
_Node* __first = _M_buckets[__n]; |
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) { |
_Node* __tmp = _M_new_node(__obj); |
__tmp->_M_next = __cur->_M_next; |
__cur->_M_next = __tmp; |
++_M_num_elements; |
return iterator(__tmp, this); |
} |
_Node* __tmp = _M_new_node(__obj); |
__tmp->_M_next = __first; |
_M_buckets[__n] = __tmp; |
++_M_num_elements; |
return iterator(__tmp, this); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj) |
{ |
resize(_M_num_elements + 1); |
size_type __n = _M_bkt_num(__obj); |
_Node* __first = _M_buckets[__n]; |
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
return __cur->_M_val; |
_Node* __tmp = _M_new_node(__obj); |
__tmp->_M_next = __first; |
_M_buckets[__n] = __tmp; |
++_M_num_elements; |
return __tmp->_M_val; |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, |
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator> |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key) |
{ |
typedef pair<iterator, iterator> _Pii; |
const size_type __n = _M_bkt_num_key(__key); |
for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next) |
if (_M_equals(_M_get_key(__first->_M_val), __key)) { |
for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next) |
if (!_M_equals(_M_get_key(__cur->_M_val), __key)) |
return _Pii(iterator(__first, this), iterator(__cur, this)); |
for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) |
if (_M_buckets[__m]) |
return _Pii(iterator(__first, this), |
iterator(_M_buckets[__m], this)); |
return _Pii(iterator(__first, this), end()); |
} |
return _Pii(end(), end()); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator, |
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator> |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::equal_range(const key_type& __key) const |
{ |
typedef pair<const_iterator, const_iterator> _Pii; |
const size_type __n = _M_bkt_num_key(__key); |
for (const _Node* __first = _M_buckets[__n] ; |
__first; |
__first = __first->_M_next) { |
if (_M_equals(_M_get_key(__first->_M_val), __key)) { |
for (const _Node* __cur = __first->_M_next; |
__cur; |
__cur = __cur->_M_next) |
if (!_M_equals(_M_get_key(__cur->_M_val), __key)) |
return _Pii(const_iterator(__first, this), |
const_iterator(__cur, this)); |
for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) |
if (_M_buckets[__m]) |
return _Pii(const_iterator(__first, this), |
const_iterator(_M_buckets[__m], this)); |
return _Pii(const_iterator(__first, this), end()); |
} |
} |
return _Pii(end(), end()); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key) |
{ |
const size_type __n = _M_bkt_num_key(__key); |
_Node* __first = _M_buckets[__n]; |
size_type __erased = 0; |
if (__first) { |
_Node* __cur = __first; |
_Node* __next = __cur->_M_next; |
while (__next) { |
if (_M_equals(_M_get_key(__next->_M_val), __key)) { |
__cur->_M_next = __next->_M_next; |
_M_delete_node(__next); |
__next = __cur->_M_next; |
++__erased; |
--_M_num_elements; |
} |
else { |
__cur = __next; |
__next = __cur->_M_next; |
} |
} |
if (_M_equals(_M_get_key(__first->_M_val), __key)) { |
_M_buckets[__n] = __first->_M_next; |
_M_delete_node(__first); |
++__erased; |
--_M_num_elements; |
} |
} |
return __erased; |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it) |
{ |
_Node* __p = __it._M_cur; |
if (__p) { |
const size_type __n = _M_bkt_num(__p->_M_val); |
_Node* __cur = _M_buckets[__n]; |
if (__cur == __p) { |
_M_buckets[__n] = __cur->_M_next; |
_M_delete_node(__cur); |
--_M_num_elements; |
} |
else { |
_Node* __next = __cur->_M_next; |
while (__next) { |
if (__next == __p) { |
__cur->_M_next = __next->_M_next; |
_M_delete_node(__next); |
--_M_num_elements; |
break; |
} |
else { |
__cur = __next; |
__next = __cur->_M_next; |
} |
} |
} |
} |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::erase(iterator __first, iterator __last) |
{ |
size_type __f_bucket = __first._M_cur ? |
_M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size(); |
size_type __l_bucket = __last._M_cur ? |
_M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size(); |
if (__first._M_cur == __last._M_cur) |
return; |
else if (__f_bucket == __l_bucket) |
_M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); |
else { |
_M_erase_bucket(__f_bucket, __first._M_cur, 0); |
for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) |
_M_erase_bucket(__n, 0); |
if (__l_bucket != _M_buckets.size()) |
_M_erase_bucket(__l_bucket, __last._M_cur); |
} |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
inline void |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first, |
const_iterator __last) |
{ |
erase(iterator(const_cast<_Node*>(__first._M_cur), |
const_cast<hashtable*>(__first._M_ht)), |
iterator(const_cast<_Node*>(__last._M_cur), |
const_cast<hashtable*>(__last._M_ht))); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
inline void |
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it) |
{ |
erase(iterator(const_cast<_Node*>(__it._M_cur), |
const_cast<hashtable*>(__it._M_ht))); |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::resize(size_type __num_elements_hint) |
{ |
const size_type __old_n = _M_buckets.size(); |
if (__num_elements_hint > __old_n) { |
const size_type __n = _M_next_size(__num_elements_hint); |
if (__n > __old_n) { |
vector<_Node*, _All> __tmp(__n, (_Node*)(0), |
_M_buckets.get_allocator()); |
__STL_TRY { |
for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) { |
_Node* __first = _M_buckets[__bucket]; |
while (__first) { |
size_type __new_bucket = _M_bkt_num(__first->_M_val, __n); |
_M_buckets[__bucket] = __first->_M_next; |
__first->_M_next = __tmp[__new_bucket]; |
__tmp[__new_bucket] = __first; |
__first = _M_buckets[__bucket]; |
} |
} |
_M_buckets.swap(__tmp); |
} |
# ifdef __STL_USE_EXCEPTIONS |
catch(...) { |
for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) { |
while (__tmp[__bucket]) { |
_Node* __next = __tmp[__bucket]->_M_next; |
_M_delete_node(__tmp[__bucket]); |
__tmp[__bucket] = __next; |
} |
} |
throw; |
} |
# endif /* __STL_USE_EXCEPTIONS */ |
} |
} |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) |
{ |
_Node* __cur = _M_buckets[__n]; |
if (__cur == __first) |
_M_erase_bucket(__n, __last); |
else { |
_Node* __next; |
for (__next = __cur->_M_next; |
__next != __first; |
__cur = __next, __next = __cur->_M_next) |
; |
while (__next != __last) { |
__cur->_M_next = __next->_M_next; |
_M_delete_node(__next); |
__next = __cur->_M_next; |
--_M_num_elements; |
} |
} |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::_M_erase_bucket(const size_type __n, _Node* __last) |
{ |
_Node* __cur = _M_buckets[__n]; |
while (__cur != __last) { |
_Node* __next = __cur->_M_next; |
_M_delete_node(__cur); |
__cur = __next; |
_M_buckets[__n] = __cur; |
--_M_num_elements; |
} |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear() |
{ |
for (size_type __i = 0; __i < _M_buckets.size(); ++__i) { |
_Node* __cur = _M_buckets[__i]; |
while (__cur != 0) { |
_Node* __next = __cur->_M_next; |
_M_delete_node(__cur); |
__cur = __next; |
} |
_M_buckets[__i] = 0; |
} |
_M_num_elements = 0; |
} |
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> |
::_M_copy_from(const hashtable& __ht) |
{ |
_M_buckets.clear(); |
_M_buckets.reserve(__ht._M_buckets.size()); |
_M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); |
__STL_TRY { |
for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { |
const _Node* __cur = __ht._M_buckets[__i]; |
if (__cur) { |
_Node* __local_copy = _M_new_node(__cur->_M_val); |
_M_buckets[__i] = __local_copy; |
for (_Node* __next = __cur->_M_next; |
__next; |
__cur = __next, __next = __cur->_M_next) { |
__local_copy->_M_next = _M_new_node(__next->_M_val); |
__local_copy = __local_copy->_M_next; |
} |
} |
} |
_M_num_elements = __ht._M_num_elements; |
} |
__STL_UNWIND(clear()); |
} |
} // namespace std |
#endif /* __SGI_STL_INTERNAL_HASHTABLE_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/stl_rope.h |
---|
0,0 → 1,2459 |
/* |
* Copyright (c) 1997-1998 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
*/ |
/* NOTE: This is an internal header file, included by other STL headers. |
* You should not attempt to use it directly. |
*/ |
// rope<_CharT,_Alloc> is a sequence of _CharT. |
// Ropes appear to be mutable, but update operations |
// really copy enough of the data structure to leave the original |
// valid. Thus ropes can be logically copied by just copying |
// a pointer value. |
#ifndef __SGI_STL_INTERNAL_ROPE_H |
# define __SGI_STL_INTERNAL_ROPE_H |
# ifdef __GC |
# define __GC_CONST const |
# else |
# include <bits/stl_threads.h> |
# define __GC_CONST // constant except for deallocation |
# endif |
# ifdef __STL_SGI_THREADS |
# include <mutex.h> |
# endif |
namespace std |
{ |
// The _S_eos function is used for those functions that |
// convert to/from C-like strings to detect the end of the string. |
// The end-of-C-string character. |
// This is what the draft standard says it should be. |
template <class _CharT> |
inline _CharT _S_eos(_CharT*) { return _CharT(); } |
// Test for basic character types. |
// For basic character types leaves having a trailing eos. |
template <class _CharT> |
inline bool _S_is_basic_char_type(_CharT*) { return false; } |
template <class _CharT> |
inline bool _S_is_one_byte_char_type(_CharT*) { return false; } |
inline bool _S_is_basic_char_type(char*) { return true; } |
inline bool _S_is_one_byte_char_type(char*) { return true; } |
inline bool _S_is_basic_char_type(wchar_t*) { return true; } |
// Store an eos iff _CharT is a basic character type. |
// Do not reference _S_eos if it isn't. |
template <class _CharT> |
inline void _S_cond_store_eos(_CharT&) {} |
inline void _S_cond_store_eos(char& __c) { __c = 0; } |
inline void _S_cond_store_eos(wchar_t& __c) { __c = 0; } |
// char_producers are logically functions that generate a section of |
// a string. These can be convereted to ropes. The resulting rope |
// invokes the char_producer on demand. This allows, for example, |
// files to be viewed as ropes without reading the entire file. |
template <class _CharT> |
class char_producer { |
public: |
virtual ~char_producer() {}; |
virtual void operator()(size_t __start_pos, size_t __len, |
_CharT* __buffer) = 0; |
// Buffer should really be an arbitrary output iterator. |
// That way we could flatten directly into an ostream, etc. |
// This is thoroughly impossible, since iterator types don't |
// have runtime descriptions. |
}; |
// Sequence buffers: |
// |
// Sequence must provide an append operation that appends an |
// array to the sequence. Sequence buffers are useful only if |
// appending an entire array is cheaper than appending element by element. |
// This is true for many string representations. |
// This should perhaps inherit from ostream<sequence::value_type> |
// and be implemented correspondingly, so that they can be used |
// for formatted. For the sake of portability, we don't do this yet. |
// |
// For now, sequence buffers behave as output iterators. But they also |
// behave a little like basic_ostringstream<sequence::value_type> and a |
// little like containers. |
template<class _Sequence, size_t _Buf_sz = 100> |
class sequence_buffer : public output_iterator { |
public: |
typedef typename _Sequence::value_type value_type; |
protected: |
_Sequence* _M_prefix; |
value_type _M_buffer[_Buf_sz]; |
size_t _M_buf_count; |
public: |
void flush() { |
_M_prefix->append(_M_buffer, _M_buffer + _M_buf_count); |
_M_buf_count = 0; |
} |
~sequence_buffer() { flush(); } |
sequence_buffer() : _M_prefix(0), _M_buf_count(0) {} |
sequence_buffer(const sequence_buffer& __x) { |
_M_prefix = __x._M_prefix; |
_M_buf_count = __x._M_buf_count; |
copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer); |
} |
sequence_buffer(sequence_buffer& __x) { |
__x.flush(); |
_M_prefix = __x._M_prefix; |
_M_buf_count = 0; |
} |
sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {} |
sequence_buffer& operator= (sequence_buffer& __x) { |
__x.flush(); |
_M_prefix = __x._M_prefix; |
_M_buf_count = 0; |
return *this; |
} |
sequence_buffer& operator= (const sequence_buffer& __x) { |
_M_prefix = __x._M_prefix; |
_M_buf_count = __x._M_buf_count; |
copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer); |
return *this; |
} |
void push_back(value_type __x) |
{ |
if (_M_buf_count < _Buf_sz) { |
_M_buffer[_M_buf_count] = __x; |
++_M_buf_count; |
} else { |
flush(); |
_M_buffer[0] = __x; |
_M_buf_count = 1; |
} |
} |
void append(value_type* __s, size_t __len) |
{ |
if (__len + _M_buf_count <= _Buf_sz) { |
size_t __i = _M_buf_count; |
size_t __j = 0; |
for (; __j < __len; __i++, __j++) { |
_M_buffer[__i] = __s[__j]; |
} |
_M_buf_count += __len; |
} else if (0 == _M_buf_count) { |
_M_prefix->append(__s, __s + __len); |
} else { |
flush(); |
append(__s, __len); |
} |
} |
sequence_buffer& write(value_type* __s, size_t __len) |
{ |
append(__s, __len); |
return *this; |
} |
sequence_buffer& put(value_type __x) |
{ |
push_back(__x); |
return *this; |
} |
sequence_buffer& operator=(const value_type& __rhs) |
{ |
push_back(__rhs); |
return *this; |
} |
sequence_buffer& operator*() { return *this; } |
sequence_buffer& operator++() { return *this; } |
sequence_buffer& operator++(int) { return *this; } |
}; |
// The following should be treated as private, at least for now. |
template<class _CharT> |
class _Rope_char_consumer { |
public: |
// If we had member templates, these should not be virtual. |
// For now we need to use run-time parametrization where |
// compile-time would do. Hence this should all be private |
// for now. |
// The symmetry with char_producer is accidental and temporary. |
virtual ~_Rope_char_consumer() {}; |
virtual bool operator()(const _CharT* __buffer, size_t __len) = 0; |
}; |
// First a lot of forward declarations. The standard seems to require |
// much stricter "declaration before use" than many of the implementations |
// that preceded it. |
template<class _CharT, class _Alloc=allocator<_CharT> > class rope; |
template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation; |
template<class _CharT, class _Alloc> struct _Rope_RopeLeaf; |
template<class _CharT, class _Alloc> struct _Rope_RopeFunction; |
template<class _CharT, class _Alloc> struct _Rope_RopeSubstring; |
template<class _CharT, class _Alloc> class _Rope_iterator; |
template<class _CharT, class _Alloc> class _Rope_const_iterator; |
template<class _CharT, class _Alloc> class _Rope_char_ref_proxy; |
template<class _CharT, class _Alloc> class _Rope_char_ptr_proxy; |
template<class _CharT, class _Alloc> |
bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, |
const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
_Rope_const_iterator<_CharT,_Alloc> operator- |
(const _Rope_const_iterator<_CharT,_Alloc>& __x, |
ptrdiff_t __n); |
template<class _CharT, class _Alloc> |
_Rope_const_iterator<_CharT,_Alloc> operator+ |
(const _Rope_const_iterator<_CharT,_Alloc>& __x, |
ptrdiff_t __n); |
template<class _CharT, class _Alloc> |
_Rope_const_iterator<_CharT,_Alloc> operator+ |
(ptrdiff_t __n, |
const _Rope_const_iterator<_CharT,_Alloc>& __x); |
template<class _CharT, class _Alloc> |
bool operator== |
(const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
bool operator< |
(const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
ptrdiff_t operator- |
(const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
_Rope_iterator<_CharT,_Alloc> operator- |
(const _Rope_iterator<_CharT,_Alloc>& __x, |
ptrdiff_t __n); |
template<class _CharT, class _Alloc> |
_Rope_iterator<_CharT,_Alloc> operator+ |
(const _Rope_iterator<_CharT,_Alloc>& __x, |
ptrdiff_t __n); |
template<class _CharT, class _Alloc> |
_Rope_iterator<_CharT,_Alloc> operator+ |
(ptrdiff_t __n, |
const _Rope_iterator<_CharT,_Alloc>& __x); |
template<class _CharT, class _Alloc> |
bool operator== |
(const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
bool operator< |
(const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
ptrdiff_t operator- |
(const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y); |
template<class _CharT, class _Alloc> |
rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left, |
const rope<_CharT,_Alloc>& __right); |
template<class _CharT, class _Alloc> |
rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left, |
const _CharT* __right); |
template<class _CharT, class _Alloc> |
rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left, |
_CharT __right); |
// Some helpers, so we can use power on ropes. |
// See below for why this isn't local to the implementation. |
// This uses a nonstandard refcount convention. |
// The result has refcount 0. |
template<class _CharT, class _Alloc> |
struct _Rope_Concat_fn |
: public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>, |
rope<_CharT,_Alloc> > { |
rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x, |
const rope<_CharT,_Alloc>& __y) { |
return __x + __y; |
} |
}; |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc> |
identity_element(_Rope_Concat_fn<_CharT, _Alloc>) |
{ |
return rope<_CharT,_Alloc>(); |
} |
// |
// What follows should really be local to rope. Unfortunately, |
// that doesn't work, since it makes it impossible to define generic |
// equality on rope iterators. According to the draft standard, the |
// template parameters for such an equality operator cannot be inferred |
// from the occurence of a member class as a parameter. |
// (SGI compilers in fact allow this, but the __result wouldn't be |
// portable.) |
// Similarly, some of the static member functions are member functions |
// only to avoid polluting the global namespace, and to circumvent |
// restrictions on type inference for template functions. |
// |
// |
// The internal data structure for representing a rope. This is |
// private to the implementation. A rope is really just a pointer |
// to one of these. |
// |
// A few basic functions for manipulating this data structure |
// are members of _RopeRep. Most of the more complex algorithms |
// are implemented as rope members. |
// |
// Some of the static member functions of _RopeRep have identically |
// named functions in rope that simply invoke the _RopeRep versions. |
// |
// A macro to introduce various allocation and deallocation functions |
// These need to be defined differently depending on whether or not |
// we are using standard conforming allocators, and whether the allocator |
// instances have real state. Thus this macro is invoked repeatedly |
// with different definitions of __ROPE_DEFINE_ALLOC. |
// __ROPE_DEFINE_ALLOC(type,name) defines |
// type * name_allocate(size_t) and |
// void name_deallocate(tipe *, size_t) |
// Both functions may or may not be static. |
#define __ROPE_DEFINE_ALLOCS(__a) \ |
__ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \ |
typedef _Rope_RopeConcatenation<_CharT,__a> __C; \ |
__ROPE_DEFINE_ALLOC(__C,_C) \ |
typedef _Rope_RopeLeaf<_CharT,__a> __L; \ |
__ROPE_DEFINE_ALLOC(__L,_L) \ |
typedef _Rope_RopeFunction<_CharT,__a> __F; \ |
__ROPE_DEFINE_ALLOC(__F,_F) \ |
typedef _Rope_RopeSubstring<_CharT,__a> __S; \ |
__ROPE_DEFINE_ALLOC(__S,_S) |
// Internal rope nodes potentially store a copy of the allocator |
// instance used to allocate them. This is mostly redundant. |
// But the alternative would be to pass allocator instances around |
// in some form to nearly all internal functions, since any pointer |
// assignment may result in a zero reference count and thus require |
// deallocation. |
// The _Rope_rep_base class encapsulates |
// the differences between SGI-style allocators and standard-conforming |
// allocators. |
#define __STATIC_IF_SGI_ALLOC /* not static */ |
// Base class for ordinary allocators. |
template <class _CharT, class _Allocator, bool _IsStatic> |
class _Rope_rep_alloc_base { |
public: |
typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return _M_data_allocator; } |
_Rope_rep_alloc_base(size_t __size, const allocator_type& __a) |
: _M_size(__size), _M_data_allocator(__a) {} |
size_t _M_size; // This is here only to avoid wasting space |
// for an otherwise empty base class. |
protected: |
allocator_type _M_data_allocator; |
# define __ROPE_DEFINE_ALLOC(_Tp, __name) \ |
typedef typename \ |
_Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \ |
/*static*/ _Tp * __name##_allocate(size_t __n) \ |
{ return __name##Allocator(_M_data_allocator).allocate(__n); } \ |
void __name##_deallocate(_Tp* __p, size_t __n) \ |
{ __name##Allocator(_M_data_allocator).deallocate(__p, __n); } |
__ROPE_DEFINE_ALLOCS(_Allocator); |
# undef __ROPE_DEFINE_ALLOC |
}; |
// Specialization for allocators that have the property that we don't |
// actually have to store an allocator object. |
template <class _CharT, class _Allocator> |
class _Rope_rep_alloc_base<_CharT,_Allocator,true> { |
public: |
typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return allocator_type(); } |
_Rope_rep_alloc_base(size_t __size, const allocator_type&) |
: _M_size(__size) {} |
size_t _M_size; |
protected: |
# define __ROPE_DEFINE_ALLOC(_Tp, __name) \ |
typedef typename \ |
_Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \ |
typedef typename \ |
_Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \ |
static _Tp* __name##_allocate(size_t __n) \ |
{ return __name##Alloc::allocate(__n); } \ |
void __name##_deallocate(_Tp *__p, size_t __n) \ |
{ __name##Alloc::deallocate(__p, __n); } |
__ROPE_DEFINE_ALLOCS(_Allocator); |
# undef __ROPE_DEFINE_ALLOC |
}; |
template <class _CharT, class _Alloc> |
struct _Rope_rep_base |
: public _Rope_rep_alloc_base<_CharT,_Alloc, |
_Alloc_traits<_CharT,_Alloc>::_S_instanceless> |
{ |
typedef _Rope_rep_alloc_base<_CharT,_Alloc, |
_Alloc_traits<_CharT,_Alloc>::_S_instanceless> |
_Base; |
typedef typename _Base::allocator_type allocator_type; |
_Rope_rep_base(size_t __size, const allocator_type& __a) |
: _Base(__size, __a) {} |
}; |
template<class _CharT, class _Alloc> |
struct _Rope_RopeRep : public _Rope_rep_base<_CharT,_Alloc> |
# ifndef __GC |
, _Refcount_Base |
# endif |
{ |
public: |
enum { _S_max_rope_depth = 45 }; |
enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; |
_Tag _M_tag:8; |
bool _M_is_balanced:8; |
unsigned char _M_depth; |
__GC_CONST _CharT* _M_c_string; |
/* Flattened version of string, if needed. */ |
/* typically 0. */ |
/* If it's not 0, then the memory is owned */ |
/* by this node. */ |
/* In the case of a leaf, this may point to */ |
/* the same memory as the data field. */ |
typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type |
allocator_type; |
_Rope_RopeRep(_Tag __t, int __d, bool __b, size_t __size, |
allocator_type __a) |
: _Rope_rep_base<_CharT,_Alloc>(__size, __a), |
# ifndef __GC |
_Refcount_Base(1), |
# endif |
_M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0) |
{ } |
# ifdef __GC |
void _M_incr () {} |
# endif |
static void _S_free_string(__GC_CONST _CharT*, size_t __len, |
allocator_type __a); |
# define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a); |
// Deallocate data section of a leaf. |
// This shouldn't be a member function. |
// But its hard to do anything else at the |
// moment, because it's templatized w.r.t. |
// an allocator. |
// Does nothing if __GC is defined. |
# ifndef __GC |
void _M_free_c_string(); |
void _M_free_tree(); |
// Deallocate t. Assumes t is not 0. |
void _M_unref_nonnil() |
{ |
if (0 == _M_decr()) _M_free_tree(); |
} |
void _M_ref_nonnil() |
{ |
_M_incr(); |
} |
static void _S_unref(_Rope_RopeRep* __t) |
{ |
if (0 != __t) { |
__t->_M_unref_nonnil(); |
} |
} |
static void _S_ref(_Rope_RopeRep* __t) |
{ |
if (0 != __t) __t->_M_incr(); |
} |
static void _S_free_if_unref(_Rope_RopeRep* __t) |
{ |
if (0 != __t && 0 == __t->_M_ref_count) __t->_M_free_tree(); |
} |
# else /* __GC */ |
void _M_unref_nonnil() {} |
void _M_ref_nonnil() {} |
static void _S_unref(_Rope_RopeRep*) {} |
static void _S_ref(_Rope_RopeRep*) {} |
static void _S_free_if_unref(_Rope_RopeRep*) {} |
# endif |
}; |
template<class _CharT, class _Alloc> |
struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> { |
public: |
// Apparently needed by VC++ |
// The data fields of leaves are allocated with some |
// extra space, to accomodate future growth and for basic |
// character types, to hold a trailing eos character. |
enum { _S_alloc_granularity = 8 }; |
static size_t _S_rounded_up_size(size_t __n) { |
size_t __size_with_eos; |
if (_S_is_basic_char_type((_CharT*)0)) { |
__size_with_eos = __n + 1; |
} else { |
__size_with_eos = __n; |
} |
# ifdef __GC |
return __size_with_eos; |
# else |
// Allow slop for in-place expansion. |
return (__size_with_eos + _S_alloc_granularity-1) |
&~ (_S_alloc_granularity-1); |
# endif |
} |
__GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */ |
/* The allocated size is */ |
/* _S_rounded_up_size(size), except */ |
/* in the GC case, in which it */ |
/* doesn't matter. */ |
typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type |
allocator_type; |
_Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, allocator_type __a) |
: _Rope_RopeRep<_CharT,_Alloc>(_S_leaf, 0, true, __size, __a), |
_M_data(__d) |
{ |
__stl_assert(__size > 0); |
if (_S_is_basic_char_type((_CharT *)0)) { |
// already eos terminated. |
_M_c_string = __d; |
} |
} |
// The constructor assumes that d has been allocated with |
// the proper allocator and the properly padded size. |
// In contrast, the destructor deallocates the data: |
# ifndef __GC |
~_Rope_RopeLeaf() { |
if (_M_data != _M_c_string) { |
_M_free_c_string(); |
} |
__STL_FREE_STRING(_M_data, _M_size, get_allocator()); |
} |
# endif |
}; |
template<class _CharT, class _Alloc> |
struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT,_Alloc> { |
public: |
_Rope_RopeRep<_CharT,_Alloc>* _M_left; |
_Rope_RopeRep<_CharT,_Alloc>* _M_right; |
typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type |
allocator_type; |
_Rope_RopeConcatenation(_Rope_RopeRep<_CharT,_Alloc>* __l, |
_Rope_RopeRep<_CharT,_Alloc>* __r, |
allocator_type __a) |
: _Rope_RopeRep<_CharT,_Alloc>(_S_concat, |
max(__l->_M_depth, __r->_M_depth) + 1, |
false, |
__l->_M_size + __r->_M_size, __a), |
_M_left(__l), _M_right(__r) |
{} |
# ifndef __GC |
~_Rope_RopeConcatenation() { |
_M_free_c_string(); |
_M_left->_M_unref_nonnil(); |
_M_right->_M_unref_nonnil(); |
} |
# endif |
}; |
template<class _CharT, class _Alloc> |
struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT,_Alloc> { |
public: |
char_producer<_CharT>* _M_fn; |
# ifndef __GC |
bool _M_delete_when_done; // Char_producer is owned by the |
// rope and should be explicitly |
// deleted when the rope becomes |
// inaccessible. |
# else |
// In the GC case, we either register the rope for |
// finalization, or not. Thus the field is unnecessary; |
// the information is stored in the collector data structures. |
// We do need a finalization procedure to be invoked by the |
// collector. |
static void _S_fn_finalization_proc(void * __tree, void *) { |
delete ((_Rope_RopeFunction *)__tree) -> _M_fn; |
} |
# endif |
typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type |
allocator_type; |
_Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, |
bool __d, allocator_type __a) |
: _Rope_RopeRep<_CharT,_Alloc>(_S_function, 0, true, __size, __a) |
, _M_fn(__f) |
# ifndef __GC |
, _M_delete_when_done(__d) |
# endif |
{ |
__stl_assert(__size > 0); |
# ifdef __GC |
if (__d) { |
GC_REGISTER_FINALIZER( |
this, _Rope_RopeFunction::_S_fn_finalization_proc, 0, 0, 0); |
} |
# endif |
} |
# ifndef __GC |
~_Rope_RopeFunction() { |
_M_free_c_string(); |
if (_M_delete_when_done) { |
delete _M_fn; |
} |
} |
# endif |
}; |
// Substring results are usually represented using just |
// concatenation nodes. But in the case of very long flat ropes |
// or ropes with a functional representation that isn't practical. |
// In that case, we represent the __result as a special case of |
// RopeFunction, whose char_producer points back to the rope itself. |
// In all cases except repeated substring operations and |
// deallocation, we treat the __result as a RopeFunction. |
template<class _CharT, class _Alloc> |
struct _Rope_RopeSubstring : public _Rope_RopeFunction<_CharT,_Alloc>, |
public char_producer<_CharT> { |
public: |
// XXX this whole class should be rewritten. |
_Rope_RopeRep<_CharT,_Alloc>* _M_base; // not 0 |
size_t _M_start; |
virtual void operator()(size_t __start_pos, size_t __req_len, |
_CharT* __buffer) { |
switch(_M_base->_M_tag) { |
case _S_function: |
case _S_substringfn: |
{ |
char_producer<_CharT>* __fn = |
((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn; |
__stl_assert(__start_pos + __req_len <= _M_size); |
__stl_assert(_M_start + _M_size <= _M_base->_M_size); |
(*__fn)(__start_pos + _M_start, __req_len, __buffer); |
} |
break; |
case _S_leaf: |
{ |
__GC_CONST _CharT* __s = |
((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data; |
uninitialized_copy_n(__s + __start_pos + _M_start, __req_len, |
__buffer); |
} |
break; |
default: |
__stl_assert(false); |
} |
} |
typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type |
allocator_type; |
_Rope_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s, |
size_t __l, allocator_type __a) |
: _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a), |
char_producer<_CharT>(), |
_M_base(__b), |
_M_start(__s) |
{ |
__stl_assert(__l > 0); |
__stl_assert(__s + __l <= __b->_M_size); |
# ifndef __GC |
_M_base->_M_ref_nonnil(); |
# endif |
_M_tag = _S_substringfn; |
} |
virtual ~_Rope_RopeSubstring() |
{ |
# ifndef __GC |
_M_base->_M_unref_nonnil(); |
// _M_free_c_string(); -- done by parent class |
# endif |
} |
}; |
// Self-destructing pointers to Rope_rep. |
// These are not conventional smart pointers. Their |
// only purpose in life is to ensure that unref is called |
// on the pointer either at normal exit or if an exception |
// is raised. It is the caller's responsibility to |
// adjust reference counts when these pointers are initialized |
// or assigned to. (This convention significantly reduces |
// the number of potentially expensive reference count |
// updates.) |
#ifndef __GC |
template<class _CharT, class _Alloc> |
struct _Rope_self_destruct_ptr { |
_Rope_RopeRep<_CharT,_Alloc>* _M_ptr; |
~_Rope_self_destruct_ptr() |
{ _Rope_RopeRep<_CharT,_Alloc>::_S_unref(_M_ptr); } |
# ifdef __STL_USE_EXCEPTIONS |
_Rope_self_destruct_ptr() : _M_ptr(0) {}; |
# else |
_Rope_self_destruct_ptr() {}; |
# endif |
_Rope_self_destruct_ptr(_Rope_RopeRep<_CharT,_Alloc>* __p) : _M_ptr(__p) {} |
_Rope_RopeRep<_CharT,_Alloc>& operator*() { return *_M_ptr; } |
_Rope_RopeRep<_CharT,_Alloc>* operator->() { return _M_ptr; } |
operator _Rope_RopeRep<_CharT,_Alloc>*() { return _M_ptr; } |
_Rope_self_destruct_ptr& operator= (_Rope_RopeRep<_CharT,_Alloc>* __x) |
{ _M_ptr = __x; return *this; } |
}; |
#endif |
// Dereferencing a nonconst iterator has to return something |
// that behaves almost like a reference. It's not possible to |
// return an actual reference since assignment requires extra |
// work. And we would get into the same problems as with the |
// CD2 version of basic_string. |
template<class _CharT, class _Alloc> |
class _Rope_char_ref_proxy { |
friend class rope<_CharT,_Alloc>; |
friend class _Rope_iterator<_CharT,_Alloc>; |
friend class _Rope_char_ptr_proxy<_CharT,_Alloc>; |
# ifdef __GC |
typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr; |
# else |
typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr; |
# endif |
typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; |
typedef rope<_CharT,_Alloc> _My_rope; |
size_t _M_pos; |
_CharT _M_current; |
bool _M_current_valid; |
_My_rope* _M_root; // The whole rope. |
public: |
_Rope_char_ref_proxy(_My_rope* __r, size_t __p) |
: _M_pos(__p), _M_current_valid(false), _M_root(__r) {} |
_Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) |
: _M_pos(__x._M_pos), _M_current_valid(false), _M_root(__x._M_root) {} |
// Don't preserve cache if the reference can outlive the |
// expression. We claim that's not possible without calling |
// a copy constructor or generating reference to a proxy |
// reference. We declare the latter to have undefined semantics. |
_Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c) |
: _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {} |
inline operator _CharT () const; |
_Rope_char_ref_proxy& operator= (_CharT __c); |
_Rope_char_ptr_proxy<_CharT,_Alloc> operator& () const; |
_Rope_char_ref_proxy& operator= (const _Rope_char_ref_proxy& __c) { |
return operator=((_CharT)__c); |
} |
}; |
template<class _CharT, class __Alloc> |
inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, |
_Rope_char_ref_proxy <_CharT, __Alloc > __b) { |
_CharT __tmp = __a; |
__a = __b; |
__b = __tmp; |
} |
template<class _CharT, class _Alloc> |
class _Rope_char_ptr_proxy { |
// XXX this class should be rewritten. |
friend class _Rope_char_ref_proxy<_CharT,_Alloc>; |
size_t _M_pos; |
rope<_CharT,_Alloc>* _M_root; // The whole rope. |
public: |
_Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) |
: _M_pos(__x._M_pos), _M_root(__x._M_root) {} |
_Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x) |
: _M_pos(__x._M_pos), _M_root(__x._M_root) {} |
_Rope_char_ptr_proxy() {} |
_Rope_char_ptr_proxy(_CharT* __x) : _M_root(0), _M_pos(0) { |
__stl_assert(0 == __x); |
} |
_Rope_char_ptr_proxy& |
operator= (const _Rope_char_ptr_proxy& __x) { |
_M_pos = __x._M_pos; |
_M_root = __x._M_root; |
return *this; |
} |
template<class _CharT2, class _Alloc2> |
friend bool operator== (const _Rope_char_ptr_proxy<_CharT2,_Alloc2>& __x, |
const _Rope_char_ptr_proxy<_CharT2,_Alloc2>& __y); |
_Rope_char_ref_proxy<_CharT,_Alloc> operator*() const { |
return _Rope_char_ref_proxy<_CharT,_Alloc>(_M_root, _M_pos); |
} |
}; |
// Rope iterators: |
// Unlike in the C version, we cache only part of the stack |
// for rope iterators, since they must be efficiently copyable. |
// When we run out of cache, we have to reconstruct the iterator |
// value. |
// Pointers from iterators are not included in reference counts. |
// Iterators are assumed to be thread private. Ropes can |
// be shared. |
template<class _CharT, class _Alloc> |
class _Rope_iterator_base |
: public random_access_iterator<_CharT, ptrdiff_t> { |
friend class rope<_CharT,_Alloc>; |
public: |
typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround |
typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; |
// Borland doesnt want this to be protected. |
protected: |
enum { _S_path_cache_len = 4 }; // Must be <= 9. |
enum { _S_iterator_buf_len = 15 }; |
size_t _M_current_pos; |
_RopeRep* _M_root; // The whole rope. |
size_t _M_leaf_pos; // Starting position for current leaf |
__GC_CONST _CharT* _M_buf_start; |
// Buffer possibly |
// containing current char. |
__GC_CONST _CharT* _M_buf_ptr; |
// Pointer to current char in buffer. |
// != 0 ==> buffer valid. |
__GC_CONST _CharT* _M_buf_end; |
// One past __last valid char in buffer. |
// What follows is the path cache. We go out of our |
// way to make this compact. |
// Path_end contains the bottom section of the path from |
// the root to the current leaf. |
const _RopeRep* _M_path_end[_S_path_cache_len]; |
int _M_leaf_index; // Last valid __pos in path_end; |
// _M_path_end[0] ... _M_path_end[leaf_index-1] |
// point to concatenation nodes. |
unsigned char _M_path_directions; |
// (path_directions >> __i) & 1 is 1 |
// iff we got from _M_path_end[leaf_index - __i - 1] |
// to _M_path_end[leaf_index - __i] by going to the |
// __right. Assumes path_cache_len <= 9. |
_CharT _M_tmp_buf[_S_iterator_buf_len]; |
// Short buffer for surrounding chars. |
// This is useful primarily for |
// RopeFunctions. We put the buffer |
// here to avoid locking in the |
// multithreaded case. |
// The cached path is generally assumed to be valid |
// only if the buffer is valid. |
static void _S_setbuf(_Rope_iterator_base& __x); |
// Set buffer contents given |
// path cache. |
static void _S_setcache(_Rope_iterator_base& __x); |
// Set buffer contents and |
// path cache. |
static void _S_setcache_for_incr(_Rope_iterator_base& __x); |
// As above, but assumes path |
// cache is valid for previous posn. |
_Rope_iterator_base() {} |
_Rope_iterator_base(_RopeRep* __root, size_t __pos) |
: _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) {} |
void _M_incr(size_t __n); |
void _M_decr(size_t __n); |
public: |
size_t index() const { return _M_current_pos; } |
_Rope_iterator_base(const _Rope_iterator_base& __x) { |
if (0 != __x._M_buf_ptr) { |
*this = __x; |
} else { |
_M_current_pos = __x._M_current_pos; |
_M_root = __x._M_root; |
_M_buf_ptr = 0; |
} |
} |
}; |
template<class _CharT, class _Alloc> class _Rope_iterator; |
template<class _CharT, class _Alloc> |
class _Rope_const_iterator : public _Rope_iterator_base<_CharT,_Alloc> { |
friend class rope<_CharT,_Alloc>; |
protected: |
typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; |
// The one from the base class may not be directly visible. |
_Rope_const_iterator(const _RopeRep* __root, size_t __pos): |
_Rope_iterator_base<_CharT,_Alloc>( |
const_cast<_RopeRep*>(__root), __pos) |
// Only nonconst iterators modify root ref count |
{} |
public: |
typedef _CharT reference; // Really a value. Returning a reference |
// Would be a mess, since it would have |
// to be included in refcount. |
typedef const _CharT* pointer; |
public: |
_Rope_const_iterator() {}; |
_Rope_const_iterator(const _Rope_const_iterator& __x) : |
_Rope_iterator_base<_CharT,_Alloc>(__x) { } |
_Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x); |
_Rope_const_iterator(const rope<_CharT,_Alloc>& __r, size_t __pos) : |
_Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) {} |
_Rope_const_iterator& operator= (const _Rope_const_iterator& __x) { |
if (0 != __x._M_buf_ptr) { |
*(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x; |
} else { |
_M_current_pos = __x._M_current_pos; |
_M_root = __x._M_root; |
_M_buf_ptr = 0; |
} |
return(*this); |
} |
reference operator*() { |
if (0 == _M_buf_ptr) _S_setcache(*this); |
return *_M_buf_ptr; |
} |
_Rope_const_iterator& operator++() { |
__GC_CONST _CharT* __next; |
if (0 != _M_buf_ptr && (__next = _M_buf_ptr + 1) < _M_buf_end) { |
_M_buf_ptr = __next; |
++_M_current_pos; |
} else { |
_M_incr(1); |
} |
return *this; |
} |
_Rope_const_iterator& operator+=(ptrdiff_t __n) { |
if (__n >= 0) { |
_M_incr(__n); |
} else { |
_M_decr(-__n); |
} |
return *this; |
} |
_Rope_const_iterator& operator--() { |
_M_decr(1); |
return *this; |
} |
_Rope_const_iterator& operator-=(ptrdiff_t __n) { |
if (__n >= 0) { |
_M_decr(__n); |
} else { |
_M_incr(-__n); |
} |
return *this; |
} |
_Rope_const_iterator operator++(int) { |
size_t __old_pos = _M_current_pos; |
_M_incr(1); |
return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos); |
// This makes a subsequent dereference expensive. |
// Perhaps we should instead copy the iterator |
// if it has a valid cache? |
} |
_Rope_const_iterator operator--(int) { |
size_t __old_pos = _M_current_pos; |
_M_decr(1); |
return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos); |
} |
template<class _CharT2, class _Alloc2> |
friend _Rope_const_iterator<_CharT2,_Alloc2> operator- |
(const _Rope_const_iterator<_CharT2,_Alloc2>& __x, |
ptrdiff_t __n); |
template<class _CharT2, class _Alloc2> |
friend _Rope_const_iterator<_CharT2,_Alloc2> operator+ |
(const _Rope_const_iterator<_CharT2,_Alloc2>& __x, |
ptrdiff_t __n); |
template<class _CharT2, class _Alloc2> |
friend _Rope_const_iterator<_CharT2,_Alloc2> operator+ |
(ptrdiff_t __n, |
const _Rope_const_iterator<_CharT2,_Alloc2>& __x); |
reference operator[](size_t __n) { |
return rope<_CharT,_Alloc>::_S_fetch(_M_root, _M_current_pos + __n); |
} |
template<class _CharT2, class _Alloc2> |
friend bool operator== |
(const _Rope_const_iterator<_CharT2,_Alloc2>& __x, |
const _Rope_const_iterator<_CharT2,_Alloc2>& __y); |
template<class _CharT2, class _Alloc2> |
friend bool operator< |
(const _Rope_const_iterator<_CharT2,_Alloc2>& __x, |
const _Rope_const_iterator<_CharT2,_Alloc2>& __y); |
template<class _CharT2, class _Alloc2> |
friend ptrdiff_t operator- |
(const _Rope_const_iterator<_CharT2,_Alloc2>& __x, |
const _Rope_const_iterator<_CharT2,_Alloc2>& __y); |
}; |
template<class _CharT, class _Alloc> |
class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> { |
friend class rope<_CharT,_Alloc>; |
protected: |
rope<_CharT,_Alloc>* _M_root_rope; |
// root is treated as a cached version of this, |
// and is used to detect changes to the underlying |
// rope. |
// Root is included in the reference count. |
// This is necessary so that we can detect changes reliably. |
// Unfortunately, it requires careful bookkeeping for the |
// nonGC case. |
_Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos) |
: _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr, __pos), |
_M_root_rope(__r) |
{ _RopeRep::_S_ref(_M_root); if (!(__r -> empty()))_S_setcache(*this); } |
void _M_check(); |
public: |
typedef _Rope_char_ref_proxy<_CharT,_Alloc> reference; |
typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer; |
public: |
rope<_CharT,_Alloc>& container() { return *_M_root_rope; } |
_Rope_iterator() { |
_M_root = 0; // Needed for reference counting. |
}; |
_Rope_iterator(const _Rope_iterator& __x) : |
_Rope_iterator_base<_CharT,_Alloc>(__x) { |
_M_root_rope = __x._M_root_rope; |
_RopeRep::_S_ref(_M_root); |
} |
_Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos); |
~_Rope_iterator() { |
_RopeRep::_S_unref(_M_root); |
} |
_Rope_iterator& operator= (const _Rope_iterator& __x) { |
_RopeRep* __old = _M_root; |
_RopeRep::_S_ref(__x._M_root); |
if (0 != __x._M_buf_ptr) { |
_M_root_rope = __x._M_root_rope; |
*(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x; |
} else { |
_M_current_pos = __x._M_current_pos; |
_M_root = __x._M_root; |
_M_root_rope = __x._M_root_rope; |
_M_buf_ptr = 0; |
} |
_RopeRep::_S_unref(__old); |
return(*this); |
} |
reference operator*() { |
_M_check(); |
if (0 == _M_buf_ptr) { |
return _Rope_char_ref_proxy<_CharT,_Alloc>( |
_M_root_rope, _M_current_pos); |
} else { |
return _Rope_char_ref_proxy<_CharT,_Alloc>( |
_M_root_rope, _M_current_pos, *_M_buf_ptr); |
} |
} |
_Rope_iterator& operator++() { |
_M_incr(1); |
return *this; |
} |
_Rope_iterator& operator+=(ptrdiff_t __n) { |
if (__n >= 0) { |
_M_incr(__n); |
} else { |
_M_decr(-__n); |
} |
return *this; |
} |
_Rope_iterator& operator--() { |
_M_decr(1); |
return *this; |
} |
_Rope_iterator& operator-=(ptrdiff_t __n) { |
if (__n >= 0) { |
_M_decr(__n); |
} else { |
_M_incr(-__n); |
} |
return *this; |
} |
_Rope_iterator operator++(int) { |
size_t __old_pos = _M_current_pos; |
_M_incr(1); |
return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos); |
} |
_Rope_iterator operator--(int) { |
size_t __old_pos = _M_current_pos; |
_M_decr(1); |
return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos); |
} |
reference operator[](ptrdiff_t __n) { |
return _Rope_char_ref_proxy<_CharT,_Alloc>( |
_M_root_rope, _M_current_pos + __n); |
} |
template<class _CharT2, class _Alloc2> |
friend bool operator== |
(const _Rope_iterator<_CharT2,_Alloc2>& __x, |
const _Rope_iterator<_CharT2,_Alloc2>& __y); |
template<class _CharT2, class _Alloc2> |
friend bool operator< |
(const _Rope_iterator<_CharT2,_Alloc2>& __x, |
const _Rope_iterator<_CharT2,_Alloc2>& __y); |
template<class _CharT2, class _Alloc2> |
friend ptrdiff_t operator- |
(const _Rope_iterator<_CharT2,_Alloc2>& __x, |
const _Rope_iterator<_CharT2,_Alloc2>& __y); |
template<class _CharT2, class _Alloc2> |
friend _Rope_iterator<_CharT2,_Alloc2> operator- |
(const _Rope_iterator<_CharT2,_Alloc2>& __x, |
ptrdiff_t __n); |
template<class _CharT2, class _Alloc2> |
friend _Rope_iterator<_CharT2,_Alloc2> operator+ |
(const _Rope_iterator<_CharT2,_Alloc2>& __x, |
ptrdiff_t __n); |
template<class _CharT2, class _Alloc2> |
friend _Rope_iterator<_CharT2,_Alloc2> operator+ |
(ptrdiff_t __n, |
const _Rope_iterator<_CharT2,_Alloc2>& __x); |
}; |
// The rope base class encapsulates |
// the differences between SGI-style allocators and standard-conforming |
// allocators. |
// Base class for ordinary allocators. |
template <class _CharT, class _Allocator, bool _IsStatic> |
class _Rope_alloc_base { |
public: |
typedef _Rope_RopeRep<_CharT,_Allocator> _RopeRep; |
typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return _M_data_allocator; } |
_Rope_alloc_base(_RopeRep *__t, const allocator_type& __a) |
: _M_tree_ptr(__t), _M_data_allocator(__a) {} |
_Rope_alloc_base(const allocator_type& __a) |
: _M_data_allocator(__a) {} |
protected: |
// The only data members of a rope: |
allocator_type _M_data_allocator; |
_RopeRep* _M_tree_ptr; |
# define __ROPE_DEFINE_ALLOC(_Tp, __name) \ |
typedef typename \ |
_Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \ |
_Tp* __name##_allocate(size_t __n) const \ |
{ return __name##Allocator(_M_data_allocator).allocate(__n); } \ |
void __name##_deallocate(_Tp *__p, size_t __n) const \ |
{ __name##Allocator(_M_data_allocator).deallocate(__p, __n); } |
__ROPE_DEFINE_ALLOCS(_Allocator) |
# undef __ROPE_DEFINE_ALLOC |
}; |
// Specialization for allocators that have the property that we don't |
// actually have to store an allocator object. |
template <class _CharT, class _Allocator> |
class _Rope_alloc_base<_CharT,_Allocator,true> { |
public: |
typedef _Rope_RopeRep<_CharT,_Allocator> _RopeRep; |
typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type |
allocator_type; |
allocator_type get_allocator() const { return allocator_type(); } |
_Rope_alloc_base(_RopeRep *__t, const allocator_type&) |
: _M_tree_ptr(__t) {} |
_Rope_alloc_base(const allocator_type&) {} |
protected: |
// The only data member of a rope: |
_RopeRep *_M_tree_ptr; |
# define __ROPE_DEFINE_ALLOC(_Tp, __name) \ |
typedef typename \ |
_Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \ |
typedef typename \ |
_Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \ |
static _Tp* __name##_allocate(size_t __n) \ |
{ return __name##Alloc::allocate(__n); } \ |
static void __name##_deallocate(_Tp *__p, size_t __n) \ |
{ __name##Alloc::deallocate(__p, __n); } |
__ROPE_DEFINE_ALLOCS(_Allocator) |
# undef __ROPE_DEFINE_ALLOC |
}; |
template <class _CharT, class _Alloc> |
struct _Rope_base |
: public _Rope_alloc_base<_CharT,_Alloc, |
_Alloc_traits<_CharT,_Alloc>::_S_instanceless> |
{ |
typedef _Rope_alloc_base<_CharT,_Alloc, |
_Alloc_traits<_CharT,_Alloc>::_S_instanceless> |
_Base; |
typedef typename _Base::allocator_type allocator_type; |
typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; |
// The one in _Base may not be visible due to template rules. |
_Rope_base(_RopeRep* __t, const allocator_type& __a) : _Base(__t, __a) {} |
_Rope_base(const allocator_type& __a) : _Base(__a) {} |
}; |
template <class _CharT, class _Alloc> |
class rope : public _Rope_base<_CharT,_Alloc> { |
public: |
typedef _CharT value_type; |
typedef ptrdiff_t difference_type; |
typedef size_t size_type; |
typedef _CharT const_reference; |
typedef const _CharT* const_pointer; |
typedef _Rope_iterator<_CharT,_Alloc> iterator; |
typedef _Rope_const_iterator<_CharT,_Alloc> const_iterator; |
typedef _Rope_char_ref_proxy<_CharT,_Alloc> reference; |
typedef _Rope_char_ptr_proxy<_CharT,_Alloc> pointer; |
friend class _Rope_iterator<_CharT,_Alloc>; |
friend class _Rope_const_iterator<_CharT,_Alloc>; |
friend struct _Rope_RopeRep<_CharT,_Alloc>; |
friend class _Rope_iterator_base<_CharT,_Alloc>; |
friend class _Rope_char_ptr_proxy<_CharT,_Alloc>; |
friend class _Rope_char_ref_proxy<_CharT,_Alloc>; |
friend struct _Rope_RopeSubstring<_CharT,_Alloc>; |
protected: |
typedef _Rope_base<_CharT,_Alloc> _Base; |
typedef typename _Base::allocator_type allocator_type; |
using _Base::_M_tree_ptr; |
typedef __GC_CONST _CharT* _Cstrptr; |
static _CharT _S_empty_c_str[1]; |
static bool _S_is0(_CharT __c) { return __c == _S_eos((_CharT*)0); } |
enum { _S_copy_max = 23 }; |
// For strings shorter than _S_copy_max, we copy to |
// concatenate. |
typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; |
typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation; |
typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf; |
typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction; |
typedef _Rope_RopeSubstring<_CharT,_Alloc> _RopeSubstring; |
// Retrieve a character at the indicated position. |
static _CharT _S_fetch(_RopeRep* __r, size_type __pos); |
# ifndef __GC |
// Obtain a pointer to the character at the indicated position. |
// The pointer can be used to change the character. |
// If such a pointer cannot be produced, as is frequently the |
// case, 0 is returned instead. |
// (Returns nonzero only if all nodes in the path have a refcount |
// of 1.) |
static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos); |
# endif |
static bool _S_apply_to_pieces( |
// should be template parameter |
_Rope_char_consumer<_CharT>& __c, |
const _RopeRep* __r, |
size_t __begin, size_t __end); |
// begin and end are assumed to be in range. |
# ifndef __GC |
static void _S_unref(_RopeRep* __t) |
{ |
_RopeRep::_S_unref(__t); |
} |
static void _S_ref(_RopeRep* __t) |
{ |
_RopeRep::_S_ref(__t); |
} |
# else /* __GC */ |
static void _S_unref(_RopeRep*) {} |
static void _S_ref(_RopeRep*) {} |
# endif |
# ifdef __GC |
typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr; |
# else |
typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr; |
# endif |
// _Result is counted in refcount. |
static _RopeRep* _S_substring(_RopeRep* __base, |
size_t __start, size_t __endp1); |
static _RopeRep* _S_concat_char_iter(_RopeRep* __r, |
const _CharT* __iter, size_t __slen); |
// Concatenate rope and char ptr, copying __s. |
// Should really take an arbitrary iterator. |
// Result is counted in refcount. |
static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r, |
const _CharT* __iter, size_t __slen) |
// As above, but one reference to __r is about to be |
// destroyed. Thus the pieces may be recycled if all |
// relevent reference counts are 1. |
# ifdef __GC |
// We can't really do anything since refcounts are unavailable. |
{ return _S_concat_char_iter(__r, __iter, __slen); } |
# else |
; |
# endif |
static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right); |
// General concatenation on _RopeRep. _Result |
// has refcount of 1. Adjusts argument refcounts. |
public: |
void apply_to_pieces( size_t __begin, size_t __end, |
_Rope_char_consumer<_CharT>& __c) const { |
_S_apply_to_pieces(__c, _M_tree_ptr, __begin, __end); |
} |
protected: |
static size_t _S_rounded_up_size(size_t __n) { |
return _RopeLeaf::_S_rounded_up_size(__n); |
} |
static size_t _S_allocated_capacity(size_t __n) { |
if (_S_is_basic_char_type((_CharT*)0)) { |
return _S_rounded_up_size(__n) - 1; |
} else { |
return _S_rounded_up_size(__n); |
} |
} |
// Allocate and construct a RopeLeaf using the supplied allocator |
// Takes ownership of s instead of copying. |
static _RopeLeaf* _S_new_RopeLeaf(__GC_CONST _CharT *__s, |
size_t __size, allocator_type __a) |
{ |
_RopeLeaf* __space = _LAllocator(__a).allocate(1); |
return new(__space) _RopeLeaf(__s, __size, __a); |
} |
static _RopeConcatenation* _S_new_RopeConcatenation( |
_RopeRep* __left, _RopeRep* __right, |
allocator_type __a) |
{ |
_RopeConcatenation* __space = _CAllocator(__a).allocate(1); |
return new(__space) _RopeConcatenation(__left, __right, __a); |
} |
static _RopeFunction* _S_new_RopeFunction(char_producer<_CharT>* __f, |
size_t __size, bool __d, allocator_type __a) |
{ |
_RopeFunction* __space = _FAllocator(__a).allocate(1); |
return new(__space) _RopeFunction(__f, __size, __d, __a); |
} |
static _RopeSubstring* _S_new_RopeSubstring( |
_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s, |
size_t __l, allocator_type __a) |
{ |
_RopeSubstring* __space = _SAllocator(__a).allocate(1); |
return new(__space) _RopeSubstring(__b, __s, __l, __a); |
} |
static |
_RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s, |
size_t __size, allocator_type __a) |
# define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \ |
_S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a) |
{ |
if (0 == __size) return 0; |
_CharT* __buf = __a.allocate(_S_rounded_up_size(__size)); |
uninitialized_copy_n(__s, __size, __buf); |
_S_cond_store_eos(__buf[__size]); |
__STL_TRY { |
return _S_new_RopeLeaf(__buf, __size, __a); |
} |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__buf, __size, __a)) |
} |
// Concatenation of nonempty strings. |
// Always builds a concatenation node. |
// Rebalances if the result is too deep. |
// Result has refcount 1. |
// Does not increment left and right ref counts even though |
// they are referenced. |
static _RopeRep* |
_S_tree_concat(_RopeRep* __left, _RopeRep* __right); |
// Concatenation helper functions |
static _RopeLeaf* |
_S_leaf_concat_char_iter(_RopeLeaf* __r, |
const _CharT* __iter, size_t __slen); |
// Concatenate by copying leaf. |
// should take an arbitrary iterator |
// result has refcount 1. |
# ifndef __GC |
static _RopeLeaf* _S_destr_leaf_concat_char_iter |
(_RopeLeaf* __r, const _CharT* __iter, size_t __slen); |
// A version that potentially clobbers __r if __r->_M_ref_count == 1. |
# endif |
private: |
static size_t _S_char_ptr_len(const _CharT* __s); |
// slightly generalized strlen |
rope(_RopeRep* __t, const allocator_type& __a = allocator_type()) |
: _Base(__t,__a) { } |
// Copy __r to the _CharT buffer. |
// Returns __buffer + __r->_M_size. |
// Assumes that buffer is uninitialized. |
static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer); |
// Again, with explicit starting position and length. |
// Assumes that buffer is uninitialized. |
static _CharT* _S_flatten(_RopeRep* __r, |
size_t __start, size_t __len, |
_CharT* __buffer); |
static const unsigned long |
_S_min_len[_RopeRep::_S_max_rope_depth + 1]; |
static bool _S_is_balanced(_RopeRep* __r) |
{ return (__r->_M_size >= _S_min_len[__r->_M_depth]); } |
static bool _S_is_almost_balanced(_RopeRep* __r) |
{ return (__r->_M_depth == 0 || |
__r->_M_size >= _S_min_len[__r->_M_depth - 1]); } |
static bool _S_is_roughly_balanced(_RopeRep* __r) |
{ return (__r->_M_depth <= 1 || |
__r->_M_size >= _S_min_len[__r->_M_depth - 2]); } |
// Assumes the result is not empty. |
static _RopeRep* _S_concat_and_set_balanced(_RopeRep* __left, |
_RopeRep* __right) |
{ |
_RopeRep* __result = _S_concat(__left, __right); |
if (_S_is_balanced(__result)) __result->_M_is_balanced = true; |
return __result; |
} |
// The basic rebalancing operation. Logically copies the |
// rope. The result has refcount of 1. The client will |
// usually decrement the reference count of __r. |
// The result is within height 2 of balanced by the above |
// definition. |
static _RopeRep* _S_balance(_RopeRep* __r); |
// Add all unbalanced subtrees to the forest of balanceed trees. |
// Used only by balance. |
static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest); |
// Add __r to forest, assuming __r is already balanced. |
static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest); |
// Print to stdout, exposing structure |
static void _S_dump(_RopeRep* __r, int __indent = 0); |
// Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp. |
static int _S_compare(const _RopeRep* __x, const _RopeRep* __y); |
public: |
bool empty() const { return 0 == _M_tree_ptr; } |
// Comparison member function. This is public only for those |
// clients that need a ternary comparison. Others |
// should use the comparison operators below. |
int compare(const rope& __y) const { |
return _S_compare(_M_tree_ptr, __y._M_tree_ptr); |
} |
rope(const _CharT* __s, const allocator_type& __a = allocator_type()) |
: _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s), |
__a),__a) |
{ } |
rope(const _CharT* __s, size_t __len, |
const allocator_type& __a = allocator_type()) |
: _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, __a), __a) |
{ } |
// Should perhaps be templatized with respect to the iterator type |
// and use Sequence_buffer. (It should perhaps use sequence_buffer |
// even now.) |
rope(const _CharT *__s, const _CharT *__e, |
const allocator_type& __a = allocator_type()) |
: _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, __a), __a) |
{ } |
rope(const const_iterator& __s, const const_iterator& __e, |
const allocator_type& __a = allocator_type()) |
: _Base(_S_substring(__s._M_root, __s._M_current_pos, |
__e._M_current_pos), __a) |
{ } |
rope(const iterator& __s, const iterator& __e, |
const allocator_type& __a = allocator_type()) |
: _Base(_S_substring(__s._M_root, __s._M_current_pos, |
__e._M_current_pos), __a) |
{ } |
rope(_CharT __c, const allocator_type& __a = allocator_type()) |
: _Base(__a) |
{ |
_CharT* __buf = _Data_allocate(_S_rounded_up_size(1)); |
construct(__buf, __c); |
__STL_TRY { |
_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a); |
} |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__buf, 1, __a)) |
} |
rope(size_t __n, _CharT __c, |
const allocator_type& __a = allocator_type()); |
rope(const allocator_type& __a = allocator_type()) |
: _Base(0, __a) {} |
// Construct a rope from a function that can compute its members |
rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn, |
const allocator_type& __a = allocator_type()) |
: _Base(__a) |
{ |
_M_tree_ptr = (0 == __len) ? |
0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a); |
} |
rope(const rope& __x, const allocator_type& __a = allocator_type()) |
: _Base(__x._M_tree_ptr, __a) |
{ |
_S_ref(_M_tree_ptr); |
} |
~rope() |
{ |
_S_unref(_M_tree_ptr); |
} |
rope& operator=(const rope& __x) |
{ |
_RopeRep* __old = _M_tree_ptr; |
__stl_assert(get_allocator() == __x.get_allocator()); |
_M_tree_ptr = __x._M_tree_ptr; |
_S_ref(_M_tree_ptr); |
_S_unref(__old); |
return(*this); |
} |
void clear() |
{ |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = 0; |
} |
void push_back(_CharT __x) |
{ |
_RopeRep* __old = _M_tree_ptr; |
_M_tree_ptr = _S_destr_concat_char_iter(_M_tree_ptr, &__x, 1); |
_S_unref(__old); |
} |
void pop_back() |
{ |
_RopeRep* __old = _M_tree_ptr; |
_M_tree_ptr = |
_S_substring(_M_tree_ptr, 0, _M_tree_ptr->_M_size - 1); |
_S_unref(__old); |
} |
_CharT back() const |
{ |
return _S_fetch(_M_tree_ptr, _M_tree_ptr->_M_size - 1); |
} |
void push_front(_CharT __x) |
{ |
_RopeRep* __old = _M_tree_ptr; |
_RopeRep* __left = |
__STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, get_allocator()); |
__STL_TRY { |
_M_tree_ptr = _S_concat(__left, _M_tree_ptr); |
_S_unref(__old); |
_S_unref(__left); |
} |
__STL_UNWIND(_S_unref(__left)) |
} |
void pop_front() |
{ |
_RopeRep* __old = _M_tree_ptr; |
_M_tree_ptr = _S_substring(_M_tree_ptr, 1, _M_tree_ptr->_M_size); |
_S_unref(__old); |
} |
_CharT front() const |
{ |
return _S_fetch(_M_tree_ptr, 0); |
} |
void balance() |
{ |
_RopeRep* __old = _M_tree_ptr; |
_M_tree_ptr = _S_balance(_M_tree_ptr); |
_S_unref(__old); |
} |
void copy(_CharT* __buffer) const { |
destroy(__buffer, __buffer + size()); |
_S_flatten(_M_tree_ptr, __buffer); |
} |
// This is the copy function from the standard, but |
// with the arguments reordered to make it consistent with the |
// rest of the interface. |
// Note that this guaranteed not to compile if the draft standard |
// order is assumed. |
size_type copy(size_type __pos, size_type __n, _CharT* __buffer) const |
{ |
size_t __size = size(); |
size_t __len = (__pos + __n > __size? __size - __pos : __n); |
destroy(__buffer, __buffer + __len); |
_S_flatten(_M_tree_ptr, __pos, __len, __buffer); |
return __len; |
} |
// Print to stdout, exposing structure. May be useful for |
// performance debugging. |
void dump() { |
_S_dump(_M_tree_ptr); |
} |
// Convert to 0 terminated string in new allocated memory. |
// Embedded 0s in the input do not terminate the copy. |
const _CharT* c_str() const; |
// As above, but lso use the flattened representation as the |
// the new rope representation. |
const _CharT* replace_with_c_str(); |
// Reclaim memory for the c_str generated flattened string. |
// Intentionally undocumented, since it's hard to say when this |
// is safe for multiple threads. |
void delete_c_str () { |
if (0 == _M_tree_ptr) return; |
if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && |
((_RopeLeaf*)_M_tree_ptr)->_M_data == |
_M_tree_ptr->_M_c_string) { |
// Representation shared |
return; |
} |
# ifndef __GC |
_M_tree_ptr->_M_free_c_string(); |
# endif |
_M_tree_ptr->_M_c_string = 0; |
} |
_CharT operator[] (size_type __pos) const { |
return _S_fetch(_M_tree_ptr, __pos); |
} |
_CharT at(size_type __pos) const { |
// if (__pos >= size()) throw out_of_range; // XXX |
return (*this)[__pos]; |
} |
const_iterator begin() const { |
return(const_iterator(_M_tree_ptr, 0)); |
} |
// An easy way to get a const iterator from a non-const container. |
const_iterator const_begin() const { |
return(const_iterator(_M_tree_ptr, 0)); |
} |
const_iterator end() const { |
return(const_iterator(_M_tree_ptr, size())); |
} |
const_iterator const_end() const { |
return(const_iterator(_M_tree_ptr, size())); |
} |
size_type size() const { |
return(0 == _M_tree_ptr? 0 : _M_tree_ptr->_M_size); |
} |
size_type length() const { |
return size(); |
} |
size_type max_size() const { |
return _S_min_len[_RopeRep::_S_max_rope_depth-1] - 1; |
// Guarantees that the result can be sufficirntly |
// balanced. Longer ropes will probably still work, |
// but it's harder to make guarantees. |
} |
typedef reverse_iterator<const_iterator> const_reverse_iterator; |
const_reverse_iterator rbegin() const { |
return const_reverse_iterator(end()); |
} |
const_reverse_iterator const_rbegin() const { |
return const_reverse_iterator(end()); |
} |
const_reverse_iterator rend() const { |
return const_reverse_iterator(begin()); |
} |
const_reverse_iterator const_rend() const { |
return const_reverse_iterator(begin()); |
} |
template<class _CharT2, class _Alloc2> |
friend rope<_CharT2,_Alloc2> |
operator+ (const rope<_CharT2,_Alloc2>& __left, |
const rope<_CharT2,_Alloc2>& __right); |
template<class _CharT2, class _Alloc2> |
friend rope<_CharT2,_Alloc2> |
operator+ (const rope<_CharT2,_Alloc2>& __left, |
const _CharT2* __right); |
template<class _CharT2, class _Alloc2> |
friend rope<_CharT2,_Alloc2> |
operator+ (const rope<_CharT2,_Alloc2>& __left, _CharT2 __right); |
// The symmetric cases are intentionally omitted, since they're presumed |
// to be less common, and we don't handle them as well. |
// The following should really be templatized. |
// The first argument should be an input iterator or |
// forward iterator with value_type _CharT. |
rope& append(const _CharT* __iter, size_t __n) { |
_RopeRep* __result = |
_S_destr_concat_char_iter(_M_tree_ptr, __iter, __n); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
return *this; |
} |
rope& append(const _CharT* __c_string) { |
size_t __len = _S_char_ptr_len(__c_string); |
append(__c_string, __len); |
return(*this); |
} |
rope& append(const _CharT* __s, const _CharT* __e) { |
_RopeRep* __result = |
_S_destr_concat_char_iter(_M_tree_ptr, __s, __e - __s); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
return *this; |
} |
rope& append(const_iterator __s, const_iterator __e) { |
__stl_assert(__s._M_root == __e._M_root); |
__stl_assert(get_allocator() == __s._M_root->get_allocator()); |
_Self_destruct_ptr __appendee(_S_substring( |
__s._M_root, __s._M_current_pos, __e._M_current_pos)); |
_RopeRep* __result = |
_S_concat(_M_tree_ptr, (_RopeRep*)__appendee); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
return *this; |
} |
rope& append(_CharT __c) { |
_RopeRep* __result = |
_S_destr_concat_char_iter(_M_tree_ptr, &__c, 1); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
return *this; |
} |
rope& append() { return append(_CharT()); } // XXX why? |
rope& append(const rope& __y) { |
__stl_assert(__y.get_allocator() == get_allocator()); |
_RopeRep* __result = _S_concat(_M_tree_ptr, __y._M_tree_ptr); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
return *this; |
} |
rope& append(size_t __n, _CharT __c) { |
rope<_CharT,_Alloc> __last(__n, __c); |
return append(__last); |
} |
void swap(rope& __b) { |
__stl_assert(get_allocator() == __b.get_allocator()); |
_RopeRep* __tmp = _M_tree_ptr; |
_M_tree_ptr = __b._M_tree_ptr; |
__b._M_tree_ptr = __tmp; |
} |
protected: |
// Result is included in refcount. |
static _RopeRep* replace(_RopeRep* __old, size_t __pos1, |
size_t __pos2, _RopeRep* __r) { |
if (0 == __old) { _S_ref(__r); return __r; } |
_Self_destruct_ptr __left( |
_S_substring(__old, 0, __pos1)); |
_Self_destruct_ptr __right( |
_S_substring(__old, __pos2, __old->_M_size)); |
_RopeRep* __result; |
__stl_assert(__old->get_allocator() == __r->get_allocator()); |
if (0 == __r) { |
__result = _S_concat(__left, __right); |
} else { |
_Self_destruct_ptr __left_result(_S_concat(__left, __r)); |
__result = _S_concat(__left_result, __right); |
} |
return __result; |
} |
public: |
void insert(size_t __p, const rope& __r) { |
_RopeRep* __result = |
replace(_M_tree_ptr, __p, __p, __r._M_tree_ptr); |
__stl_assert(get_allocator() == __r.get_allocator()); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
} |
void insert(size_t __p, size_t __n, _CharT __c) { |
rope<_CharT,_Alloc> __r(__n,__c); |
insert(__p, __r); |
} |
void insert(size_t __p, const _CharT* __i, size_t __n) { |
_Self_destruct_ptr __left(_S_substring(_M_tree_ptr, 0, __p)); |
_Self_destruct_ptr __right(_S_substring(_M_tree_ptr, __p, size())); |
_Self_destruct_ptr __left_result( |
_S_concat_char_iter(__left, __i, __n)); |
// _S_ destr_concat_char_iter should be safe here. |
// But as it stands it's probably not a win, since __left |
// is likely to have additional references. |
_RopeRep* __result = _S_concat(__left_result, __right); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
} |
void insert(size_t __p, const _CharT* __c_string) { |
insert(__p, __c_string, _S_char_ptr_len(__c_string)); |
} |
void insert(size_t __p, _CharT __c) { |
insert(__p, &__c, 1); |
} |
void insert(size_t __p) { |
_CharT __c = _CharT(); |
insert(__p, &__c, 1); |
} |
void insert(size_t __p, const _CharT* __i, const _CharT* __j) { |
rope __r(__i, __j); |
insert(__p, __r); |
} |
void insert(size_t __p, const const_iterator& __i, |
const const_iterator& __j) { |
rope __r(__i, __j); |
insert(__p, __r); |
} |
void insert(size_t __p, const iterator& __i, |
const iterator& __j) { |
rope __r(__i, __j); |
insert(__p, __r); |
} |
// (position, length) versions of replace operations: |
void replace(size_t __p, size_t __n, const rope& __r) { |
_RopeRep* __result = |
replace(_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
} |
void replace(size_t __p, size_t __n, |
const _CharT* __i, size_t __i_len) { |
rope __r(__i, __i_len); |
replace(__p, __n, __r); |
} |
void replace(size_t __p, size_t __n, _CharT __c) { |
rope __r(__c); |
replace(__p, __n, __r); |
} |
void replace(size_t __p, size_t __n, const _CharT* __c_string) { |
rope __r(__c_string); |
replace(__p, __n, __r); |
} |
void replace(size_t __p, size_t __n, |
const _CharT* __i, const _CharT* __j) { |
rope __r(__i, __j); |
replace(__p, __n, __r); |
} |
void replace(size_t __p, size_t __n, |
const const_iterator& __i, const const_iterator& __j) { |
rope __r(__i, __j); |
replace(__p, __n, __r); |
} |
void replace(size_t __p, size_t __n, |
const iterator& __i, const iterator& __j) { |
rope __r(__i, __j); |
replace(__p, __n, __r); |
} |
// Single character variants: |
void replace(size_t __p, _CharT __c) { |
iterator __i(this, __p); |
*__i = __c; |
} |
void replace(size_t __p, const rope& __r) { |
replace(__p, 1, __r); |
} |
void replace(size_t __p, const _CharT* __i, size_t __i_len) { |
replace(__p, 1, __i, __i_len); |
} |
void replace(size_t __p, const _CharT* __c_string) { |
replace(__p, 1, __c_string); |
} |
void replace(size_t __p, const _CharT* __i, const _CharT* __j) { |
replace(__p, 1, __i, __j); |
} |
void replace(size_t __p, const const_iterator& __i, |
const const_iterator& __j) { |
replace(__p, 1, __i, __j); |
} |
void replace(size_t __p, const iterator& __i, |
const iterator& __j) { |
replace(__p, 1, __i, __j); |
} |
// Erase, (position, size) variant. |
void erase(size_t __p, size_t __n) { |
_RopeRep* __result = replace(_M_tree_ptr, __p, __p + __n, 0); |
_S_unref(_M_tree_ptr); |
_M_tree_ptr = __result; |
} |
// Erase, single character |
void erase(size_t __p) { |
erase(__p, __p + 1); |
} |
// Insert, iterator variants. |
iterator insert(const iterator& __p, const rope& __r) |
{ insert(__p.index(), __r); return __p; } |
iterator insert(const iterator& __p, size_t __n, _CharT __c) |
{ insert(__p.index(), __n, __c); return __p; } |
iterator insert(const iterator& __p, _CharT __c) |
{ insert(__p.index(), __c); return __p; } |
iterator insert(const iterator& __p ) |
{ insert(__p.index()); return __p; } |
iterator insert(const iterator& __p, const _CharT* c_string) |
{ insert(__p.index(), c_string); return __p; } |
iterator insert(const iterator& __p, const _CharT* __i, size_t __n) |
{ insert(__p.index(), __i, __n); return __p; } |
iterator insert(const iterator& __p, const _CharT* __i, |
const _CharT* __j) |
{ insert(__p.index(), __i, __j); return __p; } |
iterator insert(const iterator& __p, |
const const_iterator& __i, const const_iterator& __j) |
{ insert(__p.index(), __i, __j); return __p; } |
iterator insert(const iterator& __p, |
const iterator& __i, const iterator& __j) |
{ insert(__p.index(), __i, __j); return __p; } |
// Replace, range variants. |
void replace(const iterator& __p, const iterator& __q, |
const rope& __r) |
{ replace(__p.index(), __q.index() - __p.index(), __r); } |
void replace(const iterator& __p, const iterator& __q, _CharT __c) |
{ replace(__p.index(), __q.index() - __p.index(), __c); } |
void replace(const iterator& __p, const iterator& __q, |
const _CharT* __c_string) |
{ replace(__p.index(), __q.index() - __p.index(), __c_string); } |
void replace(const iterator& __p, const iterator& __q, |
const _CharT* __i, size_t __n) |
{ replace(__p.index(), __q.index() - __p.index(), __i, __n); } |
void replace(const iterator& __p, const iterator& __q, |
const _CharT* __i, const _CharT* __j) |
{ replace(__p.index(), __q.index() - __p.index(), __i, __j); } |
void replace(const iterator& __p, const iterator& __q, |
const const_iterator& __i, const const_iterator& __j) |
{ replace(__p.index(), __q.index() - __p.index(), __i, __j); } |
void replace(const iterator& __p, const iterator& __q, |
const iterator& __i, const iterator& __j) |
{ replace(__p.index(), __q.index() - __p.index(), __i, __j); } |
// Replace, iterator variants. |
void replace(const iterator& __p, const rope& __r) |
{ replace(__p.index(), __r); } |
void replace(const iterator& __p, _CharT __c) |
{ replace(__p.index(), __c); } |
void replace(const iterator& __p, const _CharT* __c_string) |
{ replace(__p.index(), __c_string); } |
void replace(const iterator& __p, const _CharT* __i, size_t __n) |
{ replace(__p.index(), __i, __n); } |
void replace(const iterator& __p, const _CharT* __i, const _CharT* __j) |
{ replace(__p.index(), __i, __j); } |
void replace(const iterator& __p, const_iterator __i, |
const_iterator __j) |
{ replace(__p.index(), __i, __j); } |
void replace(const iterator& __p, iterator __i, iterator __j) |
{ replace(__p.index(), __i, __j); } |
// Iterator and range variants of erase |
iterator erase(const iterator& __p, const iterator& __q) { |
size_t __p_index = __p.index(); |
erase(__p_index, __q.index() - __p_index); |
return iterator(this, __p_index); |
} |
iterator erase(const iterator& __p) { |
size_t __p_index = __p.index(); |
erase(__p_index, 1); |
return iterator(this, __p_index); |
} |
rope substr(size_t __start, size_t __len = 1) const { |
return rope<_CharT,_Alloc>( |
_S_substring(_M_tree_ptr, __start, __start + __len)); |
} |
rope substr(iterator __start, iterator __end) const { |
return rope<_CharT,_Alloc>( |
_S_substring(_M_tree_ptr, __start.index(), __end.index())); |
} |
rope substr(iterator __start) const { |
size_t __pos = __start.index(); |
return rope<_CharT,_Alloc>( |
_S_substring(_M_tree_ptr, __pos, __pos + 1)); |
} |
rope substr(const_iterator __start, const_iterator __end) const { |
// This might eventually take advantage of the cache in the |
// iterator. |
return rope<_CharT,_Alloc>( |
_S_substring(_M_tree_ptr, __start.index(), __end.index())); |
} |
rope<_CharT,_Alloc> substr(const_iterator __start) { |
size_t __pos = __start.index(); |
return rope<_CharT,_Alloc>( |
_S_substring(_M_tree_ptr, __pos, __pos + 1)); |
} |
static const size_type npos; |
size_type find(_CharT __c, size_type __pos = 0) const; |
size_type find(const _CharT* __s, size_type __pos = 0) const { |
size_type __result_pos; |
const_iterator __result = search(const_begin() + __pos, const_end(), |
__s, __s + _S_char_ptr_len(__s)); |
__result_pos = __result.index(); |
# ifndef __STL_OLD_ROPE_SEMANTICS |
if (__result_pos == size()) __result_pos = npos; |
# endif |
return __result_pos; |
} |
iterator mutable_begin() { |
return(iterator(this, 0)); |
} |
iterator mutable_end() { |
return(iterator(this, size())); |
} |
typedef reverse_iterator<iterator> reverse_iterator; |
reverse_iterator mutable_rbegin() { |
return reverse_iterator(mutable_end()); |
} |
reverse_iterator mutable_rend() { |
return reverse_iterator(mutable_begin()); |
} |
reference mutable_reference_at(size_type __pos) { |
return reference(this, __pos); |
} |
# ifdef __STD_STUFF |
reference operator[] (size_type __pos) { |
return _char_ref_proxy(this, __pos); |
} |
reference at(size_type __pos) { |
// if (__pos >= size()) throw out_of_range; // XXX |
return (*this)[__pos]; |
} |
void resize(size_type __n, _CharT __c) {} |
void resize(size_type __n) {} |
void reserve(size_type __res_arg = 0) {} |
size_type capacity() const { |
return max_size(); |
} |
// Stuff below this line is dangerous because it's error prone. |
// I would really like to get rid of it. |
// copy function with funny arg ordering. |
size_type copy(_CharT* __buffer, size_type __n, |
size_type __pos = 0) const { |
return copy(__pos, __n, __buffer); |
} |
iterator end() { return mutable_end(); } |
iterator begin() { return mutable_begin(); } |
reverse_iterator rend() { return mutable_rend(); } |
reverse_iterator rbegin() { return mutable_rbegin(); } |
# else |
const_iterator end() { return const_end(); } |
const_iterator begin() { return const_begin(); } |
const_reverse_iterator rend() { return const_rend(); } |
const_reverse_iterator rbegin() { return const_rbegin(); } |
# endif |
}; |
template <class _CharT, class _Alloc> |
const rope<_CharT, _Alloc>::size_type rope<_CharT, _Alloc>::npos = |
(size_type)(-1); |
template <class _CharT, class _Alloc> |
inline bool operator== (const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return (__x._M_current_pos == __y._M_current_pos && |
__x._M_root == __y._M_root); |
} |
template <class _CharT, class _Alloc> |
inline bool operator< (const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return (__x._M_current_pos < __y._M_current_pos); |
} |
template <class _CharT, class _Alloc> |
inline bool operator!= (const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return !(__x == __y); |
} |
template <class _CharT, class _Alloc> |
inline bool operator> (const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return __y < __x; |
} |
template <class _CharT, class _Alloc> |
inline bool operator<= (const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return !(__y < __x); |
} |
template <class _CharT, class _Alloc> |
inline bool operator>= (const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return !(__x < __y); |
} |
template <class _CharT, class _Alloc> |
inline ptrdiff_t operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x, |
const _Rope_const_iterator<_CharT,_Alloc>& __y) { |
return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; |
} |
template <class _CharT, class _Alloc> |
inline _Rope_const_iterator<_CharT,_Alloc> |
operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n) { |
return _Rope_const_iterator<_CharT,_Alloc>( |
__x._M_root, __x._M_current_pos - __n); |
} |
template <class _CharT, class _Alloc> |
inline _Rope_const_iterator<_CharT,_Alloc> |
operator+(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n) { |
return _Rope_const_iterator<_CharT,_Alloc>( |
__x._M_root, __x._M_current_pos + __n); |
} |
template <class _CharT, class _Alloc> |
inline _Rope_const_iterator<_CharT,_Alloc> |
operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT,_Alloc>& __x) { |
return _Rope_const_iterator<_CharT,_Alloc>( |
__x._M_root, __x._M_current_pos + __n); |
} |
template <class _CharT, class _Alloc> |
inline bool operator== (const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return (__x._M_current_pos == __y._M_current_pos && |
__x._M_root_rope == __y._M_root_rope); |
} |
template <class _CharT, class _Alloc> |
inline bool operator< (const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return (__x._M_current_pos < __y._M_current_pos); |
} |
template <class _CharT, class _Alloc> |
inline bool operator!= (const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return !(__x == __y); |
} |
template <class _CharT, class _Alloc> |
inline bool operator> (const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return __y < __x; |
} |
template <class _CharT, class _Alloc> |
inline bool operator<= (const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return !(__y < __x); |
} |
template <class _CharT, class _Alloc> |
inline bool operator>= (const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return !(__x < __y); |
} |
template <class _CharT, class _Alloc> |
inline ptrdiff_t operator-(const _Rope_iterator<_CharT,_Alloc>& __x, |
const _Rope_iterator<_CharT,_Alloc>& __y) { |
return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; |
} |
template <class _CharT, class _Alloc> |
inline _Rope_iterator<_CharT,_Alloc> |
operator-(const _Rope_iterator<_CharT,_Alloc>& __x, |
ptrdiff_t __n) { |
return _Rope_iterator<_CharT,_Alloc>( |
__x._M_root_rope, __x._M_current_pos - __n); |
} |
template <class _CharT, class _Alloc> |
inline _Rope_iterator<_CharT,_Alloc> |
operator+(const _Rope_iterator<_CharT,_Alloc>& __x, |
ptrdiff_t __n) { |
return _Rope_iterator<_CharT,_Alloc>( |
__x._M_root_rope, __x._M_current_pos + __n); |
} |
template <class _CharT, class _Alloc> |
inline _Rope_iterator<_CharT,_Alloc> |
operator+(ptrdiff_t __n, const _Rope_iterator<_CharT,_Alloc>& __x) { |
return _Rope_iterator<_CharT,_Alloc>( |
__x._M_root_rope, __x._M_current_pos + __n); |
} |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc> |
operator+ (const rope<_CharT,_Alloc>& __left, |
const rope<_CharT,_Alloc>& __right) |
{ |
__stl_assert(__left.get_allocator() == __right.get_allocator()); |
return rope<_CharT,_Alloc>( |
rope<_CharT,_Alloc>::_S_concat(__left._M_tree_ptr, __right._M_tree_ptr)); |
// Inlining this should make it possible to keep __left and |
// __right in registers. |
} |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc>& |
operator+= (rope<_CharT,_Alloc>& __left, |
const rope<_CharT,_Alloc>& __right) |
{ |
__left.append(__right); |
return __left; |
} |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc> |
operator+ (const rope<_CharT,_Alloc>& __left, |
const _CharT* __right) { |
size_t __rlen = rope<_CharT,_Alloc>::_S_char_ptr_len(__right); |
return rope<_CharT,_Alloc>( |
rope<_CharT,_Alloc>::_S_concat_char_iter( |
__left._M_tree_ptr, __right, __rlen)); |
} |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc>& |
operator+= (rope<_CharT,_Alloc>& __left, |
const _CharT* __right) { |
__left.append(__right); |
return __left; |
} |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc> |
operator+ (const rope<_CharT,_Alloc>& __left, _CharT __right) { |
return rope<_CharT,_Alloc>( |
rope<_CharT,_Alloc>::_S_concat_char_iter( |
__left._M_tree_ptr, &__right, 1)); |
} |
template <class _CharT, class _Alloc> |
inline |
rope<_CharT,_Alloc>& |
operator+= (rope<_CharT,_Alloc>& __left, _CharT __right) { |
__left.append(__right); |
return __left; |
} |
template <class _CharT, class _Alloc> |
bool |
operator< (const rope<_CharT,_Alloc>& __left, |
const rope<_CharT,_Alloc>& __right) { |
return __left.compare(__right) < 0; |
} |
template <class _CharT, class _Alloc> |
bool |
operator== (const rope<_CharT,_Alloc>& __left, |
const rope<_CharT,_Alloc>& __right) { |
return __left.compare(__right) == 0; |
} |
template <class _CharT, class _Alloc> |
inline bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, |
const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y) { |
return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); |
} |
template <class _CharT, class _Alloc> |
inline bool |
operator!= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { |
return !(__x == __y); |
} |
template <class _CharT, class _Alloc> |
inline bool |
operator> (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { |
return __y < __x; |
} |
template <class _CharT, class _Alloc> |
inline bool |
operator<= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { |
return !(__y < __x); |
} |
template <class _CharT, class _Alloc> |
inline bool |
operator>= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { |
return !(__x < __y); |
} |
template <class _CharT, class _Alloc> |
inline bool operator!= (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, |
const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y) { |
return !(__x == __y); |
} |
template<class _CharT, class _Traits, class _Alloc> |
basic_ostream<_CharT, _Traits>& operator<< |
(basic_ostream<_CharT, _Traits>& __o, |
const rope<_CharT, _Alloc>& __r); |
typedef rope<char> crope; |
typedef rope<wchar_t> wrope; |
inline crope::reference __mutable_reference_at(crope& __c, size_t __i) |
{ |
return __c.mutable_reference_at(__i); |
} |
inline wrope::reference __mutable_reference_at(wrope& __c, size_t __i) |
{ |
return __c.mutable_reference_at(__i); |
} |
template <class _CharT, class _Alloc> |
inline void swap(rope<_CharT,_Alloc>& __x, rope<_CharT,_Alloc>& __y) { |
__x.swap(__y); |
} |
// Hash functions should probably be revisited later: |
template<> struct hash<crope> |
{ |
size_t operator()(const crope& __str) const |
{ |
size_t __size = __str.size(); |
if (0 == __size) return 0; |
return 13*__str[0] + 5*__str[__size - 1] + __size; |
} |
}; |
template<> struct hash<wrope> |
{ |
size_t operator()(const wrope& __str) const |
{ |
size_t __size = __str.size(); |
if (0 == __size) return 0; |
return 13*__str[0] + 5*__str[__size - 1] + __size; |
} |
}; |
} // namespace std |
# include <ext/ropeimpl.h> |
# endif /* __SGI_STL_INTERNAL_ROPE_H */ |
// Local Variables: |
// mode:C++ |
// End: |
/contrib/media/updf/include/ext/tree |
---|
0,0 → 1,23 |
/* |
* Copyright (c) 1997 |
* Silicon Graphics Computer Systems, Inc. |
* |
* Permission to use, copy, modify, distribute and sell this software |
* and its documentation for any purpose is hereby granted without fee, |
* provided that the above copyright notice appear in all copies and |
* that both that copyright notice and this permission notice appear |
* in supporting documentation. Silicon Graphics makes no |
* representations about the suitability of this software for any |
* purpose. It is provided "as is" without express or implied warranty. |
* |
*/ |
#ifndef _CPP_EXT_TREE |
#define _CPP_EXT_TREE 1 |
#include <bits/stl_tree.h> |
#endif |
// Local Variables: |
// mode:C++ |
// End: |