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
//! # 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(option_result_unwrap_unchecked)] #![feature(const_ptr_offset)] #![feature(const_ptr_offset_from)] // #![feature(const_replace)] #![feature(const_precise_live_drops)] #![feature(const_mut_refs)] #![feature(const_refs_to_cell)] #![feature(const_raw_ptr_deref)] #![feature(const_panic)] // #![feature(const_trait_impl)] // #![feature(const_fn_trait_bound)] // #![feature(const_fn_fn_ptr_basics)] #![feature(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};