libdvec-c

commit e57831bb67f3452791c3d98820baffedc631aeca
parent faa3fadbd2181e76482343d34b9651d062c92826
Author: Louis Burda <quent.burda@gmail.com>
Date:   Sat, 12 Aug 2023 22:35:08 +0200

Add quicksort_ex for sorting large elements efficiently

Diffstat:
M
include/dvec.h
 | 
15
+++++++++++++--
M
libdvec.api
 | 
2
++
M
libdvec.lds
 | 
4
+++-
M
src/dvec.c
 | 
65
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
M
src/test.c
 | 
2
+-

5 files changed, 83 insertions(+), 5 deletions(-)
diff --git a/include/dvec.h b/include/dvec.h
@@ -69,6 +69,8 @@ void *dvec_iter_bwd(const struct dvec *dvec, const void *p);
 
 int dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
 	void *tmp, bool reverse, dvec_sort_order_fn in_order, void *user);
+int dvec_quick_sort_ex(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);
@@ -142,7 +144,7 @@ dvec_lock(struct dvec *dvec, bool lock)
 static inline void *
 dvec_push(struct dvec *dvec)
 {
-	LIBDVEC_ABORT_ON_ARGS(dvec);
+	LIBDVEC_ABORT_ON_ARGS(!dvec);
 
 	dvec_reserve(dvec, dvec->len + 1);
 
@@ -152,7 +154,16 @@ dvec_push(struct dvec *dvec)
 static inline void *
 dvec_pop(struct dvec *dvec)
 {
-	LIBDVEC_ABORT_ON_ARGS(dvec || !dvec->len);
+	LIBDVEC_ABORT_ON_ARGS(!dvec || !dvec->len);
 
 	return dvec->data + --dvec->len * dvec->dsize;
 }
+
+static inline size_t
+dvec_idx(struct dvec *dvec, const void *p)
+{
+	LIBDVEC_ABORT_ON_ARGS(!dvec || p < dvec->data
+		|| p >= dvec->data + dvec->dsize * dvec->len);
+
+	return (size_t) ((char *)p - dvec->data) / dvec->dsize;
+}
diff --git a/libdvec.api b/libdvec.api
@@ -19,4 +19,6 @@ dvec_iter_fwd
 dvec_iter_bwd
 
 dvec_quick_sort
+dvec_quick_sort_ex
+
 dvec_binary_search
diff --git a/libdvec.lds b/libdvec.lds
@@ -1,4 +1,4 @@
-LIBDVEC_1.1.2 {
+LIBDVEC_1.1.3 {
 	global:
 		dvec_init;
 		dvec_deinit;
@@ -21,6 +21,8 @@ LIBDVEC_1.1.2 {
 		dvec_iter_bwd;
 
 		dvec_quick_sort;
+		dvec_quick_sort_ex;
+
 		dvec_binary_search;
 	local: *;
 };
diff --git a/src/dvec.c b/src/dvec.c
@@ -1,7 +1,11 @@
 #include "dvec.h"
 
 #include <string.h>
-#include <stdlib.h>
+
+struct sort_order_user_proxy {
+	dvec_sort_order_fn order_fn;
+	void *user;
+};
 
 int
 dvec_init(struct dvec *dvec, size_t dsize, size_t cap,
@@ -287,6 +291,8 @@ dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
 	bool lo_order, hi_order;
 	int rc;
 
+	if (!dvec->len) return DVEC_OK;
+
 	rc = dvec_init(&stack, sizeof(char *), 32, allocator);
 	if (rc) return rc;
 
@@ -336,6 +342,63 @@ dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
 	return DVEC_OK;
 }
 
+static bool
+dvec_quick_sort_ex_order(const void *p1, const void *p2, void *user)
+{
+	struct sort_order_user_proxy *user_proxy = user;
+	const void *d1 = *(void **)p1, *d2 = *(void **)p2;
+
+	return user_proxy->order_fn(d1, d2, user_proxy->user);
+}
+
+int
+dvec_quick_sort_ex(struct dvec *dvec, const struct allocator *allocator,
+	void *tmp, bool reverse, dvec_sort_order_fn in_order, void *user)
+{
+	struct sort_order_user_proxy user_proxy = {
+		.order_fn = in_order,
+		.user = user
+	};
+	struct dvec ptrmap;
+	void *p, **pp, **dst, **src;
+	size_t dsize;
+	int rc;
+
+	if (!dvec->len) return DVEC_OK;
+
+	dsize = dvec->dsize;
+
+	rc = dvec_init(&ptrmap, sizeof(void *), dvec->len, allocator);
+	if (rc) return rc;
+
+	for (DVEC_ITER(dvec, p))
+		*(void **)dvec_push(&ptrmap) = p;
+
+	rc = dvec_quick_sort(&ptrmap, allocator, tmp, reverse,
+		dvec_quick_sort_ex_order, &user_proxy);
+	if (rc) return rc;
+
+	for (DVEC_ITER(&ptrmap, pp)) {
+		if (!*pp || dvec_idx(&ptrmap, pp) == dvec_idx(dvec, *pp))
+			continue;
+		dst = pp;
+		memcpy(tmp, *dst, dsize);
+		while (1) {
+			src = dvec_at(&ptrmap, dvec_idx(dvec, *dst));
+			if (!*src) break;
+			memcpy(*dst, *src, dsize);
+			*dst = NULL;
+			dst = src;
+		}
+		memcpy(*dst, tmp, dsize);
+	}
+
+	rc = dvec_deinit(&ptrmap);
+	if (rc) return rc;
+
+	return DVEC_OK;
+}
+
 ssize_t
 dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp,
 	void *user, ssize_t *lower, ssize_t *higher)
diff --git a/src/test.c b/src/test.c
@@ -49,7 +49,7 @@ main(int argc, const char **argv)
 		*val = argv[i];
 	}
 
-	rc = dvec_quick_sort(&dvec, &stdlib_heap_allocator, &tmp,
+	rc = dvec_quick_sort_ex(&dvec, &stdlib_heap_allocator, &tmp,
 		false, str_sort_order, NULL);
 	if (rc) LIBDVEC_ERR(rc);