Collapsiv

Collapsiv is a methodology for allocating term data structures in a space-efficient manner. It implements maximal sharing in the same manner that hash consing does, but without the overhead of a hash table. Instead, terms are constructed on a stack, the bottom of which serves to persist term structures; this storage is searched recursively whenever a new term is created, and aliases (pointers into the stack) are returned when an existing identical term structure is found therein.

In this respository is a proof-of-concept implementation of Collapsiv in C99 as a shared library. The included GNU-compatible Makefile will build static and dynamically linked versions of this library, as well as the executable test_collapsiv which will run the tests.

TODO

• better documentation
• more tests
• better naming convention for functions
• convert to C89 aka ANSI C
• translate to 6502 assembly language