sparsemap 5.1.0

A sparse, compressed bitmap with run-length encoding, optimized for long runs of consecutive bits. 100% safe Rust, no_std, zero dependencies; reads the C sparsemap library's serialized format.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

# Changelog

All notable changes to the Rust `sparsemap` crate are documented here.
The format follows [Keep a Changelog](https://keepachangelog.com), and
the crate follows [SemVer](https://semver.org).

## [5.1.0] - 2026-06-24

Version realigned with the C `sparsemap` library, which is at 5.1.0.
There is no 5.0.0 of this crate: C 5.0.0 was an internal struct-shrink
of the C `sm_t` (per-map allocator removed, cursor externalized,
lineage folded into the capacity word) with no effect on the wire
format or on any behavior this crate can observe -- the Rust port
models a map as a `BTreeMap`, not the C byte struct, so it had nothing
to change.  Jumping straight to 5.1.0 keeps the two version numbers in
lockstep.

### Changed

- **The chunk-count header is now a full 64-bit value** (parity with C
  `sparsemap` 5.1.0).  Through 4.x it was a `u32` in the low 4 bytes of
  the 8-byte header slot, capping a serialized map at `2^32 - 1`
  (~4.29 billion) chunks; for pathologically sparse, scattered data
  (one set bit per 2048-bit chunk) that count -- not the `2^64` index
  space -- was the binding ceiling on cardinality.  Reading and writing
  the whole slot as a little-endian `u64` removes the limit.

### Compatibility

- **Wire format is unchanged at version `2`; no break.**  The header
  slot's high 4 bytes were always zero for any count `< 2^32`, so a
  5.1.0 writer emits bytes identical to 4.x for every real map, and a
  5.1.0 reader sees the same value in any 4.x buffer.  Verified: the
  checked-in C fixtures (emitted by C 4.0.0) are byte-for-byte
  identical to those emitted by C 5.1.0, and both read/write cross-FFI
  directions pass against C 5.1.0.

### Verified

- All unit, doc, and `proptest` model tests pass; `clippy -D warnings`
  and `rustfmt` clean; `no_std` build green.
- Read- and write-direction wire compatibility against C `sparsemap`
  5.1.0.

## [4.0.0] - 2026-06-04

### Fixed

- **Data loss for indices `>= 2^32`** (parity with C `sparsemap` 4.0.0):
  the wire format's chunk-start offsets are now 8 bytes (`u64`) so the
  serialized form addresses the full 64-bit universe the API has always
  advertised.  Previously, `to_bytes()` returned `EncodeError::IndexTooLarge`
  for any bit at or above `2^32`; now it succeeds for any valid index.

### Changed (breaking)

- The on-disk **wire format version** is now `2`.  Buffers written by
  the C `sparsemap` 4.0.0+ deserialize transparently; pre-4.0 buffers
  (v1, 4-byte starts) are rejected with `DecodeError::UnsupportedVersion(1)`
  and need to be re-serialized through C 4.0.0+ first.
- `SparseMap::to_bytes` is now infallible: signature changes from
  `Result<Vec<u8>, EncodeError>` to `Vec<u8>`.  Callers must drop the
  `?`/`.unwrap()`/`.expect()` they had on the result.
- `EncodeError` is removed (the `2^32` cap it expressed no longer
  exists).

### Verified

- Read-direction wire compatibility against checked-in fixtures emitted
  by C 4.0.0's `sm_serialize`.
- Write-direction wire compatibility (`ci/wire_compat.sh`): C 4.0.0
  reads byte-for-byte the buffers Rust produces, recovering identical
  bit sets across six representative shapes.
- `clippy::pedantic` and `rustfmt` clean; `no_std` build green.

## [3.0.1] - 2026-06-03

### Changed

- The crate is now **100% Rust with zero dependencies and no build
  script**.  3.0.0 carried a `cc` build-dependency and a `build.rs`
  that compiled the C library for an in-tree wire-compatibility test;
  a default `cargo add sparsemap` pulled and compiled `cc` (a no-op for
  consumers, since no C source ships in the crate).  Both are removed.
- Cross-language wire compatibility is still verified: the read
  direction (decoding C output) is now an in-crate, pure-Rust test
  against checked-in fixtures produced by the C `sm_serialize`
  (`ci/gen_fixtures.c`); the write direction (the C library reading
  Rust's `to_bytes`) runs in CI via `ci/wire_compat.sh`, which is
  excluded from the published crate.

No API or behavior changes.

## [3.0.0] - 2026-06-03

First release of the Rust port.  The version is aligned with the C
library's 3.0.0 so that "sparsemap 3.0.0" means the same thing in either
language.

### Added

- `SparseMap`: a safe, `no_std`-compatible sparse bitset over `u64`.
- Core operations: `insert`, `remove`, `contains`, `clear`,
  `cardinality`, `is_empty`, `min`, `max`, `rank`, `select`, `span`,
  `insert_range`, `remove_range`, `shifted`.
- Set algebra: `union`, `intersection`, `difference`,
  `symmetric_difference`, `intersects`, `is_subset`, `is_superset`,
  plus the `|`, `&`, `-`, `^` operators and their assigning forms.
- Iteration: `iter` (ascending), `to_vec`, and `IntoIterator` for
  `&SparseMap`.
- Standard traits: `Clone`, `Debug`, `Default`, `PartialEq`, `Eq`,
  `Hash`, `FromIterator<u64>`, `Extend<u64>`.
- `to_bytes` / `from_bytes`: serialization wire-compatible with the C
  library, with `EncodeError` / `DecodeError`.
- `forbid(unsafe_code)`; `no_std` with an `alloc` dependency and an
  optional `std` feature for `std::error::Error` impls.

### Verified

- Property tests against a `BTreeSet` oracle (stateful model, set
  operations, serialization round-trip, parse robustness).
- Cross-implementation wire-format tests: maps serialized by the C
  library deserialize here, and vice versa.
- Clean under `clippy::pedantic` and `rustfmt`.