Add bubble sort and binary search

5 files changed, 120 insertions, 4 deletions

diff --git a/include/dvec.h b/include/dvec.h
index 31be5a6..9ce2c08 100644
--- a/include/dvec.h
+++ b/include/dvec.h
@@ -2,6 +2,7 @@
 
 #include "allocator.h"
 
+#include <sys/types.h>
 #include <stdbool.h>
 #include <stddef.h>
 
@@ -38,6 +39,9 @@ struct dvec {
 	const struct allocator *allocator;
 };
 
+typedef bool (*dvec_sort_order_fn)(const void *p1, const void *p2);
+typedef int (*dvec_search_cmp_fn)(const void *cur, void *user);
+
 int dvec_init(struct dvec *dvec, size_t dsize, size_t cap,
 	const struct allocator *allocator);
 int dvec_deinit(struct dvec *dvec);
@@ -62,6 +66,12 @@ 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);
+
+ssize_t dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp,
+	void *user, ssize_t *lower, ssize_t *higher);
+
 static inline void *
 dvec_at(const struct dvec *dvec, size_t index)
 {
diff --git a/libdvec.api b/libdvec.api
index a8e364c..5a62560 100644
--- a/libdvec.api
+++ b/libdvec.api
@@ -17,3 +17,6 @@ dvec_replace
 
 dvec_iter_fwd
 dvec_iter_bwd
+
+dvec_bubble_sort
+dvec_binary_search
diff --git a/libdvec.lds b/libdvec.lds
index bcc3132..999010f 100644
--- a/libdvec.lds
+++ b/libdvec.lds
@@ -19,5 +19,8 @@ LIBDVEC_1.1.2 {
 
 		dvec_iter_fwd;
 		dvec_iter_bwd;
+
+		dvec_bubble_sort;
+		dvec_binary_search;
 	local: *;
 };
diff --git a/src/dvec.c b/src/dvec.c
index dac32b6..3ecef19 100644
--- a/src/dvec.c
+++ b/src/dvec.c
@@ -262,3 +262,74 @@ dvec_iter_bwd(const struct dvec *dvec, const void *p)
 		return NULL;
 	}
 }
+
+int
+dvec_bubble_sort(struct dvec *dvec, bool reverse, dvec_sort_order_fn in_order)
+{
+	void *cur, *next, *tmp;
+	size_t i, k;
+	int rc;
+
+	rc = dvec_reserve(dvec, dvec->len + 1);
+	if (rc) return rc;
+
+	tmp = dvec->data + dvec->len * dvec->dsize;
+
+	for (i = 1; i < dvec->len; i++) {
+		cur = dvec->data;
+		for (k = 0; k < dvec->len - i; k++) {
+			next = cur + dvec->dsize;
+			if (in_order(cur, next) == !reverse) {
+				memcpy(tmp, cur, dvec->dsize);
+				memcpy(cur, next, dvec->dsize);
+				memcpy(next, tmp, dvec->dsize);
+			}
+			cur = next;
+		}
+	}
+
+	return 0;
+}
+
+ssize_t
+dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp,
+	void *user, ssize_t *lower, ssize_t *higher)
+{
+	size_t min, max, pos;
+	int rc;
+
+	min = 0;
+	max = dvec->len;
+
+	if (lower) *lower = -1;
+	if (higher) *higher = -1;
+	while (min < max) {
+		pos = min + (max - min) / 2;
+		rc = search_cmp(dvec_at(dvec, pos), user);
+		if (!rc) {
+			if (lower && pos > 0)
+				*lower = (ssize_t) pos - 1;
+			if (higher && pos < dvec->len - 1)
+				*higher = (ssize_t) pos + 1;
+			return (ssize_t) pos;
+		} else if (rc > 0) {
+			if (pos + 1 == max) {
+				if (lower) *lower = (ssize_t) min;
+				if (higher && min < dvec->len - 1)
+					*higher = (ssize_t) min + 1;
+				break;
+			}
+			min = pos + 1;
+		} else {
+			if (min == pos) {
+				if (higher) *higher = (ssize_t) min;
+				if (lower && min > 0)
+					*lower = (ssize_t) min - 1;
+				break;
+			}
+			max = pos;
+		}
+	}
+
+	return -1;
+}
diff --git a/src/test.c b/src/test.c
index f7e1abb..6e93c32 100644
--- a/src/test.c
+++ b/src/test.c
@@ -2,6 +2,7 @@
 #include "dvec.h"
 
 #include <err.h>
+#include <stdbool.h>
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
@@ -13,27 +14,55 @@ static const char *dvec_err[] = {
 	DVEC_STRERR_INIT
 };
 
+bool
+str_sort_order(const void *p1, const void *p2)
+{
+	const char *s1 = *(const char **)p1;
+	const char *s2 = *(const char **)p2;
+
+	return strcmp(s1, s2) >= 0;
+}
+
+int
+str_search(const void *p, void *user)
+{
+	const char *str = *(const char **)p, *cmp = user;
+
+	return strcmp(cmp, str);
+}
+
 int
 main(int argc, const char **argv)
 {
 	struct dvec dvec;
+	ssize_t below, above, on;
 	int i, rc;
-	int *val;
+	const char **val;
 
-	rc = dvec_init(&dvec, sizeof(int), 16, &stdlib_heap_allocator);
+	rc = dvec_init(&dvec, sizeof(const char *), 16, &stdlib_heap_allocator);
 	if (rc) LIBDVEC_ERR(rc);
 
 	for (i = 1; i < argc; i++) {
 		rc = dvec_add_back(&dvec, 1);
 		if (rc) LIBDVEC_ERR(rc);
 		val = dvec_back(&dvec);
-		*val = atoi(argv[i]);
+		*val = argv[i];
 	}
 
+	rc = dvec_bubble_sort(&dvec, false, str_sort_order);
+	if (rc) LIBDVEC_ERR(rc);
+
+	on = dvec_binary_search(&dvec, str_search, "abc", &below, &above);
+
 	for (DVEC_ITER(&dvec, val))
-		printf("%i\n", *val);
+		printf("%s\n", *val);
 
 	printf("dvec len: %lu\n", dvec.len);
 
+	printf("\n");
+	printf("below: %li\n", below);
+	printf("on: %li\n", on);
+	printf("above: %li\n", above);
+
 	dvec_deinit(&dvec);
 }