SkTArray.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641
  1. /*
  2. * Copyright 2011 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #ifndef SkTArray_DEFINED
  8. #define SkTArray_DEFINED
  9. #include "include/core/SkMath.h"
  10. #include "include/core/SkTypes.h"
  11. #include "include/private/SkMalloc.h"
  12. #include "include/private/SkSafe32.h"
  13. #include "include/private/SkTLogic.h"
  14. #include "include/private/SkTemplates.h"
  15. #include <string.h>
  16. #include <memory>
  17. #include <new>
  18. #include <utility>
  19. /** When MEM_MOVE is true T will be bit copied when moved.
  20. When MEM_MOVE is false, T will be copy constructed / destructed.
  21. In all cases T will be default-initialized on allocation,
  22. and its destructor will be called from this object's destructor.
  23. */
  24. template <typename T, bool MEM_MOVE = false> class SkTArray {
  25. public:
  26. /**
  27. * Creates an empty array with no initial storage
  28. */
  29. SkTArray() { this->init(); }
  30. /**
  31. * Creates an empty array that will preallocate space for reserveCount
  32. * elements.
  33. */
  34. explicit SkTArray(int reserveCount) { this->init(0, reserveCount); }
  35. /**
  36. * Copies one array to another. The new array will be heap allocated.
  37. */
  38. SkTArray(const SkTArray& that) {
  39. this->init(that.fCount);
  40. this->copy(that.fItemArray);
  41. }
  42. SkTArray(SkTArray&& that) {
  43. // TODO: If 'that' owns its memory why don't we just steal the pointer?
  44. this->init(that.fCount);
  45. that.move(fMemArray);
  46. that.fCount = 0;
  47. }
  48. /**
  49. * Creates a SkTArray by copying contents of a standard C array. The new
  50. * array will be heap allocated. Be careful not to use this constructor
  51. * when you really want the (void*, int) version.
  52. */
  53. SkTArray(const T* array, int count) {
  54. this->init(count);
  55. this->copy(array);
  56. }
  57. SkTArray& operator=(const SkTArray& that) {
  58. if (this == &that) {
  59. return *this;
  60. }
  61. for (int i = 0; i < fCount; ++i) {
  62. fItemArray[i].~T();
  63. }
  64. fCount = 0;
  65. this->checkRealloc(that.count());
  66. fCount = that.count();
  67. this->copy(that.fItemArray);
  68. return *this;
  69. }
  70. SkTArray& operator=(SkTArray&& that) {
  71. if (this == &that) {
  72. return *this;
  73. }
  74. for (int i = 0; i < fCount; ++i) {
  75. fItemArray[i].~T();
  76. }
  77. fCount = 0;
  78. this->checkRealloc(that.count());
  79. fCount = that.count();
  80. that.move(fMemArray);
  81. that.fCount = 0;
  82. return *this;
  83. }
  84. ~SkTArray() {
  85. for (int i = 0; i < fCount; ++i) {
  86. fItemArray[i].~T();
  87. }
  88. if (fOwnMemory) {
  89. sk_free(fMemArray);
  90. }
  91. }
  92. /**
  93. * Resets to count() == 0 and resets any reserve count.
  94. */
  95. void reset() {
  96. this->pop_back_n(fCount);
  97. fReserved = false;
  98. }
  99. /**
  100. * Resets to count() = n newly constructed T objects and resets any reserve count.
  101. */
  102. void reset(int n) {
  103. SkASSERT(n >= 0);
  104. for (int i = 0; i < fCount; ++i) {
  105. fItemArray[i].~T();
  106. }
  107. // Set fCount to 0 before calling checkRealloc so that no elements are moved.
  108. fCount = 0;
  109. this->checkRealloc(n);
  110. fCount = n;
  111. for (int i = 0; i < fCount; ++i) {
  112. new (fItemArray + i) T;
  113. }
  114. fReserved = false;
  115. }
  116. /**
  117. * Resets to a copy of a C array and resets any reserve count.
  118. */
  119. void reset(const T* array, int count) {
  120. for (int i = 0; i < fCount; ++i) {
  121. fItemArray[i].~T();
  122. }
  123. fCount = 0;
  124. this->checkRealloc(count);
  125. fCount = count;
  126. this->copy(array);
  127. fReserved = false;
  128. }
  129. /**
  130. * Ensures there is enough reserved space for n additional elements. The is guaranteed at least
  131. * until the array size grows above n and subsequently shrinks below n, any version of reset()
  132. * is called, or reserve() is called again.
  133. */
  134. void reserve(int n) {
  135. SkASSERT(n >= 0);
  136. if (n > 0) {
  137. this->checkRealloc(n);
  138. fReserved = fOwnMemory;
  139. } else {
  140. fReserved = false;
  141. }
  142. }
  143. void removeShuffle(int n) {
  144. SkASSERT(n < fCount);
  145. int newCount = fCount - 1;
  146. fCount = newCount;
  147. fItemArray[n].~T();
  148. if (n != newCount) {
  149. this->move(n, newCount);
  150. }
  151. }
  152. /**
  153. * Number of elements in the array.
  154. */
  155. int count() const { return fCount; }
  156. /**
  157. * Is the array empty.
  158. */
  159. bool empty() const { return !fCount; }
  160. /**
  161. * Adds 1 new default-initialized T value and returns it by reference. Note
  162. * the reference only remains valid until the next call that adds or removes
  163. * elements.
  164. */
  165. T& push_back() {
  166. void* newT = this->push_back_raw(1);
  167. return *new (newT) T;
  168. }
  169. /**
  170. * Version of above that uses a copy constructor to initialize the new item
  171. */
  172. T& push_back(const T& t) {
  173. void* newT = this->push_back_raw(1);
  174. return *new (newT) T(t);
  175. }
  176. /**
  177. * Version of above that uses a move constructor to initialize the new item
  178. */
  179. T& push_back(T&& t) {
  180. void* newT = this->push_back_raw(1);
  181. return *new (newT) T(std::move(t));
  182. }
  183. /**
  184. * Construct a new T at the back of this array.
  185. */
  186. template<class... Args> T& emplace_back(Args&&... args) {
  187. void* newT = this->push_back_raw(1);
  188. return *new (newT) T(std::forward<Args>(args)...);
  189. }
  190. /**
  191. * Allocates n more default-initialized T values, and returns the address of
  192. * the start of that new range. Note: this address is only valid until the
  193. * next API call made on the array that might add or remove elements.
  194. */
  195. T* push_back_n(int n) {
  196. SkASSERT(n >= 0);
  197. void* newTs = this->push_back_raw(n);
  198. for (int i = 0; i < n; ++i) {
  199. new (static_cast<char*>(newTs) + i * sizeof(T)) T;
  200. }
  201. return static_cast<T*>(newTs);
  202. }
  203. /**
  204. * Version of above that uses a copy constructor to initialize all n items
  205. * to the same T.
  206. */
  207. T* push_back_n(int n, const T& t) {
  208. SkASSERT(n >= 0);
  209. void* newTs = this->push_back_raw(n);
  210. for (int i = 0; i < n; ++i) {
  211. new (static_cast<char*>(newTs) + i * sizeof(T)) T(t);
  212. }
  213. return static_cast<T*>(newTs);
  214. }
  215. /**
  216. * Version of above that uses a copy constructor to initialize the n items
  217. * to separate T values.
  218. */
  219. T* push_back_n(int n, const T t[]) {
  220. SkASSERT(n >= 0);
  221. this->checkRealloc(n);
  222. for (int i = 0; i < n; ++i) {
  223. new (fItemArray + fCount + i) T(t[i]);
  224. }
  225. fCount += n;
  226. return fItemArray + fCount - n;
  227. }
  228. /**
  229. * Version of above that uses the move constructor to set n items.
  230. */
  231. T* move_back_n(int n, T* t) {
  232. SkASSERT(n >= 0);
  233. this->checkRealloc(n);
  234. for (int i = 0; i < n; ++i) {
  235. new (fItemArray + fCount + i) T(std::move(t[i]));
  236. }
  237. fCount += n;
  238. return fItemArray + fCount - n;
  239. }
  240. /**
  241. * Removes the last element. Not safe to call when count() == 0.
  242. */
  243. void pop_back() {
  244. SkASSERT(fCount > 0);
  245. --fCount;
  246. fItemArray[fCount].~T();
  247. this->checkRealloc(0);
  248. }
  249. /**
  250. * Removes the last n elements. Not safe to call when count() < n.
  251. */
  252. void pop_back_n(int n) {
  253. SkASSERT(n >= 0);
  254. SkASSERT(fCount >= n);
  255. fCount -= n;
  256. for (int i = 0; i < n; ++i) {
  257. fItemArray[fCount + i].~T();
  258. }
  259. this->checkRealloc(0);
  260. }
  261. /**
  262. * Pushes or pops from the back to resize. Pushes will be default
  263. * initialized.
  264. */
  265. void resize_back(int newCount) {
  266. SkASSERT(newCount >= 0);
  267. if (newCount > fCount) {
  268. this->push_back_n(newCount - fCount);
  269. } else if (newCount < fCount) {
  270. this->pop_back_n(fCount - newCount);
  271. }
  272. }
  273. /** Swaps the contents of this array with that array. Does a pointer swap if possible,
  274. otherwise copies the T values. */
  275. void swap(SkTArray& that) {
  276. using std::swap;
  277. if (this == &that) {
  278. return;
  279. }
  280. if (fOwnMemory && that.fOwnMemory) {
  281. swap(fItemArray, that.fItemArray);
  282. swap(fCount, that.fCount);
  283. swap(fAllocCount, that.fAllocCount);
  284. } else {
  285. // This could be more optimal...
  286. SkTArray copy(std::move(that));
  287. that = std::move(*this);
  288. *this = std::move(copy);
  289. }
  290. }
  291. T* begin() {
  292. return fItemArray;
  293. }
  294. const T* begin() const {
  295. return fItemArray;
  296. }
  297. T* end() {
  298. return fItemArray ? fItemArray + fCount : nullptr;
  299. }
  300. const T* end() const {
  301. return fItemArray ? fItemArray + fCount : nullptr;
  302. }
  303. T* data() { return fItemArray; }
  304. const T* data() const { return fItemArray; }
  305. size_t size() const { return (size_t)fCount; }
  306. void resize(size_t count) { this->resize_back((int)count); }
  307. /**
  308. * Get the i^th element.
  309. */
  310. T& operator[] (int i) {
  311. SkASSERT(i < fCount);
  312. SkASSERT(i >= 0);
  313. return fItemArray[i];
  314. }
  315. const T& operator[] (int i) const {
  316. SkASSERT(i < fCount);
  317. SkASSERT(i >= 0);
  318. return fItemArray[i];
  319. }
  320. /**
  321. * equivalent to operator[](0)
  322. */
  323. T& front() { SkASSERT(fCount > 0); return fItemArray[0];}
  324. const T& front() const { SkASSERT(fCount > 0); return fItemArray[0];}
  325. /**
  326. * equivalent to operator[](count() - 1)
  327. */
  328. T& back() { SkASSERT(fCount); return fItemArray[fCount - 1];}
  329. const T& back() const { SkASSERT(fCount > 0); return fItemArray[fCount - 1];}
  330. /**
  331. * equivalent to operator[](count()-1-i)
  332. */
  333. T& fromBack(int i) {
  334. SkASSERT(i >= 0);
  335. SkASSERT(i < fCount);
  336. return fItemArray[fCount - i - 1];
  337. }
  338. const T& fromBack(int i) const {
  339. SkASSERT(i >= 0);
  340. SkASSERT(i < fCount);
  341. return fItemArray[fCount - i - 1];
  342. }
  343. bool operator==(const SkTArray<T, MEM_MOVE>& right) const {
  344. int leftCount = this->count();
  345. if (leftCount != right.count()) {
  346. return false;
  347. }
  348. for (int index = 0; index < leftCount; ++index) {
  349. if (fItemArray[index] != right.fItemArray[index]) {
  350. return false;
  351. }
  352. }
  353. return true;
  354. }
  355. bool operator!=(const SkTArray<T, MEM_MOVE>& right) const {
  356. return !(*this == right);
  357. }
  358. inline int allocCntForTest() const;
  359. protected:
  360. /**
  361. * Creates an empty array that will use the passed storage block until it
  362. * is insufficiently large to hold the entire array.
  363. */
  364. template <int N>
  365. SkTArray(SkAlignedSTStorage<N,T>* storage) {
  366. this->initWithPreallocatedStorage(0, storage->get(), N);
  367. }
  368. /**
  369. * Copy another array, using preallocated storage if preAllocCount >=
  370. * array.count(). Otherwise storage will only be used when array shrinks
  371. * to fit.
  372. */
  373. template <int N>
  374. SkTArray(const SkTArray& array, SkAlignedSTStorage<N,T>* storage) {
  375. this->initWithPreallocatedStorage(array.fCount, storage->get(), N);
  376. this->copy(array.fItemArray);
  377. }
  378. /**
  379. * Move another array, using preallocated storage if preAllocCount >=
  380. * array.count(). Otherwise storage will only be used when array shrinks
  381. * to fit.
  382. */
  383. template <int N>
  384. SkTArray(SkTArray&& array, SkAlignedSTStorage<N,T>* storage) {
  385. this->initWithPreallocatedStorage(array.fCount, storage->get(), N);
  386. array.move(fMemArray);
  387. array.fCount = 0;
  388. }
  389. /**
  390. * Copy a C array, using preallocated storage if preAllocCount >=
  391. * count. Otherwise storage will only be used when array shrinks
  392. * to fit.
  393. */
  394. template <int N>
  395. SkTArray(const T* array, int count, SkAlignedSTStorage<N,T>* storage) {
  396. this->initWithPreallocatedStorage(count, storage->get(), N);
  397. this->copy(array);
  398. }
  399. private:
  400. void init(int count = 0, int reserveCount = 0) {
  401. SkASSERT(count >= 0);
  402. SkASSERT(reserveCount >= 0);
  403. fCount = count;
  404. if (!count && !reserveCount) {
  405. fAllocCount = 0;
  406. fMemArray = nullptr;
  407. fOwnMemory = true;
  408. fReserved = false;
  409. } else {
  410. fAllocCount = SkTMax(count, SkTMax(kMinHeapAllocCount, reserveCount));
  411. fMemArray = sk_malloc_throw(fAllocCount, sizeof(T));
  412. fOwnMemory = true;
  413. fReserved = reserveCount > 0;
  414. }
  415. }
  416. void initWithPreallocatedStorage(int count, void* preallocStorage, int preallocCount) {
  417. SkASSERT(count >= 0);
  418. SkASSERT(preallocCount > 0);
  419. SkASSERT(preallocStorage);
  420. fCount = count;
  421. fMemArray = nullptr;
  422. fReserved = false;
  423. if (count > preallocCount) {
  424. fAllocCount = SkTMax(count, kMinHeapAllocCount);
  425. fMemArray = sk_malloc_throw(fAllocCount, sizeof(T));
  426. fOwnMemory = true;
  427. } else {
  428. fAllocCount = preallocCount;
  429. fMemArray = preallocStorage;
  430. fOwnMemory = false;
  431. }
  432. }
  433. /** In the following move and copy methods, 'dst' is assumed to be uninitialized raw storage.
  434. * In the following move methods, 'src' is destroyed leaving behind uninitialized raw storage.
  435. */
  436. void copy(const T* src) {
  437. // Some types may be trivially copyable, in which case we *could* use memcopy; but
  438. // MEM_MOVE == true implies that the type is trivially movable, and not necessarily
  439. // trivially copyable (think sk_sp<>). So short of adding another template arg, we
  440. // must be conservative and use copy construction.
  441. for (int i = 0; i < fCount; ++i) {
  442. new (fItemArray + i) T(src[i]);
  443. }
  444. }
  445. template <bool E = MEM_MOVE> SK_WHEN(E, void) move(int dst, int src) {
  446. memcpy(&fItemArray[dst], &fItemArray[src], sizeof(T));
  447. }
  448. template <bool E = MEM_MOVE> SK_WHEN(E, void) move(void* dst) {
  449. sk_careful_memcpy(dst, fMemArray, fCount * sizeof(T));
  450. }
  451. template <bool E = MEM_MOVE> SK_WHEN(!E, void) move(int dst, int src) {
  452. new (&fItemArray[dst]) T(std::move(fItemArray[src]));
  453. fItemArray[src].~T();
  454. }
  455. template <bool E = MEM_MOVE> SK_WHEN(!E, void) move(void* dst) {
  456. for (int i = 0; i < fCount; ++i) {
  457. new (static_cast<char*>(dst) + sizeof(T) * i) T(std::move(fItemArray[i]));
  458. fItemArray[i].~T();
  459. }
  460. }
  461. static constexpr int kMinHeapAllocCount = 8;
  462. // Helper function that makes space for n objects, adjusts the count, but does not initialize
  463. // the new objects.
  464. void* push_back_raw(int n) {
  465. this->checkRealloc(n);
  466. void* ptr = fItemArray + fCount;
  467. fCount += n;
  468. return ptr;
  469. }
  470. void checkRealloc(int delta) {
  471. SkASSERT(fCount >= 0);
  472. SkASSERT(fAllocCount >= 0);
  473. SkASSERT(-delta <= fCount);
  474. // Move into 64bit math temporarily, to avoid local overflows
  475. int64_t newCount = fCount + delta;
  476. // We allow fAllocCount to be in the range [newCount, 3*newCount]. We also never shrink
  477. // when we're currently using preallocated memory, would allocate less than
  478. // kMinHeapAllocCount, or a reserve count was specified that has yet to be exceeded.
  479. bool mustGrow = newCount > fAllocCount;
  480. bool shouldShrink = fAllocCount > 3 * newCount && fOwnMemory && !fReserved;
  481. if (!mustGrow && !shouldShrink) {
  482. return;
  483. }
  484. // Whether we're growing or shrinking, we leave at least 50% extra space for future growth.
  485. int64_t newAllocCount = newCount + ((newCount + 1) >> 1);
  486. // Align the new allocation count to kMinHeapAllocCount.
  487. static_assert(SkIsPow2(kMinHeapAllocCount), "min alloc count not power of two.");
  488. newAllocCount = (newAllocCount + (kMinHeapAllocCount - 1)) & ~(kMinHeapAllocCount - 1);
  489. // At small sizes the old and new alloc count can both be kMinHeapAllocCount.
  490. if (newAllocCount == fAllocCount) {
  491. return;
  492. }
  493. fAllocCount = Sk64_pin_to_s32(newAllocCount);
  494. SkASSERT(fAllocCount >= newCount);
  495. void* newMemArray = sk_malloc_throw(fAllocCount, sizeof(T));
  496. this->move(newMemArray);
  497. if (fOwnMemory) {
  498. sk_free(fMemArray);
  499. }
  500. fMemArray = newMemArray;
  501. fOwnMemory = true;
  502. fReserved = false;
  503. }
  504. union {
  505. T* fItemArray;
  506. void* fMemArray;
  507. };
  508. int fCount;
  509. int fAllocCount;
  510. bool fOwnMemory : 1;
  511. bool fReserved : 1;
  512. };
  513. template <typename T, bool M> static inline void swap(SkTArray<T, M>& a, SkTArray<T, M>& b) {
  514. a.swap(b);
  515. }
  516. template<typename T, bool MEM_MOVE> constexpr int SkTArray<T, MEM_MOVE>::kMinHeapAllocCount;
  517. /**
  518. * Subclass of SkTArray that contains a preallocated memory block for the array.
  519. */
  520. template <int N, typename T, bool MEM_MOVE= false>
  521. class SkSTArray : public SkTArray<T, MEM_MOVE> {
  522. private:
  523. typedef SkTArray<T, MEM_MOVE> INHERITED;
  524. public:
  525. SkSTArray() : INHERITED(&fStorage) {
  526. }
  527. SkSTArray(const SkSTArray& array)
  528. : INHERITED(array, &fStorage) {
  529. }
  530. SkSTArray(SkSTArray&& array)
  531. : INHERITED(std::move(array), &fStorage) {
  532. }
  533. explicit SkSTArray(const INHERITED& array)
  534. : INHERITED(array, &fStorage) {
  535. }
  536. explicit SkSTArray(INHERITED&& array)
  537. : INHERITED(std::move(array), &fStorage) {
  538. }
  539. explicit SkSTArray(int reserveCount)
  540. : INHERITED(reserveCount) {
  541. }
  542. SkSTArray(const T* array, int count)
  543. : INHERITED(array, count, &fStorage) {
  544. }
  545. SkSTArray& operator=(const SkSTArray& array) {
  546. INHERITED::operator=(array);
  547. return *this;
  548. }
  549. SkSTArray& operator=(SkSTArray&& array) {
  550. INHERITED::operator=(std::move(array));
  551. return *this;
  552. }
  553. SkSTArray& operator=(const INHERITED& array) {
  554. INHERITED::operator=(array);
  555. return *this;
  556. }
  557. SkSTArray& operator=(INHERITED&& array) {
  558. INHERITED::operator=(std::move(array));
  559. return *this;
  560. }
  561. private:
  562. SkAlignedSTStorage<N,T> fStorage;
  563. };
  564. #endif