cowdata.h 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392
  1. /*************************************************************************/
  2. /* cowdata.h */
  3. /*************************************************************************/
  4. /* This file is part of: */
  5. /* GODOT ENGINE */
  6. /* https://godotengine.org */
  7. /*************************************************************************/
  8. /* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */
  9. /* Copyright (c) 2014-2021 Godot Engine contributors (cf. AUTHORS.md). */
  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. #ifndef COWDATA_H_
  31. #define COWDATA_H_
  32. #include <string.h>
  33. #include <type_traits>
  34. #include "core/error_macros.h"
  35. #include "core/os/memory.h"
  36. #include "core/safe_refcount.h"
  37. template <class T>
  38. class Vector;
  39. class String;
  40. class CharString;
  41. template <class T, class V>
  42. class VMap;
  43. #if !defined(NO_THREADS)
  44. SAFE_NUMERIC_TYPE_PUN_GUARANTEES(uint32_t)
  45. #endif
  46. template <class T>
  47. class CowData {
  48. template <class TV>
  49. friend class Vector;
  50. friend class String;
  51. friend class CharString;
  52. template <class TV, class VV>
  53. friend class VMap;
  54. private:
  55. mutable T *_ptr;
  56. // internal helpers
  57. _FORCE_INLINE_ SafeNumeric<uint32_t> *_get_refcount() const {
  58. if (!_ptr)
  59. return NULL;
  60. return reinterpret_cast<SafeNumeric<uint32_t> *>(_ptr) - 2;
  61. }
  62. _FORCE_INLINE_ uint32_t *_get_size() const {
  63. if (!_ptr)
  64. return NULL;
  65. return reinterpret_cast<uint32_t *>(_ptr) - 1;
  66. }
  67. _FORCE_INLINE_ T *_get_data() const {
  68. if (!_ptr)
  69. return NULL;
  70. return reinterpret_cast<T *>(_ptr);
  71. }
  72. _FORCE_INLINE_ size_t _get_alloc_size(size_t p_elements) const {
  73. //return nearest_power_of_2_templated(p_elements*sizeof(T)+sizeof(SafeRefCount)+sizeof(int));
  74. return next_power_of_2(p_elements * sizeof(T));
  75. }
  76. _FORCE_INLINE_ bool _get_alloc_size_checked(size_t p_elements, size_t *out) const {
  77. #if defined(_add_overflow) && defined(_mul_overflow)
  78. size_t o;
  79. size_t p;
  80. if (_mul_overflow(p_elements, sizeof(T), &o)) {
  81. *out = 0;
  82. return false;
  83. }
  84. *out = next_power_of_2(o);
  85. if (_add_overflow(o, static_cast<size_t>(32), &p)) return false; //no longer allocated here
  86. return true;
  87. #else
  88. // Speed is more important than correctness here, do the operations unchecked
  89. // and hope the best
  90. *out = _get_alloc_size(p_elements);
  91. return true;
  92. #endif
  93. }
  94. void _unref(void *p_data);
  95. void _ref(const CowData *p_from);
  96. void _ref(const CowData &p_from);
  97. uint32_t _copy_on_write();
  98. public:
  99. void operator=(const CowData<T> &p_from) { _ref(p_from); }
  100. _FORCE_INLINE_ T *ptrw() {
  101. _copy_on_write();
  102. return (T *)_get_data();
  103. }
  104. _FORCE_INLINE_ const T *ptr() const {
  105. return _get_data();
  106. }
  107. _FORCE_INLINE_ int size() const {
  108. uint32_t *size = (uint32_t *)_get_size();
  109. if (size)
  110. return *size;
  111. else
  112. return 0;
  113. }
  114. _FORCE_INLINE_ void clear() { resize(0); }
  115. _FORCE_INLINE_ bool empty() const { return _ptr == 0; }
  116. _FORCE_INLINE_ void set(int p_index, const T &p_elem) {
  117. CRASH_BAD_INDEX(p_index, size());
  118. _copy_on_write();
  119. _get_data()[p_index] = p_elem;
  120. }
  121. _FORCE_INLINE_ T &get_m(int p_index) {
  122. CRASH_BAD_INDEX(p_index, size());
  123. _copy_on_write();
  124. return _get_data()[p_index];
  125. }
  126. _FORCE_INLINE_ const T &get(int p_index) const {
  127. CRASH_BAD_INDEX(p_index, size());
  128. return _get_data()[p_index];
  129. }
  130. Error resize(int p_size);
  131. _FORCE_INLINE_ void remove(int p_index) {
  132. ERR_FAIL_INDEX(p_index, size());
  133. T *p = ptrw();
  134. int len = size();
  135. for (int i = p_index; i < len - 1; i++) {
  136. p[i] = p[i + 1];
  137. };
  138. resize(len - 1);
  139. };
  140. Error insert(int p_pos, const T &p_val) {
  141. ERR_FAIL_INDEX_V(p_pos, size() + 1, ERR_INVALID_PARAMETER);
  142. resize(size() + 1);
  143. for (int i = (size() - 1); i > p_pos; i--)
  144. set(i, get(i - 1));
  145. set(p_pos, p_val);
  146. return OK;
  147. };
  148. int find(const T &p_val, int p_from = 0) const;
  149. _FORCE_INLINE_ CowData();
  150. _FORCE_INLINE_ ~CowData();
  151. _FORCE_INLINE_ CowData(CowData<T> &p_from) { _ref(p_from); };
  152. };
  153. template <class T>
  154. void CowData<T>::_unref(void *p_data) {
  155. if (!p_data)
  156. return;
  157. SafeNumeric<uint32_t> *refc = _get_refcount();
  158. if (refc->decrement() > 0)
  159. return; // still in use
  160. // clean up
  161. if (!std::is_trivially_destructible<T>::value) {
  162. uint32_t *count = _get_size();
  163. T *data = (T *)(count + 1);
  164. for (uint32_t i = 0; i < *count; ++i) {
  165. // call destructors
  166. data[i].~T();
  167. }
  168. }
  169. // free mem
  170. Memory::free_static((uint8_t *)p_data, true);
  171. }
  172. template <class T>
  173. uint32_t CowData<T>::_copy_on_write() {
  174. if (!_ptr)
  175. return 0;
  176. SafeNumeric<uint32_t> *refc = _get_refcount();
  177. uint32_t rc = refc->get();
  178. if (likely(rc > 1)) {
  179. /* in use by more than me */
  180. uint32_t current_size = *_get_size();
  181. uint32_t *mem_new = (uint32_t *)Memory::alloc_static(_get_alloc_size(current_size), true);
  182. new (mem_new - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(1); //refcount
  183. *(mem_new - 1) = current_size; //size
  184. T *_data = (T *)(mem_new);
  185. // initialize new elements
  186. if (std::is_trivially_copyable<T>::value) {
  187. memcpy(mem_new, _ptr, current_size * sizeof(T));
  188. } else {
  189. for (uint32_t i = 0; i < current_size; i++) {
  190. memnew_placement(&_data[i], T(_get_data()[i]));
  191. }
  192. }
  193. _unref(_ptr);
  194. _ptr = _data;
  195. rc = 1;
  196. }
  197. return rc;
  198. }
  199. template <class T>
  200. Error CowData<T>::resize(int p_size) {
  201. ERR_FAIL_COND_V(p_size < 0, ERR_INVALID_PARAMETER);
  202. int current_size = size();
  203. if (p_size == current_size)
  204. return OK;
  205. if (p_size == 0) {
  206. // wants to clean up
  207. _unref(_ptr);
  208. _ptr = NULL;
  209. return OK;
  210. }
  211. // possibly changing size, copy on write
  212. uint32_t rc = _copy_on_write();
  213. size_t current_alloc_size = _get_alloc_size(current_size);
  214. size_t alloc_size;
  215. ERR_FAIL_COND_V(!_get_alloc_size_checked(p_size, &alloc_size), ERR_OUT_OF_MEMORY);
  216. if (p_size > current_size) {
  217. if (alloc_size != current_alloc_size) {
  218. if (current_size == 0) {
  219. // alloc from scratch
  220. uint32_t *ptr = (uint32_t *)Memory::alloc_static(alloc_size, true);
  221. ERR_FAIL_COND_V(!ptr, ERR_OUT_OF_MEMORY);
  222. *(ptr - 1) = 0; //size, currently none
  223. new (ptr - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(1); //refcount
  224. _ptr = (T *)ptr;
  225. } else {
  226. uint32_t *_ptrnew = (uint32_t *)Memory::realloc_static(_ptr, alloc_size, true);
  227. ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY);
  228. new (_ptrnew - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(rc); //refcount
  229. _ptr = (T *)(_ptrnew);
  230. }
  231. }
  232. // construct the newly created elements
  233. if (!std::is_trivially_constructible<T>::value) {
  234. T *elems = _get_data();
  235. for (int i = *_get_size(); i < p_size; i++) {
  236. memnew_placement(&elems[i], T);
  237. }
  238. }
  239. *_get_size() = p_size;
  240. } else if (p_size < current_size) {
  241. if (!std::is_trivially_destructible<T>::value) {
  242. // deinitialize no longer needed elements
  243. for (uint32_t i = p_size; i < *_get_size(); i++) {
  244. T *t = &_get_data()[i];
  245. t->~T();
  246. }
  247. }
  248. if (alloc_size != current_alloc_size) {
  249. uint32_t *_ptrnew = (uint32_t *)Memory::realloc_static(_ptr, alloc_size, true);
  250. ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY);
  251. new (_ptrnew - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(rc); //refcount
  252. _ptr = (T *)(_ptrnew);
  253. }
  254. *_get_size() = p_size;
  255. }
  256. return OK;
  257. }
  258. template <class T>
  259. int CowData<T>::find(const T &p_val, int p_from) const {
  260. int ret = -1;
  261. if (p_from < 0 || size() == 0) {
  262. return ret;
  263. }
  264. for (int i = p_from; i < size(); i++) {
  265. if (get(i) == p_val) {
  266. ret = i;
  267. break;
  268. }
  269. }
  270. return ret;
  271. }
  272. template <class T>
  273. void CowData<T>::_ref(const CowData *p_from) {
  274. _ref(*p_from);
  275. }
  276. template <class T>
  277. void CowData<T>::_ref(const CowData &p_from) {
  278. if (_ptr == p_from._ptr)
  279. return; // self assign, do nothing.
  280. _unref(_ptr);
  281. _ptr = NULL;
  282. if (!p_from._ptr)
  283. return; //nothing to do
  284. if (p_from._get_refcount()->conditional_increment() > 0) { // could reference
  285. _ptr = p_from._ptr;
  286. }
  287. }
  288. template <class T>
  289. CowData<T>::CowData() {
  290. _ptr = NULL;
  291. }
  292. template <class T>
  293. CowData<T>::~CowData() {
  294. _unref(_ptr);
  295. }
  296. #endif /* COW_H_ */