From 96fc91baf333b6fb874f53bf4cf0a744bd0303aa Mon Sep 17 00:00:00 2001
From: skidd13 <skidd13@openttd.org>
Date: Sat, 14 Jun 2008 16:23:08 +0000
Subject: (svn r13516) -Codechange: Move MemCpyT to a fitting core header
 -Codechange: Split the sorting code from the sortlist to an appropriate
 header

---
 src/core/mem_func.hpp  | 57 +++++++++++++++++++++++++++++++++
 src/core/sort_func.hpp | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 142 insertions(+)
 create mode 100644 src/core/mem_func.hpp
 create mode 100644 src/core/sort_func.hpp

(limited to 'src/core')

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