summaryrefslogtreecommitdiff
path: root/core/templates
diff options
context:
space:
mode:
Diffstat (limited to 'core/templates')
-rw-r--r--core/templates/hash_map.h56
-rw-r--r--core/templates/hashfuncs.h33
-rw-r--r--core/templates/pair.h11
-rw-r--r--core/templates/rb_map.h (renamed from core/templates/map.h)36
-rw-r--r--core/templates/rb_set.h (renamed from core/templates/set.h)28
-rw-r--r--core/templates/rid_owner.h2
6 files changed, 110 insertions, 56 deletions
diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h
index 55292d3eb5..e5f73171a2 100644
--- a/core/templates/hash_map.h
+++ b/core/templates/hash_map.h
@@ -373,76 +373,80 @@ public:
/** Iterator API **/
- struct Iterator {
- _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
+ struct ConstIterator {
+ _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
return E->data;
}
- _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
- _FORCE_INLINE_ Iterator &operator++() {
+ _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+ _FORCE_INLINE_ ConstIterator &operator++() {
if (E) {
E = E->next;
}
return *this;
}
- _FORCE_INLINE_ Iterator &operator--() {
+ _FORCE_INLINE_ ConstIterator &operator--() {
if (E) {
E = E->prev;
}
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_ operator bool() const {
+ _FORCE_INLINE_ explicit operator bool() const {
return E != nullptr;
}
- _FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
- _FORCE_INLINE_ Iterator() {}
- _FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
- _FORCE_INLINE_ void operator=(const Iterator &p_it) {
+ _FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+ _FORCE_INLINE_ ConstIterator() {}
+ _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
+ _FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
E = p_it.E;
}
private:
- HashMapElement<TKey, TValue> *E = nullptr;
+ const HashMapElement<TKey, TValue> *E = nullptr;
};
- struct ConstIterator {
- _FORCE_INLINE_ const KeyValue<TKey, TValue> &operator*() const {
+ struct Iterator {
+ _FORCE_INLINE_ KeyValue<TKey, TValue> &operator*() const {
return E->data;
}
- _FORCE_INLINE_ const KeyValue<TKey, TValue> *operator->() const { return &E->data; }
- _FORCE_INLINE_ ConstIterator &operator++() {
+ _FORCE_INLINE_ KeyValue<TKey, TValue> *operator->() const { return &E->data; }
+ _FORCE_INLINE_ Iterator &operator++() {
if (E) {
E = E->next;
}
return *this;
}
- _FORCE_INLINE_ ConstIterator &operator--() {
+ _FORCE_INLINE_ Iterator &operator--() {
if (E) {
E = E->prev;
}
return *this;
}
- _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_ bool operator==(const Iterator &b) const { return E == b.E; }
+ _FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
- _FORCE_INLINE_ operator bool() const {
+ _FORCE_INLINE_ explicit operator bool() const {
return E != nullptr;
}
- _FORCE_INLINE_ ConstIterator(const HashMapElement<TKey, TValue> *p_E) { E = p_E; }
- _FORCE_INLINE_ ConstIterator() {}
- _FORCE_INLINE_ ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
- _FORCE_INLINE_ void operator=(const ConstIterator &p_it) {
+ _FORCE_INLINE_ Iterator(HashMapElement<TKey, TValue> *p_E) { E = p_E; }
+ _FORCE_INLINE_ Iterator() {}
+ _FORCE_INLINE_ Iterator(const Iterator &p_it) { E = p_it.E; }
+ _FORCE_INLINE_ void operator=(const Iterator &p_it) {
E = p_it.E;
}
+ operator ConstIterator() const {
+ return ConstIterator(E);
+ }
+
private:
- const HashMapElement<TKey, TValue> *E = nullptr;
+ HashMapElement<TKey, TValue> *E = nullptr;
};
_FORCE_INLINE_ Iterator begin() {
diff --git a/core/templates/hashfuncs.h b/core/templates/hashfuncs.h
index eb73ff4ede..1330d55270 100644
--- a/core/templates/hashfuncs.h
+++ b/core/templates/hashfuncs.h
@@ -163,6 +163,9 @@ static inline uint64_t make_uint64_t(T p_in) {
return _u._u64;
}
+template <class T>
+class Ref;
+
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); }
@@ -186,6 +189,12 @@ struct HashMapHasherDefault {
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(); }
+ template <class T>
+ static _FORCE_INLINE_ uint32_t hash(const T *p_pointer) { return hash_one_uint64((uint64_t)p_pointer); }
+
+ template <class T>
+ static _FORCE_INLINE_ uint32_t hash(const Ref<T> &p_ref) { return hash_one_uint64((uint64_t)p_ref.operator->()); }
+
static _FORCE_INLINE_ uint32_t hash(const Vector2i &p_vec) {
uint32_t h = hash_djb2_one_32(p_vec.x);
return hash_djb2_one_32(p_vec.y, h);
@@ -237,16 +246,36 @@ 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) {
+template <>
+struct HashMapComparatorDefault<float> {
+ static 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) {
+template <>
+struct HashMapComparatorDefault<double> {
+ static 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));
}
};
+template <>
+struct HashMapComparatorDefault<Vector2> {
+ static bool compare(const Vector2 &p_lhs, const Vector2 &p_rhs) {
+ return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y)));
+ }
+};
+
+template <>
+struct HashMapComparatorDefault<Vector3> {
+ static bool compare(const Vector3 &p_lhs, const Vector3 &p_rhs) {
+ return ((p_lhs.x == p_rhs.x) || (Math::is_nan(p_lhs.x) && Math::is_nan(p_rhs.x))) && ((p_lhs.y == p_rhs.y) || (Math::is_nan(p_lhs.y) && Math::is_nan(p_rhs.y))) && ((p_lhs.z == p_rhs.z) || (Math::is_nan(p_lhs.z) && Math::is_nan(p_rhs.z)));
+ }
+};
+
constexpr uint32_t HASH_TABLE_SIZE_MAX = 29;
const uint32_t hash_table_size_primes[HASH_TABLE_SIZE_MAX] = {
diff --git a/core/templates/pair.h b/core/templates/pair.h
index eb86e21b03..6d33213fe3 100644
--- a/core/templates/pair.h
+++ b/core/templates/pair.h
@@ -31,8 +31,8 @@
#ifndef PAIR_H
#define PAIR_H
+#include "core/templates/hashfuncs.h"
#include "core/typedefs.h"
-
template <class F, class S>
struct Pair {
F first;
@@ -69,6 +69,15 @@ struct PairSort {
}
};
+template <class F, class S>
+struct PairHash {
+ static uint32_t hash(const Pair<F, S> &P) {
+ uint64_t h1 = HashMapHasherDefault::hash(P.first);
+ uint64_t h2 = HashMapHasherDefault::hash(P.second);
+ return hash_one_uint64((h1 << 32) | h2);
+ }
+};
+
template <class K, class V>
struct KeyValue {
const K key;
diff --git a/core/templates/map.h b/core/templates/rb_map.h
index c54da1dc03..c732ccd485 100644
--- a/core/templates/map.h
+++ b/core/templates/rb_map.h
@@ -1,5 +1,5 @@
/*************************************************************************/
-/* map.h */
+/* rb_map.h */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
@@ -28,8 +28,8 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#ifndef MAP_H
-#define MAP_H
+#ifndef RB_MAP_H
+#define RB_MAP_H
#include "core/error/error_macros.h"
#include "core/os/memory.h"
@@ -39,7 +39,7 @@
// 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 {
+class RBMap {
enum Color {
RED,
BLACK
@@ -49,7 +49,7 @@ class Map {
public:
class Element {
private:
- friend class Map<K, V, C, A>;
+ friend class RBMap<K, V, C, A>;
int color = RED;
Element *right = nullptr;
Element *left = nullptr;
@@ -111,7 +111,9 @@ public:
_FORCE_INLINE_ bool operator==(const Iterator &b) const { return E == b.E; }
_FORCE_INLINE_ bool operator!=(const Iterator &b) const { return E != b.E; }
-
+ explicit operator bool() const {
+ return E != nullptr;
+ }
Iterator(Element *p_E) { E = p_E; }
Iterator() {}
Iterator(const Iterator &p_it) { E = p_it.E; }
@@ -136,7 +138,9 @@ public:
_FORCE_INLINE_ bool operator==(const ConstIterator &b) const { return E == b.E; }
_FORCE_INLINE_ bool operator!=(const ConstIterator &b) const { return E != b.E; }
-
+ explicit operator bool() const {
+ return E != nullptr;
+ }
ConstIterator(const Element *p_E) { E = p_E; }
ConstIterator() {}
ConstIterator(const ConstIterator &p_it) { E = p_it.E; }
@@ -572,7 +576,7 @@ private:
memdelete_allocator<Element, A>(p_element);
}
- void _copy_from(const Map &p_map) {
+ void _copy_from(const RBMap &p_map) {
clear();
// not the fastest way, but safeset to write.
for (Element *I = p_map.front(); I; I = I->next()) {
@@ -710,8 +714,12 @@ public:
return e;
}
- inline bool is_empty() const { return _data.size_cache == 0; }
- inline int size() const { return _data.size_cache; }
+ inline bool is_empty() const {
+ return _data.size_cache == 0;
+ }
+ inline int size() const {
+ return _data.size_cache;
+ }
int calculate_depth() const {
// used for debug mostly
@@ -735,17 +743,17 @@ public:
_data._free_root();
}
- void operator=(const Map &p_map) {
+ void operator=(const RBMap &p_map) {
_copy_from(p_map);
}
- Map(const Map &p_map) {
+ RBMap(const RBMap &p_map) {
_copy_from(p_map);
}
- _FORCE_INLINE_ Map() {}
+ _FORCE_INLINE_ RBMap() {}
- ~Map() {
+ ~RBMap() {
clear();
}
};
diff --git a/core/templates/set.h b/core/templates/rb_set.h
index a8a0a77712..2de816769c 100644
--- a/core/templates/set.h
+++ b/core/templates/rb_set.h
@@ -1,5 +1,5 @@
/*************************************************************************/
-/* set.h */
+/* rb_set.h */
/*************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
@@ -28,8 +28,8 @@
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/*************************************************************************/
-#ifndef SET_H
-#define SET_H
+#ifndef RB_SET_H
+#define RB_SET_H
#include "core/os/memory.h"
#include "core/typedefs.h"
@@ -38,7 +38,7 @@
// 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 {
+class RBSet {
enum Color {
RED,
BLACK
@@ -48,7 +48,7 @@ class Set {
public:
class Element {
private:
- friend class Set<T, C, A>;
+ friend class RBSet<T, C, A>;
int color = RED;
Element *right = nullptr;
Element *left = nullptr;
@@ -554,7 +554,7 @@ private:
memdelete_allocator<Element, A>(p_element);
}
- void _copy_from(const Set &p_set) {
+ void _copy_from(const RBSet &p_set) {
clear();
// not the fastest way, but safeset to write.
for (Element *I = p_set.front(); I; I = I->next()) {
@@ -661,8 +661,12 @@ public:
return e;
}
- inline bool is_empty() const { return _data.size_cache == 0; }
- inline int size() const { return _data.size_cache; }
+ inline bool is_empty() const {
+ return _data.size_cache == 0;
+ }
+ inline int size() const {
+ return _data.size_cache;
+ }
int calculate_depth() const {
// used for debug mostly
@@ -686,17 +690,17 @@ public:
_data._free_root();
}
- void operator=(const Set &p_set) {
+ void operator=(const RBSet &p_set) {
_copy_from(p_set);
}
- Set(const Set &p_set) {
+ RBSet(const RBSet &p_set) {
_copy_from(p_set);
}
- _FORCE_INLINE_ Set() {}
+ _FORCE_INLINE_ RBSet() {}
- ~Set() {
+ ~RBSet() {
clear();
}
};
diff --git a/core/templates/rid_owner.h b/core/templates/rid_owner.h
index 95632cdec2..d26977380e 100644
--- a/core/templates/rid_owner.h
+++ b/core/templates/rid_owner.h
@@ -36,9 +36,9 @@
#include "core/string/print_string.h"
#include "core/templates/list.h"
#include "core/templates/oa_hash_map.h"
+#include "core/templates/rb_set.h"
#include "core/templates/rid.h"
#include "core/templates/safe_refcount.h"
-#include "core/templates/set.h"
#include <stdio.h>
#include <typeinfo>
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 01:12:01 +0000