#![allow(unsafe_code)]
use super::{Entry, Equivalent, HashValue, IndexMapCore, VacantEntry};
use hashbrown::raw::RawTable;
use std::fmt;
use std::mem::replace;
type RawBucket = hashbrown::raw::Bucket<usize>;
pub(super) struct DebugIndices<'a>(pub &'a RawTable<usize>);
impl fmt::Debug for DebugIndices<'_> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let indices = unsafe { self.0.iter().map(|raw_bucket| raw_bucket.read()) };
f.debug_list().entries(indices).finish()
}
}
impl<K, V> IndexMapCore<K, V> {
fn find_equivalent<Q>(&self, hash: HashValue, key: &Q) -> Option<RawBucket>
where
Q: ?Sized + Equivalent<K>,
{
self.indices.find(hash.get(), {
move |&i| Q::equivalent(key, &self.entries[i].key)
})
}
fn find_index(&self, hash: HashValue, index: usize) -> Option<RawBucket> {
self.indices.find(hash.get(), move |&i| i == index)
}
pub(crate) fn get_index_of<Q>(&self, hash: HashValue, key: &Q) -> Option<usize>
where
Q: ?Sized + Equivalent<K>,
{
match self.find_equivalent(hash, key) {
Some(raw_bucket) => Some(unsafe { raw_bucket.read() }),
None => None,
}
}
pub(super) fn erase_index(&mut self, hash: HashValue, index: usize) {
let raw_bucket = self.find_index(hash, index).unwrap();
unsafe { self.indices.erase(raw_bucket) };
}
pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<K, V>
where
K: Eq,
{
match self.find_equivalent(hash, &key) {
Some(raw_bucket) => Entry::Occupied(OccupiedEntry {
map: self,
raw_bucket,
key,
}),
None => Entry::Vacant(VacantEntry {
map: self,
hash,
key,
}),
}
}
pub(crate) fn shift_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
where
Q: ?Sized + Equivalent<K>,
{
match self.find_equivalent(hash, key) {
Some(raw_bucket) => unsafe { Some(self.shift_remove_bucket(raw_bucket)) },
None => None,
}
}
pub(crate) fn shift_remove_index(&mut self, index: usize) -> Option<(K, V)> {
let raw_bucket = match self.entries.get(index) {
Some(entry) => self.find_index(entry.hash, index).unwrap(),
None => return None,
};
unsafe {
let (_, key, value) = self.shift_remove_bucket(raw_bucket);
Some((key, value))
}
}
#[allow(unused_unsafe)]
unsafe fn shift_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V) {
let index = unsafe { self.indices.remove(raw_bucket) };
let entry = self.entries.remove(index);
let raw_capacity = self.indices.buckets();
let shifted_entries = &self.entries[index..];
if shifted_entries.len() > raw_capacity / 2 {
unsafe {
for bucket in self.indices.iter() {
let i = bucket.read();
if i > index {
bucket.write(i - 1);
}
}
}
} else {
for (i, entry) in (index + 1..).zip(shifted_entries) {
let shifted_bucket = self.find_index(entry.hash, i).unwrap();
unsafe { shifted_bucket.write(i - 1) };
}
}
(index, entry.key, entry.value)
}
pub(crate) fn swap_remove_full<Q>(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)>
where
Q: ?Sized + Equivalent<K>,
{
match self.find_equivalent(hash, key) {
Some(raw_bucket) => unsafe { Some(self.swap_remove_bucket(raw_bucket)) },
None => None,
}
}
pub(crate) fn swap_remove_index(&mut self, index: usize) -> Option<(K, V)> {
let raw_bucket = match self.entries.get(index) {
Some(entry) => self.find_index(entry.hash, index).unwrap(),
None => return None,
};
unsafe {
let (_, key, value) = self.swap_remove_bucket(raw_bucket);
Some((key, value))
}
}
#[allow(unused_unsafe)]
unsafe fn swap_remove_bucket(&mut self, raw_bucket: RawBucket) -> (usize, K, V) {
let index = unsafe { self.indices.remove(raw_bucket) };
let entry = self.entries.swap_remove(index);
if let Some(entry) = self.entries.get(index) {
let last = self.entries.len();
let swapped_bucket = self.find_index(entry.hash, last).unwrap();
unsafe { swapped_bucket.write(index) };
}
(index, entry.key, entry.value)
}
pub(crate) fn reverse(&mut self) {
self.entries.reverse();
let len = self.entries.len();
unsafe {
for raw_bucket in self.indices.iter() {
let i = raw_bucket.read();
raw_bucket.write(len - i - 1);
}
}
}
}
pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
map: &'a mut IndexMapCore<K, V>,
raw_bucket: RawBucket,
key: K,
}
unsafe impl<K: Sync, V: Sync> Sync for OccupiedEntry<'_, K, V> {}
impl<'a, K, V> OccupiedEntry<'a, K, V> {
pub fn key(&self) -> &K {
&self.key
}
pub fn get(&self) -> &V {
&self.map.entries[self.index()].value
}
pub fn get_mut(&mut self) -> &mut V {
let index = self.index();
&mut self.map.entries[index].value
}
pub(crate) fn replace_key(self) -> K {
let index = self.index();
let old_key = &mut self.map.entries[index].key;
replace(old_key, self.key)
}
#[inline]
pub fn index(&self) -> usize {
unsafe { self.raw_bucket.read() }
}
pub fn into_mut(self) -> &'a mut V {
let index = self.index();
&mut self.map.entries[index].value
}
pub fn swap_remove_entry(self) -> (K, V) {
unsafe {
let (_, key, value) = self.map.swap_remove_bucket(self.raw_bucket);
(key, value)
}
}
pub fn shift_remove_entry(self) -> (K, V) {
unsafe {
let (_, key, value) = self.map.shift_remove_bucket(self.raw_bucket);
(key, value)
}
}
}