segvec.h (7795B)
1 #ifndef KIT_SEGVEC_H 2 #define KIT_SEGVEC_H 3 4 /* Append-only segmented array with stable element pointers. 5 * 6 * Unlike VEC_GROW (core/vec.h), pushing onto a SegVec never moves 7 * existing elements: each segment is a separately heap-allocated chunk 8 * of (1 << SEG_SHIFT) elements. Pointers returned by _push and _at 9 * remain valid for the SegVec's lifetime, which lets callers stash 10 * `T*` references across further mutations of the table. 11 * 12 * Use SegVec for typed object tables (ObjBuilder.sections, LinkImage.syms, 13 * etc.) where stable pointers matter. Use VEC_GROW for transient lists, 14 * byte builders, and any case where the consumer needs a contiguous 15 * `T* + len` range. 16 * 17 * SEGVEC_DEFINE(NAME, T, SEG_SHIFT) 18 * NAME — typedef name for the SegVec instance. 19 * T — element type. 20 * SEG_SHIFT — log2 of segment size in elements. Each segment holds 21 * (1 << SEG_SHIFT) entries. Pick smaller (4-5) for tables 22 * that typically hold few elements; larger (6-8) for 23 * tables that scale with input size. Memory waste is 24 * bounded by one partially-filled segment. 25 * 26 * Emits typedef NAME and these static functions: 27 * void NAME##_init (NAME*, Heap*) 28 * void NAME##_fini (NAME*) 29 * T* NAME##_at (const NAME*, u32 i) — NULL if out of range 30 * T* NAME##_push (NAME*, u32* idx_out) — stable T*; NULL on OOM 31 * u32 NAME##_count (const NAME*) 32 * 33 * Indexed access is O(1) via two dependent loads (segment table, then 34 * segment data). The compiler hoists the segment lookup out of inner 35 * loops when iteration is structured per-segment; for simple `for i in 36 * 0..count` loops over _at, the cost is one extra load per element. 37 * 38 * Newly-pushed slots are zero-initialized — no `memset(p, 0, sizeof *p)` 39 * boilerplate at call sites. 40 */ 41 42 #include <string.h> 43 44 #include "core/core.h" 45 #include "core/heap.h" 46 47 #define SEGVEC_DEFINE(NAME, T, SEG_SHIFT_) \ 48 enum { \ 49 NAME##_SEG_SHIFT_ = (SEG_SHIFT_), \ 50 NAME##_SEG_SIZE_ = 1u << (SEG_SHIFT_), \ 51 NAME##_SEG_MASK_ = (1u << (SEG_SHIFT_)) - 1u \ 52 }; \ 53 \ 54 typedef struct NAME { \ 55 Heap* heap; \ 56 T** segs; /* segment table; doubling-grown */ \ 57 u32 nsegs; /* used segments */ \ 58 u32 segs_cap; /* allocated segment-table slots */ \ 59 u32 count; /* total elements pushed */ \ 60 } NAME; \ 61 \ 62 __attribute__((unused)) static inline void NAME##_init(NAME* v, Heap* h) { \ 63 v->heap = h; \ 64 v->segs = NULL; \ 65 v->nsegs = 0; \ 66 v->segs_cap = 0; \ 67 v->count = 0; \ 68 } \ 69 \ 70 __attribute__((unused)) static inline void NAME##_fini(NAME* v) { \ 71 u32 i; \ 72 for (i = 0; i < v->nsegs; ++i) \ 73 v->heap->free(v->heap, v->segs[i], sizeof(T) * NAME##_SEG_SIZE_); \ 74 if (v->segs) v->heap->free(v->heap, v->segs, sizeof(T*) * v->segs_cap); \ 75 v->segs = NULL; \ 76 v->nsegs = v->segs_cap = v->count = 0; \ 77 } \ 78 \ 79 __attribute__((unused)) static inline u32 NAME##_count(const NAME* v) { \ 80 return v->count; \ 81 } \ 82 \ 83 __attribute__((unused)) static inline T* NAME##_at(const NAME* v, u32 i) { \ 84 if (i >= v->count) return NULL; \ 85 return &v->segs[i >> NAME##_SEG_SHIFT_][i & NAME##_SEG_MASK_]; \ 86 } \ 87 \ 88 /* Append a fresh zero-initialized slot. Returns the stable T*, or \ 89 * NULL on allocation failure. If idx_out is non-NULL, writes the new \ 90 * slot's index. */ \ 91 __attribute__((unused)) static inline T* NAME##_push(NAME* v, \ 92 u32* idx_out) { \ 93 u32 i = v->count; \ 94 u32 s = i >> NAME##_SEG_SHIFT_; \ 95 u32 o = i & NAME##_SEG_MASK_; \ 96 T* slot; \ 97 if (s >= v->nsegs) { \ 98 T* newseg; \ 99 if (v->nsegs == v->segs_cap) { \ 100 u32 nc = v->segs_cap ? v->segs_cap * 2u : 4u; \ 101 T** ns = \ 102 (T**)v->heap->realloc(v->heap, v->segs, sizeof(T*) * v->segs_cap, \ 103 sizeof(T*) * nc, _Alignof(T*)); \ 104 if (!ns) return NULL; \ 105 v->segs = ns; \ 106 v->segs_cap = nc; \ 107 } \ 108 newseg = (T*)v->heap->alloc(v->heap, sizeof(T) * NAME##_SEG_SIZE_, \ 109 _Alignof(T)); \ 110 if (!newseg) return NULL; \ 111 memset(newseg, 0, sizeof(T) * NAME##_SEG_SIZE_); \ 112 v->segs[v->nsegs++] = newseg; \ 113 } \ 114 slot = &v->segs[s][o]; \ 115 v->count++; \ 116 if (idx_out) *idx_out = i; \ 117 return slot; \ 118 } \ 119 /* trailing struct decl swallows the macro-call's semicolon */ \ 120 struct NAME 121 122 #endif