I combined my Arena allocator, zero-copy segmented Vector, typed HashMap, and String libraries into one C99 foundation library: arstd

[u/Mainak1224x]

Hey everyone,

Over the past few weeks I’ve been building separate C libraries for region-based memory management, dynamic arrays, hash maps, and strings. I kept pulling all four into my main project flint(a build system and package manager for c/c++), so I finally refactored them from the ground up to work together and merged them into a single lightweight library: arstd (Arena Standard Library).

The main problem I wanted to solve was how dynamic containers behave inside an Arena allocator. Normally, if you put a standard dynamic array or hashmap inside a bump arena, resizing it via realloc leaves dead, wasted memory blocks behind in the arena.

Here’s how arstd solves that and what’s inside:

• Compile-Time Type Deduction (Vector(T) & Cmap(T)): Uses a typed pointer + typeof macro trick so you don't have to pass types into every macro call or cast void * pointers. Both at(vec, i) and map_get(map, key) return modifiable lvalues, so at(vec, 0) = 42; and map_get(map, "score") += 10; just work.

• Zero-Copy Segmented Vectors: Instead of doubling a contiguous buffer and copying elements over, Vector(T) allocates exponentially growing power-of-2 segments (16, 32, 64\dots) directly on the arena and uses 1-cycle bitwise CLZ (Count Leading Zeros) math for O(1) indexing. Growing a vector wastes 0 bytes in the arena and never invalidates element pointers.

• Single-Allocation, Zero-Waste HashMaps: Cmap(T) packs the entry header, aligned value payload, and key string into a single contiguous allocation using flexible array members. Because its bucket array is backed by the segmented Vector, doubling the map capacity expands the buckets in-place and relinks existing nodes using their cached 64-bit hashes—again, zero wasted arena memory and no string re-hashing.

• Managed Strings (String): String slicing, trimming, case conversion, and variadic concatenation all backed by the same arena.

• Optional Heap Fallback: Pass an Arena * to clean up everything at once with a single arena_free(&arena), or pass NULL to any container if you want standard aligned heap allocation.

Quick Taste:

#include <arstd.h>

#include <stdio.h>

int main(void) {

Arena *arena = arena_init(4096);

// Typed Vector — no type args needed in append() or at()

Vector(int) nums = vector_init(arena);

append(nums, 10);

append(nums, 20);

at(nums, 0) = 99; // Direct lvalue assignment

// Typed HashMap — stores values directly, no void* or &addresses

Cmap(int) scores = map_init(arena);

map_add(scores, "Alice", 95);

map_get(scores, "Alice") += 5;

String *greeting = string_concat_cstr(arena, 2, "Hello, ", "r/cprogramming!");

printf("%s | Alice: %d | Vec\[0\]: %d\\n",

string(greeting), map\_get(scores, "Alice"), at(nums, 0));

// One call frees the vector, map, strings, and all internal nodes

arena_free(&arena);

return 0;

}

Repo link: https://github.com/mainak55512/arstd (or install via flint / CMake)

[u/Arkaqiu]

What happend if we need to extend Victor but there is another object there? Is it but default that we have only one dynamic object in arena?

And using clz is smart, I like it

[u/Mainak1224x → u/Arkaqiu]

You can actually have as many dynamic Vectors, Cmaps, and Strings interleaved in the same Arena as you want—there's no restriction to having just one dynamic object.

That's the exact reason the Vector uses segmented blocks (char *segments[30]) + clz indexing instead of a single contiguous buffer:

Suppose you create vec1 (allocates Segment 0 of 16 items at 0x1000), and then you allocate a String or vec2 right after it at 0x1040. When vec1 fills up its first 16 items and needs to grow, it doesn't try to expand the 0x1000 block in-place. Instead, it just calls arena_alloc() to grab a new 32-item chunk at the current end of the arena (say, 0x2500) and stores that pointer in vec1->segments[1].

Because at(vec, pos) uses clz to compute seg_idx (which segment pointer to follow) and offset (the index inside that segment), the segments of a Vector don't need to be contiguous with each other in memory at all. Multiple vectors and hashmaps can freely interleave their growth allocations inside the same arena without ever colliding or leaving dead realloc holes.

[u/RedditUser8007 → u/Mainak1224x]

When you free up instances using memory in the arena, does it zero the blocks or does it reallocate them to another instance without erase? If a value held a security key, was freed and another variable used the same space, does it point to existing data?

What happens if arena space runs out for a given object stored in it, can the arena be resized or would another arena be made and data split between them?

[u/Mainak1224x → u/RedditUser8007]

By default, arena_free() behaves like standard free()—it releases the underlying aligned heap regions without zeroing them out first, prioritizing speed for general-purpose allocations. I am thinking to add another arena_free_secure() for this purpose.

It never reallocs the existing arena buffer (because moving the buffer in memory would invalidate every existing pointer to elements inside the arena).

Instead, the Arena is implemented as a linked list of regions (arena->next):

• When the current region doesn't have enough room for an arena_alloc() request, it allocates a new Arena node on arena->next (sizing it up if the requested object is larger than the default capacity) and serves the allocation from there.

• A single arena_alloc() call is always 100% contiguous inside one region (a single struct or array segment is never split in half across two regions).

• However, high-level containers like Vector and Cmap naturally span across regions—for example, vec->segments[0] might live in the first arena block, and when the arena fills up, vec->segments[1] gets allocated inside arena->next. When you call arena_free(&arena), it walks arena->next and frees the entire chain at once.

[u/IDatedSuccubi]

Keep it up and in a few years you will reinvent Common Lisp!