# Description of Changes
Defines `SmallHashMap` in `spacetimedb_data_structures`.
The data structure is a hybrid map that is backed by a vector and linear
scan for the first `M` elements.
Then it falls back into a normal hash map.
For the first `N` elements, where `N < M`, the vector is stored inline.
That is, the vector is a `SmallVec<[(K, V); N>`.
The structure is optimized for access patterns where the keys and values
are accessed together,
therefore, keys and values are not stored separately.
# API and ABI breaking changes
None, just additive.
# Expected complexity level and risk
1
# Testing
A comprehensive proptest suite is added for the datastructure.
# Description of Changes
There were mentions of `hashbrown` in the repo that did not go through
`spacetimedb_data_structures::map`.
This caused compile errors on master when running certain tests locally.
These have been replaced with the proper imports.
The PR also bump hashbrown to 0.16.1 and foldhash to 0.2.0.
# API and ABI breaking changes
None
# Expected complexity level and risk
2
# Testing
Covered by existing tests.
* 1. Split ColumnOp into ColumnOp & FieldOp, former storing ColId
2. Shrink SqlAst to 80 bytes, so it can be passed in registers
3. Store end-result Header in IndexSemiJoin
4. Remove operational use of Header in ColumnOp & build_query
5. Simplify RowRef::{get, project, project_owned}
* Make parts of build_query actually infallible.
1. Make IndexSemiJoin::filter infallible.
2. Make ColumnOp::compare and friends infallible.
3. Make RowRef::{get, project, project_owned} infallible.
* Make RelOps::next itself infallible
* 1. with_select{_cmp}: ensure type safety o query exec cannot panic
2. Document RelValue::{get, read_or_take_column, project_owned}
3. Refactor optimize_select
4. Ensure in optimize_select that conditions are merged with preceding selects
* remove RelOps::{head, row_count}; head is redundant & row_count is useless
* remove Relation trait; it does not carry its weight
* make build_query infallible
* simplify IndexSemiJoin, make it slightly less branchy
* simplify try_index_join
* split IndexSemiJoin into Left & Right parts
* move get_field_pos to test code
* move test version of build_query to test code
Noa