/*
* Copyright 2002, 2006 Adrian Thurston <thurston@complang.org>
*/
/* This file is part of Aapl.
*
* Aapl is free software; you can redistribute it and/or modify it under the
* terms of the GNU Lesser General Public License as published by the Free
* Software Foundation; either version 2.1 of the License, or (at your option)
* any later version.
*
* Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
* more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Aapl; if not, write to the Free Software Foundation, Inc., 59
* Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifndef _AAPL_SVECTOR_H
#define _AAPL_SVECTOR_H
#include <new>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "table.h"
#include "fix_leaks.h"
#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif
/**
* \addtogroup vector
* @{
*/
/** \class SVector
* \brief Copy-on-write dynamic array.
*
* SVector is a variant of Vector that employs copy-on-write behaviour. The
* SVector copy constructor and = operator make shallow copies. If a vector
* that references shared data is modified with insert, replace, append,
* prepend, setAs or remove, a new copy is made so as not to interfere with
* the shared data. However, shared individual elements may be modified by
* bypassing the SVector interface.
*
* SVector is a dynamic array that can be used to contain complex data
* structures that have constructors and destructors as well as simple types
* such as integers and pointers.
*
* SVector supports inserting, overwriting, and removing single or multiple
* elements at once. Constructors and destructors are called wherever
* appropriate. For example, before an element is overwritten, it's
* destructor is called.
*
* SVector provides automatic resizing of allocated memory as needed and
* offers different allocation schemes for controlling how the automatic
* allocation is done. Two senses of the the length of the data is
* maintained: the amount of raw memory allocated to the vector and the number
* of actual elements in the vector. The various allocation schemes control
* how the allocated space is changed in relation to the number of elements in
* the vector.
*/
/*@}*/
/* SVector */
template < class T, class Resize = ResizeExpn > class SVector :
public STable<T>, public Resize
{
private:
typedef STable<T> BaseTable;
public:
/**
* \brief Initialize an empty vector with no space allocated.
*
* If a linear resizer is used, the step defaults to 256 units of T. For a
* runtime vector both up and down allocation schemes default to
* Exponential.
*/
SVector() { }
/**
* \brief Create a vector that contains an initial element.
*
* The vector becomes one element in length. The element's copy
* constructor is used to place the value in the vector.
*/
SVector(const T &val) { setAs(&val, 1); }
/**
* \brief Create a vector that contains an array of elements.
*
* The vector becomes len elements in length. Copy constructors are used
* to place the new elements in the vector.
*/
SVector(const T *val, long len) { setAs(val, len); }
/* Shallow copy. */
SVector( const SVector &v );
/**
* \brief Free all memory used by the vector.
*
* The vector is reset to zero elements. Destructors are called on all
* elements in the vector. The space allocated for the vector is freed.
*/
~SVector() { empty(); }
/* Delete all items. */
void empty();
/**
* \brief Deep copy another vector into this vector.
*
* Copies the entire contents of the other vector into this vector. Any
* existing contents are first deleted. Equivalent to setAs.
*/
void deepCopy( const SVector &v ) { setAs(v.data, v.length()); }
/* Perform a shallow copy of another vector. */
SVector &operator=( const SVector &v );
/*@{*/
/**
* \brief Insert one element at position pos.
*
* Elements in the vector from pos onward are shifted one space to the
* right. The copy constructor is used to place the element into this
* vector. If pos is greater than the length of the vector then undefined
* behaviour results. If pos is negative then it is treated as an offset
* relative to the length of the vector.
*/
void insert(long pos, const T &val) { insert(pos, &val, 1); }
/* Insert an array of values. */
void insert(long pos, const T *val, long len);
/**
* \brief Insert all the elements from another vector at position pos.
*
* Elements in this vector from pos onward are shifted v.length() spaces
* to the right. The element's copy constructor is used to copy the items
* into this vector. The other vector is left unchanged. If pos is off the
* end of the vector, then undefined behaviour results. If pos is negative
* then it is treated as an offset relative to the length of the vector.
* Equivalent to vector.insert(pos, other.data, other.length()).
*/
void insert(long pos, const SVector &v) { insert(pos, v.data, v.length()); }
/* Insert len copies of val into the vector. */
void insertDup(long pos, const T &val, long len);
/**
* \brief Insert one new element using the default constrcutor.
*
* Elements in the vector from pos onward are shifted one space to the right.
* The default constructor is used to init the new element. If pos is greater
* than the length of the vector then undefined behaviour results. If pos is
* negative then it is treated as an offset relative to the length of the
* vector.
*/
void insertNew(long pos) { insertNew(pos, 1); }
/* Insert len new items using default constructor. */
void insertNew(long pos, long len);
/*@}*/
/*@{*/
/**
* \brief Remove one element at position pos.
*
* The element's destructor is called. Elements to the right of pos are
* shifted one space to the left to take up the free space. If pos is greater
* than or equal to the length of the vector then undefined behavior results.
* If pos is negative then it is treated as an offset relative to the length
* of the vector.
*/
void remove(long pos) { remove(pos, 1); }
/* Delete a number of elements. */
void remove(long pos, long len);
/*@}*/
/*@{*/
/**
* \brief Replace one element at position pos.
*
* If there is an existing element at position pos (if pos is less than the
* length of the vector) then its destructor is called before the space is
* used. The copy constructor is used to place the element into the vector.
* If pos is greater than the length of the vector then undefined behaviour
* results. If pos is negative then it is treated as an offset relative to
* the length of the vector.
*/
void replace(long pos, const T &val) { replace(pos, &val, 1); }
/* Replace with an array of values. */
void replace(long pos, const T *val, long len);
/**
* \brief Replace at position pos with all the elements of another vector.
*
* Replace at position pos with all the elements of another vector. The other
* vector is left unchanged. If there are existing elements at the positions
* to be replaced, then destructors are called before the space is used. Copy
* constructors are used to place the elements into this vector. It is
* allowable for the pos and length of the other vector to specify a
* replacement that overwrites existing elements and creates new ones. If pos
* is greater than the length of the vector then undefined behaviour results.
* If pos is negative, then it is treated as an offset relative to the length
* of the vector.
*/
void replace(long pos, const SVector &v) { replace(pos, v.data, v.length()); }
/* Replace len items with len copies of val. */
void replaceDup(long pos, const T &val, long len);
/**
* \brief Replace at position pos with one new element.
*
* If there is an existing element at the position to be replaced (pos is
* less than the length of the vector) then the element's destructor is
* called before the space is used. The default constructor is used to
* initialize the new element. If pos is greater than the length of the
* vector then undefined behaviour results. If pos is negative, then it is
* treated as an offset relative to the length of the vector.
*/
void replaceNew(long pos) { replaceNew(pos, 1); }
/* Replace len items at pos with newly constructed objects. */
void replaceNew(long pos, long len);
/*@}*/
/*@{*/
/**
* \brief Set the contents of the vector to be val exactly.
*
* The vector becomes one element in length. Destructors are called on any
* existing elements in the vector. The element's copy constructor is used to
* place the val in the vector.
*/
void setAs(const T &val) { setAs(&val, 1); }
/* Set to the contents of an array. */
void setAs(const T *val, long len);
/**
* \brief Set the vector to exactly the contents of another vector.
*
* The vector becomes v.length() elements in length. Destructors are called
* on any existing elements. Copy constructors are used to place the new
* elements in the vector.
*/
void setAs(const SVector &v) { setAs(v.data, v.length()); }
/* Set as len copies of item. */
void setAsDup(const T &item, long len);
/**
* \brief Set the vector to exactly one new item.
*
* The vector becomes one element in length. Destructors are called on any
* existing elements in the vector. The default constructor is used to
* init the new item.
*/
void setAsNew() { setAsNew(1); }
/* Set as newly constructed objects using the default constructor. */
void setAsNew(long len);
/*@}*/
/*@{*/
/**
* \brief Append one elment to the end of the vector.
*
* Copy constructor is used to place the element in the vector.
*/
void append(const T &val) { replace(BaseTable::length(), &val, 1); }
/**
* \brief Append len elements to the end of the vector.
*
* Copy constructors are used to place the elements in the vector.
*/
void append(const T *val, long len) { replace(BaseTable::length(), val, len); }
/**
* \brief Append the contents of another vector.
*
* The other vector is left unchanged. Copy constructors are used to place
* the elements in the vector.
*/
void append(const SVector &v)
{ replace(BaseTable::length(), v.data, v.length()); }
/**
* \brief Append len copies of item.
*
* The copy constructor is used to place the item in the vector.
*/
void appendDup(const T &item, long len) { replaceDup(BaseTable::length(), item, len); }
/**
* \brief Append a single newly created item.
*
* The new element is initialized with the default constructor.
*/
void appendNew() { replaceNew(BaseTable::length(), 1); }
/**
* \brief Append len newly created items.
*
* The new elements are initialized with the default constructor.
*/
void appendNew(long len) { replaceNew(BaseTable::length(), len); }
/*@}*/
/*@{*/
/**
* \brief Prepend one elment to the front of the vector.
*
* Copy constructor is used to place the element in the vector.
*/
void prepend(const T &val) { insert(0, &val, 1); }
/**
* \brief Prepend len elements to the front of the vector.
*
* Copy constructors are used to place the elements in the vector.
*/
void prepend(const T *val, long len) { insert(0, val, len); }
/**
* \brief Prepend the contents of another vector.
*
* The other vector is left unchanged. Copy constructors are used to place
* the elements in the vector.
*/
void prepend(const SVector &v) { insert(0, v.data, v.length()); }
/**
* \brief Prepend len copies of item.
*
* The copy constructor is used to place the item in the vector.
*/
void prependDup(const T &item, long len) { insertDup(0, item, len); }
/**
* \brief Prepend a single newly created item.
*
* The new element is initialized with the default constructor.
*/
void prependNew() { insertNew(0, 1); }
/**
* \brief Prepend len newly created items.
*
* The new elements are initialized with the default constructor.
*/
void prependNew(long len) { insertNew(0, len); }
/*@}*/
/* Convenience access. */
T &operator[](int i) const { return BaseTable::data[i]; }
long size() const { return BaseTable::length(); }
/* Various classes for setting the iterator */
struct Iter;
struct IterFirst { IterFirst( const SVector &v ) : v(v) { } const SVector &v; };
struct IterLast { IterLast( const SVector &v ) : v(v) { } const SVector &v; };
struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
/**
* \brief Shared Vector Iterator.
* \ingroup iterators
*/
struct Iter
{
/* Construct, assign. */
Iter() : ptr(0), ptrBeg(0), ptrEnd(0) { }
/* Construct. */
Iter( const SVector &v );
Iter( const IterFirst &vf );
Iter( const IterLast &vl );
inline Iter( const IterNext &vn );
inline Iter( const IterPrev &vp );
/* Assign. */
Iter &operator=( const SVector &v );
Iter &operator=( const IterFirst &vf );
Iter &operator=( const IterLast &vl );
inline Iter &operator=( const IterNext &vf );
inline Iter &operator=( const IterPrev &vl );
/** \brief Less than end? */
bool lte() const { return ptr != ptrEnd; }
/** \brief At end? */
bool end() const { return ptr == ptrEnd; }
/** \brief Greater than beginning? */
bool gtb() const { return ptr != ptrBeg; }
/** \brief At beginning? */
bool beg() const { return ptr == ptrBeg; }
/** \brief At first element? */
bool first() const { return ptr == ptrBeg+1; }
/** \brief At last element? */
bool last() const { return ptr == ptrEnd-1; }
/* Return the position. */
long pos() const { return ptr - ptrBeg - 1; }
T &operator[](int i) const { return ptr[i]; }
/** \brief Implicit cast to T*. */
operator T*() const { return ptr; }
/** \brief Dereference operator returns T&. */
T &operator *() const { return *ptr; }
/** \brief Arrow operator returns T*. */
T *operator->() const { return ptr; }
/** \brief Move to next item. */
T *operator++() { return ++ptr; }
/** \brief Move to next item. */
T *operator++(int) { return ptr++; }
/** \brief Move to next item. */
T *increment() { return ++ptr; }
/** \brief Move to previous item. */
T *operator--() { return --ptr; }
/** \brief Move to previous item. */
T *operator--(int) { return ptr--; }
/** \brief Move to previous item. */
T *decrement() { return --ptr; }
/** \brief Return the next item. Does not modify this. */
inline IterNext next() const { return IterNext(*this); }
/** \brief Return the previous item. Does not modify this. */
inline IterPrev prev() const { return IterPrev(*this); }
/** \brief The iterator is simply a pointer. */
T *ptr;
/* For testing endpoints. */
T *ptrBeg, *ptrEnd;
};
/** \brief Return first element. */
IterFirst first() { return IterFirst( *this ); }
/** \brief Return last element. */
IterLast last() { return IterLast( *this ); }
protected:
void makeRawSpaceFor(long pos, long len);
void setAsCommon(long len);
long replaceCommon(long pos, long len);
long insertCommon(long pos, long len);
void upResize(long len);
void upResizeDup(long len);
void upResizeFromEmpty(long len);
void downResize(long len);
void downResizeDup(long len);
};
/**
* \brief Perform a shallow copy of the vector.
*
* Takes a reference to the contents of the other vector.
*/
template <class T, class Resize> SVector<T, Resize>::
SVector(const SVector<T, Resize> &v)
{
/* Take a reference to other, if any data is allocated. */
if ( v.data == 0 )
BaseTable::data = 0;
else {
/* Get the source header, up the refcount and ref it. */
STabHead *srcHead = ((STabHead*) v.data) - 1;
srcHead->refCount += 1;
BaseTable::data = (T*) (srcHead + 1);
}
}
/**
* \brief Shallow copy another vector into this vector.
*
* Takes a reference to the other vector. The contents of this vector are
* first emptied.
*
* \returns A reference to this.
*/
template <class T, class Resize> SVector<T, Resize> &
SVector<T, Resize>:: operator=( const SVector &v )
{
/* First clean out the current contents. */
empty();
/* Take a reference to other, if any data is allocated. */
if ( v.data == 0 )
BaseTable::data = 0;
else {
/* Get the source header, up the refcount and ref it. */
STabHead *srcHead = ((STabHead*) v.data) - 1;
srcHead->refCount += 1;
BaseTable::data = (T*) (srcHead + 1);
}
return *this;
}
/* Init a vector iterator with just a vector. */
template <class T, class Resize> SVector<T, Resize>::
Iter::Iter( const SVector &v )
{
long length;
if ( v.data == 0 || (length=(((STabHead*)v.data)-1)->tabLen) == 0 )
ptr = ptrBeg = ptrEnd = 0;
else {
ptr = v.data;
ptrBeg = v.data-1;
ptrEnd = v.data+length;
}
}
/* Init a vector iterator with the first of a vector. */
template <class T, class Resize> SVector<T, Resize>::
Iter::Iter( const IterFirst &vf )
{
long length;
if ( vf.v.data == 0 || (length=(((STabHead*)vf.v.data)-1)->tabLen) == 0 )
ptr = ptrBeg = ptrEnd = 0;
else {
ptr = vf.v.data;
ptrBeg = vf.v.data-1;
ptrEnd = vf.v.data+length;
}
}
/* Init a vector iterator with the last of a vector. */
template <class T, class Resize> SVector<T, Resize>::
Iter::Iter( const IterLast &vl )
{
long length;
if ( vl.v.data == 0 || (length=(((STabHead*)vl.v.data)-1)->tabLen) == 0 )
ptr = ptrBeg = ptrEnd = 0;
else {
ptr = vl.v.data+length-1;
ptrBeg = vl.v.data-1;
ptrEnd = vl.v.data+length;
}
}
/* Init a vector iterator with the next of some other iterator. */
template <class T, class Resize> SVector<T, Resize>::
Iter::Iter( const IterNext &vn )
:
ptr(vn.i.ptr+1),
ptrBeg(vn.i.ptrBeg),
ptrEnd(vn.i.ptrEnd)
{
}
/* Init a vector iterator with the prev of some other iterator. */
template <class T, class Resize> SVector<T, Resize>::
Iter::Iter( const IterPrev &vp )
:
ptr(vp.i.ptr-1),
ptrBeg(vp.i.ptrBeg),
ptrEnd(vp.i.ptrEnd)
{
}
/* Set a vector iterator with some vector. */
template <class T, class Resize> typename SVector<T, Resize>::Iter &
SVector<T, Resize>::Iter::operator=( const SVector &v )
{
long length;
if ( v.data == 0 || (length=(((STabHead*)v.data)-1)->tabLen) == 0 )
ptr = ptrBeg = ptrEnd = 0;
else {
ptr = v.data;
ptrBeg = v.data-1;
ptrEnd = v.data+length;
}
return *this;
}
/* Set a vector iterator with the first element in a vector. */
template <class T, class Resize> typename SVector<T, Resize>::Iter &
SVector<T, Resize>::Iter::operator=( const IterFirst &vf )
{
long length;
if ( vf.v.data == 0 || (length=(((STabHead*)vf.v.data)-1)->tabLen) == 0 )
ptr = ptrBeg = ptrEnd = 0;
else {
ptr = vf.v.data;
ptrBeg = vf.v.data-1;
ptrEnd = vf.v.data+length;
}
return *this;
}
/* Set a vector iterator with the last element in a vector. */
template <class T, class Resize> typename SVector<T, Resize>::Iter &
SVector<T, Resize>::Iter::operator=( const IterLast &vl )
{
long length;
if ( vl.v.data == 0 || (length=(((STabHead*)vl.v.data)-1)->tabLen) == 0 )
ptr = ptrBeg = ptrEnd = 0;
else {
ptr = vl.v.data+length-1;
ptrBeg = vl.v.data-1;
ptrEnd = vl.v.data+length;
}
return *this;
}
/* Set a vector iterator with the next of some other iterator. */
template <class T, class Resize> typename SVector<T, Resize>::Iter &
SVector<T, Resize>::Iter::operator=( const IterNext &vn )
{
ptr = vn.i.ptr+1;
ptrBeg = vn.i.ptrBeg;
ptrEnd = vn.i.ptrEnd;
return *this;
}
/* Set a vector iterator with the prev of some other iterator. */
template <class T, class Resize> typename SVector<T, Resize>::Iter &
SVector<T, Resize>::Iter::operator=( const IterPrev &vp )
{
ptr = vp.i.ptr-1;
ptrBeg = vp.i.ptrBeg;
ptrEnd = vp.i.ptrEnd;
return *this;
}
/* Up resize the data for len elements using Resize::upResize to tell us the
* new length. Reads and writes allocLen. Does not read or write length.
* Assumes that there is some data allocated already. */
template <class T, class Resize> void SVector<T, Resize>::
upResize(long len)
{
/* Get the current header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* Ask the resizer what the new length will be. */
long newLen = Resize::upResize(head->allocLen, len);
/* Did the data grow? */
if ( newLen > head->allocLen ) {
/* Table exists already, resize it up. */
head = (STabHead*) anti_leak_pool->reallocate(head, sizeof(STabHead) + sizeof(T) * head->allocLen, sizeof(STabHead) + sizeof(T) * newLen);
if ( head == 0 )
throw std::bad_alloc();
head->allocLen = newLen;
/* Save the data pointer. */
BaseTable::data = (T*) (head + 1);
}
}
/* Allocates a new buffer for an up resize that requires a duplication of the
* data. Uses Resize::upResize to get the allocation length. Reads and writes
* allocLen. This upResize does write the new length. Assumes that there is
* some data allocated already. */
template <class T, class Resize> void SVector<T, Resize>::
upResizeDup(long len)
{
/* Get the current header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* Ask the resizer what the new length will be. */
long newLen = Resize::upResize(head->allocLen, len);
/* Dereferencing the existing data, decrement the refcount. */
head->refCount -= 1;
/* Table exists already, resize it up. */
head = (STabHead*) anti_leak_pool->allocate( sizeof(STabHead) + sizeof(T) * newLen );
if ( head == 0 )
throw std::bad_alloc();
head->refCount = 1;
head->allocLen = newLen;
head->tabLen = len;
/* Save the data pointer. */
BaseTable::data = (T*) (head + 1);
}
/* Up resize the data for len elements using Resize::upResize to tell us the
* new length. Reads and writes allocLen. This upresize DOES write length.
* Assumes that no data is allocated. */
template <class T, class Resize> void SVector<T, Resize>::
upResizeFromEmpty(long len)
{
/* There is no table yet. If the len is zero, then there is no need to
* create a table. */
if ( len > 0 ) {
/* Ask the resizer what the new length will be. */
long newLen = Resize::upResize(0, len);
/* If len is greater than zero then we are always allocating the table. */
STabHead *head = (STabHead*) anti_leak_pool->allocate( sizeof(STabHead) +
sizeof(T) * newLen );
if ( head == 0 )
throw std::bad_alloc();
/* Set up the header and save the data pointer. Note that we set the
* length here. This differs from the other upResizes. */
head->refCount = 1;
head->allocLen = newLen;
head->tabLen = len;
BaseTable::data = (T*) (head + 1);
}
}
/* Down resize the data for len elements using Resize::downResize to determine
* the new length. Reads and writes allocLen. Does not read or write length. */
template <class T, class Resize> void SVector<T, Resize>::
downResize(long len)
{
/* If there is already no length, then there is nothing we can do. */
if ( BaseTable::data != 0 ) {
/* Get the current header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* Ask the resizer what the new length will be. */
long newLen = Resize::downResize( head->allocLen, len );
/* Did the data shrink? */
if ( newLen < head->allocLen ) {
if ( newLen == 0 ) {
/* Simply free the data. */
anti_leak_pool->deallocate( head, sizeof(STabHead) + sizeof(T) * head->allocLen);
BaseTable::data = 0;
}
else {
/* Not shrinking to size zero, realloc it to the smaller size. */
head = (STabHead*) anti_leak_pool->reallocate( head, sizeof(STabHead) + sizeof(T) * head->allocLen, sizeof(STabHead) + sizeof(T) * newLen );
if ( head == 0 )
throw std::bad_alloc();
/* Save the new allocated length. */
head->allocLen = newLen;
/* Save the new data ptr. */
BaseTable::data = (T*) (head + 1);
}
}
}
}
/* Allocate a new buffer for a down resize and duplication of the array. The
* new array will be len long and allocation size will be determined using
* Resize::downResize with the old array's allocLen. Does not actually copy
* any data. Reads and writes allocLen and writes the new len. */
template <class T, class Resize> void SVector<T, Resize>::
downResizeDup(long len)
{
/* If there is already no length, then there is nothing we can do. */
if ( BaseTable::data != 0 ) {
/* Get the current header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* Ask the resizer what the new length will be. */
long newLen = Resize::downResize( head->allocLen, len );
/* Detaching from the existing head, decrement the refcount. */
head->refCount -= 1;
/* Not shrinking to size zero, malloc it to the smaller size. */
head = (STabHead*) anti_leak_pool->allocate( sizeof(STabHead) + sizeof(T) * newLen );
if ( head == 0 )
throw std::bad_alloc();
/* Save the new allocated length. */
head->refCount = 1;
head->allocLen = newLen;
head->tabLen = len;
/* Save the data pointer. */
BaseTable::data = (T*) (head + 1);
}
}
/**
* \brief Free all memory used by the vector.
*
* The vector is reset to zero elements. Destructors are called on all
* elements in the vector. The space allocated for the vector is freed.
*/
template <class T, class Resize> void SVector<T, Resize>::
empty()
{
if ( BaseTable::data != 0 ) {
/* Get the header and drop the refcount on the data. */
STabHead *head = ((STabHead*) BaseTable::data) - 1;
head->refCount -= 1;
/* If the refcount just went down to zero nobody else is referencing
* the data. */
if ( head->refCount == 0 ) {
/* Call All destructors. */
T *pos = BaseTable::data;
for ( long i = 0; i < head->tabLen; pos++, i++ )
pos->~T();
/* Free the data space. */
anti_leak_pool->deallocate( head, sizeof(STabHead) + sizeof(T) * head->allocLen);
}
/* Clear the pointer. */
BaseTable::data = 0;
}
}
/* Prepare for setting the contents of the vector to some array len long.
* Handles reusing the existing space, detaching from a common space or
* growing from zero length automatically. */
template <class T, class Resize> void SVector<T, Resize>::
setAsCommon(long len)
{
if ( BaseTable::data != 0 ) {
/* Get the header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* If the refCount is one, then we can reuse the space. Otherwise we
* must detach from the referenced data create new space. */
if ( head->refCount == 1 ) {
/* Call All destructors. */
T *pos = BaseTable::data;
for ( long i = 0; i < head->tabLen; pos++, i++ )
pos->~T();
/* Adjust the allocated length. */
if ( len < head->tabLen )
downResize( len );
else if ( len > head->tabLen )
upResize( len );
if ( BaseTable::data != 0 ) {
/* Get the header again and set the length. */
head = ((STabHead*)BaseTable::data) - 1;
head->tabLen = len;
}
}
else {
/* Just detach from the data. */
head->refCount -= 1;
BaseTable::data = 0;
/* Make enough space. This will set the length. */
upResizeFromEmpty( len );
}
}
else {
/* The table is currently empty. Make enough space. This will set the
* length. */
upResizeFromEmpty( len );
}
}
/**
* \brief Set the contents of the vector to be len elements exactly.
*
* The vector becomes len elements in length. Destructors are called on any
* existing elements in the vector. Copy constructors are used to place the
* new elements in the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
setAs(const T *val, long len)
{
/* Common stuff for setting the array to len long. */
setAsCommon( len );
/* Copy data in. */
T *dst = BaseTable::data;
const T *src = val;
for ( long i = 0; i < len; i++, dst++, src++ )
new(dst) T(*src);
}
/**
* \brief Set the vector to len copies of item.
*
* The vector becomes len elements in length. Destructors are called on any
* existing elements in the vector. The element's copy constructor is used to
* copy the item into the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
setAsDup(const T &item, long len)
{
/* Do the common stuff for setting the array to len long. */
setAsCommon( len );
/* Copy item in one spot at a time. */
T *dst = BaseTable::data;
for ( long i = 0; i < len; i++, dst++ )
new(dst) T(item);
}
/**
* \brief Set the vector to exactly len new items.
*
* The vector becomes len elements in length. Destructors are called on any
* existing elements in the vector. Default constructors are used to init the
* new items.
*/
template <class T, class Resize> void SVector<T, Resize>::
setAsNew(long len)
{
/* Do the common stuff for setting the array to len long. */
setAsCommon( len );
/* Create items using default constructor. */
T *dst = BaseTable::data;
for ( long i = 0; i < len; i++, dst++ )
new(dst) T();
}
/* Make space in vector for a replacement at pos of len items. Handles reusing
* existing space, detaching or growing from zero space. */
template <class T, class Resize> long SVector<T, Resize>::
replaceCommon(long pos, long len)
{
if ( BaseTable::data != 0 ) {
/* Get the header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* If we are given a negative position to replace at then treat it as
* a position relative to the length. This doesn't have any meaning
* unless the length is at least one. */
if ( pos < 0 )
pos = head->tabLen + pos;
/* The end is the one past the last item that we want to write to. */
long i, endPos = pos + len;
if ( head->refCount == 1 ) {
/* We can reuse the space. Make sure we have enough space. */
if ( endPos > head->tabLen ) {
upResize( endPos );
/* Get the header again, whose addr may have changed after
* resizing. */
head = ((STabHead*)BaseTable::data) - 1;
/* Delete any objects we need to delete. */
T *item = BaseTable::data + pos;
for ( i = pos; i < head->tabLen; i++, item++ )
item->~T();
/* We are extending the vector, set the new data length. */
head->tabLen = endPos;
}
else {
/* Delete any objects we need to delete. */
T *item = BaseTable::data + pos;
for ( i = pos; i < endPos; i++, item++ )
item->~T();
}
}
else {
/* Use endPos to calc the end of the vector. */
long newLen = endPos;
if ( newLen < head->tabLen )
newLen = head->tabLen;
/* Duplicate and grow up to endPos. This will set the length. */
upResizeDup( newLen );
/* Copy from src up to pos. */
const T *src = (T*) (head + 1);
T *dst = BaseTable::data;
for ( i = 0; i < pos; i++, dst++, src++)
new(dst) T(*src);
/* Copy any items after the replace range. */
for ( i += len, src += len, dst += len;
i < head->tabLen; i++, dst++, src++ )
new(dst) T(*src);
}
}
else {
/* There is no data initially, must grow from zero. This will set the
* new length. */
upResizeFromEmpty( len );
}
return pos;
}
/**
* \brief Replace len elements at position pos.
*
* If there are existing elements at the positions to be replaced, then
* destructors are called before the space is used. Copy constructors are used
* to place the elements into the vector. It is allowable for the pos and
* length to specify a replacement that overwrites existing elements and
* creates new ones. If pos is greater than the length of the vector then
* undefined behaviour results. If pos is negative, then it is treated as an
* offset relative to the length of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
replace(long pos, const T *val, long len)
{
/* Common work for replacing in the vector. */
pos = replaceCommon( pos, len );
/* Copy data in using copy constructor. */
T *dst = BaseTable::data + pos;
const T *src = val;
for ( long i = 0; i < len; i++, dst++, src++ )
new(dst) T(*src);
}
/**
* \brief Replace at position pos with len copies of an item.
*
* If there are existing elements at the positions to be replaced, then
* destructors are called before the space is used. The copy constructor is
* used to place the element into this vector. It is allowable for the pos and
* length to specify a replacement that overwrites existing elements and
* creates new ones. If pos is greater than the length of the vector then
* undefined behaviour results. If pos is negative, then it is treated as an
* offset relative to the length of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
replaceDup(long pos, const T &val, long len)
{
/* Common replacement stuff. */
pos = replaceCommon( pos, len );
/* Copy data in using copy constructor. */
T *dst = BaseTable::data + pos;
for ( long i = 0; i < len; i++, dst++ )
new(dst) T(val);
}
/**
* \brief Replace at position pos with len new elements.
*
* If there are existing elements at the positions to be replaced, then
* destructors are called before the space is used. The default constructor is
* used to initialize the new elements. It is allowable for the pos and length
* to specify a replacement that overwrites existing elements and creates new
* ones. If pos is greater than the length of the vector then undefined
* behaviour results. If pos is negative, then it is treated as an offset
* relative to the length of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
replaceNew(long pos, long len)
{
/* Do the common replacement stuff. */
pos = replaceCommon( pos, len );
/* Copy data in using copy constructor. */
T *dst = BaseTable::data + pos;
for ( long i = 0; i < len; i++, dst++ )
new(dst) T();
}
/**
* \brief Remove len elements at position pos.
*
* Destructor is called on all elements removed. Elements to the right of pos
* are shifted len spaces to the left to take up the free space. If pos is
* greater than or equal to the length of the vector then undefined behavior
* results. If pos is negative then it is treated as an offset relative to the
* length of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
remove(long pos, long len)
{
/* If there is no data, we can't delete anything anyways. */
if ( BaseTable::data != 0 ) {
/* Get the header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* If we are given a negative position to remove at then
* treat it as a position relative to the length. */
if ( pos < 0 )
pos = head->tabLen + pos;
/* The first position after the last item deleted. */
long endPos = pos + len;
/* The New data length. */
long i, newLen = head->tabLen - len;
if ( head->refCount == 1 ) {
/* We are the only ones using the data. We can reuse
* the existing space. */
/* The place in the data we are deleting at. */
T *dst = BaseTable::data + pos;
/* Call Destructors. */
T *item = BaseTable::data + pos;
for ( i = 0; i < len; i += 1, item += 1 )
item->~T();
/* Shift data over if necessary. */
long lenToSlideOver = head->tabLen - endPos;
if ( len > 0 && lenToSlideOver > 0 )
memmove(BaseTable::data + pos, dst + len, sizeof(T)*lenToSlideOver);
/* Shrink the data if necessary. */
downResize( newLen );
if ( BaseTable::data != 0 ) {
/* Get the header again (because of the resize) and set the
* new data length. */
head = ((STabHead*)BaseTable::data) - 1;
head->tabLen = newLen;
}
}
else {
/* Must detach from the common data. Just copy the non-deleted
* items from the common data. */
/* Duplicate and grow down to newLen. This will set the length. */
downResizeDup( newLen );
/* Copy over just the non-deleted parts. */
const T *src = (T*) (head + 1);
T *dst = BaseTable::data;
for ( i = 0; i < pos; i++, dst++, src++ )
new(dst) T(*src);
/* ... and the second half. */
for ( i += len, src += len; i < head->tabLen; i++, src++, dst++ )
new(dst) T(*src);
}
}
}
/* Shift over existing data. Handles reusing existing space, detaching or
* growing from zero space. */
template <class T, class Resize> long SVector<T, Resize>::
insertCommon(long pos, long len)
{
if ( BaseTable::data != 0 ) {
/* Get the header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* If we are given a negative position to insert at then treat it as a
* position relative to the length. This only has meaning if there is
* existing data. */
if ( pos < 0 )
pos = head->tabLen + pos;
/* Calculate the new length. */
long i, newLen = head->tabLen + len;
if ( head->refCount == 1 ) {
/* Up resize, we are growing. */
upResize( newLen );
/* Get the header again, (the addr may have changed after
* resizing). */
head = ((STabHead*)BaseTable::data) - 1;
/* Shift over data at insert spot if needed. */
if ( len > 0 && pos < head->tabLen ) {
memmove( BaseTable::data + pos + len, BaseTable::data + pos,
sizeof(T)*(head->tabLen - pos) );
}
/* Grow the length by the len inserted. */
head->tabLen += len;
}
else {
/* Need to detach from the existing array. Copy over the other
* parts. This will set the length. */
upResizeDup( newLen );
/* Copy over the parts around the insert. */
const T *src = (T*) (head + 1);
T *dst = BaseTable::data;
for ( i = 0; i < pos; i++, dst++, src++ )
new(dst) T(*src);
/* ... and the second half. */
for ( dst += len; i < head->tabLen; i++, src++, dst++ )
new(dst) T(*src);
}
}
else {
/* There is no existing data. Start from zero. This will set the
* length. */
upResizeFromEmpty( len );
}
return pos;
}
/**
* \brief Insert len elements at position pos.
*
* Elements in the vector from pos onward are shifted len spaces to the right.
* The copy constructor is used to place the elements into this vector. If pos
* is greater than the length of the vector then undefined behaviour results.
* If pos is negative then it is treated as an offset relative to the length
* of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
insert(long pos, const T *val, long len)
{
/* Do the common insertion stuff. */
pos = insertCommon( pos, len );
/* Copy data in element by element. */
T *dst = BaseTable::data + pos;
const T *src = val;
for ( long i = 0; i < len; i++, dst++, src++ )
new(dst) T(*src);
}
/**
* \brief Insert len copies of item at position pos.
*
* Elements in the vector from pos onward are shifted len spaces to the right.
* The copy constructor is used to place the element into this vector. If pos
* is greater than the length of the vector then undefined behaviour results.
* If pos is negative then it is treated as an offset relative to the length
* of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
insertDup(long pos, const T &item, long len)
{
/* Do the common insertion stuff. */
pos = insertCommon( pos, len );
/* Copy the data item in one at a time. */
T *dst = BaseTable::data + pos;
for ( long i = 0; i < len; i++, dst++ )
new(dst) T(item);
}
/**
* \brief Insert len new elements using the default constructor.
*
* Elements in the vector from pos onward are shifted len spaces to the right.
* Default constructors are used to init the new elements. If pos is off the
* end of the vector then undefined behaviour results. If pos is negative then
* it is treated as an offset relative to the length of the vector.
*/
template <class T, class Resize> void SVector<T, Resize>::
insertNew(long pos, long len)
{
/* Do the common insertion stuff. */
pos = insertCommon( pos, len );
/* Init new data with default constructors. */
T *dst = BaseTable::data + pos;
for ( long i = 0; i < len; i++, dst++ )
new(dst) T();
}
/* Makes space for len items, Does not init the items in any way. If pos is
* greater than the length of the vector then undefined behaviour results.
* Updates the length of the vector. */
template <class T, class Resize> void SVector<T, Resize>::
makeRawSpaceFor(long pos, long len)
{
if ( BaseTable::data != 0 ) {
/* Get the header. */
STabHead *head = ((STabHead*)BaseTable::data) - 1;
/* Calculate the new length. */
long i, newLen = head->tabLen + len;
if ( head->refCount == 1 ) {
/* Up resize, we are growing. */
upResize( newLen );
/* Get the header again, (the addr may have changed after
* resizing). */
head = ((STabHead*)BaseTable::data) - 1;
/* Shift over data at insert spot if needed. */
if ( len > 0 && pos < head->tabLen ) {
memmove( BaseTable::data + pos + len, BaseTable::data + pos,
sizeof(T)*(head->tabLen - pos) );
}
/* Grow the length by the len inserted. */
head->tabLen += len;
}
else {
/* Need to detach from the existing array. Copy over the other
* parts. This will set the length. */
upResizeDup( newLen );
/* Copy over the parts around the insert. */
const T *src = (T*) (head + 1);
T *dst = BaseTable::data;
for ( i = 0; i < pos; i++, dst++, src++ )
new(dst) T(*src);
/* ... and the second half. */
for ( dst += len; i < head->tabLen; i++, src++, dst++ )
new(dst) T(*src);
}
}
else {
/* There is no existing data. Start from zero. This will set the
* length. */
upResizeFromEmpty( len );
}
}
#ifdef AAPL_NAMESPACE
}
#endif
#endif /* _AAPL_SVECTOR_H */