summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--projects/openttd_vs80.vcproj8
-rw-r--r--projects/openttd_vs90.vcproj8
-rw-r--r--source.list2
-rw-r--r--src/core/mem_func.hpp57
-rw-r--r--src/core/sort_func.hpp85
-rw-r--r--src/misc/blob.hpp11
-rw-r--r--src/sortlist_type.h65
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;
}
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-27 09:07:33 +0000