Page MenuHomeFreeBSD
Files F47965191

a.diff
hselasky (Hans Petter Selasky)
Actions

Authored By
• hselasky
Sep 8 2022, 2:40 PM
Size
9 KB
Referenced Files
None
Subscribers
None

a.diff
View Options

commit 6311a594d13b3a0199d4b14e0b25a154e8302f10
Author: Hans Petter Selasky <hps@selasky.org>
Date: Thu Sep 8 16:27:57 2022 +0200
Add support for bsort().
Signed-off-by: Hans Petter Selasky <hps@selasky.org>
diff --git a/Makefile b/Makefile
index 81301cd..8d5bbb6 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-CC = gcc
+CC = clang
CFLAGS = -Ofast -march=native -Wall -Wextra -std=c11 # -Dcheck=1
#CFLAGS = -Os -march=native -Wall -Wextra -std=c11 # -Dcheck=1
LDFLAGS = -flto
@@ -13,5 +13,5 @@ all: bench
clean:
rm -rf *.o qsort
-bench: reactos.o ms.o linux.o sortix.o freebsd.o glibc.o wada.o klibc.o illumos.o uclibc.o plan9.o mine.o mini.o musl.o diet.o bsd.o qsort.c Makefile
+bench: reactos.o ms.o linux.o sortix.o freebsd.o glibc.o wada.o klibc.o illumos.o uclibc.o plan9.o mine.o mini.o musl.o diet.o bsd.o bsort.o qsort.c Makefile
$(CC) $(CFLAGS) $(LDFLAGS) qsort.c *.o -o qsort
diff --git a/bsort.c b/bsort.c
new file mode 100644
index 0000000..300bc82
--- /dev/null
+++ b/bsort.c
@@ -0,0 +1,253 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause
+ *
+ * Copyright (c) 2016-2022 Hans Petter Selasky
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * A variant of bitonic sorting
+ *
+ * Worst case sorting complexity: log2(N) * log2(N) * N
+ * Additional memory and stack usage: none
+ */
+
+#if defined(I_AM_BSORT_R)
+typedef int cmp_t (void *, const void *, const void *);
+#define ARG_PROTO void *arg,
+#define ARG_NAME arg ,
+#define CMP(fn,arg,a,b) (fn)(arg, a, b)
+#elif defined(I_AM_BSORT_S)
+typedef int cmp_t (const void *, const void *, void *);
+#define ARG_PROTO void *arg,
+#define ARG_NAME arg ,
+#define CMP(fn,arg,a,b) (fn)(a, b, arg)
+#else
+typedef int cmp_t (const void *, const void *);
+#define ARG_PROTO
+#define ARG_NAME
+#define CMP(fn,arg,a,b) (fn)(a, b)
+#endif
+
+static inline size_t
+bsort_index(size_t t)
+{
+ t ^= t >> 1;
+ t ^= t >> 2;
+ t ^= t >> 4;
+ t ^= t >> 8;
+ t ^= t >> 16;
+ if (sizeof(t) >= 8)
+ t ^= t >> (sizeof(t) >= 8 ? 32 : 0);
+ return (t);
+}
+
+static inline void
+bsort_swap(char *pa, char *pb, const size_t es)
+{
+ if (__builtin_constant_p(es) && es == 8) {
+ uint64_t tmp;
+
+ /* swap */
+ tmp = *(uint64_t *)pa;
+ *(uint64_t *)pa = *(uint64_t *)pb;
+ *(uint64_t *)pb = tmp;
+ } else if (__builtin_constant_p(es) && es == 4) {
+ uint32_t tmp;
+
+ /* swap */
+ tmp = *(uint32_t *)pa;
+ *(uint32_t *)pa = *(uint32_t *)pb;
+ *(uint32_t *)pb = tmp;
+ } else if (__builtin_constant_p(es) && es == 2) {
+ uint16_t tmp;
+
+ /* swap */
+ tmp = *(uint16_t *)pa;
+ *(uint16_t *)pa = *(uint16_t *)pb;
+ *(uint16_t *)pb = tmp;
+ } else if (__builtin_constant_p(es) && es == 1) {
+ uint8_t tmp;
+
+ /* swap */
+ tmp = *(uint8_t *)pa;
+ *(uint8_t *)pa = *(uint8_t *)pb;
+ *(uint8_t *)pb = tmp;
+ } else {
+ char tmp[es] __aligned(8);
+
+ /* swap */
+ memcpy(tmp, pa, es);
+ memcpy(pa, pb, es);
+ memcpy(pb, tmp, es);
+ }
+}
+
+static inline bool
+bsort_xform(void *ptr, const size_t n, const size_t lim, const size_t es, ARG_PROTO cmp_t *fn)
+{
+#define BSORT_TABLE_MAX (1UL << 4)
+ size_t x, y, z;
+ unsigned t, u, v;
+ size_t p[BSORT_TABLE_MAX];
+ bool retval = false;
+
+ x = n;
+ while (1) {
+ /* optimise */
+ if (x >= BSORT_TABLE_MAX)
+ v = BSORT_TABLE_MAX;
+ else if (x >= 2)
+ v = x;
+ else
+ break;
+
+ /* divide down */
+ x /= v;
+
+ /* generate ramp table */
+ for (t = 0; t != v; t++)
+ p[t] = bsort_index(x * (t ^ (t / 2)));
+
+ /* bitonic sort */
+ for (y = 0; y != n; y += (v * x)) {
+ for (z = 0; z != x; z++) {
+ size_t w = y + z;
+
+ /* insertion sort */
+ for (t = 1; t != v; t++) {
+ /*
+ * check for arrays which are not
+ * power of two
+ */
+ if ((w ^ p[t]) >= lim)
+ break;
+ for (u = t; u != 0; u--) {
+ char *pa = (char *)ptr + ((w ^ p[u - 1]) * es);
+ char *pb = (char *)ptr + ((w ^ p[u]) * es);
+
+ if (CMP(fn, arg, pa, pb) > 0) {
+ bsort_swap(pa, pb, es);
+ retval = true;
+ } else {
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+ return (retval);
+}
+
+static void
+local_bsort(void *ptr, const size_t n, const size_t es, ARG_PROTO cmp_t *fn)
+{
+ size_t max;
+
+ /* if there are less than 2 elements, then sorting is not needed */
+ if (n < 2)
+ return;
+
+ /* compute power of two rounded up, into max */
+ max = n;
+ while (max & (max - 1))
+ max &= (max - 1);
+
+ /* round up power of two */
+ if (max != n)
+ max *= 2;
+
+ /* optimize common sort scenarios */
+ switch (es) {
+ case 8:
+ while (bsort_xform(ptr, max, n, 8, ARG_NAME fn))
+ ;
+ break;
+ case 4:
+ while (bsort_xform(ptr, max, n, 4, ARG_NAME fn))
+ ;
+ break;
+ case 2:
+ while (bsort_xform(ptr, max, n, 2, ARG_NAME fn))
+ ;
+ break;
+ case 1:
+ while (bsort_xform(ptr, max, n, 1, ARG_NAME fn))
+ ;
+ break;
+ default:
+ while (bsort_xform(ptr, max, n, es, ARG_NAME fn))
+ ;
+ break;
+ }
+}
+
+#if defined(I_AM_BSORT_R)
+void
+bsort_r(void *a, size_t n, size_t es, void *arg, cmp_t *cmp)
+{
+ local_bsort(a, n, es, cmp, arg);
+}
+#elif defined(I_AM_BSORT_S)
+errno_t
+bsort_s(void *a, rsize_t n, rsize_t es, cmp_t *cmp, void *arg)
+{
+ if (n > RSIZE_MAX) {
+ __throw_constraint_handler_s("bsort_s : n > RSIZE_MAX", EINVAL);
+ return (EINVAL);
+ } else if (es > RSIZE_MAX) {
+ __throw_constraint_handler_s("bsort_s : es > RSIZE_MAX",
+ EINVAL);
+ return (EINVAL);
+ } else if (n != 0) {
+ if (a == NULL) {
+ __throw_constraint_handler_s("bsort_s : a == NULL",
+ EINVAL);
+ return (EINVAL);
+ } else if (cmp == NULL) {
+ __throw_constraint_handler_s("bsort_s : cmp == NULL",
+ EINVAL);
+ return (EINVAL);
+ }
+ }
+
+ local_bsort(a, n, es, cmp, arg);
+ return (0);
+}
+#else
+void
+bsort(void *a, size_t n, size_t es, cmp_t *cmp)
+{
+ local_bsort(a, n, es, cmp);
+}
+#endif
diff --git a/glibc.c b/glibc.c
index b2ebc74..f92ba08 100644
--- a/glibc.c
+++ b/glibc.c
@@ -2,7 +2,7 @@
typedef int (*__compar_d_fn_t) (const void *, const void *, void *);
typedef int (*__compar_fn_t) (const void *, const void *);
#include <limits.h>
-#include <alloca.h>
+/* #include <alloca.h> */
#define __mempcpy mempcpy
#define __alloca alloca
#define __sysconf sysconf
@@ -29,7 +29,7 @@ typedef int (*__compar_fn_t) (const void *, const void *);
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
-#include <alloca.h>
+// #include <alloca.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
diff --git a/qsort.c b/qsort.c
index 1cd9f42..3a3ae02 100644
--- a/qsort.c
+++ b/qsort.c
@@ -9,6 +9,7 @@
+void bsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
void bsd_qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
void diet_qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
void illumos_qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
@@ -173,6 +174,7 @@ int main(int argc, char *argv[]) {
{ glibc_qsort, "glibc" , 0, 0 },
{ musl_qsort, "musl" , 0, 0 },
{ diet_qsort, "diet" , 0, 0 },
+ { bsort, "bsort" , 0, 0 },
{ bsd_qsort, "bsd" , 0, 0 },
{ uclibc_qsort, "uclibc" , 0, 0 },
{ plan9_qsort, "plan9" , 0, 0 },
diff --git a/sortix.c b/sortix.c
index 9f885e5..5b56e42 100644
--- a/sortix.c
+++ b/sortix.c
@@ -58,7 +58,7 @@ size_t partition(unsigned char* base,
return store_index;
}
-void qsort_r(void* base_ptr,
+static void qsort_rr(void* base_ptr,
size_t num_elements,
size_t element_size,
int (*compare)(const void*, const void*, void*),
@@ -73,10 +73,10 @@ void qsort_r(void* base_ptr,
pivot_index = partition(base, element_size, num_elements, pivot_index, compare, arg);
if ( 2 <= pivot_index )
- qsort_r(base, pivot_index, element_size, compare, arg);
+ qsort_rr(base, pivot_index, element_size, compare, arg);
if ( 2 <= num_elements - (pivot_index + 1) )
- qsort_r(array_index(base, element_size, pivot_index + 1),
+ qsort_rr(array_index(base, element_size, pivot_index + 1),
num_elements - (pivot_index + 1), element_size, compare, arg);
}
@@ -90,5 +90,5 @@ void sortix_qsort(void* base_ptr,
size_t element_size,
int (*compare)(const void*, const void*))
{
- qsort_r(base_ptr, num_elements, element_size, compare_wrapper, (void*) compare);
+ qsort_rr(base_ptr, num_elements, element_size, compare_wrapper, (void*) compare);
}

File Metadata

Mime Type
text/x-diff
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5113534
Default Alt Text
a.diff (9 KB)

Event Timeline