use alloc::vec::Vec;
use core::{
borrow::Borrow,
cell::Cell,
fmt,
fmt::Formatter,
hash::{BuildHasher, Hash, Hasher},
iter::FromIterator,
mem,
num::NonZeroUsize,
ops::{Index, IndexMut},
};
use crate::{FromIndex, Idx, IntoIndex, Key, NewIndex};
mod hasher;
use hasher::LuaBuildHasher;
mod iter;
pub use iter::{IntoIter, Iter, IterMut, Keys, Values, ValuesMut};
macro_rules! cp {
($T:ty => $U:ty, $v:ident => $field:ident) => {
match $v {
ref cell => {
let cell: &Cell<$T> = cell;
let ptr: *mut $T = cell.as_ptr();
let member_ptr: *mut $U = unsafe { ::core::ptr::addr_of_mut!((*ptr).$field) };
let cell_ptr: *mut Cell<$U> = member_ptr.cast();
unsafe { &*cell_ptr }
}
}
};
}
mod node;
use node::Node;
mod entry;
pub use entry::{Entry, OccupiedEntry, VacantEntry};
#[inline]
const fn round_pow_2(x: usize) -> usize {
if x == 0 {
0
} else {
x.next_power_of_two()
}
}
// Round x down to the next power of two
#[inline]
const fn round_down_pow_2(x: usize) -> usize {
if x.is_power_of_two() {
x
} else {
x.next_power_of_two() >> 1
}
}
#[inline]
const fn ceil_log_2(x: NonZeroUsize) -> usize {
// This function computes ceil(log2(i)).
//
// usize::MAX => usize::BITS,
// usize::MAX >> 1 => usize::BITS - 1
// ...
// 4 => 2
// 3 => 2
// 2 => 1
// 1 => 0
(usize::BITS - (x.get() - 1).leading_zeros()) as usize
}
// #[test]
// fn test_ceil_log_2() {
// let inputs = [
// (1, 0),
// (2, 1),
// (3, 2),
// (4, 2),
// (5, 3),
// (6, 3),
// (7, 3),
// (8, 3),
// (9, 4),
// (10, 4),
// (usize::MAX, usize::BITS as usize),
// (usize::MAX >> 1, usize::BITS as usize - 1),
// ];
// for (input, output) in inputs.iter().copied() {
// assert_eq!(
// ceil_log_2(NonZeroUsize::new(input).unwrap()),
// output,
// "input = {}. lz = {}",
// input,
// input.leading_zeros()
// );
// }
// }
const NUMS_LEN: usize = usize::BITS as usize;
type Nums = [usize; NUMS_LEN];
/// A hash map with an `array` part and a `hash` part, like [Lua]'s table structure.
///
/// [Lua]: https://www.lua.org/
///
/// This is most useful when you want to use the map like a sparse array, since
/// the hash part can store most of the sparse items, while the array part offers
/// better performance than `HashMap` for arrays that aren't very sparse.
///
/// It is required that the keys implement the [`Eq`] and [`Hash`] traits, although
/// this can frequently be achieved by using `#[derive(PartialEq, Eq, Hash)]`.
/// If you implement these yourself, it is important that the following
/// property holds:
///
/// ```text
/// k1 == k2 -> hash(k1) == hash(k2)
/// ```
///
/// In other words, if two keys are equal, their hashes must be equal.
///
/// Additionally, keys are required to implement the [`IntoIndex`] and [`FromIndex`]
/// traits that allow conversion to and from indices into the `array` part.
///
/// It is a logic error for a key to be modified in such a way that the key's
/// hash, as determined by the [`Hash`] trait, or its equality, as determined by
/// the [`Eq`] trait, changes while it is in the map. This is normally only
/// possible through [`Cell`], [`RefCell`], global state, or I/O.
///
/// # Examples
///
/// ```
/// use hash_arr_map::Ham;
///
/// // Type inference lets us omit an explicit type signature (which
/// // would be `Ham<i32, i32>` in this example).
/// let mut squares = Ham::new();
///
/// // Square some numbers.
/// squares.insert(1, 1);
/// squares.insert(2, 4);
/// squares.insert(3, 8);
/// squares.insert(5, 25);
///
/// // Check for a specific square.
/// if !squares.contains_key(&4) {
/// println!(
/// "We've got {} squares, but not the square of 4.",
/// squares.len()
/// );
/// }
///
/// // oops, this square is incorrect. Let's delete it
/// squares.remove(&3);
///
/// // Iterate over everything.
/// for (number, square) in &squares {
/// println!("{}'s square is {}", number, square);
/// }
/// ```
///
/// `Ham` also implements an [`Entry API`](#method.entry), which allows
/// for more complex methods of getting, setting, updating and removing keys and
/// their values:
///
/// ```rust
/// use hash_arr_map::Ham;
///
/// let text = "Rust's strings are utf-8 \u{2764}";
///
/// // Type inference lets us not say what type of map this is.
/// // (`Ham<char, usize>` in this example)
/// let mut map = Ham::new();
///
/// for c in text.chars() {
/// map.entry(c).and_modify(|c| *c += 1).or_insert(1_usize);
/// }
///
/// assert_eq!(map[&'t'], 3);
/// assert_eq!(map[&'s'], 4);
/// assert_eq!(map[&'❤'], 1);
/// ```
///
/// The easiest way to use `Ham` with a custom key type is to derive [`Eq`] and [`Hash`],
/// then implement [`IntoIndex`] and [`FromIndex`] for it.
/// We must also derive [`PartialEq`].
///
/// [`RefCell`]: core::cell::RefCell
/// [`Cell`]: core::cell::Cell
/// [`with_hasher`]: Self::with_hasher
/// [`with_capacity_and_hasher`]: Self::with_capacity_and_hasher
///
/// ```
/// use hash_arr_map::{FromIndex, Ham, Idx, IntoIndex};
///
/// #[derive(Hash, Eq, PartialEq, Debug)]
/// struct Item {
/// dollars: u8,
/// cents: u8,
/// }
///
/// impl Item {
/// /// Creates a new Item.
/// fn new(dollars: u8, cents: u8) -> Self {
/// Self { dollars, cents }
/// }
/// }
///
/// impl IntoIndex for Item {
/// fn into_index(&self) -> Option<Idx<Self>> {
/// unsafe { Idx::from_usize(((self.cents as usize) << 8) + self.dollars as usize) }
/// }
/// }
///
/// impl FromIndex for Item {
/// fn from_index(idx: Idx<Self>) -> Self {
/// Self {
/// dollars: idx.get().get() as u8,
/// cents: (idx.get().get() >> 8) as u8,
/// }
/// }
/// }
///
/// // Use a HashMap to store the item's quantity.
/// let mut items = Ham::new();
///
/// items.insert(Item::new(10, 0), 25);
/// items.insert(Item::new(5, 50), 24);
/// items.insert(Item::new(7, 75), 12);
///
/// let total: usize = items
/// .iter()
/// .map(|(item, qty)| {
/// let dollars: usize = item.dollars as usize;
/// let cents: usize = item.cents as usize;
/// (dollars * 100 + cents) * qty // In cents
/// })
/// .sum();
/// println!("Total is {}c", total);
///
/// // Use derived implementation to print the status of the items.
/// for (item, qty) in &items {
/// println!("{:?} has {} quantity", item, qty);
/// }
/// ```
///
/// A `HashMap` with fixed list of elements can be initialized from an array:
///
/// ```
/// use std::borrow::Cow;
///
/// use hash_arr_map::Ham;
///
/// let timber_resources: Ham<Cow<str>, u32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)]
/// .iter()
/// .copied()
/// .map(|(k, v)| (Cow::Borrowed(k), v))
/// .collect();
/// // use the values stored in map
/// ```
///
/// References cannot be used as keys, as they cannot be easily converted to
/// indexes and back:
///
/// ```rust,compile_fail
/// use hash_arr_map::Ham;
///
/// // This is inferred as `Ham<&str, i32>`.
/// let mut h = Ham::new();
///
/// h.insert("test", 101);
/// ```
#[derive(Clone)]
pub struct Ham<K, V> {
array: Vec<Option<V>>,
hash: Vec<Node<K, V>>,
// How many values are currently stored
len: usize,
// The last free node in the hash part.
last_free: usize,
// To build the hasher that is used to hash keys.
hash_builder: LuaBuildHasher,
}
#[cfg(feature = "imm_gc")]
unsafe impl<K: imm_gc::Trace, V: imm_gc::Trace> imm_gc::Trace for Ham<K, V> {
imm_gc::unsafe_field_trace! {
array: Vec<Option<V>>,
hash: Vec<Node<K, V>>,
}
}
#[cfg(feature = "bacon_rajan_cc")]
impl<K: bacon_rajan_cc::Trace, V: bacon_rajan_cc::Trace> bacon_rajan_cc::Trace for Ham<K, V> {
fn trace(&self, t: &mut bacon_rajan_cc::Tracer) {
self.array.trace(t);
self.hash.trace(t);
}
}
impl<K: FromIndex + fmt::Debug, V: fmt::Debug> fmt::Debug for Ham<K, V> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
#[cfg(feature = "std")]
impl<K, V> Default for Ham<K, V> {
fn default() -> Self {
Self::new()
}
}
#[cfg(feature = "std")]
impl<K, V> Ham<K, V> {
/// Creates a new `Ham`.
#[must_use]
pub fn new() -> Self {
Self {
array: Vec::new(),
len: 0,
hash: Vec::new(),
last_free: 0,
hash_builder: LuaBuildHasher::new(),
}
}
/// Creates a new `Ham` with a specific capacity.
#[must_use]
pub fn with_capacity(array_part: usize, hash_part: usize) -> Self {
let mut array = Vec::with_capacity(array_part);
array.resize_with(array_part, Option::default);
// Round up to the next power of two.
let hash_part = round_pow_2(hash_part);
let mut hash = Vec::with_capacity(hash_part);
hash.resize_with(hash_part, Node::default);
Self {
array,
len: 0,
hash,
last_free: hash_part,
hash_builder: LuaBuildHasher::new(),
}
}
}
impl<K, V> Ham<K, V> {
/// Creates a new `Ham` with a specific seed.
#[must_use]
pub const fn with_seed(seed: u64) -> Self {
Self {
array: Vec::new(),
len: 0,
hash: Vec::new(),
last_free: 0,
hash_builder: LuaBuildHasher::with_seed(seed),
}
}
/// Creates a new `Ham` with a specific capacity and a specific seed.
#[must_use]
pub fn with_capacity_and_seed(array_part: usize, hash_part: usize, seed: u64) -> Self {
let mut array = Vec::with_capacity(array_part);
array.resize_with(array_part, Option::default);
let hash_part = round_pow_2(hash_part);
let mut hash = Vec::with_capacity(hash_part);
hash.resize_with(hash_part, Node::default);
Self {
array,
len: 0,
hash,
last_free: hash_part,
hash_builder: LuaBuildHasher::with_seed(seed),
}
}
/// How many elements the `Ham` has eaten.
#[must_use]
pub const fn len(&self) -> usize {
self.len
}
#[must_use]
pub const fn is_empty(&self) -> bool {
self.len == 0
}
/// Returns the number of elements in both sections the `Ham` can eat
/// without having to allocate.
#[must_use]
pub fn capacity(&self) -> (usize, usize) {
(self.array.len(), self.hash.len())
}
/// Empties the `Ham`.
pub fn clear(&mut self) {
self.len = 0;
for item in &mut self.array {
*item = None;
}
for item in &mut self.hash {
item.take();
item.next = 0;
}
self.last_free = self.hash.len();
}
/// Whether `key` would be stored in the array part.
///
/// Note: This method may be incorrect for some values once they are
/// inserted
///
/// > Example:
/// >
/// > Initial layout:
/// > ```text
/// > array_part: [0, 1, 2],
/// > hash_part: {5}
/// > ```
/// >
/// > `is_in_array(4)` would return false, likewise `is_in_array(3)`.
/// >
/// > If `4` or `3` were now inserted, the layout would then likely be
/// > ```text
/// > array_part: [0, 1, 2, _, 4, 5], // _ is none
/// > hash_part: {}
/// > ```
/// > where 3 and 4 are now in the array.
#[must_use]
pub fn is_in_array<Q: ?Sized + IntoIndex>(&self, key: &Q) -> bool {
self.get_array(key).is_some()
}
#[must_use]
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
if let Some(v) = self.get_array(key) {
v.as_ref()
} else {
self.get_hash(key)
.and_then(|v| v.value().as_ref().map(|p| &p.1))
}
}
#[must_use]
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
self.get(key).is_some()
}
#[must_use]
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
if let Some(idx) = self.get_array_idx_only(key) {
// To get it past the borrow checker...
unsafe { self.array.get_unchecked_mut(idx) }.as_mut()
} else {
self.get_hash_mut(key)
.and_then(|v| v.value_mut().as_mut().map(|p| &mut p.1))
}
}
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
let v = self
.get_array_take(key)
.or_else(|| self.get_hash_take(key).map(|v| v.1));
if v.is_some() {
self.len -= 1;
}
v
}
}
impl<K: FromIndex, V> Ham<K, V> {
pub fn iter(&self) -> Iter<'_, K, V> {
Iter {
array: self.array.iter().enumerate(),
hash: self.hash.iter(),
len: self.len,
}
}
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
IterMut {
array: self.array.iter_mut().enumerate(),
hash: self.hash.iter_mut(),
len: self.len,
}
}
pub fn keys(&self) -> Keys<'_, K, V> {
Keys { inner: self.iter() }
}
pub fn values(&self) -> Values<'_, K, V> {
Values {
array: self.array.iter(),
hash: self.hash.iter(),
len: self.len,
}
}
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
ValuesMut {
array: self.array.iter_mut(),
hash: self.hash.iter_mut(),
len: self.len,
}
}
}
impl<K: FromIndex + Hash + Eq, V> Ham<K, V> {
#[must_use]
pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(Key<'_, K>, &V)>
where
K: Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
if let Some((idx, v)) = self.get_array_idx(key) {
v.as_ref()
.map(|v| (Key::Owned(idx.cast_safe().into_value()), v))
} else {
self.get_hash(key)
.and_then(|v| v.value().as_ref().map(|(k, v)| (Key::Borrowed(k), v)))
}
}
/// Removes a key from the map, returning the stored key and value if the
/// key was previously in the map.
///
/// The key may be any borrowed form of the map's key type, but Hash and Eq
/// on the borrowed form must match those for the key type.
///
/// # Examples
///
/// ```rust
/// use hash_arr_map::Ham;
///
/// let mut map = Ham::new();
/// map.insert(1, "a");
/// assert_eq!(map.remove_entry(&1), Some((1, "a")));
/// assert_eq!(map.remove(&1), None);
/// ```
#[must_use]
pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
let v = if let Some((idx, v)) = self.get_array_idx_mut(key) {
v.take().map(|v| (idx.cast_safe().into_value(), v))
} else {
self.get_hash_take(key)
};
if v.is_some() {
self.len -= 1;
}
v
}
}
impl<K: NewIndex + Hash + Eq, V> Ham<K, V> {
/// This function finds a boundary in the `table`, such that `table.get(n)`
/// is `Some(_)`, and `table.get(n + 1)` is `None`.
pub fn get_n(&self) -> Option<usize> {
// Binary search for a border. Entry at max must be empty, min must be 0
// or entry at min must be non-empty.
fn binary_search(
mut min: usize,
mut max: usize,
is_empty: impl Fn(usize) -> Option<bool>,
) -> Option<usize> {
while max - min > 1 {
let mid = min + (max - min) / 2;
if is_empty(mid)? {
max = mid;
} else {
min = mid;
}
}
Some(min)
}
let array_len = self.array.len();
if let Some(&None) = self.array.last() {
// It ends with a none, meaning that there is a border inside
binary_search(0, array_len, |i| Some(self.array[i].is_none()))
} else if self.array.is_empty() {
None
} else if self.hash.is_empty() {
// If there is no border in the array and no hash, the end of the
// array is the border.
Some(array_len)
} else {
// Otherwise, we check the hash part.
// First we find a None value as the max for a binary search.
let min = array_len;
let mut max = array_len + 1;
while self
.get_hash(&Idx::try_new_usize(max)?.into_value())
.is_some()
{
if max == usize::MAX {
return Some(usize::MAX);
}
max = max.saturating_mul(2);
}
binary_search(min, max, |i| {
Some(
self.get_hash(&Idx::try_new_usize(i)?.into_value())
.is_some(),
)
})
}
}
}
impl<K: IntoIndex + FromIndex + Hash + Eq, V> Ham<K, V> {
/// Gets the given key’s corresponding entry in the map for in-place manipulation.
///
/// # Examples
///
/// ```rust
/// use hash_arr_map::Ham;
///
/// let mut letters = Ham::new();
///
/// for ch in "a short treatise on fungi".chars() {
/// let counter = letters.entry(ch).or_insert(0);
/// *counter += 1;
/// }
///
/// assert_eq!(letters[&'s'], 2);
/// assert_eq!(letters[&'t'], 3);
/// assert_eq!(letters[&'u'], 1);
/// assert_eq!(letters.get(&'y'), None);
/// ```
#[must_use]
pub fn entry(&mut self, k: K) -> Entry<'_, K, V> {
Entry::make_new(self, k) // Private helper
}
/// Feed the `Ham` with a key-value pair.
///
/// If the map did not have this key present, [`None`] is returned.
///
/// If the map did have this key present, the value is updated, and the old
/// value is returned.
///
/// # Examples
///
/// ```
/// use hash_arr_map::Ham;
///
/// let mut map = Ham::new();
/// assert_eq!(map.insert(37, "a"), None);
/// assert_eq!(map.is_empty(), false);
///
/// map.insert(37, "b");
/// assert_eq!(map.insert(37, "c"), Some("b"));
/// assert_eq!(map[&37], "c");
/// ```
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if let Some(slot) = self.get_array_mut(&key) {
let v = mem::replace(slot, Some(value));
if v.is_none() {
self.len += 1;
}
v
} else if let Some(node) = self.get_hash_mut(&key) {
if let Some((_, ref mut v)) = *node.value_mut() {
Some(mem::replace(v, value))
} else {
*node.value_mut() = Some((key, value));
self.len += 1;
None
}
} else {
self.new_key(key, value);
None
}
}
/// Shrinks the capacity of the map as much as possible.
///
/// Both the hash part and the array part will be at least half full.
///
/// Note that this does not mean there will not be extra capacity. Due to
/// internal requirements, the length of the array part and the length of
/// the hash part are required to be powers of two.
pub fn shrink_to_fit(&mut self) {
self.do_rehash(None, true);
}
/// Rehashes the whole table, meaning that some entries might get moved to
/// the array part, or vice-versa.
pub fn force_rehash(&mut self) {
self.do_rehash(None, false);
}
}
impl<K: IntoIndex + FromIndex + Hash + Eq, V> Ham<K, V> {
fn insert_and_get_mut(&mut self, key: K, value: V) -> &mut V {
if let Some(idx) = self.get_array_idx_only(&key) {
// To get it past the borrow checker...
let slot = &mut self.array[idx];
if slot.is_none() {
self.len += 1;
}
slot.insert(value)
} else if let Some(idx) = self.get_hash_idx_only(&key) {
// To get it past the borrow checker...
let node = &mut self.hash[idx];
let entry = node.value_mut().take();
if entry.is_none() {
self.len += 1;
}
let key = if let Some((key, _)) = entry { key } else { key };
&mut node.value_mut().insert((key, value)).1
} else {
self.new_key(key, value)
}
}
// @@@ @@ @@@@@@ @@ @@ @@ @@ @@@@@@ @@ @@
// @@@@ @@ @@ @@ @@ @@ @@ @@ @@ @@
// @@ @@ @@ @@@@ @@ @@ @@ @@@@ @@@@ @@ @@
// @@ @@@@ @@ @@ @@ @@ @@ @@ @@ @@
// @@ @@@ @@@@@@ @@ @@ @@ @@ @@@@@@ @@
/// This function shouldn't be called if `key` can fit in the array part.
fn new_key(&mut self, key: K, value: V) -> &mut V {
if self.hash.is_empty() {
self.do_rehash(Some(&key), false);
return self.insert_and_get_mut(key, value);
}
// A cell is used so that we can have multiple pointers without borrow conflicts.
let main_pos = Self::main_position_cell(self as *mut _, &key);
let mut emplaced = main_pos;
if let Some((ref colliding_key, _)) = *unsafe { &*main_pos.as_ptr() }.value() {
if let Some(free) = Self::get_free_pos_cell(self as *mut _) {
// Make sure that free isn't already part of a chain, otherwise it
// would be broken.
// E.g:
//
// main_pos -> mp_next -> ...; free -> other -> ...
//
// Turns into
//
// main_pos -> free -> mp_next -> ...; !! -> other -> ...
debug_assert_eq!(Node::next(free) as *const _, free as *const _);
let mut other_main_pos = Self::main_position_cell(self as *mut _, colliding_key);
if main_pos as *const _ != other_main_pos {
// Colliding node is out of its main position
// We move the colliding node into the free position
// then remove the main_pos from the chain.
// omp -> ... -> main_pos -> next -> ...
// We find the node that points to main_pos
while main_pos as *const _ != Node::next(other_main_pos) {
// debug_assert_ne!((&mut *other_main_pos).next_mut(), other_main_pos);
other_main_pos = Node::next(other_main_pos);
}
// omp -> main_pos -> next -> ...
Node::set_next(other_main_pos, free);
// omp -> free; main_pos -> next -> ...
let next = Node::next(main_pos);
free.set(main_pos.replace(Node {
inner: Some((key, value)),
next: 0,
}));
if next as *const _ != main_pos {
Node::set_next(free, next);
}
// omp -> ... -> free -> next -> ...; main_pos
} else {
// Colliding node is in its main position
// New node goes into the free position and
// the chain is updated.
// main_pos -> mp_next -> ...; free
if Node::next(main_pos) as *const _ != main_pos {
Node::set_next(free, Node::next(main_pos));
}
Node::set_next(main_pos, free);
*unsafe { &mut *free.as_ptr() }.value_mut() = Some((key, value));
// main_pos -> free -> mp_next -> ...
emplaced = free;
}
} else {
// If there isn't a free place, we rehash, then go through inserting normally.
self.do_rehash(Some(&key), false);
return self.insert_and_get_mut(key, value);
}
} else {
// Not colliding => just insert
*unsafe { &mut *main_pos.as_ptr() }.value_mut() = Some((key, value));
}
self.len += 1;
&mut unsafe {
(&mut *emplaced.as_ptr())
.value_mut()
.as_mut()
.unwrap_unchecked()
}
.1
}
// @@@@ @@@@@@ @@ @@ @@ @@@@@@ @@ @@
// @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
// @@@@ @@@@ @@@@@@ @@@@@@ @@@@@@ @@@@@@
// @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
// @@ @@ @@@@@@ @@ @@ @@ @@ @@@@@@ @@ @@
fn count_int(key: &K, nums: &mut Nums) -> bool {
key.into_index()
.map(|v| nums[ceil_log_2(v.get())] += 1)
.is_some()
}
// The number of items that can be in an array that are in the hash part.
//
// returns (total_items, array_items)
fn num_use_hash(&self, nums: &mut Nums) -> (usize, usize) {
let mut total = 0;
let mut a_use = 0;
for v in &self.hash {
if let Some((key, _)) = v.value().as_ref() {
if Self::count_int(key, nums) {
a_use += 1;
}
total += 1;
}
}
(total, a_use)
}
fn num_use_array(&self, nums: &mut Nums) -> usize {
let mut a_use: usize = 0; // summation of nums
let mut i = 0; // Current index
for (lg, num) in nums.iter_mut().enumerate() {
let ttlg = 1 << lg;
let limit = core::cmp::min(ttlg, self.array.len());
if i >= limit {
break;
}
// count elements in range (2 ^ (lg - 1), 2 ^ lg)
let count = self.array[i..limit]
.iter()
.filter_map(Option::as_ref)
.count();
i = limit;
*num += count;
a_use += count;
}
a_use
}
fn do_rehash(&mut self, key: Option<&K>, shrink: bool) {
let mut nums: Nums = [0; NUMS_LEN];
let mut na = self.num_use_array(&mut nums);
let mut total_use = na;
{
let (total_add, na_add) = self.num_use_hash(&mut nums);
total_use += total_add;
na += na_add;
}
if let Some(key) = key {
if Self::count_int(key, &mut nums) {
na += 1;
}
total_use += 1;
}
let (asize, na) = compute_sizes(&nums, na);
// pna is the total number of integer keys in the table.
// nums is an array of keys in sections of 2^i
// return is (new_arr_size, num_keys_in_arr)
fn compute_sizes(nums: &Nums, pna: usize) -> (usize, usize) {
let mut a = 0; // no. of elements < 2^i
let mut na = 0; // no. of elements to go to array part
let mut optimal = 0; // optimal size for array part.
// loop while keys can fill more than half of total size
for (two_to_i, num) in nums
.iter()
.copied()
.enumerate()
.map(|(i, num)| (1 << i, num))
{
if pna <= two_to_i / 2 {
break;
}
a += num;
// more than half elements present?
if a > two_to_i / 2 {
optimal = two_to_i; // optimal size (till now)
na = a; // all elements up to optimal will go in array part
}
}
debug_assert!(
(optimal == 0 || optimal / 2 < na) && na <= optimal,
"optimal = {optimal}; na = {na}",
optimal = optimal,
na = na,
);
(optimal, na)
}
self.resize(asize, total_use - na, shrink);
}
// @@@@ @@@@@@ @@@@@@ @@@@@@ @@@@@@ @@@@@@
// @@ @@ @@ @@ @@ @@ @@
// @@@@ @@@@ @@@@@@ @@ @@ @@@@
// @@ @@ @@ @@ @@ @@ @@
// @@ @@ @@@@@@ @@@@@@ @@@@@@ @@@@@@ @@@@@@
fn resize(&mut self, array_part: usize, hash_part: usize, shrink: bool) {
// Make sure we don't break the invariant
let mut hash_part = round_pow_2(hash_part);
let old_hash = mem::replace(&mut self.hash, {
let mut v = Vec::with_capacity(hash_part);
let c = round_down_pow_2(v.capacity());
if c > hash_part {
// Use any excess capacity
hash_part = c;
}
v.resize_with(hash_part, Node::default);
v
});
let hash_part = hash_part; // Make immut
self.last_free = hash_part;
let mut array_part = array_part;
let array_grew = if array_part > self.array.len() {
self.array.resize_with(array_part, Option::default);
let c = round_down_pow_2(self.array.capacity());
if c > array_part {
// Use any excess capacity
array_part = c;
self.array.resize_with(array_part, Option::default);
}
true
} else {
false
};
let array_part = array_part;
let len = self.len;
if array_part < self.array.len() {
// We replace the arrays so that the borrow checker doesn't complain
// when we insert new keys below.
let mut array = mem::take(&mut self.array);
for (i, item) in array.drain(array_part..).enumerate() {
if let Some(item) = item {
self.new_key(
K::from_index(unsafe { Idx::new_unchecked(array_part + i + 1) }),
item,
); // Insert into the hash part.
}
}
if shrink {
array.shrink_to_fit();
}
self.array = array;
}
for node in old_hash {
if let Some((k, v)) = node.into_inner() {
if array_grew {
// Insert into the new table.
// This could go into the array, so we use self.insert
self.insert(k, v);
} else {
// Insert into the new hash part.
self.new_key(k, v);
}
}
}
self.len = len; // Fix up the length
}
}
impl<K, V> Ham<K, V> {
// @@@@@@ @@@@@@ @@@@@@ @@@@@@ @@@@@@ @@@@ @@@@@@
// @@ @@ @@ @@ @@ @@ @@ @@
// @@ @@@ @@@@ @@ @@ @@@@ @@@@ @@@@@@
// @@ @@ @@ @@ @@ @@ @@ @@ @@
// @@@@@@ @@@@@@ @@ @@ @@@@@@ @@ @@ @@@@@@
fn get_array_idx_only<Q: ?Sized + IntoIndex>(&self, key: &Q) -> Option<usize> {
let v = key.into_index()?.get().get() - 1;
self.array.get(v).map(|_| v)
}
fn get_array_idx<Q: ?Sized + IntoIndex>(&self, key: &Q) -> Option<(Idx<Q>, &Option<V>)> {
key.into_index()
.and_then(|v| Some((v.clone(), self.array.get(v.get().get() - 1)?)))
}
fn get_array_idx_mut<Q: ?Sized + IntoIndex>(
&mut self,
key: &Q,
) -> Option<(Idx<Q>, &mut Option<V>)> {
key.into_index()
.and_then(move |v| Some((v.clone(), self.array.get_mut(v.get().get() - 1)?)))
}
fn get_array<Q: ?Sized + IntoIndex>(&self, key: &Q) -> Option<&Option<V>> {
key.into_index()
.and_then(|v| self.array.get(v.get().get() - 1))
}
fn get_array_mut<Q: ?Sized + IntoIndex>(&mut self, key: &Q) -> Option<&mut Option<V>> {
key.into_index()
.and_then(move |v| self.array.get_mut(v.get().get() - 1))
}
fn get_array_take<Q: ?Sized + IntoIndex>(&mut self, key: &Q) -> Option<V> {
self.get_array_mut(key).and_then(Option::take)
}
fn get_hash_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut Node<K, V>>
where
Q: Hash + Eq,
K: Borrow<Q>,
{
if self.hash.is_empty() {
None
} else {
let mut v = Self::main_position_cell(self as *mut _, key);
while !Node::matches(v, key) {
let new_v = Node::next(v);
if new_v as *const _ == v {
return None; // There wasn't a chain.
}
v = new_v;
}
Some(unsafe { &mut *v.as_ptr() })
}
}
fn get_hash_mut_for_take<Q: ?Sized>(&mut self, key: &Q) -> Option<(&mut Node<K, V>, bool)>
where
Q: Hash + Eq,
K: Borrow<Q>,
{
if self.hash.is_empty() {
None
} else {
let mut v = Self::main_position_cell(self as *mut _, key);
let mut prev_v = None;
while !Node::matches(v, key) {
let new_v = Node::next(v);
if new_v as *const _ == v {
return None; // There wasn't a chain.
}
prev_v = Some(v);
v = new_v;
}
Some(if let Some(prev) = prev_v {
(unsafe { &mut *prev.as_ptr() }, true)
} else {
(unsafe { &mut *v.as_ptr() }, false)
})
}
}
fn get_hash_take<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
where
Q: Hash + Eq,
K: Borrow<Q>,
{
if self.hash.is_empty() {
None
} else {
let mut v = Self::main_position_cell(self as *mut _, key);
let mut prev_v = None;
// Follow the chain around
while !Node::matches(v, key) {
let new_v = Node::next(v);
if new_v as *const _ == v {
// v -> v -> v ...
return None; // There wasn't a chain.
}
prev_v = Some(v);
v = new_v;
}
let v_next = Node::next(v);
{
#[allow(clippy::cast_sign_loss)]
let num = unsafe { v.as_ptr().offset_from(self.hash.as_ptr()) } as usize;
if num > self.last_free {
self.last_free = num;
}
}
let out = if let Some(prev_v) = prev_v {
if v_next as *const _ == v {
// prev_v -> v
Node::set_next(prev_v, prev_v);
// prev_v; v
} else {
// prev_v -> v -> v_next -> ...
Node::set_next(prev_v, v_next);
// prev_v -> v_next -> ...; v -> v_next -> ...
}
unsafe { &mut *v.as_ptr() }.value_mut().take()
} else if v_next as *const _ != v {
// INVARIANT: All the keys in the chain hash to `v`
// v -> v_next -> v_next_next -> ...
// We move v_next into v and return the value of v
let v_next_next = Node::next(v_next);
let v_next_value = v_next.replace(Node::default());
let v_value = v.replace(v_next_value);
// We now fix the pointer in v_next_value
// If there was something after v_next, then set it
if v_next_next as *const _ != v_next {
Node::set_next(v, v_next_next);
}
// v_next (in *v) -> v_next_next -> ...
v_value.into_inner()
} else {
// v doesn't point to anything.
unsafe { &mut *v.as_ptr() }.value_mut().take()
};
Node::set_next(v, v);
out
}
}
fn get_hash<Q: ?Sized>(&self, key: &Q) -> Option<&Node<K, V>>
where
Q: Hash + Eq,
K: Borrow<Q>,
{
if self.hash.is_empty() {
None
} else {
let mut v = self.main_position(key);
while !v.matches_ref(key) {
let new_v = v.next_ref();
if new_v as *const _ == v {
return None; // There wasn't a chain.
}
v = new_v;
}
Some(v)
}
}
fn get_hash_idx_only<Q: ?Sized>(&self, key: &Q) -> Option<usize>
where
Q: Hash + Eq,
K: Borrow<Q>,
{
self.get_hash_idx(key).map(|v| v.0)
}
fn get_hash_idx<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &Node<K, V>)>
where
Q: Hash + Eq,
K: Borrow<Q>,
{
if self.hash.is_empty() {
None
} else {
let mut v = self.main_position(key);
while !v.matches_ref(key) {
let new_v = v.next_ref();
if new_v as *const _ == v {
return None; // There wasn't a chain.
}
v = new_v;
}
#[allow(clippy::cast_sign_loss)]
Some((
unsafe { (v as *const Node<K, V>).offset_from(self.hash.as_ptr()) } as usize,
v,
))
}
}
// @@ @@ @@ @@@@@@ @@@ @@ @@@@ @@@@@@ @@@@@@
// @@@@ @@@@ @@ @@ @@ @@@@ @@ @@ @@ @@ @@ @@
// @@ @@ @@ @@@@@@ @@ @@ @@ @@ @@@@ @@ @@ @@@@@@
// @@ @@ @@ @@ @@ @@ @@@@ @@ @@ @@ @@
// @@ @@ @@ @@ @@@@@@ @@ @@@ @@ @@@@@@ @@@@@@
/// Returns a reference to the position of a key in the table
fn main_position<Q: ?Sized + Hash>(&self, key: &Q) -> &Node<K, V> {
let mut hasher = self.hash_builder.build_hasher();
key.hash(&mut hasher);
debug_assert!(self.hash.len().is_power_of_two());
let idx = (hasher.finish() as usize) % self.hash.len();
&self.hash[idx]
}
/// Returns a reference to the position of a key in the table
fn main_position_cell<'a, Q: ?Sized + Hash>(this: *mut Self, key: &Q) -> &'a Cell<Node<K, V>> {
let mut hasher = unsafe { (*this).hash_builder }.build_hasher();
key.hash(&mut hasher);
// debug_assert!(self.hash.len().is_power_of_two());
let h = unsafe { &mut (*this).hash };
let idx = (hasher.finish() as usize) % h.len();
// Don't make any references into the buffer
// SAFETY: idx < self.hash.len()
unsafe { &*h.as_mut_ptr().add(idx).cast::<Cell<Node<K, V>>>() }
}
fn get_free_pos_cell<'a>(this: *mut Self) -> Option<&'a Cell<Node<K, V>>> {
// self.last_free = self.hash.len();
for i in (0..unsafe { (*this).last_free }).rev() {
// Don't make any references into the buffer
// SAFETY: idx < self.hash.len()
let node = unsafe { &*(*this).hash.as_mut_ptr().add(i).cast::<Cell<Node<K, V>>>() };
if unsafe { &*node.as_ptr() }.value().is_none() {
unsafe {
(*this).last_free = i;
} // It is actually last free + 1
return Some(node);
}
}
None
}
}
impl<K, Q: ?Sized, V> Index<&Q> for Ham<K, V>
where
K: Hash + Eq + Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
type Output = V;
fn index(&self, key: &Q) -> &V {
self.get(key).expect("no entry found for key")
}
}
impl<K, Q: ?Sized, V> IndexMut<&Q> for Ham<K, V>
where
K: Hash + Eq + Borrow<Q>,
Q: IntoIndex + Hash + Eq,
{
fn index_mut(&mut self, key: &Q) -> &mut V {
self.get_mut(key).expect("no entry found for key")
}
}
#[cfg(feature = "std")]
impl<K, V> FromIterator<(K, V)> for Ham<K, V>
where
K: IntoIndex + FromIndex + Hash + Eq,
{
fn from_iter<I>(iter: I) -> Self
where
I: IntoIterator<Item = (K, V)>,
{
let mut map = Self::new();
map.extend(iter);
map
}
}
impl<K, V> Extend<(K, V)> for Ham<K, V>
where
K: IntoIndex + FromIndex + Hash + Eq,
{
fn extend<I>(&mut self, iter: I)
where
I: IntoIterator<Item = (K, V)>,
{
for (k, v) in iter {
self.insert(k, v);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
const SIZE: usize = 1000;
#[test]
fn test_insert() {
let mut hash_map = Ham::with_seed(0);
for i in 0..SIZE {
hash_map.insert(i, i);
}
}
#[test]
fn test_insert_remove() {
let mut hash_map = Ham::with_seed(0);
for i in 0..SIZE {
hash_map.insert(i, i);
}
for i in 0..SIZE {
hash_map.insert(i + SIZE, i);
hash_map.remove(&i);
hash_map.shrink_to_fit();
}
}
#[test]
fn test_insert_remove_2() {
let mut hash_map = Ham::with_seed(0);
for i in 0..100 {
hash_map.insert(i, i);
}
for i in 0..100 {
hash_map.insert(i + 100, i);
hash_map.remove(&i);
}
}
}