pkbktarr: created + bump pk.h version to 0.4.3

1 files changed, 208 insertions, 0 deletions

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 */