kit

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

buf.c (3362B)

      1 /* Chunked byte buffer. Append is O(1) (spills to a fresh chunk when the
      2  * tail fills). Random-access patch is O(N_chunks) — sections rarely
      3  * cross more than a handful of chunks, so a linear walk is fine. */
      4 
      5 #include "core/buf.h"
      6 
      7 #include <string.h>
      8 
      9 static BufChunk* chunk_new(Heap* h, size_t cap) {
     10   BufChunk* c =
     11       (BufChunk*)h->alloc(h, sizeof(BufChunk) + cap, _Alignof(BufChunk));
     12   if (!c) return NULL;
     13   c->next = NULL;
     14   c->used = 0;
     15   c->cap = (u32)cap;
     16   return c;
     17 }
     18 
     19 void buf_init(Buf* b, Heap* h) {
     20   b->heap = h;
     21   b->head = NULL;
     22   b->tail = NULL;
     23   b->total = 0;
     24 }
     25 
     26 void buf_fini(Buf* b) {
     27   BufChunk* c = b->head;
     28   while (c) {
     29     BufChunk* next = c->next;
     30     b->heap->free(b->heap, c, sizeof(BufChunk) + c->cap);
     31     c = next;
     32   }
     33   b->head = b->tail = NULL;
     34   b->total = 0;
     35 }
     36 
     37 static int buf_ensure_tail(Buf* b, size_t need) {
     38   BufChunk* c;
     39   size_t cap;
     40   if (b->tail && (b->tail->cap - b->tail->used) >= need) return 0;
     41   cap = need > BUF_CHUNK ? need : BUF_CHUNK;
     42   c = chunk_new(b->heap, cap);
     43   if (!c) return 1;
     44   if (!b->head) b->head = c;
     45   if (b->tail) b->tail->next = c;
     46   b->tail = c;
     47   return 0;
     48 }
     49 
     50 void buf_write(Buf* b, const void* data, size_t n) {
     51   const u8* p = (const u8*)data;
     52   while (n) {
     53     size_t avail;
     54     if (buf_ensure_tail(b, 1)) return; /* allocation failure swallowed */
     55     avail = b->tail->cap - b->tail->used;
     56     if (avail > n) avail = n;
     57     memcpy(b->tail->data + b->tail->used, p, avail);
     58     b->tail->used += (u32)avail;
     59     b->total += (u32)avail;
     60     p += avail;
     61     n -= avail;
     62   }
     63 }
     64 
     65 u8* buf_reserve(Buf* b, size_t n) {
     66   u8* p;
     67   if (buf_ensure_tail(b, n)) return NULL;
     68   p = b->tail->data + b->tail->used;
     69   b->tail->used += (u32)n;
     70   b->total += (u32)n;
     71   return p;
     72 }
     73 
     74 u32 buf_pos(const Buf* b) { return b->total; }
     75 
     76 /* Walk the chunk list intersecting [ofs, ofs+n), invoking copy(...) for
     77  * each contiguous slice. Patch and read share this; the only difference
     78  * is the direction of the memcpy.
     79  *
     80  * `direction`: 0 = copy from `external` into chunk; 1 = copy from chunk
     81  * into `external`. Inlined at both call sites by clang. */
     82 static inline void buf_walk(BufChunk* head, u32 ofs, void* external, size_t n,
     83                             int from_chunk) {
     84   BufChunk* c = head;
     85   u32 chunk_start = 0;
     86   u8* ext = (u8*)external;
     87   while (c && n) {
     88     u32 chunk_end = chunk_start + c->used;
     89     if (ofs < chunk_end) {
     90       u32 within = ofs - chunk_start;
     91       u32 avail = c->used - within;
     92       u32 take = (u32)(n < avail ? n : avail);
     93       if (from_chunk)
     94         memcpy(ext, c->data + within, take);
     95       else
     96         memcpy(c->data + within, ext, take);
     97       ext += take;
     98       n -= take;
     99       ofs += take;
    100     }
    101     chunk_start = chunk_end;
    102     c = c->next;
    103   }
    104   /* Caller's range must lie inside the written range; if n != 0 here,
    105    * the caller exceeded buf_pos and this is a contract violation.
    106    * Silent drop matches buf_write's allocation-failure policy. */
    107 }
    108 
    109 void buf_patch(Buf* b, u32 ofs, const void* data, size_t n) {
    110   buf_walk(b->head, ofs, (void*)data, n, /*from_chunk=*/0);
    111 }
    112 
    113 void buf_read(const Buf* b, u32 ofs, void* dst, size_t n) {
    114   buf_walk(b->head, ofs, dst, n, /*from_chunk=*/1);
    115 }
    116 
    117 void buf_flatten(const Buf* b, u8* dst) {
    118   BufChunk* c = b->head;
    119   while (c) {
    120     memcpy(dst, c->data, c->used);
    121     dst += c->used;
    122     c = c->next;
    123   }
    124 }