Move source files to src/

1 files changed, 112 insertions, 0 deletions

diff --git a/src/exec_stack.h b/src/exec_stack.h
new file mode 100644
index 00000000..57e13650
--- /dev/null
+++ b/src/exec_stack.h
@@ -0,0 +1,112 @@
+#ifndef EXEC_STACK_H
+#define EXEC_STACK_H
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include "jv_alloc.h"
+
+/*
+ * The stack is a directed forest of variably sized blocks. Each block has a
+ * "next" block which is at a higher memory address, or 0 if the block has no
+ * "next" block. More than one block may have no "next" block. A block may be
+ * the "next" block of more than one other block. Pushed blocks are added at
+ * the low-address end of the stack.
+ *
+ * Stack pointers are negative integers that are offsets relative to "mem_end",
+ * the end of the allocated region. The stack "bound" is the stack pointer of
+ * the last block that would be able to fit in the currently allocated region.
+ * The stack "limit" is the stack pointer of the last block currently in the
+ * stack. The stack pointer of the "next" block is stored directly below each
+ * block.
+ *
+ *                      <- mem_end = 0x100
+ * 0xF8  +------------+
+ * 0xF0  |            |
+ * 0xE8  +------------+ <- stack_ptr1 = -0x18
+ * 0xE0  next = 0
+ * 0xD8  +------------+
+ * 0xD0  |            |
+ * 0xC8  |            |
+ * 0xC0  +------------+ <- stack_ptr2 = limit = -0x40
+ * 0xB8  next = -0x18
+ * 0xB0
+ * 0xA8                 <- bound = -0x58
+ * 0xA0
+ */
+
+struct determine_alignment {
+  char x;
+  union { int i; double d; uint64_t u64; size_t sz; void* ptr; } u;
+};
+enum {ALIGNMENT = offsetof(struct determine_alignment, u)};
+
+static size_t align_round_up(size_t sz) {
+  return ((sz + (ALIGNMENT - 1)) / ALIGNMENT) * ALIGNMENT;
+}
+
+typedef int stack_ptr;
+
+struct stack {
+  char* mem_end; // one-past-the-end of allocated region
+  stack_ptr bound;
+  stack_ptr limit; // 0 - stack is empty
+};
+
+static void stack_init(struct stack* s) {
+  s->mem_end = 0;
+  s->bound = ALIGNMENT;
+  s->limit = 0;
+}
+
+static void stack_reset(struct stack* s) {
+  assert(s->limit == 0 && "stack freed while not empty");
+  char* mem_start = s->mem_end - ( -s->bound + ALIGNMENT);
+  free(mem_start);
+  stack_init(s);
+}
+
+static int stack_pop_will_free(struct stack* s, stack_ptr p) {
+  return p == s->limit;
+}
+
+static void* stack_block(struct stack* s, stack_ptr p) {
+  return (void*)(s->mem_end + p);
+}
+
+static stack_ptr* stack_block_next(struct stack* s, stack_ptr p) {
+  return &((stack_ptr*)stack_block(s, p))[-1];
+}
+
+static void stack_reallocate(struct stack* s, size_t sz) {
+  int old_mem_length = -(s->bound) + ALIGNMENT;
+  char* old_mem_start = s->mem_end - old_mem_length;
+
+  int new_mem_length = align_round_up((old_mem_length + sz + 256) * 2);
+  char* new_mem_start = jv_mem_realloc(old_mem_start, new_mem_length);
+  memmove(new_mem_start + (new_mem_length - old_mem_length),
+            new_mem_start, old_mem_length);
+  s->mem_end = new_mem_start + new_mem_length;
+  s->bound = -(new_mem_length - ALIGNMENT);
+}
+
+static stack_ptr stack_push_block(struct stack* s, stack_ptr p, size_t sz) {
+  int alloc_sz = align_round_up(sz) + ALIGNMENT;
+  stack_ptr r = s->limit - alloc_sz;
+  if (r < s->bound) {
+    stack_reallocate(s, alloc_sz);
+  }
+  s->limit = r;
+  *stack_block_next(s, r) = p;
+  return r;
+}
+
+static stack_ptr stack_pop_block(struct stack* s, stack_ptr p, size_t sz) {
+  stack_ptr r = *stack_block_next(s, p);
+  if (p == s->limit) {
+    int alloc_sz = align_round_up(sz) + ALIGNMENT;
+    s->limit += alloc_sz;
+  }
+  return r;
+}
+#endif