SkipSpace

Heap-free C primitive for traversing and skipping huge implicit constrained search spaces on embedded systems.

SkipSpace is a deterministic embedded primitive using a compact sufficient-state machine, bounded subtree counting, and whole-subtree skipping.

Skip Space does not materialize the search tree. The caller owns a compact navigation state and a fixed workspace. The primitive updates the sufficient state, counts valid continuations with saturating arithmetic, and lets the caller visit or skip a subtree.

implicit search tree
        |
     push()
        |
 sufficient state
        |
  count subtree
        |
   visit / skip

V1 is deliberately small: navigation, bounded/saturating count, can_skip, and workspace sizing. The public core is portable C with no Arduino or ESP-IDF dependency and no dynamic allocation.

Quickstart

cmake -S . -B build -DSKIP_SPACE_BUILD_TESTS=ON
cmake --build build --config Release
ctest --test-dir build --output-on-failure

See docs/QUICKSTART.md and examples/quickstart/main.c.

What it is not

Skip Space is not a general solver, AI framework, vector database, or universal search engine. It requires a small sufficient state and a modeled transition table. count/can_skip are substantially more expensive than push/pop; applications normally use sparse skip checks. Rank/unrank is outside the V1 hot path.

The fundamental condition is:

Two prefixes may share a state only if their future-relevant behaviour is equivalent for the modeled problem.

If future behaviour requires retaining more history, the sufficient-state space can explode and the compression advantage disappears.

Embedded properties

• caller-owned, fixed workspace;
• deterministic memory use;
• saturating arithmetic with a caller-selected count type;
• no malloc, calloc, realloc, free, new, or delete in the core;
• C-compatible API and C++ linkage guards;
• depth bounded at 1000 in the V1 model.

Status

The ESP32-S3 uint32_t, 31-state, K=32 profile was measured on hardware. With sparse skip checks every 32 levels it achieved approximately 227,834 visited nodes/s. See docs/BENCHMARKS.md.

License

MIT. See LICENSE.