Godot UI is quick and snappy again!

Changed linked listed sort to use auxiliary memory
this fixes user interface performance issues.

2 files changed, 56 insertions, 2 deletions

diff --git a/core/list.h b/core/list.h
index f581feb735..0e4ba71ac4 100644
--- a/core/list.h
+++ b/core/list.h
@@ -30,7 +30,7 @@
 #define GLOBALS_LIST_H
 
 #include "os/memory.h"
-
+#include "sort.h"
 
 /**
  * Generic Templatized Linked List Implementation.
@@ -551,7 +551,7 @@ public:
 	}
 			
 	template<class C>
-	void sort_custom() {
+	void sort_custom_inplace() {
 
 		if(size()<2)
 			return;
@@ -603,6 +603,58 @@ public:
 		_data->last=to;
 	}
 
+	template<class C>
+	struct AuxiliaryComparator {
+
+		C compare;
+		_FORCE_INLINE_ bool operator()(const Element *A,const Element* B) const {
+
+			return compare(A->value,B->value);
+		}
+	};
+
+	template<class C>
+	void sort_custom() {
+
+		//this version uses auxiliary memory for speed.
+		//if you don't want to use auxiliary memory, use the in_place version
+
+		int s = size();
+		if(s<2)
+			return;
+
+
+		Element **aux_buffer = memnew_arr(Element*,s);
+
+		int idx=0;
+		for(Element *E=front();E;E=E->next_ptr) {
+
+			aux_buffer[idx]=E;
+			idx++;
+		}
+
+		SortArray<Element*,AuxiliaryComparator<C> > sort;
+		sort.sort(aux_buffer,s);
+
+		_data->first=aux_buffer[0];
+		aux_buffer[0]->prev_ptr=NULL;
+		aux_buffer[0]->next_ptr=aux_buffer[1];
+
+		_data->last=aux_buffer[s-1];
+		aux_buffer[s-1]->prev_ptr=aux_buffer[s-2];
+		aux_buffer[s-1]->next_ptr=NULL;
+
+		for(int i=1;i<s-1;i++) {
+
+			aux_buffer[i]->prev_ptr=aux_buffer[i-1];
+			aux_buffer[i]->next_ptr=aux_buffer[i+1];
+
+		}
+
+		memdelete_arr(aux_buffer);
+	}
+
+
 	/**
 	 * copy constructor for the list
 	 */
diff --git a/scene/gui/control.cpp b/scene/gui/control.cpp
index 4d32c7ea9a..a8070be91d 100644
--- a/scene/gui/control.cpp
+++ b/scene/gui/control.cpp
@@ -2267,8 +2267,10 @@ void Control::_window_sort_subwindows() {
 	if (!window->subwindow_order_dirty)
 		return;
 
+
 	window->modal_stack.sort_custom<CComparator>();
 	window->subwindows.sort_custom<CComparator>();
+
 	window->subwindow_order_dirty=false;
 
 }