(svn r13516) -Codechange: Move MemCpyT to a fitting core header

-Codechange: Split the sorting code from the sortlist to an appropriate header

7 files changed, 172 insertions, 64 deletions

diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj
index ef5e2f9ec..9435e47f4 100644
--- a/projects/openttd_vs80.vcproj
+++ b/projects/openttd_vs80.vcproj
@@ -1124,6 +1124,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\core\mem_func.hpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\minilzo.h"
 				>
 			</File>
@@ -1444,6 +1448,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\core\sort_func.hpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\sortlist_type.h"
 				>
 			</File>
diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj
index 2e6224d62..46973b67a 100644
--- a/projects/openttd_vs90.vcproj
+++ b/projects/openttd_vs90.vcproj
@@ -1121,6 +1121,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\core\mem_func.hpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\minilzo.h"
 				>
 			</File>
@@ -1441,6 +1445,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\core\sort_func.hpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\sortlist_type.h"
 				>
 			</File>
diff --git a/source.list b/source.list
index 4e873c268..e5ae95c6e 100644
--- a/source.list
+++ b/source.list
@@ -206,6 +206,7 @@ map_func.h
 map_type.h
 core/math_func.hpp
 md5.h
+core/mem_func.hpp
 minilzo.h
 mixer.h
 music.h
@@ -286,6 +287,7 @@ signs_func.h
 signs_type.h
 slope_func.h
 slope_type.h
+core/sort_func.hpp
 sortlist_type.h
 sound_func.h
 sound_type.h
diff --git a/src/core/mem_func.hpp b/src/core/mem_func.hpp
new file mode 100644
index 000000000..5a2a6bcb3
--- /dev/null
+++ b/src/core/mem_func.hpp
@@ -0,0 +1,57 @@
+/* $Id$ */
+
+/** @file mem_func.hpp Functions related to memory operations. */
+
+#ifndef MEM_FUNC_HPP
+#define MEM_FUNC_HPP
+
+#include <string.h>
+#include "math_func.hpp"
+
+/**
+ * Type-safe version of memcpy().
+ *
+ * @param destination Pointer to the destination buffer
+ * @param source Pointer to the source buffer
+ * @param num number of items to be copied. (!not number of bytes!)
+ */
+template <typename T>
+FORCEINLINE void MemCpyT(T *destination, const T *source, uint num = 1)
+{
+	memcpy(destination, source, num * sizeof(T));
+}
+
+/**
+ * Type safe memory reverse operation.
+ *  Reverse a block of memory in steps given by the
+ *  type of the pointers.
+ *
+ * @param ptr1 Start-pointer to the block of memory.
+ * @param ptr2 End-pointer to the block of memory.
+ */
+template<typename T>
+FORCEINLINE void MemReverseT(T *ptr1, T *ptr2)
+{
+	assert(ptr1 != NULL && ptr2 != NULL);
+	assert(ptr1 < ptr2);
+
+	do {
+		Swap(*ptr1, *ptr2);
+	} while (++ptr1 < --ptr2);
+}
+
+/**
+ * Type safe memory reverse operation (overloaded)
+ *
+ * @param ptr Pointer to the block of memory.
+ * @param num The number of items we want to reverse.
+ */
+template<typename T>
+FORCEINLINE void MemReverseT(T *ptr, uint num)
+{
+	assert(ptr != NULL);
+
+	MemReverseT(ptr, ptr + (num - 1));
+}
+
+#endif /* MEM_FUNC_HPP */
diff --git a/src/core/sort_func.hpp b/src/core/sort_func.hpp
new file mode 100644
index 000000000..826fa278d
--- /dev/null
+++ b/src/core/sort_func.hpp
@@ -0,0 +1,85 @@
+/* $Id$ */
+
+/** @file sort_func.hpp Functions related to sorting operations. */
+
+#ifndef SORT_FUNC_HPP
+#define SORT_FUNC_HPP
+
+#include <stdlib.h>
+#include "math_func.hpp"
+#include "mem_func.hpp"
+
+/**
+ * Type safe qsort()
+ *
+ * @todo replace the normal qsort with this one
+ * @note Use this sort for irregular sorted data.
+ *
+ * @param base Pointer to the first element of the array to be sorted.
+ * @param num Number of elements in the array pointed by base.
+ * @param comparator Function that compares two elements.
+ * @param desc Sort descending.
+ */
+template<typename T>
+FORCEINLINE void QSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
+{
+	if (num < 2) return;
+
+	qsort(base, num, sizeof(T), (int (CDECL *)(const void *, const void *))comparator);
+
+	if (desc) MemReverseT(base, num);
+}
+
+/**
+ * Type safe Gnome Sort.
+ *
+ * This is a slightly modifyied Gnome search. The basic
+ * Gnome search trys to sort already sorted list parts.
+ * The modification skips these.
+ *
+ * @note Use this sort for presorted / regular sorted data.
+ *
+ * @param base Pointer to the first element of the array to be sorted.
+ * @param num Number of elements in the array pointed by base.
+ * @param comparator Function that compares two elements.
+ * @param desc Sort descending.
+ */
+template<typename T>
+FORCEINLINE void GSortT(T *base, uint num, int (CDECL *comparator)(const T*, const T*), bool desc = false)
+{
+	if (num < 2) return;
+
+	assert(base != NULL);
+	assert(comparator != NULL);
+
+	T *a = base;
+	T *b = base + 1;
+	uint offset = 0;
+
+	while (num > 1) {
+		const int diff = comparator(a, b);
+		if ((!desc && diff <= 0) || (desc && diff >= 0)) {
+			if (offset != 0) {
+				/* Jump back to the last direction switch point */
+				a += offset;
+				b += offset;
+				offset = 0;
+				continue;
+			}
+
+			a++;
+			b++;
+			num--;
+		} else {
+			Swap(*a, *b);
+
+			if (a == base) continue;
+
+			a--;
+			b--;
+			offset++;
+		}
+	}
+}
+
+#endif /* SORT_FUNC_HPP */
diff --git a/src/misc/blob.hpp b/src/misc/blob.hpp
index c96902997..12f7e54ff 100644
--- a/src/misc/blob.hpp
+++ b/src/misc/blob.hpp
@@ -6,16 +6,7 @@
 #define BLOB_HPP
 
 #include "../core/alloc_func.hpp"
-
-/** Type-safe version of memcpy().
- * @param d destination buffer
- * @param s source buffer
- * @param num_items number of items to be copied (!not number of bytes!) */
-template <class Titem_>
-FORCEINLINE void MemCpyT(Titem_* d, const Titem_* s, int num_items = 1)
-{
-	memcpy(d, s, num_items * sizeof(Titem_));
-}
+#include "../core/mem_func.hpp"
 
 /** Base class for simple binary blobs.
 *  Item is byte.
diff --git a/src/sortlist_type.h b/src/sortlist_type.h
index 46185d503..07591bbd4 100644
--- a/src/sortlist_type.h
+++ b/src/sortlist_type.h
@@ -7,6 +7,8 @@
 
 #include "core/enum_type.hpp"
 #include "core/bitmath_func.hpp"
+#include "core/mem_func.hpp"
+#include "core/sort_func.hpp"
 #include "misc/smallvec.h"
 #include "date_type.h"
 
@@ -55,21 +57,6 @@ public: // Temporary: public for conversion only
 		this->resort_timer = DAY_TICKS * 10;
 	}
 
-	/**
-	 * Reverse the list
-	 */
-	void Reverse()
-	{
-		assert(this->IsSortable());
-
-		T *a = this->data;
-		T *b = a + (this->items - 1);
-
-		do {
-			Swap(*a, *b);
-		} while (++a < --b);
-	}
-
 public:
 	GUIList() :
 		func_list(NULL),
@@ -174,25 +161,23 @@ public:
 	 *  Since that is the worst condition for the sort function
 	 *  reverse the list here.
 	 */
-	FORCEINLINE void ToggleSortOrder()
+	void ToggleSortOrder()
 	{
 		this->flags ^= VL_DESC;
 
-		if (this->IsSortable()) this->Reverse();
+		if (this->IsSortable()) MemReverseT(this->data, this->items);
 	}
 
 	/**
-	 * GnomeSort algorithm
-	 *  This sorting uses a slightly modifyied Gnome search.
-	 *  The basic Gnome search trys to sort already sorted
-	 *  list parts. The modification skips these. For the first
-	 *  sorting we use qsort since it is faster for irregular
-	 *  sorted data.
+	 * Sort the list.
+	 *  For the first sorting we use qsort since it is
+	 *  faster for irregular sorted data. After that we
+	 *  use gsort.
 	 *
 	 * @param compare The function to compare two list items
 	 * @return true if the list sequence has been altered
 	 * */
-	FORCEINLINE bool Sort(SortFunction *compare)
+	bool Sort(SortFunction *compare)
 	{
 		/* Do not sort if the resort bit is not set */
 		if (!HASBITS(this->flags, VL_RESORT)) return false;
@@ -208,40 +193,12 @@ public:
 
 		if (HASBITS(this->flags, VL_FIRST_SORT)) {
 			CLRBITS(this->flags, VL_FIRST_SORT);
-			qsort(this->data, this->items, sizeof(T), (int (CDECL *)(const void *, const void *))compare);
 
-			if (desc) this->Reverse();
+			QSortT(this->data, this->items, compare, desc);
 			return true;
 		}
 
-		T *a = this->data;
-		T *b = a + 1;
-
-		uint length = this->items;
-		uint offset = 0; // Jump variable
-
-		while (length > 1) {
-			const int diff = compare(a, b);
-			if ((!desc && diff <= 0) || (desc && diff >= 0)) {
-				if (offset != 0) {
-					/* Jump back to the last direction switch point */
-					a += offset;
-					b += offset;
-					offset = 0;
-					continue;
-				}
-				a++;
-				b++;
-				length--;
-			} else {
-				Swap(*a, *b);
-				if (a != this->data) {
-					offset++;
-					a--;
-					b--;
-				}
-			}
-		}
+		GSortT(this->data, this->items, compare, desc);
 		return true;
 	}