kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

arena.c (2650B)

      1 /* Bump-pointer arena. One linked list of fixed-size blocks; new blocks
      2  * are allocated when a request doesn't fit. arena_reset releases all
      3  * but the head block (so the freed-and-reallocated common case stays
      4  * O(1)). Oversize allocations get their own dedicated block. */
      5 
      6 #include "core/arena.h"
      7 
      8 #include <string.h>
      9 
     10 #include "core/util.h"
     11 
     12 struct ArenaBlock {
     13   ArenaBlock* next;
     14   size_t cap;
     15   u8 data[];
     16 };
     17 
     18 #define ARENA_DEFAULT_BLOCK 65536
     19 
     20 static ArenaBlock* block_new(Heap* h, size_t cap) {
     21   ArenaBlock* b =
     22       (ArenaBlock*)h->alloc(h, sizeof(ArenaBlock) + cap, _Alignof(ArenaBlock));
     23   if (!b) return NULL;
     24   b->next = NULL;
     25   b->cap = cap;
     26   return b;
     27 }
     28 
     29 void arena_init(Arena* a, Heap* h, size_t block_size) {
     30   a->heap = h;
     31   a->head = NULL;
     32   a->cur = NULL;
     33   a->end = NULL;
     34   a->block_size = block_size ? block_size : ARENA_DEFAULT_BLOCK;
     35 }
     36 
     37 void arena_fini(Arena* a) {
     38   ArenaBlock* b = a->head;
     39   while (b) {
     40     ArenaBlock* next = b->next;
     41     a->heap->free(a->heap, b, sizeof(ArenaBlock) + b->cap);
     42     b = next;
     43   }
     44   a->head = NULL;
     45   a->cur = NULL;
     46   a->end = NULL;
     47 }
     48 
     49 void arena_reset(Arena* a) {
     50   /* Free every block past the head; reuse head if present. */
     51   if (a->head) {
     52     ArenaBlock* b = a->head->next;
     53     while (b) {
     54       ArenaBlock* next = b->next;
     55       a->heap->free(a->heap, b, sizeof(ArenaBlock) + b->cap);
     56       b = next;
     57     }
     58     a->head->next = NULL;
     59     a->cur = a->head->data;
     60     a->end = a->head->data + a->head->cap;
     61   } else {
     62     a->cur = a->end = NULL;
     63   }
     64 }
     65 
     66 void* arena_zalloc(Arena* a, size_t size, size_t align) {
     67   void* p = arena_alloc(a, size, align);
     68   if (p) memset(p, 0, size);
     69   return p;
     70 }
     71 
     72 void* arena_alloc(Arena* a, size_t size, size_t align) {
     73   uintptr_t p, aligned;
     74   size_t need;
     75 
     76   if (align == 0) align = 1;
     77   if (a->cur) {
     78     p = (uintptr_t)a->cur;
     79     aligned = (p + (uintptr_t)(align - 1)) & ~(uintptr_t)(align - 1);
     80     if (aligned + size <= (uintptr_t)a->end) {
     81       a->cur = (u8*)(aligned + size);
     82       return (void*)aligned;
     83     }
     84   }
     85   /* New block. */
     86   need = ALIGN_UP(size, align);
     87   if (need < a->block_size) need = a->block_size;
     88   {
     89     ArenaBlock* b = block_new(a->heap, need);
     90     if (!b) return NULL;
     91     b->next = a->head;
     92     a->head = b;
     93     a->cur = b->data;
     94     a->end = b->data + b->cap;
     95     p = (uintptr_t)a->cur;
     96     aligned = (p + (uintptr_t)(align - 1)) & ~(uintptr_t)(align - 1);
     97     a->cur = (u8*)(aligned + size);
     98     return (void*)aligned;
     99   }
    100 }
    101 
    102 char* arena_strdup(Arena* a, const char* s, size_t len) {
    103   char* p = (char*)arena_alloc(a, len + 1, 1);
    104   if (!p) return NULL;
    105   if (len) memcpy(p, s, len);
    106   p[len] = 0;
    107   return p;
    108 }