libdvec-c

commit faa3fadbd2181e76482343d34b9651d062c92826
parent 5aa1020935270c72f7bbfb87cf2017a2ca7d4ee7
Author: Louis Burda <quent.burda@gmail.com>
Date:   Sat, 12 Aug 2023 09:47:32 +0200

Replace bubblesort with quicksort and add _push/_pop

Diffstat:
M
include/dvec.h
 | 
22
++++++++++++++++++++--
M
libdvec.api
 | 
2
+-
M
libdvec.lds
 | 
2
+-
M
src/dvec.c
 | 
69
++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------
M
src/test.c
 | 
5
+++--

5 files changed, 79 insertions(+), 21 deletions(-)
diff --git a/include/dvec.h b/include/dvec.h
@@ -67,8 +67,8 @@ void dvec_replace(struct dvec *dvec, size_t index,
 void *dvec_iter_fwd(const struct dvec *dvec, const void *p);
 void *dvec_iter_bwd(const struct dvec *dvec, const void *p);
 
-int dvec_bubble_sort(struct dvec *dvec,
-	bool reverse, dvec_sort_order_fn in_order, void *user);
+int dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
+	void *tmp, bool reverse, dvec_sort_order_fn in_order, void *user);
 
 ssize_t dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp,
 	void *user, ssize_t *lower, ssize_t *higher);
@@ -138,3 +138,21 @@ dvec_lock(struct dvec *dvec, bool lock)
 {
 	dvec->locked = lock;
 }
+
+static inline void *
+dvec_push(struct dvec *dvec)
+{
+	LIBDVEC_ABORT_ON_ARGS(dvec);
+
+	dvec_reserve(dvec, dvec->len + 1);
+
+	return dvec->data + dvec->len++ * dvec->dsize;
+}
+
+static inline void *
+dvec_pop(struct dvec *dvec)
+{
+	LIBDVEC_ABORT_ON_ARGS(dvec || !dvec->len);
+
+	return dvec->data + --dvec->len * dvec->dsize;
+}
diff --git a/libdvec.api b/libdvec.api
@@ -18,5 +18,5 @@ dvec_replace
 dvec_iter_fwd
 dvec_iter_bwd
 
-dvec_bubble_sort
+dvec_quick_sort
 dvec_binary_search
diff --git a/libdvec.lds b/libdvec.lds
@@ -20,7 +20,7 @@ LIBDVEC_1.1.2 {
 		dvec_iter_fwd;
 		dvec_iter_bwd;
 
-		dvec_bubble_sort;
+		dvec_quick_sort;
 		dvec_binary_search;
 	local: *;
 };
diff --git a/src/dvec.c b/src/dvec.c
@@ -268,32 +268,71 @@ dvec_iter_bwd(const struct dvec *dvec, const void *p)
 	}
 }
 
+static void
+dvec_quick_sort_swap(void *a, void *b, void *tmp, size_t dsize)
+{
+	memcpy(tmp, a, dsize);
+	memcpy(a, b, dsize);
+	memcpy(b, tmp, dsize);
+}
+
 int
-dvec_bubble_sort(struct dvec *dvec, bool reverse,
-	dvec_sort_order_fn in_order, void *user)
+dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
+	void *tmp, bool reverse, dvec_sort_order_fn in_order, void *user)
 {
-	void *cur, *next, *tmp;
-	size_t i, k;
+	struct dvec stack;
+	char *pivot, *lo, *hi;
+	char *start, *end;
+	size_t dsize;
+	bool lo_order, hi_order;
 	int rc;
 
-	rc = dvec_reserve(dvec, dvec->len + 1);
+	rc = dvec_init(&stack, sizeof(char *), 32, allocator);
 	if (rc) return rc;
 
-	tmp = dvec->data + dvec->len * dvec->dsize;
+	dsize = dvec->dsize;
+
+	*(char **)dvec_push(&stack) = dvec_front(dvec);
+	*(char **)dvec_push(&stack) = dvec_back(dvec);
+	while (!dvec_empty(&stack)) {
+		end = *(char **)dvec_pop(&stack);
+		start = *(char **)dvec_pop(&stack);
+
+		if (start == end) continue;
+
+		if (start + dsize >= end) {
+			if (!in_order(start, end, user))
+				dvec_quick_sort_swap(start, end, tmp, dsize);
+			continue;
+		}
 
-	for (i = 1; i < dvec->len; i++) {
-		cur = dvec->data;
-		for (k = 0; k < dvec->len - i; k++) {
-			next = (char *) cur + dvec->dsize;
-			if (in_order(cur, next, user) == reverse) {
-				memcpy(tmp, cur, dvec->dsize);
-				memcpy(cur, next, dvec->dsize);
-				memcpy(next, tmp, dvec->dsize);
+		pivot = start + (size_t) (end - start) / dsize / 2 * dsize;
+		lo = start; hi = end;
+		while (lo < hi) {
+			lo_order = lo != pivot && in_order(lo, pivot, user);
+			hi_order = hi != pivot && in_order(pivot, hi, user);
+			if (!lo_order && !hi_order) {
+				if (lo == pivot) pivot = hi;
+				else if (hi == pivot) pivot = lo;
+				dvec_quick_sort_swap(lo, hi, tmp, dsize);
 			}
-			cur = next;
+			if (lo_order) lo += dsize;
+			if (hi_order) hi -= dsize;
+		}
+
+		if (start != pivot) {
+			*(char **)dvec_push(&stack) = start;
+			*(char **)dvec_push(&stack) = pivot - dsize;
+		}
+
+		if (end != pivot) {
+			*(char **)dvec_push(&stack) = pivot + dsize;
+			*(char **)dvec_push(&stack) = end;
 		}
 	}
 
+	dvec_deinit(&stack);
+
 	return DVEC_OK;
 }
 
diff --git a/src/test.c b/src/test.c
@@ -36,8 +36,8 @@ main(int argc, const char **argv)
 {
 	struct dvec dvec;
 	ssize_t below, above, on;
+	const char **val, *tmp;
 	int i, rc;
-	const char **val;
 
 	rc = dvec_init(&dvec, sizeof(const char *), 16, &stdlib_heap_allocator);
 	if (rc) LIBDVEC_ERR(rc);
@@ -49,7 +49,8 @@ main(int argc, const char **argv)
 		*val = argv[i];
 	}
 
-	rc = dvec_bubble_sort(&dvec, false, str_sort_order, NULL);
+	rc = dvec_quick_sort(&dvec, &stdlib_heap_allocator, &tmp,
+		false, str_sort_order, NULL);
 	if (rc) LIBDVEC_ERR(rc);
 
 	on = dvec_binary_search(&dvec, str_search, "abc", &below, &above);