path: root/pkarr.h

#ifndef PK_PKARR_H
#define PK_PKARR_H

#include <stdint.h>
#include "pkmem.h" /* deleteme */
#include "pkiter.h" /*deleteme*/

struct pk_arr {
	uint32_t next;
	uint32_t reserved;
	uint32_t stride;
	uint32_t alignment;
	struct pk_membucket *bkt;
	void *data;
};

typedef bool(pk_arr_item_compare)(void *user_data, void *item);

void pk_arr_clear(struct pk_arr *arr);
void pk_arr_reset(struct pk_arr *arr);
void pk_arr_reserve(struct pk_arr *arr, uint32_t count);
void pk_arr_resize(struct pk_arr *arr, uint32_t count);
void pk_arr_move_to_back(struct pk_arr *arr, uint32_t index);
void pk_arr_append(struct pk_arr *arr, void *data);
void pk_arr_remove_at(struct pk_arr *arr, uint32_t index);
void pk_arr_clone(struct pk_arr *lhs, struct pk_arr *rhs);
void pk_arr_swap(struct pk_arr *lhs, struct pk_arr *rhs);
uint32_t pk_arr_find_first_index(struct pk_arr *arr, void *user_data, pk_arr_item_compare *fn);
bool pk_arr_iter_begin(struct pk_arr *arr, struct pk_iter *it);
bool pk_arr_iter_end(struct pk_arr *arr, struct pk_iter *it);
bool pk_arr_iter_increment(struct pk_arr *arr, struct pk_iter *it);
bool pk_arr_iter_decrement(struct pk_arr *arr, struct pk_iter *it);

#if defined(__cplusplus)
template<typename T>
struct pk_arr_t : public pk_arr {
	pk_arr_t();
	pk_arr_t(struct pk_membucket *bkt);
	pk_arr_t(const pk_arr_t<T> &other);
	pk_arr_t(pk_arr_t<T> &&other);
	pk_arr_t &operator=(const pk_arr_t<T> &other);
	pk_arr_t &operator=(pk_arr_t<T> &&other);
	T &operator[](size_t index);
};
template<typename T>
pk_arr_t<T>::pk_arr_t() {
	this->next = 0;
	this->reserved = 0;
	this->stride = sizeof(T);
	this->alignment = alignof(T);
	this->bkt = NULL;
	this->data = NULL;
}
template<typename T>
pk_arr_t<T>::pk_arr_t(struct pk_membucket *bkt) : pk_arr_t<T>() {
	this->bkt = bkt;
}
template<typename T>
pk_arr_t<T>::pk_arr_t(const pk_arr_t<T> &other) {
	// copy ctor
	pk_arr_clone(static_cast<struct pk_arr_t *>(&const_cast<pk_arr_t<T>&>(other)), this);
}
template<typename T>
pk_arr_t<T>::pk_arr_t(pk_arr_t<T> &&other) {
	// move ctor
	pk_arr_swap(this, &other);
	other.data = NULL;
}
template<typename T>
pk_arr_t<T> &
pk_arr_t<T>::operator=(const pk_arr_t<T> &other) {
	// copy assignment
	if (this->data != NULL) {
		pk_arr_reset(this);
	}
	pk_arr_clone(static_cast<struct pk_arr_t *>(&const_cast<pk_arr_t<T>&>(other)), this);
	return *this;
}
template<typename T>
pk_arr_t<T> &
pk_arr_t<T>::operator=(pk_arr_t<T> &&other) {
	// move assignment
	if (this->data != NULL) {
		pk_arr_reset(this);
	}
	pk_arr_swap(this, &other);
	other.data = NULL;
	return *this;
}
template<typename T>
T &pk_arr_t<T>::operator[](size_t index) {
	if(index >= this->next) throw "pk_arr_t<T>::operator[] out of range";
	return reinterpret_cast<T*>(this->data)[index];
}
template<typename T>
void pk_arr_append_t(pk_arr_t<T> *arr, const T &item) {
	pk_arr_append(arr, &const_cast<T&>(item));
}
#endif

#endif /* PK_PKARR_H */
#ifdef PK_IMPL_ARR

#include "./pkmacros.h" /* deleteme */

#include <string.h>

#ifndef PK_ARR_GROW_RATIO
#define PK_ARR_GROW_RATIO 1.5
#endif
#ifndef PK_ARR_INITIAL_COUNT
#define PK_ARR_INITIAL_COUNT 16
#endif

void
pk_arr_clear(struct pk_arr *arr)
{
	arr->next = 0;
}

void
pk_arr_reset(struct pk_arr *arr)
{
	if (arr->data != NULL) pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt);
	arr->data = NULL;
	arr->next = 0;
	arr->reserved = 0;
}

void
pk_arr_reserve(struct pk_arr *arr, uint32_t count)
{
	if (arr->reserved >= count) return;
	void *new_data = pk_new(arr->stride * count, arr->alignment, arr->bkt);
	if (arr->data != NULL) {
		if (arr->next != 0) {
			memcpy(new_data, arr->data, arr->stride * arr->reserved);
		}
		pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt);
	}
	arr->reserved = count;
	arr->data = new_data;
}

void
pk_arr_resize(struct pk_arr *arr, uint32_t count)
{
	pk_arr_reserve(arr, count);
	arr->next = count;
}

void
pk_arr_move_to_back(struct pk_arr *arr, uint32_t index)
{
	if (arr->reserved == 0) return;
	if (arr->next <= 1) return;
#ifdef PK_ARR_MOVE_IN_PLACE
	uint32_t i, ii;
	char *target = (char *)pk_new(arr->stride, arr->alignment, arr->bkt);
	char *buffer = (char *)arr->data;
	// copy bytes to temp buffer
	for (ii = 0, i = arr->stride * index; ii < arr->stride; ++ii, ++i) {
		target[ii] = buffer[i];
	}
	// shift everything forward
	// arr->stride = 8
	// arr->next = 2
	// index = 0
	//
	// for (i = 0; i < 8; ++i) {
	//   b[i] = b[i + 8]
	// }
	// b[00] = b[08]
	// b[01] = b[09]
	// ...
	// b[07] = b[15]
	for (i = arr->stride * index; i < (arr->stride * (arr->next - 1)); ++i) {
		buffer[i] = buffer[i + arr->stride];
	}
	// copy temp buffer back into arr
	// arr->stride = 8
	// arr->next = 2
	// index = 0
	//
	// for (ii = 0, i = 8; ii < 8; ++ii, ++i) {
	//   b[i] = t[ii]
	// }
	// b[08] = t[00]
	// b[09] = t[01]
	// ...
	// b[15] = t[07]
	for (ii = 0, i = arr->stride * (arr->next - 1); ii < arr->stride; ++ii, ++i) {
		buffer[i] = target[ii];
	}
	pk_delete(target, arr->stride, arr->bkt);
#else
	char *new_data = (char *)pk_new(arr->stride * arr->reserved, arr->alignment, arr->bkt);
	if (index > 0) {
		memcpy(new_data, arr->data, arr->stride * index);
	}
	memcpy(
		new_data + (arr->stride * (arr->next - 1)),
		((char *)arr->data) + (arr->stride * index),
		arr->stride);
	memcpy(
		new_data + (arr->stride * index),
		((char *)arr->data) + (arr->stride * (index + 1)),
		arr->stride * (arr->next - index - 1));
	pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt);
	arr->data = (void *)new_data;
#endif
}

void
pk_arr_append(struct pk_arr *arr, void *data)
{
	if (arr->reserved == arr->next) {
		uint32_t new_count = PK_MAX(arr->reserved == 0 ? PK_ARR_INITIAL_COUNT : arr->reserved * PK_ARR_GROW_RATIO, arr->reserved + 1);
		void *new_data = pk_new(arr->stride * new_count, arr->alignment, arr->bkt);
		if (arr->data != NULL) {
			memcpy(new_data, arr->data, arr->stride * arr->reserved);
			pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt);
		}
		arr->data = new_data;
		arr->reserved = new_count;
	}
	memcpy(((char *)arr->data) + (arr->stride * arr->next), data, arr->stride);
	arr->next += 1;
	return;
}

void
pk_arr_remove_at(struct pk_arr *arr, uint32_t index)
{
	if (arr->reserved == 0) return;
	if (index == arr->next - 1) {
		arr->next -=1;
		return;
	}
#ifdef PK_ARR_MOVE_IN_PLACE
	uint32_t i;
	char *buffer = (char *)arr->data;
	// shift everything forward
	// arr->stride = 8
	// arr->next = 3
	// index = 0
	//
	// for (i = 0; i < 16; ++i) {
	//   b[i] = b[i + 8]
	// }
	// b[00] = b[08]
	// b[01] = b[09]
	// ...
	// b[15] = b[23]
	for (i = arr->stride * index; i < arr->stride * arr->next; ++i) {
		buffer[i] = buffer[i + arr->stride];
	}
#else
	char *new_data = (char *)pk_new(arr->stride * arr->reserved, arr->alignment, arr->bkt);
	if (index > 0) {
		memcpy(new_data, arr->data, arr->stride * index);
	}
	memcpy(
		new_data + (arr->stride * index),
		((char *)arr->data) + (arr->stride * (index + 1)),
		arr->stride * (arr->next - index - 1));
	pk_delete(arr->data, arr->stride * arr->reserved, arr->bkt);
	arr->data = (void *)new_data;
#endif
	arr->next -= 1;
}

void
pk_arr_clone(struct pk_arr *lhs, struct pk_arr *rhs) {
	size_t sz;
	*rhs = *lhs;
	if (lhs->data == NULL) return;
	sz = lhs->stride * lhs->reserved;
	rhs->data = pk_new(sz, lhs->alignment, lhs->bkt);
	memcpy(rhs->data, lhs->data, sz);
}

void
pk_arr_swap(struct pk_arr *lhs, struct pk_arr *rhs)
{
	struct pk_arr tmp = *lhs;
	*lhs = *rhs;
	*rhs = tmp;
}

uint32_t
pk_arr_find_first_index(struct pk_arr *arr, void *user_data, pk_arr_item_compare *fn)
{
	uint32_t i;
	char *char_data = (char *)arr->data;
	for (i = 0; i < arr->next; ++i) {
		if (fn(user_data, char_data + (arr->stride * i))) return i;
	}
	return -1;
}

bool
pk_arr_iter_begin(struct pk_arr *arr, struct pk_iter *it) {
	it->data = nullptr;
	it->id.arr.i = 0;
	if (arr->next > 0 && arr->data != nullptr && arr->data != CAFE_BABE(void)) {
		it->data = arr->data;
		return true;
	}
	return false;
}

bool pk_arr_iter_end(struct pk_arr *arr, struct pk_iter *it) {
	it->data = nullptr;
	it->id.arr.i = 0;
	if (arr->next > 0 && arr->data != nullptr && arr->data != CAFE_BABE(void)) {
		it->id.arr.i = arr->next - 1;
		it->data = (void *)((char*)arr->data + (arr->stride * it->id.arr.i));
		return true;
	}
	return false;
}

bool
pk_arr_iter_increment(struct pk_arr *arr, struct pk_iter *it) {
	if (it->id.arr.i + 1 >= arr->next) {
		return false;
	}
	it->id.arr.i += 1;
	it->data = (void *)((char*)arr->data + (arr->stride * it->id.arr.i));
	return true;
}

bool
pk_arr_iter_decrement(struct pk_arr *arr, struct pk_iter *it) {
	if (it->id.arr.i == 0) {
		return false;
	}
	it->id.arr.i -= 1;
	it->data = (void *)((char*)arr->data + (arr->stride * it->id.arr.i));
	return true;
}

#endif /* PK_IMPL_ARR */