Ruby 4.1.0dev (2026-11-19 revision b3e890bf959ffb14f55ecd016717417a62ebd04e)
arena.h
1#ifndef PRISM_INTERNAL_ARENA_H
2#define PRISM_INTERNAL_ARENA_H
3
10
11#include "prism/arena.h"
12
13#include <stddef.h>
14#include <stdint.h>
15#include <string.h>
16
17/*
18 * A single block of memory in the arena. Blocks are linked via prev pointers so
19 * they can be freed by walking the chain.
20 */
21typedef struct pm_arena_block {
22 /* The previous block in the chain (for freeing). */
23 struct pm_arena_block *prev;
24
25 /* The total usable bytes in data[]. */
26 size_t capacity;
27
28 /* The number of bytes consumed so far. */
29 size_t used;
30
31 /* The block's data. */
32 char data[PM_FLEX_ARRAY_LENGTH];
33} pm_arena_block_t;
34
35/*
36 * A bump allocator. Allocations are made by bumping a pointer within the
37 * current block. When a block is full, a new block is allocated and linked to
38 * the previous one. An allocation too large to share a block gets one of its
39 * own on a separate chain, so it does not displace the current block. All
40 * blocks are freed at once by walking both chains.
41 */
42struct pm_arena_t {
43 /* The active block (allocate from here). */
44 pm_arena_block_t *current;
45
46 /* Blocks that each hold a single large allocation, never bumped into. */
47 pm_arena_block_t *large;
48
49 /*
50 * The number of blocks allocated on the current chain, which sets the size
51 * of the next one.
52 */
53 size_t block_count;
54};
55
56/*
57 * Free all blocks in the arena. After this call, all pointers returned by
58 * pm_arena_alloc and pm_arena_zalloc are invalid.
59 */
60void pm_arena_cleanup(pm_arena_t *arena);
61
62/*
63 * Ensure the arena has at least `capacity` bytes available in its current
64 * block, allocating a new block if necessary. This allows callers to
65 * pre-size the arena to avoid repeated small block allocations.
66 */
67void pm_arena_reserve(pm_arena_t *arena, size_t capacity);
68
69/*
70 * Slow path for pm_arena_alloc: allocate a new block, either the next current
71 * block or a block of its own for a large allocation, and return a pointer to
72 * the first `size` bytes. Do not call directly — use pm_arena_alloc instead.
73 */
74void * pm_arena_alloc_slow(pm_arena_t *arena, size_t size);
75
76/*
77 * Report an allocation whose total size does not fit in a size_t. This
78 * goes through PRISM_OOM like any other allocation failure, and lives out of
79 * line so this header does not need the headers PRISM_OOM depends on.
80 */
81PRISM_NORETURN void pm_arena_alloc_overflow(void);
82
83/*
84 * Allocate memory from the arena. The returned memory is NOT zeroed. This
85 * function is infallible — it aborts on allocation failure.
86 *
87 * The fast path (bump pointer within the current block) is inlined at each
88 * call site. The slow path (new block allocation) is out-of-line.
89 */
90static PRISM_FORCE_INLINE void *
91pm_arena_alloc(pm_arena_t *arena, size_t size, size_t alignment) {
92 if (arena->current != NULL) {
93 size_t used_aligned = (arena->current->used + alignment - 1) & ~(alignment - 1);
94 size_t needed = used_aligned + size;
95
96 if (used_aligned >= arena->current->used && needed >= used_aligned && needed <= arena->current->capacity) {
97 arena->current->used = needed;
98 return arena->current->data + used_aligned;
99 }
100 }
101
102 return pm_arena_alloc_slow(arena, size);
103}
104
105/*
106 * Allocate memory from the arena whose address is aligned to the given power of
107 * two. Unlike pm_arena_alloc, the alignment may exceed the alignment of the
108 * arena's blocks, at the cost of a slower path that is not inlined.
109 */
110void * pm_arena_alloc_aligned(pm_arena_t *arena, size_t size, size_t alignment);
111
112/*
113 * Allocate memory for a single element of type T_ from the arena.
114 */
115#define PM_ARENA_ALLOC(arena_, T_) \
116 ((T_ *) pm_arena_alloc(arena_, sizeof(T_), PRISM_ALIGNOF(T_)))
117
118/*
119 * Allocate an array of elements from the arena. The returned memory is NOT
120 * zeroed. This function is infallible — it aborts on allocation failure.
121 */
122static PRISM_INLINE void *
123pm_arena_alloc_array(pm_arena_t *arena, size_t count, size_t size, size_t alignment) {
124 if (PRISM_UNLIKELY(count > SIZE_MAX / size)) pm_arena_alloc_overflow();
125 return pm_arena_alloc(arena, count * size, alignment);
126}
127
128/*
129 * Allocate an array of elements of type T_ from the arena.
130 */
131#define PM_ARENA_ALLOC_ARRAY(arena_, T_, count_) \
132 ((T_ *) pm_arena_alloc_array(arena_, count_, sizeof(T_), PRISM_ALIGNOF(T_)))
133
134/*
135 * Allocate zero-initialized memory from the arena. This function is infallible
136 * — it aborts on allocation failure.
137 */
138static PRISM_INLINE void *
139pm_arena_zalloc(pm_arena_t *arena, size_t size, size_t alignment) {
140 void *ptr = pm_arena_alloc(arena, size, alignment);
141 memset(ptr, 0, size);
142 return ptr;
143}
144
145/*
146 * Allocate a zero-initialized element of type T_ from the arena.
147 */
148#define PM_ARENA_ZALLOC(arena_, T_) \
149 ((T_ *) pm_arena_zalloc(arena_, sizeof(T_), PRISM_ALIGNOF(T_)))
150
151/*
152 * Allocate a zero-initialized array of elements from the arena. This function
153 * is infallible — it aborts on allocation failure.
154 */
155static PRISM_INLINE void *
156pm_arena_zalloc_array(pm_arena_t *arena, size_t count, size_t size, size_t alignment) {
157 void *ptr = pm_arena_alloc_array(arena, count, size, alignment);
158 memset(ptr, 0, count * size);
159 return ptr;
160}
161
162/*
163 * Allocate a zero-initialized array of elements of type T_ from the arena.
164 */
165#define PM_ARENA_ZALLOC_ARRAY(arena_, T_, count_) \
166 ((T_ *) pm_arena_zalloc_array(arena_, count_, sizeof(T_), PRISM_ALIGNOF(T_)))
167
168/*
169 * Allocate memory from the arena and copy the given data into it. This is a
170 * convenience wrapper around pm_arena_alloc + memcpy.
171 */
172static PRISM_INLINE void *
173pm_arena_memdup(pm_arena_t *arena, const void *src, size_t size, size_t alignment) {
174 void *dst = pm_arena_alloc(arena, size, alignment);
175 memcpy(dst, src, size);
176 return dst;
177}
178
179/*
180 * Resize an allocation from the arena from old_size to new_size bytes and
181 * return where it now lives. The sizes are in the same order as xrealloc_sized.
182 * An old_size of 0 means there is no allocation yet, so ptr may be NULL and a
183 * new allocation is returned.
184 *
185 * The most recent allocation in the current block ends exactly where the
186 * block's used bytes do, so it is resized in place when the block has room. Any
187 * other allocation stays where it is when it shrinks, and is copied into a new
188 * allocation when it grows, leaving the old one behind in the arena.
189 */
190static PRISM_INLINE void *
191pm_arena_realloc(pm_arena_t *arena, void *ptr, size_t new_size, size_t old_size, size_t alignment) {
192 void *result;
193
194 if (old_size == 0) {
195 result = pm_arena_alloc(arena, new_size, alignment);
196 } else {
197 pm_arena_block_t *block = arena->current;
198
199 if (block != NULL && (char *) ptr + old_size == block->data + block->used) {
200 size_t start = block->used - old_size;
201
202 if (new_size <= block->capacity - start) {
203 block->used = start + new_size;
204 return ptr;
205 }
206 }
207
208 if (new_size <= old_size) return ptr;
209
210 result = pm_arena_alloc(arena, new_size, alignment);
211 memcpy(result, ptr, old_size);
212 }
213
214 return result;
215}
216
217/*
218 * Reallocate an element of type T_ from the arena.
219 */
220#define PM_ARENA_REALLOC(arena_, ptr_, new_size_, old_size_, T_) \
221 ((T_ *) pm_arena_realloc(arena_, ptr_, new_size_, old_size_, PRISM_ALIGNOF(T_)))
222
223#endif
A bump allocator for the prism parser.
#define PRISM_UNLIKELY(x)
The compiler should predicate that this branch will not be taken.
Definition branch.h:17
#define PM_FLEX_ARRAY_LENGTH
A macro for helper define a flexible array member.
Definition flex_array.h:12
#define PRISM_FORCE_INLINE
Force a function to be inlined at every call site.
#define PRISM_INLINE
Old Visual Studio versions do not support the inline keyword, so we need to define it to be __inline.
Definition inline.h:12
#define PRISM_NORETURN
Mark a function as never returning to its caller, so that the compiler can treat the code after a cal...
Definition noreturn.h:15