Add public domain ssort_r if qsort_r and qsort_s are not present

4 files changed, 83 insertions, 2 deletions

diff --git a/configure.ac b/configure.ac
index fbb21c0e..a93d197b 100644
--- a/configure.ac
+++ b/configure.ac
@@ -384,7 +384,7 @@ AC_SUBST(RAPTOR_LIBTOOL_VERSION)
 
 
 dnl Checks for library functions.
-AC_CHECK_FUNCS(gettimeofday getopt getopt_long stricmp strcasecmp vsnprintf isascii setjmp strtok_r)
+AC_CHECK_FUNCS(gettimeofday getopt getopt_long stricmp strcasecmp vsnprintf isascii setjmp strtok_r qsort_r qsort_s)
 
 dnl librdfa
 AM_CONDITIONAL([NEED_STRTOK_R], [test "$ac_cv_func_strtok_r" = "no"])
diff --git a/src/Makefile.am b/src/Makefile.am
index 5a897bf4..bf4a1549 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -77,7 +77,7 @@ raptor_json_writer.c raptor_memstr.c raptor_concepts.c \
 raptor_syntax_description.c \
 raptor_sax2.c raptor_escaped.c \
 raptor_ntriples.c \
-sort_r.c sort_r.h
+sort_r.c sort_r.h ssort.h
 if RAPTOR_XML_LIBXML
 libraptor2_la_SOURCES += raptor_libxml.c
 endif
diff --git a/src/sort_r.c b/src/sort_r.c
index 891b7d6e..2db1c67e 100644
--- a/src/sort_r.c
+++ b/src/sort_r.c
@@ -35,8 +35,12 @@
 
 #ifndef STANDALONE
 
+#if defined(HAVE_QSORT_R) || defined(HAVE_QSORT_S)
 /* Include inline code */
 #include "sort_r.h"
+#else
+#include "ssort.h"
+#endif
 
 
 /**
@@ -61,7 +65,11 @@ void
 raptor_sort_r(void *base, size_t nel, size_t width,
               raptor_sort_r_compare compar, void *user_data)
 {
+#if defined(HAVE_QSORT_R) || defined(HAVE_QSORT_S)
   sort_r(base, nel, width, compar, user_data);
+#else
+  ssort_r(base, nel, width, compar, user_data);
+#endif
 }
 
 
diff --git a/src/ssort.h b/src/ssort.h
new file mode 100644
index 00000000..f080ced6
--- /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_sort_r_compare 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;
+}