commit e297fc2f651d3ed391bd3169f410806305fe14d0
parent 4310a29826e5263619355c3b8a6803f532e17e37
Author: Louis Burda <quent.burda@gmail.com>
Date: Mon, 20 May 2024 16:07:56 +0200
Modify error propagation and add modified status
Diffstat:
M | include/dvec.h | | | 23 | ++++++++++++++++------- |
M | src/dvec.c | | | 87 | +++++++++++++++++++++++++++++++++++++++++++------------------------------------ |
M | src/test.c | | | 17 | +++++++---------- |
3 files changed, 70 insertions(+), 57 deletions(-)
diff --git a/include/dvec.h b/include/dvec.h
@@ -3,16 +3,23 @@
#include "allocator.h"
#include <sys/types.h>
+#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h>
+#define DVEC_ERRNO(rc) ((rc) > 0 && (rc) & (1 << 30) ? (rc) & ~(1 << 30) : 0)
+#define DVEC_ERR(lut, rc) errx(1, "libdvec: %s", \
+ (rc) == DVEC_BAD ? lut[0] : (DVEC_ERRNO(rc) ? strerror(DVEC_ERRNO(rc)) : lut[rc+1]))
+
#define DVEC_ITER(dvec, p) (p) = NULL; ((p) = dvec_iter_fwd((dvec), (p)));
#define DVEC_ITER_BWD(dvec, p) (p) = NULL; ((p) = dvec_iter_bwd((dvec), (p)));
#define DVEC_STRERR_INIT \
- [DVEC_OK] = "Success", \
- [DVEC_LOCKED] = "Data vector locked"
+ [0] = "Failure", \
+ [1+DVEC_OK] = "Success", \
+ [1+DVEC_LOCKED] = "Locked", \
+ [1+DVEC_MODIFIED] = "Modified"
#ifdef LIBDVEC_ASSERT_ARGS
#include "stdlib.h"
@@ -29,8 +36,10 @@
#endif
enum {
+ DVEC_BAD = -1 & INT_MAX,
DVEC_OK = 0,
- DVEC_LOCKED = 1,
+ DVEC_LOCKED = 1 << 0,
+ DVEC_MODIFIED = 1 << 1
};
struct dvec {
@@ -42,8 +51,8 @@ struct dvec {
const struct allocator *allocator;
};
-typedef bool (*dvec_sort_order_fn)(const void *p1, const void *p2, void *u);
-typedef int (*dvec_search_cmp_fn)(const void *cur, void *user);
+typedef bool (*dvec_sort_order_fn)(const void *left, const void *right, const void *user);
+typedef int (*dvec_search_cmp_fn)(const void *other, const void *user);
int dvec_init(struct dvec *dvec, size_t dsize, size_t cap,
const struct allocator *allocator);
@@ -72,9 +81,9 @@ void *dvec_iter_fwd(const struct dvec *dvec, const void *p);
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);
+ void *tmp, bool reverse, dvec_sort_order_fn in_order, const 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);
+ void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user);
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/dvec.c b/src/dvec.c
@@ -3,16 +3,18 @@
#include <stddef.h>
#include <string.h>
+#define ERR(x) ((x) >= 0 ? DVEC_BAD : (x))
+
struct sort_order_user_proxy {
dvec_sort_order_fn order_fn;
- void *user;
+ const void *user;
};
int
dvec_init(struct dvec *dvec, size_t dsize, size_t cap,
const struct allocator *allocator)
{
- int rc;
+ int rc = 0;
LIBDVEC_ABORT_ON_ARGS(!dvec || !dsize || !allocator);
@@ -26,7 +28,7 @@ dvec_init(struct dvec *dvec, size_t dsize, size_t cap,
if (dvec->cap) {
dvec->data = allocator->alloc(allocator, cap * dsize, &rc);
LIBDVEC_ABORT_ON_ALLOC(!dvec->data);
- if (!dvec->data) return -rc;
+ if (!dvec->data) return ERR(rc);
}
return DVEC_OK;
@@ -42,29 +44,28 @@ dvec_deinit(struct dvec *dvec)
rc = dvec->allocator->free(dvec->allocator, dvec->data);
LIBDVEC_ABORT_ON_ALLOC(rc);
- return -rc;
+ return rc >= 0 ? DVEC_OK : ERR(rc);
}
struct dvec *
dvec_alloc(size_t dsize, size_t cap,
- const struct allocator *allocator, int *_rc)
+ const struct allocator *allocator, int *rc)
{
struct dvec *dvec;
- int *rc, stub;
+ int _rc;
LIBDVEC_ABORT_ON_ARGS(!allocator);
- rc = _rc ? _rc : &stub;
-
- dvec = allocator->alloc(allocator, sizeof(struct dvec), rc);
+ dvec = allocator->alloc(allocator, sizeof(struct dvec), &_rc);
LIBDVEC_ABORT_ON_ALLOC(!dvec);
if (!dvec) {
- *rc = -*rc;
+ if (rc) *rc = ERR(_rc);
return NULL;
}
- *rc = dvec_init(dvec, dsize, cap, allocator);
- if (*rc) {
+ _rc = dvec_init(dvec, dsize, cap, allocator);
+ if (_rc < 0) {
+ if (rc) *rc = _rc;
allocator->free(allocator, dvec);
return NULL;
}
@@ -80,19 +81,20 @@ aligned_size(size_t size, size_t dsize)
struct dvec *
dvec_alloc_fused(size_t dsize, size_t cap,
- const struct allocator *allocator, int *_rc)
+ const struct allocator *allocator, int *rc)
{
struct dvec *dvec;
- int *rc, stub;
size_t off;
+ int _rc = 0;
LIBDVEC_ABORT_ON_ARGS(!allocator);
- rc = _rc ? _rc : &stub;
-
off = aligned_size(sizeof(struct dvec), dsize);
- dvec = allocator->alloc(allocator, off + cap * dsize, rc);
- if (!dvec) return NULL;
+ dvec = allocator->alloc(allocator, off + cap * dsize, &_rc);
+ if (!dvec) {
+ if (_rc) *rc = ERR(_rc);
+ return NULL;
+ }
dvec->allocator = allocator;
dvec->dsize = dsize;
@@ -117,14 +119,14 @@ dvec_free(struct dvec *dvec)
if (dvec->fused) {
rc = allocator->free(allocator, dvec);
- if (rc) return -rc;
+ if (rc < 0) return rc;
} else {
rc = dvec_deinit(dvec);
if (rc) return rc;
rc = allocator->free(allocator, dvec);
LIBDVEC_ABORT_ON_ALLOC(rc);
- if (rc) return -rc;
+ if (rc < 0) return rc;
}
return DVEC_OK;
@@ -179,7 +181,7 @@ dvec_reserve(struct dvec *dvec, size_t len)
{
void *data;
size_t cap, off;
- int rc;
+ int rc = 1;
LIBDVEC_ABORT_ON_ARGS(!dvec);
@@ -195,14 +197,14 @@ dvec_reserve(struct dvec *dvec, size_t len)
data = dvec->allocator->realloc(dvec->allocator, dvec,
off + dvec->cap * dvec->dsize, &rc);
LIBDVEC_ABORT_ON_ALLOC(!data);
- if (!data) return -rc;
+ if (!data) return ERR(rc);
dvec = data;
dvec->data = (uint8_t *) dvec + off;
} else {
data = dvec->allocator->realloc(dvec->allocator,
dvec->data, cap * dvec->dsize, &rc);
LIBDVEC_ABORT_ON_ALLOC(!data);
- if (!data) return -rc;
+ if (!data) return ERR(rc);
dvec->data = data;
}
@@ -216,7 +218,7 @@ dvec_shrink(struct dvec *dvec)
{
void *data;
size_t cap, off;
- int rc;
+ int rc = 0;
LIBDVEC_ABORT_ON_ARGS(!dvec);
@@ -229,18 +231,18 @@ dvec_shrink(struct dvec *dvec)
data = dvec->allocator->realloc(dvec->allocator, dvec,
off + cap * dvec->dsize, &rc);
LIBDVEC_ABORT_ON_ALLOC(!data);
- if (!data) return -rc;
+ if (!data) return ERR(rc);
dvec = data;
dvec->data = (uint8_t *) dvec + off;
} else if (!dvec->len) {
rc = dvec->allocator->free(dvec->allocator, dvec->data);
LIBDVEC_ABORT_ON_ALLOC(rc);
- if (rc) return -rc;
+ if (rc < 0) return rc;
} else {
data = dvec->allocator->realloc(dvec->allocator,
&dvec->data, cap * dvec->dsize, &rc);
LIBDVEC_ABORT_ON_ALLOC(!data);
- if (!data) return -rc;
+ if (!data) return ERR(rc);
dvec->data = data;
}
@@ -342,13 +344,14 @@ dvec_quick_sort_swap(void *a, void *b, void *tmp, size_t dsize)
int
dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
- void *tmp, bool reverse, dvec_sort_order_fn in_order, void *user)
+ void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user)
{
+ const size_t dsize = dvec->dsize;
struct dvec stack;
- uint8_t *pivot, *lo, *hi;
uint8_t *start, *end;
- size_t dsize;
+ uint8_t *lo, *hi, *pivot;
bool lo_order, hi_order;
+ bool modified = false;
int rc;
if (!dvec->len) return DVEC_OK;
@@ -356,10 +359,9 @@ dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
rc = dvec_init(&stack, sizeof(uint8_t *), 32, allocator);
if (rc) return rc;
- dsize = dvec->dsize;
-
*(uint8_t **)dvec_push(&stack) = dvec_front(dvec);
*(uint8_t **)dvec_push(&stack) = dvec_back(dvec);
+
while (!dvec_empty(&stack)) {
end = *(uint8_t **)dvec_pop(&stack);
start = *(uint8_t **)dvec_pop(&stack);
@@ -367,13 +369,17 @@ dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
if (start == end) continue;
if (start + dsize >= end) {
- if (!in_order(start, end, user))
+ if (!in_order(start, end, user)) {
dvec_quick_sort_swap(start, end, tmp, dsize);
+ modified = true;
+ }
continue;
}
+ lo = start;
+ hi = end;
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);
@@ -381,6 +387,7 @@ dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
if (lo == pivot) pivot = hi;
else if (hi == pivot) pivot = lo;
dvec_quick_sort_swap(lo, hi, tmp, dsize);
+ modified = true;
}
if (lo_order) lo += dsize;
if (hi_order) hi -= dsize;
@@ -399,13 +406,13 @@ dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator,
dvec_deinit(&stack);
- return DVEC_OK;
+ return modified ? DVEC_MODIFIED : DVEC_OK;
}
static bool
-dvec_quick_sort_ex_order(const void *p1, const void *p2, void *user)
+dvec_quick_sort_ex_order(const void *p1, const void *p2, const void *user)
{
- struct sort_order_user_proxy *user_proxy = user;
+ const 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);
@@ -413,9 +420,9 @@ dvec_quick_sort_ex_order(const void *p1, const void *p2, 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)
+ void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user)
{
- struct sort_order_user_proxy user_proxy = {
+ const struct sort_order_user_proxy user_proxy = {
.order_fn = in_order,
.user = user
};
@@ -468,9 +475,9 @@ dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp,
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);
diff --git a/src/test.c b/src/test.c
@@ -7,15 +7,12 @@
#include <string.h>
#include <stdlib.h>
-#define LIBDVEC_ERR(rc) errx(1, "libdvec: %s", \
- rc < 0 ? strerror(-rc) : dvec_err[rc])
-
static const char *dvec_err[] = {
DVEC_STRERR_INIT
};
bool
-str_sort_order(const void *p1, const void *p2, void *user)
+str_sort_order(const void *p1, const void *p2, const void *user)
{
const char *s1 = *(const char **)p1;
const char *s2 = *(const char **)p2;
@@ -24,7 +21,7 @@ str_sort_order(const void *p1, const void *p2, void *user)
}
int
-str_search(const void *p, void *user)
+str_search(const void *p, const void *user)
{
const char *str = *(const char **)p, *cmp = user;
@@ -40,18 +37,18 @@ main(int argc, const char **argv)
int i, rc;
rc = dvec_init(&dvec, sizeof(const char *), 16, &stdlib_heap_allocator);
- if (rc) LIBDVEC_ERR(rc);
+ if (rc) DVEC_ERR(dvec_err, rc);
for (i = 1; i < argc; i++) {
rc = dvec_add_back(&dvec, 1);
- if (rc) LIBDVEC_ERR(rc);
+ if (rc) DVEC_ERR(dvec_err, rc);
val = dvec_back(&dvec);
*val = argv[i];
}
rc = dvec_quick_sort_ex(&dvec, &stdlib_heap_allocator, &tmp,
false, str_sort_order, NULL);
- if (rc) LIBDVEC_ERR(rc);
+ if (rc < 0) DVEC_ERR(dvec_err, rc);
on = dvec_binary_search(&dvec, str_search, "abc", &below, &above);
@@ -68,13 +65,13 @@ main(int argc, const char **argv)
fused = dvec_alloc_fused(sizeof(const char *), 0,
&stdlib_heap_allocator, &rc);
- if (!fused) LIBDVEC_ERR(rc);
+ if (!fused) DVEC_ERR(dvec_err, rc);
printf("fused: %p %p (+%li)\n", (void *) fused,
fused->data, fused->data - (uint8_t *) fused);
rc = dvec_free(fused);
- if (rc) LIBDVEC_ERR(rc);
+ if (rc) DVEC_ERR(dvec_err, rc);
dvec_deinit(&dvec);
}