ecere/com/containers: Sort() method

- Takes a bool ascending parameter
- Default Merge Sort algorithm in Container base class
- Overriding with Quick Sort invocation in Array
- Using sort_r() method from Isaac Turner nicely wrapping qsort_r, qsort_s and a fallback Quick Sort implementation
- Non-integer indexed classes (e.g. (Custom)AVLTree, Map) do not require sorting
- June 23rd, 2016 eC Meetup Ottawa
- LinkList and List Sort() optimizations
- Array Sort optimizations:
   - OnCompare called directly from qsort*() when possible
   - Moved branching outside qsort*() calls
   - Faster & Better fall-back algorithm by Darel Rex Finley
   - Made qsortr() and qsortrx() public
- Container: Pre-allocation optimization in base Container

diff --git a/ecere/src/com/containers/Array.ec b/ecere/src/com/containers/Array.ec
index 739fadc..b1d3840 100644 (file)
--- a/ecere/src/com/containers/Array.ec
+++ b/ecere/src/com/containers/Array.ec
@@ -8,8 +8,146 @@ import "Container"
 
 default:
 extern int __ecereVMethodID_class_OnUnserialize;
+extern int __ecereVMethodID_class_OnCompare;
+
+// qsort_r/_s wrappers adapted from public domain code by Isaac Turner
+#if (defined __APPLE__ || defined __MACH__ || defined __DARWIN__ || defined __FreeBSD__ || defined __BSD__ || defined __bsdi__ || defined OpenBSD3_1 || defined OpenBSD3_9 || defined __OpenBSD__ || \
+     defined __NetBSD__ || defined __DragonFly__ || defined AMIGA)
+   #define BSD
+   extern void qsort_r(void *base, uintsize nel, uintsize width, void *arg, int (*compare)(void *, const void *, const void *));
+#elif defined(__WIN32__)
+   extern void qsort_s(void *base, uintsize nel, uintsize width, int (*compare)(void *, const void *, const void *), void * arg);
+#elif (defined __GLIBC__ && ((__GLIBC__ > 2) || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 8)))
+   #define GLIBC
+   extern void qsort_r(void *base, uintsize nel, uintsize width, int(* compare)(const void *, const void *, void *), void *arg);
+#endif
 private:
 
+// Quick Sort algorithm adapted from public domain code by Darel Rex Finley
+static inline void quickSort(void *base, uintsize nel, uintsize w, char * piv, int (*compare)(void *, const void *, const void *), void *arg)
+{
+   #define MAX_LEVELS  300
+   uintsize beg[MAX_LEVELS], end[MAX_LEVELS];
+   int frame = 0;
+
+   beg[0] = 0;
+   end[0] = nel;
+   while(frame >= 0)
+   {
+      uintsize L = beg[frame], R = end[frame]-1;
+      if(L < R)
+      {
+         memcpy(piv, (char *)base + L*w, w);
+         while(L < R)
+         {
+            while(compare(arg, (char *)base + (R*w), piv) >= 0 && L < R) R--;
+            if(L < R)
+            {
+               memcpy((char *)base + L*w, (char *)base + R*w, w);
+               L++;
+            }
+            while(compare(arg, (char *)base + (L*w), piv) <= 0 && L < R) L++;
+            if(L < R)
+            {
+               memcpy((char *)base + R*w, (char *)base + L*w, w);
+               R--;
+            }
+         }
+         memcpy((char *)base + L*w, piv, w);
+         beg[frame+1] = L+1;
+         end[frame+1] = end[frame];
+         end[frame++] = L;
+
+         // Process smaller partition first
+         if(end[frame]-beg[frame] > end[frame-1]-beg[frame-1])
+         {
+            uintsize swap;
+            swap = beg[frame]; beg[frame] = beg[frame-1]; beg[frame-1] = swap;
+            swap = end[frame]; end[frame] = end[frame-1]; end[frame-1] = swap;
+         }
+      }
+      else
+         frame--;
+   }
+   #undef MAX_LEVELS
+}
+
+static struct SortRData { void *arg; int (*compare)(void *, const void *, const void *); };
+
+static inline int compareDeref            (SortRData cs, const void **a, const void **b)  { return  cs.compare(cs.arg, *a, *b); }
+static inline int compareDescDeref        (SortRData cs, const void **a, const void **b)  { return -cs.compare(cs.arg, *a, *b); }
+static inline int compareDesc             (SortRData cs, const void * a, const void * b)  { return -cs.compare(cs.arg,  a,  b); }
+
+static inline int compareArgLast          (const void * a, const void * b, SortRData cs)  { return  cs.compare(cs.arg,  a,  b); }
+static inline int compareDerefArgLast     (const void **a, const void **b, SortRData cs)  { return  cs.compare(cs.arg, *a, *b); }
+static inline int compareDescDerefArgLast (const void **a, const void **b, SortRData cs)  { return -cs.compare(cs.arg, *a, *b); }
+static inline int compareDescArgLast      (const void * a, const void * b, SortRData cs)  { return -cs.compare(cs.arg,  a,  b); }
+
+static inline void _qsortrx(void *base, uintsize nel, uintsize width,
+   int (*compare)(void *arg, const void *a, const void *b),
+   int (*optCompareArgLast)(const void *a, const void *b, void *arg),
+   void *arg,
+   bool deref, bool ascending)
+{
+#if defined(GLIBC)
+   if(!deref && ascending && optCompareArgLast)
+      qsort_r(base, nel, width, optCompareArgLast, arg);
+   else
+   {
+      SortRData s { arg, compare };
+      #define compare_fn !deref && ascending ? compareArgLast : !deref ? compareDescArgLast : ascending ? compareDerefArgLast : compareDescDerefArgLast
+      qsort_r(base, nel, width, compare_fn, s);
+      #undef compare_fn
+   }
+#else
+   if(!deref && ascending)
+   {
+   #if defined(BSD)
+      qsort_r(base, nel, width, arg, compare);
+   #elif defined(__WIN32__)
+      qsort_s(base, nel, width, compare, arg);
+   #else
+      {
+         char * buf = new char[width];
+         quickSort(base, nel, width, buf, compare, arg);
+         delete buf;
+      }
+   #endif
+   }
+   else
+   {
+      SortRData s { arg, compare };
+      #define compare_fn   !deref ? compareDesc : ascending ? compareDeref : compareDescDeref
+   #if defined(BSD)
+      qsort_r(base, nel, width, s, compare_fn);
+   #elif defined(__WIN32__)
+      qsort_s(base, nel, width, compare_fn, s);
+   #else
+      {
+         char * buf = new char[width];
+         quickSort(base, nel, width, buf, compare_fn, s);
+         delete buf;
+      }
+   #endif
+      #undef compare_fn
+   }
+#endif
+}
+
+public void qsortrx(void *base, uintsize nel, uintsize width,
+   int (*compare)(void *arg, const void *a, const void *b),
+   int (*optCompareArgLast)(const void *a, const void *b, void *arg),
+   void *arg,
+   bool deref, bool ascending)
+{
+   _qsortrx(base, nel, width, compare, optCompareArgLast, arg, deref, ascending);
+}
+
+public void qsortr(void *base, uintsize nel, uintsize width, int (*compare)(void *arg, const void *a, const void *b), void *arg)
+{
+   _qsortrx(base, nel, width, compare, null, arg, false, true);
+}
+
 public class Array : Container
 {
    class_fixed
@@ -227,7 +365,6 @@ public:
       }
    }
 
-
    void Free()
    {
       int c;
@@ -247,4 +384,11 @@ public:
       delete data;
       Remove(item);
    }
+
+   void Sort(bool ascending)
+   {
+      Class Dclass = class(D);
+      bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
+      _qsortrx(array, count, Dclass.typeSize, (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare], null, Dclass, !byRef, ascending);
+   }
 };

diff --git a/ecere/src/com/containers/BuiltInContainer.ec b/ecere/src/com/containers/BuiltInContainer.ec
index a78849a..aafd31c 100644 (file)
--- a/ecere/src/com/containers/BuiltInContainer.ec
+++ b/ecere/src/com/containers/BuiltInContainer.ec
@@ -131,4 +131,9 @@ public:
          tempString[0] = 0;
       return tempString;
    }
+
+   virtual void Sort(bool ascending)
+   {
+
+   }
 };

diff --git a/ecere/src/com/containers/Container.ec b/ecere/src/com/containers/Container.ec
index d613b66..2a65ad9 100644 (file)
--- a/ecere/src/com/containers/Container.ec
+++ b/ecere/src/com/containers/Container.ec
@@ -331,4 +331,92 @@ public:
          delete (void *)data;
       this = container;
    }
+
+   static void _Sort(bool ascending, Container * lists)
+   {
+      // Only sort containers with more than 1 items and which are integer indexable
+      int count = GetCount();
+      if(count >= 2 && class(I) == class(int))
+      {
+         Iterator a { this };
+         Iterator b { this };
+         Iterator mid { this };
+
+         Class Dclass = class(D);
+         bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
+         int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
+
+         Container listA = lists[0];
+         Container listB = lists[1];
+
+         // Find midpoint
+         mid.Index(count / 2-1, false);
+
+         // Split into 2 lists
+         while(a.Next())
+         {
+            listA.Add(a.data);
+            if(a.pointer == mid.pointer)
+               break;
+         }
+
+         b.pointer = mid.pointer;
+         while(b.Next())
+            listB.Add(b.data);
+
+         RemoveAll();
+
+         // Sort each of the 2 lists
+         listA._Sort(ascending, lists + 2);
+         listB._Sort(ascending, lists + 2);
+
+         // Merge
+         a = { listA };
+         b = { listB };
+         a.Next();
+         b.Next();
+
+         while(a.pointer || b.pointer)
+         {
+            int r;
+            if(a.pointer && b.pointer)
+            {
+               D dataA = a.data, dataB = b.data;
+               r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
+            }
+            else if(a.pointer)
+               r = -1;
+            else
+               r = 1;
+            if(!ascending) r *= -1;
+
+            if(r < 0)
+            {
+               Add(a.data);
+               a.Next();
+            }
+            else
+            {
+               Add(b.data);
+               b.Next();
+            }
+         }
+
+         listA.RemoveAll();
+         listB.RemoveAll();
+      }
+   }
+
+   virtual void Sort(bool ascending)
+   {
+      // Pre-allocate 2 log2(n) containers
+      int i, numLists = log2i(GetCount()) * 2;
+      Container * lists = new Container[numLists];
+      for(i = 0; i < numLists; i++)
+         lists[i] = eInstance_New(_class);
+      _Sort(ascending, lists);
+      for(i = 0; i < numLists; i++)
+         delete lists[i];
+      delete lists;
+   }
 }

diff --git a/ecere/src/com/containers/LinkList.ec b/ecere/src/com/containers/LinkList.ec
index a94dcd6..352c6ec 100644 (file)
--- a/ecere/src/com/containers/LinkList.ec
+++ b/ecere/src/com/containers/LinkList.ec
@@ -1,6 +1,11 @@
 namespace com;
 
 import "Container"
+import "List"  // Ugly dependency for List optimization in Sort()
+
+default:
+extern int __ecereVMethodID_class_OnCompare;
+private:
 
 public struct LinkElement<class T:void *>
 {
@@ -180,4 +185,110 @@ public:
       Remove(item);
       delete item;
    }
+
+   // Optimized Merge Sort Reusing List Nodes
+   static void _Sort(bool ascending, LinkList * lists)
+   {
+      // Only sort containers with more than 1 items and which are integer indexable
+      if(count >= 2)
+      {
+         LT a, b, mid;
+         Class Dclass = class(D);
+         bool byRef = (Dclass.type == systemClass && !Dclass.byValueSystemClass) || Dclass.type == bitClass || Dclass.type == enumClass || Dclass.type == unitClass;
+         bool isList = GetData == List::GetData;
+         bool isLinkList = GetData == LinkList::GetData;
+         bool isStruct = Dclass.type == structClass;
+         int (* onCompare)(void *, const void *, const void *) = (void *)Dclass._vTbl[__ecereVMethodID_class_OnCompare];
+         LinkList listA = lists[0];
+         LinkList listB = lists[1];
+
+         // Find midpoint
+         mid = GetAtPosition(count / 2-1, false, null);
+
+         // Split into 2 lists
+         a = first;
+         b = mid.link.next;
+
+         while(a)
+         {
+            LT i = a;
+            bool done = (a == mid);
+            a = a.link.next;
+            listA.LinkList::Add((void *)(uintptr)i);
+            if(done) break;
+         }
+
+         while(b)
+         {
+            LT i = b;
+            b = b.link.next;
+            listB.LinkList::Add((void *)(uintptr)i);
+         }
+
+         first = null, last = null, count = 0;
+
+         // Sort each of the 2 lists
+         listA._Sort(ascending, lists+2);
+         listB._Sort(ascending, lists+2);
+
+         // Merge
+         a = listA.first;
+         b = listB.first;
+
+         while(a || b)
+         {
+            int r;
+            if(a && b)
+            {
+               if(isLinkList)
+                  r = onCompare(Dclass, a, b);
+               else if(isList)
+               {
+                  if(isStruct || byRef)
+                     r = onCompare(Dclass, &((Link)a).data, &((Link)b).data);
+                  else
+                     r = onCompare(Dclass, (const void *)(uintptr)((Link)a).data, (const void *)(uintptr)((Link)b).data);
+               }
+               else
+               {
+                  D dataA = GetData(a), dataB = GetData(b);
+                  r = onCompare(Dclass, byRef ? &dataA : (const void *)(uintptr)dataA, byRef ? &dataB : (const void *)(uintptr)dataB);
+               }
+            }
+            else if(a)
+               r = -1;
+            else
+               r = 1;
+            if(!ascending) r *= -1;
+
+            if(r < 0)
+            {
+               LT i = a;
+               a = a.link.next;
+               LinkList::Add((void *)(uintptr)i);
+            }
+            else
+            {
+               LT i = b;
+               b = b.link.next;
+               LinkList::Add((void *)(uintptr)i);
+            }
+         }
+         listA.first = null, listA.last = null, listA.count = 0;
+         listB.first = null, listB.last = null, listB.count = 0;
+      }
+   }
+
+   void Sort(bool ascending)
+   {
+      // Pre-allocate 2 log2(n) lists
+      int i, numLists = log2i(count) * 2;
+      LinkList * lists = new LinkList[numLists];
+      for(i = 0; i < numLists; i++)
+         lists[i] = eInstance_New(_class);
+      _Sort(ascending, lists);
+      for(i = 0; i < numLists; i++)
+         delete lists[i];
+      delete lists;
+   }
 }