local_vector.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417
  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. if (unlikely(p_size > capacity)) {
  57. capacity = tight ? p_size : nearest_power_of_2_templated(p_size);
  58. data = (T *)memrealloc(data, capacity * sizeof(T));
  59. CRASH_COND_MSG(!data, "Out of memory");
  60. }
  61. if constexpr (p_init) {
  62. memnew_arr_placement(data + count, p_size - count);
  63. } else {
  64. static_assert(std::is_trivially_destructible_v<T>, "T must be trivially destructible to resize uninitialized");
  65. }
  66. count = p_size;
  67. }
  68. }
  69. public:
  70. _FORCE_INLINE_ T *ptr() { return data; }
  71. _FORCE_INLINE_ const T *ptr() const { return data; }
  72. _FORCE_INLINE_ U size() const { return count; }
  73. _FORCE_INLINE_ Span<T> span() const { return Span(data, count); }
  74. _FORCE_INLINE_ operator Span<T>() const { return span(); }
  75. // Must take a copy instead of a reference (see GH-31736).
  76. _FORCE_INLINE_ void push_back(T p_elem) {
  77. if (unlikely(count == capacity)) {
  78. reserve(count + 1);
  79. }
  80. memnew_placement(&data[count++], T(std::move(p_elem)));
  81. }
  82. void remove_at(U p_index) {
  83. ERR_FAIL_UNSIGNED_INDEX(p_index, count);
  84. count--;
  85. for (U i = p_index; i < count; i++) {
  86. data[i] = std::move(data[i + 1]);
  87. }
  88. data[count].~T();
  89. }
  90. /// Removes the item copying the last value into the position of the one to
  91. /// remove. It's generally faster than `remove_at`.
  92. void remove_at_unordered(U p_index) {
  93. ERR_FAIL_INDEX(p_index, count);
  94. count--;
  95. if (count > p_index) {
  96. data[p_index] = std::move(data[count]);
  97. }
  98. data[count].~T();
  99. }
  100. _FORCE_INLINE_ bool erase(const T &p_val) {
  101. int64_t idx = find(p_val);
  102. if (idx >= 0) {
  103. remove_at(idx);
  104. return true;
  105. }
  106. return false;
  107. }
  108. bool erase_unordered(const T &p_val) {
  109. int64_t idx = find(p_val);
  110. if (idx >= 0) {
  111. remove_at_unordered(idx);
  112. return true;
  113. }
  114. return false;
  115. }
  116. U erase_multiple_unordered(const T &p_val) {
  117. U from = 0;
  118. U occurrences = 0;
  119. while (true) {
  120. int64_t idx = find(p_val, from);
  121. if (idx == -1) {
  122. break;
  123. }
  124. remove_at_unordered(idx);
  125. from = idx;
  126. occurrences++;
  127. }
  128. return occurrences;
  129. }
  130. void reverse() {
  131. for (U i = 0; i < count / 2; i++) {
  132. SWAP(data[i], data[count - i - 1]);
  133. }
  134. }
  135. #ifndef DISABLE_DEPRECATED
  136. [[deprecated("Use reverse() instead")]] void invert() { reverse(); }
  137. #endif
  138. _FORCE_INLINE_ void clear() { resize(0); }
  139. _FORCE_INLINE_ void reset() {
  140. clear();
  141. if (data) {
  142. memfree(data);
  143. data = nullptr;
  144. capacity = 0;
  145. }
  146. }
  147. _FORCE_INLINE_ bool is_empty() const { return count == 0; }
  148. _FORCE_INLINE_ U get_capacity() const { return capacity; }
  149. void reserve(U p_size) {
  150. ERR_FAIL_COND_MSG(p_size < size(), "reserve() called with a capacity smaller than the current size. This is likely a mistake.");
  151. if (p_size > capacity) {
  152. if (tight) {
  153. capacity = p_size;
  154. } else {
  155. capacity = MAX((U)2, capacity + ((1 + capacity) >> 1));
  156. if (p_size > capacity) {
  157. capacity = p_size;
  158. }
  159. }
  160. data = (T *)memrealloc(data, capacity * sizeof(T));
  161. CRASH_COND_MSG(!data, "Out of memory");
  162. }
  163. }
  164. /// Resize the vector.
  165. /// Elements are initialized (or not) depending on what the default C++ behavior for T is.
  166. /// Note: If force_trivial is set, this will behave like resize_uninitialized instead.
  167. void resize(U p_size) {
  168. // Don't init when trivially constructible.
  169. _resize<!std::is_trivially_constructible_v<T>>(p_size);
  170. }
  171. /// Resize and set all values to 0 / false / nullptr.
  172. _FORCE_INLINE_ void resize_initialized(U p_size) { _resize<true>(p_size); }
  173. /// Resize and set all values to 0 / false / nullptr.
  174. /// This is only available for trivially destructible types (otherwise, trivial resize might be UB).
  175. _FORCE_INLINE_ void resize_uninitialized(U p_size) { _resize<false>(p_size); }
  176. _FORCE_INLINE_ const T &operator[](U p_index) const {
  177. CRASH_BAD_UNSIGNED_INDEX(p_index, count);
  178. return data[p_index];
  179. }
  180. _FORCE_INLINE_ T &operator[](U p_index) {
  181. CRASH_BAD_UNSIGNED_INDEX(p_index, count);
  182. return data[p_index];
  183. }
  184. struct Iterator {
  185. _FORCE_INLINE_ T &operator*() const {
  186. return *elem_ptr;
  187. }
  188. _FORCE_INLINE_ T *operator->() const { return elem_ptr; }
  189. _FORCE_INLINE_ Iterator &operator++() {
  190. elem_ptr++;
  191. return *this;
  192. }
  193. _FORCE_INLINE_ Iterator &operator--() {
  194. elem_ptr--;
  195. return *this;
  196. }
  197. _FORCE_INLINE_ bool operator==(const Iterator &b) const { return elem_ptr == b.elem_ptr; }
  198. _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return elem_ptr != b.elem_ptr; }
  199. Iterator(T *p_ptr) { elem_ptr = p_ptr; }
  200. Iterator() {}
  201. Iterator(const Iterator &p_it) { elem_ptr = p_it.elem_ptr; }
  202. private:
  203. T *elem_ptr = nullptr;
  204. };
  205. struct ConstIterator {
  206. _FORCE_INLINE_ const T &operator*() const {
  207. return *elem_ptr;
  208. }
  209. _FORCE_INLINE_ const T *operator->() const { return elem_ptr; }
  210. _FORCE_INLINE_ ConstIterator &operator++() {
  211. elem_ptr++;
  212. return *this;
  213. }
  214. _FORCE_INLINE_ ConstIterator &operator--() {
  215. elem_ptr--;
  216. return *this;
  217. }
  218. _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return elem_ptr == b.elem_ptr; }
  219. _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return elem_ptr != b.elem_ptr; }
  220. ConstIterator(const T *p_ptr) { elem_ptr = p_ptr; }
  221. ConstIterator() {}
  222. ConstIterator(const ConstIterator &p_it) { elem_ptr = p_it.elem_ptr; }
  223. private:
  224. const T *elem_ptr = nullptr;
  225. };
  226. _FORCE_INLINE_ Iterator begin() {
  227. return Iterator(data);
  228. }
  229. _FORCE_INLINE_ Iterator end() {
  230. return Iterator(data + size());
  231. }
  232. _FORCE_INLINE_ ConstIterator begin() const {
  233. return ConstIterator(ptr());
  234. }
  235. _FORCE_INLINE_ ConstIterator end() const {
  236. return ConstIterator(ptr() + size());
  237. }
  238. void insert(U p_pos, T p_val) {
  239. ERR_FAIL_UNSIGNED_INDEX(p_pos, count + 1);
  240. if (p_pos == count) {
  241. push_back(std::move(p_val));
  242. } else {
  243. resize(count + 1);
  244. for (U i = count - 1; i > p_pos; i--) {
  245. data[i] = std::move(data[i - 1]);
  246. }
  247. data[p_pos] = std::move(p_val);
  248. }
  249. }
  250. int64_t find(const T &p_val, int64_t p_from = 0) const {
  251. if (p_from < 0) {
  252. p_from = size() + p_from;
  253. }
  254. if (p_from < 0 || p_from >= size()) {
  255. return -1;
  256. }
  257. return span().find(p_val, p_from);
  258. }
  259. bool has(const T &p_val) const {
  260. return find(p_val) != -1;
  261. }
  262. template <typename C>
  263. void sort_custom() {
  264. U len = count;
  265. if (len == 0) {
  266. return;
  267. }
  268. SortArray<T, C> sorter;
  269. sorter.sort(data, len);
  270. }
  271. void sort() {
  272. sort_custom<Comparator<T>>();
  273. }
  274. void ordered_insert(T p_val) {
  275. U i;
  276. for (i = 0; i < count; i++) {
  277. if (p_val < data[i]) {
  278. break;
  279. }
  280. }
  281. insert(i, p_val);
  282. }
  283. operator Vector<T>() const {
  284. Vector<T> ret;
  285. ret.resize(count);
  286. T *w = ret.ptrw();
  287. if (w) {
  288. if constexpr (std::is_trivially_copyable_v<T>) {
  289. memcpy(w, data, sizeof(T) * count);
  290. } else {
  291. for (U i = 0; i < count; i++) {
  292. w[i] = data[i];
  293. }
  294. }
  295. }
  296. return ret;
  297. }
  298. Vector<uint8_t> to_byte_array() const { //useful to pass stuff to gpu or variant
  299. Vector<uint8_t> ret;
  300. ret.resize(count * sizeof(T));
  301. uint8_t *w = ret.ptrw();
  302. if (w) {
  303. memcpy(w, data, sizeof(T) * count);
  304. }
  305. return ret;
  306. }
  307. _FORCE_INLINE_ LocalVector() {}
  308. _FORCE_INLINE_ LocalVector(std::initializer_list<T> p_init) {
  309. reserve(p_init.size());
  310. for (const T &element : p_init) {
  311. push_back(element);
  312. }
  313. }
  314. _FORCE_INLINE_ LocalVector(const LocalVector &p_from) {
  315. resize(p_from.size());
  316. for (U i = 0; i < p_from.count; i++) {
  317. data[i] = p_from.data[i];
  318. }
  319. }
  320. _FORCE_INLINE_ LocalVector(LocalVector &&p_from) {
  321. data = p_from.data;
  322. count = p_from.count;
  323. capacity = p_from.capacity;
  324. p_from.data = nullptr;
  325. p_from.count = 0;
  326. p_from.capacity = 0;
  327. }
  328. inline void operator=(const LocalVector &p_from) {
  329. resize(p_from.size());
  330. for (U i = 0; i < p_from.count; i++) {
  331. data[i] = p_from.data[i];
  332. }
  333. }
  334. inline void operator=(const Vector<T> &p_from) {
  335. resize(p_from.size());
  336. for (U i = 0; i < count; i++) {
  337. data[i] = p_from[i];
  338. }
  339. }
  340. inline void operator=(LocalVector &&p_from) {
  341. if (unlikely(this == &p_from)) {
  342. return;
  343. }
  344. reset();
  345. data = p_from.data;
  346. count = p_from.count;
  347. capacity = p_from.capacity;
  348. p_from.data = nullptr;
  349. p_from.count = 0;
  350. p_from.capacity = 0;
  351. }
  352. inline void operator=(Vector<T> &&p_from) {
  353. resize(p_from.size());
  354. for (U i = 0; i < count; i++) {
  355. data[i] = std::move(p_from[i]);
  356. }
  357. }
  358. _FORCE_INLINE_ ~LocalVector() {
  359. if (data) {
  360. reset();
  361. }
  362. }
  363. };
  364. template <typename T, typename U = uint32_t>
  365. using TightLocalVector = LocalVector<T, U, false, true>;
  366. // Zero-constructing LocalVector initializes count, capacity and data to 0 and thus empty.
  367. template <typename T, typename U, bool force_trivial, bool tight>
  368. struct is_zero_constructible<LocalVector<T, U, force_trivial, tight>> : std::true_type {};