iddqd 0.4.6

Added

• from_iter_unique constructors on IdHashMap, BiHashMap, and TriHashMap, matching the existing IdOrdMap::from_iter_unique. These build a map from an iterator and, rather than overwriting, return an error on the first item that conflicts with an already-inserted one.

  Because a value in a BiHashMap or TriHashMap can conflict on more than one key at once, the error reports every distinct existing item it collides with (up to two for BiHashMap and up to three for TriHashMap).

Changed

• MSRV updated to Rust 1.86.

Fixed

• Deserialization no longer preallocates based on an unbounded size hint. Length-prefixed formats such as bincode and postcard derive their size hint from the input, so a small hostile payload claiming a huge number of elements could previously cause an excessively large allocation before any element was read. Preallocation is now capped at 1 MiB worth of items, matching what serde does for the standard library's collections.

• The insert_overwrite path on IdHashMap no longer aborts when an allocation fails, matching the existing guarantee on BiHashMap and TriHashMap. Instead, it results in a catchable panic. (The map is left unchanged, similar to BiHashMap and TriHashMap.)

  Note that BTreeMap::insert_overwrite will abort on allocation failure, because it calls into std which doesn't have an equivalent to HashMap::try_reserve.

Other improvements

• The insert paths now do fewer redundant checks for duplicates. Thanks izuzak for your first contribution!

iddqd 0.4.5

Added

• iddqd's core invariants are now formally verified under adversarial Hash and Ord impls using the Soteria symbolic executor. No new bugs were found during this process.

  The formal verification is broad (covers all possible adversarial return values) but bounded-depth; it acts as a complement to the existing layers of randomized testing, which are less broad but generate much deeper operation sequences.

  For more information on our validation philosophy, see this Oxide blog entry.

• Expanded examples for BiHashMap's Entry.

iddqd 0.4.4

Changed

• The FromIterator implementations now reserve capacity at the start of the operation.

iddqd 0.4.3

Fixed

• The insert_overwrite paths on BiHashMap and TriHashMap are now atomic in case user code panics. Thanks to SG-devel for your first contribution!

iddqd 0.4.2

Fixed

• The retain callbacks no longer permit the RefMut to be stashed outside them. This is technically a breaking change, but is being treated as a soundness bugfix.
• A number of soundness and resilience fixes for pathological implementations. These were found through a combination of human-driven analysis, example-based tests with Miri, chaos testing using fault injection with proptest, and adversarial code review from Claude Opus 4.7 and GPT-5.5. In particular, iddqd now more consistently preserves internal map state across panics in user code by using patterns like prepare-then-commit, index-based cleanup, cached hashes, and careful ordering of user-code execution relative to internal mutations.

Changed

• MSRV updated to Rust 1.85.

iddqd 0.4.1

Fixed

• Fixed a logic bug in TriHashMap::remove_unique, when key1 matches, and one of key2 and key3 matches, but not the other.

iddqd 0.4.0

Changed

• The internal implementation for item storage has been changed to use a linear slot-based buffer, resulting in 2-3x performance improvements for most workloads.
• The maps now have a limit of u32::MAX (4 294 967 295) elements at any given time. This limit is very unlikely to be reached in practice.

Fixed

• All mutation methods for IdHashMap and IdOrdMap are now panic-safe, in the sense that a panic in user code will not corrupt the map. This does not currently extend to BiHashMap and TriHashMap

Added

• Many more unit and property-based tests covering various kinds of pathological user implementations. We now have high confidence that arbitraily buggy user implementations (as long as they're in safe Rust) will not result in undefined behavior.

iddqd 0.3.18

Fixed

• Fixed a rehashing bug in hash map reserve and shrink-to-fit methods. (Due to an oversight, these methods were previously not part of our property-based tests. Now they are. Sorry about that!)

iddqd 0.3.17

Added

• Capacity management methods for all map types:
  • reserve(&mut self, additional: usize) reserves capacity for at least additional more elements.
  • shrink_to_fit(&mut self) shrinks capacity to fit the current length.
  • shrink_to(&mut self, min_capacity: usize) shrinks capacity to at least min_capacity.
  • try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>: fallible capacity reservation for hash maps (IdHashMap, BiHashMap, TriHashMap).
• New TryReserveError type in the errors module for reporting allocation failures.

Notes

• For IdOrdMap, the reserve and shrink methods only affect item storage. The internal BTreeSet used for item ordering does not support capacity control.
• IdOrdMap does not provide try_reserve, since the underlying BTreeSet does not expose fallible reservation operations.

Fixed

• Fixed an instance of potential unsoundness in retain.

Changed

The Extend implementations now pre-reserve capacity based on the iterator's size_hint.

iddqd 0.3.16

Added

• clear methods for all map types to remove all items from the map.
• Optionally, serialize ID maps as maps (JSON objects) rather than sequences (JSON arrays):
  • New IdHashMapAsMap, BiHashMapAsMap, TriHashMapAsMap, and IdOrdMapAsMap marker types to use with #[serde(with = ...)].
  • The default deserializer for each map now accepts both maps and sequences.

Changed

• Documentation improvements for serde implementations.