|
|
#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
|