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