kit

buf.c (5796B)

---

 /* Chunked byte buffer. Append is O(1) (spills to a fresh chunk when the tail
  * fills). Random-access patch/read is O(log N_chunks) via a sorted directory of
  * chunk start offsets — large sections (e.g. a multi-megabyte .text emitted for
  * tens of thousands of functions) span hundreds of chunks, and per-function
  * patch-ups would otherwise be O(N_chunks) each, i.e. O(n^2) overall. */
 
 #include "core/buf.h"
 
 #include <string.h>
 
 static BufChunk* chunk_new(Heap* h, size_t cap) {
   BufChunk* c =
       (BufChunk*)h->alloc(h, sizeof(BufChunk) + cap, _Alignof(BufChunk));
   if (!c) return NULL;
   c->next = NULL;
   c->used = 0;
   c->cap = (u32)cap;
   return c;
 }
 
 void buf_init(Buf* b, Heap* h) {
   b->heap = h;
   b->head = NULL;
   b->tail = NULL;
   b->total = 0;
   b->dir = NULL;
   b->ndir = 0;
   b->dir_cap = 0;
 }
 
 void buf_fini(Buf* b) {
   BufChunk* c = b->head;
   while (c) {
     BufChunk* next = c->next;
     b->heap->free(b->heap, c, sizeof(BufChunk) + c->cap);
     c = next;
   }
   if (b->dir)
     b->heap->free(b->heap, b->dir, (size_t)b->dir_cap * sizeof(BufChunkRef));
   b->head = b->tail = NULL;
   b->total = 0;
   b->dir = NULL;
   b->ndir = b->dir_cap = 0;
 }
 
 /* Record a newly created chunk in the directory. Best-effort: on allocation
  * failure the chunk is still reachable via the `next` chain, so buf_walk stays
  * correct (just slower for offsets past the last indexed chunk). */
 static void buf_dir_push(Buf* b, BufChunk* c, u32 start) {
   if (b->ndir == b->dir_cap) {
     u32 ncap = b->dir_cap ? b->dir_cap * 2u : 16u;
     BufChunkRef* nd = (BufChunkRef*)b->heap->alloc(
         b->heap, (size_t)ncap * sizeof(BufChunkRef), _Alignof(BufChunkRef));
     if (!nd) return;
     if (b->dir) {
       memcpy(nd, b->dir, (size_t)b->ndir * sizeof(BufChunkRef));
       b->heap->free(b->heap, b->dir, (size_t)b->dir_cap * sizeof(BufChunkRef));
     }
     b->dir = nd;
     b->dir_cap = ncap;
   }
   b->dir[b->ndir].start = start;
   b->dir[b->ndir].chunk = c;
   b->ndir++;
 }
 
 static int buf_ensure_tail(Buf* b, size_t need) {
   BufChunk* c;
   size_t cap;
   if (b->tail && (b->tail->cap - b->tail->used) >= need) return 0;
   cap = need > BUF_CHUNK ? need : BUF_CHUNK;
   c = chunk_new(b->heap, cap);
   if (!c) return 1;
   /* The new chunk starts at the current total (all prior chunks are frozen). */
   buf_dir_push(b, c, b->total);
   if (!b->head) b->head = c;
   if (b->tail) b->tail->next = c;
   b->tail = c;
   return 0;
 }
 
 /* Out-of-line tail of buf_write: handles the empty-tail and chunk-spanning
  * cases. The common single-chunk append is inlined in buf.h; only writes that
  * don't fit the current tail (or hit an empty/NULL tail) land here. */
 void buf_write_slow(Buf* b, const void* data, size_t n) {
   const u8* p = (const u8*)data;
   while (n) {
     size_t avail;
     if (buf_ensure_tail(b, 1)) return; /* allocation failure swallowed */
     avail = b->tail->cap - b->tail->used;
     if (avail > n) avail = n;
     memcpy(b->tail->data + b->tail->used, p, avail);
     b->tail->used += (u32)avail;
     b->total += (u32)avail;
     p += avail;
     n -= avail;
   }
 }
 
 u8* buf_reserve(Buf* b, size_t n) {
   u8* p;
   if (buf_ensure_tail(b, n)) return NULL;
   p = b->tail->data + b->tail->used;
   b->tail->used += (u32)n;
   b->total += (u32)n;
   return p;
 }
 
 u32 buf_pos(const Buf* b) { return b->total; }
 
 /* Walk the chunk list intersecting [ofs, ofs+n), invoking copy(...) for
  * each contiguous slice. Patch and read share this; the only difference
  * is the direction of the memcpy.
  *
  * `direction`: 0 = copy from `external` into chunk; 1 = copy from chunk
  * into `external`. Inlined at both call sites by clang. */
 static inline void buf_walk(const Buf* b, u32 ofs, void* external, size_t n,
                             int from_chunk) {
   BufChunk* c;
   u32 chunk_start;
   u8* ext = (u8*)external;
   /* Fast path: emit-time patch-ups and reads overwhelmingly target the
    * most-recently-written bytes (a function's own just-emitted prologue and
    * branches), which live in the last indexed chunk. Check it before the binary
    * search so the common case is O(1) instead of O(log n_chunks). */
   if (b->ndir > 0 && ofs >= b->dir[b->ndir - 1].start) {
     c = b->dir[b->ndir - 1].chunk;
     chunk_start = b->dir[b->ndir - 1].start;
   } else {
     /* Binary-search the directory for the last chunk whose start is <= ofs,
      * then walk forward (the range may span into following chunks). */
     u32 lo = 0, hi = b->ndir;
     while (lo < hi) {
       u32 mid = lo + ((hi - lo) >> 1);
       if (b->dir[mid].start <= ofs)
         lo = mid + 1;
       else
         hi = mid;
     }
     if (lo == 0) {
       c = b->head;
       chunk_start = 0;
     } else {
       c = b->dir[lo - 1].chunk;
       chunk_start = b->dir[lo - 1].start;
     }
   }
   while (c && n) {
     u32 chunk_end = chunk_start + c->used;
     if (ofs < chunk_end) {
       u32 within = ofs - chunk_start;
       u32 avail = c->used - within;
       u32 take = (u32)(n < avail ? n : avail);
       if (from_chunk)
         memcpy(ext, c->data + within, take);
       else
         memcpy(c->data + within, ext, take);
       ext += take;
       n -= take;
       ofs += take;
     }
     chunk_start = chunk_end;
     c = c->next;
   }
   /* Caller's range must lie inside the written range; if n != 0 here,
    * the caller exceeded buf_pos and this is a contract violation.
    * Silent drop matches buf_write's allocation-failure policy. */
 }
 
 void buf_patch(Buf* b, u32 ofs, const void* data, size_t n) {
   buf_walk(b, ofs, (void*)data, n, /*from_chunk=*/0);
 }
 
 void buf_read(const Buf* b, u32 ofs, void* dst, size_t n) {
   buf_walk(b, ofs, dst, n, /*from_chunk=*/1);
 }
 
 void buf_flatten(const Buf* b, u8* dst) {
   BufChunk* c = b->head;
   while (c) {
     memcpy(dst, c->data, c->used);
     dst += c->used;
     c = c->next;
   }
 }