git.cworth.org Git - vogl/blob - src/voglcore/vogl_growable_array.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_growable_array.h
  28 //
  29 // growable_array is backed by an embedded fixed array which can hold up to N elements, beyond this it automatically switches to a vogl::vector.
  30 // This class is only a subset of vogl::vector, but its semantics closely match it.
  31 // Objects in the embedded fixed array are not constructed until they are inserted/push_back'd, etc. They are guaranteed 8 byte alignment.
  32 // If vogl::vector supports mixins I could add this functionality into it directly without having to duplicate code (and I could cut down on the #
  33 // of member vars), but it would become much more complex.
  34 // This is like llvm::SmallVector, see http://fahrenheit2539.blogspot.com/2012/06/introduction-in-depths-look-at.html
  35 //
  36 #ifndef VOGL_GROWABLE_ARRAY_H
  37 #define VOGL_GROWABLE_ARRAY_H
  38
  39 #include "vogl_core.h"
  40
  41 namespace vogl
  42 {
  43     template <typename T, uint N>
  44     class growable_array
  45     {
  46     public:
  47         typedef T element_type;
  48         enum
  49         {
  50             cMaxFixedElements = N
  51         };
  52
  53         inline growable_array()
  54             : m_fixed_size(0)
  55         {
  56             VOGL_ASSUME(N > 0);
  57         }
  58
  59         inline growable_array(uint initial_size)
  60             : m_fixed_size(0)
  61         {
  62             VOGL_ASSUME(N > 0);
  63             resize(initial_size);
  64         }
  65
  66         inline growable_array(const growable_array &other)
  67             : m_fixed_size(0)
  68         {
  69             VOGL_ASSUME(N > 0);
  70             *this = other;
  71         }
  72
  73         inline growable_array &operator=(const growable_array &rhs)
  74         {
  75             if (this == &rhs)
  76                 return *this;
  77
  78             clear();
  79
  80             const uint rhs_size = rhs.size();
  81
  82             if (rhs_size > N)
  83                 m_dynamic_elements = rhs.m_dynamic_elements;
  84             else
  85             {
  86                 helpers::copy_array(&fixed_element(0), rhs.get_ptr(), rhs_size);
  87                 m_fixed_size = rhs_size;
  88             }
  89
  90             return *this;
  91         }
  92
  93         inline ~growable_array()
  94         {
  95             VOGL_ASSERT((m_fixed_size && m_dynamic_elements.is_empty()) || (!m_fixed_size));
  96             VOGL_ASSERT((m_fixed_size && (m_dynamic_elements.get_ptr() == NULL)) || (!m_fixed_size));
  97
  98             if (VOGL_HAS_DESTRUCTOR(T))
  99             {
 100                 scalar_type<T>::destruct_array(&fixed_element(0), m_fixed_size);
 101             }
 102         }
 103
 104         inline bool is_dynamic() const
 105         {
 106             return m_dynamic_elements.get_ptr() != NULL;
 107         }
 108
 109         inline void clear()
 110         {
 111             VOGL_ASSERT((m_fixed_size && m_dynamic_elements.is_empty() && (m_dynamic_elements.get_ptr() == NULL)) || (!m_fixed_size));
 112
 113             if (m_fixed_size)
 114             {
 115                 if (VOGL_HAS_DESTRUCTOR(T))
 116                 {
 117                     scalar_type<T>::destruct_array(&fixed_element(0), m_fixed_size);
 118                 }
 119                 m_fixed_size = 0;
 120             }
 121             else
 122             {
 123                 m_dynamic_elements.clear();
 124             }
 125         }
 126
 127         inline uint size() const
 128         {
 129             return m_fixed_size ? m_fixed_size : m_dynamic_elements.size();
 130         }
 131
 132         inline uint size_in_bytes() const
 133         {
 134             return size() * sizeof(T);
 135         }
 136
 137         inline bool is_empty() const
 138         {
 139             return !size();
 140         }
 141
 142         inline uint capacity() const
 143         {
 144             return is_dynamic() ? m_dynamic_elements.capacity() : N;
 145         }
 146
 147         inline const T *get_ptr() const
 148         {
 149             return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.get_ptr() : &fixed_element(0));
 150         }
 151         inline T *get_ptr()
 152         {
 153             return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.get_ptr() : &fixed_element(0));
 154         }
 155
 156         inline const T *begin() const
 157         {
 158             return get_ptr();
 159         }
 160         inline T *begin()
 161         {
 162             return get_ptr();
 163         }
 164
 165         inline const T *end() const
 166         {
 167             return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.end() : &fixed_element(m_fixed_size));
 168         }
 169         inline T *end()
 170         {
 171             return (m_dynamic_elements.get_ptr() ? m_dynamic_elements.end() : &fixed_element(m_fixed_size));
 172         }
 173
 174         inline const T &front() const
 175         {
 176             VOGL_ASSERT(size());
 177             return begin()[0];
 178         }
 179         inline T &front()
 180         {
 181             VOGL_ASSERT(size());
 182             return begin()[0];
 183         }
 184
 185         inline const T &back() const
 186         {
 187             VOGL_ASSERT(size());
 188             return end()[-1];
 189         }
 190         inline T &back()
 191         {
 192             VOGL_ASSERT(size());
 193             return end()[-1];
 194         }
 195
 196         inline const T &operator[](uint i) const
 197         {
 198             VOGL_ASSERT(i < size());
 199             return get_ptr()[i];
 200         }
 201
 202         inline T &operator[](uint i)
 203         {
 204             VOGL_ASSERT(i < size());
 205             return get_ptr()[i];
 206         }
 207
 208         inline void set_all(const T &val)
 209         {
 210             if (VOGL_IS_BITWISE_COPYABLE(T) && (sizeof(T) == sizeof(uint8)))
 211                 memset(get_ptr(), *reinterpret_cast<const uint8 *>(&val), size());
 212             else
 213             {
 214                 T *p = get_ptr();
 215                 T *pEnd = p + size();
 216                 while (p != pEnd)
 217                     *p++ = val;
 218             }
 219         }
 220
 221         inline void resize(uint n, bool grow_hint = false)
 222         {
 223             if (is_dynamic())
 224             {
 225                 m_dynamic_elements.resize(n, grow_hint);
 226             }
 227             else if (n <= N)
 228             {
 229                 if (n < m_fixed_size)
 230                     scalar_type<T>::destruct_array(&fixed_element(n), m_fixed_size - n);
 231                 else if (n > m_fixed_size)
 232                     scalar_type<T>::construct_array(&fixed_element(m_fixed_size), n - m_fixed_size);
 233                 m_fixed_size = n;
 234             }
 235             else
 236             {
 237                 switch_to_dynamic(n);
 238                 m_dynamic_elements.resize(n);
 239             }
 240         }
 241
 242         inline void reserve(uint n)
 243         {
 244             if ((n <= N) || (n <= size()))
 245                 return;
 246
 247             switch_to_dynamic(n);
 248         }
 249
 250         inline void push_back(const T &obj)
 251         {
 252             if (is_dynamic())
 253                 m_dynamic_elements.push_back(obj);
 254             else if ((m_fixed_size + 1) > N)
 255             {
 256                 switch_to_dynamic(m_fixed_size + 1);
 257                 m_dynamic_elements.push_back(obj);
 258             }
 259             else
 260             {
 261                 scalar_type<T>::construct(&fixed_element(m_fixed_size), obj);
 262                 ++m_fixed_size;
 263             }
 264         }
 265
 266         inline T *enlarge(uint n)
 267         {
 268             if ((m_fixed_size + n) > N)
 269                 switch_to_dynamic(m_fixed_size + n);
 270
 271             if (is_dynamic())
 272                 return m_dynamic_elements.enlarge(n);
 273
 274             T *pResult = &fixed_element(m_fixed_size);
 275             scalar_type<T>::construct_array(pResult, n);
 276             m_fixed_size += n;
 277             return pResult;
 278         }
 279
 280         inline void pop_back()
 281         {
 282             if (is_dynamic())
 283                 m_dynamic_elements.pop_back();
 284             else
 285             {
 286                 VOGL_ASSERT(m_fixed_size);
 287                 if (m_fixed_size)
 288                 {
 289                     --m_fixed_size;
 290                     scalar_type<T>::destruct(&fixed_element(m_fixed_size));
 291                 }
 292             }
 293         }
 294
 295         inline void insert(uint index, const T *p, uint n)
 296         {
 297             VOGL_ASSERT(((p + n) <= &fixed_element(0)) || (p >= &fixed_element(m_fixed_size)));
 298
 299             if ((m_fixed_size + n) > N)
 300                 switch_to_dynamic(m_fixed_size + n);
 301
 302             if (is_dynamic())
 303             {
 304                 m_dynamic_elements.insert(index, p, n);
 305                 return;
 306             }
 307
 308             VOGL_ASSERT(index <= m_fixed_size);
 309             if (!n)
 310                 return;
 311
 312             const uint orig_size = m_fixed_size;
 313             resize(m_fixed_size + n);
 314
 315             VOGL_ASSERT(!is_dynamic());
 316
 317             const uint num_to_move = orig_size - index;
 318
 319             if (VOGL_IS_BITWISE_COPYABLE(T))
 320             {
 321                 // This overwrites the destination object bits, but bitwise copyable means we don't need to worry about destruction.
 322                 memmove(&fixed_element(0) + index + n, &fixed_element(0) + index, sizeof(T) * num_to_move);
 323             }
 324             else
 325             {
 326                 const T *pSrc = &fixed_element(0) + orig_size - 1;
 327                 T *pDst = const_cast<T *>(pSrc) + n;
 328
 329                 for (uint i = 0; i < num_to_move; i++)
 330                 {
 331                     VOGL_ASSERT((pDst - &fixed_element(0)) < (int)m_fixed_size);
 332                     *pDst-- = *pSrc--;
 333                 }
 334             }
 335
 336             T *pDst = &fixed_element(0) + index;
 337
 338             if (VOGL_IS_BITWISE_COPYABLE(T))
 339             {
 340                 // This copies in the new bits, overwriting the existing objects, which is OK for copyable types that don't need destruction.
 341                 memcpy(pDst, p, sizeof(T) * n);
 342             }
 343             else
 344             {
 345                 for (uint i = 0; i < n; i++)
 346                 {
 347                     VOGL_ASSERT((pDst - &fixed_element(0)) < (int)m_fixed_size);
 348                     *pDst++ = *p++;
 349                 }
 350             }
 351         }
 352
 353         inline void insert(uint index, const T &obj)
 354         {
 355             insert(index, &obj, 1);
 356         }
 357
 358         // push_front() isn't going to be very fast - it's only here for usability.
 359         inline void push_front(const T &obj)
 360         {
 361             insert(0, &obj, 1);
 362         }
 363
 364         inline growable_array &append(const growable_array &other)
 365         {
 366             VOGL_ASSERT(this != &other);
 367             if (other.size())
 368                 insert(size(), other.get_ptr(), other.size());
 369             return *this;
 370         }
 371
 372         inline growable_array &append(const T *p, uint n)
 373         {
 374             if (n)
 375                 insert(size(), p, n);
 376             return *this;
 377         }
 378
 379         inline void erase(uint start, uint n)
 380         {
 381             if (is_dynamic())
 382             {
 383                 m_dynamic_elements.erase(start, n);
 384                 return;
 385             }
 386
 387             VOGL_ASSERT((start + n) <= m_fixed_size);
 388             if ((start + n) > m_fixed_size)
 389                 return;
 390
 391             if (!n)
 392                 return;
 393
 394             const uint num_to_move = m_fixed_size - (start + n);
 395
 396             T *pDst = &fixed_element(0) + start;
 397
 398             const T *pSrc = &fixed_element(0) + start + n;
 399
 400             if (VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T))
 401             {
 402                 // This test is overly cautious.
 403                 if ((!VOGL_IS_BITWISE_COPYABLE(T)) || VOGL_HAS_DESTRUCTOR(T))
 404                 {
 405                     // Type has been marked explictly as bitwise movable, which means we can move them around but they may need to be destructed.
 406                     // First destroy the erased objects.
 407                     scalar_type<T>::destruct_array(pDst, n);
 408                 }
 409
 410                 // Copy "down" the objects to preserve, filling in the empty slots.
 411                 memmove(pDst, pSrc, num_to_move * sizeof(T));
 412             }
 413             else
 414             {
 415                 // Type is not bitwise copyable or movable.
 416                 // Move them down one at a time by using the equals operator, and destroying anything that's left over at the end.
 417                 T *pDst_end = pDst + num_to_move;
 418                 while (pDst != pDst_end)
 419                     *pDst++ = *pSrc++;
 420
 421                 scalar_type<T>::destruct_array(pDst_end, n);
 422             }
 423
 424             m_fixed_size -= n;
 425         }
 426
 427         inline void erase(uint index)
 428         {
 429             erase(index, 1);
 430         }
 431
 432         inline void erase_unordered(uint index)
 433         {
 434             VOGL_ASSERT(index < size());
 435
 436             if ((index + 1) < size())
 437                 (*this)[index] = back();
 438
 439             pop_back();
 440         }
 441
 442         inline void sort()
 443         {
 444             introsort(begin(), end());
 445         }
 446
 447         template <typename Comp>
 448         inline void sort(Comp compare_obj)
 449         {
 450             introsort(begin(), end(), compare_obj);
 451         }
 452
 453         inline bool is_sorted() const
 454         {
 455             for (uint i = 1; i < size(); ++i)
 456                 if ((*this)[i] < (*this)[i - 1])
 457                     return false;
 458             return true;
 459         }
 460
 461         inline void unique()
 462         {
 463             if (!is_empty())
 464             {
 465                 sort();
 466
 467                 resize(static_cast<uint>(std::unique(begin(), end()) - begin()));
 468             }
 469         }
 470
 471         inline void reverse()
 472         {
 473             uint cur_size = size();
 474             uint j = cur_size >> 1;
 475             T *p = get_ptr();
 476             for (uint i = 0; i < j; i++)
 477                 utils::swap(p[i], p[cur_size - 1 - i]);
 478         }
 479
 480         inline int find(const T &key) const
 481         {
 482             uint cur_size;
 483             const T *p;
 484             if (is_dynamic())
 485             {
 486                 cur_size = m_dynamic_elements.size();
 487                 p = m_dynamic_elements.get_ptr();
 488             }
 489             else
 490             {
 491                 cur_size = m_fixed_size;
 492                 p = &fixed_element(0);
 493             }
 494
 495             VOGL_ASSERT(cur_size <= cINT32_MAX);
 496
 497             const T *p_end = p + cur_size;
 498
 499             uint index = 0;
 500
 501             while (p != p_end)
 502             {
 503                 if (key == *p)
 504                     return index;
 505
 506                 p++;
 507                 index++;
 508             }
 509
 510             return cInvalidIndex;
 511         }
 512
 513         inline int find_last(const T &key) const
 514         {
 515             uint cur_size;
 516             const T *p;
 517             if (is_dynamic())
 518             {
 519                 cur_size = m_dynamic_elements.size();
 520                 p = m_dynamic_elements.get_ptr();
 521             }
 522             else
 523             {
 524                 cur_size = m_fixed_size;
 525                 p = &fixed_element(0);
 526             }
 527
 528             VOGL_ASSERT(cur_size <= cINT32_MAX);
 529
 530             for (int i = cur_size - 1; i >= 0; --i)
 531                 if (p[i] == key)
 532                     return i;
 533
 534             return cInvalidIndex;
 535         }
 536
 537         inline int find_sorted(const T &key) const
 538         {
 539             uint cur_size;
 540             const T *p;
 541             if (is_dynamic())
 542             {
 543                 cur_size = m_dynamic_elements.size();
 544                 p = m_dynamic_elements.get_ptr();
 545             }
 546             else
 547             {
 548                 cur_size = m_fixed_size;
 549                 p = &fixed_element(0);
 550             }
 551
 552             VOGL_ASSERT(cur_size <= cINT32_MAX);
 553
 554             int begin = 0;
 555             int end = cur_size - 1;
 556
 557             while (end >= begin)
 558             {
 559                 int mid = begin + ((end - begin) >> 1);
 560
 561                 if (p[mid] < key)
 562                     begin = mid + 1;
 563                 else if (key < p[mid])
 564                     end = mid - 1;
 565                 else
 566                     return mid;
 567             }
 568
 569             return cInvalidIndex;
 570         }
 571
 572         void swap(growable_array &rhs)
 573         {
 574             growable_array &lhs = *this;
 575
 576             if (&lhs == &rhs)
 577                 return;
 578
 579             if (lhs.is_dynamic() && !rhs.is_dynamic())
 580                 helpers::move_array(&lhs.fixed_element(0), &rhs.fixed_element(0), rhs.m_fixed_size);
 581             else if (!lhs.is_dynamic() && rhs.is_dynamic())
 582                 helpers::move_array(&rhs.fixed_element(0), &lhs.fixed_element(0), lhs.m_fixed_size);
 583             else if (!lhs.is_dynamic() && !rhs.is_dynamic())
 584             {
 585                 uint common_size = math::minimum(lhs.m_fixed_size, rhs.m_fixed_size);
 586                 for (uint i = 0; i < common_size; i++)
 587                     std::swap(lhs.fixed_element(i), rhs.fixed_element(i));
 588
 589                 if (lhs.m_fixed_size > rhs.m_fixed_size)
 590                     helpers::move_array(&rhs.fixed_element(rhs.m_fixed_size), &lhs.fixed_element(rhs.m_fixed_size), lhs.m_fixed_size - rhs.m_fixed_size);
 591                 else if (rhs.m_fixed_size > lhs.m_fixed_size)
 592                     helpers::move_array(&fixed_element(lhs.m_fixed_size), &rhs.fixed_element(lhs.m_fixed_size), rhs.m_fixed_size - lhs.m_fixed_size);
 593             }
 594
 595             lhs.m_dynamic_elements.swap(rhs.m_dynamic_elements);
 596             std::swap(lhs.m_fixed_size, rhs.m_fixed_size);
 597         }
 598
 599         void switch_to_dynamic(uint new_capacity)
 600         {
 601             if (is_dynamic())
 602             {
 603                 m_dynamic_elements.reserve(new_capacity);
 604                 return;
 605             }
 606
 607             VOGL_ASSERT((new_capacity >= m_fixed_size) && (!m_dynamic_elements.size()));
 608
 609             T *pBlock = static_cast<T *>(vogl_malloc(new_capacity * sizeof(T)));
 610
 611             if (VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T))
 612             {
 613                 memcpy(pBlock, &fixed_element(0), size_in_bytes());
 614             }
 615             else
 616             {
 617                 T *pSrc = &fixed_element(0);
 618                 T *pSrc_end = &fixed_element(m_fixed_size);
 619                 T *pDst = pBlock;
 620
 621                 while (pSrc != pSrc_end)
 622                 {
 623                     scalar_type<T>::construct(pDst++, *pSrc);
 624                     scalar_type<T>::destruct(pSrc++);
 625                 }
 626             }
 627
 628             m_dynamic_elements.grant_ownership(pBlock, m_fixed_size, new_capacity);
 629             m_fixed_size = 0;
 630         }
 631
 632         void switch_to_embedded()
 633         {
 634             if (!is_dynamic() || (m_dynamic_elements.size() > N))
 635                 return;
 636
 637             uint cur_size = m_dynamic_elements.size();
 638             T *pSrc = static_cast<T *>(m_dynamic_elements.assume_ownership());
 639
 640             if (cur_size)
 641             {
 642                 T *pDst = &fixed_element(0);
 643
 644                 if (VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T))
 645                     memcpy(pDst, pSrc, cur_size * sizeof(T));
 646                 else
 647                 {
 648                     T *pSrc_end = pSrc + cur_size;
 649
 650                     while (pSrc != pSrc_end)
 651                     {
 652                         scalar_type<T>::construct(pDst++, *pSrc);
 653                         scalar_type<T>::destruct(pSrc++);
 654                     }
 655                 }
 656             }
 657
 658             m_fixed_size = cur_size;
 659             vogl_free(pSrc);
 660         }
 661
 662         inline bool operator==(const growable_array &rhs) const
 663         {
 664             uint n = size();
 665             if (n != rhs.size())
 666                 return false;
 667
 668             for (uint i = 0; i < n; i++)
 669                 if (!((*this)[i] == rhs[i]))
 670                     return false;
 671
 672             return true;
 673         }
 674
 675         inline bool operator!=(const growable_array &rhs) const
 676         {
 677             return !(*this == rhs);
 678         }
 679
 680         template <typename OtherT>
 681         inline bool operator==(const OtherT &rhs) const
 682         {
 683             uint n = size();
 684             if (n != rhs.size())
 685                 return false;
 686
 687             for (uint i = 0; i < n; i++)
 688                 if (!((*this)[i] == rhs[i]))
 689                     return false;
 690
 691             return true;
 692         }
 693
 694         template <typename OtherT>
 695         inline bool operator!=(const OtherT &rhs) const
 696         {
 697             return !(*this == rhs);
 698         }
 699
 700     private:
 701         vogl::vector<T> m_dynamic_elements;
 702         uint m_fixed_size;
 703         uint64_t m_fixed_elements[(N * sizeof(T) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
 704
 705         inline const T &fixed_element(uint i) const
 706         {
 707             return reinterpret_cast<const T *>(m_fixed_elements)[i];
 708         }
 709         inline T &fixed_element(uint i)
 710         {
 711             return reinterpret_cast<T *>(m_fixed_elements)[i];
 712         }
 713     };
 714
 715 } // namespace vogl
 716
 717 #endif // VOGL_GROWABLE_ARRAY_H