Refactored RID/RID_Owner to always use O(1) allocation.

* Implements a growing chunked allocator
* Removed redudant methods get and getptr, only getornull is supported now.

4 files changed, 281 insertions, 180 deletions

diff --git a/core/rid.cpp b/core/rid.cpp
deleted file mode 100644
index 727658314f..0000000000
--- a/core/rid.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-/*************************************************************************/
-/*  rid.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.h"
-
-RID_Data::~RID_Data() {
-}
-
-SafeRefCount RID_OwnerBase::refcount;
-
-void RID_OwnerBase::init_rid() {
-
-	refcount.init();
-}
diff --git a/core/rid.h b/core/rid.h
index 7e12409181..583d62a5b1 100644
--- a/core/rid.h
+++ b/core/rid.h
@@ -32,172 +32,45 @@
 #define RID_H
 
 #include "core/list.h"
+#include "core/oa_hash_map.h"
 #include "core/os/memory.h"
 #include "core/safe_refcount.h"
 #include "core/set.h"
 #include "core/typedefs.h"
 
-class RID_OwnerBase;
-
-class RID_Data {
-
-	friend class RID_OwnerBase;
-
-#ifndef DEBUG_ENABLED
-	RID_OwnerBase *_owner;
-#endif
-	uint32_t _id;
-
-public:
-	_FORCE_INLINE_ uint32_t get_id() const { return _id; }
-
-	virtual ~RID_Data();
-};
+class RID_AllocBase;
 
 class RID {
-	friend class RID_OwnerBase;
-
-	mutable RID_Data *_data;
+	friend class RID_AllocBase;
+	uint64_t _id;
 
 public:
-	_FORCE_INLINE_ RID_Data *get_data() const { return _data; }
-
 	_FORCE_INLINE_ bool operator==(const RID &p_rid) const {
 
-		return _data == p_rid._data;
+		return _id == p_rid._id;
 	}
 	_FORCE_INLINE_ bool operator<(const RID &p_rid) const {
 
-		return _data < p_rid._data;
+		return _id < p_rid._id;
 	}
 	_FORCE_INLINE_ bool operator<=(const RID &p_rid) const {
 
-		return _data <= p_rid._data;
+		return _id <= p_rid._id;
 	}
 	_FORCE_INLINE_ bool operator>(const RID &p_rid) const {
 
-		return _data > p_rid._data;
+		return _id > p_rid._id;
 	}
 	_FORCE_INLINE_ bool operator!=(const RID &p_rid) const {
 
-		return _data != p_rid._data;
+		return _id != p_rid._id;
 	}
-	_FORCE_INLINE_ bool is_valid() const { return _data != NULL; }
+	_FORCE_INLINE_ bool is_valid() const { return _id != 0; }
 
-	_FORCE_INLINE_ uint32_t get_id() const { return _data ? _data->get_id() : 0; }
+	_FORCE_INLINE_ uint64_t get_id() const { return _id; }
 
 	_FORCE_INLINE_ RID() {
-		_data = NULL;
-	}
-};
-
-class RID_OwnerBase {
-protected:
-	static SafeRefCount refcount;
-	_FORCE_INLINE_ void _set_data(RID &p_rid, RID_Data *p_data) {
-		p_rid._data = p_data;
-		refcount.ref();
-		p_data->_id = refcount.get();
-#ifndef DEBUG_ENABLED
-		p_data->_owner = this;
-#endif
-	}
-
-#ifndef DEBUG_ENABLED
-
-	_FORCE_INLINE_ bool _is_owner(const RID &p_rid) const {
-
-		return this == p_rid._data->_owner;
-	}
-
-	_FORCE_INLINE_ void _remove_owner(RID &p_rid) {
-
-		p_rid._data->_owner = NULL;
-	}
-#endif
-
-public:
-	virtual void get_owned_list(List<RID> *p_owned) = 0;
-
-	static void init_rid();
-	virtual ~RID_OwnerBase() {}
-};
-
-template <class T>
-class RID_Owner : public RID_OwnerBase {
-public:
-#ifdef DEBUG_ENABLED
-	mutable Set<RID_Data *> id_map;
-#endif
-public:
-	_FORCE_INLINE_ RID make_rid(T *p_data) {
-
-		RID rid;
-		_set_data(rid, p_data);
-
-#ifdef DEBUG_ENABLED
-		id_map.insert(p_data);
-#endif
-
-		return rid;
-	}
-
-	_FORCE_INLINE_ T *get(const RID &p_rid) {
-
-#ifdef DEBUG_ENABLED
-
-		ERR_FAIL_COND_V(!p_rid.is_valid(), NULL);
-		ERR_FAIL_COND_V(!id_map.has(p_rid.get_data()), NULL);
-#endif
-		return static_cast<T *>(p_rid.get_data());
-	}
-
-	_FORCE_INLINE_ T *getornull(const RID &p_rid) {
-
-#ifdef DEBUG_ENABLED
-
-		if (p_rid.get_data()) {
-			ERR_FAIL_COND_V(!id_map.has(p_rid.get_data()), NULL);
-		}
-#endif
-		return static_cast<T *>(p_rid.get_data());
-	}
-
-	_FORCE_INLINE_ T *getptr(const RID &p_rid) {
-
-		return static_cast<T *>(p_rid.get_data());
-	}
-
-	_FORCE_INLINE_ bool owns(const RID &p_rid) const {
-
-		if (p_rid.get_data() == NULL)
-			return false;
-#ifdef DEBUG_ENABLED
-		return id_map.has(p_rid.get_data());
-#else
-		return _is_owner(p_rid);
-#endif
-	}
-
-	void free(RID p_rid) {
-
-#ifdef DEBUG_ENABLED
-		id_map.erase(p_rid.get_data());
-#else
-		_remove_owner(p_rid);
-#endif
-	}
-
-	void get_owned_list(List<RID> *p_owned) {
-
-#ifdef DEBUG_ENABLED
-
-		for (typename Set<RID_Data *>::Element *E = id_map.front(); E; E = E->next()) {
-			RID r;
-			_set_data(r, static_cast<T *>(E->get()));
-			p_owned->push_back(r);
-		}
-#endif
+		_id = 0;
 	}
 };
 
diff --git a/core/rid_owner.cpp b/core/rid_owner.cpp
new file mode 100644
index 0000000000..6ebb5ceecc
--- /dev/null
+++ b/core/rid_owner.cpp
@@ -0,0 +1,3 @@
+#include "rid_owner.h"
+
+volatile uint64_t RID_AllocBase::base_id = 1;
diff --git a/core/rid_owner.h b/core/rid_owner.h
new file mode 100644
index 0000000000..2443aac0a4
--- /dev/null
+++ b/core/rid_owner.h
@@ -0,0 +1,266 @@
+#ifndef RID_OWNER_H
+#define RID_OWNER_H
+
+#include "core/print_string.h"
+#include "core/rid.h"
+
+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>
+class RID_Alloc : public RID_AllocBase {
+
+	T **chunks;
+	uint32_t **free_list_chunks;
+	uint32_t **validator_chunks;
+
+	uint32_t elements_in_chunk;
+	uint32_t max_alloc;
+	uint32_t alloc_count;
+
+	const char *description;
+
+public:
+	RID make_rid(const T &p_value) {
+
+		if (alloc_count == max_alloc) {
+			//allocate a new chunk
+			uint32_t chunk_count = alloc_count == 0 ? 0 : (max_alloc / elements_in_chunk + 1);
+
+			//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++;
+
+		return _make_from_id(id);
+	}
+
+	_FORCE_INLINE_ T *getornull(const RID &p_rid) {
+
+		uint64_t id = p_rid.get_id();
+		uint32_t idx = uint32_t(id & 0xFFFFFFFF);
+		if (unlikely(idx >= alloc_count)) {
+			return NULL;
+		}
+
+		uint32_t idx_chunk = idx / elements_in_chunk;
+		uint32_t idx_element = idx % elements_in_chunk;
+
+		uint32_t validator = uint32_t(id >> 32);
+		if (validator_chunks[idx_chunk][idx_element] != validator) {
+			return NULL;
+		}
+
+		return &chunks[idx_chunk][idx_element];
+	}
+
+	_FORCE_INLINE_ bool owns(const RID &p_rid) {
+
+		uint64_t id = p_rid.get_id();
+		uint32_t idx = uint32_t(id & 0xFFFFFFFF);
+		if (unlikely(idx >= alloc_count)) {
+			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);
+		return validator_chunks[idx_chunk][idx_element] == validator;
+	}
+
+	_FORCE_INLINE_ void free(const RID &p_rid) {
+
+		uint64_t id = p_rid.get_id();
+		uint32_t idx = uint32_t(id & 0xFFFFFFFF);
+		if (unlikely(idx >= alloc_count)) {
+			return;
+		}
+
+		uint32_t idx_chunk = idx / elements_in_chunk;
+		uint32_t idx_element = idx % elements_in_chunk;
+
+		uint32_t validator = uint32_t(id >> 32);
+		if (validator_chunks[idx_chunk][idx_element] != validator) {
+			return;
+		}
+
+		chunks[idx_chunk][idx_element].~T();
+		validator_chunks[idx_chunk][idx_element] = 0xFFFFFFFF; // go invalid
+
+		free_list_chunks[alloc_count / elements_in_chunk][alloc_count % elements_in_chunk] = idx;
+		alloc_count--;
+	}
+
+	void get_owned_list(List<RID> *p_owned) {
+		for (size_t i = 0; i < alloc_count; i++) {
+			uint64_t idx = free_list_chunks[i / elements_in_chunk][i % elements_in_chunk];
+			uint64_t validator = validator_chunks[idx / elements_in_chunk][idx % elements_in_chunk];
+			p_owned->push_back(_make_from_id((validator << 32) & idx));
+		}
+	}
+
+	void set_description(const char *p_descrption) {
+		description = p_descrption;
+	}
+
+	RID_Alloc(uint32_t p_target_chunk_byte_size = 4096) {
+		chunks = NULL;
+		free_list_chunks = NULL;
+		validator_chunks = NULL;
+
+		elements_in_chunk = sizeof(T) > p_target_chunk_byte_size ? 1 : (p_target_chunk_byte_size / sizeof(T));
+		max_alloc = 0;
+		alloc_count = 0;
+		description = NULL;
+	}
+
+	~RID_Alloc() {
+		if (alloc_count) {
+			if (description) {
+				print_error("ERROR: " + itos(alloc_count) + " RID allocations of type " + description + " were leaked at exit.");
+			} else {
+				print_error("ERROR: " + itos(alloc_count) + " RID allocations of unspecified type were leaked at exit.");
+			}
+
+			for (uint32_t i = 0; i < alloc_count; i++) {
+				uint64_t idx = free_list_chunks[i / elements_in_chunk][i % elements_in_chunk];
+				chunks[idx / elements_in_chunk][idx % elements_in_chunk].~T();
+			}
+		}
+
+		uint32_t chunk_count = alloc_count == 0 ? 0 : (max_alloc / elements_in_chunk + 1);
+		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>
+class RID_PtrOwner {
+	RID_Alloc<T *> 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 NULL;
+		}
+		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>
+class RID_Owner {
+	RID_Alloc<T> 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_ 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