mod raw;
#[cfg(not(has_std))]
use std::vec::Vec;
use hashbrown::raw::RawTable;
use std::cmp;
use std::fmt;
use std::mem::replace;
use std::ops::RangeFull;
use std::vec::Drain;
use equivalent::Equivalent;
use util::enumerate;
use {Bucket, Entries, HashValue};
pub(crate) struct IndexMapCore<K, V> {
indices: RawTable<usize>,
entries: Vec<Bucket<K, V>>,
}
#[inline(always)]
fn get_hash<K, V>(entries: &[Bucket<K, V>]) -> impl Fn(&usize) -> u64 + '_ {
move |&i| entries[i].hash.get()
}
impl<K, V> Clone for IndexMapCore<K, V>
where
K: Clone,
V: Clone,
{
fn clone(&self) -> Self {
let indices = self.indices.clone();
let mut entries = Vec::with_capacity(indices.capacity());
entries.clone_from(&self.entries);
IndexMapCore { indices, entries }
}
fn clone_from(&mut self, other: &Self) {
let hasher = get_hash(&other.entries);
self.indices.clone_from_with_hasher(&other.indices, hasher);
if self.entries.capacity() < other.entries.len() {
self.reserve_entries();
}
self.entries.clone_from(&other.entries);
}
}
impl<K, V> fmt::Debug for IndexMapCore<K, V>
where
K: fmt::Debug,
V: fmt::Debug,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct("IndexMapCore")
.field("indices", &raw::DebugIndices(&self.indices))
.field("entries", &self.entries)
.finish()
}
}
impl<K, V> Entries for IndexMapCore<K, V> {
type Entry = Bucket<K, V>;
#[inline]
fn into_entries(self) -> Vec<Self::Entry> {
self.entries
}
#[inline]
fn as_entries(&self) -> &[Self::Entry] {
&self.entries
}
#[inline]
fn as_entries_mut(&mut self) -> &mut [Self::Entry] {
&mut self.entries
}
fn with_entries<F>(&mut self, f: F)
where
F: FnOnce(&mut [Self::Entry]),
{
f(&mut self.entries);
self.rebuild_hash_table();
}
}
impl<K, V> IndexMapCore<K, V> {
#[inline]
pub(crate) fn new() -> Self {
IndexMapCore {
indices: RawTable::new(),
entries: Vec::new(),
}
}
#[inline]
pub(crate) fn with_capacity(n: usize) -> Self {
IndexMapCore {
indices: RawTable::with_capacity(n),
entries: Vec::with_capacity(n),
}
}
#[inline]
pub(crate) fn len(&self) -> usize {
self.indices.len()
}
#[inline]
pub(crate) fn capacity(&self) -> usize {
cmp::min(self.indices.capacity(), self.entries.capacity())
}
pub(crate) fn clear(&mut self) {
self.indices.clear();
self.entries.clear();
}
pub(crate) fn drain(&mut self, range: RangeFull) -> Drain<Bucket<K, V>> {
self.indices.clear();
self.entries.drain(range)
}
pub(crate) fn reserve(&mut self, additional: usize) {
self.indices.reserve(additional, get_hash(&self.entries));
self.reserve_entries();
}
fn reserve_entries(&mut self) {
let additional = self.indices.capacity() - self.entries.len();
self.entries.reserve_exact(additional);
}
pub(crate) fn shrink_to_fit(&mut self) {
self.indices.shrink_to(0, get_hash(&self.entries));
self.entries.shrink_to_fit();
}
pub(crate) fn pop(&mut self) -> Option<(K, V)> {
if let Some(entry) = self.entries.pop() {
let last = self.entries.len();
self.erase_index(entry.hash, last);
Some((entry.key, entry.value))
} else {
None
}
}
fn push(&mut self, hash: HashValue, key: K, value: V) -> usize {
let i = self.entries.len();
self.indices.insert(hash.get(), i, get_hash(&self.entries));
if i == self.entries.capacity() {
self.reserve_entries();
}
self.entries.push(Bucket { hash, key, value });
i
}
pub(crate) fn insert_full(&mut self, hash: HashValue, key: K, value: V) -> (usize, Option<V>)
where
K: Eq,
{
match self.get_index_of(hash, &key) {
Some(i) => (i, Some(replace(&mut self.entries[i].value, value))),
None => (self.push(hash, key, value), None),
}
}
pub(crate) fn retain_in_order<F>(&mut self, mut keep: F)
where
F: FnMut(&mut K, &mut V) -> bool,
{
let len = self.entries.len();
let mut n_deleted = 0;
for i in 0..len {
let will_keep = {
let entry = &mut self.entries[i];
keep(&mut entry.key, &mut entry.value)
};
if !will_keep {
n_deleted += 1;
} else if n_deleted > 0 {
self.entries.swap(i - n_deleted, i);
}
}
if n_deleted > 0 {
self.entries.truncate(len - n_deleted);
self.rebuild_hash_table();
}
}
fn rebuild_hash_table(&mut self) {
self.indices.clear();
debug_assert!(self.indices.capacity() >= self.entries.len());
for (i, entry) in enumerate(&self.entries) {
self.indices.insert_no_grow(entry.hash.get(), i);
}
}
}
pub enum Entry<'a, K: 'a, V: 'a> {
Occupied(OccupiedEntry<'a, K, V>),
Vacant(VacantEntry<'a, K, V>),
}
impl<'a, K, V> Entry<'a, K, V> {
pub fn or_insert(self, default: V) -> &'a mut V {
match self {
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(default),
}
}
pub fn or_insert_with<F>(self, call: F) -> &'a mut V
where
F: FnOnce() -> V,
{
match self {
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(call()),
}
}
pub fn key(&self) -> &K {
match *self {
Entry::Occupied(ref entry) => entry.key(),
Entry::Vacant(ref entry) => entry.key(),
}
}
pub fn index(&self) -> usize {
match *self {
Entry::Occupied(ref entry) => entry.index(),
Entry::Vacant(ref entry) => entry.index(),
}
}
pub fn and_modify<F>(self, f: F) -> Self
where
F: FnOnce(&mut V),
{
match self {
Entry::Occupied(mut o) => {
f(o.get_mut());
Entry::Occupied(o)
}
x => x,
}
}
pub fn or_default(self) -> &'a mut V
where
V: Default,
{
match self {
Entry::Occupied(entry) => entry.into_mut(),
Entry::Vacant(entry) => entry.insert(V::default()),
}
}
}
impl<'a, K: 'a + fmt::Debug, V: 'a + fmt::Debug> fmt::Debug for Entry<'a, K, V> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
Entry::Vacant(ref v) => f.debug_tuple(stringify!(Entry)).field(v).finish(),
Entry::Occupied(ref o) => f.debug_tuple(stringify!(Entry)).field(o).finish(),
}
}
}
pub use self::raw::OccupiedEntry;
impl<'a, K, V> OccupiedEntry<'a, K, V> {
pub fn insert(&mut self, value: V) -> V {
replace(self.get_mut(), value)
}
pub fn remove(self) -> V {
self.swap_remove()
}
pub fn swap_remove(self) -> V {
self.swap_remove_entry().1
}
pub fn shift_remove(self) -> V {
self.shift_remove_entry().1
}
pub fn remove_entry(self) -> (K, V) {
self.swap_remove_entry()
}
}
impl<'a, K: 'a + fmt::Debug, V: 'a + fmt::Debug> fmt::Debug for OccupiedEntry<'a, K, V> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_struct(stringify!(OccupiedEntry))
.field("key", self.key())
.field("value", self.get())
.finish()
}
}
pub struct VacantEntry<'a, K: 'a, V: 'a> {
map: &'a mut IndexMapCore<K, V>,
hash: HashValue,
key: K,
}
impl<'a, K, V> VacantEntry<'a, K, V> {
pub fn key(&self) -> &K {
&self.key
}
pub fn into_key(self) -> K {
self.key
}
pub fn index(&self) -> usize {
self.map.len()
}
pub fn insert(self, value: V) -> &'a mut V {
let i = self.map.push(self.hash, self.key, value);
&mut self.map.entries[i].value
}
}
impl<'a, K: 'a + fmt::Debug, V: 'a> fmt::Debug for VacantEntry<'a, K, V> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_tuple(stringify!(VacantEntry))
.field(self.key())
.finish()
}
}
#[test]
fn assert_send_sync() {
fn assert_send_sync<T: Send + Sync>() {}
assert_send_sync::<IndexMapCore<i32, i32>>();
assert_send_sync::<Entry<i32, i32>>();
}