summaryrefslogtreecommitdiff
path: root/src/libc/vendor
diff options
context:
space:
mode:
Diffstat (limited to 'src/libc/vendor')
-rw-r--r--src/libc/vendor/sortix/bsearch.c70
-rw-r--r--src/libc/vendor/sortix/qsort.c35
-rw-r--r--src/libc/vendor/sortix/qsort_r.c146
3 files changed, 251 insertions, 0 deletions
diff --git a/src/libc/vendor/sortix/bsearch.c b/src/libc/vendor/sortix/bsearch.c
new file mode 100644
index 0000000..028e08a
--- /dev/null
+++ b/src/libc/vendor/sortix/bsearch.c
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2012, 2016 Jonas 'Sortie' Termansen.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * stdlib/bsearch.c
+ * Binary search.
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+
+/*
+ * Semantics of binary search:
+ *
+ * bsearch(key, base, 0, size, compare) may return NULL.
+ *
+ * If 0 <= i < nmemb
+ * and ptr = base + size * i
+ * and compare(key, ptr) = 0 then
+ * bsearch(key, base, nmemb, size, compare) may return ptr.
+ *
+ * If 0 <= i < nmemb
+ * and ptr = base + size * i
+ * and compare(key, ptr) < 0 then
+ * bsearch(key, base, nmemb, size, compare) may return
+ * bsearch(key, base, i, size, compare).
+ *
+ * If 0 <= i < nmemb
+ * and ptr = base + size * i
+ * and compare(key, ptr) > 0 then
+ * bsearch(key, base, nmemb, size, compare) may return
+ * bsearch(key, base + size * (i + 1), nemb - (i + 1), size, compare).
+ */
+
+void* bsearch(const void* key,
+ const void* base_ptr,
+ size_t nmemb,
+ size_t size,
+ int (*compare)(const void*, const void*))
+{
+ const unsigned char* base = (const unsigned char*) base_ptr;
+ while ( nmemb )
+ {
+ size_t i = nmemb / 2;
+ const unsigned char* candidate = base + i * size;
+ int rel = compare(key, candidate);
+ if ( rel < 0 ) /* key smaller than candidate */
+ nmemb = i;
+ else if ( 0 < rel ) /* key greater than candidate */
+ {
+ base = candidate + size;
+ nmemb -= i + 1;
+ }
+ else /* key equal to candidate */
+ return (void*) candidate;
+ }
+ return NULL;
+}
+
diff --git a/src/libc/vendor/sortix/qsort.c b/src/libc/vendor/sortix/qsort.c
new file mode 100644
index 0000000..feef9ea
--- /dev/null
+++ b/src/libc/vendor/sortix/qsort.c
@@ -0,0 +1,35 @@
+/*
+ * Copyright (c) 2012, 2014 Jonas 'Sortie' Termansen.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * stdlib/qsort.c
+ * Sort an array.
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+static int compare_wrapper(const void* a, const void* b, void* arg)
+{
+ return ((int (*)(const void*, const void*)) arg)(a, b);
+}
+
+void qsort(void* base_ptr,
+ size_t num_elements,
+ size_t element_size,
+ int (*compare)(const void*, const void*))
+{
+ qsort_r(base_ptr, num_elements, element_size, compare_wrapper, (void*) compare);
+}
diff --git a/src/libc/vendor/sortix/qsort_r.c b/src/libc/vendor/sortix/qsort_r.c
new file mode 100644
index 0000000..8aff807
--- /dev/null
+++ b/src/libc/vendor/sortix/qsort_r.c
@@ -0,0 +1,146 @@
+/*
+ * Copyright (c) 2012, 2014, 2021 Jonas 'Sortie' Termansen.
+ * Copyright (c) 2021 Juhani 'nortti' Krekelä.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * stdlib/qsort_r.c
+ * Sort an array. Implemented using heapsort, which is not a stable sort.
+ */
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+static void memswap(unsigned char* a, unsigned char* b, size_t size)
+{
+ unsigned char tmp;
+ for ( size_t i = 0; i < size; i++ )
+ {
+ tmp = a[i];
+ a[i] = b[i];
+ b[i] = tmp;
+ }
+}
+
+static unsigned char* array_index(unsigned char* base,
+ size_t element_size,
+ size_t index)
+{
+ return base + element_size * index;
+}
+
+void qsort_r(void* base_ptr,
+ size_t num_elements,
+ size_t element_size,
+ int (*compare)(const void*, const void*, void*),
+ void* arg)
+{
+ unsigned char* base = base_ptr;
+
+ if ( !element_size || num_elements < 2 )
+ return;
+
+ // Incrementally left-to-right transform the array into a max-heap, where
+ // each element has up to two children that aren't bigger than the element.
+ for ( size_t i = 0; i < num_elements; i++ )
+ {
+ // Grow the heap by inserting another element into it (implicit, done by
+ // moving the boundary between the heap and the yet-to-be-processed
+ // array elements) and swapping it up the parent chain as long as it's
+ // bigger than its parent.
+ size_t element = i;
+ while ( element > 0 )
+ {
+ unsigned char* ptr = array_index(base, element_size, element);
+ size_t parent = (element - 1) / 2;
+ unsigned char* parent_ptr = array_index(base, element_size, parent);
+ if ( compare(parent_ptr, ptr, arg) < 0 )
+ {
+ memswap(parent_ptr, ptr, element_size);
+ element = parent;
+ }
+ else
+ break;
+ }
+ }
+
+ // The array is split into two sections, first the max-heap and then the
+ // part of the array that has been sorted.
+ // Sorting progresses right-to-left, taking the biggest value of the heap
+ // (at its root), swapping it with the last element of the heap, and
+ // adjusting the boundary between the two sections such that the old biggest
+ // value is now part of the sorted section.
+ // After this, the max-heap property is restored by swapping the old last
+ // element down as long as it's smaller than one of its children.
+ for ( size_t size = num_elements; --size; )
+ {
+ memswap(array_index(base, element_size, size), base, element_size);
+
+ size_t first_without_left = size / 2;
+ size_t first_without_right = (size - 1) / 2;
+
+ size_t element = 0;
+ while ( element < size )
+ {
+ unsigned char* ptr = array_index(base, element_size, element);
+
+ size_t left = 2 * element + 1;
+ unsigned char* left_ptr = NULL;
+ bool left_bigger = false;
+ if ( element < first_without_left )
+ {
+ left_ptr = array_index(base, element_size, left);
+ left_bigger = compare(ptr, left_ptr, arg) < 0;
+ }
+
+ size_t right = 2 * element + 2;
+ unsigned char* right_ptr = NULL;
+ bool right_bigger = false;
+ if ( element < first_without_right )
+ {
+ right_ptr = array_index(base, element_size, right);
+ right_bigger = compare(ptr, right_ptr, arg) < 0;
+ }
+
+ if ( left_bigger && right_bigger )
+ {
+ // If both the left and right child are bigger than the element,
+ // then swap the element with whichever of the left and right
+ // child is bigger.
+ if ( compare(left_ptr, right_ptr, arg) < 0 )
+ {
+ memswap(ptr, right_ptr, element_size);
+ element = right;
+ }
+ else
+ {
+ memswap(ptr, left_ptr, element_size);
+ element = left;
+ }
+ }
+ else if ( left_bigger )
+ {
+ memswap(ptr, left_ptr, element_size);
+ element = left;
+ }
+ else if ( right_bigger )
+ {
+ memswap(ptr, right_ptr, element_size);
+ element = right;
+ }
+ else
+ break;
+ }
+ }
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-22 16:02:29 +0000