headers/private/kernel/util/Vector.h

   1 // Vector.h
   2 //
   3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
   4 //
   5 // Permission is hereby granted, free of charge, to any person obtaining a
   6 // copy of this software and associated documentation files (the "Software"),
   7 // to deal in the Software without restriction, including without limitation
   8 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9 // and/or sell copies of the Software, and to permit persons to whom the
  10 // Software is furnished to do so, subject to the following conditions:
  11 //
  12 // The above copyright notice and this permission notice shall be included in
  13 // all copies or substantial portions of the Software.
  14 //
  15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  18 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21 // DEALINGS IN THE SOFTWARE.
  22 //
  23 // Except as contained in this notice, the name of a copyright holder shall
  24 // not be used in advertising or otherwise to promote the sale, use or other
  25 // dealings in this Software without prior written authorization of the
  26 // copyright holder.
  27
  28 #ifndef _VECTOR_H
  29 #define _VECTOR_H
  30
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include <SupportDefs.h>
  35 #include <util/kernel_cpp.h>
  36
  37 template<typename Value> class VectorIterator;
  38
  39 // for convenience
  40 #define _VECTOR_TEMPLATE_LIST template<typename Value>
  41 #define _VECTOR_CLASS_NAME Vector<Value>
  42 #define _VECTOR_CLASS_TYPE typename Vector<Value>
  43
  44 /*!
  45         \class Vector
  46         \brief A generic vector implementation.
  47 */
  48 template<typename Value>
  49 class Vector {
  50 public:
  51         typedef VectorIterator<Value>           Iterator;
  52         typedef VectorIterator<const Value>     ConstIterator;
  53
  54 private:
  55         static const size_t                             kDefaultChunkSize = 10;
  56         static const size_t                             kMaximalChunkSize = 1024 * 1024;
  57
  58 public:
  59         Vector(size_t chunkSize = kDefaultChunkSize);
  60         ~Vector();
  61
  62         status_t PushFront(const Value &value);
  63         status_t PushBack(const Value &value);
  64
  65         void PopFront();
  66         void PopBack();
  67
  68         status_t Add(const Value &value) { return PushBack(value); }
  69         status_t Add(const Value &value, int32 index) { return Insert(value, index); }
  70
  71         status_t Insert(const Value &value, int32 index);
  72         status_t Insert(const Value &value, const Iterator &iterator);
  73
  74         int32 Remove(const Value &value);
  75         Iterator Erase(int32 index);
  76         Iterator Erase(const Iterator &iterator);
  77
  78         inline int32 Count() const;
  79         inline bool IsEmpty() const;
  80         void MakeEmpty();
  81
  82         inline Iterator Begin();
  83         inline ConstIterator Begin() const;
  84         inline Iterator End();
  85         inline ConstIterator End() const;
  86         inline Iterator Null();
  87         inline ConstIterator Null() const;
  88         inline Iterator IteratorForIndex(int32 index);
  89         inline ConstIterator IteratorForIndex(int32 index) const;
  90
  91         inline const Value &ElementAt(int32 index) const;
  92         inline Value &ElementAt(int32 index);
  93
  94         int32 IndexOf(const Value &value, int32 start = 0) const;
  95         Iterator Find(const Value &value);
  96         Iterator Find(const Value &value, const Iterator &start);
  97         ConstIterator Find(const Value &value) const;
  98         ConstIterator Find(const Value &value, const ConstIterator &start) const;
  99
 100         inline Value &operator[](int32 index);
 101         inline const Value &operator[](int32 index) const;
 102
 103         // debugging
 104         int32 GetCapacity() const       { return fCapacity; }
 105
 106 private:
 107         inline static void _MoveItems(Value *values, int32 offset, int32 count);
 108         bool _Resize(size_t count);
 109         inline int32 _IteratorIndex(const Iterator &iterator) const;
 110         inline int32 _IteratorIndex(const ConstIterator &iterator) const;
 111
 112 private:
 113         size_t  fCapacity;
 114         size_t  fChunkSize;
 115         int32   fItemCount;
 116         Value   *fItems;
 117 };
 118
 119
 120 // VectorIterator
 121 template<typename Value>
 122 class VectorIterator {
 123 private:
 124         typedef VectorIterator<Value>   Iterator;
 125
 126 public:
 127         inline VectorIterator<Value>()
 128                 : fElement(NULL)
 129         {
 130         }
 131
 132         inline VectorIterator<Value>(const Iterator &other)
 133                 : fElement(other.fElement)
 134         {
 135         }
 136
 137         inline Iterator &operator++()
 138         {
 139                 if (fElement)
 140                         ++fElement;
 141                 return *this;
 142         }
 143
 144         inline Iterator operator++(int)
 145         {
 146                 Iterator it(*this);
 147                 ++*this;
 148                 return it;
 149         }
 150
 151         inline Iterator &operator--()
 152         {
 153                 if (fElement)
 154                         --fElement;
 155                 return *this;
 156         }
 157
 158         inline Iterator operator--(int)
 159         {
 160                 Iterator it(*this);
 161                 --*this;
 162                 return it;
 163         }
 164
 165         inline Iterator &operator=(const Iterator &other)
 166         {
 167                 fElement = other.fElement;
 168                 return *this;
 169         }
 170
 171
 172         inline bool operator==(const Iterator &other) const
 173         {
 174                 return (fElement == other.fElement);
 175         }
 176
 177         inline bool operator!=(const Iterator &other) const
 178         {
 179                 return !(*this == other);
 180         }
 181
 182         inline Value &operator*() const
 183         {
 184                 return *fElement;
 185         }
 186
 187         inline Value *operator->() const
 188         {
 189                 return fElement;
 190         }
 191
 192         inline operator bool() const
 193         {
 194                 return fElement;
 195         }
 196
 197 // private
 198 public:
 199         inline VectorIterator<Value>(Value *element)
 200                 : fElement(element)
 201         {
 202         }
 203
 204         inline Value *Element() const
 205         {
 206                 return fElement;
 207         }
 208
 209 protected:
 210         Value   *fElement;
 211 };
 212
 213
 214 // Vector
 215
 216 // constructor
 217 /*!     \brief Creates an empty vector.
 218         \param chunkSize The granularity for the vector's capacity, i.e. the
 219                    minimal number of elements the capacity grows or shrinks when
 220                    necessary.
 221 */
 222 _VECTOR_TEMPLATE_LIST
 223 _VECTOR_CLASS_NAME::Vector(size_t chunkSize)
 224         : fCapacity(0),
 225           fChunkSize(chunkSize),
 226           fItemCount(0),
 227           fItems(NULL)
 228 {
 229         if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
 230                 fChunkSize = kDefaultChunkSize;
 231         _Resize(0);
 232 }
 233
 234 // destructor
 235 /*!     \brief Frees all resources associated with the object.
 236
 237         The contained elements are destroyed. Note, that, if the element
 238         type is a pointer type, only the pointer is destroyed, not the object
 239         it points to.
 240 */
 241 _VECTOR_TEMPLATE_LIST
 242 _VECTOR_CLASS_NAME::~Vector()
 243 {
 244         MakeEmpty();
 245         free(fItems);
 246 }
 247
 248 // PushFront
 249 /*!     \brief Inserts a copy of the supplied value at the beginning of the
 250                    vector.
 251         \param value The element to be inserted.
 252         \return
 253         - \c B_OK: Everything went fine.
 254         - \c B_NO_MEMORY: Insufficient memory for this operation.
 255 */
 256 _VECTOR_TEMPLATE_LIST
 257 status_t
 258 _VECTOR_CLASS_NAME::PushFront(const Value &value)
 259 {
 260         return Insert(value, 0);
 261 }
 262
 263 // PushBack
 264 /*!     \brief Inserts a copy of the supplied value at the end of the vector.
 265         \param value The element to be inserted.
 266         \return
 267         - \c B_OK: Everything went fine.
 268         - \c B_NO_MEMORY: Insufficient memory for this operation.
 269 */
 270 _VECTOR_TEMPLATE_LIST
 271 status_t
 272 _VECTOR_CLASS_NAME::PushBack(const Value &value)
 273 {
 274         return Insert(value, fItemCount);
 275 }
 276
 277 // PopFront
 278 /*!     \brief Removes the first element of the vector.
 279
 280         Invocation on an empty vector is harmless.
 281 */
 282 _VECTOR_TEMPLATE_LIST
 283 void
 284 _VECTOR_CLASS_NAME::PopFront()
 285 {
 286         if (fItemCount > 0)
 287                 Erase(0);
 288 }
 289
 290 // PopBack
 291 /*!     \brief Removes the last element of the vector.
 292
 293         Invocation on an empty vector is harmless.
 294 */
 295 _VECTOR_TEMPLATE_LIST
 296 void
 297 _VECTOR_CLASS_NAME::PopBack()
 298 {
 299         if (fItemCount > 0)
 300                 Erase(fItemCount - 1);
 301 }
 302
 303 // _MoveItems
 304 /*!     \brief Moves elements within an array.
 305         \param items The elements to be moved.
 306         \param offset The index to which the elements shall be moved. May be
 307                    negative.
 308         \param count The number of elements to be moved.
 309 */
 310 _VECTOR_TEMPLATE_LIST
 311 inline
 312 void
 313 _VECTOR_CLASS_NAME::_MoveItems(Value* items, int32 offset, int32 count)
 314 {
 315         if (count > 0 && offset != 0)
 316                 memmove(items + offset, items, count * sizeof(Value));
 317 }
 318
 319 // Insert
 320 /*!     \brief Inserts a copy of the the supplied value at the given index.
 321         \param value The value to be inserted.
 322         \param index The index at which to insert the new element. It must
 323                    hold: 0 <= \a index <= Count().
 324         \return
 325         - \c B_OK: Everything went fine.
 326         - \c B_BAD_VALUE: \a index is out of range.
 327         - \c B_NO_MEMORY: Insufficient memory for this operation.
 328 */
 329 _VECTOR_TEMPLATE_LIST
 330 status_t
 331 _VECTOR_CLASS_NAME::Insert(const Value &value, int32 index)
 332 {
 333         if (index < 0 || index > fItemCount)
 334                 return B_BAD_VALUE;
 335         if (!_Resize(fItemCount + 1))
 336                 return B_NO_MEMORY;
 337         _MoveItems(fItems + index, 1, fItemCount - index - 1);
 338         new(fItems + index) Value(value);
 339         return B_OK;
 340 }
 341
 342 // Insert
 343 /*!     \brief Inserts a copy of the the supplied value at the given position.
 344         \param value The value to be inserted.
 345         \param iterator An iterator specifying the position at which to insert
 346                    the new element.
 347         \return
 348         - \c B_OK: Everything went fine.
 349         - \c B_BAD_VALUE: \a iterator is is invalid.
 350         - \c B_NO_MEMORY: Insufficient memory for this operation.
 351 */
 352 _VECTOR_TEMPLATE_LIST
 353 status_t
 354 _VECTOR_CLASS_NAME::Insert(const Value &value, const Iterator &iterator)
 355 {
 356         int32 index = _IteratorIndex(iterator);
 357         if (index >= 0)
 358                 return Insert(value, index);
 359         return B_BAD_VALUE;
 360 }
 361
 362 // Remove
 363 /*!     \brief Removes all elements of the supplied value.
 364         \param value The value of the elements to be removed.
 365         \return The number of removed occurrences.
 366 */
 367 _VECTOR_TEMPLATE_LIST
 368 int32
 369 _VECTOR_CLASS_NAME::Remove(const Value &value)
 370 {
 371         int32 count = 0;
 372         for (int32 i = fItemCount - 1; i >= 0; i--) {
 373                 if (ElementAt(i) == value) {
 374                         Erase(i);
 375                         count++;
 376                 }
 377         }
 378         return count;
 379 }
 380
 381 // Erase
 382 /*!     \brief Removes the element at the given index.
 383         \param index The position of the element to be removed.
 384         \return An iterator referring to the element now being located at index
 385                         \a index (End(), if it was the last element that has been
 386                         removed), or Null(), if \a index was out of range.
 387 */
 388 _VECTOR_TEMPLATE_LIST
 389 _VECTOR_CLASS_TYPE::Iterator
 390 _VECTOR_CLASS_NAME::Erase(int32 index)
 391 {
 392         if (index >= 0 && index < fItemCount) {
 393                 fItems[index].~Value();
 394                 _MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
 395                 _Resize(fItemCount - 1);
 396                 return Iterator(fItems + index);
 397         }
 398         return Null();
 399 }
 400
 401 // Erase
 402 /*!     \brief Removes the element at the given position.
 403         \param iterator An iterator referring to the element to be removed.
 404         \return An iterator referring to the element succeeding the removed
 405                         one (End(), if it was the last element that has been
 406                         removed), or Null(), if \a iterator was an invalid iterator
 407                         (in this case including End()).
 408 */
 409 _VECTOR_TEMPLATE_LIST
 410 _VECTOR_CLASS_TYPE::Iterator
 411 _VECTOR_CLASS_NAME::Erase(const Iterator &iterator)
 412 {
 413         int32 index = _IteratorIndex(iterator);
 414         if (index >= 0 && index < fItemCount)
 415                 return Erase(index);
 416         return Null();
 417 }
 418
 419 // Count
 420 /*!     \brief Returns the number of elements the vector contains.
 421         \return The number of elements the vector contains.
 422 */
 423 _VECTOR_TEMPLATE_LIST
 424 inline
 425 int32
 426 _VECTOR_CLASS_NAME::Count() const
 427 {
 428         return fItemCount;
 429 }
 430
 431 // IsEmpty
 432 /*!     \brief Returns whether the vector is empty.
 433         \return \c true, if the vector is empty, \c false otherwise.
 434 */
 435 _VECTOR_TEMPLATE_LIST
 436 inline
 437 bool
 438 _VECTOR_CLASS_NAME::IsEmpty() const
 439 {
 440         return (fItemCount == 0);
 441 }
 442
 443 // MakeEmpty
 444 /*!     \brief Removes all elements from the vector.
 445 */
 446 _VECTOR_TEMPLATE_LIST
 447 void
 448 _VECTOR_CLASS_NAME::MakeEmpty()
 449 {
 450         for (int32 i = 0; i < fItemCount; i++)
 451                 fItems[i].~Value();
 452         _Resize(0);
 453 }
 454
 455 // Begin
 456 /*!     \brief Returns an iterator referring to the beginning of the vector.
 457
 458         If the vector is not empty, Begin() refers to its first element,
 459         otherwise it is equal to End() and must not be dereferenced!
 460
 461         \return An iterator referring to the beginning of the vector.
 462 */
 463 _VECTOR_TEMPLATE_LIST
 464 inline
 465 _VECTOR_CLASS_TYPE::Iterator
 466 _VECTOR_CLASS_NAME::Begin()
 467 {
 468         return Iterator(fItems);
 469 }
 470
 471 // Begin
 472 /*!     \brief Returns an iterator referring to the beginning of the vector.
 473
 474         If the vector is not empty, Begin() refers to its first element,
 475         otherwise it is equal to End() and must not be dereferenced!
 476
 477         \return An iterator referring to the beginning of the vector.
 478 */
 479 _VECTOR_TEMPLATE_LIST
 480 inline
 481 _VECTOR_CLASS_TYPE::ConstIterator
 482 _VECTOR_CLASS_NAME::Begin() const
 483 {
 484         return ConstIterator(fItems);
 485 }
 486
 487 // End
 488 /*!     \brief Returns an iterator referring to the end of the vector.
 489
 490         The position identified by End() is the one succeeding the last
 491         element, i.e. it must not be dereferenced!
 492
 493         \return An iterator referring to the end of the vector.
 494 */
 495 _VECTOR_TEMPLATE_LIST
 496 inline
 497 _VECTOR_CLASS_TYPE::Iterator
 498 _VECTOR_CLASS_NAME::End()
 499 {
 500         return Iterator(fItems + fItemCount);
 501 }
 502
 503 // End
 504 /*!     \brief Returns an iterator referring to the end of the vector.
 505
 506         The position identified by End() is the one succeeding the last
 507         element, i.e. it must not be dereferenced!
 508
 509         \return An iterator referring to the end of the vector.
 510 */
 511 _VECTOR_TEMPLATE_LIST
 512 inline
 513 _VECTOR_CLASS_TYPE::ConstIterator
 514 _VECTOR_CLASS_NAME::End() const
 515 {
 516         return ConstIterator(fItems + fItemCount);
 517 }
 518
 519 // Null
 520 /*!     \brief Returns an invalid iterator.
 521
 522         Null() is used as a return value, if something went wrong. It must
 523         neither be incremented or decremented nor dereferenced!
 524
 525         \return An invalid iterator.
 526 */
 527 _VECTOR_TEMPLATE_LIST
 528 inline
 529 _VECTOR_CLASS_TYPE::Iterator
 530 _VECTOR_CLASS_NAME::Null()
 531 {
 532         return Iterator(NULL);
 533 }
 534
 535 // Null
 536 /*!     \brief Returns an invalid iterator.
 537
 538         Null() is used as a return value, if something went wrong. It must
 539         neither be incremented or decremented nor dereferenced!
 540
 541         \return An invalid iterator.
 542 */
 543 _VECTOR_TEMPLATE_LIST
 544 inline
 545 _VECTOR_CLASS_TYPE::ConstIterator
 546 _VECTOR_CLASS_NAME::Null() const
 547 {
 548         return ConstIterator(NULL);
 549 }
 550
 551 // IteratorForIndex
 552 /*!     \brief Returns an iterator for a given index.
 553         \return An iterator referring to the same element as \a index, or
 554                         End(), if \a index is out of range.
 555 */
 556 _VECTOR_TEMPLATE_LIST
 557 inline
 558 _VECTOR_CLASS_TYPE::Iterator
 559 _VECTOR_CLASS_NAME::IteratorForIndex(int32 index)
 560 {
 561         if (index >= 0 && index <= fItemCount)
 562                 return Iterator(fItems + index);
 563         return End();
 564 }
 565
 566 // IteratorForIndex
 567 /*!     \brief Returns an iterator for a given index.
 568         \return An iterator referring to the same element as \a index, or
 569                         End(), if \a index is out of range.
 570 */
 571 _VECTOR_TEMPLATE_LIST
 572 inline
 573 _VECTOR_CLASS_TYPE::ConstIterator
 574 _VECTOR_CLASS_NAME::IteratorForIndex(int32 index) const
 575 {
 576         if (index >= 0 && index <= fItemCount)
 577                 return ConstIterator(fItems + index);
 578         return End();
 579 }
 580
 581 // ElementAt
 582 /*!     \brief Returns the element at a given index.
 583         \param index The index identifying the element to be returned.
 584         \return The element identified by the given index.
 585 */
 586 _VECTOR_TEMPLATE_LIST
 587 inline
 588 const Value &
 589 _VECTOR_CLASS_NAME::ElementAt(int32 index) const
 590 {
 591         if (index >= 0 && index < fItemCount)
 592                 return fItems[index];
 593         // Return the 0th element by default. Unless the allocation failed, there
 594         // is always a 0th element -- uninitialized perhaps.
 595         return fItems[0];
 596 }
 597
 598 // ElementAt
 599 /*!     \brief Returns the element at a given index.
 600         \param index The index identifying the element to be returned.
 601         \return The element identified by the given index.
 602 */
 603 _VECTOR_TEMPLATE_LIST
 604 inline
 605 Value &
 606 _VECTOR_CLASS_NAME::ElementAt(int32 index)
 607 {
 608         if (index >= 0 && index < fItemCount)
 609                 return fItems[index];
 610         // Return the 0th element by default. Unless the allocation failed, there
 611         // is always a 0th element -- uninitialized perhaps.
 612         return fItems[0];
 613 }
 614
 615 // IndexOf
 616 /*!     \brief Returns the index of the next element with the specified value.
 617         \param value The value of the element to be found.
 618         \param start The index at which to be started to search for the element.
 619         \return The index of the found element, or \c -1, if no further element
 620                         with the given value could be found or \a index is out of range.
 621 */
 622 _VECTOR_TEMPLATE_LIST
 623 int32
 624 _VECTOR_CLASS_NAME::IndexOf(const Value &value, int32 start) const
 625 {
 626         if (start >= 0) {
 627                 for (int32 i = start; i < fItemCount; i++) {
 628                         if (fItems[i] == value)
 629                                 return i;
 630                 }
 631         }
 632         return -1;
 633 }
 634
 635 // Find
 636 /*!     \brief Returns an iterator referring to the next element with the
 637                    specified value.
 638         \param value The value of the element to be found.
 639         \return An iterator referring to the found element, or End(), if no
 640                         further with the given value could be found.
 641 */
 642 _VECTOR_TEMPLATE_LIST
 643 inline
 644 _VECTOR_CLASS_TYPE::Iterator
 645 _VECTOR_CLASS_NAME::Find(const Value &value)
 646 {
 647         return Find(value, Begin());
 648 }
 649
 650 // Find
 651 /*!     \brief Returns an iterator referring to the next element with the
 652                    specified value.
 653         \param value The value of the element to be found.
 654         \param start And iterator specifying where to start searching for the
 655                    element.
 656         \return An iterator referring to the found element, or End(), if no
 657                         further with the given value could be found or \a start was
 658                         invalid.
 659 */
 660 _VECTOR_TEMPLATE_LIST
 661 _VECTOR_CLASS_TYPE::Iterator
 662 _VECTOR_CLASS_NAME::Find(const Value &value, const Iterator &start)
 663 {
 664         int32 index = IndexOf(value, _IteratorIndex(start));
 665         if (index >= 0)
 666                 return Iterator(fItems + index);
 667         return End();
 668 }
 669
 670 // Find
 671 /*!     \brief Returns an iterator referring to the of the next element with the
 672                    specified value.
 673         \param value The value of the element to be found.
 674         \return An iterator referring to the found element, or End(), if no
 675                         further with the given value could be found.
 676 */
 677 _VECTOR_TEMPLATE_LIST
 678 inline
 679 _VECTOR_CLASS_TYPE::ConstIterator
 680 _VECTOR_CLASS_NAME::Find(const Value &value) const
 681 {
 682         return Find(value, Begin());
 683 }
 684
 685 // Find
 686 /*!     \brief Returns an iterator referring to the of the next element with the
 687                    specified value.
 688         \param value The value of the element to be found.
 689         \param start And iterator specifying where to start searching for the
 690                    element.
 691         \return An iterator referring to the found element, or End(), if no
 692                         further with the given value could be found or \a start was
 693                         invalid.
 694 */
 695 _VECTOR_TEMPLATE_LIST
 696 _VECTOR_CLASS_TYPE::ConstIterator
 697 _VECTOR_CLASS_NAME::Find(const Value &value, const ConstIterator &start) const
 698 {
 699         int32 index = IndexOf(value, _IteratorIndex(start));
 700         if (index >= 0)
 701                 return ConstIterator(fItems + index);
 702         return End();
 703 }
 704
 705 // []
 706 /*!     \brief Semantically equivalent to ElementAt().
 707 */
 708 _VECTOR_TEMPLATE_LIST
 709 inline
 710 Value &
 711 _VECTOR_CLASS_NAME::operator[](int32 index)
 712 {
 713         return ElementAt(index);
 714 }
 715
 716 // []
 717 /*!     \brief Semantically equivalent to ElementAt().
 718 */
 719 _VECTOR_TEMPLATE_LIST
 720 inline
 721 const Value &
 722 _VECTOR_CLASS_NAME::operator[](int32 index) const
 723 {
 724         return ElementAt(index);
 725 }
 726
 727 // _Resize
 728 /*!     \brief Resizes the vector.
 729
 730         The internal element array will be grown or shrunk to the next multiple
 731         of \a fChunkSize >= \a count, but no less than \a fChunkSize.
 732
 733         Also adjusts \a fItemCount according to the supplied \a count, but does
 734         not invoke a destructor or constructor on any element.
 735
 736         \param count The number of element.
 737         \return \c true, if everything went fine, \c false, if the memory
 738                         allocation failed.
 739 */
 740 _VECTOR_TEMPLATE_LIST
 741 bool
 742 _VECTOR_CLASS_NAME::_Resize(size_t count)
 743 {
 744         bool result = true;
 745         // calculate the new capacity
 746         int32 newSize = count;
 747         if (newSize <= 0)
 748                 newSize = 1;
 749         newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
 750         // resize if necessary
 751         if ((size_t)newSize != fCapacity) {
 752                 Value* newItems = (Value*)realloc(fItems, newSize * sizeof(Value));
 753                 if (newItems) {
 754                         fItems = newItems;
 755                         fCapacity = newSize;
 756                 } else
 757                         result = false;
 758         }
 759         if (result)
 760                 fItemCount = count;
 761         return result;
 762 }
 763
 764 // _IteratorIndex
 765 /*!     \brief Returns index of the element the supplied iterator refers to.
 766         \return The index of the element the supplied iterator refers to, or
 767                         \c -1, if the iterator is invalid (End() is considered valid
 768                         here, and Count() is returned).
 769 */
 770 _VECTOR_TEMPLATE_LIST
 771 inline
 772 int32
 773 _VECTOR_CLASS_NAME::_IteratorIndex(const Iterator &iterator) const
 774 {
 775         if (iterator.Element()) {
 776                 int32 index = iterator.Element() - fItems;
 777                 if (index >= 0 && index <= fItemCount)
 778                         return index;
 779         }
 780         return -1;
 781 }
 782
 783 // _IteratorIndex
 784 /*!     \brief Returns index of the element the supplied iterator refers to.
 785         \return The index of the element the supplied iterator refers to, or
 786                         \c -1, if the iterator is invalid (End() is considered valid
 787                         here, and Count() is returned).
 788 */
 789 _VECTOR_TEMPLATE_LIST
 790 inline
 791 int32
 792 _VECTOR_CLASS_NAME::_IteratorIndex(const ConstIterator &iterator) const
 793 {
 794         if (iterator.Element()) {
 795                 int32 index = iterator.Element() - fItems;
 796                 if (index >= 0 && index <= fItemCount)
 797                         return index;
 798         }
 799         return -1;
 800 }
 801
 802 #endif  // _VECTOR_H