A DAFSA (also called a DAWG — directed acyclic word graph) is a minimized, deterministic, acyclic finite-state automaton that represents a set of strings/keys. Unlike a trie, shared suffixes are merged, so common prefixes and suffixes collapse into shared states, yielding a compact representation.
Unlike a batch-built automaton, this implementation supports add and delete of individual keys while keeping the automaton minimal after every operation, following Carrasco & Forcada (2002):
Keys are _n length-delimited, so they may contain embedded NUL bytes.
This is the canonical DAFSA engine for the fixpoint-linux stack — a split multi-file implementation (not a single monolithic .c), consumed as a git submodule by downstream projects.
dafsa.h # public opaque API dafsa_internal.h # shared internal decls dafsa.c # public entry, driver dafsa_state.c # state + register dafsa_core.c # add/delete/lookup core dafsa_persist.c # save/load (PDWG v4) dafsa_view.c # mmap read-only view dafsa_wal.c # write-ahead log dafsa_crc32.c # sidecar checksum dafsa_build.c # bulk minimal build dafsa_rank.c # rank/serialization dafsa_view_rank.c # ranked view helpers
dafsa_create / dafsa_free manage an opaque heap handle with growable state — no fixed static arrays, no per-edge malloc/free.
dafsa_add_n / dafsa_lookup_n / dafsa_delete_n (plus NUL-terminated add / lookup / delete wrappers) work on length-delimited keys.
dafsa_build_sorted constructs a minimal automaton from a sorted, deduplicated key list (Daciuk et al.), the fast path for large initial corpora.
dafsa_prefix_enum enumerates hits under a prefix; dafsa_stats reports state/transition counts; dafsa_dot exports a Graphviz description; dafsa_abi_version reports the ABI.
Portably C11 — builds with a system cc (see the Makefile) into a shared libdafsa.so.
dafsa_save / dafsa_load persist the automaton to the compact PDWG v4 on-disk format. dafsa_load_readonly mmaps the file for a read-only, zero-copy fast path — search-only, skipping the inode/register rebuild.
A write-ahead log (dafsa_wal_*) records append_add / append_del operations for crash-consistent, replayable updates: dafsa_wal_replay applies them back into the automaton. dafsa_view_open_layered layers a mmap'd base index with the WAL for a fast read path over recent writes.
$ dafsa_view_open(fst_path) # mmap, search-only, zero-copy $ dafsa_view_open_layered(fst_path, wal_path) # base index + WAL overlay $ dafsa_load(path) # read-write, rebuilds inode/register
A DAFSA-backed Datalog engine in C. Uses this engine at vendor/dafsa for bulk minimal build + rank + view.
A full-text indexer. Uses this engine at indexer/dafsa/vendor/dafsa and keeps its own dafsa_build.c build_main locally.
Both the engine and the docs site are built with dhake: the C engine into a shared libdafsa.so, and the Elm app (rendered against the Fixpoint design package) into the docs site.
$ ./dhake/dhake.com libdafsa.so # build libdafsa.so $ ./dhake/dhake.com clean # remove objects + lib $ ./dhake/dhake.com # build dist/index.html (docs site)