mod detach_range;
mod detached_entry_mut;
mod entry_mut;
mod entry_ref;
mod extract_range;
mod index_state;
mod internal;
mod owned_entry;
mod try_insert_error;
use std::borrow::Borrow;
use std::collections::hash_map::RandomState;
use std::fmt;
use std::hash::BuildHasher;
use std::hash::Hash;
use std::ops::Bound;
use std::ops::RangeBounds;
pub use self::detach_range::DetachRange;
pub use self::detached_entry_mut::DetachedEntryMut;
pub use self::entry_mut::EntryMut;
pub use self::entry_ref::EntryRef;
pub use self::extract_range::ExtractRange;
pub use self::index_state::IndexState;
use self::internal::InternalState;
use self::internal::Record;
use self::internal::Sequence;
use self::internal::SlotId;
pub use self::owned_entry::OwnedEntry;
pub use self::try_insert_error::TryInsertError;
type SequenceBounds<O> = (Bound<(O, Sequence)>, Bound<(O, Sequence)>);
#[must_use = "the map owns its records and ordered index"]
pub struct OrderedIndexMap<K, O, V, S = RandomState> {
state: InternalState<K, O, V>,
hash_builder: S,
poisoned: bool,
}
impl<K, O, V> OrderedIndexMap<K, O, V, RandomState> {
#[inline]
pub fn new() -> Self {
Self::with_hasher(RandomState::new())
}
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, RandomState::new())
}
}
impl<K, O, V, S> OrderedIndexMap<K, O, V, S> {
#[inline]
pub const fn with_hasher(hash_builder: S) -> Self {
Self {
state: InternalState::new(),
hash_builder,
poisoned: false,
}
}
#[inline]
pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
Self {
state: InternalState::with_capacity(capacity),
hash_builder,
poisoned: false,
}
}
#[must_use]
#[inline]
pub fn len(&self) -> usize {
self.assert_healthy();
self.state.arena.len()
}
#[must_use]
#[inline]
pub fn is_empty(&self) -> bool {
self.assert_healthy();
self.state.arena.len() == 0
}
#[must_use]
#[inline]
pub fn attached_len(&self) -> usize {
self.assert_healthy();
self.state.ordered.len()
}
#[must_use]
#[inline]
pub fn is_attached_empty(&self) -> bool {
self.assert_healthy();
self.state.ordered.is_empty()
}
#[must_use]
#[inline]
pub fn capacity(&self) -> usize {
self.assert_healthy();
self.state.arena.capacity().min(self.state.primary.capacity())
}
#[inline]
pub fn clear(&mut self) {
self.with_mutation(|state, _| {
state.primary.clear();
state.ordered.clear();
state.arena.clear();
state.next_sequence = 0;
});
}
#[inline]
pub fn iter(&self) -> impl Iterator<Item = EntryRef<'_, K, O, V>> {
self.assert_healthy();
self.state.primary.iter().map(|id| self.entry_ref(*id))
}
#[inline]
pub fn iter_ordered(&self) -> impl DoubleEndedIterator<Item = EntryRef<'_, K, O, V>> + ExactSizeIterator {
self.assert_healthy();
self.state.ordered.values().map(|id| self.entry_ref(*id))
}
#[inline]
pub fn values_ordered(&self) -> impl DoubleEndedIterator<Item = &V> + ExactSizeIterator {
self.iter_ordered().map(|entry| entry.value)
}
#[inline]
pub fn first(&self) -> Option<EntryRef<'_, K, O, V>>
where
O: Ord,
{
self.assert_healthy();
let id = *self.state.ordered.first_key_value()?.1;
Some(self.entry_ref(id))
}
#[inline]
pub fn range<R>(&self, range: R) -> impl DoubleEndedIterator<Item = EntryRef<'_, K, O, V>>
where
O: Clone + Ord,
R: RangeBounds<O>,
{
self.assert_healthy();
self.state
.ordered
.range(order_range_bounds(&range))
.map(|(_, id)| self.entry_ref(*id))
}
#[inline]
fn assert_healthy(&self) {
assert!(
!self.poisoned,
"OrderedIndexMap is poisoned after a prior mutation panic",
);
}
#[inline]
fn with_mutation<R>(&mut self, operation: impl FnOnce(&mut InternalState<K, O, V>, &S) -> R) -> R {
self.assert_healthy();
self.poisoned = true;
let result = operation(&mut self.state, &self.hash_builder);
self.poisoned = false;
result
}
#[inline]
fn entry_ref(&self, id: SlotId) -> EntryRef<'_, K, O, V> {
let record = self
.state
.arena
.get(id)
.expect("primary index must reference an occupied arena slot");
EntryRef {
key: &record.key,
order: &record.order,
value: &record.value,
state: record.state(),
}
}
#[inline]
fn entry_mut(&mut self, id: SlotId) -> EntryMut<'_, K, O, V> {
let record = self
.state
.arena
.get_mut(id)
.expect("primary index must reference an occupied arena slot");
let state = record.state();
EntryMut {
key: &record.key,
order: &record.order,
value: &mut record.value,
state,
}
}
#[inline]
fn detached_entry_mut(&mut self, id: SlotId) -> DetachedEntryMut<'_, K, O, V> {
let record = self
.state
.arena
.get_mut(id)
.expect("primary index must reference an occupied arena slot");
assert!(
record.sequence.is_none(),
"detached entry view requires a detached record",
);
DetachedEntryMut {
key: &record.key,
order: &record.order,
value: &mut record.value,
}
}
}
impl<K, O, V, S> OrderedIndexMap<K, O, V, S>
where
S: BuildHasher,
{
#[must_use]
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.find_slot(key).is_some()
}
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
let id = self.find_slot(key)?;
Some(&self.state.arena.get(id)?.value)
}
#[inline]
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
let id = self.find_slot(key)?;
Some(&mut self.state.arena.get_mut(id)?.value)
}
#[inline]
pub fn get_entry<Q>(&self, key: &Q) -> Option<EntryRef<'_, K, O, V>>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.find_slot(key).map(|id| self.entry_ref(id))
}
#[inline]
pub fn get_entry_mut<Q>(&mut self, key: &Q) -> Option<EntryMut<'_, K, O, V>>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
let id = self.find_slot(key)?;
Some(self.entry_mut(id))
}
pub fn reserve(&mut self, additional: usize)
where
K: Hash,
{
self.with_mutation(|state, hash_builder| {
state.arena.reserve(additional);
let arena = &state.arena;
state.primary.reserve(additional, |id| {
hash_builder.hash_one(
&arena
.get(*id)
.expect("primary index must reference an occupied arena slot")
.key,
)
});
});
}
#[inline]
fn find_slot<Q>(&self, key: &Q) -> Option<SlotId>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.assert_healthy();
let hash = self.hash_builder.hash_one(key);
self.state
.primary
.find(hash, |id| {
self.state
.arena
.get(*id)
.is_some_and(|record| record.key.borrow() == key)
})
.copied()
}
}
impl<K, O, V, S> OrderedIndexMap<K, O, V, S>
where
K: Eq + Hash,
O: Ord + Clone,
S: BuildHasher,
{
pub fn insert(&mut self, key: K, order: O, value: V) -> Option<OwnedEntry<K, O, V>> {
self.assert_healthy();
let hash = self.hash_builder.hash_one(&key);
let previous_id = self.find_slot(&key);
let previous_ordered_key = previous_id.and_then(|id| {
let record = self
.state
.arena
.get(id)
.expect("primary index must reference an occupied arena slot");
record.sequence.map(|sequence| (record.order.clone(), sequence))
});
let indexed_order = order.clone();
self.with_mutation(move |state, hash_builder| {
let previous = previous_id.map(|id| {
remove_primary_id(state, hash, id);
if let Some(ordered_key) = previous_ordered_key {
let removed = state.ordered.remove(&ordered_key);
assert_eq!(removed, Some(id), "ordered index must reference replaced slot");
}
owned_from_record(state.arena.remove(id).expect("replaced primary slot must be occupied"))
});
let sequence = state.allocate_sequence();
let id = state.arena.insert(Record {
key,
order,
value,
sequence: Some(sequence),
});
let arena = &state.arena;
state.primary.insert_unique(hash, id, |candidate| {
hash_builder.hash_one(
&arena
.get(*candidate)
.expect("primary index must reference an occupied arena slot")
.key,
)
});
let old = state.ordered.insert((indexed_order, sequence), id);
assert!(old.is_none(), "ordered index sequence must be unique");
previous
})
}
pub fn try_insert(&mut self, key: K, order: O, value: V) -> Result<EntryMut<'_, K, O, V>, TryInsertError<K, O, V>> {
self.assert_healthy();
if self.find_slot(&key).is_some() {
return Err(TryInsertError::new(key, order, value));
}
let hash = self.hash_builder.hash_one(&key);
let indexed_order = order.clone();
let id = self.with_mutation(move |state, hash_builder| {
let sequence = state.allocate_sequence();
let id = state.arena.insert(Record {
key,
order,
value,
sequence: Some(sequence),
});
let arena = &state.arena;
state.primary.insert_unique(hash, id, |candidate| {
hash_builder.hash_one(
&arena
.get(*candidate)
.expect("primary index must reference an occupied arena slot")
.key,
)
});
let previous = state.ordered.insert((indexed_order, sequence), id);
assert!(previous.is_none(), "ordered index sequence must be unique");
id
});
Ok(self.entry_mut(id))
}
pub fn remove<Q>(&mut self, key: &Q) -> Option<OwnedEntry<K, O, V>>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.assert_healthy();
let hash = self.hash_builder.hash_one(key);
let id = self.find_slot(key)?;
let ordered_key = {
let record = self
.state
.arena
.get(id)
.expect("primary index must reference an occupied arena slot");
record.sequence.map(|sequence| (record.order.clone(), sequence))
};
Some(self.remove_slot(hash, id, ordered_key))
}
pub fn detach<Q>(&mut self, key: &Q) -> Option<DetachedEntryMut<'_, K, O, V>>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.assert_healthy();
let id = self.find_slot(key)?;
let ordered_key = {
let record = self
.state
.arena
.get(id)
.expect("primary index must reference an occupied arena slot");
(record.order.clone(), record.sequence?)
};
self.detach_slot(id, ordered_key);
Some(self.detached_entry_mut(id))
}
pub fn attach<Q>(&mut self, key: &Q) -> Option<EntryMut<'_, K, O, V>>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.assert_healthy();
let id = self.find_slot(key)?;
let indexed_order = {
let record = self
.state
.arena
.get(id)
.expect("primary index must reference an occupied arena slot");
if record.sequence.is_some() {
return None;
}
record.order.clone()
};
self.with_mutation(|state, _| {
let sequence = state.allocate_sequence();
let old = state.ordered.insert((indexed_order, sequence), id);
assert!(old.is_none(), "ordered index sequence must be unique");
state
.arena
.get_mut(id)
.expect("attached primary slot must be occupied")
.sequence = Some(sequence);
});
Some(self.entry_mut(id))
}
pub fn set_order<Q>(&mut self, key: &Q, order: O) -> Option<O>
where
K: Borrow<Q>,
Q: Eq + Hash + ?Sized,
{
self.assert_healthy();
let id = self.find_slot(key)?;
let (old_ordered_key, indexed_order) = {
let record = self
.state
.arena
.get(id)
.expect("primary index must reference an occupied arena slot");
(
record.sequence.map(|sequence| (record.order.clone(), sequence)),
record.sequence.map(|_| order.clone()),
)
};
Some(self.with_mutation(|state, _| {
let new_sequence = indexed_order.as_ref().map(|_| state.allocate_sequence());
if let Some(old_key) = old_ordered_key {
let removed = state.ordered.remove(&old_key);
assert_eq!(removed, Some(id), "ordered index must reference reordered slot");
}
if let (Some(indexed_order), Some(sequence)) = (indexed_order, new_sequence) {
let old = state.ordered.insert((indexed_order, sequence), id);
assert!(old.is_none(), "ordered index sequence must be unique");
}
let record = state
.arena
.get_mut(id)
.expect("reordered primary slot must be occupied");
record.sequence = new_sequence;
std::mem::replace(&mut record.order, order)
}))
}
pub fn detach_range<R>(&mut self, range: R) -> DetachRange<'_, K, O, V, S>
where
R: RangeBounds<O>,
{
self.assert_healthy();
DetachRange {
map: self,
bounds: order_range_bounds(&range),
}
}
pub fn extract_range<R>(&mut self, range: R) -> ExtractRange<'_, K, O, V, S>
where
R: RangeBounds<O>,
{
self.assert_healthy();
ExtractRange {
map: self,
bounds: order_range_bounds(&range),
}
}
}
impl<K, O, V, S> OrderedIndexMap<K, O, V, S>
where
K: Hash,
O: Ord,
S: BuildHasher,
{
pub fn pop_first(&mut self) -> Option<OwnedEntry<K, O, V>> {
self.assert_healthy();
let id = *self.state.ordered.first_key_value().map(|(_, id)| id)?;
let hash = {
let record = self
.state
.arena
.get(id)
.expect("ordered index must reference an occupied arena slot");
self.hash_builder.hash_one(&record.key)
};
Some(self.with_mutation(|state, _| {
remove_primary_id(state, hash, id);
let (ordered_key, removed_id) = state
.ordered
.pop_first()
.expect("first ordered slot must remain present");
assert_eq!(removed_id, id, "first ordered slot must match the preflight slot",);
drop(ordered_key);
owned_from_record(state.arena.remove(id).expect("removed primary slot must be occupied"))
}))
}
}
impl<K, O, V, S> OrderedIndexMap<K, O, V, S>
where
O: Ord,
{
fn detach_slot(&mut self, id: SlotId, ordered_key: (O, Sequence)) {
self.with_mutation(|state, _| {
let removed = state.ordered.remove(&ordered_key);
assert_eq!(removed, Some(id), "ordered index must reference detached slot");
state
.arena
.get_mut(id)
.expect("detached primary slot must be occupied")
.sequence = None;
});
}
fn remove_slot(&mut self, hash: u64, id: SlotId, ordered_key: Option<(O, Sequence)>) -> OwnedEntry<K, O, V> {
self.with_mutation(|state, _| {
remove_primary_id(state, hash, id);
if let Some(ordered_key) = ordered_key {
let removed = state.ordered.remove(&ordered_key);
assert_eq!(removed, Some(id), "ordered index must reference removed slot");
}
owned_from_record(state.arena.remove(id).expect("removed primary slot must be occupied"))
})
}
}
impl<K, O, V, S> Default for OrderedIndexMap<K, O, V, S>
where
S: Default,
{
#[inline]
fn default() -> Self {
Self::with_hasher(S::default())
}
}
impl<K, O, V, S> Clone for OrderedIndexMap<K, O, V, S>
where
K: Clone,
O: Clone,
V: Clone,
S: Clone,
{
fn clone(&self) -> Self {
self.assert_healthy();
Self {
state: self.state.clone(),
hash_builder: self.hash_builder.clone(),
poisoned: false,
}
}
}
impl<K, O, V, S> fmt::Debug for OrderedIndexMap<K, O, V, S>
where
K: fmt::Debug,
O: fmt::Debug,
V: fmt::Debug,
S: fmt::Debug,
{
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.assert_healthy();
formatter
.debug_struct("OrderedIndexMap")
.field("state", &self.state)
.field("hash_builder", &self.hash_builder)
.finish()
}
}
fn remove_primary_id<K, O, V>(state: &mut InternalState<K, O, V>, hash: u64, id: SlotId) {
let entry = state
.primary
.find_entry(hash, |candidate| *candidate == id)
.expect("primary index must reference removed slot");
let (removed, _) = entry.remove();
assert_eq!(removed, id, "primary index removed an unexpected slot");
}
fn owned_from_record<K, O, V>(record: Record<K, O, V>) -> OwnedEntry<K, O, V> {
let state = record.state();
OwnedEntry {
key: record.key,
order: record.order,
value: record.value,
state,
}
}
#[must_use]
fn order_range_bounds<O, R>(range: &R) -> SequenceBounds<O>
where
O: Clone + Ord,
R: RangeBounds<O>,
{
assert_valid_order_range(range);
(
match range.start_bound() {
Bound::Included(order) => Bound::Included((order.clone(), Sequence(0))),
Bound::Excluded(order) => Bound::Excluded((order.clone(), Sequence(u64::MAX))),
Bound::Unbounded => Bound::Unbounded,
},
match range.end_bound() {
Bound::Included(order) => Bound::Included((order.clone(), Sequence(u64::MAX))),
Bound::Excluded(order) => Bound::Excluded((order.clone(), Sequence(0))),
Bound::Unbounded => Bound::Unbounded,
},
)
}
fn assert_valid_order_range<O, R>(range: &R)
where
O: Ord,
R: RangeBounds<O>,
{
let (start, start_excluded) = match range.start_bound() {
Bound::Included(order) => (Some(order), false),
Bound::Excluded(order) => (Some(order), true),
Bound::Unbounded => (None, false),
};
let (end, end_excluded) = match range.end_bound() {
Bound::Included(order) => (Some(order), false),
Bound::Excluded(order) => (Some(order), true),
Bound::Unbounded => (None, false),
};
if let (Some(start), Some(end)) = (start, end) {
assert!(start <= end, "range start is greater than range end",);
assert!(
start != end || !(start_excluded && end_excluded),
"range start and end are equal and excluded",
);
}
}