Introduction to the Segment Array: A Stable-Pointer Data Structure in C
By
ibobev
An everything bagel for the brain. Substantive, layered, well-seasoned.
Summary
The article introduces a data structure called a 'segment array,' which serves as an alternative to dynamic arrays in C, offering stable pointers and compatibility with arena allocators. The author explains its various names and implementations, providing a downloadable single-header implementation for practical use.
Key quotes
· 4 pulledA data structure that can be used in place of dynamic arrays, has stable pointers, and works well with arena allocators.
It’s been independently discovered by different programmers over the years and so goes by different names.
A 2001 paper called it a 'levelwise-allocated pile' (bleh). Others call it an 'exponential array'. I use the name 'segment array'.
I use C in this article, but its concepts work in other languages like Zig, Rust, or C++.
You might also wanna read
Practical Applications of Skiplists: From Niche Data Structure to Real-World Problem Solving
The article explores skiplists, a data structure often considered niche, and reveals their practical applications through the author's perso
antithesis.com·1mo ago
Cscript Style Guide: A Python-Inspired Approach to C Programming
Cscript is presented as a style guide for writing C code that aims to make C development faster and more Python-like while maintaining C's p
github.com·4mo ago
Pigeon's Device: An Independent Loop Optimization Technique in C Programming
The article introduces Pigeon's device, a loop optimization technique in C programming that was independently developed from Duff's device.
GPU-Accelerated Cuckoo Filter Implementation Using CUDA
This article describes a GPU-accelerated Cuckoo Filter implementation using CUDA, developed as part of a thesis project. The library provide
github.com·4mo ago
Wavelet Matrix: High-Performance Rust Implementation for Indexed Sequence Queries
Wavelet-matrix is a high-performance Rust-powered implementation of the Wavelet Matrix data structure for indexing static sequences of integ
pypi.org·5mo agoImplementing Closures in C Using JIT-Compiled Wrappers for Win32 Window Procedures
The article discusses an advanced programming technique for creating closures in C using JIT-compiled wrappers, specifically applied to Win3