Merge pull request #12656 from karroffel/dictionary-ordered-hashmap

make Dictionary use OrderedHashMap

1 files changed, 35 insertions, 68 deletions

diff --git a/core/dictionary.cpp b/core/dictionary.cpp
index bb2e892951..1b431f9ec9 100644
--- a/core/dictionary.cpp
+++ b/core/dictionary.cpp
@@ -29,6 +29,7 @@
 /*************************************************************************/
 #include "dictionary.h"
 
+#include "ordered_hash_map.h"
 #include "safe_refcount.h"
 #include "variant.h"
 
@@ -39,22 +40,8 @@ struct _DictionaryVariantHash {
 
 struct DictionaryPrivate {
 
-	struct Data {
-		Variant variant;
-		int order;
-	};
-
 	SafeRefCount refcount;
-	HashMap<Variant, Data, _DictionaryVariantHash> variant_map;
-	int counter;
-};
-
-struct DictionaryPrivateSort {
-
-	bool operator()(const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *A, const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *B) const {
-
-		return A->data.order < B->data.order;
-	}
+	OrderedHashMap<Variant, Variant, _DictionaryVariantHash> variant_map;
 };
 
 void Dictionary::get_key_list(List<Variant> *p_keys) const {
@@ -62,61 +49,45 @@ void Dictionary::get_key_list(List<Variant> *p_keys) const {
 	if (_p->variant_map.empty())
 		return;
 
-	int count = _p->variant_map.size();
-	const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair **pairs = (const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair **)alloca(count * sizeof(HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *));
-	_p->variant_map.get_key_value_ptr_array(pairs);
-
-	SortArray<const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *, DictionaryPrivateSort> sort;
-	sort.sort(pairs, count);
-
-	for (int i = 0; i < count; i++) {
-		p_keys->push_back(pairs[i]->key);
+	for (OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::Element E = _p->variant_map.front(); E; E = E.next()) {
+		p_keys->push_back(E.key());
 	}
 }
 
 Variant &Dictionary::operator[](const Variant &p_key) {
 
-	DictionaryPrivate::Data *v = _p->variant_map.getptr(p_key);
-
-	if (!v) {
-
-		DictionaryPrivate::Data d;
-		d.order = _p->counter++;
-		_p->variant_map[p_key] = d;
-		v = _p->variant_map.getptr(p_key);
-	}
-	return v->variant;
+	return _p->variant_map[p_key];
 }
 
 const Variant &Dictionary::operator[](const Variant &p_key) const {
 
-	return _p->variant_map[p_key].variant;
+	return ((const OrderedHashMap<Variant, Variant, _DictionaryVariantHash> *)&_p->variant_map)->operator[](p_key);
 }
 const Variant *Dictionary::getptr(const Variant &p_key) const {
 
-	const DictionaryPrivate::Data *v = _p->variant_map.getptr(p_key);
-	if (!v)
+	OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::ConstElement E = ((const OrderedHashMap<Variant, Variant, _DictionaryVariantHash> *)&_p->variant_map)->find(p_key);
+
+	if (!E)
 		return NULL;
-	else
-		return &v->variant;
+	return &E.get();
 }
 
 Variant *Dictionary::getptr(const Variant &p_key) {
 
-	DictionaryPrivate::Data *v = _p->variant_map.getptr(p_key);
-	if (!v)
+	OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::Element E = _p->variant_map.find(p_key);
+
+	if (!E)
 		return NULL;
-	else
-		return &v->variant;
+	return &E.get();
 }
 
 Variant Dictionary::get_valid(const Variant &p_key) const {
 
-	DictionaryPrivate::Data *v = _p->variant_map.getptr(p_key);
-	if (!v)
+	OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::ConstElement E = ((const OrderedHashMap<Variant, Variant, _DictionaryVariantHash> *)&_p->variant_map)->find(p_key);
+
+	if (!E)
 		return Variant();
-	else
-		return v->variant;
+	return E.get();
 }
 
 int Dictionary::size() const {
@@ -171,7 +142,6 @@ void Dictionary::_ref(const Dictionary &p_from) const {
 void Dictionary::clear() {
 
 	_p->variant_map.clear();
-	_p->counter = 0;
 }
 
 void Dictionary::_unref() const {
@@ -205,15 +175,10 @@ Array Dictionary::keys() const {
 	if (_p->variant_map.empty())
 		return varr;
 
-	int count = _p->variant_map.size();
-	const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair **pairs = (const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair **)alloca(count * sizeof(HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *));
-	_p->variant_map.get_key_value_ptr_array(pairs);
-
-	SortArray<const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *, DictionaryPrivateSort> sort;
-	sort.sort(pairs, count);
-
-	for (int i = 0; i < count; i++) {
-		varr[i] = pairs[i]->key;
+	int i = 0;
+	for (OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::Element E = _p->variant_map.front(); E; E = E.next()) {
+		varr[i] = E.key();
+		i++;
 	}
 
 	return varr;
@@ -226,15 +191,10 @@ Array Dictionary::values() const {
 	if (_p->variant_map.empty())
 		return varr;
 
-	int count = _p->variant_map.size();
-	const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair **pairs = (const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair **)alloca(count * sizeof(HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *));
-	_p->variant_map.get_key_value_ptr_array(pairs);
-
-	SortArray<const HashMap<Variant, DictionaryPrivate::Data, _DictionaryVariantHash>::Pair *, DictionaryPrivateSort> sort;
-	sort.sort(pairs, count);
-
-	for (int i = 0; i < count; i++) {
-		varr[i] = pairs[i]->data.variant;
+	int i = 0;
+	for (OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::Element E = _p->variant_map.front(); E; E = E.next()) {
+		varr[i] = E.get();
+		i++;
 	}
 
 	return varr;
@@ -242,7 +202,15 @@ Array Dictionary::values() const {
 
 const Variant *Dictionary::next(const Variant *p_key) const {
 
-	return _p->variant_map.next(p_key);
+	if (p_key == NULL) {
+		// caller wants to get the first element
+		return &_p->variant_map.front().key();
+	}
+	OrderedHashMap<Variant, Variant, _DictionaryVariantHash>::Element E = _p->variant_map.find(*p_key);
+
+	if (E && E.next())
+		return &E.next().key();
+	return NULL;
 }
 
 Dictionary Dictionary::copy() const {
@@ -273,7 +241,6 @@ Dictionary::Dictionary() {
 
 	_p = memnew(DictionaryPrivate);
 	_p->refcount.init();
-	_p->counter = 0;
 }
 Dictionary::~Dictionary() {