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
//! # The `hash_arr_map` Crate
//!
//! This crate contains a different implementation of a hash map that, instead
//! of always storing both the key and the value, can, for specific keys, just
//! store the value, inferring the key from the value's context.
//!
//! This results in the map having separate `array` and `hash` parts, where the
//! `hash` part stores both keys and values, while the `array` part stores just
//! values. The array part's indices are 1-based, meaning that a key of 0 will
//! not be stored in it.
//!
//! The design is based on [Lua]'s table design, which is the language's
//! associative hash map. Due to it being Lua's only data structure, it was
//! used with integer keys very frequently. In order to improve the performance
//! of tables with integer keys, a separate array section was created that was
//! only indexed by integer, meaning that keys did not need to be hashed.
//!
//! [Lua]: https://www.lua.org/
//!
//! As an example, say you make a new [`Ham`] with a capacity of 2 in
//! the array part and 2 in the hash part.
//!
//! ```rust
//! use hash_arr_map::Ham;
//! let mut map = Ham::with_capacity(2, 2);
//! # let _: Ham<i32, i32> = map; // Infer type
//! ```
//!
//! You then feed it the key-value pairs `1, 10`, `2, 20`, `3, 30`, and `4, 40`.
//!
//! ```rust
//! # use hash_arr_map::Ham;
//! # let mut map = Ham::with_capacity(2, 2);
//! # let _: Ham<i32, i32> = map; // Infer type
//! map.insert(1, 10);
//! map.insert(2, 20);
//! map.insert(3, 30);
//! map.insert(4, 40);
//! ```
//!
//! The map will not have allocated, since there is ample capacity.
//!
//! One possible layout of the map would be this:
//!
//! ```text
//! +----------------------------+
//! | Ham |
//! | +------------+-----------+ | +----+----+----+----+
//! | | array_part | hash_part ----> | 4 | 40 | 3 | 30 |
//! | +-----|------+-----------+ | +----+----+----+----+
//! +-------|--------------------+
//! | +----+----+
//! '--> | 10 | 20 |
//! +----+----+
//! ```
//!
//! Note that the keys of `1` and `2` have not been stored. This is because
//! they can be recalculated from the index into the array part.
#![feature(
const_ptr_offset,
const_ptr_offset_from,
const_precise_live_drops,
const_mut_refs,
const_refs_to_cell,
const_raw_ptr_deref,
crate_visibility_modifier
)]
#![forbid(unsafe_op_in_unsafe_fn)]
#![warn(clippy::missing_const_for_fn)]
#![no_std]
extern crate alloc;
#[cfg(feature = "std")]
extern crate std;
pub mod map;
pub use map::Ham;
pub mod set;
pub use set::HashArrSet;
mod key;
pub use key::Key;
mod test_index;
pub use test_index::{FromIndex, Idx, IntoIndex, NewIndex};