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};