1 files changed, 119 insertions, 0 deletions
diff --git a/dynarray.h b/dynarray.h
new file mode 100755
index 0000000..7e75ac2
--- /dev/null
+++ b/dynarray.h
@@ -0,0 +1,119 @@
+#pragma once
+
+#include <cassert>
+#include <type_traits>
+
+#include "pal.h"
+
+static constexpr size_t kBytesPerCommit = pal::kPageSize;
+
+size_t GetCommittedBytes(size_t used_bytes) {
+    return ((used_bytes + kBytesPerCommit - 1) / kBytesPerCommit) * kBytesPerCommit;
+}
+
+struct Arena {
+    char* base = nullptr;
+    size_t cap = 0;
+    size_t len = 0;
+
+    Arena() = delete;
+    Arena(const Arena&) = delete;
+    Arena(Arena&& other) {
+        base = other.base;
+        cap = other.cap;
+        len = other.len;
+
+        other.base = nullptr;
+        other.cap = 0;
+        other.len = 0;
+    }
+
+    explicit Arena(size_t max_len) {
+        assert(max_len != 0);
+
+        cap = GetCommittedBytes(max_len);
+        len = 0;
+
+        void* buf = pal::MemReserve(cap);
+        if (buf == nullptr) {
+            throw std::bad_alloc();
+        }
+
+        base = static_cast<char*>(buf);
+    }
+
+    ~Arena() {
+        if (base != nullptr) {
+            pal::MemFree(base, cap);
+        }
+    }
+
+    bool Grow(size_t additional_len) {
+        assert(len+additional_len <= cap);
+        size_t old_committed = GetCommittedBytes(len);
+        size_t new_committed = GetCommittedBytes(len+additional_len);
+        size_t delta = new_committed - old_committed;
+        if (delta == 0) {
+            len += additional_len;
+            return true;
+        }
+
+        if (!pal::MemCommit(base + old_committed, delta)) {
+            return false;
+        }
+
+        len += additional_len;
+        return true;
+    }
+};
+
+template <typename T>
+class DynArray {
+    Arena arena;
+
+public:
+    // Redundant, but useful as documentation.
+    DynArray() = delete;
+    DynArray(const DynArray<T>& other) = delete;
+    DynArray(DynArray&& other) = default;
+
+    explicit DynArray(size_t max_len)
+    : arena(max_len * sizeof(T)) {}
+
+    // Support for range loops.
+    T* begin() {
+        return reinterpret_cast<T*>(arena.base);
+    }
+
+    T* end() {
+        return reinterpret_cast<T*>(arena.base + arena.len);
+    }
+
+    bool Append(T v) {
+        auto* dst = end();
+
+        if (!arena.Grow(sizeof(T))) {
+            return false;
+        }
+
+        new (dst) T(std::move(v));
+        return true;
+    }
+
+    size_t Len() const {
+        return arena.len / sizeof(T);
+    }
+
+    T& operator[](size_t i) {
+        assert(i < Len());
+        return begin()[i];
+    }
+
+    ~DynArray() {
+        if (!std::is_trivially_destructible_v<T>) {
+            for (auto* p = begin(); p != end(); p++) {
+                p->~T();
+            }
+        }
+    }
+};