pk.h: update to 0.4.4

1 files changed, 271 insertions, 2 deletions

diff --git a/src/pk.h b/src/pk.h
index 30051a1..c9e1d44 100644
--- a/src/pk.h
+++ b/src/pk.h
@@ -1,7 +1,7 @@
 #ifndef PK_SINGLE_HEADER_FILE_H
 #define PK_SINGLE_HEADER_FILE_H
 /*******************************************************************************
-* PK Single-Header-Library V0.4.2
+* PK Single-Header-Library V0.4.4
 *
 * Author:           Jonathan Bradley
 * Copyright:        © 2024-2025 Jonathan Bradley
@@ -214,9 +214,47 @@
 *  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 "0.4.2"
+#define PK_VERSION "0.4.4"
 
 #ifdef PK_IMPL_ALL
 # ifndef PK_IMPL_MEM_TYPES
@@ -240,6 +278,9 @@
 # ifndef PK_IMPL_UUID
 #  define PK_IMPL_UUID
 # endif
+# ifndef PK_IMPL_BKTARR
+#  define PK_IMPL_BKTARR
+# endif
 #endif
 #ifndef PK_MACROS_H
 #define PK_MACROS_H
@@ -2227,12 +2268,15 @@ void pk_uuid_init(time_t srand_seed);
 void pk_uuid_teardown();
 
 struct pk_uuid pk_uuid_new_v7();
+bool pk_uuid_equals(struct pk_uuid lhs, struct pk_uuid rhs);
 
 #if defined(__cplusplus)
 #include <ostream>
 #include <iomanip>
 std::ostream& operator<<(std::ostream &o, const struct pk_uuid& uuid);
 std::istream& operator>>(std::istream &i, struct pk_uuid& uuid);
+bool operator==(const pk_uuid &lhs, const pk_uuid &rhs);
+bool operator!=(const pk_uuid &lhs, const pk_uuid &rhs);
 #endif
 
 #endif /* PK_UUID_H */
@@ -2344,11 +2388,22 @@ pk_uuid_new_v7()
 	return ret;
 }
 
+bool pk_uuid_equals(struct pk_uuid lhs, struct pk_uuid rhs)
+{
+	int i;
+	for (i = 0; i < 16; ++i) {
+		if (lhs.uuid[i] != rhs.uuid[i]) return false;
+	}
+	return true;
+}
+
 #if defined(__cplusplus)
 std::ostream&
 operator<<(std::ostream &o, const struct pk_uuid& uuid)
 {
 	int i;
+	std::ios_base::fmtflags orig_flags = o.flags();
+	auto fill = o.fill();
 	o << std::hex;
 	for (i = 0; i < 4; ++i) {
 		o << std::setw(2) << std::setfill('0');
@@ -2374,6 +2429,8 @@ operator<<(std::ostream &o, const struct pk_uuid& uuid)
 		o << std::setw(2) << std::setfill('0');
 		o << (uint16_t)uuid.uuid[i];
 	}
+	o.fill(fill);
+	o.flags(orig_flags);
 	return o;
 }
 
@@ -2406,7 +2463,219 @@ err_out:
 	uuid = pk_uuid_zed;
 	return i;
 }
+
+bool operator==(const pk_uuid &lhs, const pk_uuid &rhs) { return pk_uuid_equals(lhs, rhs); }
+
+bool operator!=(const pk_uuid &lhs, const pk_uuid &rhs) { return !pk_uuid_equals(lhs, rhs); }
+
 #endif
 
 #endif
+#ifndef PK_PKBKTARR_H
+#define PK_PKBKTARR_H
+
+
+#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)
+#include <assert.h>
+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 */
 #endif /* PK_SINGLE_HEADER_FILE_H */