Dictionary keys are now sorted by insertion order

2 files changed, 89 insertions, 13 deletions

diff --git a/core/dictionary.cpp b/core/dictionary.cpp
index 62e5d6bc3c..94bb0b6e8c 100644
--- a/core/dictionary.cpp
+++ b/core/dictionary.cpp
@@ -37,18 +37,47 @@ struct _DictionaryVariantHash {
 };
 
 
+
+
+
 struct DictionaryPrivate {
 
+	struct Data {
+		Variant variant;
+		int order;
+	};
+
 	SafeRefCount refcount;
-	HashMap<Variant,Variant,_DictionaryVariantHash> variant_map;
+	HashMap<Variant,Data,_DictionaryVariantHash> variant_map;
+	int counter;
 	bool shared;
 
 };
 
+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;
+	}
+};
 
 void Dictionary::get_key_list( List<Variant> *p_keys) const {
 
-	_p->variant_map.get_key_list(p_keys);
+	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);
+	}
+
 }
 
 void Dictionary::_copy_on_write() const {
@@ -69,30 +98,52 @@ Variant& Dictionary::operator[](const Variant& p_key) {
 
 	_copy_on_write();
 
-	return _p->variant_map[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;
 }
 
 const Variant& Dictionary::operator[](const Variant& p_key) const {
 
-	return _p->variant_map[p_key];
+	return _p->variant_map[p_key].variant;
 
 }
 const Variant* Dictionary::getptr(const Variant& p_key) const {
 
-	return _p->variant_map.getptr(p_key);
+	const DictionaryPrivate::Data *v =_p->variant_map.getptr(p_key);
+	if (!v)
+		return NULL;
+	else
+		return &v->variant;
 }
+
 Variant* Dictionary::getptr(const Variant& p_key) {
 
-	_copy_on_write();
-	return _p->variant_map.getptr(p_key);
+	_copy_on_write();	
+	DictionaryPrivate::Data *v =_p->variant_map.getptr(p_key);
+	if (!v)
+		return NULL;
+	else
+		return &v->variant;
+
+
 }
 
 Variant Dictionary::get_valid(const Variant& p_key) const {
 
-	const Variant *v = getptr(p_key);
+	DictionaryPrivate::Data *v =_p->variant_map.getptr(p_key);
 	if (!v)
 		return Variant();
-	return *v;
+	else
+		return v->variant;
 }
 
 
@@ -151,6 +202,7 @@ void Dictionary::clear() {
 
 	_copy_on_write();
 	_p->variant_map.clear();
+	_p->counter=0;
 }
 
 bool Dictionary::is_shared() const {
@@ -203,11 +255,20 @@ Array Dictionary::values() const {
 
 	Array varr;
 	varr.resize(size());
-	const Variant *key=NULL;
-	int i=0;
-	while((key=next(key))){
-		varr[i++] = _p->variant_map[*key];
+	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;
 	}
+
 	return varr;
 }
 
@@ -269,6 +330,7 @@ Dictionary::Dictionary(bool p_shared) {
 
 	_p=memnew( DictionaryPrivate );
 	_p->refcount.init();
+	_p->counter=0;
 	_p->shared=p_shared;
 
 }
diff --git a/core/hash_map.h b/core/hash_map.h
index 523a4a6214..fba12b55ec 100644
--- a/core/hash_map.h
+++ b/core/hash_map.h
@@ -596,6 +596,20 @@ public:
 		hash_table_power=0;
 	}
 
+	void get_key_value_ptr_array(const Pair **p_pairs) const {
+		if (!hash_table)
+			return;
+		for(int i=0;i<(1<<hash_table_power);i++) {
+
+			Entry *e=hash_table[i];
+			while(e) {
+				*p_pairs=&e->pair;
+				p_pairs++;
+				e=e->next;
+			}
+		}
+	}
+
 	void get_key_list(List<TKey> *p_keys) const {
 		if (!hash_table)
 			return;