1 files changed, 73 insertions, 0 deletions
diff --git a/src/ssort.h b/src/ssort.h
new file mode 100644
index 0000000..7cc1572
--- /dev/null
+++ b/src/ssort.h
@@ -0,0 +1,73 @@
+/*
+**  ssort()  --  Fast, small, qsort()-compatible Shell sort
+**
+**  by Ray Gardner,  public domain   5/90
+*/
+
+#include <stddef.h>
+
+/**
+ * ssort_r:
+ * @base: base data
+ * @nel: number of elements at @base
+ * @width: width of an element
+ * @comp: comparison function taking args (a, b, @arg)
+ * @arg: user data (thunk) for the comparison function @comp
+ *
+ * Fast, small shell sort compatible to qsort_r() taking an extra thunk / user data arg.
+ *
+ * Sorts data at @base of @nel elements of width @width using
+ * comparison function @comp that takes args (a, b, @arg).
+ *
+ * Return value: non-0 on failure
+ *
+*/
+static int
+ssort_r(void* base, size_t nel, size_t width,
+        raptor_data_compare_arg_handler comp,
+        void* arg)
+{
+  size_t wnel, gap, k;
+
+  /* bad args */
+  if(!base || !width || !comp)
+    return -1;
+
+  /* nothing to do */
+  if(nel < 2)
+    return 0;
+
+  wnel = width * nel;
+  for(gap = 0; ++gap < nel;)
+    gap *= 3;
+
+  while((gap /= 3) != 0) {
+    size_t wgap = width * gap;
+    size_t i;
+
+    for(i = wgap; i < wnel; i += width) {
+      size_t j = i;
+      do {
+        char* a;
+        char* b;
+
+        j -= wgap;
+        a = j + (char *)base;
+        b = a + wgap;
+
+        if ((*comp)(a, b, arg) <= 0)
+          break;
+
+        k = width;
+        do {
+          char tmp = *a;
+          *a++ = *b;
+          *b++ = tmp;
+        } while (--k);
+
+      } while(j >= wgap);
+    }
+  }
+
+  return 0;
+}