kit

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

arena.c (4504B)

      1 /* Bump-pointer arena. A singly-linked list of blocks held in allocation order.
      2  * Block sizes grow geometrically (block_size, doubling up to ARENA_MAX_BLOCK)
      3  * so a large arena needs O(log n) heap allocations instead of O(n) fixed-size
      4  * blocks. arena_reset RETAINS every block (the high-water capacity) and only
      5  * rewinds the bump cursor to the first block, so a reset/refill cycle reuses
      6  * its memory with zero heap traffic; only arena_fini returns blocks to the
      7  * heap. A request larger than the current geometric size gets its own
      8  * exactly-sized block. */
      9 
     10 #include "core/arena.h"
     11 
     12 #include <string.h>
     13 
     14 #include "core/util.h"
     15 
     16 struct ArenaBlock {
     17   ArenaBlock* next;
     18   size_t cap;
     19   u8 data[];
     20 };
     21 
     22 #define ARENA_DEFAULT_BLOCK 65536
     23 #define ARENA_MAX_BLOCK (1u << 20) /* geometric block-growth ceiling (1 MiB) \
     24                                     */
     25 
     26 static ArenaBlock* block_new(Heap* h, size_t cap) {
     27   ArenaBlock* b =
     28       (ArenaBlock*)h->alloc(h, sizeof(ArenaBlock) + cap, _Alignof(ArenaBlock));
     29   if (!b) return NULL;
     30   b->next = NULL;
     31   b->cap = cap;
     32   return b;
     33 }
     34 
     35 void arena_init(Arena* a, Heap* h, size_t block_size) {
     36   a->heap = h;
     37   a->head = NULL;
     38   a->cur_block = NULL;
     39   a->cur = NULL;
     40   a->end = NULL;
     41   a->block_size = block_size ? block_size : ARENA_DEFAULT_BLOCK;
     42   a->next_size = a->block_size;
     43 }
     44 
     45 void arena_fini(Arena* a) {
     46   ArenaBlock* b = a->head;
     47   while (b) {
     48     ArenaBlock* next = b->next;
     49     a->heap->free(a->heap, b, sizeof(ArenaBlock) + b->cap);
     50     b = next;
     51   }
     52   a->head = NULL;
     53   a->cur_block = NULL;
     54   a->cur = NULL;
     55   a->end = NULL;
     56   a->next_size = a->block_size;
     57 }
     58 
     59 int arena_is_empty(const Arena* a) {
     60   /* The pristine predicate: reset would be a no-op. Either nothing was ever
     61    * allocated (head==NULL), or the cursor is rewound to the first block's base
     62    * -- exactly the state arena_reset re-establishes (retained blocks past the
     63    * head are fine: reset keeps them either way). */
     64   if (!a->head) return 1;
     65   return a->cur_block == a->head && a->cur == a->head->data;
     66 }
     67 
     68 void arena_reset(Arena* a) {
     69   /* Retain the high-water capacity: rewind the cursor to the first block and
     70    * keep every block linked for reuse on refill. No heap traffic -- distinct
     71    * from arena_fini, which is the only path that returns blocks to the heap. */
     72   if (!a->head) return;
     73   a->cur_block = a->head;
     74   a->cur = a->head->data;
     75   a->end = a->head->data + a->head->cap;
     76 }
     77 
     78 void* arena_zalloc(Arena* a, size_t size, size_t align) {
     79   void* p = arena_alloc(a, size, align);
     80   if (p) memset(p, 0, size);
     81   return p;
     82 }
     83 
     84 void* arena_alloc(Arena* a, size_t size, size_t align) {
     85   uintptr_t aligned;
     86   size_t cap;
     87   ArenaBlock* b;
     88 
     89   if (align == 0) align = 1;
     90 
     91   /* Fast path: bump within the current block. */
     92   if (a->cur_block) {
     93     aligned = ((uintptr_t)a->cur + (align - 1)) & ~(uintptr_t)(align - 1);
     94     if (aligned + size <= (uintptr_t)a->end) {
     95       a->cur = (u8*)(aligned + size);
     96       return (void*)aligned;
     97     }
     98   }
     99 
    100   /* Current block is full -- advance through the retained blocks (the
    101    * high-water capacity preserved by arena_reset) before touching the heap. */
    102   while (a->cur_block && a->cur_block->next) {
    103     a->cur_block = a->cur_block->next;
    104     a->cur = a->cur_block->data;
    105     a->end = a->cur_block->data + a->cur_block->cap;
    106     aligned = ((uintptr_t)a->cur + (align - 1)) & ~(uintptr_t)(align - 1);
    107     if (aligned + size <= (uintptr_t)a->end) {
    108       a->cur = (u8*)(aligned + size);
    109       return (void*)aligned;
    110     }
    111   }
    112 
    113   /* No retained block fits: append a fresh one. Use the geometric size when the
    114    * request fits it (and grow the next size), else size the block exactly to an
    115    * oversize request. cap >= size + align always leaves room for alignment, as
    116    * the heap returns max_align_t-aligned storage. */
    117   cap = size + align;
    118   if (cap <= a->next_size) {
    119     cap = a->next_size;
    120     a->next_size *= 2;
    121     if (a->next_size > ARENA_MAX_BLOCK) a->next_size = ARENA_MAX_BLOCK;
    122   }
    123   b = block_new(a->heap, cap);
    124   if (!b) return NULL;
    125   b->next = NULL;
    126   if (a->cur_block)
    127     a->cur_block->next = b;
    128   else
    129     a->head = b;
    130   a->cur_block = b;
    131   a->cur = b->data;
    132   a->end = b->data + b->cap;
    133   aligned = ((uintptr_t)a->cur + (align - 1)) & ~(uintptr_t)(align - 1);
    134   a->cur = (u8*)(aligned + size);
    135   return (void*)aligned;
    136 }
    137 
    138 char* arena_strdup(Arena* a, const char* s, size_t len) {
    139   char* p = (char*)arena_alloc(a, len + 1, 1);
    140   if (!p) return NULL;
    141   if (len) memcpy(p, s, len);
    142   p[len] = 0;
    143   return p;
    144 }