ais: a plain-text index in C99, no dependencies, nothing allocated on the record path
I wrote a small tool for myself. You file a path, a link or a note under keys you choose, and get it back by those keys. What I would like comment on is how it is written, not what it does.
I came to C alongside FORTRAN, Ada 83 and Pascal in the 90s, so I think in functions, data locality and streams before objects. The rule is that memory is bounded by the structs, not by the data. Records go through one at a time, on the stack, in fixed buffers. get, find, set, merge and compact allocate nothing at all, so a 10 GB store and a 10 KB store run in the same footprint. Set operations are k-way merges over sorted posting lists: keep the head of each list and advance.
Six heap sites in 18k lines, each written down with what bounds it.
Two things I know are wrong: main() is 630 lines and the HTTP handler is 520. Both are flat dispatchers, both are too long, and both are written down as debts rather than defended.
On a million records, 85 MB store, one core: building the whole index is 7.9 s in one streaming pass, a full scan is 1.8 s (cat class), and a get on the hottest key, 270k ids, is 2.2 s. That last one used to take hours, because finding a record by id meant scanning the store; an id-to-offset index fixed it. Bulk import is still O(n^(2)) and I say so in the same doc.
C99, GPLv2+, no dependencies, plain Makefile. About 5k lines of tests, run under AddressSanitizer and UBSan on every push.
Style doc: https://github.com/Anode1/ais/blob/main/doc/dev/STYLE.md
Numbers, reproducible with a seeded generator: https://github.com/Anode1/ais/blob/main/doc/performance.txt
Code: https://github.com/Anode1/ais