stacktest.cpp

#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);
    
}