rename fns again, add ta_calloc() & memset

1 files changed, 249 insertions, 0 deletions

diff --git a/tinyalloc.c b/tinyalloc.c
new file mode 100644
index 0000000..b48f85c
--- /dev/null
+++ b/tinyalloc.c
@@ -0,0 +1,249 @@
+#include "tinyalloc.h"
+
+#ifdef NDEBUG
+#define print_s(X)
+#define print_i(X)
+#else
+extern void print_s(char *);
+extern void print_i(size_t);
+#endif
+
+typedef struct Block Block;
+
+struct Block {
+    void *addr;
+    Block *next;
+    size_t size;
+};
+
+typedef struct {
+    Block *free;   // first free block
+    Block *used;   // first used block
+    Block *avail;  // first available blank block
+    size_t top;    // top free addr
+    Block blocks[TA_HEAP_BLOCKS];
+} Heap;
+
+static Heap *heap = (Heap *)TA_BASE;
+
+/**
+ * Insert block into free list, sorted by addr.
+ */
+static void insert_block(Block *block) {
+    Block *ptr  = heap->free;
+    Block *prev = NULL;
+    while (ptr != NULL) {
+        if ((size_t)block->addr <= (size_t)ptr->addr) {
+            print_s("insert");
+            print_i((size_t)ptr);
+            break;
+        }
+        prev = ptr;
+        ptr  = ptr->next;
+    }
+    if (prev != NULL) {
+        if (ptr == NULL) {
+            print_s("new tail");
+        }
+        prev->next = block;
+    } else {
+        print_s("new head");
+        heap->free = block;
+    }
+    block->next = ptr;
+}
+
+static void release_blocks(Block *scan, Block *to) {
+    Block *scan_next;
+    while (scan != to) {
+        print_s("release");
+        print_i((size_t)scan);
+        scan_next   = scan->next;
+        scan->next  = heap->avail;
+        scan->addr  = 0;
+        scan->size  = 0;
+        heap->avail = scan;
+        scan        = scan_next;
+    }
+}
+
+static void compact() {
+    Block *ptr  = heap->free;
+    Block *prev = NULL;
+    Block *scan;
+    while (ptr != NULL) {
+        prev        = ptr;
+        scan        = ptr->next;
+        size_t base = (size_t)ptr->addr;
+        while (scan != NULL &&
+               (size_t)prev->addr + prev->size == (size_t)scan->addr) {
+            print_s("merge");
+            print_i((size_t)scan);
+            prev = scan;
+            scan = scan->next;
+        }
+        if (prev != ptr) {
+            size_t new_size = prev->addr + prev->size - ptr->addr;
+            print_s("new size");
+            print_i(new_size);
+            ptr->size   = new_size;
+            Block *next = prev->next;
+            // make merged blocks available
+            release_blocks(ptr->next, prev->next);
+            // relink
+            ptr->next = next;
+            ptr       = next;
+        } else {
+            ptr = ptr->next;
+        }
+    }
+}
+
+bool ta_init() {
+    heap->free   = NULL;
+    heap->used   = NULL;
+    heap->avail  = heap->blocks;
+    heap->top    = TA_HEAP_START;
+    Block *block = heap->blocks;
+    size_t i = TA_HEAP_BLOCKS - 1;
+    while(i--) {
+        block->next = block + 1;
+        block++;
+    }
+    return true;
+}
+
+bool ta_free(void *free) {
+    Block *block = heap->used;
+    Block *prev  = NULL;
+    while (block != NULL) {
+        if (free == block->addr) {
+            if (prev) {
+                prev->next = block->next;
+            } else {
+                heap->used = block->next;
+            }
+            insert_block(block);
+            compact();
+            return true;
+        }
+        prev  = block;
+        block = block->next;
+    }
+    return false;
+}
+
+static Block *alloc_block(size_t num) {
+    Block *ptr  = heap->free;
+    Block *prev = NULL;
+    size_t top  = heap->top;
+    num         = (num + TA_ALIGN - 1) & -TA_ALIGN;
+    while (ptr != NULL) {
+        const int is_top = (size_t)ptr->addr + ptr->size >= top;
+        if (is_top || ptr->size >= num) {
+            if (prev != NULL) {
+                prev->next = ptr->next;
+            } else {
+                heap->free = ptr->next;
+            }
+            ptr->next  = heap->used;
+            heap->used = ptr;
+            if (is_top) {
+                print_s("resize top block");
+                ptr->size = num;
+                heap->top = (size_t)ptr->addr + num;
+            } else if (heap->avail != NULL) {
+                size_t excess = ptr->size - num;
+                if (excess >= TA_SIZE_THRESHOLD) {
+                    ptr->size    = num;
+                    Block *split = heap->avail;
+                    heap->avail  = split->next;
+                    split->addr  = ptr->addr + num;
+                    print_s("split");
+                    print_i((size_t)split->addr);
+                    split->size = excess;
+                    insert_block(split);
+                    compact();
+                }
+            }
+            return ptr;
+        }
+        prev = ptr;
+        ptr  = ptr->next;
+    }
+    // no matching free blocks
+    // see if any other blocks available
+    size_t new_top = top + num;
+    if (heap->avail != NULL && new_top <= TA_HEAP_LIMIT) {
+        ptr         = heap->avail;
+        heap->avail = ptr->next;
+        ptr->addr   = (void *)top;
+        ptr->next   = heap->used;
+        ptr->size   = num;
+        heap->used  = ptr;
+        heap->top   = new_top;
+        return ptr;
+    }
+    return NULL;
+}
+
+void *ta_alloc(size_t num) {
+    Block *block = alloc_block(num);
+    if (block != NULL) {
+        return block->addr;
+    }
+    return NULL;
+}
+
+static void memset(void *ptr, uint8_t c, size_t num) {
+    size_t *ptrw = (size_t *)ptr;
+    size_t numw  = (num & -sizeof(size_t)) / sizeof(size_t);
+    size_t cw    = c;
+    cw           = (cw << 24) | (cw << 16) | (cw << 8) | cw;
+    #ifdef __LP64__
+    cw |= (cw << 32);
+    #endif
+    while (numw--) {
+        *ptrw++ = cw;
+    }
+    num &= (sizeof(size_t) - 1);
+    uint8_t *ptrb = (uint8_t *)ptrw;
+    while (num--) {
+        *ptrb++ = c;
+    }
+}
+
+void *ta_calloc(size_t num, size_t size) {
+    num *= size;
+    Block *block = alloc_block(num);
+    if (block != NULL) {
+        memset(block->addr, 0, num);
+        return block->addr;
+    }
+    return NULL;
+}
+
+static size_t count_blocks(Block *ptr) {
+    size_t num = 0;
+    while (ptr != NULL) {
+        num++;
+        ptr = ptr->next;
+    }
+    return num;
+}
+
+size_t ta_num_free() {
+    return count_blocks(heap->free);
+}
+
+size_t ta_num_used() {
+    return count_blocks(heap->used);
+}
+
+size_t ta_num_avail() {
+    return count_blocks(heap->avail);
+}
+
+bool ta_check() {
+    return TA_HEAP_BLOCKS == ta_num_free() + ta_num_used() + ta_num_avail();
+}