summaryrefslogtreecommitdiffstats
path: root/lib/libdvec/src/dvec.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/libdvec/src/dvec.c')
-rw-r--r--lib/libdvec/src/dvec.c87
1 files changed, 47 insertions, 40 deletions
diff --git a/lib/libdvec/src/dvec.c b/lib/libdvec/src/dvec.c
index 52226dc..bc71f3f 100644
--- a/lib/libdvec/src/dvec.c
+++ b/lib/libdvec/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);
generated by cgit v1.2.3-71-gd317 (git 2.46.0) at 2025-12-16 04:56:56 +0000