Merge pull request #73813 from groud/improve_y_sort_performances

Greatly improve Y-sort performance on TileMaps

1 files changed, 51 insertions, 0 deletions

diff --git a/core/templates/self_list.h b/core/templates/self_list.h
index ff6fa953ae..fdf91beacc 100644
--- a/core/templates/self_list.h
+++ b/core/templates/self_list.h
@@ -105,6 +105,57 @@ public:
 			}
 		}
 
+		void sort() {
+			sort_custom<Comparator<T>>();
+		}
+
+		template <class C>
+		void sort_custom() {
+			if (_first == _last) {
+				return;
+			}
+
+			SelfList<T> *from = _first;
+			SelfList<T> *current = from;
+			SelfList<T> *to = from;
+
+			while (current) {
+				SelfList<T> *next = current->_next;
+
+				if (from != current) {
+					current->_prev = nullptr;
+					current->_next = from;
+
+					SelfList<T> *find = from;
+					C less;
+					while (find && less(*find->_self, *current->_self)) {
+						current->_prev = find;
+						current->_next = find->_next;
+						find = find->_next;
+					}
+
+					if (current->_prev) {
+						current->_prev->_next = current;
+					} else {
+						from = current;
+					}
+
+					if (current->_next) {
+						current->_next->_prev = current;
+					} else {
+						to = current;
+					}
+				} else {
+					current->_prev = nullptr;
+					current->_next = nullptr;
+				}
+
+				current = next;
+			}
+			_first = from;
+			_last = to;
+		}
+
 		_FORCE_INLINE_ SelfList<T> *first() { return _first; }
 		_FORCE_INLINE_ const SelfList<T> *first() const { return _first; }