local_vector.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414
  1. /**************************************************************************/
  2. /* local_vector.h */
  3. /**************************************************************************/
  4. /* This file is part of: */
  5. /* GODOT ENGINE */
  6. /* https://godotengine.org */
  7. /**************************************************************************/
  8. /* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
  9. /* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
  10. /* */
  11. /* Permission is hereby granted, free of charge, to any person obtaining */
  12. /* a copy of this software and associated documentation files (the */
  13. /* "Software"), to deal in the Software without restriction, including */
  14. /* without limitation the rights to use, copy, modify, merge, publish, */
  15. /* distribute, sublicense, and/or sell copies of the Software, and to */
  16. /* permit persons to whom the Software is furnished to do so, subject to */
  17. /* the following conditions: */
  18. /* */
  19. /* The above copyright notice and this permission notice shall be */
  20. /* included in all copies or substantial portions of the Software. */
  21. /* */
  22. /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
  23. /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
  24. /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
  25. /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
  26. /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
  27. /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
  28. /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
  29. /**************************************************************************/
  30. #pragma once
  31. #include "core/error/error_macros.h"
  32. #include "core/os/memory.h"
  33. #include "core/templates/sort_array.h"
  34. #include "core/templates/vector.h"
  35. #include <initializer_list>
  36. #include <type_traits>
  37. // If tight, it grows strictly as much as needed.
  38. // Otherwise, it grows exponentially (the default and what you want in most cases).
  39. template <typename T, typename U = uint32_t, bool force_trivial = false, bool tight = false>
  40. class LocalVector {
  41. static_assert(!force_trivial, "force_trivial is no longer supported. Use resize_uninitialized instead.");
  42. private:
  43. U count = 0;
  44. U capacity = 0;
  45. T *data = nullptr;
  46. template <bool p_init>
  47. void _resize(U p_size) {
  48. if (p_size < count) {
  49. if constexpr (!std::is_trivially_destructible_v<T>) {
  50. for (U i = p_size; i < count; i++) {
  51. data[i].~T();
  52. }
  53. }
  54. count = p_size;
  55. } else if (p_size > count) {
  56. reserve(p_size);
  57. if constexpr (p_init) {
  58. memnew_arr_placement(data + count, p_size - count);
  59. } else {
  60. static_assert(std::is_trivially_destructible_v<T>, "T must be trivially destructible to resize uninitialized");
  61. }
  62. count = p_size;
  63. }
  64. }
  65. public:
  66. _FORCE_INLINE_ T *ptr() { return data; }
  67. _FORCE_INLINE_ const T *ptr() const { return data; }
  68. _FORCE_INLINE_ U size() const { return count; }
  69. _FORCE_INLINE_ Span<T> span() const { return Span(data, count); }
  70. _FORCE_INLINE_ operator Span<T>() const { return span(); }
  71. // Must take a copy instead of a reference (see GH-31736).
  72. _FORCE_INLINE_ void push_back(T p_elem) {
  73. if (unlikely(count == capacity)) {
  74. reserve(count + 1);
  75. }
  76. memnew_placement(&data[count++], T(std::move(p_elem)));
  77. }
  78. void remove_at(U p_index) {
  79. ERR_FAIL_UNSIGNED_INDEX(p_index, count);
  80. count--;
  81. for (U i = p_index; i < count; i++) {
  82. data[i] = std::move(data[i + 1]);
  83. }
  84. data[count].~T();
  85. }
  86. /// Removes the item copying the last value into the position of the one to
  87. /// remove. It's generally faster than `remove_at`.
  88. void remove_at_unordered(U p_index) {
  89. ERR_FAIL_INDEX(p_index, count);
  90. count--;
  91. if (count > p_index) {
  92. data[p_index] = std::move(data[count]);
  93. }
  94. data[count].~T();
  95. }
  96. _FORCE_INLINE_ bool erase(const T &p_val) {
  97. int64_t idx = find(p_val);
  98. if (idx >= 0) {
  99. remove_at(idx);
  100. return true;
  101. }
  102. return false;
  103. }
  104. bool erase_unordered(const T &p_val) {
  105. int64_t idx = find(p_val);
  106. if (idx >= 0) {
  107. remove_at_unordered(idx);
  108. return true;
  109. }
  110. return false;
  111. }
  112. U erase_multiple_unordered(const T &p_val) {
  113. U from = 0;
  114. U occurrences = 0;
  115. while (true) {
  116. int64_t idx = find(p_val, from);
  117. if (idx == -1) {
  118. break;
  119. }
  120. remove_at_unordered(idx);
  121. from = idx;
  122. occurrences++;
  123. }
  124. return occurrences;
  125. }
  126. void reverse() {
  127. for (U i = 0; i < count / 2; i++) {
  128. SWAP(data[i], data[count - i - 1]);
  129. }
  130. }
  131. #ifndef DISABLE_DEPRECATED
  132. [[deprecated("Use reverse() instead")]] void invert() { reverse(); }
  133. #endif
  134. _FORCE_INLINE_ void clear() { resize(0); }
  135. _FORCE_INLINE_ void reset() {
  136. clear();
  137. if (data) {
  138. memfree(data);
  139. data = nullptr;
  140. capacity = 0;
  141. }
  142. }
  143. _FORCE_INLINE_ bool is_empty() const { return count == 0; }
  144. _FORCE_INLINE_ U get_capacity() const { return capacity; }
  145. void reserve(U p_size) {
  146. ERR_FAIL_COND_MSG(p_size < size(), "reserve() called with a capacity smaller than the current size. This is likely a mistake.");
  147. if (p_size > capacity) {
  148. if (tight) {
  149. capacity = p_size;
  150. } else {
  151. capacity = MAX((U)2, capacity + ((1 + capacity) >> 1));
  152. if (p_size > capacity) {
  153. capacity = p_size;
  154. }
  155. }
  156. data = (T *)memrealloc(data, capacity * sizeof(T));
  157. CRASH_COND_MSG(!data, "Out of memory");
  158. }
  159. }
  160. /// Resize the vector.
  161. /// Elements are initialized (or not) depending on what the default C++ behavior for T is.
  162. /// Note: If force_trivial is set, this will behave like resize_uninitialized instead.
  163. void resize(U p_size) {
  164. // Don't init when trivially constructible.
  165. _resize<!std::is_trivially_constructible_v<T>>(p_size);
  166. }
  167. /// Resize and set all values to 0 / false / nullptr.
  168. _FORCE_INLINE_ void resize_initialized(U p_size) { _resize<true>(p_size); }
  169. /// Resize and set all values to 0 / false / nullptr.
  170. /// This is only available for trivially destructible types (otherwise, trivial resize might be UB).
  171. _FORCE_INLINE_ void resize_uninitialized(U p_size) { _resize<false>(p_size); }
  172. _FORCE_INLINE_ const T &operator[](U p_index) const {
  173. CRASH_BAD_UNSIGNED_INDEX(p_index, count);
  174. return data[p_index];
  175. }
  176. _FORCE_INLINE_ T &operator[](U p_index) {
  177. CRASH_BAD_UNSIGNED_INDEX(p_index, count);
  178. return data[p_index];
  179. }
  180. struct Iterator {
  181. _FORCE_INLINE_ T &operator*() const {
  182. return *elem_ptr;
  183. }
  184. _FORCE_INLINE_ T *operator->() const { return elem_ptr; }
  185. _FORCE_INLINE_ Iterator &operator++() {
  186. elem_ptr++;
  187. return *this;
  188. }
  189. _FORCE_INLINE_ Iterator &operator--() {
  190. elem_ptr--;
  191. return *this;
  192. }
  193. _FORCE_INLINE_ bool operator==(const Iterator &b) const { return elem_ptr == b.elem_ptr; }
  194. _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return elem_ptr != b.elem_ptr; }
  195. Iterator(T *p_ptr) { elem_ptr = p_ptr; }
  196. Iterator() {}
  197. Iterator(const Iterator &p_it) { elem_ptr = p_it.elem_ptr; }
  198. private:
  199. T *elem_ptr = nullptr;
  200. };
  201. struct ConstIterator {
  202. _FORCE_INLINE_ const T &operator*() const {
  203. return *elem_ptr;
  204. }
  205. _FORCE_INLINE_ const T *operator->() const { return elem_ptr; }
  206. _FORCE_INLINE_ ConstIterator &operator++() {
  207. elem_ptr++;
  208. return *this;
  209. }
  210. _FORCE_INLINE_ ConstIterator &operator--() {
  211. elem_ptr--;
  212. return *this;
  213. }
  214. _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return elem_ptr == b.elem_ptr; }
  215. _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return elem_ptr != b.elem_ptr; }
  216. ConstIterator(const T *p_ptr) { elem_ptr = p_ptr; }
  217. ConstIterator() {}
  218. ConstIterator(const ConstIterator &p_it) { elem_ptr = p_it.elem_ptr; }
  219. private:
  220. const T *elem_ptr = nullptr;
  221. };
  222. _FORCE_INLINE_ Iterator begin() {
  223. return Iterator(data);
  224. }
  225. _FORCE_INLINE_ Iterator end() {
  226. return Iterator(data + size());
  227. }
  228. _FORCE_INLINE_ ConstIterator begin() const {
  229. return ConstIterator(ptr());
  230. }
  231. _FORCE_INLINE_ ConstIterator end() const {
  232. return ConstIterator(ptr() + size());
  233. }
  234. void insert(U p_pos, T p_val) {
  235. ERR_FAIL_UNSIGNED_INDEX(p_pos, count + 1);
  236. if (p_pos == count) {
  237. push_back(std::move(p_val));
  238. } else {
  239. resize(count + 1);
  240. for (U i = count - 1; i > p_pos; i--) {
  241. data[i] = std::move(data[i - 1]);
  242. }
  243. data[p_pos] = std::move(p_val);
  244. }
  245. }
  246. int64_t find(const T &p_val, int64_t p_from = 0) const {
  247. if (p_from < 0) {
  248. p_from = size() + p_from;
  249. }
  250. if (p_from < 0 || p_from >= size()) {
  251. return -1;
  252. }
  253. return span().find(p_val, p_from);
  254. }
  255. bool has(const T &p_val) const {
  256. return find(p_val) != -1;
  257. }
  258. template <typename C>
  259. void sort_custom() {
  260. U len = count;
  261. if (len == 0) {
  262. return;
  263. }
  264. SortArray<T, C> sorter;
  265. sorter.sort(data, len);
  266. }
  267. void sort() {
  268. sort_custom<Comparator<T>>();
  269. }
  270. void ordered_insert(T p_val) {
  271. U i;
  272. for (i = 0; i < count; i++) {
  273. if (p_val < data[i]) {
  274. break;
  275. }
  276. }
  277. insert(i, p_val);
  278. }
  279. operator Vector<T>() const {
  280. Vector<T> ret;
  281. ret.resize(count);
  282. T *w = ret.ptrw();
  283. if (w) {
  284. if constexpr (std::is_trivially_copyable_v<T>) {
  285. memcpy(w, data, sizeof(T) * count);
  286. } else {
  287. for (U i = 0; i < count; i++) {
  288. w[i] = data[i];
  289. }
  290. }
  291. }
  292. return ret;
  293. }
  294. Vector<uint8_t> to_byte_array() const { //useful to pass stuff to gpu or variant
  295. Vector<uint8_t> ret;
  296. ret.resize(count * sizeof(T));
  297. uint8_t *w = ret.ptrw();
  298. if (w) {
  299. memcpy(w, data, sizeof(T) * count);
  300. }
  301. return ret;
  302. }
  303. _FORCE_INLINE_ LocalVector() {}
  304. _FORCE_INLINE_ LocalVector(std::initializer_list<T> p_init) {
  305. reserve(p_init.size());
  306. for (const T &element : p_init) {
  307. push_back(element);
  308. }
  309. }
  310. _FORCE_INLINE_ LocalVector(const LocalVector &p_from) {
  311. resize(p_from.size());
  312. for (U i = 0; i < p_from.count; i++) {
  313. data[i] = p_from.data[i];
  314. }
  315. }
  316. _FORCE_INLINE_ LocalVector(LocalVector &&p_from) {
  317. data = p_from.data;
  318. count = p_from.count;
  319. capacity = p_from.capacity;
  320. p_from.data = nullptr;
  321. p_from.count = 0;
  322. p_from.capacity = 0;
  323. }
  324. inline void operator=(const LocalVector &p_from) {
  325. resize(p_from.size());
  326. for (U i = 0; i < p_from.count; i++) {
  327. data[i] = p_from.data[i];
  328. }
  329. }
  330. inline void operator=(const Vector<T> &p_from) {
  331. resize(p_from.size());
  332. for (U i = 0; i < count; i++) {
  333. data[i] = p_from[i];
  334. }
  335. }
  336. inline void operator=(LocalVector &&p_from) {
  337. if (unlikely(this == &p_from)) {
  338. return;
  339. }
  340. reset();
  341. data = p_from.data;
  342. count = p_from.count;
  343. capacity = p_from.capacity;
  344. p_from.data = nullptr;
  345. p_from.count = 0;
  346. p_from.capacity = 0;
  347. }
  348. inline void operator=(Vector<T> &&p_from) {
  349. resize(p_from.size());
  350. for (U i = 0; i < count; i++) {
  351. data[i] = std::move(p_from[i]);
  352. }
  353. }
  354. _FORCE_INLINE_ ~LocalVector() {
  355. if (data) {
  356. reset();
  357. }
  358. }
  359. };
  360. template <typename T, typename U = uint32_t>
  361. using TightLocalVector = LocalVector<T, U, false, true>;
  362. // Zero-constructing LocalVector initializes count, capacity and data to 0 and thus empty.
  363. template <typename T, typename U, bool force_trivial, bool tight>
  364. struct is_zero_constructible<LocalVector<T, U, force_trivial, tight>> : std::true_type {};