You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
321 lines
9.5 KiB
321 lines
9.5 KiB
|
|
#pragma once
|
|
#ifndef ULE_ARRAY_H
|
|
#define ULE_ARRAY_H
|
|
|
|
#include <new> // operator new, operator delete
|
|
|
|
#include "config.h"
|
|
#include "alloc.h" // allocators...
|
|
#include "serialize.h" // serialization
|
|
#include "string.h" // String::memcpy, String::memset
|
|
#include "types.h" // type definitions
|
|
|
|
|
|
// this is a dynamic array (grows as needed)
|
|
// should work with any data type for T including primitive types
|
|
// some initial |capacity| is heap-allocated and a pointer is stored to it as |data|
|
|
// the |length| of the array, or number of filled slots is also tracked.
|
|
template <typename T>
|
|
struct Array {
|
|
T* data;
|
|
u32 length;
|
|
u32 capacity;
|
|
Allocator* allocator;
|
|
|
|
Array<T>(u32 _capacity = 8, Allocator* allocator = &Allocator::GetDefault()) {
|
|
ULE_TYPES_H_FTAG;
|
|
this->data = (T*) allocator->mallocate(sizeof(T) * _capacity, allocator->state);
|
|
String::memset(this->data, '\0', sizeof(T) * _capacity);
|
|
this->length = 0;
|
|
this->capacity = _capacity;
|
|
this->allocator = allocator;
|
|
}
|
|
static Array<T>* Init(u32 _capacity = 8, Allocator* allocator = &Allocator::GetDefault()) {
|
|
Array<T>* array = allocator->mallocate(sizeof(Array<T>), allocator->state);
|
|
array->allocator = allocator;
|
|
array->length = 0;
|
|
array->capacity = _capacity;
|
|
const size_t size = sizeof(T) * _capacity;
|
|
array->data = (T*) allocator->mallocate(size, array->allocator->state);
|
|
String::memset(array->data, '\0', size);
|
|
return array;
|
|
}
|
|
|
|
// function call overhead + dev 'massert' bounds-checking overhead.
|
|
// you can use "->data[i]" if you know you can't be out of bounds.
|
|
T& Array::operator[](u32 index) const {
|
|
ULE_TYPES_H_FTAG;
|
|
massert(index >= 0 && index < this->length, "array access out of bounds!");
|
|
return this->data[index];
|
|
}
|
|
|
|
void checkIfShouldGrow() {
|
|
ULE_TYPES_H_FTAG;
|
|
if (this->isFull()) {
|
|
// optimal number as you approach infinite elements approaches PHI, but 1.5 sometimes works better for finite sizes
|
|
//
|
|
// it seems, that a commonly chosen growth rate of '2' is perhaps the worst possible choice.
|
|
// if you grow at a rate of 2x, you end up (likely) never being able to re-use the freed 'hole' in the heap
|
|
// for a future allocation of the same kind.
|
|
// useful reading for those interested in their own dynamic array implementations:
|
|
// (facebook's vector impl, a strictly better std::vector)
|
|
// https://github.com/facebook/folly/blob/main/folly/docs/FBVector.md
|
|
//
|
|
this->capacity = (u32) (this->capacity * 1.5);
|
|
this->data = (T*) pRealloc(data, sizeof(T) * this->capacity);
|
|
}
|
|
}
|
|
|
|
// for when the order in the array doesn't matter, move the end of the array into the removed slot
|
|
void removeSwapWithEnd(u32 index) {
|
|
ULE_TYPES_H_FTAG;
|
|
if (this->isEmpty()) return; // overhead, maybe assert instead?
|
|
|
|
u32 end = this->length - 1;
|
|
if (index != end) {
|
|
this->data[index] = this->data[end];
|
|
}
|
|
this->pop();
|
|
}
|
|
|
|
void removeSwapWithEnd(T* addr) {
|
|
ULE_TYPES_H_FTAG;
|
|
for (u32 i = 0; i < this->length; i++) {
|
|
if ((this->data + i) == addr) {
|
|
removeSwapWithEnd(i);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
|
|
void removeAndShrink(u32 index) {
|
|
ULE_TYPES_H_FTAG;
|
|
for (u32 i = index + 1; i < this->length; i++) {
|
|
String::memcpy(&this->data[i - 1], &this->data[i], sizeof(T));
|
|
}
|
|
this->length--;
|
|
}
|
|
|
|
void removeAndShrink(T* elementAddr) {
|
|
ULE_TYPES_H_FTAG;
|
|
s32 index = -1;
|
|
for (u32 i = 0; i < this->length; i++) {
|
|
if ((this->data + i) == elementAddr) {
|
|
index = i;
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (index == -1) {
|
|
return;
|
|
}
|
|
|
|
for (u32 i = index + 1; i < this->length; i++) {
|
|
String::memcpy((void*)(this->data + i - 1), (void*)(this->data + i), sizeof(T));
|
|
}
|
|
this->length--;
|
|
}
|
|
|
|
T pop() {
|
|
ULE_TYPES_H_FTAG;
|
|
if (this->isEmpty()) {
|
|
die("empty");
|
|
}
|
|
|
|
return this->data[--this->length];
|
|
}
|
|
|
|
// sometimes, you want to copy some POD data on the stack to the next position in the internal array
|
|
// that's what this does
|
|
u32 pushCopy(T* e) {
|
|
ULE_TYPES_H_FTAG;
|
|
this->checkIfShouldGrow();
|
|
|
|
String::memcpy((void*) &this->data[this->length++], e, sizeof(T));
|
|
|
|
return this->length - 1;
|
|
}
|
|
|
|
// returns the next address into which you can store a T. makes sure there's enough room first.
|
|
// it is irresponsible to call this and then not store a T in that address. this increments length,
|
|
// reserving the next spot for you.
|
|
//
|
|
// C++ 'placement new' is the more safe/standard way to do this, but it requires your initialization
|
|
// logic is in a constructor somewhere, which isn't necessarily the case for you, and isn't for us.
|
|
//
|
|
T* pushNextAddrPromise() {
|
|
ULE_TYPES_H_FTAG;
|
|
this->checkIfShouldGrow();
|
|
|
|
return &this->data[this->length++];
|
|
}
|
|
|
|
u32 push(T e) {
|
|
ULE_TYPES_H_FTAG;
|
|
this->checkIfShouldGrow();
|
|
|
|
this->data[this->length++] = e;
|
|
|
|
return this->length - 1;
|
|
}
|
|
|
|
u32 pushMany(T* elements, u32 count) {
|
|
ULE_TYPES_H_FTAG;
|
|
// ensure we have capacity. if we have to realloc multiple times that can suck,
|
|
// but should be avoidable in practice by having an appropriately large initial capacity
|
|
while (this->capacity < (this->length + count)) {
|
|
this->capacity *= 1.5;
|
|
this->data = (T*) pRealloc(data, sizeof (T) * this->capacity);
|
|
}
|
|
|
|
u32 start = this->length;
|
|
for (u32 i1 = start, i2 = 0; i1 < count; i1++, i2++) {
|
|
this->data[this->length++] = elements[i2];
|
|
}
|
|
|
|
return start;
|
|
}
|
|
|
|
void reverse() {
|
|
ULE_TYPES_H_FTAG;
|
|
u32 count = this->length / 2;
|
|
|
|
for (u32 i = 0; i < count; i++) {
|
|
u32 offset = this->length - 1 - i;
|
|
|
|
T temp = this->data[i];
|
|
this->data[i] = this->data[offset];
|
|
this->data[offset] = temp;
|
|
}
|
|
}
|
|
|
|
T shift() {
|
|
ULE_TYPES_H_FTAG;
|
|
if (this->length == 0) {
|
|
return null;
|
|
}
|
|
|
|
T out = this->data[0];
|
|
this->length -= 1;
|
|
|
|
for (u32 i = 0; i < this->length; i++) {
|
|
*(this->data + i) = *(this->data + i + 1);
|
|
}
|
|
|
|
return out;
|
|
}
|
|
|
|
T unshift(T e) {
|
|
ULE_TYPES_H_FTAG;
|
|
this->checkIfShouldGrow();
|
|
|
|
for (u32 i = 0; i < this->length; i++) {
|
|
*(this->data + i + 1) = *(this->data + i);
|
|
}
|
|
|
|
this->data[0] = e;
|
|
this->length += 1;
|
|
|
|
return this->length;
|
|
}
|
|
|
|
T peek() const {
|
|
ULE_TYPES_H_FTAG;
|
|
if (this->isEmpty()) {
|
|
return null;
|
|
}
|
|
|
|
return this->data[this->length - 1];
|
|
}
|
|
|
|
bool isEmpty() const {
|
|
ULE_TYPES_H_FTAG;
|
|
return this->length == 0;
|
|
}
|
|
|
|
bool isFull() const {
|
|
ULE_TYPES_H_FTAG;
|
|
return this->length == this->capacity;
|
|
}
|
|
|
|
void sort(bool(*comparator)(T a, T b)) {
|
|
ULE_TYPES_H_FTAG;
|
|
massert(comparator != null, "can't call sort with a null comparator");
|
|
const auto length = this->length;
|
|
for (u32 i = 0; i < length; i++) {
|
|
for (u32 j = i + 1; j < length; j++) {
|
|
if (comparator(this->data[i], this->data[j])) {
|
|
auto temp = this->data[i];
|
|
this->data[i] = this->data[j];
|
|
this->data[j] = temp;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void clear() {
|
|
ULE_TYPES_H_FTAG;
|
|
this->length = 0;
|
|
}
|
|
};
|
|
|
|
#ifdef ULE_CONFIG_OPTION_SERIALIZATION
|
|
template <typename T>
|
|
static void serialize(String* str, Array<T> array) {
|
|
ULE_TYPES_H_FTAG;
|
|
serialize(str, array.length);
|
|
serialize(str, array.capacity);
|
|
for (u32 i = 0; i < array.length; i++) {
|
|
serialize(str, array.data[i]);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void serialize(String* str, Array<T>* array) {
|
|
ULE_TYPES_H_FTAG;
|
|
SERIALIZE_HANDLE_NULL(str, array);
|
|
serialize(str, array->length);
|
|
serialize(str, array->capacity);
|
|
for (u32 i = 0; i < array->length; i++) {
|
|
serialize(str, array->data[i]);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void deserialize(char** buffer, Array<T>* array) {
|
|
ULE_TYPES_H_FTAG;
|
|
deserialize(buffer, &array->length);
|
|
deserialize(buffer, &array->capacity);
|
|
|
|
// |array| should have already been allocated, including its |data| member,
|
|
// but this may not be sufficient to write in the data we now wish to.
|
|
// realloc to be sure.
|
|
array->data = (T*) pRealloc(array->data, sizeof(T) * array->capacity);
|
|
if (array->data == null) {
|
|
massert(false, "failed to realloc when deserializing an array.");
|
|
}
|
|
|
|
for (u32 i = 0; i < array->length; i++) {
|
|
deserialize(buffer, array->data + i);
|
|
}
|
|
}
|
|
|
|
template <typename T>
|
|
static void deserialize(char** buffer, Array<T>** array) {
|
|
ULE_TYPES_H_FTAG;
|
|
DESERIALIZE_HANDLE_NULL(buffer, array);
|
|
u32 length, capacity;
|
|
deserialize(buffer, &length);
|
|
deserialize(buffer, &capacity);
|
|
Array<T>* _array = new Array<T>(capacity);
|
|
_array->length = length;
|
|
for (u32 i = 0; i < _array->length; i++) {
|
|
deserialize(buffer, _array->data + i);
|
|
}
|
|
*array = _array;
|
|
}
|
|
#endif // ULE_CONFIG_OPTION_SERIALIZATION
|
|
|
|
#endif
|
|
|