summaryrefslogtreecommitdiffstats
path: root/core
diff options
context:
space:
mode:
Diffstat (limited to 'core')
-rw-r--r--core/templates/hash_map.cpp43
-rw-r--r--core/templates/hash_map.h43
-rw-r--r--core/variant/dictionary.cpp5
-rw-r--r--core/variant/dictionary.h1
-rw-r--r--core/variant/variant_call.cpp1
5 files changed, 93 insertions, 0 deletions
diff --git a/core/templates/hash_map.cpp b/core/templates/hash_map.cpp
new file mode 100644
index 0000000000..93664dd2e1
--- /dev/null
+++ b/core/templates/hash_map.cpp
@@ -0,0 +1,43 @@
+/**************************************************************************/
+/* hash_map.cpp */
+/**************************************************************************/
+/* This file is part of: */
+/* GODOT ENGINE */
+/* https://godotengine.org */
+/**************************************************************************/
+/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
+/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
+/* */
+/* 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 "hash_map.h"
+
+#include "core/variant/variant.h"
+
+bool _hashmap_variant_less_than(const Variant &p_left, const Variant &p_right) {
+ bool valid = false;
+ Variant res;
+ Variant::evaluate(Variant::OP_LESS, p_left, p_right, res, valid);
+ if (!valid) {
+ res = false;
+ }
+ return res;
+}
diff --git a/core/templates/hash_map.h b/core/templates/hash_map.h
index a3e8c2c788..329952e8d4 100644
--- a/core/templates/hash_map.h
+++ b/core/templates/hash_map.h
@@ -61,6 +61,8 @@ struct HashMapElement {
data(p_key, p_value) {}
};
+bool _hashmap_variant_less_than(const Variant &p_left, const Variant &p_right);
+
template <typename TKey, typename TValue,
typename Hasher = HashMapHasherDefault,
typename Comparator = HashMapComparatorDefault<TKey>,
@@ -271,6 +273,47 @@ public:
num_elements = 0;
}
+ void sort() {
+ if (elements == nullptr || num_elements < 2) {
+ return; // An empty or single element HashMap is already sorted.
+ }
+ // Use insertion sort because we want this operation to be fast for the
+ // common case where the input is already sorted or nearly sorted.
+ HashMapElement<TKey, TValue> *inserting = head_element->next;
+ while (inserting != nullptr) {
+ HashMapElement<TKey, TValue> *after = nullptr;
+ for (HashMapElement<TKey, TValue> *current = inserting->prev; current != nullptr; current = current->prev) {
+ if (_hashmap_variant_less_than(inserting->data.key, current->data.key)) {
+ after = current;
+ } else {
+ break;
+ }
+ }
+ HashMapElement<TKey, TValue> *next = inserting->next;
+ if (after != nullptr) {
+ // Modify the elements around `inserting` to remove it from its current position.
+ inserting->prev->next = next;
+ if (next == nullptr) {
+ tail_element = inserting->prev;
+ } else {
+ next->prev = inserting->prev;
+ }
+ // Modify `before` and `after` to insert `inserting` between them.
+ HashMapElement<TKey, TValue> *before = after->prev;
+ if (before == nullptr) {
+ head_element = inserting;
+ } else {
+ before->next = inserting;
+ }
+ after->prev = inserting;
+ // Point `inserting` to its new surroundings.
+ inserting->prev = before;
+ inserting->next = after;
+ }
+ inserting = next;
+ }
+ }
+
TValue &get(const TKey &p_key) {
uint32_t pos = 0;
bool exists = _lookup_pos(p_key, pos);
diff --git a/core/variant/dictionary.cpp b/core/variant/dictionary.cpp
index 2db754438f..501ca69205 100644
--- a/core/variant/dictionary.cpp
+++ b/core/variant/dictionary.cpp
@@ -294,6 +294,11 @@ void Dictionary::clear() {
_p->variant_map.clear();
}
+void Dictionary::sort() {
+ ERR_FAIL_COND_MSG(_p->read_only, "Dictionary is in read-only state.");
+ _p->variant_map.sort();
+}
+
void Dictionary::merge(const Dictionary &p_dictionary, bool p_overwrite) {
ERR_FAIL_COND_MSG(_p->read_only, "Dictionary is in read-only state.");
for (const KeyValue<Variant, Variant> &E : p_dictionary._p->variant_map) {
diff --git a/core/variant/dictionary.h b/core/variant/dictionary.h
index 5f3ce40219..bbfb5b3083 100644
--- a/core/variant/dictionary.h
+++ b/core/variant/dictionary.h
@@ -64,6 +64,7 @@ public:
int size() const;
bool is_empty() const;
void clear();
+ void sort();
void merge(const Dictionary &p_dictionary, bool p_overwrite = false);
Dictionary merged(const Dictionary &p_dictionary, bool p_overwrite = false) const;
diff --git a/core/variant/variant_call.cpp b/core/variant/variant_call.cpp
index ab33c9db55..29e11462c9 100644
--- a/core/variant/variant_call.cpp
+++ b/core/variant/variant_call.cpp
@@ -2272,6 +2272,7 @@ static void _register_variant_builtin_methods_misc() {
bind_method(Dictionary, is_empty, sarray(), varray());
bind_method(Dictionary, clear, sarray(), varray());
bind_method(Dictionary, assign, sarray("dictionary"), varray());
+ bind_method(Dictionary, sort, sarray(), varray());
bind_method(Dictionary, merge, sarray("dictionary", "overwrite"), varray(false));
bind_method(Dictionary, merged, sarray("dictionary", "overwrite"), varray(false));
bind_method(Dictionary, has, sarray("key"), varray());