Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <iostream>
#include <type_traits>
// Big stack.
static size_t stackSize = 1024*1024*10;
static thread_local uint8_t* start = nullptr;
static thread_local uint8_t* stack = nullptr;
// An array with simple stack based allocation.
// Size is fixed on creation.
//
// I'm assuming this is difficult with std::vector
// and a custom allocator because it can grow.
//
// T must be trivial for now
template<class T>
class stack_array {
size_t _size;
T* ptr;
public:
stack_array(size_t size) : _size(size) {
static_assert(std::is_trivial<T>::value);
if(stack == nullptr) {
start = stack = (uint8_t*) malloc(stackSize);
}
ptr = (T*) stack;
stack += size*sizeof(T);
assert(stack < start + stackSize);
printf("ctor %p, stack %d\n", (void*) this, int(stack - start));
}
// I think the copy constructor violates our stack
// nesting property, since the lifetimes overlap.
stack_array(const stack_array&) = delete;
~stack_array() {
stack -= _size*sizeof(T);
printf("dtor %p, stack %d\n", (void*) this, int(stack - start));
}
stack_array& operator=(const stack_array& a) {
printf("assign\n");
assert(_size == a._size);
for(size_t i=0;i<_size;++i) {
ptr[i] = a.ptr[i];
}
return *this;
}
// Is this actually correct?
stack_array(stack_array&& other) {
printf("move\n");
ptr = other.ptr;
_size = other._size;
other._size = 0;
}
T& operator[](size_t i) { assert(i < _size); return ptr[i]; }
const T& operator[](size_t i) const { assert(i < _size); return ptr[i]; }
size_t size() const { return _size; }
};
// Fibonacci sequence
stack_array<int> fib(size_t n) {
stack_array<int> f(n);
f[0] = 0;
f[1] = 1;
for(size_t i=2;i<n;++i) {
f[i] = f[i-1] + f[i-2];
}
return f;
}
template<class T, class F>
void foreach(const stack_array<T> &a, F f) {
for(size_t i=0;i<a.size();++i) {
f(a[i]);
}
}
template<class T, class F>
auto map(const stack_array<T> &a, F f) {
stack_array< decltype(f(T())) > r(a.size());
for(size_t i=0;i<a.size();++i) {
r[i] = f(a[i]);
}
return r;
}
template<class T, class F>
auto filter(const stack_array<T> &a, F f) {
stack_array<int> b(a.size());
size_t n = 0;
for(size_t i=0;i<a.size();++i) {
if(f(a[i])) {
b[n++] = i;
}
}
stack_array<T> r(n);
for(size_t i=0;i<n;++i) {
r[i] = a[b[i]];
}
return r;
}
template<class T> void printArray(const stack_array<T> &a) {
foreach(a, [](T t){ std::cout << t << std::endl;});
}
int main(int argc, char* argv[]) {
{
stack_array<int> a = fib(20);
printArray(a);
printArray(map(a, [](int i) { return i+1; }));
printArray(filter(a, [](int i) { return i%2; }));
stack_array<int> b(a.size());
b = a;
}
assert(stack == start);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.