SkTDArray.h 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372
  1. /*
  2. * Copyright 2006 The Android Open Source Project
  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 SkTDArray_DEFINED
  8. #define SkTDArray_DEFINED
  9. #include "include/core/SkTypes.h"
  10. #include "include/private/SkMalloc.h"
  11. #include "include/private/SkTo.h"
  12. #include <initializer_list>
  13. #include <utility>
  14. template <typename T> class SkTDArray {
  15. public:
  16. SkTDArray() : fArray(nullptr), fReserve(0), fCount(0) {}
  17. SkTDArray(const T src[], int count) {
  18. SkASSERT(src || count == 0);
  19. fReserve = fCount = 0;
  20. fArray = nullptr;
  21. if (count) {
  22. fArray = (T*)sk_malloc_throw(count * sizeof(T));
  23. memcpy(fArray, src, sizeof(T) * count);
  24. fReserve = fCount = count;
  25. }
  26. }
  27. SkTDArray(const std::initializer_list<T>& list) : SkTDArray(list.begin(), list.size()) {}
  28. SkTDArray(const SkTDArray<T>& src) : fArray(nullptr), fReserve(0), fCount(0) {
  29. SkTDArray<T> tmp(src.fArray, src.fCount);
  30. this->swap(tmp);
  31. }
  32. SkTDArray(SkTDArray<T>&& src) : fArray(nullptr), fReserve(0), fCount(0) {
  33. this->swap(src);
  34. }
  35. ~SkTDArray() {
  36. sk_free(fArray);
  37. }
  38. SkTDArray<T>& operator=(const SkTDArray<T>& src) {
  39. if (this != &src) {
  40. if (src.fCount > fReserve) {
  41. SkTDArray<T> tmp(src.fArray, src.fCount);
  42. this->swap(tmp);
  43. } else {
  44. sk_careful_memcpy(fArray, src.fArray, sizeof(T) * src.fCount);
  45. fCount = src.fCount;
  46. }
  47. }
  48. return *this;
  49. }
  50. SkTDArray<T>& operator=(SkTDArray<T>&& src) {
  51. if (this != &src) {
  52. this->swap(src);
  53. src.reset();
  54. }
  55. return *this;
  56. }
  57. friend bool operator==(const SkTDArray<T>& a, const SkTDArray<T>& b) {
  58. return a.fCount == b.fCount &&
  59. (a.fCount == 0 ||
  60. !memcmp(a.fArray, b.fArray, a.fCount * sizeof(T)));
  61. }
  62. friend bool operator!=(const SkTDArray<T>& a, const SkTDArray<T>& b) {
  63. return !(a == b);
  64. }
  65. void swap(SkTDArray<T>& that) {
  66. using std::swap;
  67. swap(fArray, that.fArray);
  68. swap(fReserve, that.fReserve);
  69. swap(fCount, that.fCount);
  70. }
  71. bool isEmpty() const { return fCount == 0; }
  72. bool empty() const { return this->isEmpty(); }
  73. /**
  74. * Return the number of elements in the array
  75. */
  76. int count() const { return fCount; }
  77. size_t size() const { return fCount; }
  78. /**
  79. * Return the total number of elements allocated.
  80. * reserved() - count() gives you the number of elements you can add
  81. * without causing an allocation.
  82. */
  83. int reserved() const { return fReserve; }
  84. /**
  85. * return the number of bytes in the array: count * sizeof(T)
  86. */
  87. size_t bytes() const { return fCount * sizeof(T); }
  88. T* begin() { return fArray; }
  89. const T* begin() const { return fArray; }
  90. T* end() { return fArray ? fArray + fCount : nullptr; }
  91. const T* end() const { return fArray ? fArray + fCount : nullptr; }
  92. T& operator[](int index) {
  93. SkASSERT(index < fCount);
  94. return fArray[index];
  95. }
  96. const T& operator[](int index) const {
  97. SkASSERT(index < fCount);
  98. return fArray[index];
  99. }
  100. T& getAt(int index) {
  101. return (*this)[index];
  102. }
  103. void reset() {
  104. if (fArray) {
  105. sk_free(fArray);
  106. fArray = nullptr;
  107. fReserve = fCount = 0;
  108. } else {
  109. SkASSERT(fReserve == 0 && fCount == 0);
  110. }
  111. }
  112. void rewind() {
  113. // same as setCount(0)
  114. fCount = 0;
  115. }
  116. /**
  117. * Sets the number of elements in the array.
  118. * If the array does not have space for count elements, it will increase
  119. * the storage allocated to some amount greater than that required.
  120. * It will never shrink the storage.
  121. */
  122. void setCount(int count) {
  123. SkASSERT(count >= 0);
  124. if (count > fReserve) {
  125. this->resizeStorageToAtLeast(count);
  126. }
  127. fCount = count;
  128. }
  129. void setReserve(int reserve) {
  130. SkASSERT(reserve >= 0);
  131. if (reserve > fReserve) {
  132. this->resizeStorageToAtLeast(reserve);
  133. }
  134. }
  135. void reserve(size_t n) {
  136. SkASSERT_RELEASE(SkTFitsIn<int>(n));
  137. this->setReserve(SkToInt(n));
  138. }
  139. T* prepend() {
  140. this->adjustCount(1);
  141. memmove(fArray + 1, fArray, (fCount - 1) * sizeof(T));
  142. return fArray;
  143. }
  144. T* append() {
  145. return this->append(1, nullptr);
  146. }
  147. T* append(int count, const T* src = nullptr) {
  148. int oldCount = fCount;
  149. if (count) {
  150. SkASSERT(src == nullptr || fArray == nullptr ||
  151. src + count <= fArray || fArray + oldCount <= src);
  152. this->adjustCount(count);
  153. if (src) {
  154. memcpy(fArray + oldCount, src, sizeof(T) * count);
  155. }
  156. }
  157. return fArray + oldCount;
  158. }
  159. T* insert(int index) {
  160. return this->insert(index, 1, nullptr);
  161. }
  162. T* insert(int index, int count, const T* src = nullptr) {
  163. SkASSERT(count);
  164. SkASSERT(index <= fCount);
  165. size_t oldCount = fCount;
  166. this->adjustCount(count);
  167. T* dst = fArray + index;
  168. memmove(dst + count, dst, sizeof(T) * (oldCount - index));
  169. if (src) {
  170. memcpy(dst, src, sizeof(T) * count);
  171. }
  172. return dst;
  173. }
  174. void remove(int index, int count = 1) {
  175. SkASSERT(index + count <= fCount);
  176. fCount = fCount - count;
  177. memmove(fArray + index, fArray + index + count, sizeof(T) * (fCount - index));
  178. }
  179. void removeShuffle(int index) {
  180. SkASSERT(index < fCount);
  181. int newCount = fCount - 1;
  182. fCount = newCount;
  183. if (index != newCount) {
  184. memcpy(fArray + index, fArray + newCount, sizeof(T));
  185. }
  186. }
  187. int find(const T& elem) const {
  188. const T* iter = fArray;
  189. const T* stop = fArray + fCount;
  190. for (; iter < stop; iter++) {
  191. if (*iter == elem) {
  192. return SkToInt(iter - fArray);
  193. }
  194. }
  195. return -1;
  196. }
  197. int rfind(const T& elem) const {
  198. const T* iter = fArray + fCount;
  199. const T* stop = fArray;
  200. while (iter > stop) {
  201. if (*--iter == elem) {
  202. return SkToInt(iter - stop);
  203. }
  204. }
  205. return -1;
  206. }
  207. /**
  208. * Returns true iff the array contains this element.
  209. */
  210. bool contains(const T& elem) const {
  211. return (this->find(elem) >= 0);
  212. }
  213. /**
  214. * Copies up to max elements into dst. The number of items copied is
  215. * capped by count - index. The actual number copied is returned.
  216. */
  217. int copyRange(T* dst, int index, int max) const {
  218. SkASSERT(max >= 0);
  219. SkASSERT(!max || dst);
  220. if (index >= fCount) {
  221. return 0;
  222. }
  223. int count = SkMin32(max, fCount - index);
  224. memcpy(dst, fArray + index, sizeof(T) * count);
  225. return count;
  226. }
  227. void copy(T* dst) const {
  228. this->copyRange(dst, 0, fCount);
  229. }
  230. // routines to treat the array like a stack
  231. void push_back(const T& v) { *this->append() = v; }
  232. T* push() { return this->append(); }
  233. const T& top() const { return (*this)[fCount - 1]; }
  234. T& top() { return (*this)[fCount - 1]; }
  235. void pop(T* elem) { SkASSERT(fCount > 0); if (elem) *elem = (*this)[fCount - 1]; --fCount; }
  236. void pop() { SkASSERT(fCount > 0); --fCount; }
  237. void deleteAll() {
  238. T* iter = fArray;
  239. T* stop = fArray + fCount;
  240. while (iter < stop) {
  241. delete *iter;
  242. iter += 1;
  243. }
  244. this->reset();
  245. }
  246. void freeAll() {
  247. T* iter = fArray;
  248. T* stop = fArray + fCount;
  249. while (iter < stop) {
  250. sk_free(*iter);
  251. iter += 1;
  252. }
  253. this->reset();
  254. }
  255. void unrefAll() {
  256. T* iter = fArray;
  257. T* stop = fArray + fCount;
  258. while (iter < stop) {
  259. (*iter)->unref();
  260. iter += 1;
  261. }
  262. this->reset();
  263. }
  264. void safeUnrefAll() {
  265. T* iter = fArray;
  266. T* stop = fArray + fCount;
  267. while (iter < stop) {
  268. SkSafeUnref(*iter);
  269. iter += 1;
  270. }
  271. this->reset();
  272. }
  273. #ifdef SK_DEBUG
  274. void validate() const {
  275. SkASSERT((fReserve == 0 && fArray == nullptr) ||
  276. (fReserve > 0 && fArray != nullptr));
  277. SkASSERT(fCount <= fReserve);
  278. }
  279. #endif
  280. void shrinkToFit() {
  281. fReserve = fCount;
  282. fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
  283. }
  284. private:
  285. T* fArray;
  286. int fReserve;
  287. int fCount;
  288. /**
  289. * Adjusts the number of elements in the array.
  290. * This is the same as calling setCount(count() + delta).
  291. */
  292. void adjustCount(int delta) {
  293. SkASSERT(delta > 0);
  294. // We take care to avoid overflow here.
  295. // The sum of fCount and delta is at most 4294967294, which fits fine in uint32_t.
  296. uint32_t count = (uint32_t)fCount + (uint32_t)delta;
  297. SkASSERT_RELEASE( SkTFitsIn<int>(count) );
  298. this->setCount(SkTo<int>(count));
  299. }
  300. /**
  301. * Increase the storage allocation such that it can hold (fCount + extra)
  302. * elements.
  303. * It never shrinks the allocation, and it may increase the allocation by
  304. * more than is strictly required, based on a private growth heuristic.
  305. *
  306. * note: does NOT modify fCount
  307. */
  308. void resizeStorageToAtLeast(int count) {
  309. SkASSERT(count > fReserve);
  310. // We take care to avoid overflow here.
  311. // The maximum value we can get for reserve here is 2684354563, which fits in uint32_t.
  312. uint32_t reserve = (uint32_t)count + 4;
  313. reserve += reserve / 4;
  314. SkASSERT_RELEASE( SkTFitsIn<int>(reserve) );
  315. fReserve = SkTo<int>(reserve);
  316. fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
  317. }
  318. };
  319. template <typename T> static inline void swap(SkTDArray<T>& a, SkTDArray<T>& b) {
  320. a.swap(b);
  321. }
  322. #endif