PDeque.h
// PDeque.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2006
@import "cxPersistStore.h"
@import "IPersistStore.h"
@import "Ceda/cxObject/WCSpace.h"
#include "Ceda/cxUtils/VectorOfByte.h"
#include "Ceda/cxUtils/MakeIterator.h"
#include <iterator>
#include <deque>
@def mDefinePDeque(DequeName, T, bool elementHasPrefs, int numElementsPerPage) =
{
///////////////////////////////////////////////////////////////////////////////////////////////
// Page
//
// A page implements IPersistable so that it may be saved as a serial element on the hard-disk
// and be identified with an OID.
// The pages form a doubly linked list
@def Page = DequeName@@@quote(Page)
$class Page isa ceda::IPersistable
{
public:
Page()
{
// Avoid memory reallocations as the page grows and shrinks
m_values.reserve(numElementsPerPage);
}
//~Page() { Tracer() << "~Page() : " << this << '\n'; }
// Implementation of IObject
void VisitObjects(ceda::IObjectVisitor& v) const
{
@if (elementHasPrefs)
{
v << m_values;
}
//Tracer() << "Visiting: this = " << this << " m_prev = " << m_prev << " m_next = " << m_next << '\n';
v << m_prev << m_next;
}
static const ceda::schema_t Page@@_SCHEMA = 1;
// Implementation of IPersistable
void Serialise(ceda::Archive& ar) const
{
ceda::SerialiseSchema(ar, Page@@_SCHEMA);
ar << m_prev
<< m_next
<< m_values;
}
void Deserialise(ceda::InputArchive& ar)
{
ceda::schema_t schema;
ceda::DeserialiseSchema(ar,Page@@_SCHEMA,schema);
ar >> m_prev
>> m_next
>> m_values;
}
void VisitPrefs(ceda::IPrefVisitor& v) const
{
@if (elementHasPrefs)
{
v << m_values;
}
// As far as ownership semantics is concerned, each page is assumed to be the parent of
// the next page in the linked list.
v << m_next;
v.VisitParent(m_prev);
}
ceda::ssize_t size() const { return m_values.size(); }
public:
ceda::cref<Page> m_prev; // Ptr to prev page in the double linked list
ceda::cref<Page> m_next; // Ptr to next page in the double linked list
typedef ceda::xvector<T> VALUES;
VALUES m_values; // Elements stored in this page
};
///////////////////////////////////////////////////////////////////////////////////////////////
@def bool CEDA_USE_OLD_ITERATOR_IMPL = false
@def mWritePostFixOperatorsForIterator(iterator) =
{
// Postfix
const iterator operator++(int) { iterator it = *this; ++(*this); return it; }
const iterator operator--(int) { iterator it = *this; --(*this); return it; }
}
$class DequeName isa ceda::IPersistable
{
public:
@if (CEDA_USE_OLD_ITERATOR_IMPL)
{
///////////////////////////////////////////////////////////////////////////////////////////
// const_iterator
/*
A bidirectional iterator that can move to one before beginning as well as one past end
positions
An iterator remains valid with calls to push_back(), but not push_front().
If the iterator is currently at end() then following a call to push_back() the iterator
will point at the last element in the PDeque (i.e. back()).
*/
class const_iterator
{
public:
const_iterator() : m_deque(nullptr), m_page(nullptr), m_startIndex(-1), m_index(-1) {}
const_iterator(const DequeName* deque, Page* page, ceda::ssize_t startIndex, ceda::ssize_t index) :
m_deque(deque),
m_page(page),
m_startIndex(startIndex),
m_index(index)
{
cxAssert(deque);
}
void VisitObjects(ceda::IObjectVisitor& v) const { v << m_deque << m_page; }
// Prefix
const_iterator& operator++()
{
cxAssert(m_deque);
if (!m_page)
{
// This can happen if the iterator was initialised when the PDeque was empty
cxAssert(m_startIndex == -1);
cxAssert(m_index == 0 || m_index == -1);
if (m_index == -1)
{
// Cannot assume that PDeque is nonempty, so easiest to simply increment
// m_index and return
m_index = 0;
return *this;
}
m_page = m_deque->m_first.Get();
m_startIndex = 0;
cxAssert(m_page);
}
ceda::ssize_t endIndex = m_startIndex + m_page->size();
// Note that m_index = m_startIndex - 1 is possible in (and only in) the case where
// m_index = -1 (i.e. the iterator is at one before the beginning of the sequence)
cxAssert(
(m_index == -1 && m_startIndex == 0) ||
(m_startIndex <= m_index && m_index <= endIndex));
if (++m_index > endIndex)
{
// Move to next page
m_page = m_page->m_next.Get();
cxAssert(m_page);
m_startIndex = endIndex;
}
return *this;
}
// Prefix
const_iterator& operator--()
{
cxAssert(m_deque);
cxAssert(m_page);
//Tracer() << "m_startIndex = " << m_startIndex << '\n';
//Tracer() << "m_index = " << m_index << '\n';
cxAssert(m_startIndex <= m_index && m_index <= m_startIndex + m_page->size());
if (--m_index < m_startIndex)
{
Page* prev = m_page->m_prev.Get();
if (prev)
{
m_page = prev;
m_startIndex -= prev->size();
cxAssert(m_startIndex >= 0);
}
else
{
cxAssert(m_startIndex == 0);
cxAssert(m_index == -1);
}
}
return *this;
}
mWritePostFixOperatorsForIterator(const_iterator)
const T& operator*() const
{
cxAssert(m_deque);
if (!m_page)
{
// This can happen if the iterator was initialised when the PDeque was empty
cxAssert(m_startIndex == -1);
cxAssert(m_index == 0);
const_cast<const_iterator*>(this)->m_page = m_deque->m_first.Get();
const_cast<const_iterator*>(this)->m_startIndex = 0;
cxAssert(m_page);
}
ceda::ssize_t offset = m_index - m_startIndex;
ceda::ssize_t numElements = m_page->size();
cxAssert(0 <= offset && offset <= numElements);
if (offset < numElements)
{
return m_page->m_values[offset];
}
else
{
// Move onto the next page
Page* next = m_page->m_next.Get();
cxAssert(next);
const_cast<const_iterator*>(this)->m_page = next;
const_cast<const_iterator*>(this)->m_startIndex = m_index;
return m_page->m_values[0];
}
}
const T* operator->() const
{
return &operator*();
}
ceda::ssize_t operator-(const const_iterator& rhs) const { return m_index - rhs.m_index; }
// Note that comparisons avoid testing m_page
bool operator==(const const_iterator& rhs) const
{
cxAssert(m_deque);
cxAssert(m_deque == rhs.m_deque);
return m_index == rhs.m_index;
}
bool operator!=(const const_iterator& rhs) const
{
cxAssert(m_deque);
cxAssert(m_deque == rhs.m_deque);
return m_index != rhs.m_index;
}
// Get index position into the PDeque
ceda::ssize_t GetIndex() const
{
cxAssert(m_deque);
return m_index;
}
private:
// Should only be called if the iterator position is valid in the sense that a call to operator*()
// is possible.
Page* GetPage()
{
cxAssert(m_deque);
if (!m_page)
{
// This can happen if the iterator was initialised when the PDeque was empty
cxAssert(m_startIndex == -1);
cxAssert(m_index == 0);
const_cast<const_iterator*>(this)->m_page = m_deque->m_first.Get();
const_cast<const_iterator*>(this)->m_startIndex = 0;
cxAssert(m_page);
}
return m_page;
}
const DequeName* m_deque;
/*
m_page points at the "current page". Must not be nullptr unless the PDeque is empty or
m_index = 0 or m_index = -1.
Calling it the current page is a bit of a misnomer because
1) it is permissible for the iterator position to be one past the last element of
m_page (meaning that the iterator is actually pointing at the first element
of the next page!)
Note that this rather surprising admission allows the iterator to point at a
position one past the last page without needing to clear m_page. More importantly,
it allows for an iterator to remain valid as elements are pushed onto the back
of the deque. Consider an iterator that points at the end of the PDeque and the
last page is full. The iterator must later support operator++() and operator*()
after additional elements (and pages) are appended to the PDeque.
2) it is permissible for m_page to point at the first page in the PDeque when
m_index = -1.
*/
Page* m_page;
// The index position in the PDeque of the zeroth element on m_page, or -1 if the
// PDeque is empty.
ceda::ssize_t m_startIndex;
// Current index position in the PDeque. -1 represents "one before beginning", and
// PDeque.size represents "one past end"
ceda::ssize_t m_index;
friend class DequeName;
};
const_iterator begin() const
{
return const_iterator(this,nullptr,-1,0);
}
const_iterator end() const
{
if (m_size > 0)
{
Page* last = m_last.Get();
cxAssert(last);
return const_iterator(this,last, m_size - last->size(), m_size);
}
else
{
cxAssert(m_size == 0);
return const_iterator(this,nullptr,-1,0);
}
}
///////////////////////////////////////////////////////////////////////////////////////////
// iterator
// iterator inherits from const_iterator allowing for implicit cast from iterator
// to const_iterator
struct iterator : public const_iterator
{
// Provide write access to elements
T& operator*() const { return const_cast<T&>(const_iterator::operator*()); }
T* operator->() const { return const_cast<T*>(&const_iterator::operator*()); }
iterator& operator++() { const_iterator::operator++(); return *this; }
iterator& operator--() { const_iterator::operator--(); return *this; }
mWritePostFixOperatorsForIterator(iterator)
};
iterator begin()
{
return static_cast<iterator&>(const_cast<const DequeName*>(this)->begin());
}
iterator end()
{
return static_cast<iterator&>(const_cast<const DequeName*>(this)->end());
}
///////////////////////////////////////////////////////////////////////////////////////////
// const_reverse_iterator
// Note that the STL already provides an adapter to make a reverse_iterator from a
// bidirectional iterator. It assumes operator*() will first decrement the
// iterator. Our const_iterator already supports one before beginning so
// we opt for a more efficient implementation.
class const_reverse_iterator
{
public:
const_reverse_iterator(const const_iterator& it) : m_it(it) {}
void VisitObjects(ceda::IObjectVisitor& v) const { m_it.VisitObjects(v); }
const T& operator*() const { return *m_it; }
const T* operator->() const { return &*m_it; }
const_reverse_iterator& operator++() { --m_it; return *this; }
const_reverse_iterator& operator--() { ++m_it; return *this; }
mWritePostFixOperatorsForIterator(const_reverse_iterator)
bool operator==(const const_reverse_iterator& rhs) const { return m_it == rhs.m_it; }
bool operator!=(const const_reverse_iterator& rhs) const { return m_it != rhs.m_it; }
ceda::ssize_t operator-(const const_reverse_iterator& rhs) const { return m_it - rhs.m_it; }
ceda::ssize_t GetIndex() const { return m_it.GetIndex(); }
private:
const_iterator m_it;
};
const_reverse_iterator rbegin() const
{
if (m_size > 0)
{
Page* last = m_last.Get();
cxAssert(last);
return const_reverse_iterator(const_iterator(this,last, m_size - last->size(), m_size-1));
}
else
{
cxAssert(m_size == 0);
//cxAssert(!m_first);
//cxAssert(!m_last);
return const_reverse_iterator(const_iterator(this,nullptr,-1,-1));
}
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(const_iterator(this,nullptr,-1,-1));
}
///////////////////////////////////////////////////////////////////////////////////////////
// reverse_iterator
// reverse_iterator inherits from const_reverse_iterator allowing for implicit cast from
// reverse_iterator to const_reverse_iterator
struct reverse_iterator : public const_reverse_iterator
{
// Provide write access to elements
T& operator*() const { return const_cast<T&>(const_reverse_iterator::operator*()); }
T* operator->() const { return const_cast<T*>(&const_reverse_iterator::operator*()); }
reverse_iterator& operator++() { const_reverse_iterator::operator++(); return *this; }
reverse_iterator& operator--() { const_reverse_iterator::operator--(); return *this; }
mWritePostFixOperatorsForIterator(reverse_iterator)
};
reverse_iterator rbegin()
{
return static_cast<reverse_iterator&>(const_cast<const DequeName*>(this)->rbegin());
}
reverse_iterator rend()
{
return static_cast<reverse_iterator&>(const_cast<const DequeName*>(this)->rend());
}
}
@else
{
/*
Attempt at using make_iterator. Not used at the moment because std::reverse_iterator<>
adapter doesn't implement VisitObjects() for us.
*/
class IteratorPolicy
{
public:
IteratorPolicy() : m_deque(nullptr), m_page(nullptr), m_startIndex(-1), m_index(-1) {}
IteratorPolicy(const DequeName* deque, Page* page, ceda::ssize_t startIndex, ceda::ssize_t index) :
m_deque(deque),
m_page(page),
m_startIndex(startIndex),
m_index(index)
{
cxAssert(deque);
}
void VisitObjects(ceda::IObjectVisitor& v) const { v << m_deque << m_page; }
typedef std::bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef std::ptrdiff_t difference_type; // just to keep compiler happy
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
void next()
{
cxAssert(m_deque);
if (!m_page)
{
// This can happen if the iterator was initialised when the PDeque was empty
cxAssert(m_startIndex == -1);
cxAssert(m_index == 0 || m_index == -1);
if (m_index == -1)
{
// Cannot assume that PDeque is nonempty, so easiest to simply increment
// m_index and return
m_index = 0;
return;
}
m_page = m_deque->m_first.Get();
m_startIndex = 0;
cxAssert(m_page);
}
ceda::ssize_t endIndex = m_startIndex + m_page->size();
// Note that m_index = m_startIndex - 1 is possible in (and only in) the case where
// m_index = -1 (i.e. the iterator is at one before the beginning of the sequence)
cxAssert(
(m_index == -1 && m_startIndex == 0) ||
(m_startIndex <= m_index && m_index <= endIndex));
if (++m_index > endIndex)
{
// Move to next page
m_page = m_page->m_next.Get();
cxAssert(m_page);
m_startIndex = endIndex;
}
}
void prev()
{
cxAssert(m_deque);
cxAssert(m_page);
//Tracer() << "m_startIndex = " << m_startIndex << '\n';
//Tracer() << "m_index = " << m_index << '\n';
cxAssert(m_startIndex <= m_index && m_index <= m_startIndex + m_page->size());
if (--m_index < m_startIndex)
{
Page* prev = m_page->m_prev.Get();
if (prev)
{
m_page = prev;
m_startIndex -= prev->size();
cxAssert(m_startIndex >= 0);
}
else
{
cxAssert(m_startIndex == 0);
cxAssert(m_index == -1);
}
}
}
const value_type& const_deref() const
{
cxAssert(m_deque);
if (!m_page)
{
// This can happen if the iterator was initialised when the PDeque was empty
cxAssert(m_startIndex == -1);
cxAssert(m_index == 0);
const_cast<IteratorPolicy*>(this)->m_page = m_deque->m_first.Get();
const_cast<IteratorPolicy*>(this)->m_startIndex = 0;
cxAssert(m_page);
}
ceda::ssize_t offset = m_index - m_startIndex;
ceda::ssize_t numElements = m_page->size();
cxAssert(0 <= offset && offset <= numElements);
if (offset < numElements)
{
return m_page->m_values[offset];
}
else
{
// Move onto the next page
Page* next = m_page->m_next.Get();
cxAssert(next);
const_cast<IteratorPolicy*>(this)->m_page = next;
const_cast<IteratorPolicy*>(this)->m_startIndex = m_index;
return m_page->m_values[0];
}
}
value_type& deref() const
{
// todo : need to mark page as dirty
return (value_type&) const_deref();
}
ceda::ssize_t operator-(const IteratorPolicy& rhs) const
{
return m_index - rhs.m_index;
}
// Note that comparisons avoid testing m_page
bool operator==(const IteratorPolicy& rhs) const
{
cxAssert(m_deque);
cxAssert(m_deque == rhs.m_deque);
return m_index == rhs.m_index;
}
// Get index position into the PDeque
ceda::ssize_t GetIndex() const
{
cxAssert(m_deque);
return m_index;
}
private:
// Should only be called if the iterator position is valid in the sense that a call to operator*()
// is possible.
Page* GetPage()
{
cxAssert(m_deque);
if (!m_page)
{
// This can happen if the iterator was initialised when the PDeque was empty
cxAssert(m_startIndex == -1);
cxAssert(m_index == 0);
const_cast<IteratorPolicy*>(this)->m_page = m_deque->m_first.Get();
const_cast<IteratorPolicy*>(this)->m_startIndex = 0;
cxAssert(m_page);
}
return m_page;
}
const DequeName* m_deque;
/*
m_page points at the "current page". Must not be nullptr unless the PDeque is empty or
m_index = 0 or m_index = -1.
Calling it the current page is a bit of a misnomer because
1) it is permissible for the iterator position to be one past the last element of
m_page (meaning that the iterator is actually pointing at the first element
of the next page!)
Note that this rather surprising admission allows the iterator to point at a
position one past the last page without needing to clear m_page. More importantly,
it allows for an iterator to remain valid as elements are pushed onto the back
of the deque. Consider an iterator that points at the end of the PDeque and the
last page is full. The iterator must later support operator++() and operator*()
after additional elements (and pages) are appended to the PDeque.
2) it is permissible for m_page to point at the first page in the PDeque when
m_index = -1.
*/
Page* m_page;
// The index position in the PDeque of the zeroth element on m_page, or -1 if the
// PDeque is empty.
ceda::ssize_t m_startIndex;
// Current index position in the PDeque. -1 represents "one before beginning", and
// PDeque.size represents "one past end"
ceda::ssize_t m_index;
friend class DequeName;
};
typedef ceda::make_iterator<IteratorPolicy> iterator;
iterator begin()
{
return iterator(IteratorPolicy(this,nullptr,-1,0));
}
iterator end()
{
if (m_size > 0)
{
Page* last = m_last.Get();
cxAssert(last);
return iterator(IteratorPolicy(this,last, m_size - last->size(), m_size));
}
else
{
cxAssert(m_size == 0);
return iterator(IteratorPolicy(this,nullptr,-1,0));
}
}
typedef ceda::make_const_iterator<IteratorPolicy> const_iterator;
const_iterator begin() const { return const_cast<DequeName*>(this)->begin(); }
const_iterator end() const { return const_cast<DequeName*>(this)->end(); }
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
typedef std::reverse_iterator<iterator> reverse_iterator;
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
}
///////////////////////////////////////////////////////////////////////////////////////////
DequeName() : m_size(0) {}
// Implementation of IObject
void VisitObjects(ceda::IObjectVisitor& v) const { v << m_first << m_last; }
// Implementation of IPersistable
void VisitPrefs(ceda::IPrefVisitor& v) const
{
// todo. The pointer m_last breaks the assumption of a tree structure.
// Therefore a PDeque can't be cloned automatically with the current system.
v << m_first /*<< m_last*/;
}
static const ceda::schema_t DequeName@@_SCHEMA = 1;
void Serialise(ceda::Archive& ar) const
{
ceda::SerialiseSchema(ar, DequeName@@_SCHEMA);
ar << m_first
<< m_last;
SerialiseVariableLengthUint(ar,m_size);
}
void Deserialise(ceda::InputArchive& ar)
{
ceda::schema_t schema;
ceda::DeserialiseSchema(ar,DequeName@@_SCHEMA,schema);
ar >> m_first >> m_last;
DeserialiseVariableLengthUint(ar,m_size);
}
/////////////// compare //////////////////
// Returns -1,0,1 for lexicographic compare
int compare(const DequeName& r) const
{
return ceda::LexicographicalCompareX(begin(), end(), r.begin(), r.end());
}
bool _Eq(const DequeName& r) const
{
return size() == r.size() && ceda::IsEqual(begin(), end(), r.begin());
}
bool _Lt(const DequeName& r) const
{
return compare(r) < 0;
}
// Note that push_front causes insertions into the front of the first page and
// therefore causes copying of elements. Therefore it isn't as efficient as
// push_back.
void push_front(const T& x)
{
cxAssert(ceda::HaveLockedCSpace());
Page* firstPage = AlwaysGetFirstPage();
ceda::ssize_t numElements = firstPage->size();
if (numElements >= numElementsPerPage)
{
// First page is full - create a new first page
Page* prevFirstPage = firstPage;
firstPage = $new Page;
// Fix links
prevFirstPage->m_prev = firstPage;
prevFirstPage->MarkAsDirtyWithoutTrace();
// Affiliates new first page with old first page
DeclareReachable(prevFirstPage,firstPage);
firstPage->m_next = prevFirstPage;
m_first = firstPage;
}
firstPage->m_values.insert( (ceda::ssize_t) 0,x); // casted need to avoid ambiguity if iterator is a raw pointer
firstPage->MarkAsDirtyWithoutTrace();
@if (elementHasPrefs)
{
// Declare reachability by visiting all prefs in x
DeclareReachableX(firstPage,x);
}
++m_size;
MarkAsDirtyWithoutTrace();
}
void push_back(const T& x)
{
cxAssert(ceda::HaveLockedCSpace());
Page* lastPage = AlwaysGetLastPage();
ceda::ssize_t numElements = lastPage->size();
if (numElements >= numElementsPerPage)
{
// Last page is full - create a new last page
Page* prevLastPage = lastPage;
lastPage = $new Page;
// Fix links
prevLastPage->m_next = lastPage;
prevLastPage->MarkAsDirtyWithoutTrace();
// Affiliates new last page with old last page
DeclareReachable(prevLastPage,lastPage);
lastPage->m_prev = prevLastPage;
m_last = lastPage;
//Tracer() << "push_back overflowed...\n";
//Tracer() << " lastPage = " << lastPage << '\n';
//Tracer() << " prevLastPage = " << prevLastPage << '\n';
//Tracer() << " lastPage->m_prev = " << lastPage->m_prev << '\n';
}
lastPage->m_values.push_back(x);
lastPage->MarkAsDirtyWithoutTrace();
@if (elementHasPrefs)
{
// Declare reachability by visiting all prefs in x
DeclareReachableX(lastPage,x);
}
++m_size;
MarkAsDirtyWithoutTrace();
}
void clear()
{
cxAssert(ceda::HaveLockedCSpace());
// todo: AsyncPermanentlyDeleteSubTree() takes a ptr<IPersistable>. It seems
// unfortunate that we will end up faulting the page into memory just to mark it as
// an object to be async deleted. Would rather simply push the OID if possible.
if (m_first) ceda::AsyncPermanentlyDeleteSubTree(m_first.Get());
m_size = 0;
m_first.Clear();
m_last.Clear();
MarkAsDirtyWithoutTrace();
}
typedef T value_type;
bool empty() const { return m_size == 0; }
ceda::ssize_t size() const { return m_size; }
// Note that operator[] cannot be made efficient, and a programmer would be well advised to
// use an iterator instead.
// todo
//const T& operator[](ceda::ssize_t i) const { return *(begin() + i); }
//T& operator[](ceda::ssize_t i) { return *(begin() + i); }
T& front()
{
Page* first = m_first.Get();
cxAssert(first);
if (first->m_values.empty())
{
first = m_first->m_next.Get();
cxAssert(first);
}
cxAssert(!first->m_values.empty());
return first->m_values.front();
}
T& back()
{
Page* last = m_last.Get();
cxAssert(last);
if (last->m_values.empty())
{
last = m_last->m_next.Get();
cxAssert(last);
}
cxAssert(!last->m_values.empty());
return last->m_values.back();
}
const T& front() const
{
return const_cast<DequeName*>(this)->front();
}
const T& back() const
{
return const_cast<DequeName*>(this)->back();
}
// Note that pop_front causes deletions at the front of the first page and
// therefore causes copying of elements. Therefore it isn't as efficient as
// pop_back.
void pop_front()
{
cxAssert(ceda::HaveLockedCSpace());
cxAssert(m_size > 0);
Page* first = m_first.Get();
cxAssert(first);
cxAssert(!first->m_prev);
cxAssert(!first->m_values.empty());
first->m_values.erase_element(0);
first->MarkAsDirtyWithoutTrace();
if (first->m_values.empty())
{
if (first->m_next)
{
cxAssert(first->m_next->m_prev == first);
first->m_next->m_prev.Clear();
first->m_next->MarkAsDirtyWithoutTrace();
m_first = first->m_next;
first->m_next.Clear();
}
else
{
cxAssert(m_size == 1);
cxAssert(m_first == m_last);
m_first.Clear();
m_last.Clear();
}
ceda::AsyncPermanentlyDeleteObject(first);
}
--m_size;
MarkAsDirtyWithoutTrace();
}
void pop_back()
{
cxAssert(ceda::HaveLockedCSpace());
cxAssert(m_size > 0);
Page* last = m_last.Get();
cxAssert(last);
cxAssert(!last->m_next);
cxAssert(!last->m_values.empty());
last->m_values.pop_back();
last->MarkAsDirtyWithoutTrace();
if (last->m_values.empty())
{
if (last->m_prev)
{
cxAssert(last->m_prev->m_next == last);
last->m_prev->m_next.Clear();
last->m_prev->MarkAsDirtyWithoutTrace();
m_last = last->m_prev;
last->m_prev.Clear();
}
else
{
cxAssert(m_size == 1);
cxAssert(m_first == m_last);
m_first.Clear();
m_last.Clear();
}
ceda::AsyncPermanentlyDeleteObject(last);
}
--m_size;
MarkAsDirtyWithoutTrace();
}
// It is assumed that rhs belongs to the same PersistStore but not necessarily the same
// PSpace
void swap(DequeName& rhs)
{
//todo: assert that rhs belongs to the same PersistStore.
using std::swap;
cxAssert(ceda::HaveLockedCSpace());
swap(m_size, rhs.m_size);
swap(m_first, rhs.m_first);
swap(m_last, rhs.m_last);
MarkAsDirtyWithoutTrace();
rhs.MarkAsDirtyWithoutTrace();
}
// Erase all elements from i onwards from this PDeque
void EraseTail(iterator i)
{
cxAssert(ceda::HaveLockedCSpace());
if (i != end())
{
// Get the page for the iterator
Page* page = i.GetPage();
cxAssert(page);
ceda::ssize_t offset = i.m_index - i.m_startIndex;
ceda::ssize_t m = page->size();
cxAssert(0 <= offset && offset <= m);
if (offset < m)
{
// Delete excess elements on this page
ceda::PermanentlyDeleteReachablePrefVisitor pdv;
for (Page::VALUES::iterator it = page->m_values.begin() + offset;
it != page->m_values.end() ; ++it)
{
pdv << *it;
}
page->m_values.erase(page->m_values.begin() + offset,page->m_values.end());
page->MarkAsDirtyWithoutTrace();
}
if (page->m_next)
{
// Make this page the last page
ceda::AsyncPermanentlyDeleteSubTree(page->m_next.Get());
page->m_next = nullptr;
m_last = page;
page->MarkAsDirtyWithoutTrace();
}
m_size = i.m_index;
MarkAsDirtyWithoutTrace();
}
}
// Transfer all elements from this PDeque from position i onwards to v
void TransferTail(iterator i, std::deque<T >& v)
{
cxAssert(ceda::HaveLockedCSpace());
// Number of elements to be transferred
ceda::ssize_t n = m_size - i.m_index;
cxAssert(n >= 0);
v.resize(n);
iterator j = i;
for (ceda::ssize_t k=0 ; k < n ; ++k)
{
v[k] = *j;
++j;
}
cxAssert(j == end());
// Erase the elements from i onwards from this PDeque
EraseTail(i);
}
private:
Page* CreateFirstPage()
{
cxAssert(!m_first);
cxAssert(!m_last);
Page* p = $new Page;
m_first = m_last = p;
MarkAsDirtyWithoutTrace();
DeclareReachable(this,p);
return p;
}
Page* AlwaysGetFirstPage()
{
if (Page* first = m_first.Get()) return first;
else return CreateFirstPage();
}
Page* AlwaysGetLastPage()
{
if (Page* last = m_last.Get()) return last;
else return CreateFirstPage();
}
private:
// Pointers to the first and last pages in this PDeque
ceda::cref<Page> m_first;
ceda::cref<Page> m_last;
// Total number of elements stored in this PDeque
ceda::ssize_t m_size;
@if (CEDA_USE_OLD_ITERATOR_IMPL)
{
friend class const_iterator;
}
@else
{
friend class IteratorPolicy;
}
};
@if (!CEDA_USE_OLD_ITERATOR_IMPL)
{
inline ceda::IObjectVisitor& operator<<(ceda::IObjectVisitor& v, const DequeName::const_reverse_iterator& x)
{
x.base().VisitObjects(v);
return v;
}
}
inline bool operator==(const DequeName& x, const DequeName& y) { return x._Eq(y); }
inline bool operator!=(const DequeName& x, const DequeName& y) { return !(x == y); }
inline bool operator<(const DequeName& x, const DequeName& y) { return x._Lt(y); }
inline bool operator>(const DequeName& x, const DequeName& y) { return y < x; }
inline bool operator<=(const DequeName& x, const DequeName& y) { return !(y < x); }
inline bool operator>=(const DequeName& x, const DequeName& y) { return !(x < y); }
}