pkbktarr: created + bump pk.h version to 0.4.3

6 files changed, 699 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index 630516a..a6aedb9 100644
--- a/Makefile
+++ b/Makefile
@@ -14,6 +14,7 @@ SRC =  \
 	pkarr.h \
 	pkstn.h \
 	pkuuid.h \
+	pkbktarr.h \
 	test/pkmacros.c \
 	test/pkmacros.cpp \
 	test/pkmem-types.c \
@@ -32,6 +33,8 @@ SRC =  \
 	test/pktmr.cpp \
 	test/pkuuid.c\
 	test/pkuuid.cpp \
+	test/pkbktarr.c\
+	test/pkbktarr.cpp \
 
 OBJ = $(SRC:%.c=.o)
 PPOBJ = $(SRC:%.cpp=.so)
@@ -48,6 +51,7 @@ all: options .WAIT clean .WAIT \
 	pkstn \
 	pktmr \
 	pkuuid \
+	pkbktarr \
 	test/test-pkmem-types test/test-pkmem-types-cpp \
 	test/test-pkmem test/test-pkmem-cpp \
 	test/test-pkmacros test/test-pkmacros-cpp \
@@ -57,6 +61,7 @@ all: options .WAIT clean .WAIT \
 	test/test-pkstn test/test-pkstn-cpp \
 	test/test-pktmr test/test-pktmr-cpp \
 	test/test-pkuuid test/test-pkuuid-cpp \
+	test/test-pkbktarr test/test-pkbktarr-cpp \
 
 options:
 	@echo at-suite build options:
@@ -98,6 +103,8 @@ pktmr: pktmr.gch pktmr.gchpp
 
 pkuuid: pkuuid.gch pkuuid.gchpp
 
+pkbktarr: pkbktarr.gch pkbktarr.gchpp
+
 build: pkmacros
 build: pkmem-types
 build: pkmem
@@ -107,6 +114,7 @@ build: pkarr
 build: pkstn
 build: pktmr
 build: pkuuid
+build: pkbktarr
 	echo "#ifndef PK_SINGLE_HEADER_FILE_H\n#define PK_SINGLE_HEADER_FILE_H" > pk.h
 	cat pk.h.in \
 	pkmacros.h \
@@ -118,6 +126,7 @@ build: pkuuid
 	pkstn.h \
 	pktmr.h \
 	pkuuid.h \
+	pkbktarr.h \
 	>> pk.h
 	echo "#endif /* PK_SINGLE_HEADER_FILE_H */" >> pk.h
 	sed -i -r \
@@ -182,6 +191,12 @@ test/test-pkuuid: test/pkuuid.o
 test/test-pkuuid-cpp: test/pkuuid.so
 	$(CXX) -g -O3 -std=c++23 $(CXXFLAGS) -o $@ $^ $(LDFLAGS)
 
+test/test-pkbktarr: test/pkbktarr.o
+	$(CC) -g -O3 -std=c2x $(CFLAGS) -o $@ $^ $(LDFLAGS)
+
+test/test-pkbktarr-cpp: test/pkbktarr.so
+	$(CXX) -g -O3 -std=c++23 $(CXXFLAGS) -o $@ $^ $(LDFLAGS)
+
 test: pkmacros pkmem-types pkmem pkstr pkev pkarr
 test: test/test-pkmacros test/test-pkmacros-cpp
 test: test/test-pkmem-types test/test-pkmem-types-cpp
@@ -192,6 +207,7 @@ test: test/test-pkarr test/test-pkarr-cpp
 test: test/test-pkstn test/test-pkstn-cpp
 test: test/test-pktmr test/test-pktmr-cpp
 test: test/test-pkuuid test/test-pkuuid-cpp
+test: test/test-pkbktarr test/test-pkbktarr-cpp
 test:
 	@echo ""
 	./test/test-pkmacros ; echo Result: $$? "\n"
@@ -212,6 +228,8 @@ test:
 	./test/test-pktmr-cpp ; echo Result: $$? "\n"
 	./test/test-pkuuid ; echo Result: $$? "\n"
 	./test/test-pkuuid-cpp ; echo Result: $$? "\n"
+	./test/test-pkbktarr ; echo Result: $$? "\n"
+	./test/test-pkbktarr-cpp ; echo Result: $$? "\n"
 
 clean:
 	rm -f *.plist *.gch *.gchpp *.o *.so test/*.o test/*.so test/test-*
diff --git a/config.mk b/config.mk
index 49708a8..83c26be 100644
--- a/config.mk
+++ b/config.mk
@@ -1,5 +1,5 @@
 # pk.h version
-VERSION = 0.4.2
+VERSION = 0.4.3
 
 # paths
 PREFIX = /usr/local
@@ -23,6 +23,7 @@ SHARED_FLAGS = -D_DEFAULT_SOURCE -D_POSIX_C_SOURCE=200809L \
  -DPK_IMPL_ARR \
  -DPK_IMPL_STN \
  -DPK_IMPL_UUID \
+ -DPK_IMPL_BKTARR \
 
 CFLAGS       += -Wall -Wextra -pedantic $(INCS) $(SHARED_FLAGS)
 CXXFLAGS     += -Wall -Wextra -pedantic $(INCS) $(SHARED_FLAGS)
diff --git a/pk.h.in b/pk.h.in
index 0fcad06..5142c76 100644
--- a/pk.h.in
+++ b/pk.h.in
@@ -213,6 +213,44 @@
 *  2 times for each uuidv7 to fill 74 bits with random data (with an XOR for the
 *  remaining 10 bits).
 *
+********************************************************************************
+* pkbktarr.h: define PK_IMPL_BKTARR before including pk.h to enable ad-hoc.
+*
+* Provides a struct for bucketed data allocation.
+*
+* Maximum (default) bucket limits are as follows:
+* buckets:        0xFFFFFF    (16777215)
+* items/bucket:   0x40        (64)
+*
+* Note that you may specify separate `pk_membucket`s for the the struct's
+*  arrays `bucketed_data` + `idx_unused`, and the actual bucketed array data
+*  found within `bucketed_data`.
+* If the `pk_membucket` for "data" is exclusive to this struct, each bucket (and
+*  by extension, the data) will be contiguious in memory.
+*
+* Examples:
+* ```c
+* struct pk_bkt_arr_handle custom_limits;
+* custom_limits.b = 8;
+* custom_limits.i = 8;
+* struct pk_bkt_arr arr;
+* pk_bkt_arr_init(
+*   &arr, sizeof(int), alignof(int), custom_limits, bkt_buckets, bkt_data);
+* struct pk_bkt_arr_handle h = pk_bkt_arr_new_handle(&arr);
+* int **int_ptrs = (int**)arr.bucketed_data;
+* int_ptrs[h.b][h.i] = 128;
+* pk_bkt_arr_free_handle(&arr, h);
+* pk_bkt_arr_teardown(&arr);
+* ```
+* ```c++
+* // default limits, no pk_membucket
+* struct pk_bkt_arr<int> arr();
+* struct pk_bkt_arr_handle h = pk_bkt_arr_new_handle(&arr);
+* arr[h] = 128;
+* pk_bkt_arr_free_handle(&arr, h);
+* arr.~pk_bkt_arr<int>(); // manually call dtor for globals
+* ```
+*
 *******************************************************************************/
 
 #define PK_VERSION "@@PK_VERSION@@"
@@ -239,4 +277,7 @@
 # ifndef PK_IMPL_UUID
 #  define PK_IMPL_UUID
 # endif
+# ifndef PK_IMPL_BKTARR
+#  define PK_IMPL_BKTARR
+# endif
 #endif
diff --git a/pkbktarr.h b/pkbktarr.h
new file mode 100644
index 0000000..7ab9840
--- /dev/null
+++ b/pkbktarr.h
@@ -0,0 +1,208 @@
+#ifndef PK_PKBKTARR_H
+#define PK_PKBKTARR_H
+
+#include "./pkmem.h" /* deleteme */
+#include "./pkmacros.h" /* deleteme */
+
+#define PK_BKT_ARR_HANDLE_B_MAX 0xFFFFFF
+#define PK_BKT_ARR_HANDLE_I_MAX 64
+
+struct pk_bkt_arr_handle {
+	unsigned int b : 24;
+	unsigned int i : 8;
+};
+
+struct pk_bkt_arr {
+	struct pk_membucket *bkt_buckets;
+	struct pk_membucket *bkt_data;
+	unsigned long long *idx_unused;
+	void **bucketed_data;
+	struct pk_bkt_arr_handle head_l;
+	struct pk_bkt_arr_handle head_r;
+	struct pk_bkt_arr_handle limits;
+	unsigned int reserved_buckets;
+	unsigned long stride;
+	unsigned long alignment;
+};
+
+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_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);
+int pk_bkt_arr_handle_compare(struct pk_bkt_arr_handle lhs, struct pk_bkt_arr_handle rhs);
+struct pk_bkt_arr_handle pk_bkt_arr_handle_increment(struct pk_bkt_arr *arr, struct pk_bkt_arr_handle h);
+struct pk_bkt_arr_handle pk_bkt_arr_handle_decrement(struct pk_bkt_arr *arr, struct pk_bkt_arr_handle h);
+
+#if defined (__cplusplus)
+template<typename T>
+struct pk_bkt_arr_t : public pk_bkt_arr {
+	pk_bkt_arr_t();
+	pk_bkt_arr_t(struct pk_bkt_arr_handle limits, struct pk_membucket *bkt_buckets = nullptr, struct pk_membucket *bkt_data = nullptr);
+	~pk_bkt_arr_t();
+	T &operator[](struct pk_bkt_arr_handle);
+};
+template<typename T>
+pk_bkt_arr_t<T>::pk_bkt_arr_t() {
+	pk_bkt_arr_init(this, sizeof(T), alignof(T), {PK_BKT_ARR_HANDLE_B_MAX, PK_BKT_ARR_HANDLE_I_MAX}, nullptr, nullptr);
+}
+template<typename T>
+pk_bkt_arr_t<T>::pk_bkt_arr_t(struct pk_bkt_arr_handle limits, struct pk_membucket *bkt_buckets, struct pk_membucket *bkt_data) {
+	pk_bkt_arr_init(this, sizeof(T), alignof(T), limits, bkt_buckets, bkt_data);
+}
+template<typename T>
+pk_bkt_arr_t<T>::~pk_bkt_arr_t() {
+	pk_bkt_arr_teardown(this);
+}
+template<typename T>
+T &pk_bkt_arr_t<T>::operator[](struct pk_bkt_arr_handle handle) {
+	assert(this->idx_unused != nullptr);
+	assert(this->bucketed_data != nullptr);
+	assert(handle.b <= this->limits.b);
+	assert(handle.i <= this->limits.i);
+	assert(handle.b != this->head_r.b || handle.i < this->head_r.i);
+	T** two_star_programmer = reinterpret_cast<T**>(this->bucketed_data);
+	return two_star_programmer[handle.b][handle.i];
+}
+#endif
+
+#endif /* PK_PKBKTARR_H */
+#ifdef PK_IMPL_BKTARR
+
+#include <assert.h>
+#include <string.h>
+
+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);
+	assert(limits.i <= PK_BKT_ARR_HANDLE_I_MAX);
+	assert(bkt_arr != nullptr);
+	memset(bkt_arr, 0, sizeof(struct pk_bkt_arr));
+	bkt_arr->bkt_buckets = bkt_buckets;
+	bkt_arr->bkt_data = bkt_data;
+	bkt_arr->head_l.b = 0ul;
+	bkt_arr->head_l.i = 0ul;
+	bkt_arr->head_r.b = 0ul;
+	bkt_arr->head_r.i = 0ul;
+	bkt_arr->limits = limits;
+	bkt_arr->reserved_buckets = 1;
+	bkt_arr->stride = stride;
+	bkt_arr->alignment = alignment;
+	bkt_arr->idx_unused = (unsigned long long *)pk_new(sizeof(unsigned long long), alignof(unsigned long long), bkt_buckets);
+	bkt_arr->idx_unused[0] = 0xFFFFFFFFFFFFFFFF;
+	bkt_arr->bucketed_data = (void **)pk_new(sizeof(void *), alignof(void *), bkt_buckets);
+	bkt_arr->bucketed_data[0] = pk_new(stride * limits.i, alignment, bkt_data);
+}
+
+void pk_bkt_arr_teardown(struct pk_bkt_arr *bkt_arr)
+{
+	int b;
+	size_t sz = bkt_arr->limits.i * bkt_arr->stride;
+	if (bkt_arr->idx_unused == nullptr && bkt_arr->bucketed_data == nullptr) return;
+	for (b = bkt_arr->reserved_buckets - 1; b > -1; --b) {
+		pk_delete(bkt_arr->bucketed_data[b], sz, bkt_arr->bkt_data);
+	}
+	pk_delete((void *)bkt_arr->idx_unused, sizeof(unsigned long long) * (bkt_arr->reserved_buckets), bkt_arr->bkt_buckets);
+	pk_delete((void *)bkt_arr->bucketed_data, sizeof(void *) * (bkt_arr->reserved_buckets), bkt_arr->bkt_buckets);
+	memset(bkt_arr, 0, sizeof(struct pk_bkt_arr));
+}
+
+struct pk_bkt_arr_handle pk_bkt_arr_new_handle(struct pk_bkt_arr *bkt_arr)
+{
+	struct pk_bkt_arr_handle ret;
+	unsigned int b, i, ii;
+	assert(bkt_arr != nullptr);
+	// if we have an existing open slot
+	if (pk_bkt_arr_handle_compare(bkt_arr->head_l, bkt_arr->head_r) != 0) {
+		ret = bkt_arr->head_l;
+		for (b = bkt_arr->head_l.b; b < bkt_arr->reserved_buckets; ++b) {
+			if (bkt_arr->idx_unused[b] == 0ull) continue;
+			// I feel like you could do a binary search here, but for 64 elements is it worth it?
+			i = bkt_arr->head_l.b == b ? bkt_arr->head_l.i + 1 : 0;
+			ii = bkt_arr->head_r.b == b ? bkt_arr->head_r.i : PK_MIN(64, bkt_arr->limits.i);
+			for (; i < ii; ++i) {
+				if (bkt_arr->idx_unused[b] & (1ull << i)) {
+					bkt_arr->head_l.b = b;
+					bkt_arr->head_l.i = i;
+					goto done;
+				}
+			}
+		}
+		bkt_arr->head_l = bkt_arr->head_r;
+		goto done;
+	}
+	if (pk_bkt_arr_handle_compare(pk_bkt_arr_handle_increment(bkt_arr, bkt_arr->head_l), bkt_arr->head_l) == 0 && bkt_arr->reserved_buckets == bkt_arr->limits.b && bkt_arr->idx_unused[bkt_arr->head_r.b] == 0) {
+		PK_LOGV_ERR("[pk_bkt_arr_new_handle] Exceeded bucket limits!: b:%u i:%u\n", bkt_arr->limits.b, bkt_arr->limits.i);
+		exit(1);
+	}
+	if (bkt_arr->head_r.b == bkt_arr->reserved_buckets && bkt_arr->head_r.i == 0) {
+		bkt_arr->reserved_buckets += 1;
+
+		unsigned long long *new_idx_unused = (unsigned long long *)pk_new(sizeof(unsigned long long) * bkt_arr->reserved_buckets, alignof(unsigned long long), bkt_arr->bkt_buckets);
+		void **new_data_ptrs = (void **)pk_new(sizeof(void *) * bkt_arr->reserved_buckets, alignof(void *), bkt_arr->bkt_buckets);
+
+		for (b = 0; b < bkt_arr->reserved_buckets - 1; ++b) {
+			new_idx_unused[b] = bkt_arr->idx_unused[b];
+			new_data_ptrs[b] = bkt_arr->bucketed_data[b];
+		}
+		new_idx_unused[bkt_arr->reserved_buckets - 1] = 0xFFFFFFFFFFFFFFFF;
+		new_data_ptrs[bkt_arr->reserved_buckets - 1] = pk_new(bkt_arr->stride * bkt_arr->limits.i, bkt_arr->alignment, bkt_arr->bkt_data);
+
+		pk_delete((void *)bkt_arr->idx_unused, sizeof(unsigned long long) * (bkt_arr->reserved_buckets - 1), bkt_arr->bkt_buckets);
+		pk_delete((void *)bkt_arr->bucketed_data, sizeof(void *) * (bkt_arr->reserved_buckets - 1), bkt_arr->bkt_buckets);
+		bkt_arr->idx_unused = new_idx_unused;
+		bkt_arr->bucketed_data = new_data_ptrs;
+	}
+	ret = bkt_arr->head_r;
+	bkt_arr->head_r = pk_bkt_arr_handle_increment(bkt_arr, bkt_arr->head_r);
+	bkt_arr->head_l = pk_bkt_arr_handle_increment(bkt_arr, bkt_arr->head_l);
+done:
+	bkt_arr->idx_unused[ret.b] &= ~(1ull << ret.i);
+	return ret;
+}
+
+void pk_bkt_arr_free_handle(struct pk_bkt_arr *bkt_arr, struct pk_bkt_arr_handle handle)
+{
+	assert(bkt_arr != nullptr);
+	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;
+		return;
+	}
+}
+
+int pk_bkt_arr_handle_compare(struct pk_bkt_arr_handle lhs, struct pk_bkt_arr_handle rhs)
+{
+	if (lhs.b == rhs.b && lhs.i == rhs.i) return 0;
+	if (lhs.b == rhs.b) return (int)rhs.i - (int)lhs.i;
+	return (int)rhs.b - (int)lhs.b;
+}
+
+struct pk_bkt_arr_handle pk_bkt_arr_handle_increment(struct pk_bkt_arr *arr, struct pk_bkt_arr_handle h)
+{
+	h.i += 1;
+	if (arr->limits.i == h.i) {
+		if (h.b + 1 < arr->limits.b) {
+			h.b += 1;
+			h.i = 0;
+		} else {
+			h.i -= 1;
+		}
+	}
+	return h;
+}
+
+struct pk_bkt_arr_handle pk_bkt_arr_handle_decrement(struct pk_bkt_arr *arr, struct pk_bkt_arr_handle h)
+{
+	if (h.i == 0) {
+		if (h.b != 0) {
+			h.b -= 1;
+			h.i = arr->limits.i;
+		} else {
+			return h;
+		}
+	}
+	h.i -= 1;
+	return h;
+}
+
+#endif /* PK_IMPL_BKTARR */
diff --git a/test/pkbktarr.c b/test/pkbktarr.c
new file mode 100644
index 0000000..2a00807
--- /dev/null
+++ b/test/pkbktarr.c
@@ -0,0 +1,367 @@
+
+#include "../pkbktarr.h"
+
+#include <setjmp.h>
+#include <unistd.h>
+
+static bool expected_exit = false;
+static bool caught = false;
+static jmp_buf jmp_env;
+// https://stackoverflow.com/questions/64190847/how-to-catch-a-call-to-exit-for-unit-testing
+// stub function
+void
+exit(int code)
+{
+	if (expected_exit) {
+		caught = true;
+		longjmp(jmp_env, 1);
+	} else {
+		_exit(code);
+	}
+}
+
+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);
+}
+
+void test_teardown(struct pk_membucket **bkt_buckets, struct pk_membucket **bkt_data)
+{
+	pk_bucket_destroy(*bkt_buckets);
+	pk_bucket_destroy(*bkt_data);
+	*bkt_buckets = nullptr;
+	*bkt_data = nullptr;
+}
+
+int main(int argc, char *argv[])
+{
+	(void)argc;
+	(void)argv;
+	int b, i, v;
+
+	struct pk_membucket *bkt_buckets = nullptr;
+	struct pk_membucket *bkt_data = nullptr;
+
+	// test ancillary
+	{
+		struct pk_bkt_arr_handle handles[2][2];
+		for (b = 0; b < 2; ++b) {
+			for (i = 0; i < 2; ++i) {
+				handles[b][i].b = b;
+				handles[b][i].i = i;
+			}
+		}
+		if (v = pk_bkt_arr_handle_compare(handles[0][0], handles[0][0]), v != 0) exit(1);
+		if (v = pk_bkt_arr_handle_compare(handles[1][0], handles[1][1]), v <= 0) exit(1);
+		if (v = pk_bkt_arr_handle_compare(handles[1][1], handles[1][0]), v >= 0) exit(1);
+	}
+
+	// test ancillary 2
+	{
+		struct pk_bkt_arr arr;
+		struct pk_bkt_arr_handle h1, h2;
+		arr.limits.b = 3;
+		arr.limits.i = 3;
+
+		h1.b = 0;
+		h1.i = 0;
+		if (h2 = pk_bkt_arr_handle_increment(&arr, h1), h2.b != 0 || h2.i != 1) exit(1);
+		h1.b = 1;
+		h1.i = 1;
+		if (h2 = pk_bkt_arr_handle_increment(&arr, h1), h2.b != 1 || h2.i != 2) exit(1);
+		h1.b = 1;
+		h1.i = 2;
+		if (h2 = pk_bkt_arr_handle_increment(&arr, h1), h2.b != 2 || h2.i != 0) exit(1);
+		h1.b = 2;
+		h1.i = 2;
+		if (h2 = pk_bkt_arr_handle_increment(&arr, h1), h2.b != 2 || h2.i != 2) exit(1);
+		h1.b = 0;
+		h1.i = 0;
+		if (h2 = pk_bkt_arr_handle_decrement(&arr, h1), h2.b != 0 || h2.i != 0) exit(1);
+		h1.b = 2;
+		h1.i = 2;
+		if (h2 = pk_bkt_arr_handle_decrement(&arr, h1), h2.b != 2 || h2.i != 1) exit(1);
+		h1.b = 2;
+		h1.i = 0;
+		if (h2 = pk_bkt_arr_handle_decrement(&arr, h1), h2.b != 1 || h2.i != 2) exit(1);
+	}
+
+	// test it works
+	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_free_handle(&arr, h);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 0) 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_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);
+	{
+		assert(bkt_buckets != nullptr);
+		assert(bkt_data != nullptr);
+		struct pk_bkt_arr arr = {0};
+		struct pk_bkt_arr_handle h1, h2, 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);
+
+		h1 = pk_bkt_arr_new_handle(&arr);
+		h2 = pk_bkt_arr_new_handle(&arr);
+		if (h1.b != 0) exit(1);
+		if (h1.i != 0) exit(1);
+		if (h2.b != 0) exit(1);
+		if (h2.i != 1) exit(1);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 2) exit(1);
+		if (arr.head_r.b != 0) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFFFC) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 1) exit(1);
+
+		pk_bkt_arr_free_handle(&arr, h1);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 0) exit(1);
+		if (arr.head_r.b != 0) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFFFD) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 1) exit(1);
+
+		h2 = pk_bkt_arr_new_handle(&arr);
+		if (h2.b != 0) exit(1);
+		if (h2.i != 0) exit(1);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 2) exit(1);
+		if (arr.head_r.b != 0) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFFFC) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 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 allocating 2nd bucket
+	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 h1, h2, limits;
+		limits.b = 8;
+		limits.i = 8;
+		struct pk_bkt_arr_handle handles[limits.b][limits.i];
+		pk_bkt_arr_init(&arr, sizeof(int), alignof(int), limits, bkt_buckets, bkt_data);
+
+		for (i = 0; i < limits.i; ++i) {
+			handles[0][i] = pk_bkt_arr_new_handle(&arr);
+			if (handles[0][i].b != 0) exit(1);
+			if (handles[0][i].i != i) exit(1);
+			if (i == limits.i - 1) {
+				if (arr.head_l.b != 1) exit(1);
+				if (arr.head_l.i != 0) exit(1);
+				if (arr.head_r.b != 1) exit(1);
+				if (arr.head_r.i != 0) exit(1);
+			} else {
+				if (arr.head_l.b != 0) exit(1);
+				if (arr.head_l.i != i + 1) exit(1);
+				if (arr.head_r.b != 0) exit(1);
+				if (arr.head_r.i != i + 1) exit(1);
+			}
+			if (arr.reserved_buckets != 1) exit(1);
+			if (bkt_buckets->allocs != 2) exit(1);
+			if (bkt_data->allocs != 1) exit(1);
+		}
+
+		h1 = pk_bkt_arr_new_handle(&arr);
+		if (h1.b != 1) exit(1);
+		if (h1.i != 0) exit(1);
+		if (arr.head_l.b != 1) exit(1);
+		if (arr.head_l.i != 1) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 1) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFF00) exit(1);
+		if (arr.idx_unused[1] != 0xFFFFFFFFFFFFFFFE) exit(1);
+		if (arr.reserved_buckets != 2) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) exit(1);
+
+		h1 = pk_bkt_arr_new_handle(&arr);
+		if (h1.b != 1) exit(1);
+		if (h1.i != 1) exit(1);
+		if (arr.head_l.b != 1) exit(1);
+		if (arr.head_l.i != 2) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFF00) exit(1);
+		if (arr.idx_unused[1] != 0xFFFFFFFFFFFFFFFC) exit(1);
+		if (arr.reserved_buckets != 2) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) exit(1);
+
+		h1.b = 0;
+		h1.i = 3;
+		pk_bkt_arr_free_handle(&arr, h1);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 3) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFF08) exit(1);
+		if (arr.idx_unused[1] != 0xFFFFFFFFFFFFFFFC) exit(1);
+		if (arr.reserved_buckets != 2) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) exit(1);
+
+		h2 = pk_bkt_arr_new_handle(&arr);
+		if (h2.b != 0) exit(1);
+		if (h2.i != 3) exit(1);
+		if (arr.head_l.b != 1) exit(1);
+		if (arr.head_l.i != 2) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFF00) exit(1);
+		if (arr.idx_unused[1] != 0xFFFFFFFFFFFFFFFC) exit(1);
+		if (arr.reserved_buckets != 2) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) exit(1);
+
+		h1.b = 1;
+		h1.i = 0;
+		h2.b = 1;
+		h2.i = 1;
+		pk_bkt_arr_free_handle(&arr, h1);
+		pk_bkt_arr_free_handle(&arr, h2);
+		if (arr.head_l.b != 1) exit(1);
+		if (arr.head_l.i != 0) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFF00) exit(1);
+		if (arr.idx_unused[1] != 0xFFFFFFFFFFFFFFFF) exit(1);
+		if (arr.reserved_buckets != 2) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) exit(1);
+
+		h2 = pk_bkt_arr_new_handle(&arr);
+		if (h2.b != 1) exit(1);
+		if (h2.i != 0) exit(1);
+		if (arr.head_l.b != 1) exit(1);
+		if (arr.head_l.i != 1) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 2) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFF00) exit(1);
+		if (arr.idx_unused[1] != 0xFFFFFFFFFFFFFFFE) exit(1);
+		if (arr.reserved_buckets != 2) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) 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 limits
+	test_spinup(&bkt_buckets, &bkt_data);
+	do
+	{
+		assert(bkt_buckets != nullptr);
+		assert(bkt_data != nullptr);
+		int b, i, r;
+		struct pk_bkt_arr arr = {0};
+		struct pk_bkt_arr_handle limits;
+		limits.b = 2;
+		limits.i = 8;
+		struct pk_bkt_arr_handle handles[limits.b][limits.i];
+
+		expected_exit = false;
+		caught = false;
+		r = setjmp(jmp_env);
+		if (r == 1) {
+			if (expected_exit == true && caught == true) {
+				expected_exit = false;
+				caught = false;
+				PK_LOGV_INF("%s: successfully caught err.\n", __FILE__);
+				fflush(stdout);
+				fflush(stderr);
+				break;
+			} else {
+				goto uncaught_err;
+			}
+		}
+
+		pk_bkt_arr_init(&arr, sizeof(int), alignof(int), limits, bkt_buckets, bkt_data);
+
+		for (b = 0; b < limits.b; ++b) {
+			for (i = 0; i < limits.i; ++i) {
+				handles[b][i] = pk_bkt_arr_new_handle(&arr);
+			}
+		}
+		if (arr.head_l.b != 1) exit(1);
+		if (arr.head_l.i != 7) exit(1);
+		if (arr.head_r.b != 1) exit(1);
+		if (arr.head_r.i != 7) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 2) exit(1);
+
+		expected_exit = true;
+		caught = false;
+		struct pk_bkt_arr_handle h = pk_bkt_arr_new_handle(&arr);
+		(void)h;
+		exit(1);
+
+		/*
+		pk_bkt_arr_free_handle(&arr, h);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 0) 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_teardown(&arr);
+		if (bkt_buckets->allocs != 0) exit(1);
+		if (bkt_data->allocs != 0) exit(1);
+		*/
+	}
+	while (false);
+	test_teardown(&bkt_buckets, &bkt_data);
+
+	return 0;
+uncaught_err:
+	PK_LOGV_ERR("%s: failed to catch err.\n", __FILE__);
+	fflush(stdout);
+	fflush(stderr);
+	return -1;
+}
diff --git a/test/pkbktarr.cpp b/test/pkbktarr.cpp
new file mode 100644
index 0000000..e7fb5ee
--- /dev/null
+++ b/test/pkbktarr.cpp
@@ -0,0 +1,63 @@
+
+#include "../pkbktarr.h"
+
+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);
+}
+
+void test_teardown(struct pk_membucket **bkt_buckets, struct pk_membucket **bkt_data)
+{
+	pk_bucket_destroy(*bkt_buckets);
+	pk_bucket_destroy(*bkt_data);
+	*bkt_buckets = nullptr;
+	*bkt_data = nullptr;
+}
+
+int main(int argc, char *argv[])
+{
+	(void)argc;
+	(void)argv;
+
+	struct pk_membucket *bkt_buckets = nullptr;
+	struct pk_membucket *bkt_data = nullptr;
+
+	// test it works
+	test_spinup(&bkt_buckets, &bkt_data);
+	{
+		assert(bkt_buckets != nullptr);
+		assert(bkt_data != nullptr);
+		struct pk_bkt_arr_handle limits;
+		limits.b = PK_BKT_ARR_HANDLE_B_MAX;
+		limits.i = PK_BKT_ARR_HANDLE_I_MAX;
+		struct pk_bkt_arr_t<int> arr(limits, bkt_buckets, bkt_data);
+
+		struct pk_bkt_arr_handle h = pk_bkt_arr_new_handle(&arr);
+		arr[h] = 128;
+		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 (arr.idx_unused[0] != 0xFFFFFFFFFFFFFFFE) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 1) exit(1);
+		if (arr[h] != 128) exit(1);
+
+		pk_bkt_arr_free_handle(&arr, h);
+		if (arr.head_l.b != 0) exit(1);
+		if (arr.head_l.i != 0) exit(1);
+		if (arr.head_r.b != 0) exit(1);
+		if (arr.head_r.i != 1) exit(1);
+		if (arr.idx_unused[0] != 0xFFFFFFFFFFFFFFFF) exit(1);
+		if (bkt_buckets->allocs != 2) exit(1);
+		if (bkt_data->allocs != 1) exit(1);
+
+		arr.~pk_bkt_arr_t<int>();
+		if (bkt_buckets->allocs != 0) exit(1);
+		if (bkt_data->allocs != 0) exit(1);
+	}
+	test_teardown(&bkt_buckets, &bkt_data);
+}