diff options
Diffstat (limited to 'core')
| -rw-r--r-- | core/SCsub | 2 | ||||
| -rw-r--r-- | core/map.h | 319 | ||||
| -rw-r--r-- | core/safe_refcount.cpp | 148 | ||||
| -rw-r--r-- | core/safe_refcount.h | 135 | ||||
| -rw-r--r-- | core/set.h | 130 | ||||
| -rw-r--r-- | core/variant.h | 1 | ||||
| -rw-r--r-- | core/variant_call.cpp | 70 | ||||
| -rw-r--r-- | core/variant_op.cpp | 52 |
8 files changed, 437 insertions, 420 deletions
diff --git a/core/SCsub b/core/SCsub index e78fe185a9..e9b21bc71b 100644 --- a/core/SCsub +++ b/core/SCsub @@ -83,7 +83,7 @@ thirdparty_minizip_sources = [ thirdparty_minizip_sources = [thirdparty_minizip_dir + file for file in thirdparty_minizip_sources] env.add_source_files(env.core_sources, thirdparty_minizip_sources) -if "builtin_zstd" in env and env["builtin_zstd"] == "yes": +if 'builtin_zstd' in env and env['builtin_zstd']: SConscript("#thirdparty/zstd/SCsub") diff --git a/core/map.h b/core/map.h index a37d898a9c..f01062ebed 100644 --- a/core/map.h +++ b/core/map.h @@ -31,6 +31,7 @@ #define MAP_H #include "set.h" + /** @author Juan Linietsky <reduzio@gmail.com> */ @@ -52,7 +53,6 @@ public: private: friend class Map<K, V, C, A>; - //Color color; int color; Element *right; Element *left; @@ -61,7 +61,6 @@ public: Element *_prev; K _key; V _value; - //_Data *data; public: @@ -147,7 +146,6 @@ private: #ifdef GLOBALNIL_DISABLED memdelete_allocator<Element, A>(_nil); #endif - //memdelete_allocator<Element,A>(_root); } }; @@ -158,6 +156,7 @@ private: ERR_FAIL_COND(p_node == _data._nil && p_color == RED); p_node->color = p_color; } + inline void _rotate_left(Element *p_node) { Element *r = p_node->right; @@ -206,8 +205,9 @@ private: while (node == node->parent->right) { node = node->parent; } + if (node->parent == _data._root) - return NULL; + return NULL; // No successor, as p_node = last node return node->parent; } } @@ -225,10 +225,11 @@ private: } else { while (node == node->parent->left) { - if (node->parent == _data._root) - return NULL; node = node->parent; } + + if (node == _data._root) + return NULL; // No predecessor, as p_node = first node return node->parent; } } @@ -239,16 +240,15 @@ private: C less; while (node != _data._nil) { - if (less(p_key, node->_key)) node = node->left; else if (less(node->_key, p_key)) node = node->right; else - break; // found + return node; // found } - return (node != _data._nil) ? node : NULL; + return NULL; } Element *_find_closest(const K &p_key) const { @@ -265,24 +265,68 @@ private: else if (less(node->_key, p_key)) node = node->right; else - break; // found + return node; // found } - if (node == _data._nil) { - if (prev == NULL) - return NULL; - if (less(p_key, prev->_key)) { + if (prev == NULL) + return NULL; // tree empty - prev = prev->_prev; - } + if (less(p_key, prev->_key)) + prev = prev->_prev; - return prev; + return prev; + } - } else - return node; + void _insert_rb_fix(Element *p_new_node) { + + Element *node = p_new_node; + Element *nparent = node->parent; + Element *ngrand_parent; + + while (nparent->color == RED) { + ngrand_parent = nparent->parent; + + if (nparent == ngrand_parent->left) { + if (ngrand_parent->right->color == RED) { + _set_color(nparent, BLACK); + _set_color(ngrand_parent->right, BLACK); + _set_color(ngrand_parent, RED); + node = ngrand_parent; + nparent = node->parent; + } else { + if (node == nparent->right) { + _rotate_left(nparent); + node = nparent; + nparent = node->parent; + } + _set_color(nparent, BLACK); + _set_color(ngrand_parent, RED); + _rotate_right(ngrand_parent); + } + } else { + if (ngrand_parent->left->color == RED) { + _set_color(nparent, BLACK); + _set_color(ngrand_parent->left, BLACK); + _set_color(ngrand_parent, RED); + node = ngrand_parent; + nparent = node->parent; + } else { + if (node == nparent->left) { + _rotate_right(nparent); + node = nparent; + nparent = node->parent; + } + _set_color(nparent, BLACK); + _set_color(ngrand_parent, RED); + _rotate_left(ngrand_parent); + } + } + } + + _set_color(_data._root->left, BLACK); } - Element *_insert(const K &p_key, bool &r_exists) { + Element *_insert(const K &p_key, const V &p_value) { Element *new_parent = _data._root; Element *node = _data._root->left; @@ -297,27 +341,25 @@ private: else if (less(node->_key, p_key)) node = node->right; else { - r_exists = true; - return node; + node->_value = p_value; + return node; // Return existing node with new value } } Element *new_node = memnew_allocator(Element, A); - new_node->parent = new_parent; new_node->right = _data._nil; new_node->left = _data._nil; new_node->_key = p_key; + new_node->_value = p_value; //new_node->data=_data; - if (new_parent == _data._root || less(p_key, new_parent->_key)) { + if (new_parent == _data._root || less(p_key, new_parent->_key)) { new_parent->left = new_node; } else { new_parent->right = new_node; } - r_exists = false; - new_node->_next = _successor(new_node); new_node->_prev = _predecessor(new_node); if (new_node->_next) @@ -325,168 +367,113 @@ private: if (new_node->_prev) new_node->_prev->_next = new_node; - return new_node; - } - - Element *_insert_rb(const K &p_key, const V &p_value) { - - bool exists = false; - Element *new_node = _insert(p_key, exists); - - if (new_node) { - new_node->_value = p_value; - } - if (exists) - return new_node; - - Element *node = new_node; _data.size_cache++; - - while (node->parent->color == RED) { - - if (node->parent == node->parent->parent->left) { - - Element *aux = node->parent->parent->right; - - if (aux->color == RED) { - _set_color(node->parent, BLACK); - _set_color(aux, BLACK); - _set_color(node->parent->parent, RED); - node = node->parent->parent; - } else { - if (node == node->parent->right) { - node = node->parent; - _rotate_left(node); - } - _set_color(node->parent, BLACK); - _set_color(node->parent->parent, RED); - _rotate_right(node->parent->parent); - } - } else { - Element *aux = node->parent->parent->left; - - if (aux->color == RED) { - _set_color(node->parent, BLACK); - _set_color(aux, BLACK); - _set_color(node->parent->parent, RED); - node = node->parent->parent; - } else { - if (node == node->parent->left) { - node = node->parent; - _rotate_right(node); - } - _set_color(node->parent, BLACK); - _set_color(node->parent->parent, RED); - _rotate_left(node->parent->parent); - } - } - } - _set_color(_data._root->left, BLACK); + _insert_rb_fix(new_node); return new_node; } - void _erase_fix(Element *p_node) { + void _erase_fix_rb(Element *p_node) { Element *root = _data._root->left; - Element *node = p_node; - - while ((node->color == BLACK) && (root != node)) { - if (node == node->parent->left) { - Element *aux = node->parent->right; - if (aux->color == RED) { - _set_color(aux, BLACK); - _set_color(node->parent, RED); - _rotate_left(node->parent); - aux = node->parent->right; - } - if ((aux->right->color == BLACK) && (aux->left->color == BLACK)) { - _set_color(aux, RED); - node = node->parent; + Element *node = _data._nil; + Element *sibling = p_node; + Element *parent = sibling->parent; + + while (node != root) { // If red node found, will exit at a break + if (sibling->color == RED) { + _set_color(sibling, BLACK); + _set_color(parent, RED); + if (sibling == parent->right) { + sibling = sibling->left; + _rotate_left(parent); } else { - if (aux->right->color == BLACK) { - _set_color(aux->left, BLACK); - _set_color(aux, RED); - _rotate_right(aux); - aux = node->parent->right; - } - _set_color(aux, node->parent->color); - _set_color(node->parent, BLACK); - _set_color(aux->right, BLACK); - _rotate_left(node->parent); - node = root; /* this is to exit while loop */ + sibling = sibling->right; + _rotate_right(parent); } - } else { /* the code below is has left and right switched from above */ - Element *aux = node->parent->left; - if (aux->color == RED) { - _set_color(aux, BLACK); - _set_color(node->parent, RED); - _rotate_right(node->parent); - aux = node->parent->left; + } + if ((sibling->left->color == BLACK) && (sibling->right->color == BLACK)) { + _set_color(sibling, RED); + if (parent->color == RED) { + _set_color(parent, BLACK); + break; + } else { // loop: haven't found any red nodes yet + node = parent; + parent = node->parent; + sibling = (node == parent->left) ? parent->right : parent->left; } - if ((aux->right->color == BLACK) && (aux->left->color == BLACK)) { - _set_color(aux, RED); - node = node->parent; + } else { + if (sibling == parent->right) { + if (sibling->right->color == BLACK) { + _set_color(sibling->left, BLACK); + _set_color(sibling, RED); + _rotate_right(sibling); + sibling = sibling->parent; + } + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->right, BLACK); + _rotate_left(parent); + break; } else { - if (aux->left->color == BLACK) { - _set_color(aux->right, BLACK); - _set_color(aux, RED); - _rotate_left(aux); - aux = node->parent->left; + if (sibling->left->color == BLACK) { + _set_color(sibling->right, BLACK); + _set_color(sibling, RED); + _rotate_left(sibling); + sibling = sibling->parent; } - _set_color(aux, node->parent->color); - _set_color(node->parent, BLACK); - _set_color(aux->left, BLACK); - _rotate_right(node->parent); - node = root; + + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->left, BLACK); + _rotate_right(parent); + break; } } } - _set_color(node, BLACK); - ERR_FAIL_COND(_data._nil->color != BLACK); } void _erase(Element *p_node) { - Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : _successor(p_node); - if (!rp) - rp = _data._nil; + Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : p_node->_next; Element *node = (rp->left == _data._nil) ? rp->right : rp->left; node->parent = rp->parent; - if (_data._root == node->parent) { - _data._root->left = node; + Element *sibling; + if (rp == rp->parent->left) { + rp->parent->left = node; + sibling = rp->parent->right; } else { - if (rp == rp->parent->left) { - rp->parent->left = node; - } else { - rp->parent->right = node; - } + rp->parent->right = node; + sibling = rp->parent->left; + } + + if (node->color == RED) { + node->parent = rp->parent; + _set_color(node, BLACK); + } else if (rp->color == BLACK && rp->parent != _data._root) { + _erase_fix_rb(sibling); } if (rp != p_node) { ERR_FAIL_COND(rp == _data._nil); - if (rp->color == BLACK) - _erase_fix(node); - rp->left = p_node->left; rp->right = p_node->right; rp->parent = p_node->parent; rp->color = p_node->color; - p_node->left->parent = rp; - p_node->right->parent = rp; + if (p_node->left != _data._nil) + p_node->left->parent = rp; + if (p_node->right != _data._nil) + p_node->right->parent = rp; if (p_node == p_node->parent->left) { p_node->parent->left = rp; } else { p_node->parent->right = rp; } - } else { - if (p_node->color == BLACK) - _erase_fix(node); } if (p_node->_next) @@ -501,11 +488,12 @@ private: void _calculate_depth(Element *p_element, int &max_d, int d) const { - if (p_element == _data._nil) { + if (p_element == _data._nil) return; - } + _calculate_depth(p_element->left, max_d, d + 1); _calculate_depth(p_element->right, max_d, d + 1); + if (d > max_d) max_d = d; } @@ -544,6 +532,7 @@ public: if (!_data._root) return NULL; + Element *res = _find(p_key); return res; } @@ -552,6 +541,7 @@ public: if (!_data._root) return NULL; + const Element *res = _find_closest(p_key); return res; } @@ -560,21 +550,28 @@ public: if (!_data._root) return NULL; + Element *res = _find_closest(p_key); return res; } + bool has(const K &p_key) const { + + return find(p_key) != NULL; + } + Element *insert(const K &p_key, const V &p_value) { if (!_data._root) _data._create_root(); - return _insert_rb(p_key, p_value); + return _insert(p_key, p_value); } void erase(Element *p_element) { - if (!_data._root) + if (!_data._root || !p_element) return; + _erase(p_element); if (_data.size_cache == 0 && _data._root) _data._free_root(); @@ -584,20 +581,17 @@ public: if (!_data._root) return false; + Element *e = find(p_key); if (!e) return false; + _erase(e); + if (_data.size_cache == 0 && _data._root) + _data._free_root(); return true; } - bool has(const K &p_key) const { - - if (!_data._root) - return false; - return find(p_key) != NULL; - } - const V &operator[](const K &p_key) const { CRASH_COND(!_data._root); @@ -605,6 +599,7 @@ public: CRASH_COND(!e); return e->_value; } + V &operator[](const K &p_key) { if (!_data._root) @@ -614,7 +609,6 @@ public: if (!e) e = insert(p_key, V()); - CRASH_COND(!e); return e->_value; } @@ -637,6 +631,7 @@ public: if (!_data._root) return NULL; + Element *e = _data._root->left; if (e == _data._nil) return NULL; @@ -649,10 +644,12 @@ public: inline bool empty() const { return _data.size_cache == 0; } inline int size() const { return _data.size_cache; } + int calculate_depth() const { // used for debug mostly if (!_data._root) return 0; + int max_d = 0; _calculate_depth(_data._root->left, max_d, 0); return max_d; @@ -662,10 +659,10 @@ public: if (!_data._root) return; + _cleanup_tree(_data._root->left); _data._root->left = _data._nil; _data.size_cache = 0; - _data._nil->parent = _data._nil; _data._free_root(); } diff --git a/core/safe_refcount.cpp b/core/safe_refcount.cpp index c330a983a7..c9acdb7970 100644 --- a/core/safe_refcount.cpp +++ b/core/safe_refcount.cpp @@ -27,122 +27,10 @@ /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ /*************************************************************************/ -#include "safe_refcount.h" - -// Atomic functions, these are used for multithread safe reference counters! - -#ifdef NO_THREADS - -/* Bogus implementation unaware of multiprocessing */ - -template <class T> -static _ALWAYS_INLINE_ T _atomic_conditional_increment_impl(register T *pw) { - - if (*pw == 0) - return 0; - - (*pw)++; - - return *pw; -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_decrement_impl(register T *pw) { - - (*pw)--; - - return *pw; -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_increment_impl(register T *pw) { - - (*pw)++; - - return *pw; -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_sub_impl(register T *pw, register T val) { - - (*pw) -= val; - - return *pw; -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_add_impl(register T *pw, register T val) { - - (*pw) += val; - - return *pw; -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_exchange_if_greater_impl(register T *pw, register T val) { - - if (val > *pw) - *pw = val; - - return *pw; -} -#elif defined(__GNUC__) - -/* Implementation for GCC & Clang */ - -// GCC guarantees atomic intrinsics for sizes of 1, 2, 4 and 8 bytes. -// Clang states it supports GCC atomic builtins. - -template <class T> -static _ALWAYS_INLINE_ T _atomic_conditional_increment_impl(register T *pw) { - - while (true) { - T tmp = static_cast<T const volatile &>(*pw); - if (tmp == 0) - return 0; // if zero, can't add to it anymore - if (__sync_val_compare_and_swap(pw, tmp, tmp + 1) == tmp) - return tmp + 1; - } -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_decrement_impl(register T *pw) { - - return __sync_sub_and_fetch(pw, 1); -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_increment_impl(register T *pw) { - - return __sync_add_and_fetch(pw, 1); -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_sub_impl(register T *pw, register T val) { - - return __sync_sub_and_fetch(pw, val); -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_add_impl(register T *pw, register T val) { - - return __sync_add_and_fetch(pw, val); -} - -template <class T> -static _ALWAYS_INLINE_ T _atomic_exchange_if_greater_impl(register T *pw, register T val) { - - while (true) { - T tmp = static_cast<T const volatile &>(*pw); - if (tmp >= val) - return tmp; // already greater, or equal - if (__sync_val_compare_and_swap(pw, tmp, val) == tmp) - return val; - } -} +#include "safe_refcount.h" -#elif defined(_MSC_VER) +#if defined(_MSC_VER) /* Implementation for MSVC-Windows */ @@ -169,73 +57,66 @@ static _ALWAYS_INLINE_ T _atomic_exchange_if_greater_impl(register T *pw, regist return m_val; \ } -static _ALWAYS_INLINE_ uint32_t _atomic_conditional_increment_impl(register uint32_t *pw) { +_ALWAYS_INLINE_ uint32_t _atomic_conditional_increment_impl(register uint32_t *pw) { ATOMIC_CONDITIONAL_INCREMENT_BODY(pw, LONG, InterlockedCompareExchange, uint32_t) } -static _ALWAYS_INLINE_ uint32_t _atomic_decrement_impl(register uint32_t *pw) { +_ALWAYS_INLINE_ uint32_t _atomic_decrement_impl(register uint32_t *pw) { return InterlockedDecrement((LONG volatile *)pw); } -static _ALWAYS_INLINE_ uint32_t _atomic_increment_impl(register uint32_t *pw) { +_ALWAYS_INLINE_ uint32_t _atomic_increment_impl(register uint32_t *pw) { return InterlockedIncrement((LONG volatile *)pw); } -static _ALWAYS_INLINE_ uint32_t _atomic_sub_impl(register uint32_t *pw, register uint32_t val) { +_ALWAYS_INLINE_ uint32_t _atomic_sub_impl(register uint32_t *pw, register uint32_t val) { return InterlockedExchangeAdd((LONG volatile *)pw, -(int32_t)val) - val; } -static _ALWAYS_INLINE_ uint32_t _atomic_add_impl(register uint32_t *pw, register uint32_t val) { +_ALWAYS_INLINE_ uint32_t _atomic_add_impl(register uint32_t *pw, register uint32_t val) { return InterlockedAdd((LONG volatile *)pw, val); } -static _ALWAYS_INLINE_ uint32_t _atomic_exchange_if_greater_impl(register uint32_t *pw, register uint32_t val) { +_ALWAYS_INLINE_ uint32_t _atomic_exchange_if_greater_impl(register uint32_t *pw, register uint32_t val) { ATOMIC_EXCHANGE_IF_GREATER_BODY(pw, val, LONG, InterlockedCompareExchange, uint32_t) } -static _ALWAYS_INLINE_ uint64_t _atomic_conditional_increment_impl(register uint64_t *pw) { +_ALWAYS_INLINE_ uint64_t _atomic_conditional_increment_impl(register uint64_t *pw) { ATOMIC_CONDITIONAL_INCREMENT_BODY(pw, LONGLONG, InterlockedCompareExchange64, uint64_t) } -static _ALWAYS_INLINE_ uint64_t _atomic_decrement_impl(register uint64_t *pw) { +_ALWAYS_INLINE_ uint64_t _atomic_decrement_impl(register uint64_t *pw) { return InterlockedDecrement64((LONGLONG volatile *)pw); } -static _ALWAYS_INLINE_ uint64_t _atomic_increment_impl(register uint64_t *pw) { +_ALWAYS_INLINE_ uint64_t _atomic_increment_impl(register uint64_t *pw) { return InterlockedIncrement64((LONGLONG volatile *)pw); } -static _ALWAYS_INLINE_ uint64_t _atomic_sub_impl(register uint64_t *pw, register uint64_t val) { +_ALWAYS_INLINE_ uint64_t _atomic_sub_impl(register uint64_t *pw, register uint64_t val) { return InterlockedExchangeAdd64((LONGLONG volatile *)pw, -(int64_t)val) - val; } -static _ALWAYS_INLINE_ uint64_t _atomic_add_impl(register uint64_t *pw, register uint64_t val) { +_ALWAYS_INLINE_ uint64_t _atomic_add_impl(register uint64_t *pw, register uint64_t val) { return InterlockedAdd64((LONGLONG volatile *)pw, val); } -static _ALWAYS_INLINE_ uint64_t _atomic_exchange_if_greater_impl(register uint64_t *pw, register uint64_t val) { +_ALWAYS_INLINE_ uint64_t _atomic_exchange_if_greater_impl(register uint64_t *pw, register uint64_t val) { ATOMIC_EXCHANGE_IF_GREATER_BODY(pw, val, LONGLONG, InterlockedCompareExchange64, uint64_t) } -#else - -//no threads supported? -#error Must provide atomic functions for this platform or compiler! - -#endif - // The actual advertised functions; they'll call the right implementation uint32_t atomic_conditional_increment(register uint32_t *counter) { @@ -285,3 +166,4 @@ uint64_t atomic_add(register uint64_t *pw, register uint64_t val) { uint64_t atomic_exchange_if_greater(register uint64_t *pw, register uint64_t val) { return _atomic_exchange_if_greater_impl(pw, val); } +#endif diff --git a/core/safe_refcount.h b/core/safe_refcount.h index 802d84cccc..39967d5ac4 100644 --- a/core/safe_refcount.h +++ b/core/safe_refcount.h @@ -36,20 +36,141 @@ #include "platform_config.h" #include "typedefs.h" -uint32_t atomic_conditional_increment(register uint32_t *counter); +// Atomic functions, these are used for multithread safe reference counters! + +#ifdef NO_THREADS + +/* Bogus implementation unaware of multiprocessing */ + +template <class T> +static _ALWAYS_INLINE_ T atomic_conditional_increment(register T *pw) { + + if (*pw == 0) + return 0; + + (*pw)++; + + return *pw; +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_decrement(register T *pw) { + + (*pw)--; + + return *pw; +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_increment(register T *pw) { + + (*pw)++; + + return *pw; +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_sub(register T *pw, register V val) { + + (*pw) -= val; + + return *pw; +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_add(register T *pw, register V val) { + + (*pw) += val; + + return *pw; +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_exchange_if_greater(register T *pw, register V val) { + + if (val > *pw) + *pw = val; + + return *pw; +} + +#elif defined(__GNUC__) + +/* Implementation for GCC & Clang */ + +// GCC guarantees atomic intrinsics for sizes of 1, 2, 4 and 8 bytes. +// Clang states it supports GCC atomic builtins. + +template <class T> +static _ALWAYS_INLINE_ T atomic_conditional_increment(register T *pw) { + + while (true) { + T tmp = static_cast<T const volatile &>(*pw); + if (tmp == 0) + return 0; // if zero, can't add to it anymore + if (__sync_val_compare_and_swap(pw, tmp, tmp + 1) == tmp) + return tmp + 1; + } +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_decrement(register T *pw) { + + return __sync_sub_and_fetch(pw, 1); +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_increment(register T *pw) { + + return __sync_add_and_fetch(pw, 1); +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_sub(register T *pw, register V val) { + + return __sync_sub_and_fetch(pw, val); +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_add(register T *pw, register V val) { + + return __sync_add_and_fetch(pw, val); +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_exchange_if_greater(register T *pw, register V val) { + + while (true) { + T tmp = static_cast<T const volatile &>(*pw); + if (tmp >= val) + return tmp; // already greater, or equal + if (__sync_val_compare_and_swap(pw, tmp, val) == tmp) + return val; + } +} + +#elif defined(_MSC_VER) +// For MSVC use a separate compilation unit to prevent windows.h from polluting +// the global namespace. +uint32_t atomic_conditional_increment(register uint32_t *pw); uint32_t atomic_decrement(register uint32_t *pw); uint32_t atomic_increment(register uint32_t *pw); uint32_t atomic_sub(register uint32_t *pw, register uint32_t val); uint32_t atomic_add(register uint32_t *pw, register uint32_t val); uint32_t atomic_exchange_if_greater(register uint32_t *pw, register uint32_t val); -uint64_t atomic_conditional_increment(register uint64_t *counter); +uint64_t atomic_conditional_increment(register uint64_t *pw); uint64_t atomic_decrement(register uint64_t *pw); uint64_t atomic_increment(register uint64_t *pw); uint64_t atomic_sub(register uint64_t *pw, register uint64_t val); uint64_t atomic_add(register uint64_t *pw, register uint64_t val); uint64_t atomic_exchange_if_greater(register uint64_t *pw, register uint64_t val); +#else +//no threads supported? +#error Must provide atomic functions for this platform or compiler! +#endif + struct SafeRefCount { uint32_t count; @@ -57,17 +178,17 @@ struct SafeRefCount { public: // destroy() is called when weak_count_ drops to zero. - bool ref() { //true on success + _ALWAYS_INLINE_ bool ref() { //true on success return atomic_conditional_increment(&count) != 0; } - uint32_t refval() { //true on success + _ALWAYS_INLINE_ uint32_t refval() { //true on success return atomic_conditional_increment(&count); } - bool unref() { // true if must be disposed of + _ALWAYS_INLINE_ bool unref() { // true if must be disposed of if (atomic_decrement(&count) == 0) { return true; @@ -76,12 +197,12 @@ public: return false; } - uint32_t get() const { // nothrow + _ALWAYS_INLINE_ uint32_t get() const { // nothrow return count; } - void init(uint32_t p_value = 1) { + _ALWAYS_INLINE_ void init(uint32_t p_value = 1) { count = p_value; } diff --git a/core/set.h b/core/set.h index d91dd9b3ea..0f48e07520 100644 --- a/core/set.h +++ b/core/set.h @@ -100,17 +100,15 @@ private: Element *_nil; int size_cache; - _Data() { + _FORCE_INLINE_ _Data() { #ifdef GLOBALNIL_DISABLED _nil = memnew_allocator(Element, A); _nil->parent = _nil->left = _nil->right = _nil; _nil->color = BLACK; #else - _nil = (Element *)&_GlobalNilClass::_nil; #endif _root = NULL; - size_cache = 0; } @@ -132,6 +130,7 @@ private: ~_Data() { _free_root(); + #ifdef GLOBALNIL_DISABLED memdelete_allocator<Element, A>(_nil); #endif @@ -196,7 +195,7 @@ private: } if (node->parent == _data._root) - return NULL; // No successor, as p_node is the last node. + return NULL; // No successor, as p_node = last node return node->parent; } } @@ -218,7 +217,7 @@ private: } if (node == _data._root) - return NULL; // No predecessor, as p_node is the first node. + return NULL; // No predecessor, as p_node = first node. return node->parent; } } @@ -266,65 +265,13 @@ private: return prev; } - Element *_insert(const T &p_value, bool &r_exists) { - - Element *new_parent = _data._root; - Element *node = _data._root->left; - C less; - - while (node != _data._nil) { - - new_parent = node; - - if (less(p_value, node->value)) - node = node->left; - else if (less(node->value, p_value)) - node = node->right; - else { - r_exists = true; - return node; - } - } - - r_exists = false; + void _insert_rb_fix(Element *p_new_node) { - Element *new_node = memnew_allocator(Element, A); - new_node->parent = new_parent; - new_node->right = _data._nil; - new_node->left = _data._nil; - new_node->value = p_value; - //new_node->data=_data; - - if (new_parent == _data._root || less(p_value, new_parent->value)) { - new_parent->left = new_node; - } else { - new_parent->right = new_node; - } - - new_node->_next = _successor(new_node); - new_node->_prev = _predecessor(new_node); - if (new_node->_next) - new_node->_next->_prev = new_node; - if (new_node->_prev) - new_node->_prev->_next = new_node; - - return new_node; - } - - Element *_insert_rb(const T &p_value) { - - bool exists = false; - Element *new_node = _insert(p_value, exists); - if (exists) - return new_node; - - _data.size_cache++; - Element *node = new_node; + Element *node = p_new_node; Element *nparent = node->parent; Element *ngrand_parent; while (nparent->color == RED) { - ngrand_parent = nparent->parent; if (nparent == ngrand_parent->left) { @@ -365,11 +312,53 @@ private: } _set_color(_data._root->left, BLACK); + } + + Element *_insert(const T &p_value) { + + Element *new_parent = _data._root; + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + + new_parent = node; + + if (less(p_value, node->value)) + node = node->left; + else if (less(node->value, p_value)) + node = node->right; + else { + return node; // Return existing node + } + } + Element *new_node = memnew_allocator(Element, A); + new_node->parent = new_parent; + new_node->right = _data._nil; + new_node->left = _data._nil; + new_node->value = p_value; + //new_node->data=_data; + + if (new_parent == _data._root || less(p_value, new_parent->value)) { + new_parent->left = new_node; + } else { + new_parent->right = new_node; + } + + new_node->_next = _successor(new_node); + new_node->_prev = _predecessor(new_node); + if (new_node->_next) + new_node->_next->_prev = new_node; + if (new_node->_prev) + new_node->_prev->_next = new_node; + + _data.size_cache++; + _insert_rb_fix(new_node); return new_node; } - void _erase_fix(Element *p_node) { + void _erase_fix_rb(Element *p_node) { Element *root = _data._root->left; Element *node = _data._nil; @@ -450,7 +439,7 @@ private: node->parent = rp->parent; _set_color(node, BLACK); } else if (rp->color == BLACK && rp->parent != _data._root) { - _erase_fix(sibling); + _erase_fix_rb(sibling); } if (rp != p_node) { @@ -485,11 +474,12 @@ private: void _calculate_depth(Element *p_element, int &max_d, int d) const { - if (p_element == _data._nil) { + if (p_element == _data._nil) return; - } + _calculate_depth(p_element->left, max_d, d + 1); _calculate_depth(p_element->right, max_d, d + 1); + if (d > max_d) max_d = d; } @@ -533,10 +523,13 @@ public: return res; } + Element *lower_bound(const T &p_value) const { + + return _lower_bound(p_value); + } + bool has(const T &p_value) const { - if (!_data._root) - return false; return find(p_value) != NULL; } @@ -544,7 +537,7 @@ public: if (!_data._root) _data._create_root(); - return _insert_rb(p_value); + return _insert(p_value); } void erase(Element *p_element) { @@ -602,11 +595,6 @@ public: return e; } - Element *lower_bound(const T &p_value) const { - - return _lower_bound(p_value); - } - inline int size() const { return _data.size_cache; } int calculate_depth() const { diff --git a/core/variant.h b/core/variant.h index 5ea540a63f..e0d0bf05c8 100644 --- a/core/variant.h +++ b/core/variant.h @@ -368,6 +368,7 @@ public: static Vector<Variant> get_method_default_arguments(Variant::Type p_type, const StringName &p_method); static Variant::Type get_method_return_type(Variant::Type p_type, const StringName &p_method, bool *r_has_return = NULL); static Vector<StringName> get_method_argument_names(Variant::Type p_type, const StringName &p_method); + static bool is_method_const(Variant::Type p_type, const StringName &p_method); void set_named(const StringName &p_index, const Variant &p_value, bool *r_valid = NULL); Variant get_named(const StringName &p_index, bool *r_valid = NULL) const; diff --git a/core/variant_call.cpp b/core/variant_call.cpp index 7205280938..d141621fbb 100644 --- a/core/variant_call.cpp +++ b/core/variant_call.cpp @@ -53,6 +53,7 @@ struct _VariantCall { Vector<StringName> arg_names; Variant::Type return_type; + bool _const; #ifdef DEBUG_ENABLED bool returns; #endif @@ -145,11 +146,12 @@ struct _VariantCall { #endif } - static void addfunc(Variant::Type p_type, Variant::Type p_return, const StringName &p_name, VariantFunc p_func, const Vector<Variant> &p_defaultarg, const Arg &p_argtype1 = Arg(), const Arg &p_argtype2 = Arg(), const Arg &p_argtype3 = Arg(), const Arg &p_argtype4 = Arg(), const Arg &p_argtype5 = Arg()) { + static void addfunc(bool p_const, Variant::Type p_type, Variant::Type p_return, const StringName &p_name, VariantFunc p_func, const Vector<Variant> &p_defaultarg, const Arg &p_argtype1 = Arg(), const Arg &p_argtype2 = Arg(), const Arg &p_argtype3 = Arg(), const Arg &p_argtype4 = Arg(), const Arg &p_argtype5 = Arg()) { FuncData funcdata; funcdata.func = p_func; funcdata.default_args = p_defaultarg; + funcdata._const = p_const; #ifdef DEBUG_ENABLED funcdata.return_type = p_return; funcdata.returns = p_return != Variant::NIL; @@ -1201,6 +1203,17 @@ Vector<Variant::Type> Variant::get_method_argument_types(Variant::Type p_type, c return E->get().arg_types; } +bool Variant::is_method_const(Variant::Type p_type, const StringName &p_method) { + + const _VariantCall::TypeFunc &fd = _VariantCall::type_funcs[p_type]; + + const Map<StringName, _VariantCall::FuncData>::Element *E = fd.functions.find(p_method); + if (!E) + return false; + + return E->get()._const; +} + Vector<StringName> Variant::get_method_argument_names(Variant::Type p_type, const StringName &p_method) { const _VariantCall::TypeFunc &fd = _VariantCall::type_funcs[p_type]; @@ -1248,6 +1261,10 @@ void Variant::get_method_list(List<MethodInfo> *p_list) const { MethodInfo mi; mi.name = E->key(); + if (fd._const) { + mi.flags |= METHOD_FLAG_CONST; + } + for (int i = 0; i < fd.arg_types.size(); i++) { PropertyInfo pi; @@ -1360,15 +1377,26 @@ void register_variant_methods() { _VariantCall::constant_data = memnew_arr(_VariantCall::ConstantData, Variant::VARIANT_MAX); #define ADDFUNC0(m_vtype, m_ret, m_class, m_method, m_defarg) \ - _VariantCall::addfunc(Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg); + _VariantCall::addfunc(true, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg); #define ADDFUNC1(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_defarg) \ - _VariantCall::addfunc(Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1))); + _VariantCall::addfunc(true, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1))); #define ADDFUNC2(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_arg2, m_argname2, m_defarg) \ - _VariantCall::addfunc(Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2))); + _VariantCall::addfunc(true, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2))); #define ADDFUNC3(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_arg2, m_argname2, m_arg3, m_argname3, m_defarg) \ - _VariantCall::addfunc(Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2)), _VariantCall::Arg(Variant::m_arg3, _scs_create(m_argname3))); + _VariantCall::addfunc(true, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2)), _VariantCall::Arg(Variant::m_arg3, _scs_create(m_argname3))); #define ADDFUNC4(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_arg2, m_argname2, m_arg3, m_argname3, m_arg4, m_argname4, m_defarg) \ - _VariantCall::addfunc(Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2)), _VariantCall::Arg(Variant::m_arg3, _scs_create(m_argname3)), _VariantCall::Arg(Variant::m_arg4, _scs_create(m_argname4))); + _VariantCall::addfunc(true, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2)), _VariantCall::Arg(Variant::m_arg3, _scs_create(m_argname3)), _VariantCall::Arg(Variant::m_arg4, _scs_create(m_argname4))); + +#define ADDFUNC0NC(m_vtype, m_ret, m_class, m_method, m_defarg) \ + _VariantCall::addfunc(false, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg); +#define ADDFUNC1NC(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_defarg) \ + _VariantCall::addfunc(false, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1))); +#define ADDFUNC2NC(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_arg2, m_argname2, m_defarg) \ + _VariantCall::addfunc(false, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2))); +#define ADDFUNC3NC(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_arg2, m_argname2, m_arg3, m_argname3, m_defarg) \ + _VariantCall::addfunc(false, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2)), _VariantCall::Arg(Variant::m_arg3, _scs_create(m_argname3))); +#define ADDFUNC4NC(m_vtype, m_ret, m_class, m_method, m_arg1, m_argname1, m_arg2, m_argname2, m_arg3, m_argname3, m_arg4, m_argname4, m_defarg) \ + _VariantCall::addfunc(false, Variant::m_vtype, Variant::m_ret, _scs_create(#m_method), VCALL(m_class, m_method), m_defarg, _VariantCall::Arg(Variant::m_arg1, _scs_create(m_argname1)), _VariantCall::Arg(Variant::m_arg2, _scs_create(m_argname2)), _VariantCall::Arg(Variant::m_arg3, _scs_create(m_argname3)), _VariantCall::Arg(Variant::m_arg4, _scs_create(m_argname4))); /* STRING */ ADDFUNC1(STRING, INT, String, casecmp_to, STRING, "to", varray()); @@ -1545,7 +1573,7 @@ void register_variant_methods() { ADDFUNC0(DICTIONARY, INT, Dictionary, size, varray()); ADDFUNC0(DICTIONARY, BOOL, Dictionary, empty, varray()); - ADDFUNC0(DICTIONARY, NIL, Dictionary, clear, varray()); + ADDFUNC0NC(DICTIONARY, NIL, Dictionary, clear, varray()); ADDFUNC1(DICTIONARY, BOOL, Dictionary, has, NIL, "key", varray()); ADDFUNC1(DICTIONARY, BOOL, Dictionary, has_all, ARRAY, "keys", varray()); ADDFUNC1(DICTIONARY, NIL, Dictionary, erase, NIL, "key", varray()); @@ -1555,15 +1583,15 @@ void register_variant_methods() { ADDFUNC0(ARRAY, INT, Array, size, varray()); ADDFUNC0(ARRAY, BOOL, Array, empty, varray()); - ADDFUNC0(ARRAY, NIL, Array, clear, varray()); + ADDFUNC0NC(ARRAY, NIL, Array, clear, varray()); ADDFUNC0(ARRAY, INT, Array, hash, varray()); - ADDFUNC1(ARRAY, NIL, Array, push_back, NIL, "value", varray()); - ADDFUNC1(ARRAY, NIL, Array, push_front, NIL, "value", varray()); - ADDFUNC1(ARRAY, NIL, Array, append, NIL, "value", varray()); - ADDFUNC1(ARRAY, NIL, Array, resize, INT, "size", varray()); - ADDFUNC2(ARRAY, NIL, Array, insert, INT, "position", NIL, "value", varray()); - ADDFUNC1(ARRAY, NIL, Array, remove, INT, "position", varray()); - ADDFUNC1(ARRAY, NIL, Array, erase, NIL, "value", varray()); + ADDFUNC1NC(ARRAY, NIL, Array, push_back, NIL, "value", varray()); + ADDFUNC1NC(ARRAY, NIL, Array, push_front, NIL, "value", varray()); + ADDFUNC1NC(ARRAY, NIL, Array, append, NIL, "value", varray()); + ADDFUNC1NC(ARRAY, NIL, Array, resize, INT, "size", varray()); + ADDFUNC2NC(ARRAY, NIL, Array, insert, INT, "position", NIL, "value", varray()); + ADDFUNC1NC(ARRAY, NIL, Array, remove, INT, "position", varray()); + ADDFUNC1NC(ARRAY, NIL, Array, erase, NIL, "value", varray()); ADDFUNC0(ARRAY, NIL, Array, front, varray()); ADDFUNC0(ARRAY, NIL, Array, back, varray()); ADDFUNC2(ARRAY, INT, Array, find, NIL, "what", INT, "from", varray(0)); @@ -1571,12 +1599,12 @@ void register_variant_methods() { ADDFUNC1(ARRAY, INT, Array, find_last, NIL, "value", varray()); ADDFUNC1(ARRAY, INT, Array, count, NIL, "value", varray()); ADDFUNC1(ARRAY, BOOL, Array, has, NIL, "value", varray()); - ADDFUNC0(ARRAY, NIL, Array, pop_back, varray()); - ADDFUNC0(ARRAY, NIL, Array, pop_front, varray()); - ADDFUNC0(ARRAY, NIL, Array, sort, varray()); - ADDFUNC2(ARRAY, NIL, Array, sort_custom, OBJECT, "obj", STRING, "func", varray()); - ADDFUNC0(ARRAY, NIL, Array, invert, varray()); - ADDFUNC0(ARRAY, ARRAY, Array, duplicate, varray()); + ADDFUNC0NC(ARRAY, NIL, Array, pop_back, varray()); + ADDFUNC0NC(ARRAY, NIL, Array, pop_front, varray()); + ADDFUNC0NC(ARRAY, NIL, Array, sort, varray()); + ADDFUNC2NC(ARRAY, NIL, Array, sort_custom, OBJECT, "obj", STRING, "func", varray()); + ADDFUNC0NC(ARRAY, NIL, Array, invert, varray()); + ADDFUNC0NC(ARRAY, ARRAY, Array, duplicate, varray()); ADDFUNC0(POOL_BYTE_ARRAY, INT, PoolByteArray, size, varray()); ADDFUNC2(POOL_BYTE_ARRAY, NIL, PoolByteArray, set, INT, "idx", INT, "byte", varray()); diff --git a/core/variant_op.cpp b/core/variant_op.cpp index 4065b6a844..03ec336291 100644 --- a/core/variant_op.cpp +++ b/core/variant_op.cpp @@ -100,32 +100,32 @@ } /* clang-format on */ -#define CASES(PREFIX) static void *switch_table_##PREFIX[25][27] = { \ - TYPES(PREFIX, OP_EQUAL), \ - TYPES(PREFIX, OP_NOT_EQUAL), \ - TYPES(PREFIX, OP_LESS), \ - TYPES(PREFIX, OP_LESS_EQUAL), \ - TYPES(PREFIX, OP_GREATER), \ - TYPES(PREFIX, OP_GREATER_EQUAL), \ - TYPES(PREFIX, OP_ADD), \ - TYPES(PREFIX, OP_SUBTRACT), \ - TYPES(PREFIX, OP_MULTIPLY), \ - TYPES(PREFIX, OP_DIVIDE), \ - TYPES(PREFIX, OP_NEGATE), \ - TYPES(PREFIX, OP_POSITIVE), \ - TYPES(PREFIX, OP_MODULE), \ - TYPES(PREFIX, OP_STRING_CONCAT), \ - TYPES(PREFIX, OP_SHIFT_LEFT), \ - TYPES(PREFIX, OP_SHIFT_RIGHT), \ - TYPES(PREFIX, OP_BIT_AND), \ - TYPES(PREFIX, OP_BIT_OR), \ - TYPES(PREFIX, OP_BIT_XOR), \ - TYPES(PREFIX, OP_BIT_NEGATE), \ - TYPES(PREFIX, OP_AND), \ - TYPES(PREFIX, OP_OR), \ - TYPES(PREFIX, OP_XOR), \ - TYPES(PREFIX, OP_NOT), \ - TYPES(PREFIX, OP_IN), \ +#define CASES(PREFIX) static const void *switch_table_##PREFIX[25][27] = { \ + TYPES(PREFIX, OP_EQUAL), \ + TYPES(PREFIX, OP_NOT_EQUAL), \ + TYPES(PREFIX, OP_LESS), \ + TYPES(PREFIX, OP_LESS_EQUAL), \ + TYPES(PREFIX, OP_GREATER), \ + TYPES(PREFIX, OP_GREATER_EQUAL), \ + TYPES(PREFIX, OP_ADD), \ + TYPES(PREFIX, OP_SUBTRACT), \ + TYPES(PREFIX, OP_MULTIPLY), \ + TYPES(PREFIX, OP_DIVIDE), \ + TYPES(PREFIX, OP_NEGATE), \ + TYPES(PREFIX, OP_POSITIVE), \ + TYPES(PREFIX, OP_MODULE), \ + TYPES(PREFIX, OP_STRING_CONCAT), \ + TYPES(PREFIX, OP_SHIFT_LEFT), \ + TYPES(PREFIX, OP_SHIFT_RIGHT), \ + TYPES(PREFIX, OP_BIT_AND), \ + TYPES(PREFIX, OP_BIT_OR), \ + TYPES(PREFIX, OP_BIT_XOR), \ + TYPES(PREFIX, OP_BIT_NEGATE), \ + TYPES(PREFIX, OP_AND), \ + TYPES(PREFIX, OP_OR), \ + TYPES(PREFIX, OP_XOR), \ + TYPES(PREFIX, OP_NOT), \ + TYPES(PREFIX, OP_IN), \ } #define SWITCH(PREFIX, op, val) goto *switch_table_##PREFIX[op][val]; |