summaryrefslogtreecommitdiff
path: root/core/templates
diff options
context:
space:
mode:
Diffstat (limited to 'core/templates')
-rw-r--r--core/templates/command_queue_mt.h2
-rw-r--r--core/templates/cowdata.h18
-rw-r--r--core/templates/hash_map.h18
-rw-r--r--core/templates/hashfuncs.h13
-rw-r--r--core/templates/local_vector.h2
-rw-r--r--core/templates/map.h2
-rw-r--r--core/templates/paged_allocator.h5
-rw-r--r--core/templates/pooled_list.h14
-rw-r--r--core/templates/rid_owner.h28
-rw-r--r--core/templates/safe_list.h375
-rw-r--r--core/templates/search_array.h67
-rw-r--r--core/templates/set.h9
-rw-r--r--core/templates/vector.h10
13 files changed, 520 insertions, 43 deletions
diff --git a/core/templates/command_queue_mt.h b/core/templates/command_queue_mt.h
index acc46da0d5..519a896ffc 100644
--- a/core/templates/command_queue_mt.h
+++ b/core/templates/command_queue_mt.h
@@ -321,7 +321,7 @@ class CommandQueueMT {
DECL_CMD(0)
SPACE_SEP_LIST(DECL_CMD, 15)
- /* comands that return */
+ // Commands that return.
DECL_CMD_RET(0)
SPACE_SEP_LIST(DECL_CMD_RET, 15)
diff --git a/core/templates/cowdata.h b/core/templates/cowdata.h
index c985593473..9b8c0eb528 100644
--- a/core/templates/cowdata.h
+++ b/core/templates/cowdata.h
@@ -49,6 +49,12 @@ class VMap;
SAFE_NUMERIC_TYPE_PUN_GUARANTEES(uint32_t)
#endif
+// Silence a false positive warning (see GH-52119).
+#if defined(__GNUC__) && !defined(__clang__)
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wplacement-new"
+#endif
+
template <class T>
class CowData {
template <class TV>
@@ -232,7 +238,7 @@ uint32_t CowData<T>::_copy_on_write() {
uint32_t *mem_new = (uint32_t *)Memory::alloc_static(_get_alloc_size(current_size), true);
- new (mem_new - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(1); //refcount
+ new (mem_new - 2) SafeNumeric<uint32_t>(1); //refcount
*(mem_new - 1) = current_size; //size
T *_data = (T *)(mem_new);
@@ -286,14 +292,14 @@ Error CowData<T>::resize(int p_size) {
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
- new (ptr - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(1); //refcount
+ new (ptr - 2) SafeNumeric<uint32_t>(1); //refcount
_ptr = (T *)ptr;
} else {
uint32_t *_ptrnew = (uint32_t *)Memory::realloc_static(_ptr, alloc_size, true);
ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY);
- new (_ptrnew - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(rc); //refcount
+ new (_ptrnew - 2) SafeNumeric<uint32_t>(rc); //refcount
_ptr = (T *)(_ptrnew);
}
@@ -323,7 +329,7 @@ Error CowData<T>::resize(int p_size) {
if (alloc_size != current_alloc_size) {
uint32_t *_ptrnew = (uint32_t *)Memory::realloc_static(_ptr, alloc_size, true);
ERR_FAIL_COND_V(!_ptrnew, ERR_OUT_OF_MEMORY);
- new (_ptrnew - 2, sizeof(uint32_t), "") SafeNumeric<uint32_t>(rc); //refcount
+ new (_ptrnew - 2) SafeNumeric<uint32_t>(rc); //refcount
_ptr = (T *)(_ptrnew);
}
@@ -380,4 +386,8 @@ CowData<T>::~CowData() {
_unref(_ptr);
}
+#if defined(__GNUC__) && !defined(__clang__)
+#pragma GCC diagnostic pop
+#endif
+
#endif // COWDATA_H
diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h
index 1257b54449..1634219c23 100644
--- a/core/templates/hash_map.h
+++ b/core/templates/hash_map.h
@@ -62,7 +62,9 @@ public:
TKey key;
TData data;
- Pair() {}
+ Pair(const TKey &p_key) :
+ key(p_key),
+ data() {}
Pair(const TKey &p_key, const TData &p_data) :
key(p_key),
data(p_data) {
@@ -90,6 +92,12 @@ public:
const TData &value() const {
return pair.value();
}
+
+ Element(const TKey &p_key) :
+ pair(p_key) {}
+ Element(const Element &p_other) :
+ hash(p_other.hash),
+ pair(p_other.pair.key, p_other.pair.data) {}
};
private:
@@ -192,14 +200,12 @@ private:
Element *create_element(const TKey &p_key) {
/* if element doesn't exist, create it */
- Element *e = memnew(Element);
+ Element *e = memnew(Element(p_key));
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++;
@@ -228,9 +234,7 @@ private:
const Element *e = p_t.hash_table[i];
while (e) {
- Element *le = memnew(Element); /* local element */
-
- *le = *e; /* copy data */
+ Element *le = memnew(Element(*e)); /* local element */
/* add to list and reassign pointers */
le->next = hash_table[i];
diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h
index 4572b269cf..c1a7c4146e 100644
--- a/core/templates/hashfuncs.h
+++ b/core/templates/hashfuncs.h
@@ -74,6 +74,13 @@ 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;
}
+/**
+ * Thomas Wang's 64-bit to 32-bit Hash function:
+ * https://web.archive.org/web/20071223173210/https:/www.concentric.net/~Ttwang/tech/inthash.htm
+ *
+ * @param p_int - 64-bit unsigned integer key to be hashed
+ * @return unsigned 32-bit value representing hashcode
+ */
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;
@@ -82,7 +89,7 @@ static inline uint32_t hash_one_uint64(const uint64_t p_int) {
v = v ^ (v >> 11);
v = v + (v << 6);
v = v ^ (v >> 22);
- return (int)v;
+ return uint32_t(v);
}
static inline uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381) {
@@ -95,7 +102,7 @@ static inline uint32_t hash_djb2_one_float(double p_in, uint32_t p_prev = 5381)
if (p_in == 0.0f) {
u.d = 0.0;
} else if (Math::is_nan(p_in)) {
- u.d = Math_NAN;
+ u.d = NAN;
} else {
u.d = p_in;
}
@@ -124,7 +131,7 @@ static inline uint64_t hash_djb2_one_float_64(double p_in, uint64_t p_prev = 538
if (p_in == 0.0f) {
u.d = 0.0;
} else if (Math::is_nan(p_in)) {
- u.d = Math_NAN;
+ u.d = NAN;
} else {
u.d = p_in;
}
diff --git a/core/templates/local_vector.h b/core/templates/local_vector.h
index 668ec513d6..5704b8f230 100644
--- a/core/templates/local_vector.h
+++ b/core/templates/local_vector.h
@@ -170,7 +170,7 @@ public:
push_back(p_val);
} else {
resize(count + 1);
- for (U i = count; i > p_pos; i--) {
+ for (U i = count - 1; i > p_pos; i--) {
data[i] = data[i - 1];
}
data[p_pos] = p_val;
diff --git a/core/templates/map.h b/core/templates/map.h
index a47547d355..badb407e5d 100644
--- a/core/templates/map.h
+++ b/core/templates/map.h
@@ -36,7 +36,7 @@
#include "core/templates/pair.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
+// https://web.archive.org/web/20120507164830/https://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 {
diff --git a/core/templates/paged_allocator.h b/core/templates/paged_allocator.h
index 481289309f..dfc885c6eb 100644
--- a/core/templates/paged_allocator.h
+++ b/core/templates/paged_allocator.h
@@ -50,7 +50,8 @@ class PagedAllocator {
SpinLock spin_lock;
public:
- T *alloc() {
+ template <class... Args>
+ T *alloc(const Args &&...p_args) {
if (thread_safe) {
spin_lock.lock();
}
@@ -75,7 +76,7 @@ public:
if (thread_safe) {
spin_lock.unlock();
}
- memnew_placement(alloc, T);
+ memnew_placement(alloc, T(p_args...));
return alloc;
}
diff --git a/core/templates/pooled_list.h b/core/templates/pooled_list.h
index b4a6d2d1dd..b139dadb75 100644
--- a/core/templates/pooled_list.h
+++ b/core/templates/pooled_list.h
@@ -28,13 +28,16 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#pragma once
+#ifndef POOLED_LIST_H
+#define POOLED_LIST_H
+
+#include "core/templates/local_vector.h"
// Simple template to provide a pool with O(1) allocate and free.
// The freelist could alternatively be a linked list placed within the unused elements
// to use less memory, however a separate freelist is probably more cache friendly.
-
-// NOTE : Take great care when using this with non POD types. The construction and destruction
+//
+// NOTE: Take great care when using this with non POD types. The construction and destruction
// is done in the LocalVector, NOT as part of the pool. So requesting a new item does not guarantee
// a constructor is run, and free does not guarantee a destructor.
// You should generally handle clearing
@@ -42,9 +45,6 @@
// This is by design for fastest use in the BVH. If you want a more general pool
// that does call constructors / destructors on request / free, this should probably be
// a separate template.
-
-#include "core/templates/local_vector.h"
-
template <class T, bool force_trivial = false>
class PooledList {
LocalVector<T, uint32_t, force_trivial> list;
@@ -93,3 +93,5 @@ public:
_used_size--;
}
};
+
+#endif // POOLED_LIST_H
diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h
index 4f5c74ca46..71d41eacc4 100644
--- a/core/templates/rid_owner.h
+++ b/core/templates/rid_owner.h
@@ -53,14 +53,16 @@ protected:
return rid;
}
- static uint64_t _gen_id() {
- return base_id.increment();
- }
-
static RID _gen_rid() {
return _make_from_id(_gen_id());
}
+ friend struct VariantUtilityFunctions;
+
+ static uint64_t _gen_id() {
+ return base_id.increment();
+ }
+
public:
virtual ~RID_AllocBase() {}
};
@@ -101,7 +103,7 @@ class RID_Alloc : public RID_AllocBase {
//initialize
for (uint32_t i = 0; i < elements_in_chunk; i++) {
- //dont initialize chunk
+ // Don't initialize chunk.
validator_chunks[chunk_count][i] = 0xFFFFFFFF;
free_list_chunks[chunk_count][i] = alloc_count + i;
}
@@ -149,7 +151,7 @@ public:
return _allocate_rid();
}
- _FORCE_INLINE_ T *getornull(const RID &p_rid, bool p_initialize = false) {
+ _FORCE_INLINE_ T *get_or_null(const RID &p_rid, bool p_initialize = false) {
if (p_rid == RID()) {
return nullptr;
}
@@ -208,12 +210,12 @@ public:
return ptr;
}
void initialize_rid(RID p_rid) {
- T *mem = getornull(p_rid, true);
+ T *mem = get_or_null(p_rid, true);
ERR_FAIL_COND(!mem);
memnew_placement(mem, T);
}
void initialize_rid(RID p_rid, const T &p_value) {
- T *mem = getornull(p_rid, true);
+ T *mem = get_or_null(p_rid, true);
ERR_FAIL_COND(!mem);
memnew_placement(mem, T(p_value));
}
@@ -397,8 +399,8 @@ public:
alloc.initialize_rid(p_rid, p_ptr);
}
- _FORCE_INLINE_ T *getornull(const RID &p_rid) {
- T **ptr = alloc.getornull(p_rid);
+ _FORCE_INLINE_ T *get_or_null(const RID &p_rid) {
+ T **ptr = alloc.get_or_null(p_rid);
if (unlikely(!ptr)) {
return nullptr;
}
@@ -406,7 +408,7 @@ public:
}
_FORCE_INLINE_ void replace(const RID &p_rid, T *p_new_ptr) {
- T **ptr = alloc.getornull(p_rid);
+ T **ptr = alloc.get_or_null(p_rid);
ERR_FAIL_COND(!ptr);
*ptr = p_new_ptr;
}
@@ -467,8 +469,8 @@ public:
alloc.initialize_rid(p_rid, p_ptr);
}
- _FORCE_INLINE_ T *getornull(const RID &p_rid) {
- return alloc.getornull(p_rid);
+ _FORCE_INLINE_ T *get_or_null(const RID &p_rid) {
+ return alloc.get_or_null(p_rid);
}
_FORCE_INLINE_ bool owns(const RID &p_rid) {
diff --git a/core/templates/safe_list.h b/core/templates/safe_list.h
new file mode 100644
index 0000000000..d8f010663b
--- /dev/null
+++ b/core/templates/safe_list.h
@@ -0,0 +1,375 @@
+/*************************************************************************/
+/* safe_list.h */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2021 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_LIST_H
+#define SAFE_LIST_H
+
+#include "core/os/memory.h"
+#include "core/typedefs.h"
+#include <functional>
+
+#if !defined(NO_THREADS)
+
+#include <atomic>
+#include <type_traits>
+
+// Design goals for these classes:
+// - Accessing this list with an iterator will never result in a use-after free,
+// even if the element being accessed has been logically removed from the list on
+// another thread.
+// - Logical deletion from the list will not result in deallocation at that time,
+// instead the node will be deallocated at a later time when it is safe to do so.
+// - No blocking synchronization primitives will be used.
+
+// This is used in very specific areas of the engine where it's critical that these guarantees are held.
+
+template <class T, class A = DefaultAllocator>
+class SafeList {
+ struct SafeListNode {
+ std::atomic<SafeListNode *> next = nullptr;
+
+ // If the node is logically deleted, this pointer will typically point
+ // to the previous list item in time that was also logically deleted.
+ std::atomic<SafeListNode *> graveyard_next = nullptr;
+
+ std::function<void(T)> deletion_fn = [](T t) { return; };
+
+ T val;
+ };
+
+ static_assert(std::atomic<T>::is_always_lock_free);
+
+ std::atomic<SafeListNode *> head = nullptr;
+ std::atomic<SafeListNode *> graveyard_head = nullptr;
+
+ std::atomic_uint active_iterator_count = 0;
+
+public:
+ class Iterator {
+ friend class SafeList;
+
+ SafeListNode *cursor;
+ SafeList *list;
+
+ Iterator(SafeListNode *p_cursor, SafeList *p_list) :
+ cursor(p_cursor), list(p_list) {
+ list->active_iterator_count++;
+ }
+
+ public:
+ Iterator(const Iterator &p_other) :
+ cursor(p_other.cursor), list(p_other.list) {
+ list->active_iterator_count++;
+ }
+
+ ~Iterator() {
+ list->active_iterator_count--;
+ }
+
+ public:
+ T &operator*() {
+ return cursor->val;
+ }
+
+ Iterator &operator++() {
+ cursor = cursor->next;
+ return *this;
+ }
+
+ // These two operators are mostly useful for comparisons to nullptr.
+ bool operator==(const void *p_other) const {
+ return cursor == p_other;
+ }
+
+ bool operator!=(const void *p_other) const {
+ return cursor != p_other;
+ }
+
+ // These two allow easy range-based for loops.
+ bool operator==(const Iterator &p_other) const {
+ return cursor == p_other.cursor;
+ }
+
+ bool operator!=(const Iterator &p_other) const {
+ return cursor != p_other.cursor;
+ }
+ };
+
+public:
+ // Calling this will cause an allocation.
+ void insert(T p_value) {
+ SafeListNode *new_node = memnew_allocator(SafeListNode, A);
+ new_node->val = p_value;
+ SafeListNode *expected_head = nullptr;
+ do {
+ expected_head = head.load();
+ new_node->next.store(expected_head);
+ } while (!head.compare_exchange_strong(/* expected= */ expected_head, /* new= */ new_node));
+ }
+
+ Iterator find(T p_value) {
+ for (Iterator it = begin(); it != end(); ++it) {
+ if (*it == p_value) {
+ return it;
+ }
+ }
+ return end();
+ }
+
+ void erase(T p_value, std::function<void(T)> p_deletion_fn) {
+ Iterator tmp = find(p_value);
+ erase(tmp, p_deletion_fn);
+ }
+
+ void erase(T p_value) {
+ Iterator tmp = find(p_value);
+ erase(tmp, [](T t) { return; });
+ }
+
+ void erase(Iterator &p_iterator, std::function<void(T)> p_deletion_fn) {
+ p_iterator.cursor->deletion_fn = p_deletion_fn;
+ erase(p_iterator);
+ }
+
+ void erase(Iterator &p_iterator) {
+ if (find(p_iterator.cursor->val) == nullptr) {
+ // Not in the list, nothing to do.
+ return;
+ }
+ // First, remove the node from the list.
+ while (true) {
+ Iterator prev = begin();
+ SafeListNode *expected_head = prev.cursor;
+ for (; prev != end(); ++prev) {
+ if (prev.cursor && prev.cursor->next == p_iterator.cursor) {
+ break;
+ }
+ }
+ if (prev != end()) {
+ // There exists a node before this.
+ prev.cursor->next.store(p_iterator.cursor->next.load());
+ // Done.
+ break;
+ } else {
+ if (head.compare_exchange_strong(/* expected= */ expected_head, /* new= */ p_iterator.cursor->next.load())) {
+ // Successfully reassigned the head pointer before another thread changed it to something else.
+ break;
+ }
+ // Fall through upon failure, try again.
+ }
+ }
+ // Then queue it for deletion by putting it in the node graveyard.
+ // Don't touch `next` because an iterator might still be pointing at this node.
+ SafeListNode *expected_head = nullptr;
+ do {
+ expected_head = graveyard_head.load();
+ p_iterator.cursor->graveyard_next.store(expected_head);
+ } while (!graveyard_head.compare_exchange_strong(/* expected= */ expected_head, /* new= */ p_iterator.cursor));
+ }
+
+ Iterator begin() {
+ return Iterator(head.load(), this);
+ }
+
+ Iterator end() {
+ return Iterator(nullptr, this);
+ }
+
+ // Calling this will cause zero to many deallocations.
+ void maybe_cleanup() {
+ SafeListNode *cursor = nullptr;
+ SafeListNode *new_graveyard_head = nullptr;
+ do {
+ // The access order here is theoretically important.
+ cursor = graveyard_head.load();
+ if (active_iterator_count.load() != 0) {
+ // It's not safe to clean up with an active iterator, because that iterator
+ // could be pointing to an element that we want to delete.
+ return;
+ }
+ // Any iterator created after this point will never point to a deleted node.
+ // Swap it out with the current graveyard head.
+ } while (!graveyard_head.compare_exchange_strong(/* expected= */ cursor, /* new= */ new_graveyard_head));
+ // Our graveyard list is now unreachable by any active iterators,
+ // detached from the main graveyard head and ready for deletion.
+ while (cursor) {
+ SafeListNode *tmp = cursor;
+ cursor = cursor->graveyard_next;
+ tmp->deletion_fn(tmp->val);
+ memdelete_allocator<SafeListNode, A>(tmp);
+ }
+ }
+};
+
+#else // NO_THREADS
+
+// Effectively the same structure without the atomics. It's probably possible to simplify it but the semantics shouldn't differ greatly.
+template <class T, class A = DefaultAllocator>
+class SafeList {
+ struct SafeListNode {
+ SafeListNode *next = nullptr;
+
+ // If the node is logically deleted, this pointer will typically point to the previous list item in time that was also logically deleted.
+ SafeListNode *graveyard_next = nullptr;
+
+ std::function<void(T)> deletion_fn = [](T t) { return; };
+
+ T val;
+ };
+
+ SafeListNode *head = nullptr;
+ SafeListNode *graveyard_head = nullptr;
+
+ unsigned int active_iterator_count = 0;
+
+public:
+ class Iterator {
+ friend class SafeList;
+
+ SafeListNode *cursor;
+ SafeList *list;
+
+ public:
+ Iterator(SafeListNode *p_cursor, SafeList *p_list) :
+ cursor(p_cursor), list(p_list) {
+ list->active_iterator_count++;
+ }
+
+ ~Iterator() {
+ list->active_iterator_count--;
+ }
+
+ T &operator*() {
+ return cursor->val;
+ }
+
+ Iterator &operator++() {
+ cursor = cursor->next;
+ return *this;
+ }
+
+ // These two operators are mostly useful for comparisons to nullptr.
+ bool operator==(const void *p_other) const {
+ return cursor == p_other;
+ }
+
+ bool operator!=(const void *p_other) const {
+ return cursor != p_other;
+ }
+
+ // These two allow easy range-based for loops.
+ bool operator==(const Iterator &p_other) const {
+ return cursor == p_other.cursor;
+ }
+
+ bool operator!=(const Iterator &p_other) const {
+ return cursor != p_other.cursor;
+ }
+ };
+
+public:
+ // Calling this will cause an allocation.
+ void insert(T p_value) {
+ SafeListNode *new_node = memnew_allocator(SafeListNode, A);
+ new_node->val = p_value;
+ new_node->next = head;
+ head = new_node;
+ }
+
+ Iterator find(T p_value) {
+ for (Iterator it = begin(); it != end(); ++it) {
+ if (*it == p_value) {
+ return it;
+ }
+ }
+ return end();
+ }
+
+ void erase(T p_value, std::function<void(T)> p_deletion_fn) {
+ erase(find(p_value), p_deletion_fn);
+ }
+
+ void erase(T p_value) {
+ erase(find(p_value), [](T t) { return; });
+ }
+
+ void erase(Iterator p_iterator, std::function<void(T)> p_deletion_fn) {
+ p_iterator.cursor->deletion_fn = p_deletion_fn;
+ erase(p_iterator);
+ }
+
+ void erase(Iterator p_iterator) {
+ Iterator prev = begin();
+ for (; prev != end(); ++prev) {
+ if (prev.cursor && prev.cursor->next == p_iterator.cursor) {
+ break;
+ }
+ }
+ if (prev == end()) {
+ // Not in the list, nothing to do.
+ return;
+ }
+ // First, remove the node from the list.
+ prev.cursor->next = p_iterator.cursor->next;
+
+ // Then queue it for deletion by putting it in the node graveyard. Don't touch `next` because an iterator might still be pointing at this node.
+ p_iterator.cursor->graveyard_next = graveyard_head;
+ graveyard_head = p_iterator.cursor;
+ }
+
+ Iterator begin() {
+ return Iterator(head, this);
+ }
+
+ Iterator end() {
+ return Iterator(nullptr, this);
+ }
+
+ // Calling this will cause zero to many deallocations.
+ void maybe_cleanup() {
+ SafeListNode *cursor = graveyard_head;
+ if (active_iterator_count != 0) {
+ // It's not safe to clean up with an active iterator, because that iterator could be pointing to an element that we want to delete.
+ return;
+ }
+ graveyard_head = nullptr;
+ // Our graveyard list is now unreachable by any active iterators, detached from the main graveyard head and ready for deletion.
+ while (cursor) {
+ SafeListNode *tmp = cursor;
+ cursor = cursor->next;
+ tmp->deletion_fn(tmp->val);
+ memdelete_allocator<SafeListNode, A>(tmp);
+ }
+ }
+};
+
+#endif
+
+#endif // SAFE_LIST_H
diff --git a/core/templates/search_array.h b/core/templates/search_array.h
new file mode 100644
index 0000000000..8efc32df82
--- /dev/null
+++ b/core/templates/search_array.h
@@ -0,0 +1,67 @@
+/*************************************************************************/
+/* search_array.h */
+/*************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/*************************************************************************/
+/* Copyright (c) 2007-2021 Juan Linietsky, Ariel Manzur. */
+/* Copyright (c) 2014-2021 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 SEARCH_ARRAY_H
+#define SEARCH_ARRAY_H
+
+#include <core/templates/sort_array.h>
+
+template <class T, class Comparator = _DefaultComparator<T>>
+class SearchArray {
+public:
+ Comparator compare;
+
+ inline int bisect(const T *p_array, int p_len, const T &p_value, bool p_before) const {
+ int lo = 0;
+ int hi = p_len;
+ if (p_before) {
+ while (lo < hi) {
+ const int mid = (lo + hi) / 2;
+ if (compare(p_array[mid], p_value)) {
+ lo = mid + 1;
+ } else {
+ hi = mid;
+ }
+ }
+ } else {
+ while (lo < hi) {
+ const int mid = (lo + hi) / 2;
+ if (compare(p_value, p_array[mid])) {
+ hi = mid;
+ } else {
+ lo = mid + 1;
+ }
+ }
+ }
+ return lo;
+ }
+};
+
+#endif // SEARCH_ARRAY_H
diff --git a/core/templates/set.h b/core/templates/set.h
index 245c174862..0a80ceefb5 100644
--- a/core/templates/set.h
+++ b/core/templates/set.h
@@ -35,7 +35,7 @@
#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
+// https://web.archive.org/web/20120507164830/https://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
template <class T, class C = Comparator<T>, class A = DefaultAllocator>
class Set {
@@ -71,6 +71,9 @@ public:
Element *prev() {
return _prev;
}
+ T &get() {
+ return value;
+ }
const T &get() const {
return value;
};
@@ -118,8 +121,8 @@ public:
return *this;
}
- _FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
- _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
+ _FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
+ _FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
_FORCE_INLINE_ ConstIterator(const Element *p_E) { E = p_E; }
_FORCE_INLINE_ ConstIterator() {}
diff --git a/core/templates/vector.h b/core/templates/vector.h
index 08cbef6ba4..4b008a45a4 100644
--- a/core/templates/vector.h
+++ b/core/templates/vector.h
@@ -40,6 +40,7 @@
#include "core/error/error_macros.h"
#include "core/os/memory.h"
#include "core/templates/cowdata.h"
+#include "core/templates/search_array.h"
#include "core/templates/sort_array.h"
template <class T>
@@ -92,7 +93,7 @@ public:
void append_array(Vector<T> p_other);
- bool has(const T &p_val) {
+ bool has(const T &p_val) const {
return find(p_val, 0) != -1;
}
@@ -112,6 +113,11 @@ public:
sort_custom<_DefaultComparator<T>>();
}
+ int bsearch(const T &p_value, bool p_before) {
+ SearchArray<T> search;
+ return search.bisect(ptrw(), size(), p_value, p_before);
+ }
+
Vector<T> duplicate() {
return *this;
}
@@ -229,7 +235,7 @@ public:
_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return elem_ptr == b.elem_ptr; }
_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return elem_ptr != b.elem_ptr; }
- ConstIterator(T *p_ptr) { elem_ptr = p_ptr; }
+ ConstIterator(const T *p_ptr) { elem_ptr = p_ptr; }
ConstIterator() {}
ConstIterator(const ConstIterator &p_it) { elem_ptr = p_it.elem_ptr; }
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-22 05:28:09 +0000