From 4333aa240c68f22b235981bed56d11a592fdfd1d Mon Sep 17 00:00:00 2001
From: Juan Linietsky <reduzio@gmail.com>
Date: Sun, 15 Feb 2015 12:38:25 -0300
Subject: Godot UI is quick and snappy again!

Changed linked listed sort to use auxiliary memory
this fixes user interface performance issues.
---
 core/list.h | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 54 insertions(+), 2 deletions(-)

(limited to 'core/list.h')

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
 	 */
-- 
cgit v1.2.3