1 files changed, 66 insertions, 0 deletions
diff --git a/magic_buddy.c b/magic_buddy.c
index a4874fe..4529e7d 100644
--- a/magic_buddy.c
+++ b/magic_buddy.c
@@ -122,3 +122,69 @@ void debug_buddy(void) {
         }
     }
 }
+
+///////// "advanced features"
+static struct free_list *rhs_child_of(struct free_list *block, size_t logsize) {
+    size_t virt_block = (size_t)block - (size_t)BASE;
+    size_t virt_child = virt_block | (1 << (logsize - 1));
+    return (void*)((uint8_t*)BASE + virt_buddy);
+}
+
+// NOTE: this method is perhaps more complicated than it needs to be because we
+// take great pains to avoid writing to the region that is being preallocated
+// (e.g., in case it is device MMIO).
+int preallocate(void *start, size_t size) {
+    assert(size);
+    void *end = (void*)((uint8_t*)start + size);
+
+    // (1) check if BASE itself is a free node
+    struct free_list *parent = (void*)BASE;
+    size_t parent_logsize = ROOT_LOGSIZE;
+    while (!isfree(parent)) {
+        // pick the proper child and recurse
+        struct free_list *rhs_child = rhs_child_of(parent, parent_logsize);
+        if (rhs_child <= start) parent = rhs_child;
+        if (!parent_logsize--) return 0;
+    }
+    // parent is free!
+    void *parent_end = (void*)((uint8_t*)parent + (1 << parent_logsize));
+    // if the size has no chance of fitting, return 0.
+    if (parent_end < end) return 0;
+    // otherwise, split this parent
+    pop(parent, parent_logsize);
+    while (1) {
+        // check whether the child could fit it.
+        struct free_list *rhs_child = rhs_child_of(parent, parent_logsize);
+        struct free_list *next_child = (rhs_child <= start) parent : rhs_child;
+        void *child_end = (void*)((uint8_t*)next_child + (1 << (parent_logsize - 1)));
+        if (child_end < end) {
+            // the child *cannot* fit it, so allocate this parent.
+            return 1;
+        } else {
+            // the child *can* fit it, so split this parent into two children.
+            struct free_list *lhs_child = parent;
+            if (rhs_child <= start) {
+                // the lhs child will be free
+                makefree(lhs_child);
+                push(lhs_child, parent_logsize - 1);
+                parent = rhs_child;
+            } else {
+                // the rhs child will be free
+                makefree(rhs_child);
+                push(rhs_child, parent_logsize - 1);
+                parent = lhs_child;
+            }
+        }
+        parent_logsize--;
+    }
+    return 0;
+}
+
+void *reallocate(void *old, size_t old_size, size_t new_size) {
+    // if new_size < old_size, repeatedly split ourself. TODO: does this mess
+    // with fragmentation?
+
+    // otherwise, basically identical to preallocate, except what we want to
+    // allocate is roughly @old + old_size (with proper rounding to
+    // boundaries).
+}