Add bubble sort and binary search

1 files changed, 71 insertions, 0 deletions

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;
+}