commit 046c59cd98066bc1fe9e48a27e048213ea80dede
parent f2542dd0d235474b6df46dcb7f5b4eafbccfde48
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 26 May 2023 04:02:39 +0200
Add bubble sort and binary search
Diffstat:
5 files changed, 120 insertions(+), 4 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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);
}