aapl/svector.h

   1 /*
   2  *  Copyright 2002, 2006 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _AAPL_SVECTOR_H
  23 #define _AAPL_SVECTOR_H
  24
  25 #include <new>
  26 #include <string.h>
  27 #include <stdlib.h>
  28 #include <assert.h>
  29 #include "table.h"
  30
  31 #ifdef AAPL_NAMESPACE
  32 namespace Aapl {
  33 #endif
  34
  35 /**
  36  * \addtogroup vector
  37  * @{
  38  */
  39
  40 /** \class SVector
  41  * \brief Copy-on-write dynamic array.
  42  *
  43  * SVector is a variant of Vector that employs copy-on-write behaviour. The
  44  * SVector copy constructor and = operator make shallow copies. If a vector
  45  * that references shared data is modified with insert, replace, append,
  46  * prepend, setAs or remove, a new copy is made so as not to interfere with
  47  * the shared data. However, shared individual elements may be modified by
  48  * bypassing the SVector interface.
  49  *
  50  * SVector is a dynamic array that can be used to contain complex data
  51  * structures that have constructors and destructors as well as simple types
  52  * such as integers and pointers.
  53  *
  54  * SVector supports inserting, overwriting, and removing single or multiple
  55  * elements at once. Constructors and destructors are called wherever
  56  * appropriate.  For example, before an element is overwritten, it's
  57  * destructor is called.
  58  *
  59  * SVector provides automatic resizing of allocated memory as needed and
  60  * offers different allocation schemes for controlling how the automatic
  61  * allocation is done.  Two senses of the the length of the data is
  62  * maintained: the amount of raw memory allocated to the vector and the number
  63  * of actual elements in the vector. The various allocation schemes control
  64  * how the allocated space is changed in relation to the number of elements in
  65  * the vector.
  66  */
  67
  68 /*@}*/
  69
  70 /* SVector */
  71 template < class T, class Resize = ResizeExpn > class SVector :
  72         public STable<T>, public Resize
  73 {
  74 private:
  75         typedef STable<T> BaseTable;
  76
  77 public:
  78         /**
  79          * \brief Initialize an empty vector with no space allocated.
  80          *
  81          * If a linear resizer is used, the step defaults to 256 units of T. For a
  82          * runtime vector both up and down allocation schemes default to
  83          * Exponential.
  84          */
  85         SVector() { }
  86
  87         /**
  88          * \brief Create a vector that contains an initial element.
  89          *
  90          * The vector becomes one element in length. The element's copy
  91          * constructor is used to place the value in the vector.
  92          */
  93         SVector(const T &val)             { setAs(&val, 1); }
  94
  95         /**
  96          * \brief Create a vector that contains an array of elements.
  97          *
  98          * The vector becomes len elements in length.  Copy constructors are used
  99          * to place the new elements in the vector.
 100          */
 101         SVector(const T *val, long len)   { setAs(val, len); }
 102
 103         /* Shallow copy. */
 104         SVector( const SVector &v );
 105
 106         /* Shallow copy. */
 107         SVector(STabHead *head);
 108
 109         /**
 110          * \brief Free all memory used by the vector.
 111          *
 112          * The vector is reset to zero elements. Destructors are called on all
 113          * elements in the vector. The space allocated for the vector is freed.
 114          */
 115         ~SVector() { empty(); }
 116
 117         /* Delete all items. */
 118         void empty();
 119
 120         /**
 121          * \brief Deep copy another vector into this vector.
 122          *
 123          * Copies the entire contents of the other vector into this vector. Any
 124          * existing contents are first deleted. Equivalent to setAs.
 125          */
 126         void deepCopy( const SVector &v )     { setAs(v.data, v.length()); }
 127
 128         /* Perform a shallow copy of another vector. */
 129         SVector &operator=( const SVector &v );
 130
 131         /* Perform a shallow copy of another vector by the header. */
 132         SVector &operator=( STabHead *head );
 133
 134
 135         /*@{*/
 136         /**
 137          * \brief Insert one element at position pos.
 138          *
 139          * Elements in the vector from pos onward are shifted one space to the
 140          * right. The copy constructor is used to place the element into this
 141          * vector. If pos is greater than the length of the vector then undefined
 142          * behaviour results. If pos is negative then it is treated as an offset
 143          * relative to the length of the vector.
 144          */
 145         void insert(long pos, const T &val)     { insert(pos, &val, 1); }
 146
 147         /* Insert an array of values. */
 148         void insert(long pos, const T *val, long len);
 149
 150         /**
 151          * \brief Insert all the elements from another vector at position pos.
 152          *
 153          * Elements in this vector from pos onward are shifted v.length() spaces
 154          * to the right. The element's copy constructor is used to copy the items
 155          * into this vector. The other vector is left unchanged. If pos is off the
 156          * end of the vector, then undefined behaviour results. If pos is negative
 157          * then it is treated as an offset relative to the length of the vector.
 158          * Equivalent to vector.insert(pos, other.data, other.length()).
 159          */
 160         void insert(long pos, const SVector &v) { insert(pos, v.data, v.length()); }
 161
 162         /* Insert len copies of val into the vector. */
 163         void insertDup(long pos, const T &val, long len);
 164
 165         /**
 166          * \brief Insert one new element using the default constrcutor.
 167          *
 168          * Elements in the vector from pos onward are shifted one space to the right.
 169          * The default constructor is used to init the new element. If pos is greater
 170          * than the length of the vector then undefined behaviour results. If pos is
 171          * negative then it is treated as an offset relative to the length of the
 172          * vector.
 173          */
 174         void insertNew(long pos)                { insertNew(pos, 1); }
 175
 176         /* Insert len new items using default constructor. */
 177         void insertNew(long pos, long len);
 178         /*@}*/
 179
 180         /*@{*/
 181         /**
 182          * \brief Remove one element at position pos.
 183          *
 184          * The element's destructor is called. Elements to the right of pos are
 185          * shifted one space to the left to take up the free space. If pos is greater
 186          * than or equal to the length of the vector then undefined behavior results.
 187          * If pos is negative then it is treated as an offset relative to the length
 188          * of the vector.
 189          */
 190         void remove(long pos)                   { remove(pos, 1); }
 191
 192         /* Delete a number of elements. */
 193         void remove(long pos, long len);
 194         /*@}*/
 195
 196         /*@{*/
 197         /**
 198          * \brief Replace one element at position pos.
 199          *
 200          * If there is an existing element at position pos (if pos is less than the
 201          * length of the vector) then its destructor is called before the space is
 202          * used. The copy constructor is used to place the element into the vector.
 203          * If pos is greater than the length of the vector then undefined behaviour
 204          * results.  If pos is negative then it is treated as an offset relative to
 205          * the length of the vector.
 206          */
 207         void replace(long pos, const T &val)     { replace(pos, &val, 1); }
 208
 209         /* Replace with an array of values. */
 210         void replace(long pos, const T *val, long len);
 211
 212         /**
 213          * \brief Replace at position pos with all the elements of another vector.
 214          *
 215          * Replace at position pos with all the elements of another vector. The other
 216          * vector is left unchanged. If there are existing elements at the positions
 217          * to be replaced, then destructors are called before the space is used. Copy
 218          * constructors are used to place the elements into this vector. It is
 219          * allowable for the pos and length of the other vector to specify a
 220          * replacement that overwrites existing elements and creates new ones.  If pos
 221          * is greater than the length of the vector then undefined behaviour results.
 222          * If pos is negative, then it is treated as an offset relative to the length
 223          * of the vector.
 224          */
 225         void replace(long pos, const SVector &v) { replace(pos, v.data, v.length()); }
 226
 227         /* Replace len items with len copies of val. */
 228         void replaceDup(long pos, const T &val, long len);
 229
 230         /**
 231          * \brief Replace at position pos with one new element.
 232          *
 233          * If there is an existing element at the position to be replaced (pos is
 234          * less than the length of the vector) then the element's destructor is
 235          * called before the space is used. The default constructor is used to
 236          * initialize the new element. If pos is greater than the length of the
 237          * vector then undefined behaviour results. If pos is negative, then it is
 238          * treated as an offset relative to the length of the vector.
 239          */
 240         void replaceNew(long pos)                { replaceNew(pos, 1); }
 241
 242         /* Replace len items at pos with newly constructed objects. */
 243         void replaceNew(long pos, long len);
 244         /*@}*/
 245
 246         /*@{*/
 247
 248         /**
 249          * \brief Set the contents of the vector to be val exactly.
 250          *
 251          * The vector becomes one element in length. Destructors are called on any
 252          * existing elements in the vector. The element's copy constructor is used to
 253          * place the val in the vector.
 254          */
 255         void setAs(const T &val)             { setAs(&val, 1); }
 256
 257         /* Set to the contents of an array. */
 258         void setAs(const T *val, long len);
 259
 260         /**
 261          * \brief Set the vector to exactly the contents of another vector.
 262          *
 263          * The vector becomes v.length() elements in length. Destructors are called
 264          * on any existing elements. Copy constructors are used to place the new
 265          * elements in the vector.
 266          */
 267         void setAs(const SVector &v)         { setAs(v.data, v.length()); }
 268
 269         /* Set as len copies of item. */
 270         void setAsDup(const T &item, long len);
 271
 272         /**
 273          * \brief Set the vector to exactly one new item.
 274          *
 275          * The vector becomes one element in length. Destructors are called on any
 276          * existing elements in the vector. The default constructor is used to
 277          * init the new item.
 278          */
 279         void setAsNew()                      { setAsNew(1); }
 280
 281         /* Set as newly constructed objects using the default constructor. */
 282         void setAsNew(long len);
 283         /*@}*/
 284
 285         /*@{*/
 286         /**
 287          * \brief Append one elment to the end of the vector.
 288          *
 289          * Copy constructor is used to place the element in the vector.
 290          */
 291         void append(const T &val)                { replace(BaseTable::length(), &val, 1); }
 292
 293         /**
 294          * \brief Append len elements to the end of the vector.
 295          *
 296          * Copy constructors are used to place the elements in the vector.
 297          */
 298         void append(const T *val, long len)       { replace(BaseTable::length(), val, len); }
 299
 300         /**
 301          * \brief Append the contents of another vector.
 302          *
 303          * The other vector is left unchanged. Copy constructors are used to place
 304          * the elements in the vector.
 305          */
 306         void append(const SVector &v)
 307                         { replace(BaseTable::length(), v.data, v.length()); }
 308
 309         /**
 310          * \brief Append len copies of item.
 311          *
 312          * The copy constructor is used to place the item in the vector.
 313          */
 314         void appendDup(const T &item, long len)   { replaceDup(BaseTable::length(), item, len); }
 315
 316         /**
 317          * \brief Append a single newly created item.
 318          *
 319          * The new element is initialized with the default constructor.
 320          */
 321         void appendNew()                         { replaceNew(BaseTable::length(), 1); }
 322
 323         /**
 324          * \brief Append len newly created items.
 325          *
 326          * The new elements are initialized with the default constructor.
 327          */
 328         void appendNew(long len)                  { replaceNew(BaseTable::length(), len); }
 329         /*@}*/
 330
 331
 332         /*@{*/
 333         /**
 334          * \brief Prepend one elment to the front of the vector.
 335          *
 336          * Copy constructor is used to place the element in the vector.
 337          */
 338         void prepend(const T &val)               { insert(0, &val, 1); }
 339
 340         /**
 341          * \brief Prepend len elements to the front of the vector.
 342          *
 343          * Copy constructors are used to place the elements in the vector.
 344          */
 345         void prepend(const T *val, long len)      { insert(0, val, len); }
 346
 347         /**
 348          * \brief Prepend the contents of another vector.
 349          *
 350          * The other vector is left unchanged. Copy constructors are used to place
 351          * the elements in the vector.
 352          */
 353         void prepend(const SVector &v)           { insert(0, v.data, v.length()); }
 354
 355         /**
 356          * \brief Prepend len copies of item.
 357          *
 358          * The copy constructor is used to place the item in the vector.
 359          */
 360         void prependDup(const T &item, long len)  { insertDup(0, item, len); }
 361
 362         /**
 363          * \brief Prepend a single newly created item.
 364          *
 365          * The new element is initialized with the default constructor.
 366          */
 367         void prependNew()                        { insertNew(0, 1); }
 368
 369         /**
 370          * \brief Prepend len newly created items.
 371          *
 372          * The new elements are initialized with the default constructor.
 373          */
 374         void prependNew(long len)                 { insertNew(0, len); }
 375         /*@}*/
 376
 377         /* Convenience access. */
 378         T &operator[](int i) const { return BaseTable::data[i]; }
 379         long size() const           { return BaseTable::length(); }
 380
 381         /* Various classes for setting the iterator */
 382         struct Iter;
 383         struct IterFirst { IterFirst( const SVector &v ) : v(v) { } const SVector &v; };
 384         struct IterLast { IterLast( const SVector &v ) : v(v) { } const SVector &v; };
 385         struct IterNext { IterNext( const Iter &i ) : i(i) { } const Iter &i; };
 386         struct IterPrev { IterPrev( const Iter &i ) : i(i) { } const Iter &i; };
 387
 388         /**
 389          * \brief Shared Vector Iterator.
 390          * \ingroup iterators
 391          */
 392         struct Iter
 393         {
 394                 /* Construct, assign. */
 395                 Iter() : ptr(0), ptrBeg(0), ptrEnd(0) { }
 396
 397                 /* Construct. */
 398                 Iter( const SVector &v );
 399                 Iter( const IterFirst &vf );
 400                 Iter( const IterLast &vl );
 401                 inline Iter( const IterNext &vn );
 402                 inline Iter( const IterPrev &vp );
 403
 404                 /* Assign. */
 405                 Iter &operator=( const SVector &v );
 406                 Iter &operator=( const IterFirst &vf );
 407                 Iter &operator=( const IterLast &vl );
 408                 inline Iter &operator=( const IterNext &vf );
 409                 inline Iter &operator=( const IterPrev &vl );
 410
 411                 /** \brief Less than end? */
 412                 bool lte() const { return ptr != ptrEnd; }
 413
 414                 /** \brief At end? */
 415                 bool end() const { return ptr == ptrEnd; }
 416
 417                 /** \brief Greater than beginning? */
 418                 bool gtb() const { return ptr != ptrBeg; }
 419
 420                 /** \brief At beginning? */
 421                 bool beg() const { return ptr == ptrBeg; }
 422
 423                 /** \brief At first element? */
 424                 bool first() const { return ptr == ptrBeg+1; }
 425
 426                 /** \brief At last element? */
 427                 bool last() const { return ptr == ptrEnd-1; }
 428
 429                 /* Return the position. */
 430                 long pos() const { return ptr - ptrBeg - 1; }
 431                 T &operator[](int i) const { return ptr[i]; }
 432
 433                 /** \brief Implicit cast to T*. */
 434                 operator T*() const   { return ptr; }
 435
 436                 /** \brief Dereference operator returns T&. */
 437                 T &operator *() const { return *ptr; }
 438
 439                 /** \brief Arrow operator returns T*. */
 440                 T *operator->() const { return ptr; }
 441
 442                 /** \brief Move to next item. */
 443                 T *operator++()       { return ++ptr; }
 444
 445                 /** \brief Move to next item. */
 446                 T *operator++(int)    { return ptr++; }
 447
 448                 /** \brief Move to next item. */
 449                 T *increment()        { return ++ptr; }
 450
 451                 /** \brief Move to previous item. */
 452                 T *operator--()       { return --ptr; }
 453
 454                 /** \brief Move to previous item. */
 455                 T *operator--(int)    { return ptr--; }
 456
 457                 /** \brief Move to previous item. */
 458                 T *decrement()        { return --ptr; }
 459
 460                 /** \brief Return the next item. Does not modify this. */
 461                 inline IterNext next() const { return IterNext(*this); }
 462
 463                 /** \brief Return the previous item. Does not modify this. */
 464                 inline IterPrev prev() const { return IterPrev(*this); }
 465
 466                 /** \brief The iterator is simply a pointer. */
 467                 T *ptr;
 468
 469                 /* For testing endpoints. */
 470                 T *ptrBeg, *ptrEnd;
 471         };
 472
 473         /** \brief Return first element. */
 474         IterFirst first() { return IterFirst( *this ); }
 475
 476         /** \brief Return last element. */
 477         IterLast last() { return IterLast( *this ); }
 478
 479 protected:
 480         void makeRawSpaceFor(long pos, long len);
 481
 482         void setAsCommon(long len);
 483         long replaceCommon(long pos, long len);
 484         long insertCommon(long pos, long len);
 485
 486         void upResize(long len);
 487         void upResizeDup(long len);
 488         void upResizeFromEmpty(long len);
 489         void downResize(long len);
 490         void downResizeDup(long len);
 491 };
 492
 493 #if 0
 494 /* Create a vector with an intial number of elements and size. */
 495 template <class T, class Resize> SVector<T, Resize>::
 496                 SVector( long size, long allocLen )
 497 {
 498         /* Allocate the space if we are given a positive allocLen. */
 499         if ( allocLen > 0 ) {
 500                 /* Allocate the data needed. */
 501                 STabHead *head = (STabHead*) malloc( sizeof(STabHead) +
 502                                 sizeof(T) * allocLen );
 503                 if ( head == 0 )
 504                         throw std::bad_alloc();
 505
 506                 /* Set up the header and save the data pointer. */
 507                 head->refCount = 1;
 508                 head->allocLen = allocLen;
 509                 head->tabLen = 0;
 510                 BaseTable::data = (T*) (head + 1);
 511         }
 512
 513         /* Grow to the size specified. If we did not have enough space
 514          * allocated that is ok. Table will be grown to the right size. */
 515         setAsNew( size );
 516 }
 517 #endif
 518
 519 /**
 520  * \brief Perform a shallow copy of the vector.
 521  *
 522  * Takes a reference to the contents of the other vector.
 523  */
 524 template <class T, class Resize> SVector<T, Resize>::
 525                 SVector(const SVector<T, Resize> &v)
 526 {
 527         /* Take a reference to other, if any data is allocated. */
 528         if ( v.data == 0 )
 529                 BaseTable::data = 0;
 530         else {
 531                 /* Get the source header, up the refcount and ref it. */
 532                 STabHead *srcHead = ((STabHead*) v.data) - 1;
 533                 srcHead->refCount += 1;
 534                 BaseTable::data = (T*) (srcHead + 1);
 535         }
 536 }
 537
 538 #if 0
 539 /**
 540  * \brief Perform a shallow copy of the vector from only the header.
 541  *
 542  * Takes a reference to the contents specified by the header.
 543  */
 544 template <class T, class Resize> SVector<T, Resize>::
 545                 SVector(STabHead *head)
 546 {
 547         /* Take a reference to other, if the header is no-null. */
 548         if ( head == 0 )
 549                 BaseTable::data = 0;
 550         else {
 551                 head->refCount += 1;
 552                 BaseTable::data = (T*) (head + 1);
 553         }
 554 }
 555 #endif
 556
 557
 558 /**
 559  * \brief Shallow copy another vector into this vector.
 560  *
 561  * Takes a reference to the other vector. The contents of this vector are
 562  * first emptied.
 563  *
 564  * \returns A reference to this.
 565  */
 566 template <class T, class Resize> SVector<T, Resize> &
 567                 SVector<T, Resize>:: operator=( const SVector &v )
 568 {
 569         /* First clean out the current contents. */
 570         empty();
 571
 572         /* Take a reference to other, if any data is allocated. */
 573         if ( v.data == 0 )
 574                 BaseTable::data = 0;
 575         else {
 576                 /* Get the source header, up the refcount and ref it. */
 577                 STabHead *srcHead = ((STabHead*) v.data) - 1;
 578                 srcHead->refCount += 1;
 579                 BaseTable::data = (T*) (srcHead + 1);
 580         }
 581         return *this;
 582 }
 583
 584 /**
 585  * \brief Shallow copy another vector into this vector from only the header.
 586  *
 587  * Takes a reference to the other header vector. The contents of this vector
 588  * are first emptied.
 589  *
 590  * \returns A reference to this.
 591  */
 592 template <class T, class Resize> SVector<T, Resize> &
 593                 SVector<T, Resize>::operator=( STabHead *head )
 594 {
 595         /* First clean out the current contents. */
 596         empty();
 597
 598         /* Take a reference to other, if the header is no-null. */
 599         if ( head == 0 )
 600                 BaseTable::data = 0;
 601         else {
 602                 head->refCount += 1;
 603                 BaseTable::data = (T*) (head + 1);
 604         }
 605         return *this;
 606 }
 607
 608 /* Init a vector iterator with just a vector. */
 609 template <class T, class Resize> SVector<T, Resize>::
 610                 Iter::Iter( const SVector &v )
 611 {
 612         long length;
 613         if ( v.data == 0 || (length=(((STabHead*)v.data)-1)->tabLen) == 0 )
 614                 ptr = ptrBeg = ptrEnd = 0;
 615         else {
 616                 ptr = v.data;
 617                 ptrBeg = v.data-1;
 618                 ptrEnd = v.data+length;
 619         }
 620 }
 621
 622 /* Init a vector iterator with the first of a vector. */
 623 template <class T, class Resize> SVector<T, Resize>::
 624                 Iter::Iter( const IterFirst &vf )
 625 {
 626         long length;
 627         if ( vf.v.data == 0 || (length=(((STabHead*)vf.v.data)-1)->tabLen) == 0 )
 628                 ptr = ptrBeg = ptrEnd = 0;
 629         else {
 630                 ptr = vf.v.data;
 631                 ptrBeg = vf.v.data-1;
 632                 ptrEnd = vf.v.data+length;
 633         }
 634 }
 635
 636 /* Init a vector iterator with the last of a vector. */
 637 template <class T, class Resize> SVector<T, Resize>::
 638                 Iter::Iter( const IterLast &vl )
 639 {
 640         long length;
 641         if ( vl.v.data == 0 || (length=(((STabHead*)vl.v.data)-1)->tabLen) == 0 )
 642                 ptr = ptrBeg = ptrEnd = 0;
 643         else {
 644                 ptr = vl.v.data+length-1;
 645                 ptrBeg = vl.v.data-1;
 646                 ptrEnd = vl.v.data+length;
 647         }
 648 }
 649
 650 /* Init a vector iterator with the next of some other iterator. */
 651 template <class T, class Resize> SVector<T, Resize>::
 652                 Iter::Iter( const IterNext &vn )
 653 :
 654         ptr(vn.i.ptr+1),
 655         ptrBeg(vn.i.ptrBeg),
 656         ptrEnd(vn.i.ptrEnd)
 657 {
 658 }
 659
 660 /* Init a vector iterator with the prev of some other iterator. */
 661 template <class T, class Resize> SVector<T, Resize>::
 662                 Iter::Iter( const IterPrev &vp )
 663 :
 664         ptr(vp.i.ptr-1),
 665         ptrBeg(vp.i.ptrBeg),
 666         ptrEnd(vp.i.ptrEnd)
 667 {
 668 }
 669
 670 /* Set a vector iterator with some vector. */
 671 template <class T, class Resize> typename SVector<T, Resize>::Iter &
 672                 SVector<T, Resize>::Iter::operator=( const SVector &v )
 673 {
 674         long length;
 675         if ( v.data == 0 || (length=(((STabHead*)v.data)-1)->tabLen) == 0 )
 676                 ptr = ptrBeg = ptrEnd = 0;
 677         else {
 678                 ptr = v.data;
 679                 ptrBeg = v.data-1;
 680                 ptrEnd = v.data+length;
 681         }
 682         return *this;
 683 }
 684
 685 /* Set a vector iterator with the first element in a vector. */
 686 template <class T, class Resize> typename SVector<T, Resize>::Iter &
 687                 SVector<T, Resize>::Iter::operator=( const IterFirst &vf )
 688 {
 689         long length;
 690         if ( vf.v.data == 0 || (length=(((STabHead*)vf.v.data)-1)->tabLen) == 0 )
 691                 ptr = ptrBeg = ptrEnd = 0;
 692         else {
 693                 ptr = vf.v.data;
 694                 ptrBeg = vf.v.data-1;
 695                 ptrEnd = vf.v.data+length;
 696         }
 697         return *this;
 698 }
 699
 700 /* Set a vector iterator with the last element in a vector. */
 701 template <class T, class Resize> typename SVector<T, Resize>::Iter &
 702                 SVector<T, Resize>::Iter::operator=( const IterLast &vl )
 703 {
 704         long length;
 705         if ( vl.v.data == 0 || (length=(((STabHead*)vl.v.data)-1)->tabLen) == 0 )
 706                 ptr = ptrBeg = ptrEnd = 0;
 707         else {
 708                 ptr = vl.v.data+length-1;
 709                 ptrBeg = vl.v.data-1;
 710                 ptrEnd = vl.v.data+length;
 711         }
 712         return *this;
 713 }
 714
 715 /* Set a vector iterator with the next of some other iterator. */
 716 template <class T, class Resize> typename SVector<T, Resize>::Iter &
 717                 SVector<T, Resize>::Iter::operator=( const IterNext &vn )
 718 {
 719         ptr = vn.i.ptr+1;
 720         ptrBeg = vn.i.ptrBeg;
 721         ptrEnd = vn.i.ptrEnd;
 722         return *this;
 723 }
 724
 725 /* Set a vector iterator with the prev of some other iterator. */
 726 template <class T, class Resize> typename SVector<T, Resize>::Iter &
 727                 SVector<T, Resize>::Iter::operator=( const IterPrev &vp )
 728 {
 729         ptr = vp.i.ptr-1;
 730         ptrBeg = vp.i.ptrBeg;
 731         ptrEnd = vp.i.ptrEnd;
 732         return *this;
 733 }
 734
 735 /* Up resize the data for len elements using Resize::upResize to tell us the
 736  * new length. Reads and writes allocLen. Does not read or write length.
 737  * Assumes that there is some data allocated already. */
 738 template <class T, class Resize> void SVector<T, Resize>::
 739                 upResize(long len)
 740 {
 741         /* Get the current header. */
 742         STabHead *head = ((STabHead*)BaseTable::data) - 1;
 743
 744         /* Ask the resizer what the new length will be. */
 745         long newLen = Resize::upResize(head->allocLen, len);
 746
 747         /* Did the data grow? */
 748         if ( newLen > head->allocLen ) {
 749                 head->allocLen = newLen;
 750
 751                 /* Table exists already, resize it up. */
 752                 head = (STabHead*) realloc( head, sizeof(STabHead) +
 753                                 sizeof(T) * newLen );
 754                 if ( head == 0 )
 755                         throw std::bad_alloc();
 756
 757                 /* Save the data pointer. */
 758                 BaseTable::data = (T*) (head + 1);
 759         }
 760 }
 761
 762 /* Allocates a new buffer for an up resize that requires a duplication of the
 763  * data. Uses Resize::upResize to get the allocation length.  Reads and writes
 764  * allocLen. This upResize does write the new length.  Assumes that there is
 765  * some data allocated already. */
 766 template <class T, class Resize> void SVector<T, Resize>::
 767                 upResizeDup(long len)
 768 {
 769         /* Get the current header. */
 770         STabHead *head = ((STabHead*)BaseTable::data) - 1;
 771
 772         /* Ask the resizer what the new length will be. */
 773         long newLen = Resize::upResize(head->allocLen, len);
 774
 775         /* Dereferencing the existing data, decrement the refcount. */
 776         head->refCount -= 1;
 777
 778         /* Table exists already, resize it up. */
 779         head = (STabHead*) malloc( sizeof(STabHead) + sizeof(T) * newLen );
 780         if ( head == 0 )
 781                 throw std::bad_alloc();
 782
 783         head->refCount = 1;
 784         head->allocLen = newLen;
 785         head->tabLen = len;
 786
 787         /* Save the data pointer. */
 788         BaseTable::data = (T*) (head + 1);
 789 }
 790
 791 /* Up resize the data for len elements using Resize::upResize to tell us the
 792  * new length. Reads and writes allocLen. This upresize DOES write length.
 793  * Assumes that no data is allocated. */
 794 template <class T, class Resize> void SVector<T, Resize>::
 795                 upResizeFromEmpty(long len)
 796 {
 797         /* There is no table yet. If the len is zero, then there is no need to
 798          * create a table. */
 799         if ( len > 0 ) {
 800                 /* Ask the resizer what the new length will be. */
 801                 long newLen = Resize::upResize(0, len);
 802
 803                 /* If len is greater than zero then we are always allocating the table. */
 804                 STabHead *head = (STabHead*) malloc( sizeof(STabHead) +
 805                                 sizeof(T) * newLen );
 806                 if ( head == 0 )
 807                         throw std::bad_alloc();
 808
 809                 /* Set up the header and save the data pointer. Note that we set the
 810                  * length here. This differs from the other upResizes. */
 811                 head->refCount = 1;
 812                 head->allocLen = newLen;
 813                 head->tabLen = len;
 814                 BaseTable::data = (T*) (head + 1);
 815         }
 816 }
 817
 818 /* Down resize the data for len elements using Resize::downResize to determine
 819  * the new length. Reads and writes allocLen. Does not read or write length. */
 820 template <class T, class Resize> void SVector<T, Resize>::
 821                 downResize(long len)
 822 {
 823         /* If there is already no length, then there is nothing we can do. */
 824         if ( BaseTable::data != 0 ) {
 825                 /* Get the current header. */
 826                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
 827
 828                 /* Ask the resizer what the new length will be. */
 829                 long newLen = Resize::downResize( head->allocLen, len );
 830
 831                 /* Did the data shrink? */
 832                 if ( newLen < head->allocLen ) {
 833                         if ( newLen == 0 ) {
 834                                 /* Simply free the data. */
 835                                 free( head );
 836                                 BaseTable::data = 0;
 837                         }
 838                         else {
 839                                 /* Save the new allocated length. */
 840                                 head->allocLen = newLen;
 841
 842                                 /* Not shrinking to size zero, realloc it to the smaller size. */
 843                                 head = (STabHead*) realloc( head, sizeof(STabHead) +
 844                                                 sizeof(T) * newLen );
 845                                 if ( head == 0 )
 846                                         throw std::bad_alloc();
 847
 848                                 /* Save the new data ptr. */
 849                                 BaseTable::data = (T*) (head + 1);
 850                         }
 851                 }
 852         }
 853 }
 854
 855 /* Allocate a new buffer for a down resize and duplication of the array.  The
 856  * new array will be len long and allocation size will be determined using
 857  * Resize::downResize with the old array's allocLen. Does not actually copy
 858  * any data. Reads and writes allocLen and writes the new len. */
 859 template <class T, class Resize> void SVector<T, Resize>::
 860                 downResizeDup(long len)
 861 {
 862         /* If there is already no length, then there is nothing we can do. */
 863         if ( BaseTable::data != 0 ) {
 864                 /* Get the current header. */
 865                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
 866
 867                 /* Ask the resizer what the new length will be. */
 868                 long newLen = Resize::downResize( head->allocLen, len );
 869
 870                 /* Detaching from the existing head, decrement the refcount. */
 871                 head->refCount -= 1;
 872
 873                 /* Not shrinking to size zero, malloc it to the smaller size. */
 874                 head = (STabHead*) malloc( sizeof(STabHead) + sizeof(T) * newLen );
 875                 if ( head == 0 )
 876                         throw std::bad_alloc();
 877
 878                 /* Save the new allocated length. */
 879                 head->refCount = 1;
 880                 head->allocLen = newLen;
 881                 head->tabLen = len;
 882
 883                 /* Save the data pointer. */
 884                 BaseTable::data = (T*) (head + 1);
 885         }
 886 }
 887
 888 /**
 889  * \brief Free all memory used by the vector.
 890  *
 891  * The vector is reset to zero elements. Destructors are called on all
 892  * elements in the vector. The space allocated for the vector is freed.
 893  */
 894 template <class T, class Resize> void SVector<T, Resize>::
 895                 empty()
 896 {
 897         if ( BaseTable::data != 0 ) {
 898                 /* Get the header and drop the refcount on the data. */
 899                 STabHead *head = ((STabHead*) BaseTable::data) - 1;
 900                 head->refCount -= 1;
 901
 902                 /* If the refcount just went down to zero nobody else is referencing
 903                  * the data. */
 904                 if ( head->refCount == 0 ) {
 905                         /* Call All destructors. */
 906                         T *pos = BaseTable::data;
 907                         for ( long i = 0; i < head->tabLen; pos++, i++ )
 908                                 pos->~T();
 909
 910                         /* Free the data space. */
 911                         free( head );
 912                 }
 913
 914                 /* Clear the pointer. */
 915                 BaseTable::data = 0;
 916         }
 917 }
 918
 919 /* Prepare for setting the contents of the vector to some array len long.
 920  * Handles reusing the existing space, detaching from a common space or
 921  * growing from zero length automatically. */
 922 template <class T, class Resize> void SVector<T, Resize>::
 923                 setAsCommon(long len)
 924 {
 925         if ( BaseTable::data != 0 ) {
 926                 /* Get the header. */
 927                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
 928
 929                 /* If the refCount is one, then we can reuse the space. Otherwise we
 930                  * must detach from the referenced data create new space. */
 931                 if ( head->refCount == 1 ) {
 932                         /* Call All destructors. */
 933                         T *pos = BaseTable::data;
 934                         for ( long i = 0; i < head->tabLen; pos++, i++ )
 935                                 pos->~T();
 936
 937                         /* Adjust the allocated length. */
 938                         if ( len < head->tabLen )
 939                                 downResize( len );
 940                         else if ( len > head->tabLen )
 941                                 upResize( len );
 942
 943                         if ( BaseTable::data != 0 ) {
 944                                 /* Get the header again and set the length. */
 945                                 head = ((STabHead*)BaseTable::data) - 1;
 946                                 head->tabLen = len;
 947                         }
 948                 }
 949                 else {
 950                         /* Just detach from the data. */
 951                         head->refCount -= 1;
 952                         BaseTable::data = 0;
 953
 954                         /* Make enough space. This will set the length. */
 955                         upResizeFromEmpty( len );
 956                 }
 957         }
 958         else {
 959                 /* The table is currently empty. Make enough space. This will set the
 960                  * length. */
 961                 upResizeFromEmpty( len );
 962         }
 963 }
 964
 965 /**
 966  * \brief Set the contents of the vector to be len elements exactly.
 967  *
 968  * The vector becomes len elements in length. Destructors are called on any
 969  * existing elements in the vector. Copy constructors are used to place the
 970  * new elements in the vector.
 971  */
 972 template <class T, class Resize> void SVector<T, Resize>::
 973                 setAs(const T *val, long len)
 974 {
 975         /* Common stuff for setting the array to len long. */
 976         setAsCommon( len );
 977
 978         /* Copy data in. */
 979         T *dst = BaseTable::data;
 980         const T *src = val;
 981         for ( long i = 0; i < len; i++, dst++, src++ )
 982                 new(dst) T(*src);
 983 }
 984
 985
 986 /**
 987  * \brief Set the vector to len copies of item.
 988  *
 989  * The vector becomes len elements in length. Destructors are called on any
 990  * existing elements in the vector. The element's copy constructor is used to
 991  * copy the item into the vector.
 992  */
 993 template <class T, class Resize> void SVector<T, Resize>::
 994                 setAsDup(const T &item, long len)
 995 {
 996         /* Do the common stuff for setting the array to len long. */
 997         setAsCommon( len );
 998
 999         /* Copy item in one spot at a time. */
1000         T *dst = BaseTable::data;
1001         for ( long i = 0; i < len; i++, dst++ )
1002                 new(dst) T(item);
1003 }
1004
1005 /**
1006  * \brief Set the vector to exactly len new items.
1007  *
1008  * The vector becomes len elements in length. Destructors are called on any
1009  * existing elements in the vector. Default constructors are used to init the
1010  * new items.
1011  */
1012 template <class T, class Resize> void SVector<T, Resize>::
1013                 setAsNew(long len)
1014 {
1015         /* Do the common stuff for setting the array to len long. */
1016         setAsCommon( len );
1017
1018         /* Create items using default constructor. */
1019         T *dst = BaseTable::data;
1020         for ( long i = 0; i < len; i++, dst++ )
1021                 new(dst) T();
1022 }
1023
1024 /* Make space in vector for a replacement at pos of len items. Handles reusing
1025  * existing space, detaching or growing from zero space. */
1026 template <class T, class Resize> long SVector<T, Resize>::
1027                 replaceCommon(long pos, long len)
1028 {
1029         if ( BaseTable::data != 0 ) {
1030                 /* Get the header. */
1031                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
1032
1033                 /* If we are given a negative position to replace at then treat it as
1034                  * a position relative to the length. This doesn't have any meaning
1035                  * unless the length is at least one. */
1036                 if ( pos < 0 )
1037                         pos = head->tabLen + pos;
1038
1039                 /* The end is the one past the last item that we want to write to. */
1040                 long i, endPos = pos + len;
1041
1042                 if ( head->refCount == 1 ) {
1043                         /* We can reuse the space. Make sure we have enough space. */
1044                         if ( endPos > head->tabLen ) {
1045                                 upResize( endPos );
1046
1047                                 /* Get the header again, whose addr may have changed after
1048                                  * resizing. */
1049                                 head = ((STabHead*)BaseTable::data) - 1;
1050
1051                                 /* Delete any objects we need to delete. */
1052                                 T *item = BaseTable::data + pos;
1053                                 for ( i = pos; i < head->tabLen; i++, item++ )
1054                                         item->~T();
1055
1056                                 /* We are extending the vector, set the new data length. */
1057                                 head->tabLen = endPos;
1058                         }
1059                         else {
1060                                 /* Delete any objects we need to delete. */
1061                                 T *item = BaseTable::data + pos;
1062                                 for ( i = pos; i < endPos; i++, item++ )
1063                                         item->~T();
1064                         }
1065                 }
1066                 else {
1067                         /* Use endPos to calc the end of the vector. */
1068                         long newLen = endPos;
1069                         if ( newLen < head->tabLen )
1070                                 newLen = head->tabLen;
1071
1072                         /* Duplicate and grow up to endPos. This will set the length. */
1073                         upResizeDup( newLen );
1074
1075                         /* Copy from src up to pos. */
1076                         const T *src = (T*) (head + 1);
1077                         T *dst = BaseTable::data;
1078                         for ( i = 0; i < pos; i++, dst++, src++)
1079                                 new(dst) T(*src);
1080
1081                         /* Copy any items after the replace range. */
1082                         for ( i += len, src += len, dst += len;
1083                                         i < head->tabLen; i++, dst++, src++ )
1084                                 new(dst) T(*src);
1085                 }
1086         }
1087         else {
1088                 /* There is no data initially, must grow from zero. This will set the
1089                  * new length. */
1090                 upResizeFromEmpty( len );
1091         }
1092
1093         return pos;
1094 }
1095
1096
1097 /**
1098  * \brief Replace len elements at position pos.
1099  *
1100  * If there are existing elements at the positions to be replaced, then
1101  * destructors are called before the space is used. Copy constructors are used
1102  * to place the elements into the vector. It is allowable for the pos and
1103  * length to specify a replacement that overwrites existing elements and
1104  * creates new ones.  If pos is greater than the length of the vector then
1105  * undefined behaviour results. If pos is negative, then it is treated as an
1106  * offset relative to the length of the vector.
1107  */
1108 template <class T, class Resize> void SVector<T, Resize>::
1109                 replace(long pos, const T *val, long len)
1110 {
1111         /* Common work for replacing in the vector. */
1112         pos = replaceCommon( pos, len );
1113
1114         /* Copy data in using copy constructor. */
1115         T *dst = BaseTable::data + pos;
1116         const T *src = val;
1117         for ( long i = 0; i < len; i++, dst++, src++ )
1118                 new(dst) T(*src);
1119 }
1120
1121 /**
1122  * \brief Replace at position pos with len copies of an item.
1123  *
1124  * If there are existing elements at the positions to be replaced, then
1125  * destructors are called before the space is used. The copy constructor is
1126  * used to place the element into this vector. It is allowable for the pos and
1127  * length to specify a replacement that overwrites existing elements and
1128  * creates new ones. If pos is greater than the length of the vector then
1129  * undefined behaviour results.  If pos is negative, then it is treated as an
1130  * offset relative to the length of the vector.
1131  */
1132 template <class T, class Resize> void SVector<T, Resize>::
1133                 replaceDup(long pos, const T &val, long len)
1134 {
1135         /* Common replacement stuff. */
1136         pos = replaceCommon( pos, len );
1137
1138         /* Copy data in using copy constructor. */
1139         T *dst = BaseTable::data + pos;
1140         for ( long i = 0; i < len; i++, dst++ )
1141                 new(dst) T(val);
1142 }
1143
1144 /**
1145  * \brief Replace at position pos with len new elements.
1146  *
1147  * If there are existing elements at the positions to be replaced, then
1148  * destructors are called before the space is used. The default constructor is
1149  * used to initialize the new elements. It is allowable for the pos and length
1150  * to specify a replacement that overwrites existing elements and creates new
1151  * ones. If pos is greater than the length of the vector then undefined
1152  * behaviour results. If pos is negative, then it is treated as an offset
1153  * relative to the length of the vector.
1154  */
1155 template <class T, class Resize> void SVector<T, Resize>::
1156                 replaceNew(long pos, long len)
1157 {
1158         /* Do the common replacement stuff. */
1159         pos = replaceCommon( pos, len );
1160
1161         /* Copy data in using copy constructor. */
1162         T *dst = BaseTable::data + pos;
1163         for ( long i = 0; i < len; i++, dst++ )
1164                 new(dst) T();
1165 }
1166
1167 /**
1168  * \brief Remove len elements at position pos.
1169  *
1170  * Destructor is called on all elements removed. Elements to the right of pos
1171  * are shifted len spaces to the left to take up the free space. If pos is
1172  * greater than or equal to the length of the vector then undefined behavior
1173  * results. If pos is negative then it is treated as an offset relative to the
1174  * length of the vector.
1175  */
1176 template <class T, class Resize> void SVector<T, Resize>::
1177                 remove(long pos, long len)
1178 {
1179         /* If there is no data, we can't delete anything anyways. */
1180         if ( BaseTable::data != 0 ) {
1181                 /* Get the header. */
1182                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
1183
1184                 /* If we are given a negative position to remove at then
1185                  * treat it as a position relative to the length. */
1186                 if ( pos < 0 )
1187                         pos = head->tabLen + pos;
1188
1189                 /* The first position after the last item deleted. */
1190                 long endPos = pos + len;
1191
1192                 /* The New data length. */
1193                 long i, newLen = head->tabLen - len;
1194
1195                 if ( head->refCount == 1 ) {
1196                         /* We are the only ones using the data. We can reuse
1197                          * the existing space. */
1198
1199                         /* The place in the data we are deleting at. */
1200                         T *dst = BaseTable::data + pos;
1201
1202                         /* Call Destructors. */
1203                         T *item = BaseTable::data + pos;
1204                         for ( i = 0; i < len; i += 1, item += 1 )
1205                                 item->~T();
1206
1207                         /* Shift data over if necessary. */
1208                         long lenToSlideOver = head->tabLen - endPos;
1209                         if ( len > 0 && lenToSlideOver > 0 )
1210                                 memmove(BaseTable::data + pos, dst + len, sizeof(T)*lenToSlideOver);
1211
1212                         /* Shrink the data if necessary. */
1213                         downResize( newLen );
1214
1215                         if ( BaseTable::data != 0 ) {
1216                                 /* Get the header again (because of the resize) and set the
1217                                  * new data length. */
1218                                 head = ((STabHead*)BaseTable::data) - 1;
1219                                 head->tabLen = newLen;
1220                         }
1221                 }
1222                 else {
1223                         /* Must detach from the common data. Just copy the non-deleted
1224                          * items from the common data. */
1225
1226                         /* Duplicate and grow down to newLen. This will set the length. */
1227                         downResizeDup( newLen );
1228
1229                         /* Copy over just the non-deleted parts. */
1230                         const T *src = (T*) (head + 1);
1231                         T *dst = BaseTable::data;
1232                         for ( i = 0; i < pos; i++, dst++, src++ )
1233                                 new(dst) T(*src);
1234
1235                         /* ... and the second half. */
1236                         for ( i += len, src += len; i < head->tabLen; i++, src++, dst++ )
1237                                 new(dst) T(*src);
1238                 }
1239         }
1240 }
1241
1242 /* Shift over existing data. Handles reusing existing space, detaching or
1243  * growing from zero space. */
1244 template <class T, class Resize> long SVector<T, Resize>::
1245                 insertCommon(long pos, long len)
1246 {
1247         if ( BaseTable::data != 0 ) {
1248                 /* Get the header. */
1249                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
1250
1251                 /* If we are given a negative position to insert at then treat it as a
1252                  * position relative to the length. This only has meaning if there is
1253                  * existing data. */
1254                 if ( pos < 0 )
1255                         pos = head->tabLen + pos;
1256
1257                 /* Calculate the new length. */
1258                 long i, newLen = head->tabLen + len;
1259
1260                 if ( head->refCount == 1 ) {
1261                         /* Up resize, we are growing. */
1262                         upResize( newLen );
1263
1264                         /* Get the header again, (the addr may have changed after
1265                          * resizing). */
1266                         head = ((STabHead*)BaseTable::data) - 1;
1267
1268                         /* Shift over data at insert spot if needed. */
1269                         if ( len > 0 && pos < head->tabLen ) {
1270                                 memmove( BaseTable::data + pos + len, BaseTable::data + pos,
1271                                                 sizeof(T)*(head->tabLen - pos) );
1272                         }
1273
1274                         /* Grow the length by the len inserted. */
1275                         head->tabLen += len;
1276                 }
1277                 else {
1278                         /* Need to detach from the existing array. Copy over the other
1279                          * parts. This will set the length. */
1280                         upResizeDup( newLen );
1281
1282                         /* Copy over the parts around the insert. */
1283                         const T *src = (T*) (head + 1);
1284                         T *dst = BaseTable::data;
1285                         for ( i = 0; i < pos; i++, dst++, src++ )
1286                                 new(dst) T(*src);
1287
1288                         /* ... and the second half. */
1289                         for ( dst += len; i < head->tabLen; i++, src++, dst++ )
1290                                 new(dst) T(*src);
1291                 }
1292         }
1293         else {
1294                 /* There is no existing data. Start from zero. This will set the
1295                  * length. */
1296                 upResizeFromEmpty( len );
1297         }
1298
1299         return pos;
1300 }
1301
1302
1303 /**
1304  * \brief Insert len elements at position pos.
1305  *
1306  * Elements in the vector from pos onward are shifted len spaces to the right.
1307  * The copy constructor is used to place the elements into this vector. If pos
1308  * is greater than the length of the vector then undefined behaviour results.
1309  * If pos is negative then it is treated as an offset relative to the length
1310  * of the vector.
1311  */
1312 template <class T, class Resize> void SVector<T, Resize>::
1313                 insert(long pos, const T *val, long len)
1314 {
1315         /* Do the common insertion stuff. */
1316         pos = insertCommon( pos, len );
1317
1318         /* Copy data in element by element. */
1319         T *dst = BaseTable::data + pos;
1320         const T *src = val;
1321         for ( long i = 0; i < len; i++, dst++, src++ )
1322                 new(dst) T(*src);
1323 }
1324
1325 /**
1326  * \brief Insert len copies of item at position pos.
1327  *
1328  * Elements in the vector from pos onward are shifted len spaces to the right.
1329  * The copy constructor is used to place the element into this vector. If pos
1330  * is greater than the length of the vector then undefined behaviour results.
1331  * If pos is negative then it is treated as an offset relative to the length
1332  * of the vector.
1333  */
1334 template <class T, class Resize> void SVector<T, Resize>::
1335                 insertDup(long pos, const T &item, long len)
1336 {
1337         /* Do the common insertion stuff. */
1338         pos = insertCommon( pos, len );
1339
1340         /* Copy the data item in one at a time. */
1341         T *dst = BaseTable::data + pos;
1342         for ( long i = 0; i < len; i++, dst++ )
1343                 new(dst) T(item);
1344 }
1345
1346
1347 /**
1348  * \brief Insert len new elements using the default constructor.
1349  *
1350  * Elements in the vector from pos onward are shifted len spaces to the right.
1351  * Default constructors are used to init the new elements. If pos is off the
1352  * end of the vector then undefined behaviour results. If pos is negative then
1353  * it is treated as an offset relative to the length of the vector.
1354  */
1355 template <class T, class Resize> void SVector<T, Resize>::
1356                 insertNew(long pos, long len)
1357 {
1358         /* Do the common insertion stuff. */
1359         pos = insertCommon( pos, len );
1360
1361         /* Init new data with default constructors. */
1362         T *dst = BaseTable::data + pos;
1363         for ( long i = 0; i < len; i++, dst++ )
1364                 new(dst) T();
1365 }
1366
1367 /* Makes space for len items, Does not init the items in any way.  If pos is
1368  * greater than the length of the vector then undefined behaviour results.
1369  * Updates the length of the vector. */
1370 template <class T, class Resize> void SVector<T, Resize>::
1371                 makeRawSpaceFor(long pos, long len)
1372 {
1373         if ( BaseTable::data != 0 ) {
1374                 /* Get the header. */
1375                 STabHead *head = ((STabHead*)BaseTable::data) - 1;
1376
1377                 /* Calculate the new length. */
1378                 long i, newLen = head->tabLen + len;
1379
1380                 if ( head->refCount == 1 ) {
1381                         /* Up resize, we are growing. */
1382                         upResize( newLen );
1383
1384                         /* Get the header again, (the addr may have changed after
1385                          * resizing). */
1386                         head = ((STabHead*)BaseTable::data) - 1;
1387
1388                         /* Shift over data at insert spot if needed. */
1389                         if ( len > 0 && pos < head->tabLen ) {
1390                                 memmove( BaseTable::data + pos + len, BaseTable::data + pos,
1391                                                 sizeof(T)*(head->tabLen - pos) );
1392                         }
1393
1394                         /* Grow the length by the len inserted. */
1395                         head->tabLen += len;
1396                 }
1397                 else {
1398                         /* Need to detach from the existing array. Copy over the other
1399                          * parts. This will set the length. */
1400                         upResizeDup( newLen );
1401
1402                         /* Copy over the parts around the insert. */
1403                         const T *src = (T*) (head + 1);
1404                         T *dst = BaseTable::data;
1405                         for ( i = 0; i < pos; i++, dst++, src++ )
1406                                 new(dst) T(*src);
1407
1408                         /* ... and the second half. */
1409                         for ( dst += len; i < head->tabLen; i++, src++, dst++ )
1410                                 new(dst) T(*src);
1411                 }
1412         }
1413         else {
1414                 /* There is no existing data. Start from zero. This will set the
1415                  * length. */
1416                 upResizeFromEmpty( len );
1417         }
1418 }
1419
1420
1421 #ifdef AAPL_NAMESPACE
1422 }
1423 #endif
1424
1425
1426 #endif /* _AAPL_SVECTOR_H */