Changeset 59972 in vbox for trunk/src/VBox/Runtime/common/sort

Timestamp:

Mar 9, 2016 8:06:41 PM (9 years ago)

Author:

vboxsync

svn:sync-xref-src-repo-rev:

105937

Message:

Implemented RTSortShell.

File:

• trunk/src/VBox/Runtime/common/sort/shellsort.cpp (modified) (1 diff)

trunk/src/VBox/Runtime/common/sort/shellsort.cpp

@@ -32 +32 @@
 #include <iprt/sort.h>
 
+#include <iprt/alloca.h>
+#include <iprt/assert.h>
+#include <iprt/string.h>
+
+
+
+RTDECL(void) RTSortShell(void *pvArray, size_t cElements, size_t cbElement, PFNRTSORTCMP pfnCmp, void *pvUser)
+{
+    Assert(cbElement <= 32);
+
+    /* Anything worth sorting? */
+    if (cElements < 2)
+        return;
+
+    uint8_t *pbArray = (uint8_t *)pvArray;
+    void    *pvTmp   = alloca(cbElement);
+    size_t   cGap    = (cElements + 1) / 2;
+    while (cGap > 0)
+    {
+        size_t i;
+        for (i = cGap; i < cElements; i++)
+        {
+            memcpy(pvTmp, &pbArray[i * cbElement], cbElement);
+            size_t  j     = i;
+            while (   j >= cGap
+                   && pfnCmp(&pbArray[(j - cGap) * cbElement], pvTmp, pvUser) > 0)
+            {
+                memmove(&pbArray[j * cbElement], &pbArray[(j - cGap) * cbElement], cbElement);
+                j -= cGap;
+            }
+            memcpy(&pbArray[j * cbElement], pvTmp, cbElement);
+        }
+
+        /* This does not generate the most optimal gap sequence, but it has the
+           advantage of being simple and avoid floating point. */
+        cGap /= 2;
+    }
+}