1365 lines
43 KiB
Plaintext
1365 lines
43 KiB
Plaintext
|
///////////////////////////////////////////////////////////////////////////
|
||
|
// FILE: deque (Definition of std::deque)
|
||
|
//
|
||
|
// =========================================================================
|
||
|
//
|
||
|
// Open Watcom Project
|
||
|
//
|
||
|
// Copyright (c) 2004-2010 The Open Watcom Contributors. All Rights Reserved.
|
||
|
//
|
||
|
// This file is automatically generated. Do not edit directly.
|
||
|
//
|
||
|
// =========================================================================
|
||
|
//
|
||
|
// Description: This header is part of the C++ standard library. It defines
|
||
|
// a double ended queue template that provides random access
|
||
|
// to its elements yet amortized O(1) time push/pop operations
|
||
|
// on *both* ends.
|
||
|
// References to objects are *not* invalidated with an insert
|
||
|
// operation.
|
||
|
// Extention: extra template parameter PageSize allow
|
||
|
// number of objects per block of allocations to be adjusted
|
||
|
// must be power of 2 because of assumptions in math in operations
|
||
|
///////////////////////////////////////////////////////////////////////////
|
||
|
#ifndef _DEQUE_INCLUDED
|
||
|
#define _DEQUE_INCLUDED
|
||
|
|
||
|
#ifndef _ENABLE_AUTODEPEND
|
||
|
#pragma read_only_file;
|
||
|
#endif
|
||
|
|
||
|
#ifndef __cplusplus
|
||
|
#error This header file requires C++
|
||
|
#endif
|
||
|
|
||
|
#ifndef _ITERATOR_INCLUDED
|
||
|
#include <iterator>
|
||
|
#endif
|
||
|
|
||
|
#ifndef _LIMITS_INCLUDED
|
||
|
#include <limits>
|
||
|
#endif
|
||
|
|
||
|
#ifndef _MEMORY_INCLUDED
|
||
|
#include <memory>
|
||
|
#endif
|
||
|
|
||
|
#ifndef _STDEXCEPT_INCLUDED
|
||
|
#include <stdexcep>
|
||
|
#endif
|
||
|
|
||
|
#ifndef _TYPE_TRAITS_INCLUDED
|
||
|
#include <type_tra>
|
||
|
#endif
|
||
|
|
||
|
namespace std {
|
||
|
|
||
|
template< class Type, class Allocator = allocator< Type >,
|
||
|
int PageSize = 32 > //to do, assert/force power of 2
|
||
|
class deque {
|
||
|
public:
|
||
|
typedef typename Allocator::reference reference;
|
||
|
typedef typename Allocator::const_reference const_reference;
|
||
|
typedef typename Allocator::size_type size_type;
|
||
|
typedef typename Allocator::difference_type difference_type;
|
||
|
typedef Type value_type;
|
||
|
typedef Allocator allocator_type;
|
||
|
typedef typename Allocator::pointer pointer;
|
||
|
typedef typename Allocator::const_pointer const_pointer;
|
||
|
|
||
|
// Class iterator
|
||
|
// --------------
|
||
|
class iterator :
|
||
|
public std::iterator< random_access_iterator_tag, Type > {
|
||
|
friend class deque;
|
||
|
public:
|
||
|
iterator( deque *d, deque::size_type n ) :
|
||
|
dp( d ), i( n ) { }
|
||
|
|
||
|
iterator( ) { }
|
||
|
|
||
|
value_type &operator*( );
|
||
|
value_type *operator->( );
|
||
|
|
||
|
iterator &operator++( );
|
||
|
iterator operator++( int );
|
||
|
iterator &operator--( );
|
||
|
iterator operator--( int );
|
||
|
|
||
|
friend bool operator==(iterator lhs, iterator rhs)
|
||
|
{ return( lhs.dp == rhs.dp && lhs.i == rhs.i ); }
|
||
|
friend bool operator< (iterator lhs, iterator rhs)
|
||
|
{ return( lhs.dp->dist_from_first(lhs.i) < rhs.dp->dist_from_first(rhs.i) ); }
|
||
|
friend bool operator!=(iterator lhs, iterator rhs)
|
||
|
{ return( !( lhs == rhs ) ); }
|
||
|
friend bool operator>=(iterator lhs, iterator rhs)
|
||
|
{ return( !( lhs < rhs ) ); }
|
||
|
friend bool operator> (iterator lhs, iterator rhs)
|
||
|
{ return( rhs < lhs ); }
|
||
|
friend bool operator<=(iterator lhs, iterator rhs)
|
||
|
{ return( !( lhs > rhs ) ); }
|
||
|
|
||
|
iterator &operator+=( difference_type n );
|
||
|
iterator &operator-=( difference_type n );
|
||
|
friend iterator operator+( iterator it, difference_type n )
|
||
|
{ it += n; return( it ); }
|
||
|
friend iterator operator+( difference_type n, iterator it )
|
||
|
{ it += n; return( it ); }
|
||
|
friend iterator operator-( iterator it, difference_type n )
|
||
|
{ it -= n; return( it ); }
|
||
|
|
||
|
private:
|
||
|
deque *dp;
|
||
|
// index is combined cbuf and page index to save memory
|
||
|
deque::size_type i;
|
||
|
};
|
||
|
|
||
|
// Class const_iterator
|
||
|
// --------------------
|
||
|
class const_iterator :
|
||
|
public std::iterator< random_access_iterator_tag, const Type > {
|
||
|
public:
|
||
|
const_iterator( const deque *p, deque::size_type n ) :
|
||
|
dp( p ), i( n ) { }
|
||
|
|
||
|
const_iterator( ) { }
|
||
|
|
||
|
value_type &operator*( );
|
||
|
value_type *operator->( );
|
||
|
|
||
|
const_iterator &operator++( );
|
||
|
const_iterator operator++( int );
|
||
|
const_iterator &operator--( );
|
||
|
const_iterator operator--( int );
|
||
|
|
||
|
friend bool operator==(const_iterator lhs, const_iterator rhs)
|
||
|
{ return( lhs.dp == rhs.dp && lhs.i == rhs.i ); }
|
||
|
friend bool operator< (const_iterator lhs, const_iterator rhs)
|
||
|
{ return( lhs.dp->dist_from_first(lhs.i) < rhs.dp->dist_from_first(rhs.i) ); }
|
||
|
friend bool operator!=(const_iterator lhs, const_iterator rhs)
|
||
|
{ return( !( lhs == rhs ) ); }
|
||
|
friend bool operator>=(const_iterator lhs, const_iterator rhs)
|
||
|
{ return( !( lhs < rhs ) ); }
|
||
|
friend bool operator> (const_iterator lhs, const_iterator rhs)
|
||
|
{ return( rhs < lhs ); }
|
||
|
friend bool operator<=(const_iterator lhs, const_iterator rhs)
|
||
|
{ return( !( lhs > rhs ) ); }
|
||
|
|
||
|
const_iterator &operator+=( difference_type n );
|
||
|
const_iterator &operator-=( difference_type n );
|
||
|
friend const_iterator operator+( const_iterator it, difference_type n )
|
||
|
{ it += n; return( it ); }
|
||
|
friend const_iterator operator+( difference_type n, const_iterator it )
|
||
|
{ it += n; return( it ); }
|
||
|
friend const_iterator operator-( const_iterator it, difference_type n )
|
||
|
{ it -= n; return( it ); }
|
||
|
|
||
|
private:
|
||
|
const deque *dp;
|
||
|
deque::size_type i;
|
||
|
};
|
||
|
friend class iterator;
|
||
|
friend class const_iterator;
|
||
|
|
||
|
typedef std::reverse_iterator< iterator > reverse_iterator;
|
||
|
typedef std::reverse_iterator< const_iterator > const_reverse_iterator;
|
||
|
|
||
|
explicit deque( const Allocator & = Allocator( ) );
|
||
|
explicit deque( size_type n, const Type &value = Type( ), const Allocator & = Allocator( ) );
|
||
|
// copy ctor should probably be templated so it is possible to construct a
|
||
|
// deque from one with a different PageSize.
|
||
|
deque( const deque &other );
|
||
|
~deque( );
|
||
|
deque &operator=( const deque &other );
|
||
|
void assign( size_type n, const Type &value );
|
||
|
allocator_type get_allocator( ) const;
|
||
|
|
||
|
iterator begin( );
|
||
|
const_iterator begin( ) const;
|
||
|
iterator end( );
|
||
|
const_iterator end( ) const;
|
||
|
reverse_iterator rbegin( );
|
||
|
const_reverse_iterator rbegin( ) const;
|
||
|
reverse_iterator rend( );
|
||
|
const_reverse_iterator rend( ) const;
|
||
|
|
||
|
size_type size( ) const;
|
||
|
size_type max_size( ) const;
|
||
|
void resize( size_type n, Type c = Type( ) );
|
||
|
size_type capacity( ) const; // Not required by the standard.
|
||
|
bool empty( ) const;
|
||
|
void reserve( size_type n ); // Not required by the standard.
|
||
|
|
||
|
reference operator[]( size_type n );
|
||
|
const_reference operator[]( size_type n ) const;
|
||
|
reference at( size_type n );
|
||
|
const_reference at( size_type n ) const;
|
||
|
reference front( );
|
||
|
const_reference front( ) const;
|
||
|
reference back( );
|
||
|
const_reference back( ) const;
|
||
|
|
||
|
void push_front( const Type &item );
|
||
|
void push_back( const Type &item );
|
||
|
void pop_front( );
|
||
|
void pop_back( );
|
||
|
iterator insert( iterator position, const Type &x );
|
||
|
void insert( iterator position, size_type n, const Type &x );
|
||
|
template< class InputIt >
|
||
|
void insert( iterator pos, InputIt first, InputIt last )
|
||
|
{
|
||
|
helper_insert( pos, first, last, tr1::is_integral<InputIt>::type() );
|
||
|
}
|
||
|
iterator erase( iterator position );
|
||
|
iterator erase( iterator first, iterator last );
|
||
|
void swap( deque &x );
|
||
|
void clear( );
|
||
|
|
||
|
bool _Sane( ) const; // Check invariants.
|
||
|
|
||
|
private:
|
||
|
// 1. cbuf = circular buffer of pointers, pointing to pages of objects
|
||
|
// 2. cbuf has size cbuf_length.
|
||
|
// 3. cbuf never shrinks
|
||
|
// 4. cbuf_length is a power of two (bitwise and with (cbuflength - 1) to wrap)
|
||
|
// 5. cbuf allocated with rebound cmem
|
||
|
// 6. get_ci(tail) indexes the tail page, grows positive
|
||
|
// 7. get_ci(head) indexes the head page, grows negative
|
||
|
// 8. when cbuf empty head == wrap(tail+1)
|
||
|
// 9. always at least one empty element empty (for end iterator to point to)
|
||
|
// 9. buffer reallocated when an insert would cause chead == ctail,
|
||
|
// or the last element would be used up, but not
|
||
|
// first insert after container empty (see is_back/front_full() )
|
||
|
//
|
||
|
Allocator pmem; // (de)alloc pages of contained types
|
||
|
typedef Allocator::rebind<pointer>::other cbuf_allocator_t;
|
||
|
cbuf_allocator_t cmem; // (de)alloc circular buffer of pointers
|
||
|
typedef cbuf_allocator_t::pointer cbuf_t;
|
||
|
cbuf_t cbuf; // Pointer to start of circular buffer space.
|
||
|
size_type cbuf_length; // total circular buffer slots
|
||
|
size_type deq_used; // Number of buffer slots in use by objects.
|
||
|
size_type head; // cbuf and page index of first element
|
||
|
size_type tail; // cbuf and page index of last element
|
||
|
|
||
|
bool is_back_full( size_type n = 1 );
|
||
|
bool is_front_full( size_type n = 1 );
|
||
|
void grow_cbuf( size_type );
|
||
|
void new_page( size_type ci ); // create/move page at ci
|
||
|
size_type dist_from_first( size_type i ) const; // i is compressed cbuf and page index
|
||
|
size_type dist_from_last( size_type i ) const;
|
||
|
// get cbuf or page indexes from combined index
|
||
|
// if pagesize is power of 2 this will generate simple bit shift/mask
|
||
|
inline static size_type get_ci( size_type i ) { return( i / PageSize ); }
|
||
|
inline static size_type get_pi( size_type i ) { return( i % PageSize ); }
|
||
|
// pagesize and cbuf_length must be power of 2 for this to work
|
||
|
size_type wrap( size_type i ) const { return( i & ( cbuf_length * PageSize - 1 ) ); }
|
||
|
|
||
|
// used by various insert functions
|
||
|
// push [first, last) starting after tail
|
||
|
// recommend allocate sufficient space first
|
||
|
// exception saftey weak, used to build the strong functions
|
||
|
template< class it >
|
||
|
void push_back_many( it first, it last )
|
||
|
{
|
||
|
while( first != last ){
|
||
|
push_back( *f );
|
||
|
++first;
|
||
|
}
|
||
|
}
|
||
|
|
||
|
// member templates - to be moved outside class when compiler supports this
|
||
|
public:
|
||
|
// overloaded helpers get called by insert(many) depending on iterator type
|
||
|
// int type
|
||
|
template< class InputIt1, class InputIt2 >
|
||
|
void insert_helper( iterator pos, InputIt1 first, InputIt2 last, tr1::true_type )
|
||
|
{
|
||
|
insert( pos, static_cast<size_type>(first), static_cast<value_type>(last) );
|
||
|
}
|
||
|
// non int type
|
||
|
// to do: specialise for iterator of type input it (make temp copy of elements
|
||
|
// in order to count them)
|
||
|
template< class It1, class It2 >
|
||
|
void insert_helper( iterator pos, It1 first, It2 last, tr1::false_type )
|
||
|
{/*
|
||
|
// if at begin
|
||
|
|
||
|
// if at end
|
||
|
|
||
|
// if nearer end
|
||
|
// to do - test
|
||
|
|
||
|
// count elements
|
||
|
size_type d = last-first;//= distance( first, last );
|
||
|
// resize cbuf
|
||
|
if( is_back_full(d) ){
|
||
|
size_type n = cbuf_length;
|
||
|
size_type t = cbuf_length + ( d / PageSize ) + 1;
|
||
|
while( n < t ) n *= 2;
|
||
|
grow_cbuf( n );
|
||
|
}
|
||
|
// create temp
|
||
|
// (exception will automatically clean up temp giving strong safety)
|
||
|
deque temp;
|
||
|
// calculate temp starting pos
|
||
|
size_type tmp_fst = 0;
|
||
|
if( distance_to_first( pos.i ) < PageSize ) {
|
||
|
|
||
|
// copy from start of page to pos
|
||
|
// copy from first to last
|
||
|
// copy pos to end
|
||
|
// delete old pages
|
||
|
// move new pages
|
||
|
// update indexes
|
||
|
// temp will clean up automatically
|
||
|
|
||
|
|
||
|
|
||
|
// if nearer begin
|
||
|
*/
|
||
|
}
|
||
|
};
|
||
|
|
||
|
// ===================================
|
||
|
// Member functions of deque::iterator
|
||
|
// ===================================
|
||
|
|
||
|
// operator*( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::iterator::value_type&
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator*( )
|
||
|
{
|
||
|
return( dp->cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
|
||
|
// operator->( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::iterator::value_type*
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator->( )
|
||
|
{
|
||
|
return( &dp->cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
|
||
|
// operator++( )
|
||
|
// *************
|
||
|
// ++pre
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator &
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator++( )
|
||
|
{
|
||
|
i = dp->wrap( i + 1 );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// operator++( int )
|
||
|
// *****************
|
||
|
// post++
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator++( int )
|
||
|
{
|
||
|
iterator ret_value( *this );
|
||
|
i = dp->wrap( i + 1 );
|
||
|
return( ret_value );
|
||
|
}
|
||
|
|
||
|
// operator--( )
|
||
|
// *************
|
||
|
// --pre
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator &
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator--( )
|
||
|
{
|
||
|
i = dp->wrap( i - 1 );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// operator--( int )
|
||
|
// *****************
|
||
|
// post--
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator--( int )
|
||
|
{
|
||
|
iterator ret_value( *this );
|
||
|
i = dp->wrap( i - 1 );
|
||
|
return( ret_value );
|
||
|
}
|
||
|
|
||
|
// operator+=( difference_type )
|
||
|
// *****************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator &
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator+=( difference_type n )
|
||
|
{
|
||
|
i = dp->wrap( i + n );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// operator-=( difference_type )
|
||
|
// *****************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::iterator &
|
||
|
deque< Type, Allocator, PageSize >::iterator::operator-=( difference_type n )
|
||
|
{
|
||
|
i = dp->wrap( i - n );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// =========================================
|
||
|
// Member functions of deque::const_iterator
|
||
|
// =========================================
|
||
|
|
||
|
// operator*( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator::value_type &
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator*( )
|
||
|
{
|
||
|
return( dp->cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
|
||
|
// operator->( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator::value_type const*
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator->( )
|
||
|
{
|
||
|
return( &dp->cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
// operator++( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator &
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator++( )
|
||
|
{
|
||
|
i = dp->wrap( i + 1 );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// operator++( int )
|
||
|
// *****************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator++( int )
|
||
|
{
|
||
|
const_iterator ret_value( *this );
|
||
|
i = dp->wrap( i + 1 );
|
||
|
return( ret_value );
|
||
|
}
|
||
|
|
||
|
// operator--( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator &
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator--( )
|
||
|
{
|
||
|
i = dp->wrap( i - 1 );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// operator--( int )
|
||
|
// *****************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator--( int )
|
||
|
{
|
||
|
const_iterator ret_value( *this );
|
||
|
i = dp->wrap( i + 1 );
|
||
|
return( ret_value );
|
||
|
}
|
||
|
|
||
|
// operator+=( difference_type )
|
||
|
// *****************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator &
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator+=( difference_type n )
|
||
|
{
|
||
|
i = dp->wrap( i + n );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// operator-=( difference_type )
|
||
|
// *****************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator &
|
||
|
deque< Type, Allocator, PageSize >::const_iterator::operator-=( difference_type n )
|
||
|
{
|
||
|
i = dp->wrap( i - n );
|
||
|
return( *this );
|
||
|
}
|
||
|
|
||
|
// =========================
|
||
|
// Member functions of deque
|
||
|
// =========================
|
||
|
|
||
|
// dist_from_first( )
|
||
|
// *************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::size_type
|
||
|
deque< Type, Allocator, PageSize >::dist_from_first( size_type i ) const
|
||
|
{
|
||
|
return( wrap(i - head) );
|
||
|
}
|
||
|
|
||
|
// dist_from_last( )
|
||
|
// *************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::size_type
|
||
|
deque< Type, Allocator, PageSize >::dist_from_last( size_type i ) const
|
||
|
{
|
||
|
return( wrap(i - tail) );
|
||
|
}
|
||
|
|
||
|
// is_front_full( )
|
||
|
// *************************
|
||
|
// check push front wont overflow
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
bool deque< Type, Allocator, PageSize >::is_front_full( size_type n )
|
||
|
{
|
||
|
return( deq_used +n >= cbuf_length * PageSize || // only n elements left
|
||
|
(// or must not overflow chead into same page as ctail
|
||
|
get_ci(tail) != get_ci(head) &&
|
||
|
get_ci( wrap(head - n) ) == get_ci(tail)
|
||
|
) );
|
||
|
}
|
||
|
|
||
|
// is_back_full( )
|
||
|
// *************************
|
||
|
// check push back wont overflow
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
bool deque< Type, Allocator, PageSize >::is_back_full( size_type n )
|
||
|
{
|
||
|
return( deq_used + n >= cbuf_length * PageSize || //only n elements left
|
||
|
(// or must not overflow ctail into same page as chead
|
||
|
get_ci(tail) != get_ci(head) &&
|
||
|
get_ci( wrap( tail + n ) ) == get_ci(head)
|
||
|
) );
|
||
|
}
|
||
|
|
||
|
// grow_cbuf( )
|
||
|
// *************************
|
||
|
// allocate bigger circular buffer (must be power of 2) and move into place
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::grow_cbuf( size_type new_length )
|
||
|
{
|
||
|
//cout<<"grow_cbuf"<<"\n";
|
||
|
// new length must be power of 2 and bigger than cbuf_length
|
||
|
cbuf_t result = cmem.allocate( new_length );
|
||
|
size_type d, s;
|
||
|
|
||
|
try{
|
||
|
// copy current contents to start of new buffer
|
||
|
for( d = 0, s = get_ci(head); d < cbuf_length; ++d ){
|
||
|
result[d] = cbuf[s];
|
||
|
s = (s+1) & (cbuf_length - 1); // length always power of 2
|
||
|
}
|
||
|
// initialise new elements to point to null
|
||
|
for( ; d < new_length; ++d ){
|
||
|
result[d] = 0;
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
cmem.deallocate( result, new_length );
|
||
|
throw;
|
||
|
}
|
||
|
|
||
|
// remove original and update outputs only if allocation successful.
|
||
|
cmem.deallocate( cbuf, cbuf_length );
|
||
|
cbuf = result;
|
||
|
cbuf_length = new_length;
|
||
|
head = get_pi(head); // new page 0 but same index into page
|
||
|
tail = wrap( head + deq_used - 1 );
|
||
|
}
|
||
|
|
||
|
// new_page( ci )
|
||
|
// *************************
|
||
|
// put a new/unused page at circular buffer location ci
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::new_page( size_type ci )
|
||
|
{
|
||
|
// todo: look for unused page in some likely locations and move
|
||
|
// rather than allocate to save a bit of allocating in likely scenarios
|
||
|
pointer page = pmem.allocate( PageSize );
|
||
|
cbuf[ci] = page;
|
||
|
}
|
||
|
|
||
|
|
||
|
// deque( const Allocator & )
|
||
|
// **************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
deque< Type, Allocator, PageSize >::deque( const Allocator &a ) : pmem( a )//, cmem( a ) //bug?
|
||
|
{
|
||
|
cbuf = cmem.allocate( 2 );
|
||
|
cbuf[0] = 0;
|
||
|
cbuf[1] = 0;
|
||
|
cbuf_length = 2;
|
||
|
deq_used = 0;
|
||
|
head = 1;
|
||
|
tail = 0;
|
||
|
}
|
||
|
|
||
|
// deque( size_type, const Type &, const Allocator & )
|
||
|
// ***************************************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
deque< Type, Allocator, PageSize >::deque(
|
||
|
size_type n,
|
||
|
const Type &value,
|
||
|
const Allocator & ) //: cmem( a )//,pmem( a ) //bug?
|
||
|
{
|
||
|
// find suitable buffer size
|
||
|
cbuf_length = 2;
|
||
|
while( cbuf_length*PageSize <= n ) cbuf_length *= 2;
|
||
|
|
||
|
// allocate buf and pages
|
||
|
cbuf = cmem.allocate( cbuf_length );
|
||
|
size_type i;
|
||
|
try {
|
||
|
for( i = 0; i < cbuf_length; i++ ){
|
||
|
cbuf[i] = pmem.allocate( PageSize );
|
||
|
}
|
||
|
}catch( ... ) {
|
||
|
while( i ){
|
||
|
i--;
|
||
|
pmem.deallocate( cbuf[i], PageSize );
|
||
|
}
|
||
|
cmem.deallocate( cbuf, cbuf_length );
|
||
|
throw;
|
||
|
}
|
||
|
// fill pages
|
||
|
try{
|
||
|
for( i = 0; i < n; i++ ){
|
||
|
pmem.construct( &cbuf[get_ci(i)][get_pi(i)], value );
|
||
|
}
|
||
|
}catch(...){
|
||
|
while( i ){
|
||
|
i--;
|
||
|
pmem.destroy( &cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
for( i = 0; i < cbuf_length; i++ ){
|
||
|
pmem.deallocate( cbuf[i], PageSize );
|
||
|
}
|
||
|
cmem.deallocate( cbuf, cbuf_length );
|
||
|
}
|
||
|
// set ptrs
|
||
|
deq_used = n;
|
||
|
head = 0;
|
||
|
tail = n - 1;
|
||
|
}
|
||
|
|
||
|
// deque( const deque & )
|
||
|
// ************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
deque< Type, Allocator, PageSize >::deque( const deque &other )
|
||
|
: cmem( other.cmem ), pmem( other.pmem )
|
||
|
{
|
||
|
cbuf = cmem.allocate( other.cbuf_length );
|
||
|
cbuf_length = other.cbuf_length;
|
||
|
size_type i;
|
||
|
head = 0;
|
||
|
tail = 0; // force alloc on first copy
|
||
|
size_type s = other.head;
|
||
|
try{
|
||
|
i = 0; //count page allocs
|
||
|
while( tail < other.deq_used ){
|
||
|
if( get_pi(tail) == 0 ){
|
||
|
cbuf[ get_ci(tail) ] = pmem.allocate( PageSize );
|
||
|
i++;
|
||
|
}
|
||
|
|
||
|
pmem.construct( &cbuf[get_ci(tail)][get_pi(tail)], other.cbuf[get_ci(s)][get_pi(s)] );
|
||
|
s = wrap(s+1);
|
||
|
tail++;
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
// unwind constructions
|
||
|
while( tail ){
|
||
|
--tail;
|
||
|
pmem.destroy( &cbuf[get_ci(tail)][get_pi(tail)] );
|
||
|
}
|
||
|
// unwind page allocs
|
||
|
while( i ){
|
||
|
--i;
|
||
|
pmem.deallocate( cbuf[i], PageSize );
|
||
|
}
|
||
|
cmem.deallocate( cbuf, cbuf_length );
|
||
|
}
|
||
|
// set unused buf pages pointers to null
|
||
|
while( i < cbuf_length){
|
||
|
cbuf[i++] = 0;
|
||
|
}
|
||
|
tail = wrap(tail - 1);
|
||
|
deq_used = other.deq_used;
|
||
|
}
|
||
|
|
||
|
// ~deque( )
|
||
|
// **********
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
deque< Type, Allocator, PageSize >::~deque( )
|
||
|
{
|
||
|
size_type i;
|
||
|
// Destroy objects actually in use
|
||
|
for( i = 0; i < deq_used; i++ ){
|
||
|
pmem.destroy( &cbuf[get_ci(head)][get_pi(head)] );
|
||
|
head = wrap( head + 1 );
|
||
|
}
|
||
|
// delete pages
|
||
|
for( i = 0; i < cbuf_length; i++ ){
|
||
|
if( cbuf[i] ) pmem.deallocate( cbuf[i], PageSize );
|
||
|
}
|
||
|
// delete buffer
|
||
|
cmem.deallocate( cbuf, cbuf_length );
|
||
|
}
|
||
|
|
||
|
// clear( )
|
||
|
// ********
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::clear( )
|
||
|
{
|
||
|
size_type i;
|
||
|
// Destroy objects actually in use
|
||
|
for( i = 0; i < deq_used; i++ ){
|
||
|
pmem.destroy( &cbuf[get_ci(head)][get_pi(head)] );
|
||
|
head = wrap( head + 1 );
|
||
|
}
|
||
|
// head now == tail+1
|
||
|
deq_used = 0;
|
||
|
|
||
|
// but don't delete any pages or buffers ?
|
||
|
// is this good behaviour or should we dealloc too?
|
||
|
}
|
||
|
|
||
|
|
||
|
// begin( )
|
||
|
// ********
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::iterator
|
||
|
deque< Type, Allocator, PageSize >::begin( )
|
||
|
{
|
||
|
return( iterator( this, head ) );
|
||
|
}
|
||
|
|
||
|
// begin( ) const
|
||
|
// **************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator
|
||
|
deque< Type, Allocator, PageSize >::begin( ) const
|
||
|
{
|
||
|
return( const_iterator( this, head ) );
|
||
|
}
|
||
|
|
||
|
// end( )
|
||
|
// ******
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::iterator
|
||
|
deque< Type, Allocator, PageSize >::end( )
|
||
|
{
|
||
|
return( iterator( this, wrap( tail + 1 ) ) );
|
||
|
}
|
||
|
|
||
|
// end( ) const
|
||
|
// ************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_iterator
|
||
|
deque< Type, Allocator, PageSize >::end( ) const
|
||
|
{
|
||
|
return( const_iterator( this, wrap( tail + 1 ) ) );
|
||
|
}
|
||
|
|
||
|
// rbegin( )
|
||
|
// *********
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::reverse_iterator
|
||
|
deque< Type, Allocator, PageSize >::rbegin( )
|
||
|
{
|
||
|
return( reverse_iterator( iterator( this, tail ) ) );
|
||
|
}
|
||
|
|
||
|
// rbegin( ) const
|
||
|
// ***************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_reverse_iterator
|
||
|
deque< Type, Allocator, PageSize >::rbegin( ) const
|
||
|
{
|
||
|
return( const_reverse_iterator( const_iterator( this, tail ) ) );
|
||
|
}
|
||
|
|
||
|
// rend( )
|
||
|
// *******
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::reverse_iterator
|
||
|
deque< Type, Allocator, PageSize >::rend( )
|
||
|
{
|
||
|
return( reverse_iterator( iterator( this, wrap(head-1) ) ) );
|
||
|
}
|
||
|
|
||
|
// rend( ) const
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_reverse_iterator
|
||
|
deque< Type, Allocator, PageSize >::rend( ) const
|
||
|
{
|
||
|
return( const_reverse_iterator( const_iterator( this, wrap(head-1) ) ) );
|
||
|
}
|
||
|
|
||
|
// size( ) const
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize>::size_type
|
||
|
deque< Type, Allocator, PageSize >::size( ) const
|
||
|
{
|
||
|
return( deq_used );
|
||
|
}
|
||
|
|
||
|
// max_size( ) const
|
||
|
// *****************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::size_type
|
||
|
deque< Type, Allocator, PageSize >::max_size( ) const
|
||
|
{
|
||
|
return( std::numeric_limits< size_type >::max( ) / sizeof( Type ) );
|
||
|
}
|
||
|
|
||
|
// capacity( ) const
|
||
|
// *****************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::size_type
|
||
|
deque< Type, Allocator, PageSize >::capacity( ) const
|
||
|
{
|
||
|
return( cbuf_length * PageSize );
|
||
|
}
|
||
|
|
||
|
// empty( ) const
|
||
|
// **************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
bool deque< Type, Allocator, PageSize >::empty( ) const
|
||
|
{
|
||
|
return( deq_used == 0 );
|
||
|
}
|
||
|
|
||
|
// reserve( size_type )
|
||
|
// ********************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::reserve( size_type new_capacity )
|
||
|
{
|
||
|
// find new cbuf size power of 2 at least size requested
|
||
|
size_type temp = (new_capacity + PageSize - 1 ) / PageSize;
|
||
|
size_type new_cbuf_len = cbuf_length;
|
||
|
while( new_cbuf_len < temp ) new_cbuf_len *= 2;
|
||
|
|
||
|
if( new_cbuf_len <= cbuf_length ) return; // we currently don't do strinking
|
||
|
|
||
|
if( new_cbuf_len * PageSize > max_size( ) )
|
||
|
throw length_error( "deque::reserve" );
|
||
|
|
||
|
grow_cbuf( new_cbuf_len );
|
||
|
|
||
|
// reserve all the pages as well
|
||
|
for( size_type i = 0; i < cbuf_length; i++ ){
|
||
|
if( !cbuf[i] ) cbuf[i] = pmem.allocate( PageSize );
|
||
|
}
|
||
|
}
|
||
|
|
||
|
// operator[]( size_type )
|
||
|
// ***********************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::reference
|
||
|
deque< Type, Allocator, PageSize >::operator[]( size_type n )
|
||
|
{
|
||
|
size_type i = wrap( head + n );
|
||
|
return( cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
|
||
|
// operator[]( size_type ) const
|
||
|
// *****************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator,PageSize >::const_reference
|
||
|
deque< Type, Allocator, PageSize >::operator[]( size_type n ) const
|
||
|
{
|
||
|
return( const_cast<deque*>(this)->operator[](n) );
|
||
|
}
|
||
|
|
||
|
// at( size_type )
|
||
|
// ***************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::reference
|
||
|
deque< Type, Allocator, PageSize >::at( size_type n )
|
||
|
{
|
||
|
if( n >= deq_used )
|
||
|
throw out_of_range( "deque::at" );
|
||
|
return( ( *this )[n] );
|
||
|
}
|
||
|
|
||
|
// at( size_type ) const
|
||
|
// *********************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::const_reference
|
||
|
deque< Type, Allocator, PageSize >::at( size_type n ) const
|
||
|
{
|
||
|
return( const_cast<deque*>(this)->at(n) );
|
||
|
}
|
||
|
|
||
|
// front( )
|
||
|
// ********
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::reference
|
||
|
deque< Type, Allocator, PageSize >::front( )
|
||
|
{
|
||
|
return( cbuf[get_ci(head)][get_pi(head)] );
|
||
|
}
|
||
|
|
||
|
// front( ) const
|
||
|
// **************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_reference
|
||
|
deque< Type, Allocator, PageSize >::front( ) const
|
||
|
{
|
||
|
return( cbuf[get_ci(head)][get_pi(head)] );
|
||
|
}
|
||
|
|
||
|
// back( )
|
||
|
// *******
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::reference
|
||
|
deque< Type, Allocator, PageSize >::back( )
|
||
|
{
|
||
|
return( cbuf[get_ci(tail)][get_pi(tail)] );
|
||
|
}
|
||
|
|
||
|
// back( ) const
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
typename deque< Type, Allocator, PageSize >::const_reference
|
||
|
deque< Type, Allocator, PageSize >::back( ) const
|
||
|
{
|
||
|
return( cbuf[get_ci(tail)][get_pi(tail)] );
|
||
|
}
|
||
|
|
||
|
// push_front( )
|
||
|
// *************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::push_front( const Type &item )
|
||
|
{
|
||
|
if( is_front_full() ) grow_cbuf( cbuf_length * 2 );
|
||
|
|
||
|
size_type temp_ci, temp_i; // For exception safety
|
||
|
|
||
|
temp_i = wrap( head - 1 );
|
||
|
temp_ci = get_ci(temp_i);
|
||
|
|
||
|
if( !cbuf[temp_ci] ) new_page( temp_ci );
|
||
|
|
||
|
// attempt copy of item
|
||
|
new ( static_cast<void *>( &cbuf[temp_ci][get_pi(temp_i)] ) ) Type( item );
|
||
|
|
||
|
// if success fix up container members
|
||
|
head = temp_i;
|
||
|
++deq_used;
|
||
|
}
|
||
|
|
||
|
// push_back( )
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::push_back( const Type &item )
|
||
|
{
|
||
|
if( is_back_full() ) grow_cbuf( cbuf_length * 2 );
|
||
|
|
||
|
size_type temp_ci, temp_i; // For exception safety
|
||
|
|
||
|
temp_i = wrap( tail + 1 );
|
||
|
temp_ci = get_ci(temp_i);
|
||
|
|
||
|
if( !cbuf[temp_ci] ) new_page( temp_ci );
|
||
|
|
||
|
// attempt copy of item
|
||
|
new ( static_cast<void *>( &cbuf[temp_ci][get_pi(temp_i)] ) ) Type( item );
|
||
|
|
||
|
// if success fix up container members
|
||
|
tail = temp_i;
|
||
|
++deq_used;
|
||
|
}
|
||
|
|
||
|
// pop_front( )
|
||
|
// ************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
void deque< Type, Allocator, PageSize >::pop_front( )
|
||
|
{
|
||
|
pmem.destroy( & cbuf[get_ci(head)][get_pi(head)] );
|
||
|
head = wrap( head + 1 );
|
||
|
--deq_used;
|
||
|
}
|
||
|
|
||
|
// pop_back( )
|
||
|
// ***********
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
void deque< Type, Allocator, PageSize >::pop_back( )
|
||
|
{
|
||
|
pmem.destroy( & cbuf[get_ci(tail)][get_pi(tail)] );
|
||
|
tail = wrap( tail - 1 );
|
||
|
--deq_used;
|
||
|
}
|
||
|
|
||
|
// insert( iterator, type )
|
||
|
// ************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator
|
||
|
deque< Type, Allocator, PageSize >::insert( iterator it, const Type &x )
|
||
|
{
|
||
|
// check if at first or last element
|
||
|
if( it == begin() ){
|
||
|
push_front( x );
|
||
|
return( begin() );
|
||
|
}else if( it == end() ){
|
||
|
push_back( x );
|
||
|
return( iterator( this, tail ) );
|
||
|
}
|
||
|
|
||
|
// to do - move from end if quicker
|
||
|
size_type i, ins, dist, num_pages;
|
||
|
// copy from begining
|
||
|
dist = dist_from_first( it.i ); // dist of new element after it has been inserted
|
||
|
if( is_front_full() ) grow_cbuf( cbuf_length * 2 );
|
||
|
ins = wrap( head + dist - 1 ); // index to insert new element
|
||
|
// calc num of pages needed to copy
|
||
|
num_pages = dist / PageSize + 1;
|
||
|
if( dist % PageSize > get_pi( ins ) ) num_pages += 1;
|
||
|
// temp array of pages
|
||
|
cbuf_t temp_pages = cmem.allocate( num_pages );
|
||
|
try{
|
||
|
for( i = 0; i < num_pages; i++ ){
|
||
|
temp_pages[i] = pmem.allocate( PageSize );
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
while( i ){
|
||
|
i--;
|
||
|
pmem.deallocate( temp_pages[i], PageSize );
|
||
|
}
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
throw;
|
||
|
}
|
||
|
// is last page a full page or is end reached during it?
|
||
|
size_type end;
|
||
|
if( get_ci(tail) == get_ci(ins) ) end = get_pi(tail);
|
||
|
else end = PageSize - 1;
|
||
|
try{
|
||
|
// copy from end to insert point
|
||
|
for( i = end; i > get_pi(ins); i-- ){
|
||
|
pmem.construct( &temp_pages[num_pages-1][i], cbuf[get_ci(ins)][i] );
|
||
|
}
|
||
|
// copy new element
|
||
|
pmem.construct( &temp_pages[num_pages-1][i], x );
|
||
|
}catch( ... ){
|
||
|
while( i < end ){
|
||
|
i++;
|
||
|
pmem.destroy( &temp_pages[num_pages-1][i] );
|
||
|
}
|
||
|
for( i = 0; i< num_pages; i++ ) pmem.deallocate( temp_pages[i], PageSize );
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
throw;
|
||
|
}
|
||
|
// copy from begining to insert point
|
||
|
size_type s,d;
|
||
|
try{
|
||
|
d = wrap(head-1) % PageSize; // new page 0 start point
|
||
|
s = head;
|
||
|
while( s != wrap(ins+1) ){
|
||
|
pmem.construct( &temp_pages[get_ci(d)][get_pi(d)], cbuf[get_ci(s)][get_pi(s)] );
|
||
|
s = wrap( s + 1 );
|
||
|
++d;
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
while( s != head ){
|
||
|
s = wrap( s -1 );
|
||
|
pmem.destroy( &temp_pages[get_ci(s)][get_pi(s)] );
|
||
|
}
|
||
|
for( i = 0; i < num_pages; i++ )pmem.deallocate( temp_pages[i], PageSize );
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
throw;
|
||
|
}
|
||
|
// destroy orig objects
|
||
|
for( i = head; i != wrap( 1 + end + get_ci(ins)*PageSize ); i = wrap( i + 1 ) ){
|
||
|
pmem.destroy( &cbuf[get_ci(i)][get_pi(i)] );
|
||
|
}
|
||
|
// copy new pages, destroy old from inserted page to new head
|
||
|
s = get_ci( ins );
|
||
|
for( i = 1; i <= num_pages; i++ ){
|
||
|
if( cbuf[s] ) pmem.deallocate( cbuf[s], PageSize );
|
||
|
cbuf[s] = temp_pages[ num_pages - i ];
|
||
|
s = ( s - 1 ) & ( cbuf_length - 1 );
|
||
|
}
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
//update pointers
|
||
|
head = wrap( head - 1 );
|
||
|
++deq_used;
|
||
|
|
||
|
return( iterator( this, ins ) );
|
||
|
}
|
||
|
|
||
|
|
||
|
// erase( iterator )
|
||
|
// *****************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
typename deque< Type, Allocator, PageSize >::iterator
|
||
|
deque< Type, Allocator, PageSize >::erase( iterator e )
|
||
|
{
|
||
|
// check if at first or last element
|
||
|
if( dist_from_first( e.i ) == 0 ){
|
||
|
pop_front();
|
||
|
return( begin() );
|
||
|
}else if( dist_from_last( e.i ) == 0 ){
|
||
|
pop_back();
|
||
|
return( end() );
|
||
|
}
|
||
|
// to do - move from end if quicker
|
||
|
//if( dist_from_first( e.i ) < dist_from_last( e.i ) ) {
|
||
|
// if nearer to begining
|
||
|
size_type s, end;
|
||
|
int i;
|
||
|
// alloc temp pages
|
||
|
size_type dist = dist_from_first( e.i ) - 1;
|
||
|
size_type num_pages = dist / PageSize + 1;
|
||
|
if( (dist % PageSize) > get_pi( e.i ) ) num_pages += 1;
|
||
|
|
||
|
cbuf_t temp_pages = cmem.allocate( num_pages );
|
||
|
try{
|
||
|
for( i = 0; i < num_pages; i++ ){
|
||
|
temp_pages[i] = pmem.allocate( PageSize );
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
while( i ){
|
||
|
i--;
|
||
|
pmem.deallocate( temp_pages[i], PageSize );
|
||
|
}
|
||
|
throw;
|
||
|
}
|
||
|
// copy from end of erased page to erased element
|
||
|
// tail might be before PageSize-1 of this page
|
||
|
if( get_ci(e.i) == get_ci(tail) ) end = get_pi(tail);
|
||
|
else end = PageSize-1;
|
||
|
|
||
|
try{
|
||
|
for( i = end; i > get_pi( e.i ); i-- ){
|
||
|
pmem.construct( &temp_pages[num_pages-1][i], cbuf[ get_ci( e.i ) ][ i ] );
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
while( i < end ){
|
||
|
i++;
|
||
|
pmem.destroy( &temp_pages[num_pages-1][i] );
|
||
|
}
|
||
|
for( i = 0; i < num_pages; i++ ) pmem.deallocate( temp_pages[i], PageSize );
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
throw;
|
||
|
}
|
||
|
// copy from beginning to erased element
|
||
|
try{
|
||
|
size_type d = (head+1) % PageSize; // start on new page 0
|
||
|
for( s = head; s != e.i; ++d ){
|
||
|
pmem.construct( &temp_pages[get_ci(d)][get_pi(d)], cbuf[get_ci(s)][get_pi(s)] );
|
||
|
s = wrap(s+1);
|
||
|
}
|
||
|
}catch( ... ){
|
||
|
while( s != head ){
|
||
|
s = wrap( s - 1 );
|
||
|
pmem.destroy( &temp_pages[get_ci(s)][get_pi(s)] );
|
||
|
}
|
||
|
for( i = 0; i < num_pages; i++ ) pmem.deallocate( temp_pages[i], PageSize );
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
throw;
|
||
|
}
|
||
|
// destroy old objects
|
||
|
for( s = head; s != wrap( 1 + end + get_ci(e.i)*PageSize ); ){
|
||
|
pmem.destroy( &cbuf[get_ci(s)][get_pi(s)] );
|
||
|
s = wrap( s + 1 );
|
||
|
}
|
||
|
// copy new pages
|
||
|
size_type j = get_ci(e.i);
|
||
|
for( i = num_pages; i > 0; ){
|
||
|
pmem.deallocate( cbuf[j], PageSize );
|
||
|
--i;
|
||
|
cbuf[j] = temp_pages[i];
|
||
|
j = ( j - 1 ) & ( cbuf_length - 1 );
|
||
|
}
|
||
|
// there may be a page freed up but we won't bother deleting it
|
||
|
|
||
|
// remove temp page array
|
||
|
cmem.deallocate( temp_pages, num_pages );
|
||
|
// update pointers
|
||
|
--deq_used;
|
||
|
head = wrap(head + 1);
|
||
|
|
||
|
return( e + 1 );
|
||
|
//}else{
|
||
|
//nearer to end
|
||
|
// to do
|
||
|
//}
|
||
|
}
|
||
|
|
||
|
// _Sane( ) const
|
||
|
// **************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
bool deque< Type, Allocator, PageSize >::_Sane( ) const
|
||
|
{
|
||
|
if( cbuf_length == 0 ){
|
||
|
//cout<<"buf len "<<cbuf_length<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
if( cbuf_length*PageSize < deq_used ){
|
||
|
//cout<<"len*page"<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
|
||
|
// Is cbuf_length a power of 2?
|
||
|
size_type temp = cbuf_length;
|
||
|
while( temp != 1 ) {
|
||
|
if( temp & 0x1 ){
|
||
|
//cout<<"p2"<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
temp >>= 1;
|
||
|
}
|
||
|
|
||
|
// Check the head and tail indicies.
|
||
|
if( get_ci(head) >= cbuf_length || get_ci(tail) >= cbuf_length ){
|
||
|
//cout<<"head "<<head<<" tail "<<tail<<" len "<<cbuf_length<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
if( get_ci(head) == get_ci(tail) && get_pi(head) > get_pi(tail) && deq_used != 0 ){
|
||
|
//cout<<"chead==ctail & phead>ptail"<<deq_used<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
if( deq_used == 0 && wrap( head - tail ) != 1 ){
|
||
|
//cout<<"bad empty h t ptrs"<<head<<", "<<tail<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
|
||
|
// Check distance between indecies stacks up with deq_used
|
||
|
if( wrap(1 + tail - head) != deq_used ){
|
||
|
//cout<<"dist "<<wrap(1 + tail - head)<<" used "<<deq_used<<" head "<<head<<" tail "<<tail<<"\n";
|
||
|
return( false );
|
||
|
}
|
||
|
|
||
|
return( true );
|
||
|
}
|
||
|
|
||
|
/* bug : funtion templates can't have non-type template params
|
||
|
// ==============================
|
||
|
// Ordinary functions using deque
|
||
|
// ==============================
|
||
|
|
||
|
// NOTE: The implementation of operator== and operator< is probably
|
||
|
// the same for all three sequence containers. Should this be a helper
|
||
|
// template parameterized by container type? (Probably)
|
||
|
|
||
|
// operator==( const deque &, const deque & )
|
||
|
// ******************************************
|
||
|
template< class Type, class Allocator, int PageSize1, int PageSize2 >
|
||
|
bool operator==( const deque< Type, Allocator, PageSize1 > &x,
|
||
|
const deque< Type, Allocator, PageSize2 > &y )
|
||
|
{
|
||
|
if( x.size( ) != y.size( ) ) return( false );
|
||
|
|
||
|
deque< Type, Allocator, PageSize1 >::size_type index = 0;
|
||
|
while( index < x.size( ) ) {
|
||
|
if( x[index] != y[index] ) return( false );
|
||
|
++index;
|
||
|
}
|
||
|
return( true );
|
||
|
}
|
||
|
|
||
|
// operator<( const deque &, const deque & )
|
||
|
// *****************************************
|
||
|
template< class Type, class Allocator, int PageSize1, int PageSize2 >
|
||
|
bool operator< ( const deque< Type, Allocator, PageSize1 > &x,
|
||
|
const deque< Type, Allocator, PageSize2 > &y )
|
||
|
{
|
||
|
deque< Type, Allocator, PageSize1 >::size_type index = 0;
|
||
|
while( index != x.size( ) && index != y.size( ) ) {
|
||
|
if( x[index] < y[index] ) return( true );
|
||
|
if( y[index] < x[index] ) return( false );
|
||
|
++index;
|
||
|
}
|
||
|
return( index == x.size( ) && index != y.size( ) );
|
||
|
}
|
||
|
|
||
|
// operator!=( const deque &, const deque & )
|
||
|
// ******************************************
|
||
|
template< class Type, class Allocator, int PageSize1, int PageSize2 >
|
||
|
inline
|
||
|
bool operator!=( const deque< Type, Allocator, PageSize1 > &x,
|
||
|
const deque< Type, Allocator, PageSize2 > &y )
|
||
|
{
|
||
|
return( !( x == y ) );
|
||
|
}
|
||
|
|
||
|
// operator>( const deque &, const deque & )
|
||
|
// *****************************************
|
||
|
template< class Type, class Allocator, int PageSize1, int PageSize2 >
|
||
|
inline
|
||
|
bool operator> ( const deque< Type, Allocator, PageSize1 > &x,
|
||
|
const deque< Type, Allocator, PageSize2 > &y )
|
||
|
{
|
||
|
return( y < x );
|
||
|
}
|
||
|
|
||
|
// operator>=( const deque &, const deque & )
|
||
|
// ******************************************
|
||
|
template< class Type, class Allocator, int PageSize1, int PageSize2 >
|
||
|
inline
|
||
|
bool operator>=( const deque< Type, Allocator, PageSize1 > &x,
|
||
|
const deque< Type, Allocator, PageSize2 > &y )
|
||
|
{
|
||
|
return( !( x < y ) );
|
||
|
}
|
||
|
|
||
|
// operator<=( const deque &, const deque & )
|
||
|
// ******************************************
|
||
|
template< class Type, class Allocator, int PageSize1, int PageSize2 >
|
||
|
inline
|
||
|
bool operator<=( const deque< Type, Allocator, PageSize1 > &x,
|
||
|
const deque< Type, Allocator, PageSize2 > &y )
|
||
|
{
|
||
|
return( !( x > y ) );
|
||
|
}
|
||
|
|
||
|
#ifdef __NEVER
|
||
|
// swap( deque &, deque & )
|
||
|
// **************************
|
||
|
template< class Type, class Allocator, int PageSize >
|
||
|
inline
|
||
|
void swap( deque< Type, Allocator, PageSize > &x, deque< Type, Allocator, PageSize > &y )
|
||
|
{
|
||
|
x.swap( y );
|
||
|
}
|
||
|
#endif
|
||
|
*/
|
||
|
} // namespace std
|
||
|
|
||
|
#endif
|