pkbktarr: add _find_first_index and _iterate

2 files changed, 143 insertions, 0 deletions

diff --git a/pkbktarr.h b/pkbktarr.h
index ea0fab4..a263f61 100644
--- a/pkbktarr.h
+++ b/pkbktarr.h
@@ -10,6 +10,9 @@
 #define PK_BKT_ARR_HANDLE_B_MAX 0xFFFFFF
 #define PK_BKT_ARR_HANDLE_I_MAX 64
 
+typedef bool (pk_bkt_arr_compare_fn)(void *user_data, void *obj_data);
+typedef void (pk_bkt_arr_iterate_fn)(void *obj_data);
+
 struct pk_bkt_arr_handle {
 	unsigned int b : 24;
 	unsigned int i : 8;
@@ -28,8 +31,18 @@ struct pk_bkt_arr {
 	unsigned long alignment;
 };
 
+enum PK_BKT_ARR_HANDLE_VALIDATION : uint8_t {
+	PK_BKT_ARR_HANDLE_VALIDATION_VALID                      = 0,
+	PK_BKT_ARR_HANDLE_VALIDATION_BUCKET_INDEX_TOO_HIGH      = 1 << 0,
+	PK_BKT_ARR_HANDLE_VALIDATION_ITEM_INDEX_TOO_HIGH        = 2 << 1,
+};
+
+enum PK_BKT_ARR_HANDLE_VALIDATION pk_bkt_arr_handle_validate(struct pk_bkt_arr *bkt_arr, struct pk_bkt_arr_handle handle);
+
 void pk_bkt_arr_init(struct pk_bkt_arr *bkt_arr, unsigned long stride, unsigned long alignment, struct pk_bkt_arr_handle limits, struct pk_membucket *bkt_buckets, struct pk_membucket *bkt_data);
 void pk_bkt_arr_clear(struct pk_bkt_arr *bkt_arr);
+struct pk_bkt_arr_handle pk_bkt_arr_find_first_handle(struct pk_bkt_arr *bkt_arr, void *user_data, pk_bkt_arr_compare_fn fn);
+void pk_bkt_arr_iterate(struct pk_bkt_arr *bkt_arr, pk_bkt_arr_iterate_fn fn);
 void pk_bkt_arr_teardown(struct pk_bkt_arr *bkt_arr);
 struct pk_bkt_arr_handle pk_bkt_arr_new_handle(struct pk_bkt_arr *bkt_arr);
 void pk_bkt_arr_free_handle(struct pk_bkt_arr *bkt_arr, struct pk_bkt_arr_handle handle);
@@ -76,6 +89,20 @@ T &pk_bkt_arr_t<T>::operator[](struct pk_bkt_arr_handle handle) {
 #include <assert.h>
 #include <string.h>
 
+enum PK_BKT_ARR_HANDLE_VALIDATION pk_bkt_arr_handle_validate(struct pk_bkt_arr *bkt_arr, struct pk_bkt_arr_handle handle) {
+	assert(bkt_arr != NULL);
+	uint8_t ret = 0;
+	if (handle.b >= bkt_arr->reserved_buckets || handle.b >= bkt_arr->limits.b) {
+		ret |= PK_BKT_ARR_HANDLE_VALIDATION_BUCKET_INDEX_TOO_HIGH;
+	}
+	if (handle.b == bkt_arr->reserved_buckets-1 && handle.i > bkt_arr->head_r.i) {
+		ret |= PK_BKT_ARR_HANDLE_VALIDATION_ITEM_INDEX_TOO_HIGH;
+	} else if (handle.b < bkt_arr->reserved_buckets-1 && handle.i > bkt_arr->limits.i) {
+		ret |= PK_BKT_ARR_HANDLE_VALIDATION_ITEM_INDEX_TOO_HIGH;
+	}
+	return (enum PK_BKT_ARR_HANDLE_VALIDATION)ret;
+}
+
 void pk_bkt_arr_init(struct pk_bkt_arr *bkt_arr, unsigned long stride, unsigned long alignment, struct pk_bkt_arr_handle limits, struct pk_membucket *bkt_buckets, struct pk_membucket *bkt_data)
 {
 	assert(limits.b <= PK_BKT_ARR_HANDLE_B_MAX);
@@ -109,6 +136,46 @@ void pk_bkt_arr_clear(struct pk_bkt_arr *bkt_arr) {
 	}
 }
 
+struct pk_bkt_arr_handle pk_bkt_arr_find_first_handle(struct pk_bkt_arr *bkt_arr, void *user_data, pk_bkt_arr_compare_fn fn) {
+	assert(bkt_arr != NULL);
+	assert(fn != NULL);
+	struct pk_bkt_arr_handle ret;
+	unsigned int b, i, ii;
+	ret.b = PK_BKT_ARR_HANDLE_B_MAX;
+	ret.i = PK_BKT_ARR_HANDLE_I_MAX;
+	for (b = 0; b < bkt_arr->reserved_buckets; ++b) {
+		char *arr = ((char**)(bkt_arr->bucketed_data))[b];
+		ii = b == bkt_arr->reserved_buckets-1 ? bkt_arr->head_r.i : bkt_arr->limits.i;
+		for (i = 0; i < ii; ++i) {
+			if (PK_HAS_FLAG(bkt_arr->idx_unused[b], 1ull << i)) {
+				continue;
+			}
+			if (fn(user_data, arr+(bkt_arr->stride * i))) {
+				ret.b = b;
+				ret.i = i;
+				return ret;
+			}
+		}
+	}
+	return ret;
+}
+
+void pk_bkt_arr_iterate(struct pk_bkt_arr *bkt_arr, pk_bkt_arr_iterate_fn fn) {
+	assert(bkt_arr != NULL);
+	assert(fn != NULL);
+	unsigned int b, i, ii;
+	for (b = 0; b < bkt_arr->reserved_buckets; ++b) {
+		char *arr = ((char**)(bkt_arr->bucketed_data))[b];
+		ii = b == bkt_arr->reserved_buckets-1 ? bkt_arr->head_r.i : bkt_arr->limits.i;
+		for (i = 0; i < ii; ++i) {
+			if (PK_HAS_FLAG(bkt_arr->idx_unused[b], 1ull << i)) {
+				continue;
+			}
+			fn(arr+(bkt_arr->stride * i));
+		}
+	}
+}
+
 void pk_bkt_arr_teardown(struct pk_bkt_arr *bkt_arr)
 {
 	int b;
@@ -183,6 +250,7 @@ done:
 void pk_bkt_arr_free_handle(struct pk_bkt_arr *bkt_arr, struct pk_bkt_arr_handle handle)
 {
 	assert(bkt_arr != nullptr);
+	assert(pk_bkt_arr_handle_validate(bkt_arr, handle) == PK_BKT_ARR_HANDLE_VALIDATION_VALID);
 	bkt_arr->idx_unused[handle.b] |= (1ull << handle.i);
 	if (handle.b < bkt_arr->head_l.b || (handle.b == bkt_arr->head_l.b && handle.i < bkt_arr->head_l.i)) {
 		bkt_arr->head_l = handle;
diff --git a/test/pkbktarr.c b/test/pkbktarr.c
index 1750359..55cf3df 100644
--- a/test/pkbktarr.c
+++ b/test/pkbktarr.c
@@ -23,10 +23,23 @@ exit(int code)
 	}
 }
 
+bool find_int_val(void *user_data, void *arr_item) {
+	int lhs = *((int*)user_data);
+	int rhs = *((int*)arr_item);
+	return lhs == rhs;
+}
+
+static int global_counter = 0;
+void iter(void *arr_item) {
+	(void)arr_item;
+	global_counter += 1;
+}
+
 void test_spinup(struct pk_membucket **bkt_buckets, struct pk_membucket **bkt_data)
 {
 	*bkt_buckets = pk_bucket_create("buckets", 1 << 16, false);
 	*bkt_data = pk_bucket_create("data", 1 << 16, false);
+	global_counter = 0;
 }
 
 void test_teardown(struct pk_membucket **bkt_buckets, struct pk_membucket **bkt_data)
@@ -170,6 +183,68 @@ int main(int argc, char *argv[])
 	}
 	test_teardown(&bkt_buckets, &bkt_data);
 
+	// test find
+	test_spinup(&bkt_buckets, &bkt_data);
+	{
+		assert(bkt_buckets != nullptr);
+		assert(bkt_data != nullptr);
+		struct pk_bkt_arr arr = {0};
+		struct pk_bkt_arr_handle limits;
+		limits.b = PK_BKT_ARR_HANDLE_B_MAX;
+		limits.i = PK_BKT_ARR_HANDLE_I_MAX;
+		pk_bkt_arr_init(&arr, sizeof(int), alignof(int), limits, bkt_buckets, bkt_data);
+
+		struct pk_bkt_arr_handle h = pk_bkt_arr_new_handle(&arr);
+		if (h.b != 0) exit(1);
+		if (h.i != 0) exit(1);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 1) exit(1);
+		if (arr.head_r.b != 0) exit(1);
+		if (arr.head_r.i != 1) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 1) exit(1);
+
+		int val = 69;
+		((int**)arr.bucketed_data)[h.b][h.i] = val;
+		struct pk_bkt_arr_handle found_h = pk_bkt_arr_find_first_handle(&arr, &val, find_int_val);
+		if (pk_bkt_arr_handle_compare(h, found_h) != 0) exit(1);
+
+		pk_bkt_arr_teardown(&arr);
+		if (bkt_buckets->allocs != 0) exit(1);
+		if (bkt_data->allocs != 0) exit(1);
+	}
+	test_teardown(&bkt_buckets, &bkt_data);
+
+	// test iterate
+	test_spinup(&bkt_buckets, &bkt_data);
+	{
+		assert(bkt_buckets != nullptr);
+		assert(bkt_data != nullptr);
+		struct pk_bkt_arr arr = {0};
+		struct pk_bkt_arr_handle limits;
+		limits.b = PK_BKT_ARR_HANDLE_B_MAX;
+		limits.i = PK_BKT_ARR_HANDLE_I_MAX;
+		pk_bkt_arr_init(&arr, sizeof(int), alignof(int), limits, bkt_buckets, bkt_data);
+
+		struct pk_bkt_arr_handle h = pk_bkt_arr_new_handle(&arr);
+		if (h.b != 0) exit(1);
+		if (h.i != 0) exit(1);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 1) exit(1);
+		if (arr.head_r.b != 0) exit(1);
+		if (arr.head_r.i != 1) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 1) exit(1);
+
+		pk_bkt_arr_iterate(&arr, iter);
+		if (global_counter != 1) exit(1);
+
+		pk_bkt_arr_teardown(&arr);
+		if (bkt_buckets->allocs != 0) exit(1);
+		if (bkt_data->allocs != 0) exit(1);
+	}
+	test_teardown(&bkt_buckets, &bkt_data);
+
 	// test release & re-use slot
 	test_spinup(&bkt_buckets, &bkt_data);
 	{