2 ms·
In 2020 I wrote a serialization system for types in C, as the foundation for a kind of distributed database. Types are a tree structure: records with fields tha
by kazinator 6y ago
In 2020 I wrote a serialization system for types in C, as the foundation for a kind of distributed database. Types are a tree structure: records with fields that can be records; arrays with elements that can be any type. Thus the serializing and deserializing operations are recursive.
The system has no external tooling (no description language). The application uses the C API to construct the needed types at initialization time.
I have a test case whereby a whole linked list is serialized and deserialized. The deserialize function mallocs the necessary nodes. There is a function to recursively free the object, using the serial type as a guide.
Another time, a little bit farther back, I worked with something recursive on the job fairly recently was speeding up the recursive file system tree walking function in BusyBox. It fails to take advantage of the Linux-specific d_type field in the inode. With that you can avoid stat calls.
This shaved a bunch of time off the boot of an embedded system, where BuxyBox's mdev program was scanning through device nodes in /sys.
Yet another time. I used recursion to shrink a Linux image by blowing away unused content in the initramfs. That time I used Python to write a kind of "garbage collection" program: it recursively traversed the contents of an initramfs filesystem, determining what files are reachable, marking those files and deleting the rest. Reachability was determined mainly by scanning the file contents for occurrences of the names of other files, with some other heuristics. The root node was the init script; the idea being that anything not required by the initramfs init script is bloat. The idea worked; we got a smaller initramfs that still booted fine.