diff options
Diffstat (limited to 'core/templates')
27 files changed, 7117 insertions, 0 deletions
diff --git a/core/templates/SCsub b/core/templates/SCsub new file mode 100644 index 0000000000..8c4c843a33 --- /dev/null +++ b/core/templates/SCsub @@ -0,0 +1,7 @@ +#!/usr/bin/env python + +Import("env") + +env_templates = env.Clone() + +env_templates.add_source_files(env.core_sources, "*.cpp") diff --git a/core/templates/command_queue_mt.cpp b/core/templates/command_queue_mt.cpp new file mode 100644 index 0000000000..a94853a21c --- /dev/null +++ b/core/templates/command_queue_mt.cpp @@ -0,0 +1,112 @@ +/*************************************************************************/ +/* command_queue_mt.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#include "command_queue_mt.h" + +#include "core/config/project_settings.h" +#include "core/os/os.h" + +void CommandQueueMT::lock() { + mutex.lock(); +} + +void CommandQueueMT::unlock() { + mutex.unlock(); +} + +void CommandQueueMT::wait_for_flush() { + // wait one millisecond for a flush to happen + OS::get_singleton()->delay_usec(1000); +} + +CommandQueueMT::SyncSemaphore *CommandQueueMT::_alloc_sync_sem() { + int idx = -1; + + while (true) { + lock(); + for (int i = 0; i < SYNC_SEMAPHORES; i++) { + if (!sync_sems[i].in_use) { + sync_sems[i].in_use = true; + idx = i; + break; + } + } + unlock(); + + if (idx == -1) { + wait_for_flush(); + } else { + break; + } + } + + return &sync_sems[idx]; +} + +bool CommandQueueMT::dealloc_one() { +tryagain: + if (dealloc_ptr == (write_ptr_and_epoch >> 1)) { + // The queue is empty + return false; + } + + uint32_t size = *(uint32_t *)&command_mem[dealloc_ptr]; + + if (size == 0) { + // End of command buffer wrap down + dealloc_ptr = 0; + goto tryagain; + } + + if (size & 1) { + // Still used, nothing can be deallocated + return false; + } + + dealloc_ptr += (size >> 1) + 8; + return true; +} + +CommandQueueMT::CommandQueueMT(bool p_sync) { + command_mem_size = GLOBAL_DEF_RST("memory/limits/command_queue/multithreading_queue_size_kb", DEFAULT_COMMAND_MEM_SIZE_KB); + ProjectSettings::get_singleton()->set_custom_property_info("memory/limits/command_queue/multithreading_queue_size_kb", PropertyInfo(Variant::INT, "memory/limits/command_queue/multithreading_queue_size_kb", PROPERTY_HINT_RANGE, "1,4096,1,or_greater")); + command_mem_size *= 1024; + command_mem = (uint8_t *)memalloc(command_mem_size); + if (p_sync) { + sync = memnew(Semaphore); + } +} + +CommandQueueMT::~CommandQueueMT() { + if (sync) { + memdelete(sync); + } + memfree(command_mem); +} diff --git a/core/templates/command_queue_mt.h b/core/templates/command_queue_mt.h new file mode 100644 index 0000000000..ac38d330de --- /dev/null +++ b/core/templates/command_queue_mt.h @@ -0,0 +1,529 @@ +/*************************************************************************/ +/* command_queue_mt.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef COMMAND_QUEUE_MT_H +#define COMMAND_QUEUE_MT_H + +#include "core/os/memory.h" +#include "core/os/mutex.h" +#include "core/os/semaphore.h" +#include "core/templates/simple_type.h" +#include "core/typedefs.h" + +#define COMMA(N) _COMMA_##N +#define _COMMA_0 +#define _COMMA_1 , +#define _COMMA_2 , +#define _COMMA_3 , +#define _COMMA_4 , +#define _COMMA_5 , +#define _COMMA_6 , +#define _COMMA_7 , +#define _COMMA_8 , +#define _COMMA_9 , +#define _COMMA_10 , +#define _COMMA_11 , +#define _COMMA_12 , +#define _COMMA_13 , +#define _COMMA_14 , +#define _COMMA_15 , + +// 1-based comma separated list of ITEMs +#define COMMA_SEP_LIST(ITEM, LENGTH) _COMMA_SEP_LIST_##LENGTH(ITEM) +#define _COMMA_SEP_LIST_15(ITEM) \ + _COMMA_SEP_LIST_14(ITEM) \ + , ITEM(15) +#define _COMMA_SEP_LIST_14(ITEM) \ + _COMMA_SEP_LIST_13(ITEM) \ + , ITEM(14) +#define _COMMA_SEP_LIST_13(ITEM) \ + _COMMA_SEP_LIST_12(ITEM) \ + , ITEM(13) +#define _COMMA_SEP_LIST_12(ITEM) \ + _COMMA_SEP_LIST_11(ITEM) \ + , ITEM(12) +#define _COMMA_SEP_LIST_11(ITEM) \ + _COMMA_SEP_LIST_10(ITEM) \ + , ITEM(11) +#define _COMMA_SEP_LIST_10(ITEM) \ + _COMMA_SEP_LIST_9(ITEM) \ + , ITEM(10) +#define _COMMA_SEP_LIST_9(ITEM) \ + _COMMA_SEP_LIST_8(ITEM) \ + , ITEM(9) +#define _COMMA_SEP_LIST_8(ITEM) \ + _COMMA_SEP_LIST_7(ITEM) \ + , ITEM(8) +#define _COMMA_SEP_LIST_7(ITEM) \ + _COMMA_SEP_LIST_6(ITEM) \ + , ITEM(7) +#define _COMMA_SEP_LIST_6(ITEM) \ + _COMMA_SEP_LIST_5(ITEM) \ + , ITEM(6) +#define _COMMA_SEP_LIST_5(ITEM) \ + _COMMA_SEP_LIST_4(ITEM) \ + , ITEM(5) +#define _COMMA_SEP_LIST_4(ITEM) \ + _COMMA_SEP_LIST_3(ITEM) \ + , ITEM(4) +#define _COMMA_SEP_LIST_3(ITEM) \ + _COMMA_SEP_LIST_2(ITEM) \ + , ITEM(3) +#define _COMMA_SEP_LIST_2(ITEM) \ + _COMMA_SEP_LIST_1(ITEM) \ + , ITEM(2) +#define _COMMA_SEP_LIST_1(ITEM) \ + _COMMA_SEP_LIST_0(ITEM) \ + ITEM(1) +#define _COMMA_SEP_LIST_0(ITEM) + +// 1-based semicolon separated list of ITEMs +#define SEMIC_SEP_LIST(ITEM, LENGTH) _SEMIC_SEP_LIST_##LENGTH(ITEM) +#define _SEMIC_SEP_LIST_15(ITEM) \ + _SEMIC_SEP_LIST_14(ITEM); \ + ITEM(15) +#define _SEMIC_SEP_LIST_14(ITEM) \ + _SEMIC_SEP_LIST_13(ITEM); \ + ITEM(14) +#define _SEMIC_SEP_LIST_13(ITEM) \ + _SEMIC_SEP_LIST_12(ITEM); \ + ITEM(13) +#define _SEMIC_SEP_LIST_12(ITEM) \ + _SEMIC_SEP_LIST_11(ITEM); \ + ITEM(12) +#define _SEMIC_SEP_LIST_11(ITEM) \ + _SEMIC_SEP_LIST_10(ITEM); \ + ITEM(11) +#define _SEMIC_SEP_LIST_10(ITEM) \ + _SEMIC_SEP_LIST_9(ITEM); \ + ITEM(10) +#define _SEMIC_SEP_LIST_9(ITEM) \ + _SEMIC_SEP_LIST_8(ITEM); \ + ITEM(9) +#define _SEMIC_SEP_LIST_8(ITEM) \ + _SEMIC_SEP_LIST_7(ITEM); \ + ITEM(8) +#define _SEMIC_SEP_LIST_7(ITEM) \ + _SEMIC_SEP_LIST_6(ITEM); \ + ITEM(7) +#define _SEMIC_SEP_LIST_6(ITEM) \ + _SEMIC_SEP_LIST_5(ITEM); \ + ITEM(6) +#define _SEMIC_SEP_LIST_5(ITEM) \ + _SEMIC_SEP_LIST_4(ITEM); \ + ITEM(5) +#define _SEMIC_SEP_LIST_4(ITEM) \ + _SEMIC_SEP_LIST_3(ITEM); \ + ITEM(4) +#define _SEMIC_SEP_LIST_3(ITEM) \ + _SEMIC_SEP_LIST_2(ITEM); \ + ITEM(3) +#define _SEMIC_SEP_LIST_2(ITEM) \ + _SEMIC_SEP_LIST_1(ITEM); \ + ITEM(2) +#define _SEMIC_SEP_LIST_1(ITEM) \ + _SEMIC_SEP_LIST_0(ITEM) \ + ITEM(1) +#define _SEMIC_SEP_LIST_0(ITEM) + +// 1-based space separated list of ITEMs +#define SPACE_SEP_LIST(ITEM, LENGTH) _SPACE_SEP_LIST_##LENGTH(ITEM) +#define _SPACE_SEP_LIST_15(ITEM) \ + _SPACE_SEP_LIST_14(ITEM) \ + ITEM(15) +#define _SPACE_SEP_LIST_14(ITEM) \ + _SPACE_SEP_LIST_13(ITEM) \ + ITEM(14) +#define _SPACE_SEP_LIST_13(ITEM) \ + _SPACE_SEP_LIST_12(ITEM) \ + ITEM(13) +#define _SPACE_SEP_LIST_12(ITEM) \ + _SPACE_SEP_LIST_11(ITEM) \ + ITEM(12) +#define _SPACE_SEP_LIST_11(ITEM) \ + _SPACE_SEP_LIST_10(ITEM) \ + ITEM(11) +#define _SPACE_SEP_LIST_10(ITEM) \ + _SPACE_SEP_LIST_9(ITEM) \ + ITEM(10) +#define _SPACE_SEP_LIST_9(ITEM) \ + _SPACE_SEP_LIST_8(ITEM) \ + ITEM(9) +#define _SPACE_SEP_LIST_8(ITEM) \ + _SPACE_SEP_LIST_7(ITEM) \ + ITEM(8) +#define _SPACE_SEP_LIST_7(ITEM) \ + _SPACE_SEP_LIST_6(ITEM) \ + ITEM(7) +#define _SPACE_SEP_LIST_6(ITEM) \ + _SPACE_SEP_LIST_5(ITEM) \ + ITEM(6) +#define _SPACE_SEP_LIST_5(ITEM) \ + _SPACE_SEP_LIST_4(ITEM) \ + ITEM(5) +#define _SPACE_SEP_LIST_4(ITEM) \ + _SPACE_SEP_LIST_3(ITEM) \ + ITEM(4) +#define _SPACE_SEP_LIST_3(ITEM) \ + _SPACE_SEP_LIST_2(ITEM) \ + ITEM(3) +#define _SPACE_SEP_LIST_2(ITEM) \ + _SPACE_SEP_LIST_1(ITEM) \ + ITEM(2) +#define _SPACE_SEP_LIST_1(ITEM) \ + _SPACE_SEP_LIST_0(ITEM) \ + ITEM(1) +#define _SPACE_SEP_LIST_0(ITEM) + +#define ARG(N) p##N +#define PARAM(N) P##N p##N +#define TYPE_PARAM(N) class P##N +#define PARAM_DECL(N) typename GetSimpleTypeT<P##N>::type_t p##N + +#define DECL_CMD(N) \ + template <class T, class M COMMA(N) COMMA_SEP_LIST(TYPE_PARAM, N)> \ + struct Command##N : public CommandBase { \ + T *instance; \ + M method; \ + SEMIC_SEP_LIST(PARAM_DECL, N); \ + virtual void call() { \ + (instance->*method)(COMMA_SEP_LIST(ARG, N)); \ + } \ + }; + +#define DECL_CMD_RET(N) \ + template <class T, class M, COMMA_SEP_LIST(TYPE_PARAM, N) COMMA(N) class R> \ + struct CommandRet##N : public SyncCommand { \ + R *ret; \ + T *instance; \ + M method; \ + SEMIC_SEP_LIST(PARAM_DECL, N); \ + virtual void call() { \ + *ret = (instance->*method)(COMMA_SEP_LIST(ARG, N)); \ + } \ + }; + +#define DECL_CMD_SYNC(N) \ + template <class T, class M COMMA(N) COMMA_SEP_LIST(TYPE_PARAM, N)> \ + struct CommandSync##N : public SyncCommand { \ + T *instance; \ + M method; \ + SEMIC_SEP_LIST(PARAM_DECL, N); \ + virtual void call() { \ + (instance->*method)(COMMA_SEP_LIST(ARG, N)); \ + } \ + }; + +#define TYPE_ARG(N) P##N +#define CMD_TYPE(N) Command##N<T, M COMMA(N) COMMA_SEP_LIST(TYPE_ARG, N)> +#define CMD_ASSIGN_PARAM(N) cmd->p##N = p##N + +#define DECL_PUSH(N) \ + template <class T, class M COMMA(N) COMMA_SEP_LIST(TYPE_PARAM, N)> \ + void push(T *p_instance, M p_method COMMA(N) COMMA_SEP_LIST(PARAM, N)) { \ + CMD_TYPE(N) *cmd = allocate_and_lock<CMD_TYPE(N)>(); \ + cmd->instance = p_instance; \ + cmd->method = p_method; \ + SEMIC_SEP_LIST(CMD_ASSIGN_PARAM, N); \ + unlock(); \ + if (sync) \ + sync->post(); \ + } + +#define CMD_RET_TYPE(N) CommandRet##N<T, M, COMMA_SEP_LIST(TYPE_ARG, N) COMMA(N) R> + +#define DECL_PUSH_AND_RET(N) \ + template <class T, class M, COMMA_SEP_LIST(TYPE_PARAM, N) COMMA(N) class R> \ + void push_and_ret(T *p_instance, M p_method, COMMA_SEP_LIST(PARAM, N) COMMA(N) R *r_ret) { \ + SyncSemaphore *ss = _alloc_sync_sem(); \ + CMD_RET_TYPE(N) *cmd = allocate_and_lock<CMD_RET_TYPE(N)>(); \ + cmd->instance = p_instance; \ + cmd->method = p_method; \ + SEMIC_SEP_LIST(CMD_ASSIGN_PARAM, N); \ + cmd->ret = r_ret; \ + cmd->sync_sem = ss; \ + unlock(); \ + if (sync) \ + sync->post(); \ + ss->sem.wait(); \ + ss->in_use = false; \ + } + +#define CMD_SYNC_TYPE(N) CommandSync##N<T, M COMMA(N) COMMA_SEP_LIST(TYPE_ARG, N)> + +#define DECL_PUSH_AND_SYNC(N) \ + template <class T, class M COMMA(N) COMMA_SEP_LIST(TYPE_PARAM, N)> \ + void push_and_sync(T *p_instance, M p_method COMMA(N) COMMA_SEP_LIST(PARAM, N)) { \ + SyncSemaphore *ss = _alloc_sync_sem(); \ + CMD_SYNC_TYPE(N) *cmd = allocate_and_lock<CMD_SYNC_TYPE(N)>(); \ + cmd->instance = p_instance; \ + cmd->method = p_method; \ + SEMIC_SEP_LIST(CMD_ASSIGN_PARAM, N); \ + cmd->sync_sem = ss; \ + unlock(); \ + if (sync) \ + sync->post(); \ + ss->sem.wait(); \ + ss->in_use = false; \ + } + +#define MAX_CMD_PARAMS 15 + +class CommandQueueMT { + struct SyncSemaphore { + Semaphore sem; + bool in_use = false; + }; + + struct CommandBase { + virtual void call() = 0; + virtual void post() {} + virtual ~CommandBase() {} + }; + + struct SyncCommand : public CommandBase { + SyncSemaphore *sync_sem; + + virtual void post() { + sync_sem->sem.post(); + } + }; + + DECL_CMD(0) + SPACE_SEP_LIST(DECL_CMD, 15) + + /* comands that return */ + DECL_CMD_RET(0) + SPACE_SEP_LIST(DECL_CMD_RET, 15) + + /* commands that don't return but sync */ + DECL_CMD_SYNC(0) + SPACE_SEP_LIST(DECL_CMD_SYNC, 15) + + /***** BASE *******/ + + enum { + DEFAULT_COMMAND_MEM_SIZE_KB = 256, + SYNC_SEMAPHORES = 8 + }; + + uint8_t *command_mem = nullptr; + uint32_t read_ptr_and_epoch = 0; + uint32_t write_ptr_and_epoch = 0; + uint32_t dealloc_ptr = 0; + uint32_t command_mem_size = 0; + SyncSemaphore sync_sems[SYNC_SEMAPHORES]; + Mutex mutex; + Semaphore *sync = nullptr; + + template <class T> + T *allocate() { + // alloc size is size+T+safeguard + uint32_t alloc_size = ((sizeof(T) + 8 - 1) & ~(8 - 1)) + 8; + + // Assert that the buffer is big enough to hold at least two messages. + ERR_FAIL_COND_V(alloc_size * 2 + sizeof(uint32_t) > command_mem_size, nullptr); + + tryagain: + uint32_t write_ptr = write_ptr_and_epoch >> 1; + + if (write_ptr < dealloc_ptr) { + // behind dealloc_ptr, check that there is room + if ((dealloc_ptr - write_ptr) <= alloc_size) { + // There is no more room, try to deallocate something + if (dealloc_one()) { + goto tryagain; + } + return nullptr; + } + } else { + // ahead of dealloc_ptr, check that there is room + + if ((command_mem_size - write_ptr) < alloc_size + sizeof(uint32_t)) { + // no room at the end, wrap down; + + if (dealloc_ptr == 0) { // don't want write_ptr to become dealloc_ptr + + // There is no more room, try to deallocate something + if (dealloc_one()) { + goto tryagain; + } + return nullptr; + } + + // if this happens, it's a bug + ERR_FAIL_COND_V((command_mem_size - write_ptr) < 8, nullptr); + // zero means, wrap to beginning + + uint32_t *p = (uint32_t *)&command_mem[write_ptr]; + *p = 1; + write_ptr_and_epoch = 0 | (1 & ~write_ptr_and_epoch); // Invert epoch. + // See if we can get the thread to run and clear up some more space while we wait. + // This is required if alloc_size * 2 + 4 > COMMAND_MEM_SIZE + if (sync) { + sync->post(); + } + goto tryagain; + } + } + // Allocate the size and the 'in use' bit. + // First bit used to mark if command is still in use (1) + // or if it has been destroyed and can be deallocated (0). + uint32_t size = (sizeof(T) + 8 - 1) & ~(8 - 1); + uint32_t *p = (uint32_t *)&command_mem[write_ptr]; + *p = (size << 1) | 1; + write_ptr += 8; + // allocate the command + T *cmd = memnew_placement(&command_mem[write_ptr], T); + write_ptr += size; + write_ptr_and_epoch = (write_ptr << 1) | (write_ptr_and_epoch & 1); + return cmd; + } + + template <class T> + T *allocate_and_lock() { + lock(); + T *ret; + + while ((ret = allocate<T>()) == nullptr) { + unlock(); + // sleep a little until fetch happened and some room is made + wait_for_flush(); + lock(); + } + + return ret; + } + + bool flush_one(bool p_lock = true) { + if (p_lock) { + lock(); + } + tryagain: + + // tried to read an empty queue + if (read_ptr_and_epoch == write_ptr_and_epoch) { + if (p_lock) { + unlock(); + } + return false; + } + + uint32_t read_ptr = read_ptr_and_epoch >> 1; + uint32_t size_ptr = read_ptr; + uint32_t size = *(uint32_t *)&command_mem[read_ptr] >> 1; + + if (size == 0) { + *(uint32_t *)&command_mem[read_ptr] = 0; // clear in-use bit. + //end of ringbuffer, wrap + read_ptr_and_epoch = 0 | (1 & ~read_ptr_and_epoch); // Invert epoch. + goto tryagain; + } + + read_ptr += 8; + + CommandBase *cmd = reinterpret_cast<CommandBase *>(&command_mem[read_ptr]); + + read_ptr += size; + + read_ptr_and_epoch = (read_ptr << 1) | (read_ptr_and_epoch & 1); + + if (p_lock) { + unlock(); + } + cmd->call(); + if (p_lock) { + lock(); + } + + cmd->post(); + cmd->~CommandBase(); + *(uint32_t *)&command_mem[size_ptr] &= ~1; + + if (p_lock) { + unlock(); + } + return true; + } + + void lock(); + void unlock(); + void wait_for_flush(); + SyncSemaphore *_alloc_sync_sem(); + bool dealloc_one(); + +public: + /* NORMAL PUSH COMMANDS */ + DECL_PUSH(0) + SPACE_SEP_LIST(DECL_PUSH, 15) + + /* PUSH AND RET COMMANDS */ + DECL_PUSH_AND_RET(0) + SPACE_SEP_LIST(DECL_PUSH_AND_RET, 15) + + /* PUSH AND RET SYNC COMMANDS*/ + DECL_PUSH_AND_SYNC(0) + SPACE_SEP_LIST(DECL_PUSH_AND_SYNC, 15) + + void wait_and_flush_one() { + ERR_FAIL_COND(!sync); + sync->wait(); + flush_one(); + } + + void flush_all() { + //ERR_FAIL_COND(sync); + lock(); + while (flush_one(false)) { + } + unlock(); + } + + CommandQueueMT(bool p_sync); + ~CommandQueueMT(); +}; + +#undef ARG +#undef PARAM +#undef TYPE_PARAM +#undef PARAM_DECL +#undef DECL_CMD +#undef DECL_CMD_RET +#undef DECL_CMD_SYNC +#undef TYPE_ARG +#undef CMD_TYPE +#undef CMD_ASSIGN_PARAM +#undef DECL_PUSH +#undef CMD_RET_TYPE +#undef DECL_PUSH_AND_RET +#undef CMD_SYNC_TYPE +#undef DECL_CMD_SYNC + +#endif // COMMAND_QUEUE_MT_H diff --git a/core/templates/cowdata.h b/core/templates/cowdata.h new file mode 100644 index 0000000000..d5eb08286d --- /dev/null +++ b/core/templates/cowdata.h @@ -0,0 +1,372 @@ +/*************************************************************************/ +/* cowdata.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef COWDATA_H +#define COWDATA_H + +#include "core/error/error_macros.h" +#include "core/os/memory.h" +#include "core/templates/safe_refcount.h" + +#include <string.h> + +template <class T> +class Vector; +class String; +class Char16String; +class CharString; +template <class T, class V> +class VMap; + +template <class T> +class CowData { + template <class TV> + friend class Vector; + friend class String; + friend class Char16String; + friend class CharString; + template <class TV, class VV> + friend class VMap; + +private: + mutable T *_ptr = nullptr; + + // internal helpers + + _FORCE_INLINE_ uint32_t *_get_refcount() const { + if (!_ptr) { + return nullptr; + } + + return reinterpret_cast<uint32_t *>(_ptr) - 2; + } + + _FORCE_INLINE_ uint32_t *_get_size() const { + if (!_ptr) { + return nullptr; + } + + return reinterpret_cast<uint32_t *>(_ptr) - 1; + } + + _FORCE_INLINE_ T *_get_data() const { + if (!_ptr) { + return nullptr; + } + return reinterpret_cast<T *>(_ptr); + } + + _FORCE_INLINE_ size_t _get_alloc_size(size_t p_elements) const { + return next_power_of_2(p_elements * sizeof(T)); + } + + _FORCE_INLINE_ bool _get_alloc_size_checked(size_t p_elements, size_t *out) const { +#if defined(__GNUC__) + size_t o; + size_t p; + if (__builtin_mul_overflow(p_elements, sizeof(T), &o)) { + *out = 0; + return false; + } + *out = next_power_of_2(o); + if (__builtin_add_overflow(o, static_cast<size_t>(32), &p)) { + return false; // No longer allocated here. + } + return true; +#else + // Speed is more important than correctness here, do the operations unchecked + // and hope for the best. + *out = _get_alloc_size(p_elements); + return true; +#endif + } + + void _unref(void *p_data); + void _ref(const CowData *p_from); + void _ref(const CowData &p_from); + void _copy_on_write(); + +public: + void operator=(const CowData<T> &p_from) { _ref(p_from); } + + _FORCE_INLINE_ T *ptrw() { + _copy_on_write(); + return (T *)_get_data(); + } + + _FORCE_INLINE_ const T *ptr() const { + return _get_data(); + } + + _FORCE_INLINE_ int size() const { + uint32_t *size = (uint32_t *)_get_size(); + if (size) { + return *size; + } else { + return 0; + } + } + + _FORCE_INLINE_ void clear() { resize(0); } + _FORCE_INLINE_ bool empty() const { return _ptr == nullptr; } + + _FORCE_INLINE_ void set(int p_index, const T &p_elem) { + CRASH_BAD_INDEX(p_index, size()); + _copy_on_write(); + _get_data()[p_index] = p_elem; + } + + _FORCE_INLINE_ T &get_m(int p_index) { + CRASH_BAD_INDEX(p_index, size()); + _copy_on_write(); + return _get_data()[p_index]; + } + + _FORCE_INLINE_ const T &get(int p_index) const { + CRASH_BAD_INDEX(p_index, size()); + + return _get_data()[p_index]; + } + + Error resize(int p_size); + + _FORCE_INLINE_ void remove(int p_index) { + ERR_FAIL_INDEX(p_index, size()); + T *p = ptrw(); + int len = size(); + for (int i = p_index; i < len - 1; i++) { + p[i] = p[i + 1]; + } + + resize(len - 1); + } + + Error insert(int p_pos, const T &p_val) { + ERR_FAIL_INDEX_V(p_pos, size() + 1, ERR_INVALID_PARAMETER); + resize(size() + 1); + for (int i = (size() - 1); i > p_pos; i--) { + set(i, get(i - 1)); + } + set(p_pos, p_val); + + return OK; + } + + int find(const T &p_val, int p_from = 0) const; + + _FORCE_INLINE_ CowData() {} + _FORCE_INLINE_ ~CowData(); + _FORCE_INLINE_ CowData(CowData<T> &p_from) { _ref(p_from); }; +}; + +template <class T> +void CowData<T>::_unref(void *p_data) { + if (!p_data) { + return; + } + + uint32_t *refc = _get_refcount(); + + if (atomic_decrement(refc) > 0) { + return; // still in use + } + // clean up + + if (!__has_trivial_destructor(T)) { + uint32_t *count = _get_size(); + T *data = (T *)(count + 1); + + for (uint32_t i = 0; i < *count; ++i) { + // call destructors + data[i].~T(); + } + } + + // free mem + Memory::free_static((uint8_t *)p_data, true); +} + +template <class T> +void CowData<T>::_copy_on_write() { + if (!_ptr) { + return; + } + + uint32_t *refc = _get_refcount(); + + if (unlikely(*refc > 1)) { + /* in use by more than me */ + uint32_t current_size = *_get_size(); + + uint32_t *mem_new = (uint32_t *)Memory::alloc_static(_get_alloc_size(current_size), true); + + *(mem_new - 2) = 1; //refcount + *(mem_new - 1) = current_size; //size + + T *_data = (T *)(mem_new); + + // initialize new elements + if (__has_trivial_copy(T)) { + memcpy(mem_new, _ptr, current_size * sizeof(T)); + + } else { + for (uint32_t i = 0; i < current_size; i++) { + memnew_placement(&_data[i], T(_get_data()[i])); + } + } + + _unref(_ptr); + _ptr = _data; + } +} + +template <class T> +Error CowData<T>::resize(int p_size) { + ERR_FAIL_COND_V(p_size < 0, ERR_INVALID_PARAMETER); + + int current_size = size(); + + if (p_size == current_size) { + return OK; + } + + if (p_size == 0) { + // wants to clean up + _unref(_ptr); + _ptr = nullptr; + return OK; + } + + // possibly changing size, copy on write + _copy_on_write(); + + size_t current_alloc_size = _get_alloc_size(current_size); + size_t alloc_size; + ERR_FAIL_COND_V(!_get_alloc_size_checked(p_size, &alloc_size), ERR_OUT_OF_MEMORY); + + if (p_size > current_size) { + if (alloc_size != current_alloc_size) { + if (current_size == 0) { + // alloc from scratch + uint32_t *ptr = (uint32_t *)Memory::alloc_static(alloc_size, true); + ERR_FAIL_COND_V(!ptr, ERR_OUT_OF_MEMORY); + *(ptr - 1) = 0; //size, currently none + *(ptr - 2) = 1; //refcount + + _ptr = (T *)ptr; + + } else { + void *_ptrnew = (T *)Memory::realloc_static(_ptr, alloc_size, true); + ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY); + _ptr = (T *)(_ptrnew); + } + } + + // construct the newly created elements + + if (!__has_trivial_constructor(T)) { + T *elems = _get_data(); + + for (int i = *_get_size(); i < p_size; i++) { + memnew_placement(&elems[i], T); + } + } + + *_get_size() = p_size; + + } else if (p_size < current_size) { + if (!__has_trivial_destructor(T)) { + // deinitialize no longer needed elements + for (uint32_t i = p_size; i < *_get_size(); i++) { + T *t = &_get_data()[i]; + t->~T(); + } + } + + if (alloc_size != current_alloc_size) { + void *_ptrnew = (T *)Memory::realloc_static(_ptr, alloc_size, true); + ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY); + + _ptr = (T *)(_ptrnew); + } + + *_get_size() = p_size; + } + + return OK; +} + +template <class T> +int CowData<T>::find(const T &p_val, int p_from) const { + int ret = -1; + + if (p_from < 0 || size() == 0) { + return ret; + } + + for (int i = p_from; i < size(); i++) { + if (get(i) == p_val) { + ret = i; + break; + } + } + + return ret; +} + +template <class T> +void CowData<T>::_ref(const CowData *p_from) { + _ref(*p_from); +} + +template <class T> +void CowData<T>::_ref(const CowData &p_from) { + if (_ptr == p_from._ptr) { + return; // self assign, do nothing. + } + + _unref(_ptr); + _ptr = nullptr; + + if (!p_from._ptr) { + return; //nothing to do + } + + if (atomic_conditional_increment(p_from._get_refcount()) > 0) { // could reference + _ptr = p_from._ptr; + } +} + +template <class T> +CowData<T>::~CowData() { + _unref(_ptr); +} + +#endif // COWDATA_H diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h new file mode 100644 index 0000000000..f6b889015a --- /dev/null +++ b/core/templates/hash_map.h @@ -0,0 +1,551 @@ +/*************************************************************************/ +/* hash_map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef HASH_MAP_H +#define HASH_MAP_H + +#include "core/error/error_macros.h" +#include "core/math/math_funcs.h" +#include "core/os/memory.h" +#include "core/string/ustring.h" +#include "core/templates/hashfuncs.h" +#include "core/templates/list.h" + +/** + * @class HashMap + * @author Juan Linietsky <reduzio@gmail.com> + * + * Implementation of a standard Hashing HashMap, for quick lookups of Data associated with a Key. + * The implementation provides hashers for the default types, if you need a special kind of hasher, provide + * your own. + * @param TKey Key, search is based on it, needs to be hasheable. It is unique in this container. + * @param TData Data, data associated with the key + * @param Hasher Hasher object, needs to provide a valid static hash function for TKey + * @param Comparator comparator object, needs to be able to safely compare two TKey values. It needs to ensure that x == x for any items inserted in the map. Bear in mind that nan != nan when implementing an equality check. + * @param MIN_HASH_TABLE_POWER Miminum size of the hash table, as a power of two. You rarely need to change this parameter. + * @param RELATIONSHIP Relationship at which the hash table is resized. if amount of elements is RELATIONSHIP + * times bigger than the hash table, table is resized to solve this condition. if RELATIONSHIP is zero, table is always MIN_HASH_TABLE_POWER. + * +*/ + +template <class TKey, class TData, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<TKey>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> +class HashMap { +public: + struct Pair { + TKey key; + TData data; + + Pair() {} + Pair(const TKey &p_key, const TData &p_data) : + key(p_key), + data(p_data) { + } + }; + + struct Element { + private: + friend class HashMap; + + uint32_t hash; + Element *next = nullptr; + Element() {} + Pair pair; + + public: + const TKey &key() const { + return pair.key; + } + + TData &value() { + return pair.data; + } + + const TData &value() const { + return pair.value(); + } + }; + +private: + Element **hash_table = nullptr; + uint8_t hash_table_power = 0; + uint32_t elements = 0; + + void make_hash_table() { + ERR_FAIL_COND(hash_table); + + hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER)); + + hash_table_power = MIN_HASH_TABLE_POWER; + elements = 0; + for (int i = 0; i < (1 << MIN_HASH_TABLE_POWER); i++) { + hash_table[i] = nullptr; + } + } + + void erase_hash_table() { + ERR_FAIL_COND_MSG(elements, "Cannot erase hash table if there are still elements inside."); + + memdelete_arr(hash_table); + hash_table = nullptr; + hash_table_power = 0; + elements = 0; + } + + void check_hash_table() { + int new_hash_table_power = -1; + + if ((int)elements > ((1 << hash_table_power) * RELATIONSHIP)) { + /* rehash up */ + new_hash_table_power = hash_table_power + 1; + + while ((int)elements > ((1 << new_hash_table_power) * RELATIONSHIP)) { + new_hash_table_power++; + } + + } else if ((hash_table_power > (int)MIN_HASH_TABLE_POWER) && ((int)elements < ((1 << (hash_table_power - 1)) * RELATIONSHIP))) { + /* rehash down */ + new_hash_table_power = hash_table_power - 1; + + while ((int)elements < ((1 << (new_hash_table_power - 1)) * RELATIONSHIP)) { + new_hash_table_power--; + } + + if (new_hash_table_power < (int)MIN_HASH_TABLE_POWER) { + new_hash_table_power = MIN_HASH_TABLE_POWER; + } + } + + if (new_hash_table_power == -1) { + return; + } + + Element **new_hash_table = memnew_arr(Element *, ((uint64_t)1 << new_hash_table_power)); + ERR_FAIL_COND_MSG(!new_hash_table, "Out of memory."); + + for (int i = 0; i < (1 << new_hash_table_power); i++) { + new_hash_table[i] = nullptr; + } + + if (hash_table) { + for (int i = 0; i < (1 << hash_table_power); i++) { + while (hash_table[i]) { + Element *se = hash_table[i]; + hash_table[i] = se->next; + int new_pos = se->hash & ((1 << new_hash_table_power) - 1); + se->next = new_hash_table[new_pos]; + new_hash_table[new_pos] = se; + } + } + + memdelete_arr(hash_table); + } + hash_table = new_hash_table; + hash_table_power = new_hash_table_power; + } + + /* I want to have only one function.. */ + _FORCE_INLINE_ const Element *get_element(const TKey &p_key) const { + uint32_t hash = Hasher::hash(p_key); + uint32_t index = hash & ((1 << hash_table_power) - 1); + + Element *e = hash_table[index]; + + while (e) { + /* checking hash first avoids comparing key, which may take longer */ + if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { + /* the pair exists in this hashtable, so just update data */ + return e; + } + + e = e->next; + } + + return nullptr; + } + + Element *create_element(const TKey &p_key) { + /* if element doesn't exist, create it */ + Element *e = memnew(Element); + ERR_FAIL_COND_V_MSG(!e, nullptr, "Out of memory."); + uint32_t hash = Hasher::hash(p_key); + uint32_t index = hash & ((1 << hash_table_power) - 1); + e->next = hash_table[index]; + e->hash = hash; + e->pair.key = p_key; + e->pair.data = TData(); + + hash_table[index] = e; + elements++; + + return e; + } + + void copy_from(const HashMap &p_t) { + if (&p_t == this) { + return; /* much less bother with that */ + } + + clear(); + + if (!p_t.hash_table || p_t.hash_table_power == 0) { + return; /* not copying from empty table */ + } + + hash_table = memnew_arr(Element *, (uint64_t)1 << p_t.hash_table_power); + hash_table_power = p_t.hash_table_power; + elements = p_t.elements; + + for (int i = 0; i < (1 << p_t.hash_table_power); i++) { + hash_table[i] = nullptr; + + const Element *e = p_t.hash_table[i]; + + while (e) { + Element *le = memnew(Element); /* local element */ + + *le = *e; /* copy data */ + + /* add to list and reassign pointers */ + le->next = hash_table[i]; + hash_table[i] = le; + + e = e->next; + } + } + } + +public: + Element *set(const TKey &p_key, const TData &p_data) { + return set(Pair(p_key, p_data)); + } + + Element *set(const Pair &p_pair) { + Element *e = nullptr; + if (!hash_table) { + make_hash_table(); // if no table, make one + } else { + e = const_cast<Element *>(get_element(p_pair.key)); + } + + /* if we made it up to here, the pair doesn't exist, create and assign */ + + if (!e) { + e = create_element(p_pair.key); + if (!e) { + return nullptr; + } + check_hash_table(); // perform mantenience routine + } + + e->pair.data = p_pair.data; + return e; + } + + bool has(const TKey &p_key) const { + return getptr(p_key) != nullptr; + } + + /** + * Get a key from data, return a const reference. + * WARNING: this doesn't check errors, use either getptr and check nullptr, or check + * first with has(key) + */ + + const TData &get(const TKey &p_key) const { + const TData *res = getptr(p_key); + CRASH_COND_MSG(!res, "Map key not found."); + return *res; + } + + TData &get(const TKey &p_key) { + TData *res = getptr(p_key); + CRASH_COND_MSG(!res, "Map key not found."); + return *res; + } + + /** + * Same as get, except it can return nullptr when item was not found. + * This is mainly used for speed purposes. + */ + + _FORCE_INLINE_ TData *getptr(const TKey &p_key) { + if (unlikely(!hash_table)) { + return nullptr; + } + + Element *e = const_cast<Element *>(get_element(p_key)); + + if (e) { + return &e->pair.data; + } + + return nullptr; + } + + _FORCE_INLINE_ const TData *getptr(const TKey &p_key) const { + if (unlikely(!hash_table)) { + return nullptr; + } + + const Element *e = const_cast<Element *>(get_element(p_key)); + + if (e) { + return &e->pair.data; + } + + return nullptr; + } + + /** + * Same as get, except it can return nullptr when item was not found. + * This version is custom, will take a hash and a custom key (that should support operator==() + */ + + template <class C> + _FORCE_INLINE_ TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) { + if (unlikely(!hash_table)) { + return nullptr; + } + + uint32_t hash = p_custom_hash; + uint32_t index = hash & ((1 << hash_table_power) - 1); + + Element *e = hash_table[index]; + + while (e) { + /* checking hash first avoids comparing key, which may take longer */ + if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { + /* the pair exists in this hashtable, so just update data */ + return &e->pair.data; + } + + e = e->next; + } + + return nullptr; + } + + template <class C> + _FORCE_INLINE_ const TData *custom_getptr(C p_custom_key, uint32_t p_custom_hash) const { + if (unlikely(!hash_table)) { + return nullptr; + } + + uint32_t hash = p_custom_hash; + uint32_t index = hash & ((1 << hash_table_power) - 1); + + const Element *e = hash_table[index]; + + while (e) { + /* checking hash first avoids comparing key, which may take longer */ + if (e->hash == hash && Comparator::compare(e->pair.key, p_custom_key)) { + /* the pair exists in this hashtable, so just update data */ + return &e->pair.data; + } + + e = e->next; + } + + return nullptr; + } + + /** + * Erase an item, return true if erasing was successful + */ + + bool erase(const TKey &p_key) { + if (unlikely(!hash_table)) { + return false; + } + + uint32_t hash = Hasher::hash(p_key); + uint32_t index = hash & ((1 << hash_table_power) - 1); + + Element *e = hash_table[index]; + Element *p = nullptr; + while (e) { + /* checking hash first avoids comparing key, which may take longer */ + if (e->hash == hash && Comparator::compare(e->pair.key, p_key)) { + if (p) { + p->next = e->next; + } else { + //begin of list + hash_table[index] = e->next; + } + + memdelete(e); + elements--; + + if (elements == 0) { + erase_hash_table(); + } else { + check_hash_table(); + } + return true; + } + + p = e; + e = e->next; + } + + return false; + } + + inline const TData &operator[](const TKey &p_key) const { //constref + + return get(p_key); + } + inline TData &operator[](const TKey &p_key) { //assignment + + Element *e = nullptr; + if (!hash_table) { + make_hash_table(); // if no table, make one + } else { + e = const_cast<Element *>(get_element(p_key)); + } + + /* if we made it up to here, the pair doesn't exist, create */ + if (!e) { + e = create_element(p_key); + CRASH_COND(!e); + check_hash_table(); // perform mantenience routine + } + + return e->pair.data; + } + + /** + * Get the next key to p_key, and the first key if p_key is null. + * Returns a pointer to the next key if found, nullptr otherwise. + * Adding/Removing elements while iterating will, of course, have unexpected results, don't do it. + * + * Example: + * + * const TKey *k=nullptr; + * + * while( (k=table.next(k)) ) { + * + * print( *k ); + * } + * + */ + const TKey *next(const TKey *p_key) const { + if (unlikely(!hash_table)) { + return nullptr; + } + + if (!p_key) { /* get the first key */ + + for (int i = 0; i < (1 << hash_table_power); i++) { + if (hash_table[i]) { + return &hash_table[i]->pair.key; + } + } + + } else { /* get the next key */ + + const Element *e = get_element(*p_key); + ERR_FAIL_COND_V_MSG(!e, nullptr, "Invalid key supplied."); + if (e->next) { + /* if there is a "next" in the list, return that */ + return &e->next->pair.key; + } else { + /* go to next elements */ + uint32_t index = e->hash & ((1 << hash_table_power) - 1); + index++; + for (int i = index; i < (1 << hash_table_power); i++) { + if (hash_table[i]) { + return &hash_table[i]->pair.key; + } + } + } + + /* nothing found, was at end */ + } + + return nullptr; /* nothing found */ + } + + inline unsigned int size() const { + return elements; + } + + inline bool empty() const { + return elements == 0; + } + + void clear() { + /* clean up */ + if (hash_table) { + for (int i = 0; i < (1 << hash_table_power); i++) { + while (hash_table[i]) { + Element *e = hash_table[i]; + hash_table[i] = e->next; + memdelete(e); + } + } + + memdelete_arr(hash_table); + } + + hash_table = nullptr; + hash_table_power = 0; + elements = 0; + } + + void operator=(const HashMap &p_table) { + copy_from(p_table); + } + + void get_key_list(List<TKey> *r_keys) const { + if (unlikely(!hash_table)) { + return; + } + for (int i = 0; i < (1 << hash_table_power); i++) { + Element *e = hash_table[i]; + while (e) { + r_keys->push_back(e->pair.key); + e = e->next; + } + } + } + + HashMap() {} + + HashMap(const HashMap &p_table) { + copy_from(p_table); + } + + ~HashMap() { + clear(); + } +}; + +#endif // HASH_MAP_H diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h new file mode 100644 index 0000000000..86bb1b5228 --- /dev/null +++ b/core/templates/hashfuncs.h @@ -0,0 +1,174 @@ +/*************************************************************************/ +/* hashfuncs.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef HASHFUNCS_H +#define HASHFUNCS_H + +#include "core/math/math_defs.h" +#include "core/math/math_funcs.h" +#include "core/object/object_id.h" +#include "core/string/node_path.h" +#include "core/string/string_name.h" +#include "core/string/ustring.h" +#include "core/templates/rid.h" +#include "core/typedefs.h" +/** + * Hashing functions + */ + +/** + * DJB2 Hash function + * @param C String + * @return 32-bits hashcode + */ +static inline uint32_t hash_djb2(const char *p_cstr) { + const unsigned char *chr = (const unsigned char *)p_cstr; + uint32_t hash = 5381; + uint32_t c; + + while ((c = *chr++)) { + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + } + + return hash; +} + +static inline uint32_t hash_djb2_buffer(const uint8_t *p_buff, int p_len, uint32_t p_prev = 5381) { + uint32_t hash = p_prev; + + for (int i = 0; i < p_len; i++) { + hash = ((hash << 5) + hash) + p_buff[i]; /* hash * 33 + c */ + } + + return hash; +} + +static inline uint32_t hash_djb2_one_32(uint32_t p_in, uint32_t p_prev = 5381) { + return ((p_prev << 5) + p_prev) + p_in; +} + +static inline uint32_t hash_one_uint64(const uint64_t p_int) { + uint64_t v = p_int; + v = (~v) + (v << 18); // v = (v << 18) - v - 1; + v = v ^ (v >> 31); + v = v * 21; // v = (v + (v << 2)) + (v << 4); + v = v ^ (v >> 11); + v = v + (v << 6); + v = v ^ (v >> 22); + return (int)v; +} + +static inline uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381) { + union { + double d; + uint64_t i; + } u; + + // Normalize +/- 0.0 and NaN values so they hash the same. + if (p_in == 0.0f) { + u.d = 0.0; + } else if (Math::is_nan(p_in)) { + u.d = Math_NAN; + } else { + u.d = p_in; + } + + return ((p_prev << 5) + p_prev) + hash_one_uint64(u.i); +} + +template <class T> +static inline uint32_t make_uint32_t(T p_in) { + union { + T t; + uint32_t _u32; + } _u; + _u._u32 = 0; + _u.t = p_in; + return _u._u32; +} + +static inline uint64_t hash_djb2_one_64(uint64_t p_in, uint64_t p_prev = 5381) { + return ((p_prev << 5) + p_prev) + p_in; +} + +template <class T> +static inline uint64_t make_uint64_t(T p_in) { + union { + T t; + uint64_t _u64; + } _u; + _u._u64 = 0; // in case p_in is smaller + + _u.t = p_in; + return _u._u64; +} + +struct HashMapHasherDefault { + static _FORCE_INLINE_ uint32_t hash(const String &p_string) { return p_string.hash(); } + static _FORCE_INLINE_ uint32_t hash(const char *p_cstr) { return hash_djb2(p_cstr); } + static _FORCE_INLINE_ uint32_t hash(const uint64_t p_int) { return hash_one_uint64(p_int); } + static _FORCE_INLINE_ uint32_t hash(const ObjectID &p_id) { return hash_one_uint64(p_id); } + + static _FORCE_INLINE_ uint32_t hash(const int64_t p_int) { return hash(uint64_t(p_int)); } + static _FORCE_INLINE_ uint32_t hash(const float p_float) { return hash_djb2_one_float(p_float); } + static _FORCE_INLINE_ uint32_t hash(const double p_double) { return hash_djb2_one_float(p_double); } + static _FORCE_INLINE_ uint32_t hash(const uint32_t p_int) { return p_int; } + static _FORCE_INLINE_ uint32_t hash(const int32_t p_int) { return (uint32_t)p_int; } + static _FORCE_INLINE_ uint32_t hash(const uint16_t p_int) { return p_int; } + static _FORCE_INLINE_ uint32_t hash(const int16_t p_int) { return (uint32_t)p_int; } + static _FORCE_INLINE_ uint32_t hash(const uint8_t p_int) { return p_int; } + static _FORCE_INLINE_ uint32_t hash(const int8_t p_int) { return (uint32_t)p_int; } + static _FORCE_INLINE_ uint32_t hash(const wchar_t p_wchar) { return (uint32_t)p_wchar; } + static _FORCE_INLINE_ uint32_t hash(const char16_t p_uchar) { return (uint32_t)p_uchar; } + static _FORCE_INLINE_ uint32_t hash(const char32_t p_uchar) { return (uint32_t)p_uchar; } + static _FORCE_INLINE_ uint32_t hash(const RID &p_rid) { return hash_one_uint64(p_rid.get_id()); } + + static _FORCE_INLINE_ uint32_t hash(const StringName &p_string_name) { return p_string_name.hash(); } + static _FORCE_INLINE_ uint32_t hash(const NodePath &p_path) { return p_path.hash(); } + + //static _FORCE_INLINE_ uint32_t hash(const void* p_ptr) { return uint32_t(uint64_t(p_ptr))*(0x9e3779b1L); } +}; + +template <typename T> +struct HashMapComparatorDefault { + static bool compare(const T &p_lhs, const T &p_rhs) { + return p_lhs == p_rhs; + } + + bool compare(const float &p_lhs, const float &p_rhs) { + return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs)); + } + + bool compare(const double &p_lhs, const double &p_rhs) { + return (p_lhs == p_rhs) || (Math::is_nan(p_lhs) && Math::is_nan(p_rhs)); + } +}; + +#endif // HASHFUNCS_H diff --git a/core/templates/list.h b/core/templates/list.h new file mode 100644 index 0000000000..d745066e4c --- /dev/null +++ b/core/templates/list.h @@ -0,0 +1,688 @@ +/*************************************************************************/ +/* list.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef LIST_H +#define LIST_H + +#include "core/error/error_macros.h" +#include "core/os/memory.h" +#include "core/templates/sort_array.h" + +/** + * Generic Templatized Linked List Implementation. + * The implementation differs from the STL one because + * a compatible preallocated linked list can be written + * using the same API, or features such as erasing an element + * from the iterator. + */ + +template <class T, class A = DefaultAllocator> +class List { + struct _Data; + +public: + class Element { + private: + friend class List<T, A>; + + T value; + Element *next_ptr = nullptr; + Element *prev_ptr = nullptr; + _Data *data = nullptr; + + public: + /** + * Get NEXT Element iterator, for constant lists. + */ + _FORCE_INLINE_ const Element *next() const { + return next_ptr; + } + /** + * Get NEXT Element iterator, + */ + _FORCE_INLINE_ Element *next() { + return next_ptr; + } + + /** + * Get PREV Element iterator, for constant lists. + */ + _FORCE_INLINE_ const Element *prev() const { + return prev_ptr; + } + /** + * Get PREV Element iterator, + */ + _FORCE_INLINE_ Element *prev() { + return prev_ptr; + } + + /** + * * operator, for using as *iterator, when iterators are defined on stack. + */ + _FORCE_INLINE_ const T &operator*() const { + return value; + } + /** + * operator->, for using as iterator->, when iterators are defined on stack, for constant lists. + */ + _FORCE_INLINE_ const T *operator->() const { + return &value; + } + /** + * * operator, for using as *iterator, when iterators are defined on stack, + */ + _FORCE_INLINE_ T &operator*() { + return value; + } + /** + * operator->, for using as iterator->, when iterators are defined on stack, for constant lists. + */ + _FORCE_INLINE_ T *operator->() { + return &value; + } + + /** + * get the value stored in this element. + */ + _FORCE_INLINE_ T &get() { + return value; + } + /** + * get the value stored in this element, for constant lists + */ + _FORCE_INLINE_ const T &get() const { + return value; + } + /** + * set the value stored in this element. + */ + _FORCE_INLINE_ void set(const T &p_value) { + value = (T &)p_value; + } + + void erase() { + data->erase(this); + } + + _FORCE_INLINE_ Element() {} + }; + +private: + struct _Data { + Element *first; + Element *last; + int size_cache; + + bool erase(const Element *p_I) { + ERR_FAIL_COND_V(!p_I, false); + ERR_FAIL_COND_V(p_I->data != this, false); + + if (first == p_I) { + first = p_I->next_ptr; + } + + if (last == p_I) { + last = p_I->prev_ptr; + } + + if (p_I->prev_ptr) { + p_I->prev_ptr->next_ptr = p_I->next_ptr; + } + + if (p_I->next_ptr) { + p_I->next_ptr->prev_ptr = p_I->prev_ptr; + } + + memdelete_allocator<Element, A>(const_cast<Element *>(p_I)); + size_cache--; + + return true; + } + }; + + _Data *_data = nullptr; + +public: + /** + * return a const iterator to the beginning of the list. + */ + _FORCE_INLINE_ const Element *front() const { + return _data ? _data->first : nullptr; + } + + /** + * return an iterator to the beginning of the list. + */ + _FORCE_INLINE_ Element *front() { + return _data ? _data->first : nullptr; + } + + /** + * return a const iterator to the last member of the list. + */ + _FORCE_INLINE_ const Element *back() const { + return _data ? _data->last : nullptr; + } + + /** + * return an iterator to the last member of the list. + */ + _FORCE_INLINE_ Element *back() { + return _data ? _data->last : nullptr; + } + + /** + * store a new element at the end of the list + */ + Element *push_back(const T &value) { + if (!_data) { + _data = memnew_allocator(_Data, A); + _data->first = nullptr; + _data->last = nullptr; + _data->size_cache = 0; + } + + Element *n = memnew_allocator(Element, A); + n->value = (T &)value; + + n->prev_ptr = _data->last; + n->next_ptr = nullptr; + n->data = _data; + + if (_data->last) { + _data->last->next_ptr = n; + } + + _data->last = n; + + if (!_data->first) { + _data->first = n; + } + + _data->size_cache++; + + return n; + } + + void pop_back() { + if (_data && _data->last) { + erase(_data->last); + } + } + + /** + * store a new element at the beginning of the list + */ + Element *push_front(const T &value) { + if (!_data) { + _data = memnew_allocator(_Data, A); + _data->first = nullptr; + _data->last = nullptr; + _data->size_cache = 0; + } + + Element *n = memnew_allocator(Element, A); + n->value = (T &)value; + n->prev_ptr = nullptr; + n->next_ptr = _data->first; + n->data = _data; + + if (_data->first) { + _data->first->prev_ptr = n; + } + + _data->first = n; + + if (!_data->last) { + _data->last = n; + } + + _data->size_cache++; + + return n; + } + + void pop_front() { + if (_data && _data->first) { + erase(_data->first); + } + } + + Element *insert_after(Element *p_element, const T &p_value) { + CRASH_COND(p_element && (!_data || p_element->data != _data)); + + if (!p_element) { + return push_back(p_value); + } + + Element *n = memnew_allocator(Element, A); + n->value = (T &)p_value; + n->prev_ptr = p_element; + n->next_ptr = p_element->next_ptr; + n->data = _data; + + if (!p_element->next_ptr) { + _data->last = n; + } else { + p_element->next_ptr->prev_ptr = n; + } + + p_element->next_ptr = n; + + _data->size_cache++; + + return n; + } + + Element *insert_before(Element *p_element, const T &p_value) { + CRASH_COND(p_element && (!_data || p_element->data != _data)); + + if (!p_element) { + return push_back(p_value); + } + + Element *n = memnew_allocator(Element, A); + n->value = (T &)p_value; + n->prev_ptr = p_element->prev_ptr; + n->next_ptr = p_element; + n->data = _data; + + if (!p_element->prev_ptr) { + _data->first = n; + } else { + p_element->prev_ptr->next_ptr = n; + } + + p_element->prev_ptr = n; + + _data->size_cache++; + + return n; + } + + /** + * find an element in the list, + */ + template <class T_v> + Element *find(const T_v &p_val) { + Element *it = front(); + while (it) { + if (it->value == p_val) { + return it; + } + it = it->next(); + } + + return nullptr; + } + + /** + * erase an element in the list, by iterator pointing to it. Return true if it was found/erased. + */ + bool erase(const Element *p_I) { + if (_data && p_I) { + bool ret = _data->erase(p_I); + + if (_data->size_cache == 0) { + memdelete_allocator<_Data, A>(_data); + _data = nullptr; + } + + return ret; + } + + return false; + } + + /** + * erase the first element in the list, that contains value + */ + bool erase(const T &value) { + Element *I = find(value); + return erase(I); + } + + /** + * return whether the list is empty + */ + _FORCE_INLINE_ bool empty() const { + return (!_data || !_data->size_cache); + } + + /** + * clear the list + */ + void clear() { + while (front()) { + erase(front()); + } + } + + _FORCE_INLINE_ int size() const { + return _data ? _data->size_cache : 0; + } + + void swap(Element *p_A, Element *p_B) { + ERR_FAIL_COND(!p_A || !p_B); + ERR_FAIL_COND(p_A->data != _data); + ERR_FAIL_COND(p_B->data != _data); + + if (p_A == p_B) { + return; + } + Element *A_prev = p_A->prev_ptr; + Element *A_next = p_A->next_ptr; + Element *B_prev = p_B->prev_ptr; + Element *B_next = p_B->next_ptr; + + if (A_prev) { + A_prev->next_ptr = p_B; + } else { + _data->first = p_B; + } + if (B_prev) { + B_prev->next_ptr = p_A; + } else { + _data->first = p_A; + } + if (A_next) { + A_next->prev_ptr = p_B; + } else { + _data->last = p_B; + } + if (B_next) { + B_next->prev_ptr = p_A; + } else { + _data->last = p_A; + } + p_A->prev_ptr = A_next == p_B ? p_B : B_prev; + p_A->next_ptr = B_next == p_A ? p_B : B_next; + p_B->prev_ptr = B_next == p_A ? p_A : A_prev; + p_B->next_ptr = A_next == p_B ? p_A : A_next; + } + /** + * copy the list + */ + void operator=(const List &p_list) { + clear(); + const Element *it = p_list.front(); + while (it) { + push_back(it->get()); + it = it->next(); + } + } + + T &operator[](int p_index) { + CRASH_BAD_INDEX(p_index, size()); + + Element *I = front(); + int c = 0; + while (c < p_index) { + I = I->next(); + c++; + } + + return I->get(); + } + + const T &operator[](int p_index) const { + CRASH_BAD_INDEX(p_index, size()); + + const Element *I = front(); + int c = 0; + while (c < p_index) { + I = I->next(); + c++; + } + + return I->get(); + } + + void move_to_back(Element *p_I) { + ERR_FAIL_COND(p_I->data != _data); + if (!p_I->next_ptr) { + return; + } + + if (_data->first == p_I) { + _data->first = p_I->next_ptr; + } + + if (_data->last == p_I) { + _data->last = p_I->prev_ptr; + } + + if (p_I->prev_ptr) { + p_I->prev_ptr->next_ptr = p_I->next_ptr; + } + + p_I->next_ptr->prev_ptr = p_I->prev_ptr; + + _data->last->next_ptr = p_I; + p_I->prev_ptr = _data->last; + p_I->next_ptr = nullptr; + _data->last = p_I; + } + + void invert() { + int s = size() / 2; + Element *F = front(); + Element *B = back(); + for (int i = 0; i < s; i++) { + SWAP(F->value, B->value); + F = F->next(); + B = B->prev(); + } + } + + void move_to_front(Element *p_I) { + ERR_FAIL_COND(p_I->data != _data); + if (!p_I->prev_ptr) { + return; + } + + if (_data->first == p_I) { + _data->first = p_I->next_ptr; + } + + if (_data->last == p_I) { + _data->last = p_I->prev_ptr; + } + + p_I->prev_ptr->next_ptr = p_I->next_ptr; + + if (p_I->next_ptr) { + p_I->next_ptr->prev_ptr = p_I->prev_ptr; + } + + _data->first->prev_ptr = p_I; + p_I->next_ptr = _data->first; + p_I->prev_ptr = nullptr; + _data->first = p_I; + } + + void move_before(Element *value, Element *where) { + if (value->prev_ptr) { + value->prev_ptr->next_ptr = value->next_ptr; + } else { + _data->first = value->next_ptr; + } + if (value->next_ptr) { + value->next_ptr->prev_ptr = value->prev_ptr; + } else { + _data->last = value->prev_ptr; + } + + value->next_ptr = where; + if (!where) { + value->prev_ptr = _data->last; + _data->last = value; + return; + } + + value->prev_ptr = where->prev_ptr; + + if (where->prev_ptr) { + where->prev_ptr->next_ptr = value; + } else { + _data->first = value; + } + + where->prev_ptr = value; + } + + /** + * simple insertion sort + */ + + void sort() { + sort_custom<Comparator<T>>(); + } + + template <class C> + void sort_custom_inplace() { + if (size() < 2) { + return; + } + + Element *from = front(); + Element *current = from; + Element *to = from; + + while (current) { + Element *next = current->next_ptr; + + if (from != current) { + current->prev_ptr = nullptr; + current->next_ptr = from; + + Element *find = from; + C less; + while (find && less(find->value, current->value)) { + current->prev_ptr = find; + current->next_ptr = find->next_ptr; + find = find->next_ptr; + } + + if (current->prev_ptr) { + current->prev_ptr->next_ptr = current; + } else { + from = current; + } + + if (current->next_ptr) { + current->next_ptr->prev_ptr = current; + } else { + to = current; + } + } else { + current->prev_ptr = nullptr; + current->next_ptr = nullptr; + } + + current = next; + } + _data->first = from; + _data->last = to; + } + + template <class C> + struct AuxiliaryComparator { + C compare; + _FORCE_INLINE_ bool operator()(const Element *a, const Element *b) const { + return compare(a->value, b->value); + } + }; + + template <class C> + void sort_custom() { + //this version uses auxiliary memory for speed. + //if you don't want to use auxiliary memory, use the in_place version + + int s = size(); + if (s < 2) { + return; + } + + Element **aux_buffer = memnew_arr(Element *, s); + + int idx = 0; + for (Element *E = front(); E; E = E->next_ptr) { + aux_buffer[idx] = E; + idx++; + } + + SortArray<Element *, AuxiliaryComparator<C>> sort; + sort.sort(aux_buffer, s); + + _data->first = aux_buffer[0]; + aux_buffer[0]->prev_ptr = nullptr; + aux_buffer[0]->next_ptr = aux_buffer[1]; + + _data->last = aux_buffer[s - 1]; + aux_buffer[s - 1]->prev_ptr = aux_buffer[s - 2]; + aux_buffer[s - 1]->next_ptr = nullptr; + + for (int i = 1; i < s - 1; i++) { + aux_buffer[i]->prev_ptr = aux_buffer[i - 1]; + aux_buffer[i]->next_ptr = aux_buffer[i + 1]; + } + + memdelete_arr(aux_buffer); + } + + const void *id() const { + return (void *)_data; + } + + /** + * copy constructor for the list + */ + List(const List &p_list) { + const Element *it = p_list.front(); + while (it) { + push_back(it->get()); + it = it->next(); + } + } + + List() {} + + ~List() { + clear(); + if (_data) { + ERR_FAIL_COND(_data->size_cache); + memdelete_allocator<_Data, A>(_data); + } + } +}; + +#endif // LIST_H diff --git a/core/templates/local_vector.h b/core/templates/local_vector.h new file mode 100644 index 0000000000..4ef040dc77 --- /dev/null +++ b/core/templates/local_vector.h @@ -0,0 +1,246 @@ +/*************************************************************************/ +/* local_vector.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef LOCAL_VECTOR_H +#define LOCAL_VECTOR_H + +#include "core/error/error_macros.h" +#include "core/os/copymem.h" +#include "core/os/memory.h" +#include "core/templates/sort_array.h" +#include "core/templates/vector.h" + +template <class T, class U = uint32_t, bool force_trivial = false> +class LocalVector { +private: + U count = 0; + U capacity = 0; + T *data = nullptr; + +public: + T *ptr() { + return data; + } + + const T *ptr() const { + return data; + } + + _FORCE_INLINE_ void push_back(T p_elem) { + if (unlikely(count == capacity)) { + if (capacity == 0) { + capacity = 1; + } else { + capacity <<= 1; + } + data = (T *)memrealloc(data, capacity * sizeof(T)); + CRASH_COND_MSG(!data, "Out of memory"); + } + + if (!__has_trivial_constructor(T) && !force_trivial) { + memnew_placement(&data[count++], T(p_elem)); + } else { + data[count++] = p_elem; + } + } + + void remove(U p_index) { + ERR_FAIL_UNSIGNED_INDEX(p_index, count); + count--; + for (U i = p_index; i < count; i++) { + data[i] = data[i + 1]; + } + if (!__has_trivial_destructor(T) && !force_trivial) { + data[count].~T(); + } + } + + void erase(const T &p_val) { + int64_t idx = find(p_val); + if (idx >= 0) { + remove(idx); + } + } + + void invert() { + for (U i = 0; i < count / 2; i++) { + SWAP(data[i], data[count - i - 1]); + } + } + + _FORCE_INLINE_ void clear() { resize(0); } + _FORCE_INLINE_ void reset() { + clear(); + if (data) { + memfree(data); + data = nullptr; + capacity = 0; + } + } + _FORCE_INLINE_ bool empty() const { return count == 0; } + _FORCE_INLINE_ void reserve(U p_size) { + p_size = nearest_power_of_2_templated(p_size); + if (p_size > capacity) { + capacity = p_size; + data = (T *)memrealloc(data, capacity * sizeof(T)); + CRASH_COND_MSG(!data, "Out of memory"); + } + } + + _FORCE_INLINE_ U size() const { return count; } + void resize(U p_size) { + if (p_size < count) { + if (!__has_trivial_destructor(T) && !force_trivial) { + for (U i = p_size; i < count; i++) { + data[i].~T(); + } + } + count = p_size; + } else if (p_size > count) { + if (unlikely(p_size > capacity)) { + if (capacity == 0) { + capacity = 1; + } + while (capacity < p_size) { + capacity <<= 1; + } + data = (T *)memrealloc(data, capacity * sizeof(T)); + CRASH_COND_MSG(!data, "Out of memory"); + } + if (!__has_trivial_constructor(T) && !force_trivial) { + for (U i = count; i < p_size; i++) { + memnew_placement(&data[i], T); + } + } + count = p_size; + } + } + _FORCE_INLINE_ const T &operator[](U p_index) const { + CRASH_BAD_UNSIGNED_INDEX(p_index, count); + return data[p_index]; + } + _FORCE_INLINE_ T &operator[](U p_index) { + CRASH_BAD_UNSIGNED_INDEX(p_index, count); + return data[p_index]; + } + + void insert(U p_pos, T p_val) { + ERR_FAIL_UNSIGNED_INDEX(p_pos, count + 1); + if (p_pos == count) { + push_back(p_val); + } else { + resize(count + 1); + for (U i = count; i > p_pos; i--) { + data[i] = data[i - 1]; + } + data[p_pos] = p_val; + } + } + + int64_t find(const T &p_val, U p_from = 0) const { + for (U i = 0; i < count; i++) { + if (data[i] == p_val) { + return int64_t(i); + } + } + return -1; + } + + template <class C> + void sort_custom() { + U len = count; + if (len == 0) { + return; + } + + SortArray<T, C> sorter; + sorter.sort(data, len); + } + + void sort() { + sort_custom<_DefaultComparator<T>>(); + } + + void ordered_insert(T p_val) { + U i; + for (i = 0; i < count; i++) { + if (p_val < data[i]) { + break; + } + } + insert(i, p_val); + } + + operator Vector<T>() const { + Vector<T> ret; + ret.resize(size()); + T *w = ret.ptrw(); + copymem(w, data, sizeof(T) * count); + return ret; + } + + Vector<uint8_t> to_byte_array() const { //useful to pass stuff to gpu or variant + Vector<uint8_t> ret; + ret.resize(count * sizeof(T)); + uint8_t *w = ret.ptrw(); + copymem(w, data, sizeof(T) * count); + return ret; + } + + _FORCE_INLINE_ LocalVector() {} + _FORCE_INLINE_ LocalVector(const LocalVector &p_from) { + resize(p_from.size()); + for (U i = 0; i < p_from.count; i++) { + data[i] = p_from.data[i]; + } + } + inline LocalVector &operator=(const LocalVector &p_from) { + resize(p_from.size()); + for (U i = 0; i < p_from.count; i++) { + data[i] = p_from.data[i]; + } + return *this; + } + inline LocalVector &operator=(const Vector<T> &p_from) { + resize(p_from.size()); + for (U i = 0; i < count; i++) { + data[i] = p_from[i]; + } + return *this; + } + + _FORCE_INLINE_ ~LocalVector() { + if (data) { + reset(); + } + } +}; + +#endif // LOCAL_VECTOR_H diff --git a/core/templates/map.h b/core/templates/map.h new file mode 100644 index 0000000000..c454d69256 --- /dev/null +++ b/core/templates/map.h @@ -0,0 +1,668 @@ +/*************************************************************************/ +/* map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef MAP_H +#define MAP_H + +#include "core/error/error_macros.h" +#include "core/templates/set.h" + +// based on the very nice implementation of rb-trees by: +// https://web.archive.org/web/20120507164830/http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html + +template <class K, class V, class C = Comparator<K>, class A = DefaultAllocator> +class Map { + enum Color { + RED, + BLACK + }; + struct _Data; + +public: + class Element { + private: + friend class Map<K, V, C, A>; + int color = RED; + Element *right = nullptr; + Element *left = nullptr; + Element *parent = nullptr; + Element *_next = nullptr; + Element *_prev = nullptr; + K _key; + V _value; + //_Data *data; + + public: + const Element *next() const { + return _next; + } + Element *next() { + return _next; + } + const Element *prev() const { + return _prev; + } + Element *prev() { + return _prev; + } + const K &key() const { + return _key; + } + V &value() { + return _value; + } + const V &value() const { + return _value; + } + V &get() { + return _value; + } + const V &get() const { + return _value; + } + Element() {} + }; + +private: + struct _Data { + Element *_root = nullptr; + Element *_nil; + int size_cache = 0; + + _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 + } + + void _create_root() { + _root = memnew_allocator(Element, A); + _root->parent = _root->left = _root->right = _nil; + _root->color = BLACK; + } + + void _free_root() { + if (_root) { + memdelete_allocator<Element, A>(_root); + _root = nullptr; + } + } + + ~_Data() { + _free_root(); + +#ifdef GLOBALNIL_DISABLED + memdelete_allocator<Element, A>(_nil); +#endif + } + }; + + _Data _data; + + inline void _set_color(Element *p_node, int p_color) { + 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; + p_node->right = r->left; + if (r->left != _data._nil) { + r->left->parent = p_node; + } + r->parent = p_node->parent; + if (p_node == p_node->parent->left) { + p_node->parent->left = r; + } else { + p_node->parent->right = r; + } + + r->left = p_node; + p_node->parent = r; + } + + inline void _rotate_right(Element *p_node) { + Element *l = p_node->left; + p_node->left = l->right; + if (l->right != _data._nil) { + l->right->parent = p_node; + } + l->parent = p_node->parent; + if (p_node == p_node->parent->right) { + p_node->parent->right = l; + } else { + p_node->parent->left = l; + } + + l->right = p_node; + p_node->parent = l; + } + + inline Element *_successor(Element *p_node) const { + Element *node = p_node; + + if (node->right != _data._nil) { + node = node->right; + while (node->left != _data._nil) { /* returns the minimum of the right subtree of node */ + node = node->left; + } + return node; + } else { + while (node == node->parent->right) { + node = node->parent; + } + + if (node->parent == _data._root) { + return nullptr; // No successor, as p_node = last node + } + return node->parent; + } + } + + inline Element *_predecessor(Element *p_node) const { + Element *node = p_node; + + if (node->left != _data._nil) { + node = node->left; + while (node->right != _data._nil) { /* returns the minimum of the left subtree of node */ + node = node->right; + } + return node; + } else { + while (node == node->parent->left) { + node = node->parent; + } + + if (node == _data._root) { + return nullptr; // No predecessor, as p_node = first node + } + return node->parent; + } + } + + Element *_find(const K &p_key) const { + Element *node = _data._root->left; + 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 { + return node; // found + } + } + + return nullptr; + } + + Element *_find_closest(const K &p_key) const { + Element *node = _data._root->left; + Element *prev = nullptr; + C less; + + while (node != _data._nil) { + prev = node; + + if (less(p_key, node->_key)) { + node = node->left; + } else if (less(node->_key, p_key)) { + node = node->right; + } else { + return node; // found + } + } + + if (prev == nullptr) { + return nullptr; // tree empty + } + + if (less(p_key, prev->_key)) { + prev = prev->_prev; + } + + return prev; + } + + 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, const V &p_value) { + Element *new_parent = _data._root; + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + new_parent = node; + + if (less(p_key, node->_key)) { + node = node->left; + } else if (less(node->_key, p_key)) { + node = node->right; + } else { + 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)) { + 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_rb(Element *p_node) { + Element *root = _data._root->left; + 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 { + sibling = sibling->right; + _rotate_right(parent); + } + } + 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; + } + } 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 (sibling->left->color == BLACK) { + _set_color(sibling->right, BLACK); + _set_color(sibling, RED); + _rotate_left(sibling); + sibling = sibling->parent; + } + + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->left, BLACK); + _rotate_right(parent); + break; + } + } + } + + 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 : p_node->_next; + Element *node = (rp->left == _data._nil) ? rp->right : rp->left; + + Element *sibling; + if (rp == rp->parent->left) { + rp->parent->left = node; + sibling = rp->parent->right; + } else { + 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); + + rp->left = p_node->left; + rp->right = p_node->right; + rp->parent = p_node->parent; + rp->color = p_node->color; + 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; + } + } + + if (p_node->_next) { + p_node->_next->_prev = p_node->_prev; + } + if (p_node->_prev) { + p_node->_prev->_next = p_node->_next; + } + + memdelete_allocator<Element, A>(p_node); + _data.size_cache--; + ERR_FAIL_COND(_data._nil->color == RED); + } + + void _calculate_depth(Element *p_element, int &max_d, int d) const { + 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; + } + } + + void _cleanup_tree(Element *p_element) { + if (p_element == _data._nil) { + return; + } + + _cleanup_tree(p_element->left); + _cleanup_tree(p_element->right); + memdelete_allocator<Element, A>(p_element); + } + + void _copy_from(const Map &p_map) { + clear(); + // not the fastest way, but safeset to write. + for (Element *I = p_map.front(); I; I = I->next()) { + insert(I->key(), I->value()); + } + } + +public: + const Element *find(const K &p_key) const { + if (!_data._root) { + return nullptr; + } + + const Element *res = _find(p_key); + return res; + } + + Element *find(const K &p_key) { + if (!_data._root) { + return nullptr; + } + + Element *res = _find(p_key); + return res; + } + + const Element *find_closest(const K &p_key) const { + if (!_data._root) { + return nullptr; + } + + const Element *res = _find_closest(p_key); + return res; + } + + Element *find_closest(const K &p_key) { + if (!_data._root) { + return nullptr; + } + + Element *res = _find_closest(p_key); + return res; + } + + bool has(const K &p_key) const { + return find(p_key) != nullptr; + } + + Element *insert(const K &p_key, const V &p_value) { + if (!_data._root) { + _data._create_root(); + } + return _insert(p_key, p_value); + } + + void erase(Element *p_element) { + if (!_data._root || !p_element) { + return; + } + + _erase(p_element); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + } + + bool erase(const K &p_key) { + 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; + } + + const V &operator[](const K &p_key) const { + CRASH_COND(!_data._root); + const Element *e = find(p_key); + CRASH_COND(!e); + return e->_value; + } + + V &operator[](const K &p_key) { + if (!_data._root) { + _data._create_root(); + } + + Element *e = find(p_key); + if (!e) { + e = insert(p_key, V()); + } + + return e->_value; + } + + Element *front() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->left != _data._nil) { + e = e->left; + } + + return e; + } + + Element *back() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->right != _data._nil) { + e = e->right; + } + + return e; + } + + 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; + } + + void clear() { + if (!_data._root) { + return; + } + + _cleanup_tree(_data._root->left); + _data._root->left = _data._nil; + _data.size_cache = 0; + _data._free_root(); + } + + void operator=(const Map &p_map) { + _copy_from(p_map); + } + + Map(const Map &p_map) { + _copy_from(p_map); + } + + _FORCE_INLINE_ Map() {} + + ~Map() { + clear(); + } +}; + +#endif // MAP_H diff --git a/core/templates/oa_hash_map.h b/core/templates/oa_hash_map.h new file mode 100644 index 0000000000..d9d632b4ce --- /dev/null +++ b/core/templates/oa_hash_map.h @@ -0,0 +1,399 @@ +/*************************************************************************/ +/* oa_hash_map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef OA_HASH_MAP_H +#define OA_HASH_MAP_H + +#include "core/math/math_funcs.h" +#include "core/os/copymem.h" +#include "core/os/memory.h" +#include "core/templates/hashfuncs.h" + +/** + * A HashMap implementation that uses open addressing with Robin Hood hashing. + * Robin Hood hashing swaps out entries that have a smaller probing distance + * than the to-be-inserted entry, that evens out the average probing distance + * and enables faster lookups. Backward shift deletion is employed to further + * improve the performance and to avoid infinite loops in rare cases. + * + * The entries are stored inplace, so huge keys or values might fill cache lines + * a lot faster. + * + * Only used keys and values are constructed. For free positions there's space + * in the arrays for each, but that memory is kept uninitialized. + * + * The assignment operator copy the pairs from one map to the other. + */ +template <class TKey, class TValue, + class Hasher = HashMapHasherDefault, + class Comparator = HashMapComparatorDefault<TKey>> +class OAHashMap { +private: + TValue *values = nullptr; + TKey *keys = nullptr; + uint32_t *hashes = nullptr; + + uint32_t capacity = 0; + + uint32_t num_elements = 0; + + static const uint32_t EMPTY_HASH = 0; + + _FORCE_INLINE_ uint32_t _hash(const TKey &p_key) const { + uint32_t hash = Hasher::hash(p_key); + + if (hash == EMPTY_HASH) { + hash = EMPTY_HASH + 1; + } + + return hash; + } + + _FORCE_INLINE_ uint32_t _get_probe_length(uint32_t p_pos, uint32_t p_hash) const { + uint32_t original_pos = p_hash % capacity; + return (p_pos - original_pos + capacity) % capacity; + } + + _FORCE_INLINE_ void _construct(uint32_t p_pos, uint32_t p_hash, const TKey &p_key, const TValue &p_value) { + memnew_placement(&keys[p_pos], TKey(p_key)); + memnew_placement(&values[p_pos], TValue(p_value)); + hashes[p_pos] = p_hash; + + num_elements++; + } + + bool _lookup_pos(const TKey &p_key, uint32_t &r_pos) const { + uint32_t hash = _hash(p_key); + uint32_t pos = hash % capacity; + uint32_t distance = 0; + + while (true) { + if (hashes[pos] == EMPTY_HASH) { + return false; + } + + if (distance > _get_probe_length(pos, hashes[pos])) { + return false; + } + + if (hashes[pos] == hash && Comparator::compare(keys[pos], p_key)) { + r_pos = pos; + return true; + } + + pos = (pos + 1) % capacity; + distance++; + } + } + + void _insert_with_hash(uint32_t p_hash, const TKey &p_key, const TValue &p_value) { + uint32_t hash = p_hash; + uint32_t distance = 0; + uint32_t pos = hash % capacity; + + TKey key = p_key; + TValue value = p_value; + + while (true) { + if (hashes[pos] == EMPTY_HASH) { + _construct(pos, hash, key, value); + + return; + } + + // not an empty slot, let's check the probing length of the existing one + uint32_t existing_probe_len = _get_probe_length(pos, hashes[pos]); + if (existing_probe_len < distance) { + SWAP(hash, hashes[pos]); + SWAP(key, keys[pos]); + SWAP(value, values[pos]); + distance = existing_probe_len; + } + + pos = (pos + 1) % capacity; + distance++; + } + } + + void _resize_and_rehash(uint32_t p_new_capacity) { + uint32_t old_capacity = capacity; + + // Capacity can't be 0. + capacity = MAX(1, p_new_capacity); + + TKey *old_keys = keys; + TValue *old_values = values; + uint32_t *old_hashes = hashes; + + num_elements = 0; + keys = static_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity)); + values = static_cast<TValue *>(Memory::alloc_static(sizeof(TValue) * capacity)); + hashes = static_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity)); + + for (uint32_t i = 0; i < capacity; i++) { + hashes[i] = 0; + } + + if (old_capacity == 0) { + // Nothing to do. + return; + } + + for (uint32_t i = 0; i < old_capacity; i++) { + if (old_hashes[i] == EMPTY_HASH) { + continue; + } + + _insert_with_hash(old_hashes[i], old_keys[i], old_values[i]); + + old_keys[i].~TKey(); + old_values[i].~TValue(); + } + + Memory::free_static(old_keys); + Memory::free_static(old_values); + Memory::free_static(old_hashes); + } + + void _resize_and_rehash() { + _resize_and_rehash(capacity * 2); + } + +public: + _FORCE_INLINE_ uint32_t get_capacity() const { return capacity; } + _FORCE_INLINE_ uint32_t get_num_elements() const { return num_elements; } + + bool empty() const { + return num_elements == 0; + } + + void clear() { + for (uint32_t i = 0; i < capacity; i++) { + if (hashes[i] == EMPTY_HASH) { + continue; + } + + hashes[i] = EMPTY_HASH; + values[i].~TValue(); + keys[i].~TKey(); + } + + num_elements = 0; + } + + void insert(const TKey &p_key, const TValue &p_value) { + if (num_elements + 1 > 0.9 * capacity) { + _resize_and_rehash(); + } + + uint32_t hash = _hash(p_key); + + _insert_with_hash(hash, p_key, p_value); + } + + void set(const TKey &p_key, const TValue &p_data) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + + if (exists) { + values[pos] = p_data; + } else { + insert(p_key, p_data); + } + } + + /** + * returns true if the value was found, false otherwise. + * + * if r_data is not nullptr then the value will be written to the object + * it points to. + */ + bool lookup(const TKey &p_key, TValue &r_data) const { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + + if (exists) { + r_data = values[pos]; + return true; + } + + return false; + } + + /** + * returns true if the value was found, false otherwise. + * + * if r_data is not nullptr then the value will be written to the object + * it points to. + */ + TValue *lookup_ptr(const TKey &p_key) const { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + + if (exists) { + return &values[pos]; + } + return nullptr; + } + + _FORCE_INLINE_ bool has(const TKey &p_key) const { + uint32_t _pos = 0; + return _lookup_pos(p_key, _pos); + } + + void remove(const TKey &p_key) { + uint32_t pos = 0; + bool exists = _lookup_pos(p_key, pos); + + if (!exists) { + return; + } + + uint32_t next_pos = (pos + 1) % capacity; + while (hashes[next_pos] != EMPTY_HASH && + _get_probe_length(next_pos, hashes[next_pos]) != 0) { + SWAP(hashes[next_pos], hashes[pos]); + SWAP(keys[next_pos], keys[pos]); + SWAP(values[next_pos], values[pos]); + pos = next_pos; + next_pos = (pos + 1) % capacity; + } + + hashes[pos] = EMPTY_HASH; + values[pos].~TValue(); + keys[pos].~TKey(); + + num_elements--; + } + + /** + * reserves space for a number of elements, useful to avoid many resizes and rehashes + * if adding a known (possibly large) number of elements at once, must be larger than old + * capacity. + **/ + void reserve(uint32_t p_new_capacity) { + ERR_FAIL_COND(p_new_capacity < capacity); + _resize_and_rehash(p_new_capacity); + } + + struct Iterator { + bool valid; + + const TKey *key; + TValue *value; + + private: + uint32_t pos; + friend class OAHashMap; + }; + + Iterator iter() const { + Iterator it; + + it.valid = true; + it.pos = 0; + + return next_iter(it); + } + + Iterator next_iter(const Iterator &p_iter) const { + if (!p_iter.valid) { + return p_iter; + } + + Iterator it; + it.valid = false; + it.pos = p_iter.pos; + it.key = nullptr; + it.value = nullptr; + + for (uint32_t i = it.pos; i < capacity; i++) { + it.pos = i + 1; + + if (hashes[i] == EMPTY_HASH) { + continue; + } + + it.valid = true; + it.key = &keys[i]; + it.value = &values[i]; + return it; + } + + return it; + } + + OAHashMap(const OAHashMap &p_other) { + (*this) = p_other; + } + + OAHashMap &operator=(const OAHashMap &p_other) { + if (capacity != 0) { + clear(); + } + + _resize_and_rehash(p_other.capacity); + + for (Iterator it = p_other.iter(); it.valid; it = p_other.next_iter(it)) { + set(*it.key, *it.value); + } + return *this; + } + + OAHashMap(uint32_t p_initial_capacity = 64) { + // Capacity can't be 0. + capacity = MAX(1, p_initial_capacity); + + keys = static_cast<TKey *>(Memory::alloc_static(sizeof(TKey) * capacity)); + values = static_cast<TValue *>(Memory::alloc_static(sizeof(TValue) * capacity)); + hashes = static_cast<uint32_t *>(Memory::alloc_static(sizeof(uint32_t) * capacity)); + + for (uint32_t i = 0; i < capacity; i++) { + hashes[i] = EMPTY_HASH; + } + } + + ~OAHashMap() { + for (uint32_t i = 0; i < capacity; i++) { + if (hashes[i] == EMPTY_HASH) { + continue; + } + + values[i].~TValue(); + keys[i].~TKey(); + } + + Memory::free_static(keys); + Memory::free_static(values); + Memory::free_static(hashes); + } +}; + +#endif // OA_HASH_MAP_H diff --git a/core/templates/ordered_hash_map.h b/core/templates/ordered_hash_map.h new file mode 100644 index 0000000000..9398868b01 --- /dev/null +++ b/core/templates/ordered_hash_map.h @@ -0,0 +1,299 @@ +/*************************************************************************/ +/* ordered_hash_map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef ORDERED_HASH_MAP_H +#define ORDERED_HASH_MAP_H + +#include "core/templates/hash_map.h" +#include "core/templates/list.h" +#include "core/templates/pair.h" + +/** + * A hash map which allows to iterate elements in insertion order. + * Insertion, lookup, deletion have O(1) complexity. + * The API aims to be consistent with Map rather than HashMap, because the + * former is more frequently used and is more coherent with the rest of the + * codebase. + * Deletion during iteration is safe and will preserve the order. + */ +template <class K, class V, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<K>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> +class OrderedHashMap { + typedef List<Pair<const K *, V>> InternalList; + typedef HashMap<K, typename InternalList::Element *, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP> InternalMap; + + InternalList list; + InternalMap map; + +public: + class Element { + friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; + + typename InternalList::Element *list_element = nullptr; + typename InternalList::Element *prev_element = nullptr; + typename InternalList::Element *next_element = nullptr; + + Element(typename InternalList::Element *p_element) { + list_element = p_element; + + if (list_element) { + next_element = list_element->next(); + prev_element = list_element->prev(); + } + } + + public: + _FORCE_INLINE_ Element() {} + + Element next() const { + return Element(next_element); + } + + Element prev() const { + return Element(prev_element); + } + + Element(const Element &other) : + list_element(other.list_element), + prev_element(other.prev_element), + next_element(other.next_element) { + } + + Element &operator=(const Element &other) { + list_element = other.list_element; + next_element = other.next_element; + prev_element = other.prev_element; + return *this; + } + + _FORCE_INLINE_ bool operator==(const Element &p_other) const { + return this->list_element == p_other.list_element; + } + _FORCE_INLINE_ bool operator!=(const Element &p_other) const { + return this->list_element != p_other.list_element; + } + + operator bool() const { + return (list_element != nullptr); + } + + const K &key() const { + CRASH_COND(!list_element); + return *(list_element->get().first); + } + + V &value() { + CRASH_COND(!list_element); + return list_element->get().second; + } + + const V &value() const { + CRASH_COND(!list_element); + return list_element->get().second; + } + + V &get() { + CRASH_COND(!list_element); + return list_element->get().second; + } + + const V &get() const { + CRASH_COND(!list_element); + return list_element->get().second; + } + }; + + class ConstElement { + friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; + + const typename InternalList::Element *list_element = nullptr; + + ConstElement(const typename InternalList::Element *p_element) : + list_element(p_element) { + } + + public: + _FORCE_INLINE_ ConstElement() {} + + ConstElement(const ConstElement &other) : + list_element(other.list_element) { + } + + ConstElement &operator=(const ConstElement &other) { + list_element = other.list_element; + return *this; + } + + ConstElement next() const { + return ConstElement(list_element ? list_element->next() : nullptr); + } + + ConstElement prev() const { + return ConstElement(list_element ? list_element->prev() : nullptr); + } + + _FORCE_INLINE_ bool operator==(const ConstElement &p_other) const { + return this->list_element == p_other.list_element; + } + _FORCE_INLINE_ bool operator!=(const ConstElement &p_other) const { + return this->list_element != p_other.list_element; + } + + operator bool() const { + return (list_element != nullptr); + } + + const K &key() const { + CRASH_COND(!list_element); + return *(list_element->get().first); + } + + const V &value() const { + CRASH_COND(!list_element); + return list_element->get().second; + } + + const V &get() const { + CRASH_COND(!list_element); + return list_element->get().second; + } + }; + + ConstElement find(const K &p_key) const { + typename InternalList::Element *const *list_element = map.getptr(p_key); + if (list_element) { + return ConstElement(*list_element); + } + return ConstElement(nullptr); + } + + Element find(const K &p_key) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + return Element(*list_element); + } + return Element(nullptr); + } + + Element insert(const K &p_key, const V &p_value) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + (*list_element)->get().second = p_value; + return Element(*list_element); + } + typename InternalList::Element *new_element = list.push_back(Pair<const K *, V>(nullptr, p_value)); + typename InternalMap::Element *e = map.set(p_key, new_element); + new_element->get().first = &e->key(); + + return Element(new_element); + } + + void erase(Element &p_element) { + map.erase(p_element.key()); + list.erase(p_element.list_element); + p_element.list_element = nullptr; + } + + bool erase(const K &p_key) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + list.erase(*list_element); + map.erase(p_key); + return true; + } + return false; + } + + inline bool has(const K &p_key) const { + return map.has(p_key); + } + + const V &operator[](const K &p_key) const { + ConstElement e = find(p_key); + CRASH_COND(!e); + return e.value(); + } + + V &operator[](const K &p_key) { + Element e = find(p_key); + if (!e) { + // consistent with Map behaviour + e = insert(p_key, V()); + } + return e.value(); + } + + inline Element front() { + return Element(list.front()); + } + + inline Element back() { + return Element(list.back()); + } + + inline ConstElement front() const { + return ConstElement(list.front()); + } + + inline ConstElement back() const { + return ConstElement(list.back()); + } + + inline bool empty() const { return list.empty(); } + inline int size() const { return list.size(); } + + const void *id() const { + return list.id(); + } + + void clear() { + map.clear(); + list.clear(); + } + +private: + void _copy_from(const OrderedHashMap &p_map) { + for (ConstElement E = p_map.front(); E; E = E.next()) { + insert(E.key(), E.value()); + } + } + +public: + void operator=(const OrderedHashMap &p_map) { + _copy_from(p_map); + } + + OrderedHashMap(const OrderedHashMap &p_map) { + _copy_from(p_map); + } + + _FORCE_INLINE_ OrderedHashMap() {} +}; + +#endif // ORDERED_HASH_MAP_H diff --git a/core/templates/pair.h b/core/templates/pair.h new file mode 100644 index 0000000000..89ea2b9fd9 --- /dev/null +++ b/core/templates/pair.h @@ -0,0 +1,67 @@ +/*************************************************************************/ +/* pair.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef PAIR_H +#define PAIR_H + +template <class F, class S> +struct Pair { + F first; + S second; + + Pair() : + first(), + second() { + } + + Pair(F p_first, const S &p_second) : + first(p_first), + second(p_second) { + } +}; + +template <class F, class S> +bool operator==(const Pair<F, S> &pair, const Pair<F, S> &other) { + return (pair.first == other.first) && (pair.second == other.second); +} + +template <class F, class S> +bool operator!=(const Pair<F, S> &pair, const Pair<F, S> &other) { + return (pair.first != other.first) || (pair.second != other.second); +} + +template <class F, class S> +struct PairSort { + bool operator()(const Pair<F, S> &A, const Pair<F, S> &B) const { + return A.first < B.first; + } +}; + +#endif // PAIR_H diff --git a/core/templates/rid.h b/core/templates/rid.h new file mode 100644 index 0000000000..a475d166d5 --- /dev/null +++ b/core/templates/rid.h @@ -0,0 +1,69 @@ +/*************************************************************************/ +/* rid.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef RID_H +#define RID_H + +#include "core/typedefs.h" + +class RID_AllocBase; + +class RID { + friend class RID_AllocBase; + uint64_t _id = 0; + +public: + _FORCE_INLINE_ bool operator==(const RID &p_rid) const { + return _id == p_rid._id; + } + _FORCE_INLINE_ bool operator<(const RID &p_rid) const { + return _id < p_rid._id; + } + _FORCE_INLINE_ bool operator<=(const RID &p_rid) const { + return _id <= p_rid._id; + } + _FORCE_INLINE_ bool operator>(const RID &p_rid) const { + return _id > p_rid._id; + } + _FORCE_INLINE_ bool operator>=(const RID &p_rid) const { + return _id >= p_rid._id; + } + _FORCE_INLINE_ bool operator!=(const RID &p_rid) const { + return _id != p_rid._id; + } + _FORCE_INLINE_ bool is_valid() const { return _id != 0; } + _FORCE_INLINE_ bool is_null() const { return _id == 0; } + + _FORCE_INLINE_ uint64_t get_id() const { return _id; } + + _FORCE_INLINE_ RID() {} +}; + +#endif // RID_H diff --git a/core/templates/rid_owner.cpp b/core/templates/rid_owner.cpp new file mode 100644 index 0000000000..a5065f29f8 --- /dev/null +++ b/core/templates/rid_owner.cpp @@ -0,0 +1,33 @@ +/*************************************************************************/ +/* rid_owner.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#include "rid_owner.h" + +volatile uint64_t RID_AllocBase::base_id = 1; diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h new file mode 100644 index 0000000000..d1bcb92010 --- /dev/null +++ b/core/templates/rid_owner.h @@ -0,0 +1,404 @@ +/*************************************************************************/ +/* rid_owner.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef RID_OWNER_H +#define RID_OWNER_H + +#include "core/os/memory.h" +#include "core/os/spin_lock.h" +#include "core/string/print_string.h" +#include "core/templates/list.h" +#include "core/templates/oa_hash_map.h" +#include "core/templates/rid.h" +#include "core/templates/safe_refcount.h" +#include "core/templates/set.h" + +#include <stdio.h> +#include <typeinfo> + +class RID_AllocBase { + static volatile uint64_t base_id; + +protected: + static RID _make_from_id(uint64_t p_id) { + RID rid; + rid._id = p_id; + return rid; + } + + static uint64_t _gen_id() { + return atomic_increment(&base_id); + } + + static RID _gen_rid() { + return _make_from_id(_gen_id()); + } + +public: + virtual ~RID_AllocBase() {} +}; + +template <class T, bool THREAD_SAFE = false> +class RID_Alloc : public RID_AllocBase { + T **chunks = nullptr; + uint32_t **free_list_chunks = nullptr; + uint32_t **validator_chunks = nullptr; + + uint32_t elements_in_chunk; + uint32_t max_alloc = 0; + uint32_t alloc_count = 0; + + const char *description = nullptr; + + SpinLock spin_lock; + +public: + RID make_rid(const T &p_value) { + if (THREAD_SAFE) { + spin_lock.lock(); + } + + if (alloc_count == max_alloc) { + //allocate a new chunk + uint32_t chunk_count = alloc_count == 0 ? 0 : (max_alloc / elements_in_chunk); + + //grow chunks + chunks = (T **)memrealloc(chunks, sizeof(T *) * (chunk_count + 1)); + chunks[chunk_count] = (T *)memalloc(sizeof(T) * elements_in_chunk); //but don't initialize + + //grow validators + validator_chunks = (uint32_t **)memrealloc(validator_chunks, sizeof(uint32_t *) * (chunk_count + 1)); + validator_chunks[chunk_count] = (uint32_t *)memalloc(sizeof(uint32_t) * elements_in_chunk); + //grow free lists + free_list_chunks = (uint32_t **)memrealloc(free_list_chunks, sizeof(uint32_t *) * (chunk_count + 1)); + free_list_chunks[chunk_count] = (uint32_t *)memalloc(sizeof(uint32_t) * elements_in_chunk); + + //initialize + for (uint32_t i = 0; i < elements_in_chunk; i++) { + //dont initialize chunk + validator_chunks[chunk_count][i] = 0xFFFFFFFF; + free_list_chunks[chunk_count][i] = alloc_count + i; + } + + max_alloc += elements_in_chunk; + } + + uint32_t free_index = free_list_chunks[alloc_count / elements_in_chunk][alloc_count % elements_in_chunk]; + + uint32_t free_chunk = free_index / elements_in_chunk; + uint32_t free_element = free_index % elements_in_chunk; + + T *ptr = &chunks[free_chunk][free_element]; + memnew_placement(ptr, T(p_value)); + + uint32_t validator = (uint32_t)(_gen_id() & 0xFFFFFFFF); + uint64_t id = validator; + id <<= 32; + id |= free_index; + + validator_chunks[free_chunk][free_element] = validator; + alloc_count++; + + if (THREAD_SAFE) { + spin_lock.unlock(); + } + + return _make_from_id(id); + } + + _FORCE_INLINE_ T *getornull(const RID &p_rid) { + if (THREAD_SAFE) { + spin_lock.lock(); + } + + uint64_t id = p_rid.get_id(); + uint32_t idx = uint32_t(id & 0xFFFFFFFF); + if (unlikely(idx >= max_alloc)) { + if (THREAD_SAFE) { + spin_lock.unlock(); + } + return nullptr; + } + + uint32_t idx_chunk = idx / elements_in_chunk; + uint32_t idx_element = idx % elements_in_chunk; + + uint32_t validator = uint32_t(id >> 32); + if (unlikely(validator_chunks[idx_chunk][idx_element] != validator)) { + if (THREAD_SAFE) { + spin_lock.unlock(); + } + return nullptr; + } + + T *ptr = &chunks[idx_chunk][idx_element]; + + if (THREAD_SAFE) { + spin_lock.unlock(); + } + + return ptr; + } + + _FORCE_INLINE_ bool owns(const RID &p_rid) { + if (THREAD_SAFE) { + spin_lock.lock(); + } + + uint64_t id = p_rid.get_id(); + uint32_t idx = uint32_t(id & 0xFFFFFFFF); + if (unlikely(idx >= max_alloc)) { + if (THREAD_SAFE) { + spin_lock.unlock(); + } + return false; + } + + uint32_t idx_chunk = idx / elements_in_chunk; + uint32_t idx_element = idx % elements_in_chunk; + + uint32_t validator = uint32_t(id >> 32); + + bool owned = validator_chunks[idx_chunk][idx_element] == validator; + + if (THREAD_SAFE) { + spin_lock.unlock(); + } + + return owned; + } + + _FORCE_INLINE_ void free(const RID &p_rid) { + if (THREAD_SAFE) { + spin_lock.lock(); + } + + uint64_t id = p_rid.get_id(); + uint32_t idx = uint32_t(id & 0xFFFFFFFF); + if (unlikely(idx >= max_alloc)) { + if (THREAD_SAFE) { + spin_lock.unlock(); + } + ERR_FAIL(); + } + + uint32_t idx_chunk = idx / elements_in_chunk; + uint32_t idx_element = idx % elements_in_chunk; + + uint32_t validator = uint32_t(id >> 32); + if (unlikely(validator_chunks[idx_chunk][idx_element] != validator)) { + if (THREAD_SAFE) { + spin_lock.unlock(); + } + ERR_FAIL(); + } + + chunks[idx_chunk][idx_element].~T(); + validator_chunks[idx_chunk][idx_element] = 0xFFFFFFFF; // go invalid + + alloc_count--; + free_list_chunks[alloc_count / elements_in_chunk][alloc_count % elements_in_chunk] = idx; + + if (THREAD_SAFE) { + spin_lock.unlock(); + } + } + + _FORCE_INLINE_ uint32_t get_rid_count() const { + return alloc_count; + } + + _FORCE_INLINE_ T *get_ptr_by_index(uint32_t p_index) { + ERR_FAIL_UNSIGNED_INDEX_V(p_index, alloc_count, nullptr); + if (THREAD_SAFE) { + spin_lock.lock(); + } + uint64_t idx = free_list_chunks[p_index / elements_in_chunk][p_index % elements_in_chunk]; + T *ptr = &chunks[idx / elements_in_chunk][idx % elements_in_chunk]; + if (THREAD_SAFE) { + spin_lock.unlock(); + } + return ptr; + } + + _FORCE_INLINE_ RID get_rid_by_index(uint32_t p_index) { + ERR_FAIL_INDEX_V(p_index, alloc_count, RID()); + if (THREAD_SAFE) { + spin_lock.lock(); + } + uint64_t idx = free_list_chunks[p_index / elements_in_chunk][p_index % elements_in_chunk]; + uint64_t validator = validator_chunks[idx / elements_in_chunk][idx % elements_in_chunk]; + + RID rid = _make_from_id((validator << 32) | idx); + if (THREAD_SAFE) { + spin_lock.unlock(); + } + return rid; + } + + void get_owned_list(List<RID> *p_owned) { + if (THREAD_SAFE) { + spin_lock.lock(); + } + for (size_t i = 0; i < max_alloc; i++) { + uint64_t validator = validator_chunks[i / elements_in_chunk][i % elements_in_chunk]; + if (validator != 0xFFFFFFFF) { + p_owned->push_back(_make_from_id((validator << 32) | i)); + } + } + if (THREAD_SAFE) { + spin_lock.unlock(); + } + } + + void set_description(const char *p_descrption) { + description = p_descrption; + } + + RID_Alloc(uint32_t p_target_chunk_byte_size = 4096) { + elements_in_chunk = sizeof(T) > p_target_chunk_byte_size ? 1 : (p_target_chunk_byte_size / sizeof(T)); + } + + ~RID_Alloc() { + if (alloc_count) { + if (description) { + print_error("ERROR: " + itos(alloc_count) + " RID allocations of type '" + description + "' were leaked at exit."); + } else { +#ifdef NO_SAFE_CAST + print_error("ERROR: " + itos(alloc_count) + " RID allocations of type 'unknown' were leaked at exit."); +#else + print_error("ERROR: " + itos(alloc_count) + " RID allocations of type '" + typeid(T).name() + "' were leaked at exit."); +#endif + } + + for (size_t i = 0; i < max_alloc; i++) { + uint64_t validator = validator_chunks[i / elements_in_chunk][i % elements_in_chunk]; + if (validator != 0xFFFFFFFF) { + chunks[i / elements_in_chunk][i % elements_in_chunk].~T(); + } + } + } + + uint32_t chunk_count = max_alloc / elements_in_chunk; + for (uint32_t i = 0; i < chunk_count; i++) { + memfree(chunks[i]); + memfree(validator_chunks[i]); + memfree(free_list_chunks[i]); + } + + if (chunks) { + memfree(chunks); + memfree(free_list_chunks); + memfree(validator_chunks); + } + } +}; + +template <class T, bool THREAD_SAFE = false> +class RID_PtrOwner { + RID_Alloc<T *, THREAD_SAFE> alloc; + +public: + _FORCE_INLINE_ RID make_rid(T *p_ptr) { + return alloc.make_rid(p_ptr); + } + + _FORCE_INLINE_ T *getornull(const RID &p_rid) { + T **ptr = alloc.getornull(p_rid); + if (unlikely(!ptr)) { + return nullptr; + } + return *ptr; + } + + _FORCE_INLINE_ bool owns(const RID &p_rid) { + return alloc.owns(p_rid); + } + + _FORCE_INLINE_ void free(const RID &p_rid) { + alloc.free(p_rid); + } + + _FORCE_INLINE_ void get_owned_list(List<RID> *p_owned) { + return alloc.get_owned_list(p_owned); + } + + void set_description(const char *p_descrption) { + alloc.set_description(p_descrption); + } + RID_PtrOwner(uint32_t p_target_chunk_byte_size = 4096) : + alloc(p_target_chunk_byte_size) {} +}; + +template <class T, bool THREAD_SAFE = false> +class RID_Owner { + RID_Alloc<T, THREAD_SAFE> alloc; + +public: + _FORCE_INLINE_ RID make_rid(const T &p_ptr) { + return alloc.make_rid(p_ptr); + } + + _FORCE_INLINE_ T *getornull(const RID &p_rid) { + return alloc.getornull(p_rid); + } + + _FORCE_INLINE_ bool owns(const RID &p_rid) { + return alloc.owns(p_rid); + } + + _FORCE_INLINE_ void free(const RID &p_rid) { + alloc.free(p_rid); + } + + _FORCE_INLINE_ uint32_t get_rid_count() const { + return alloc.get_rid_count(); + } + + _FORCE_INLINE_ RID get_rid_by_index(uint32_t p_index) { + return alloc.get_rid_by_index(p_index); + } + + _FORCE_INLINE_ T *get_ptr_by_index(uint32_t p_index) { + return alloc.get_ptr_by_index(p_index); + } + + _FORCE_INLINE_ void get_owned_list(List<RID> *p_owned) { + return alloc.get_owned_list(p_owned); + } + + void set_description(const char *p_descrption) { + alloc.set_description(p_descrption); + } + RID_Owner(uint32_t p_target_chunk_byte_size = 4096) : + alloc(p_target_chunk_byte_size) {} +}; + +#endif // RID_OWNER_H diff --git a/core/templates/ring_buffer.h b/core/templates/ring_buffer.h new file mode 100644 index 0000000000..12ec047fb6 --- /dev/null +++ b/core/templates/ring_buffer.h @@ -0,0 +1,220 @@ +/*************************************************************************/ +/* ring_buffer.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef RING_BUFFER_H +#define RING_BUFFER_H + +#include "core/templates/vector.h" + +template <typename T> +class RingBuffer { + Vector<T> data; + int read_pos = 0; + int write_pos = 0; + int size_mask; + + inline int inc(int &p_var, int p_size) const { + int ret = p_var; + p_var += p_size; + p_var = p_var & size_mask; + return ret; + } + +public: + T read() { + ERR_FAIL_COND_V(space_left() < 1, T()); + return data.ptr()[inc(read_pos, 1)]; + } + + int read(T *p_buf, int p_size, bool p_advance = true) { + int left = data_left(); + p_size = MIN(left, p_size); + int pos = read_pos; + int to_read = p_size; + int dst = 0; + while (to_read) { + int end = pos + to_read; + end = MIN(end, size()); + int total = end - pos; + const T *read = data.ptr(); + for (int i = 0; i < total; i++) { + p_buf[dst++] = read[pos + i]; + } + to_read -= total; + pos = 0; + } + if (p_advance) { + inc(read_pos, p_size); + } + return p_size; + } + + int copy(T *p_buf, int p_offset, int p_size) const { + int left = data_left(); + if ((p_offset + p_size) > left) { + p_size -= left - p_offset; + if (p_size <= 0) { + return 0; + } + } + p_size = MIN(left, p_size); + int pos = read_pos; + inc(pos, p_offset); + int to_read = p_size; + int dst = 0; + while (to_read) { + int end = pos + to_read; + end = MIN(end, size()); + int total = end - pos; + for (int i = 0; i < total; i++) { + p_buf[dst++] = data[pos + i]; + } + to_read -= total; + pos = 0; + } + return p_size; + } + + int find(const T &t, int p_offset, int p_max_size) const { + int left = data_left(); + if ((p_offset + p_max_size) > left) { + p_max_size -= left - p_offset; + if (p_max_size <= 0) { + return 0; + } + } + p_max_size = MIN(left, p_max_size); + int pos = read_pos; + inc(pos, p_offset); + int to_read = p_max_size; + while (to_read) { + int end = pos + to_read; + end = MIN(end, size()); + int total = end - pos; + for (int i = 0; i < total; i++) { + if (data[pos + i] == t) { + return i + (p_max_size - to_read); + } + } + to_read -= total; + pos = 0; + } + return -1; + } + + inline int advance_read(int p_n) { + p_n = MIN(p_n, data_left()); + inc(read_pos, p_n); + return p_n; + } + + inline int decrease_write(int p_n) { + p_n = MIN(p_n, data_left()); + inc(write_pos, size_mask + 1 - p_n); + return p_n; + } + + Error write(const T &p_v) { + ERR_FAIL_COND_V(space_left() < 1, FAILED); + data.write[inc(write_pos, 1)] = p_v; + return OK; + } + + int write(const T *p_buf, int p_size) { + int left = space_left(); + p_size = MIN(left, p_size); + + int pos = write_pos; + int to_write = p_size; + int src = 0; + while (to_write) { + int end = pos + to_write; + end = MIN(end, size()); + int total = end - pos; + + for (int i = 0; i < total; i++) { + data.write[pos + i] = p_buf[src++]; + } + to_write -= total; + pos = 0; + } + + inc(write_pos, p_size); + return p_size; + } + + inline int space_left() const { + int left = read_pos - write_pos; + if (left < 0) { + return size() + left - 1; + } + if (left == 0) { + return size() - 1; + } + return left - 1; + } + inline int data_left() const { + return size() - space_left() - 1; + } + + inline int size() const { + return data.size(); + } + + inline void clear() { + read_pos = 0; + write_pos = 0; + } + + void resize(int p_power) { + int old_size = size(); + int new_size = 1 << p_power; + int mask = new_size - 1; + data.resize(1 << p_power); + if (old_size < new_size && read_pos > write_pos) { + for (int i = 0; i < write_pos; i++) { + data.write[(old_size + i) & mask] = data[i]; + } + write_pos = (old_size + write_pos) & mask; + } else { + read_pos = read_pos & mask; + write_pos = write_pos & mask; + } + + size_mask = mask; + } + + RingBuffer<T>(int p_power = 0) { + resize(p_power); + } + ~RingBuffer<T>() {} +}; + +#endif // RING_BUFFER_H diff --git a/core/templates/safe_refcount.cpp b/core/templates/safe_refcount.cpp new file mode 100644 index 0000000000..d5ee778ef7 --- /dev/null +++ b/core/templates/safe_refcount.cpp @@ -0,0 +1,161 @@ +/*************************************************************************/ +/* safe_refcount.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* 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" + +#if defined(_MSC_VER) + +/* Implementation for MSVC-Windows */ + +// don't pollute my namespace! +#include <windows.h> + +#define ATOMIC_CONDITIONAL_INCREMENT_BODY(m_pw, m_win_type, m_win_cmpxchg, m_cpp_type) \ + /* try to increment until it actually works */ \ + /* taken from boost */ \ + while (true) { \ + m_cpp_type tmp = static_cast<m_cpp_type const volatile &>(*(m_pw)); \ + if (tmp == 0) { \ + return 0; /* if zero, can't add to it anymore */ \ + } \ + if (m_win_cmpxchg((m_win_type volatile *)(m_pw), tmp + 1, tmp) == tmp) { \ + return tmp + 1; \ + } \ + } + +#define ATOMIC_EXCHANGE_IF_GREATER_BODY(m_pw, m_val, m_win_type, m_win_cmpxchg, m_cpp_type) \ + while (true) { \ + m_cpp_type tmp = static_cast<m_cpp_type const volatile &>(*(m_pw)); \ + if (tmp >= m_val) { \ + return tmp; /* already greater, or equal */ \ + } \ + if (m_win_cmpxchg((m_win_type volatile *)(m_pw), m_val, tmp) == tmp) { \ + return m_val; \ + } \ + } + +_ALWAYS_INLINE_ uint32_t _atomic_conditional_increment_impl(volatile uint32_t *pw) { + ATOMIC_CONDITIONAL_INCREMENT_BODY(pw, LONG, InterlockedCompareExchange, uint32_t); +} + +_ALWAYS_INLINE_ uint32_t _atomic_decrement_impl(volatile uint32_t *pw) { + return InterlockedDecrement((LONG volatile *)pw); +} + +_ALWAYS_INLINE_ uint32_t _atomic_increment_impl(volatile uint32_t *pw) { + return InterlockedIncrement((LONG volatile *)pw); +} + +_ALWAYS_INLINE_ uint32_t _atomic_sub_impl(volatile uint32_t *pw, volatile uint32_t val) { + return InterlockedExchangeAdd((LONG volatile *)pw, -(int32_t)val) - val; +} + +_ALWAYS_INLINE_ uint32_t _atomic_add_impl(volatile uint32_t *pw, volatile uint32_t val) { + return InterlockedAdd((LONG volatile *)pw, val); +} + +_ALWAYS_INLINE_ uint32_t _atomic_exchange_if_greater_impl(volatile uint32_t *pw, volatile uint32_t val) { + ATOMIC_EXCHANGE_IF_GREATER_BODY(pw, val, LONG, InterlockedCompareExchange, uint32_t); +} + +_ALWAYS_INLINE_ uint64_t _atomic_conditional_increment_impl(volatile uint64_t *pw) { + ATOMIC_CONDITIONAL_INCREMENT_BODY(pw, LONGLONG, InterlockedCompareExchange64, uint64_t); +} + +_ALWAYS_INLINE_ uint64_t _atomic_decrement_impl(volatile uint64_t *pw) { + return InterlockedDecrement64((LONGLONG volatile *)pw); +} + +_ALWAYS_INLINE_ uint64_t _atomic_increment_impl(volatile uint64_t *pw) { + return InterlockedIncrement64((LONGLONG volatile *)pw); +} + +_ALWAYS_INLINE_ uint64_t _atomic_sub_impl(volatile uint64_t *pw, volatile uint64_t val) { + return InterlockedExchangeAdd64((LONGLONG volatile *)pw, -(int64_t)val) - val; +} + +_ALWAYS_INLINE_ uint64_t _atomic_add_impl(volatile uint64_t *pw, volatile uint64_t val) { + return InterlockedAdd64((LONGLONG volatile *)pw, val); +} + +_ALWAYS_INLINE_ uint64_t _atomic_exchange_if_greater_impl(volatile uint64_t *pw, volatile uint64_t val) { + ATOMIC_EXCHANGE_IF_GREATER_BODY(pw, val, LONGLONG, InterlockedCompareExchange64, uint64_t); +} + +// The actual advertised functions; they'll call the right implementation + +uint32_t atomic_conditional_increment(volatile uint32_t *pw) { + return _atomic_conditional_increment_impl(pw); +} + +uint32_t atomic_decrement(volatile uint32_t *pw) { + return _atomic_decrement_impl(pw); +} + +uint32_t atomic_increment(volatile uint32_t *pw) { + return _atomic_increment_impl(pw); +} + +uint32_t atomic_sub(volatile uint32_t *pw, volatile uint32_t val) { + return _atomic_sub_impl(pw, val); +} + +uint32_t atomic_add(volatile uint32_t *pw, volatile uint32_t val) { + return _atomic_add_impl(pw, val); +} + +uint32_t atomic_exchange_if_greater(volatile uint32_t *pw, volatile uint32_t val) { + return _atomic_exchange_if_greater_impl(pw, val); +} + +uint64_t atomic_conditional_increment(volatile uint64_t *pw) { + return _atomic_conditional_increment_impl(pw); +} + +uint64_t atomic_decrement(volatile uint64_t *pw) { + return _atomic_decrement_impl(pw); +} + +uint64_t atomic_increment(volatile uint64_t *pw) { + return _atomic_increment_impl(pw); +} + +uint64_t atomic_sub(volatile uint64_t *pw, volatile uint64_t val) { + return _atomic_sub_impl(pw, val); +} + +uint64_t atomic_add(volatile uint64_t *pw, volatile uint64_t val) { + return _atomic_add_impl(pw, val); +} + +uint64_t atomic_exchange_if_greater(volatile uint64_t *pw, volatile uint64_t val) { + return _atomic_exchange_if_greater_impl(pw, val); +} +#endif diff --git a/core/templates/safe_refcount.h b/core/templates/safe_refcount.h new file mode 100644 index 0000000000..dc4e62354a --- /dev/null +++ b/core/templates/safe_refcount.h @@ -0,0 +1,203 @@ +/*************************************************************************/ +/* safe_refcount.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef SAFE_REFCOUNT_H +#define SAFE_REFCOUNT_H + +#include "core/os/mutex.h" +#include "core/typedefs.h" +#include "platform_config.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(volatile T *pw) { + if (*pw == 0) { + return 0; + } + + (*pw)++; + + return *pw; +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_decrement(volatile T *pw) { + (*pw)--; + + return *pw; +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_increment(volatile T *pw) { + (*pw)++; + + return *pw; +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_sub(volatile T *pw, volatile V val) { + (*pw) -= val; + + return *pw; +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_add(volatile T *pw, volatile V val) { + (*pw) += val; + + return *pw; +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_exchange_if_greater(volatile T *pw, volatile 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(volatile 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(volatile T *pw) { + return __sync_sub_and_fetch(pw, 1); +} + +template <class T> +static _ALWAYS_INLINE_ T atomic_increment(volatile T *pw) { + return __sync_add_and_fetch(pw, 1); +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_sub(volatile T *pw, volatile V val) { + return __sync_sub_and_fetch(pw, val); +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_add(volatile T *pw, volatile V val) { + return __sync_add_and_fetch(pw, val); +} + +template <class T, class V> +static _ALWAYS_INLINE_ T atomic_exchange_if_greater(volatile T *pw, volatile 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(volatile uint32_t *pw); +uint32_t atomic_decrement(volatile uint32_t *pw); +uint32_t atomic_increment(volatile uint32_t *pw); +uint32_t atomic_sub(volatile uint32_t *pw, volatile uint32_t val); +uint32_t atomic_add(volatile uint32_t *pw, volatile uint32_t val); +uint32_t atomic_exchange_if_greater(volatile uint32_t *pw, volatile uint32_t val); + +uint64_t atomic_conditional_increment(volatile uint64_t *pw); +uint64_t atomic_decrement(volatile uint64_t *pw); +uint64_t atomic_increment(volatile uint64_t *pw); +uint64_t atomic_sub(volatile uint64_t *pw, volatile uint64_t val); +uint64_t atomic_add(volatile uint64_t *pw, volatile uint64_t val); +uint64_t atomic_exchange_if_greater(volatile uint64_t *pw, volatile uint64_t val); + +#else +//no threads supported? +#error Must provide atomic functions for this platform or compiler! +#endif + +struct SafeRefCount { + uint32_t count; + +public: + // destroy() is called when weak_count_ drops to zero. + + _ALWAYS_INLINE_ bool ref() { // true on success + + return atomic_conditional_increment(&count) != 0; + } + + _ALWAYS_INLINE_ uint32_t refval() { // none-zero on success + + return atomic_conditional_increment(&count); + } + + _ALWAYS_INLINE_ bool unref() { // true if must be disposed of + + return atomic_decrement(&count) == 0; + } + + _ALWAYS_INLINE_ uint32_t unrefval() { // 0 if must be disposed of + + return atomic_decrement(&count); + } + + _ALWAYS_INLINE_ uint32_t get() const { // nothrow + + return count; + } + + _ALWAYS_INLINE_ void init(uint32_t p_value = 1) { + count = p_value; + } +}; + +#endif // SAFE_REFCOUNT_H diff --git a/core/templates/self_list.h b/core/templates/self_list.h new file mode 100644 index 0000000000..2a037d109c --- /dev/null +++ b/core/templates/self_list.h @@ -0,0 +1,139 @@ +/*************************************************************************/ +/* self_list.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef SELF_LIST_H +#define SELF_LIST_H + +#include "core/error/error_macros.h" +#include "core/typedefs.h" + +template <class T> +class SelfList { +public: + class List { + SelfList<T> *_first = nullptr; + SelfList<T> *_last = nullptr; + + public: + void add(SelfList<T> *p_elem) { + ERR_FAIL_COND(p_elem->_root); + + p_elem->_root = this; + p_elem->_next = _first; + p_elem->_prev = nullptr; + + if (_first) { + _first->_prev = p_elem; + + } else { + _last = p_elem; + } + + _first = p_elem; + } + + void add_last(SelfList<T> *p_elem) { + ERR_FAIL_COND(p_elem->_root); + + p_elem->_root = this; + p_elem->_next = nullptr; + p_elem->_prev = _last; + + if (_last) { + _last->_next = p_elem; + + } else { + _first = p_elem; + } + + _last = p_elem; + } + + void remove(SelfList<T> *p_elem) { + ERR_FAIL_COND(p_elem->_root != this); + if (p_elem->_next) { + p_elem->_next->_prev = p_elem->_prev; + } + + if (p_elem->_prev) { + p_elem->_prev->_next = p_elem->_next; + } + + if (_first == p_elem) { + _first = p_elem->_next; + } + + if (_last == p_elem) { + _last = p_elem->_prev; + } + + p_elem->_next = nullptr; + p_elem->_prev = nullptr; + p_elem->_root = nullptr; + } + + _FORCE_INLINE_ SelfList<T> *first() { return _first; } + _FORCE_INLINE_ const SelfList<T> *first() const { return _first; } + + _FORCE_INLINE_ List() {} + _FORCE_INLINE_ ~List() { ERR_FAIL_COND(_first != nullptr); } + }; + +private: + List *_root = nullptr; + T *_self; + SelfList<T> *_next = nullptr; + SelfList<T> *_prev = nullptr; + +public: + _FORCE_INLINE_ bool in_list() const { return _root; } + _FORCE_INLINE_ void remove_from_list() { + if (_root) { + _root->remove(this); + } + } + _FORCE_INLINE_ SelfList<T> *next() { return _next; } + _FORCE_INLINE_ SelfList<T> *prev() { return _prev; } + _FORCE_INLINE_ const SelfList<T> *next() const { return _next; } + _FORCE_INLINE_ const SelfList<T> *prev() const { return _prev; } + _FORCE_INLINE_ T *self() const { return _self; } + + _FORCE_INLINE_ SelfList(T *p_self) { + _self = p_self; + } + + _FORCE_INLINE_ ~SelfList() { + if (_root) { + _root->remove(this); + } + } +}; + +#endif // SELF_LIST_H diff --git a/core/templates/set.h b/core/templates/set.h new file mode 100644 index 0000000000..1bc0a3f41e --- /dev/null +++ b/core/templates/set.h @@ -0,0 +1,619 @@ +/*************************************************************************/ +/* set.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef SET_H +#define SET_H + +#include "core/os/memory.h" +#include "core/typedefs.h" + +// based on the very nice implementation of rb-trees by: +// https://web.archive.org/web/20120507164830/http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html + +template <class T, class C = Comparator<T>, class A = DefaultAllocator> +class Set { + enum Color { + RED, + BLACK + }; + struct _Data; + +public: + class Element { + private: + friend class Set<T, C, A>; + int color = RED; + Element *right = nullptr; + Element *left = nullptr; + Element *parent = nullptr; + Element *_next = nullptr; + Element *_prev = nullptr; + T value; + //_Data *data; + + public: + const Element *next() const { + return _next; + } + Element *next() { + return _next; + } + const Element *prev() const { + return _prev; + } + Element *prev() { + return _prev; + } + const T &get() const { + return value; + }; + Element() {} + }; + +private: + struct _Data { + Element *_root = nullptr; + Element *_nil; + int size_cache = 0; + + _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 + } + + void _create_root() { + _root = memnew_allocator(Element, A); + _root->parent = _root->left = _root->right = _nil; + _root->color = BLACK; + } + + void _free_root() { + if (_root) { + memdelete_allocator<Element, A>(_root); + _root = nullptr; + } + } + + ~_Data() { + _free_root(); + +#ifdef GLOBALNIL_DISABLED + memdelete_allocator<Element, A>(_nil); +#endif + } + }; + + _Data _data; + + inline void _set_color(Element *p_node, int p_color) { + 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; + p_node->right = r->left; + if (r->left != _data._nil) { + r->left->parent = p_node; + } + r->parent = p_node->parent; + if (p_node == p_node->parent->left) { + p_node->parent->left = r; + } else { + p_node->parent->right = r; + } + + r->left = p_node; + p_node->parent = r; + } + + inline void _rotate_right(Element *p_node) { + Element *l = p_node->left; + p_node->left = l->right; + if (l->right != _data._nil) { + l->right->parent = p_node; + } + l->parent = p_node->parent; + if (p_node == p_node->parent->right) { + p_node->parent->right = l; + } else { + p_node->parent->left = l; + } + + l->right = p_node; + p_node->parent = l; + } + + inline Element *_successor(Element *p_node) const { + Element *node = p_node; + + if (node->right != _data._nil) { + node = node->right; + while (node->left != _data._nil) { /* returns the minimum of the right subtree of node */ + node = node->left; + } + return node; + } else { + while (node == node->parent->right) { + node = node->parent; + } + + if (node->parent == _data._root) { + return nullptr; // No successor, as p_node = last node + } + return node->parent; + } + } + + inline Element *_predecessor(Element *p_node) const { + Element *node = p_node; + + if (node->left != _data._nil) { + node = node->left; + while (node->right != _data._nil) { /* returns the minimum of the left subtree of node */ + node = node->right; + } + return node; + } else { + while (node == node->parent->left) { + node = node->parent; + } + + if (node == _data._root) { + return nullptr; // No predecessor, as p_node = first node. + } + return node->parent; + } + } + + Element *_find(const T &p_value) const { + Element *node = _data._root->left; + C less; + + while (node != _data._nil) { + if (less(p_value, node->value)) { + node = node->left; + } else if (less(node->value, p_value)) { + node = node->right; + } else { + return node; // found + } + } + + return nullptr; + } + + Element *_lower_bound(const T &p_value) const { + Element *node = _data._root->left; + Element *prev = nullptr; + C less; + + while (node != _data._nil) { + prev = node; + + if (less(p_value, node->value)) { + node = node->left; + } else if (less(node->value, p_value)) { + node = node->right; + } else { + return node; // found + } + } + + if (prev == nullptr) { + return nullptr; // tree empty + } + + if (less(prev->value, p_value)) { + prev = prev->_next; + } + + return prev; + } + + 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 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_rb(Element *p_node) { + Element *root = _data._root->left; + 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 { + sibling = sibling->right; + _rotate_right(parent); + } + } + 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; + } + } 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 (sibling->left->color == BLACK) { + _set_color(sibling->right, BLACK); + _set_color(sibling, RED); + _rotate_left(sibling); + sibling = sibling->parent; + } + + _set_color(sibling, parent->color); + _set_color(parent, BLACK); + _set_color(sibling->left, BLACK); + _rotate_right(parent); + break; + } + } + } + + 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 : p_node->_next; + Element *node = (rp->left == _data._nil) ? rp->right : rp->left; + + Element *sibling; + if (rp == rp->parent->left) { + rp->parent->left = node; + sibling = rp->parent->right; + } else { + 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); + + rp->left = p_node->left; + rp->right = p_node->right; + rp->parent = p_node->parent; + rp->color = p_node->color; + 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; + } + } + + if (p_node->_next) { + p_node->_next->_prev = p_node->_prev; + } + if (p_node->_prev) { + p_node->_prev->_next = p_node->_next; + } + + memdelete_allocator<Element, A>(p_node); + _data.size_cache--; + ERR_FAIL_COND(_data._nil->color == RED); + } + + void _calculate_depth(Element *p_element, int &max_d, int d) const { + 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; + } + } + + void _cleanup_tree(Element *p_element) { + if (p_element == _data._nil) { + return; + } + + _cleanup_tree(p_element->left); + _cleanup_tree(p_element->right); + memdelete_allocator<Element, A>(p_element); + } + + void _copy_from(const Set &p_set) { + clear(); + // not the fastest way, but safeset to write. + for (Element *I = p_set.front(); I; I = I->next()) { + insert(I->get()); + } + } + +public: + const Element *find(const T &p_value) const { + if (!_data._root) { + return nullptr; + } + + const Element *res = _find(p_value); + return res; + } + + Element *find(const T &p_value) { + if (!_data._root) { + return nullptr; + } + + Element *res = _find(p_value); + return res; + } + + Element *lower_bound(const T &p_value) const { + return _lower_bound(p_value); + } + + bool has(const T &p_value) const { + return find(p_value) != nullptr; + } + + Element *insert(const T &p_value) { + if (!_data._root) { + _data._create_root(); + } + return _insert(p_value); + } + + void erase(Element *p_element) { + if (!_data._root || !p_element) { + return; + } + + _erase(p_element); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + } + + bool erase(const T &p_value) { + if (!_data._root) { + return false; + } + + Element *e = find(p_value); + if (!e) { + return false; + } + + _erase(e); + if (_data.size_cache == 0 && _data._root) { + _data._free_root(); + } + return true; + } + + Element *front() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->left != _data._nil) { + e = e->left; + } + + return e; + } + + Element *back() const { + if (!_data._root) { + return nullptr; + } + + Element *e = _data._root->left; + if (e == _data._nil) { + return nullptr; + } + + while (e->right != _data._nil) { + e = e->right; + } + + return e; + } + + 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; + } + + void clear() { + if (!_data._root) { + return; + } + + _cleanup_tree(_data._root->left); + _data._root->left = _data._nil; + _data.size_cache = 0; + _data._free_root(); + } + + void operator=(const Set &p_set) { + _copy_from(p_set); + } + + Set(const Set &p_set) { + _copy_from(p_set); + } + + _FORCE_INLINE_ Set() {} + + ~Set() { + clear(); + } +}; + +#endif // SET_H diff --git a/core/templates/simple_type.h b/core/templates/simple_type.h new file mode 100644 index 0000000000..841ab9f384 --- /dev/null +++ b/core/templates/simple_type.h @@ -0,0 +1,56 @@ +/*************************************************************************/ +/* simple_type.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef SIMPLE_TYPE_H +#define SIMPLE_TYPE_H + +/* Batch of specializations to obtain the actual simple type */ + +template <class T> +struct GetSimpleTypeT { + typedef T type_t; +}; + +template <class T> +struct GetSimpleTypeT<T &> { + typedef T type_t; +}; + +template <class T> +struct GetSimpleTypeT<T const> { + typedef T type_t; +}; + +template <class T> +struct GetSimpleTypeT<T const &> { + typedef T type_t; +}; + +#endif // SIMPLE_TYPE_H diff --git a/core/templates/sort_array.h b/core/templates/sort_array.h new file mode 100644 index 0000000000..a4326ac565 --- /dev/null +++ b/core/templates/sort_array.h @@ -0,0 +1,321 @@ +/*************************************************************************/ +/* sort_array.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef SORT_ARRAY_H +#define SORT_ARRAY_H + +#include "core/error/error_macros.h" +#include "core/typedefs.h" + +#define ERR_BAD_COMPARE(cond) \ + if (unlikely(cond)) { \ + ERR_PRINT("bad comparison function; sorting will be broken"); \ + break; \ + } + +template <class T> +struct _DefaultComparator { + _FORCE_INLINE_ bool operator()(const T &a, const T &b) const { return (a < b); } +}; + +#ifdef DEBUG_ENABLED +#define SORT_ARRAY_VALIDATE_ENABLED true +#else +#define SORT_ARRAY_VALIDATE_ENABLED false +#endif + +template <class T, class Comparator = _DefaultComparator<T>, bool Validate = SORT_ARRAY_VALIDATE_ENABLED> +class SortArray { + enum { + + INTROSORT_THRESHOLD = 16 + }; + +public: + Comparator compare; + + inline const T &median_of_3(const T &a, const T &b, const T &c) const { + if (compare(a, b)) { + if (compare(b, c)) { + return b; + } else if (compare(a, c)) { + return c; + } else { + return a; + } + } else if (compare(a, c)) { + return a; + } else if (compare(b, c)) { + return c; + } else { + return b; + } + } + + inline int bitlog(int n) const { + int k; + for (k = 0; n != 1; n >>= 1) { + ++k; + } + return k; + } + + /* Heap / Heapsort functions */ + + inline void push_heap(int p_first, int p_hole_idx, int p_top_index, T p_value, T *p_array) const { + int parent = (p_hole_idx - 1) / 2; + while (p_hole_idx > p_top_index && compare(p_array[p_first + parent], p_value)) { + p_array[p_first + p_hole_idx] = p_array[p_first + parent]; + p_hole_idx = parent; + parent = (p_hole_idx - 1) / 2; + } + p_array[p_first + p_hole_idx] = p_value; + } + + inline void pop_heap(int p_first, int p_last, int p_result, T p_value, T *p_array) const { + p_array[p_result] = p_array[p_first]; + adjust_heap(p_first, 0, p_last - p_first, p_value, p_array); + } + inline void pop_heap(int p_first, int p_last, T *p_array) const { + pop_heap(p_first, p_last - 1, p_last - 1, p_array[p_last - 1], p_array); + } + + inline void adjust_heap(int p_first, int p_hole_idx, int p_len, T p_value, T *p_array) const { + int top_index = p_hole_idx; + int second_child = 2 * p_hole_idx + 2; + + while (second_child < p_len) { + if (compare(p_array[p_first + second_child], p_array[p_first + (second_child - 1)])) { + second_child--; + } + + p_array[p_first + p_hole_idx] = p_array[p_first + second_child]; + p_hole_idx = second_child; + second_child = 2 * (second_child + 1); + } + + if (second_child == p_len) { + p_array[p_first + p_hole_idx] = p_array[p_first + (second_child - 1)]; + p_hole_idx = second_child - 1; + } + push_heap(p_first, p_hole_idx, top_index, p_value, p_array); + } + + inline void sort_heap(int p_first, int p_last, T *p_array) const { + while (p_last - p_first > 1) { + pop_heap(p_first, p_last--, p_array); + } + } + + inline void make_heap(int p_first, int p_last, T *p_array) const { + if (p_last - p_first < 2) { + return; + } + int len = p_last - p_first; + int parent = (len - 2) / 2; + + while (true) { + adjust_heap(p_first, parent, len, p_array[p_first + parent], p_array); + if (parent == 0) { + return; + } + parent--; + } + } + + inline void partial_sort(int p_first, int p_last, int p_middle, T *p_array) const { + make_heap(p_first, p_middle, p_array); + for (int i = p_middle; i < p_last; i++) { + if (compare(p_array[i], p_array[p_first])) { + pop_heap(p_first, p_middle, i, p_array[i], p_array); + } + } + sort_heap(p_first, p_middle, p_array); + } + + inline void partial_select(int p_first, int p_last, int p_middle, T *p_array) const { + make_heap(p_first, p_middle, p_array); + for (int i = p_middle; i < p_last; i++) { + if (compare(p_array[i], p_array[p_first])) { + pop_heap(p_first, p_middle, i, p_array[i], p_array); + } + } + } + + inline int partitioner(int p_first, int p_last, T p_pivot, T *p_array) const { + const int unmodified_first = p_first; + const int unmodified_last = p_last; + + while (true) { + while (compare(p_array[p_first], p_pivot)) { + if (Validate) { + ERR_BAD_COMPARE(p_first == unmodified_last - 1); + } + p_first++; + } + p_last--; + while (compare(p_pivot, p_array[p_last])) { + if (Validate) { + ERR_BAD_COMPARE(p_last == unmodified_first); + } + p_last--; + } + + if (!(p_first < p_last)) { + return p_first; + } + + SWAP(p_array[p_first], p_array[p_last]); + p_first++; + } + } + + inline void introsort(int p_first, int p_last, T *p_array, int p_max_depth) const { + while (p_last - p_first > INTROSORT_THRESHOLD) { + if (p_max_depth == 0) { + partial_sort(p_first, p_last, p_last, p_array); + return; + } + + p_max_depth--; + + int cut = partitioner( + p_first, + p_last, + median_of_3( + p_array[p_first], + p_array[p_first + (p_last - p_first) / 2], + p_array[p_last - 1]), + p_array); + + introsort(cut, p_last, p_array, p_max_depth); + p_last = cut; + } + } + + inline void introselect(int p_first, int p_nth, int p_last, T *p_array, int p_max_depth) const { + while (p_last - p_first > 3) { + if (p_max_depth == 0) { + partial_select(p_first, p_nth + 1, p_last, p_array); + SWAP(p_first, p_nth); + return; + } + + p_max_depth--; + + int cut = partitioner( + p_first, + p_last, + median_of_3( + p_array[p_first], + p_array[p_first + (p_last - p_first) / 2], + p_array[p_last - 1]), + p_array); + + if (cut <= p_nth) { + p_first = cut; + } else { + p_last = cut; + } + } + + insertion_sort(p_first, p_last, p_array); + } + + inline void unguarded_linear_insert(int p_last, T p_value, T *p_array) const { + int next = p_last - 1; + while (compare(p_value, p_array[next])) { + if (Validate) { + ERR_BAD_COMPARE(next == 0); + } + p_array[p_last] = p_array[next]; + p_last = next; + next--; + } + p_array[p_last] = p_value; + } + + inline void linear_insert(int p_first, int p_last, T *p_array) const { + T val = p_array[p_last]; + if (compare(val, p_array[p_first])) { + for (int i = p_last; i > p_first; i--) { + p_array[i] = p_array[i - 1]; + } + + p_array[p_first] = val; + } else { + unguarded_linear_insert(p_last, val, p_array); + } + } + + inline void insertion_sort(int p_first, int p_last, T *p_array) const { + if (p_first == p_last) { + return; + } + for (int i = p_first + 1; i != p_last; i++) { + linear_insert(p_first, i, p_array); + } + } + + inline void unguarded_insertion_sort(int p_first, int p_last, T *p_array) const { + for (int i = p_first; i != p_last; i++) { + unguarded_linear_insert(i, p_array[i], p_array); + } + } + + inline void final_insertion_sort(int p_first, int p_last, T *p_array) const { + if (p_last - p_first > INTROSORT_THRESHOLD) { + insertion_sort(p_first, p_first + INTROSORT_THRESHOLD, p_array); + unguarded_insertion_sort(p_first + INTROSORT_THRESHOLD, p_last, p_array); + } else { + insertion_sort(p_first, p_last, p_array); + } + } + + inline void sort_range(int p_first, int p_last, T *p_array) const { + if (p_first != p_last) { + introsort(p_first, p_last, p_array, bitlog(p_last - p_first) * 2); + final_insertion_sort(p_first, p_last, p_array); + } + } + + inline void sort(T *p_array, int p_len) const { + sort_range(0, p_len, p_array); + } + + inline void nth_element(int p_first, int p_last, int p_nth, T *p_array) const { + if (p_first == p_last || p_nth == p_last) { + return; + } + introselect(p_first, p_nth, p_last, p_array, bitlog(p_last - p_first) * 2); + } +}; + +#endif // SORT_ARRAY_H diff --git a/core/templates/thread_work_pool.cpp b/core/templates/thread_work_pool.cpp new file mode 100644 index 0000000000..3a95e83ffc --- /dev/null +++ b/core/templates/thread_work_pool.cpp @@ -0,0 +1,81 @@ +/*************************************************************************/ +/* thread_work_pool.cpp */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#include "thread_work_pool.h" + +#include "core/os/os.h" + +void ThreadWorkPool::_thread_function(ThreadData *p_thread) { + while (true) { + p_thread->start.wait(); + if (p_thread->exit.load()) { + break; + } + p_thread->work->work(); + p_thread->completed.post(); + } +} + +void ThreadWorkPool::init(int p_thread_count) { + ERR_FAIL_COND(threads != nullptr); + if (p_thread_count < 0) { + p_thread_count = OS::get_singleton()->get_processor_count(); + } + + thread_count = p_thread_count; + threads = memnew_arr(ThreadData, thread_count); + + for (uint32_t i = 0; i < thread_count; i++) { + threads[i].exit.store(false); + threads[i].thread = memnew(std::thread(ThreadWorkPool::_thread_function, &threads[i])); + } +} + +void ThreadWorkPool::finish() { + if (threads == nullptr) { + return; + } + + for (uint32_t i = 0; i < thread_count; i++) { + threads[i].exit.store(true); + threads[i].start.post(); + } + for (uint32_t i = 0; i < thread_count; i++) { + threads[i].thread->join(); + memdelete(threads[i].thread); + } + + memdelete_arr(threads); + threads = nullptr; +} + +ThreadWorkPool::~ThreadWorkPool() { + finish(); +} diff --git a/core/templates/thread_work_pool.h b/core/templates/thread_work_pool.h new file mode 100644 index 0000000000..661060aa3f --- /dev/null +++ b/core/templates/thread_work_pool.h @@ -0,0 +1,133 @@ +/*************************************************************************/ +/* thread_work_pool.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef THREAD_WORK_POOL_H +#define THREAD_WORK_POOL_H + +#include "core/os/memory.h" +#include "core/os/semaphore.h" + +#include <atomic> +#include <thread> + +class ThreadWorkPool { + std::atomic<uint32_t> index; + + struct BaseWork { + std::atomic<uint32_t> *index; + uint32_t max_elements; + virtual void work() = 0; + virtual ~BaseWork() = default; + }; + + template <class C, class M, class U> + struct Work : public BaseWork { + C *instance; + M method; + U userdata; + virtual void work() { + while (true) { + uint32_t work_index = index->fetch_add(1, std::memory_order_relaxed); + if (work_index >= max_elements) { + break; + } + (instance->*method)(work_index, userdata); + } + } + }; + + struct ThreadData { + std::thread *thread; + Semaphore start; + Semaphore completed; + std::atomic<bool> exit; + BaseWork *work; + }; + + ThreadData *threads = nullptr; + uint32_t thread_count = 0; + BaseWork *current_work = nullptr; + + static void _thread_function(ThreadData *p_thread); + +public: + template <class C, class M, class U> + void begin_work(uint32_t p_elements, C *p_instance, M p_method, U p_userdata) { + ERR_FAIL_COND(!threads); //never initialized + ERR_FAIL_COND(current_work != nullptr); + + index.store(0); + + Work<C, M, U> *w = memnew((Work<C, M, U>)); + w->instance = p_instance; + w->userdata = p_userdata; + w->method = p_method; + w->index = &index; + w->max_elements = p_elements; + + current_work = w; + + for (uint32_t i = 0; i < thread_count; i++) { + threads[i].work = w; + threads[i].start.post(); + } + } + + bool is_working() const { + return current_work != nullptr; + } + + uint32_t get_work_index() const { + return index; + } + + void end_work() { + ERR_FAIL_COND(current_work == nullptr); + for (uint32_t i = 0; i < thread_count; i++) { + threads[i].completed.wait(); + threads[i].work = nullptr; + } + + memdelete(current_work); + current_work = nullptr; + } + + template <class C, class M, class U> + void do_work(uint32_t p_elements, C *p_instance, M p_method, U p_userdata) { + begin_work(p_elements, p_instance, p_method, p_userdata); + end_work(); + } + + void init(int p_thread_count = -1); + void finish(); + ~ThreadWorkPool(); +}; + +#endif // THREAD_POOL_H diff --git a/core/templates/vector.h b/core/templates/vector.h new file mode 100644 index 0000000000..9d45f7c30a --- /dev/null +++ b/core/templates/vector.h @@ -0,0 +1,222 @@ +/*************************************************************************/ +/* vector.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef VECTOR_H +#define VECTOR_H + +/** + * @class Vector + * @author Juan Linietsky + * Vector container. Regular Vector Container. Use with care and for smaller arrays when possible. Use Vector for large arrays. +*/ + +#include "core/error/error_macros.h" +#include "core/os/copymem.h" +#include "core/os/memory.h" +#include "core/templates/cowdata.h" +#include "core/templates/sort_array.h" + +template <class T> +class VectorWriteProxy { +public: + _FORCE_INLINE_ T &operator[](int p_index) { + CRASH_BAD_INDEX(p_index, ((Vector<T> *)(this))->_cowdata.size()); + + return ((Vector<T> *)(this))->_cowdata.ptrw()[p_index]; + } +}; + +template <class T> +class Vector { + friend class VectorWriteProxy<T>; + +public: + VectorWriteProxy<T> write; + +private: + CowData<T> _cowdata; + +public: + bool push_back(T p_elem); + _FORCE_INLINE_ bool append(const T &p_elem) { return push_back(p_elem); } //alias + + void remove(int p_index) { _cowdata.remove(p_index); } + void erase(const T &p_val) { + int idx = find(p_val); + if (idx >= 0) { + remove(idx); + } + } + void invert(); + + _FORCE_INLINE_ T *ptrw() { return _cowdata.ptrw(); } + _FORCE_INLINE_ const T *ptr() const { return _cowdata.ptr(); } + _FORCE_INLINE_ void clear() { resize(0); } + _FORCE_INLINE_ bool empty() const { return _cowdata.empty(); } + + _FORCE_INLINE_ T get(int p_index) { return _cowdata.get(p_index); } + _FORCE_INLINE_ const T &get(int p_index) const { return _cowdata.get(p_index); } + _FORCE_INLINE_ void set(int p_index, const T &p_elem) { _cowdata.set(p_index, p_elem); } + _FORCE_INLINE_ int size() const { return _cowdata.size(); } + Error resize(int p_size) { return _cowdata.resize(p_size); } + _FORCE_INLINE_ const T &operator[](int p_index) const { return _cowdata.get(p_index); } + Error insert(int p_pos, T p_val) { return _cowdata.insert(p_pos, p_val); } + int find(const T &p_val, int p_from = 0) const { return _cowdata.find(p_val, p_from); } + + void append_array(Vector<T> p_other); + + bool has(const T &p_val) { + return find(p_val, 0) != -1; + } + + template <class C> + void sort_custom() { + int len = _cowdata.size(); + if (len == 0) { + return; + } + + T *data = ptrw(); + SortArray<T, C> sorter; + sorter.sort(data, len); + } + + void sort() { + sort_custom<_DefaultComparator<T>>(); + } + + void ordered_insert(const T &p_val) { + int i; + for (i = 0; i < _cowdata.size(); i++) { + if (p_val < operator[](i)) { + break; + } + } + insert(i, p_val); + } + + inline Vector &operator=(const Vector &p_from) { + _cowdata._ref(p_from._cowdata); + return *this; + } + + Vector<uint8_t> to_byte_array() const { + Vector<uint8_t> ret; + ret.resize(size() * sizeof(T)); + copymem(ret.ptrw(), ptr(), sizeof(T) * size()); + return ret; + } + + Vector<T> subarray(int p_from, int p_to) const { + if (p_from < 0) { + p_from = size() + p_from; + } + if (p_to < 0) { + p_to = size() + p_to; + } + + ERR_FAIL_INDEX_V(p_from, size(), Vector<T>()); + ERR_FAIL_INDEX_V(p_to, size(), Vector<T>()); + + Vector<T> slice; + int span = 1 + p_to - p_from; + slice.resize(span); + const T *r = ptr(); + T *w = slice.ptrw(); + for (int i = 0; i < span; ++i) { + w[i] = r[p_from + i]; + } + + return slice; + } + + bool operator==(const Vector<T> &p_arr) const { + int s = size(); + if (s != p_arr.size()) { + return false; + } + for (int i = 0; i < s; i++) { + if (operator[](i) != p_arr[i]) { + return false; + } + } + return true; + } + + bool operator!=(const Vector<T> &p_arr) const { + int s = size(); + if (s != p_arr.size()) { + return true; + } + for (int i = 0; i < s; i++) { + if (operator[](i) != p_arr[i]) { + return true; + } + } + return false; + } + + _FORCE_INLINE_ Vector() {} + _FORCE_INLINE_ Vector(const Vector &p_from) { _cowdata._ref(p_from._cowdata); } + + _FORCE_INLINE_ ~Vector() {} +}; + +template <class T> +void Vector<T>::invert() { + for (int i = 0; i < size() / 2; i++) { + T *p = ptrw(); + SWAP(p[i], p[size() - i - 1]); + } +} + +template <class T> +void Vector<T>::append_array(Vector<T> p_other) { + const int ds = p_other.size(); + if (ds == 0) { + return; + } + const int bs = size(); + resize(bs + ds); + for (int i = 0; i < ds; ++i) { + ptrw()[bs + i] = p_other[i]; + } +} + +template <class T> +bool Vector<T>::push_back(T p_elem) { + Error err = resize(size() + 1); + ERR_FAIL_COND_V(err, true); + set(size() - 1, p_elem); + + return false; +} + +#endif // VECTOR_H diff --git a/core/templates/vmap.h b/core/templates/vmap.h new file mode 100644 index 0000000000..8d2a3d2a9c --- /dev/null +++ b/core/templates/vmap.h @@ -0,0 +1,202 @@ +/*************************************************************************/ +/* vmap.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef VMAP_H +#define VMAP_H + +#include "core/templates/cowdata.h" +#include "core/typedefs.h" + +template <class T, class V> +class VMap { +public: + struct Pair { + T key; + V value; + + _FORCE_INLINE_ Pair() {} + + _FORCE_INLINE_ Pair(const T &p_key, const V &p_value) { + key = p_key; + value = p_value; + } + }; + +private: + CowData<Pair> _cowdata; + + _FORCE_INLINE_ int _find(const T &p_val, bool &r_exact) const { + r_exact = false; + if (_cowdata.empty()) { + return 0; + } + + int low = 0; + int high = _cowdata.size() - 1; + const Pair *a = _cowdata.ptr(); + int middle = 0; + +#ifdef DEBUG_ENABLED + if (low > high) { + ERR_PRINT("low > high, this may be a bug"); + } +#endif + while (low <= high) { + middle = (low + high) / 2; + + if (p_val < a[middle].key) { + high = middle - 1; //search low end of array + } else if (a[middle].key < p_val) { + low = middle + 1; //search high end of array + } else { + r_exact = true; + return middle; + } + } + + //return the position where this would be inserted + if (a[middle].key < p_val) { + middle++; + } + return middle; + } + + _FORCE_INLINE_ int _find_exact(const T &p_val) const { + if (_cowdata.empty()) { + return -1; + } + + int low = 0; + int high = _cowdata.size() - 1; + int middle; + const Pair *a = _cowdata.ptr(); + + while (low <= high) { + middle = (low + high) / 2; + + if (p_val < a[middle].key) { + high = middle - 1; //search low end of array + } else if (a[middle].key < p_val) { + low = middle + 1; //search high end of array + } else { + return middle; + } + } + + return -1; + } + +public: + int insert(const T &p_key, const V &p_val) { + bool exact; + int pos = _find(p_key, exact); + if (exact) { + _cowdata.get_m(pos).value = p_val; + return pos; + } + _cowdata.insert(pos, Pair(p_key, p_val)); + return pos; + } + + bool has(const T &p_val) const { + return _find_exact(p_val) != -1; + } + + void erase(const T &p_val) { + int pos = _find_exact(p_val); + if (pos < 0) { + return; + } + _cowdata.remove(pos); + } + + int find(const T &p_val) const { + return _find_exact(p_val); + } + + int find_nearest(const T &p_val) const { + bool exact; + return _find(p_val, exact); + } + + _FORCE_INLINE_ int size() const { return _cowdata.size(); } + _FORCE_INLINE_ bool empty() const { return _cowdata.empty(); } + + const Pair *get_array() const { + return _cowdata.ptr(); + } + + Pair *get_array() { + return _cowdata.ptrw(); + } + + const V &getv(int p_index) const { + return _cowdata.get(p_index).value; + } + + V &getv(int p_index) { + return _cowdata.get_m(p_index).value; + } + + const T &getk(int p_index) const { + return _cowdata.get(p_index).key; + } + + T &getk(int p_index) { + return _cowdata.get_m(p_index).key; + } + + inline const V &operator[](const T &p_key) const { + int pos = _find_exact(p_key); + + CRASH_COND(pos < 0); + + return _cowdata.get(pos).value; + } + + inline V &operator[](const T &p_key) { + int pos = _find_exact(p_key); + if (pos < 0) { + pos = insert(p_key, V()); + } + + return _cowdata.get_m(pos).value; + } + + _FORCE_INLINE_ VMap() {} + _FORCE_INLINE_ VMap(const VMap &p_from) { _cowdata._ref(p_from._cowdata); } + + inline VMap &operator=(const VMap &p_from) { + _cowdata._ref(p_from._cowdata); + return *this; + } +}; + +#endif // VMAP_H diff --git a/core/templates/vset.h b/core/templates/vset.h new file mode 100644 index 0000000000..4c0b8717b6 --- /dev/null +++ b/core/templates/vset.h @@ -0,0 +1,142 @@ +/*************************************************************************/ +/* vset.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* https://godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md). */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ + +#ifndef VSET_H +#define VSET_H + +#include "core/templates/vector.h" +#include "core/typedefs.h" + +template <class T> +class VSet { + Vector<T> _data; + + _FORCE_INLINE_ int _find(const T &p_val, bool &r_exact) const { + r_exact = false; + if (_data.empty()) { + return 0; + } + + int low = 0; + int high = _data.size() - 1; + const T *a = &_data[0]; + int middle = 0; + +#ifdef DEBUG_ENABLED + if (low > high) { + ERR_PRINT("low > high, this may be a bug"); + } +#endif + + while (low <= high) { + middle = (low + high) / 2; + + if (p_val < a[middle]) { + high = middle - 1; //search low end of array + } else if (a[middle] < p_val) { + low = middle + 1; //search high end of array + } else { + r_exact = true; + return middle; + } + } + + //return the position where this would be inserted + if (a[middle] < p_val) { + middle++; + } + return middle; + } + + _FORCE_INLINE_ int _find_exact(const T &p_val) const { + if (_data.empty()) { + return -1; + } + + int low = 0; + int high = _data.size() - 1; + int middle; + const T *a = &_data[0]; + + while (low <= high) { + middle = (low + high) / 2; + + if (p_val < a[middle]) { + high = middle - 1; //search low end of array + } else if (a[middle] < p_val) { + low = middle + 1; //search high end of array + } else { + return middle; + } + } + + return -1; + } + +public: + void insert(const T &p_val) { + bool exact; + int pos = _find(p_val, exact); + if (exact) { + return; + } + _data.insert(pos, p_val); + } + + bool has(const T &p_val) const { + return _find_exact(p_val) != -1; + } + + void erase(const T &p_val) { + int pos = _find_exact(p_val); + if (pos < 0) { + return; + } + _data.remove(pos); + } + + int find(const T &p_val) const { + return _find_exact(p_val); + } + + _FORCE_INLINE_ bool empty() const { return _data.empty(); } + + _FORCE_INLINE_ int size() const { return _data.size(); } + + inline T &operator[](int p_index) { + return _data.write[p_index]; + } + + inline const T &operator[](int p_index) const { + return _data[p_index]; + } +}; + +#endif // VSET_H |