use super::{OrderedMap, Value};
use rustc_hash::{FxBuildHasher, FxHashMap, FxHashSet, FxHasher};
use std::hash::{BuildHasher, Hash, Hasher};
use std::iter::FusedIterator;
use std::rc::{Rc, Weak};
const MAX_SHAPE_KEYS: usize = 8;
const MAX_POOL_ENTRIES: usize = 4096;
const SCANNED_KEYS: usize = 16;
#[derive(Default)]
pub(crate) struct KeysSeen {
hashes: Option<FxHashSet<u64>>,
}
impl KeysSeen {
pub(crate) fn admits(&mut self, entries: &[(String, Value)], key: &str) -> bool {
if entries.len() < SCANNED_KEYS {
return !entries.iter().any(|(k, _)| k == key);
}
let hash = |k: &str| FxBuildHasher.hash_one(k);
let hashes = self
.hashes
.get_or_insert_with(|| entries.iter().map(|(k, _)| hash(k)).collect());
hashes.insert(hash(key)) || !entries.iter().any(|(k, _)| k == key)
}
}
struct KeyShape {
keys: OrderedMap<()>,
}
#[derive(Clone)]
enum Storage {
Empty,
Owned(Box<OrderedMap<Value>>),
Small(Vec<(String, Value)>),
Shared {
shape: Rc<KeyShape>,
values: Vec<Value>,
},
}
#[derive(Clone)]
pub struct MapEntries {
storage: Storage,
}
impl Default for MapEntries {
fn default() -> Self {
Self::new()
}
}
impl MapEntries {
pub fn new() -> Self {
Self {
storage: Storage::Empty,
}
}
pub(crate) fn building() -> Self {
Self {
storage: Storage::Small(Vec::new()),
}
}
pub fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, FxBuildHasher)
}
pub fn with_capacity_and_hasher(capacity: usize, hasher: FxBuildHasher) -> Self {
Self::from(OrderedMap::with_capacity_and_hasher(capacity, hasher))
}
pub fn len(&self) -> usize {
match &self.storage {
Storage::Empty => 0,
Storage::Owned(entries) => entries.len(),
Storage::Small(entries) => entries.len(),
Storage::Shared { values, .. } => values.len(),
}
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn capacity(&self) -> usize {
match &self.storage {
Storage::Empty => 0,
Storage::Owned(entries) => entries.capacity(),
Storage::Small(entries) => entries.capacity(),
Storage::Shared { values, .. } => values.capacity(),
}
}
pub fn is_shared(&self) -> bool {
matches!(self.storage, Storage::Shared { .. })
}
pub fn get(&self, key: &str) -> Option<&Value> {
match &self.storage {
Storage::Empty => None,
Storage::Owned(entries) => entries.get(key),
Storage::Small(entries) => entries.iter().find(|(k, _)| k == key).map(|(_, v)| v),
Storage::Shared { shape, values } => {
shape.keys.get_index_of(key).map(|index| &values[index])
}
}
}
pub fn contains_key(&self, key: &str) -> bool {
self.get_index_of(key).is_some()
}
pub fn get_index_of(&self, key: &str) -> Option<usize> {
match &self.storage {
Storage::Empty => None,
Storage::Owned(entries) => entries.get_index_of(key),
Storage::Small(entries) => entries.iter().position(|(k, _)| k == key),
Storage::Shared { shape, .. } => shape.keys.get_index_of(key),
}
}
pub fn get_index(&self, index: usize) -> Option<(&String, &Value)> {
match &self.storage {
Storage::Empty => None,
Storage::Owned(entries) => entries.get_index(index),
Storage::Small(entries) => entries.get(index).map(|(k, v)| (k, v)),
Storage::Shared { shape, values } => shape
.keys
.get_index(index)
.map(|(key, ())| (key, &values[index])),
}
}
pub fn get_mut(&mut self, key: &str) -> Option<&mut Value> {
match &mut self.storage {
Storage::Empty => None,
Storage::Owned(entries) => entries.get_mut(key),
Storage::Small(entries) => entries
.iter_mut()
.find(|(k, _)| k.as_str() == key)
.map(|(_, v)| v),
Storage::Shared { shape, values } => {
let index = shape.keys.get_index_of(key)?;
Some(&mut values[index])
}
}
}
pub fn get_index_mut(&mut self, index: usize) -> Option<(&String, &mut Value)> {
match &mut self.storage {
Storage::Empty => None,
Storage::Owned(entries) => entries.get_index_mut(index),
Storage::Small(entries) => entries.get_mut(index).map(|(k, v)| (&*k, v)),
Storage::Shared { shape, values } => {
let (key, ()) = shape.keys.get_index(index)?;
Some((key, &mut values[index]))
}
}
}
pub fn iter(&self) -> MapEntriesIter<'_> {
MapEntriesIter {
inner: match &self.storage {
Storage::Empty => IterStorage::Empty,
Storage::Owned(entries) => IterStorage::Owned(entries.iter()),
Storage::Small(entries) => IterStorage::Small(entries.iter()),
Storage::Shared { shape, values } => {
IterStorage::Shared(shape.keys.keys().zip(values.iter()))
}
},
}
}
pub fn keys(&self) -> MapEntriesKeys<'_> {
MapEntriesKeys { inner: self.iter() }
}
pub fn values(&self) -> MapEntriesValues<'_> {
MapEntriesValues { inner: self.iter() }
}
pub fn iter_mut(&mut self) -> MapEntriesIterMut<'_> {
MapEntriesIterMut {
inner: match &mut self.storage {
Storage::Empty => IterMutStorage::Empty,
Storage::Owned(entries) => IterMutStorage::Owned(entries.iter_mut()),
Storage::Small(entries) => IterMutStorage::Small(entries.iter_mut()),
Storage::Shared { shape, values } => {
IterMutStorage::Shared(shape.keys.keys().zip(values.iter_mut()))
}
},
}
}
pub fn values_mut(&mut self) -> MapEntriesValuesMut<'_> {
MapEntriesValuesMut {
inner: self.iter_mut(),
}
}
pub fn insert(&mut self, key: String, value: Value) -> Option<Value> {
match &mut self.storage {
Storage::Empty => {}
Storage::Owned(entries) => return entries.insert(key, value),
Storage::Small(entries) => {
if let Some((_, old)) = entries.iter_mut().find(|(k, _)| k.as_str() == key.as_str())
{
return Some(std::mem::replace(old, value));
}
if entries.len() < MAX_SHAPE_KEYS {
entries.push((key, value));
return None;
}
}
Storage::Shared { shape, values } => {
if let Some(index) = shape.keys.get_index_of(key.as_str()) {
return Some(std::mem::replace(&mut values[index], value));
}
}
}
self.as_ordered_mut().insert(key, value)
}
pub fn shift_remove(&mut self, key: &str) -> Option<Value> {
if !self.contains_key(key) {
return None;
}
self.as_ordered_mut().shift_remove(key)
}
pub fn swap_remove(&mut self, key: &str) -> Option<Value> {
if !self.contains_key(key) {
return None;
}
self.as_ordered_mut().swap_remove(key)
}
pub fn clear(&mut self) {
match &mut self.storage {
Storage::Empty => {}
Storage::Owned(entries) => entries.clear(),
Storage::Small(entries) => entries.clear(),
Storage::Shared { .. } => {
let old = std::mem::replace(&mut self.storage, Storage::Empty);
drop(old);
}
}
}
pub fn as_ordered_mut(&mut self) -> &mut OrderedMap<Value> {
if !matches!(self.storage, Storage::Owned(_)) {
let old = std::mem::replace(&mut self.storage, Storage::Empty);
self.storage = Storage::Owned(Box::new(Self { storage: old }.into_ordered()));
}
match &mut self.storage {
Storage::Owned(entries) => entries,
Storage::Empty | Storage::Small(_) | Storage::Shared { .. } => {
unreachable!("entries were promoted")
}
}
}
pub fn into_ordered(self) -> OrderedMap<Value> {
match self.storage {
Storage::Empty => OrderedMap::default(),
Storage::Owned(entries) => *entries,
Storage::Small(entries) => entries.into_iter().collect(),
Storage::Shared { shape, values } => {
let mut entries = OrderedMap::with_capacity_and_hasher(values.len(), FxBuildHasher);
for (key, value) in shape.keys.keys().zip(values) {
entries.insert(key.clone(), value);
}
entries
}
}
}
pub(crate) fn with_values(&self, values: Vec<Value>) -> Self {
assert_eq!(
values.len(),
self.len(),
"map reconstruction changes key count"
);
match &self.storage {
Storage::Empty => Self::new(),
Storage::Owned(entries) => entries.keys().cloned().zip(values).collect(),
Storage::Small(entries) => Self {
storage: Storage::Small(
entries.iter().map(|(k, _)| k.clone()).zip(values).collect(),
),
},
Storage::Shared { shape, .. } => Self {
storage: Storage::Shared {
shape: shape.clone(),
values,
},
},
}
}
}
impl From<OrderedMap<Value>> for MapEntries {
fn from(entries: OrderedMap<Value>) -> Self {
if entries.capacity() == 0 {
Self::new()
} else {
Self {
storage: Storage::Owned(Box::new(entries)),
}
}
}
}
impl From<MapEntries> for OrderedMap<Value> {
fn from(entries: MapEntries) -> Self {
entries.into_ordered()
}
}
impl FromIterator<(String, Value)> for MapEntries {
fn from_iter<T: IntoIterator<Item = (String, Value)>>(iter: T) -> Self {
Self::from(OrderedMap::from_iter(iter))
}
}
impl Extend<(String, Value)> for MapEntries {
fn extend<T: IntoIterator<Item = (String, Value)>>(&mut self, iter: T) {
for (key, value) in iter {
self.insert(key, value);
}
}
}
enum IterStorage<'a> {
Empty,
Owned(indexmap::map::Iter<'a, String, Value>),
Small(std::slice::Iter<'a, (String, Value)>),
Shared(std::iter::Zip<indexmap::map::Keys<'a, String, ()>, std::slice::Iter<'a, Value>>),
}
pub struct MapEntriesIter<'a> {
inner: IterStorage<'a>,
}
impl<'a> Iterator for MapEntriesIter<'a> {
type Item = (&'a String, &'a Value);
fn next(&mut self) -> Option<Self::Item> {
match &mut self.inner {
IterStorage::Empty => None,
IterStorage::Owned(iter) => iter.next(),
IterStorage::Small(iter) => iter.next().map(|(k, v)| (k, v)),
IterStorage::Shared(iter) => iter.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl DoubleEndedIterator for MapEntriesIter<'_> {
fn next_back(&mut self) -> Option<Self::Item> {
match &mut self.inner {
IterStorage::Empty => None,
IterStorage::Owned(iter) => iter.next_back(),
IterStorage::Small(iter) => iter.next_back().map(|(k, v)| (k, v)),
IterStorage::Shared(iter) => iter.next_back(),
}
}
}
impl ExactSizeIterator for MapEntriesIter<'_> {
fn len(&self) -> usize {
match &self.inner {
IterStorage::Empty => 0,
IterStorage::Owned(iter) => iter.len(),
IterStorage::Small(iter) => iter.len(),
IterStorage::Shared(iter) => iter.len(),
}
}
}
impl FusedIterator for MapEntriesIter<'_> {}
pub struct MapEntriesKeys<'a> {
inner: MapEntriesIter<'a>,
}
impl<'a> Iterator for MapEntriesKeys<'a> {
type Item = &'a String;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(key, _)| key)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl DoubleEndedIterator for MapEntriesKeys<'_> {
fn next_back(&mut self) -> Option<Self::Item> {
self.inner.next_back().map(|(key, _)| key)
}
}
impl ExactSizeIterator for MapEntriesKeys<'_> {
fn len(&self) -> usize {
self.inner.len()
}
}
impl FusedIterator for MapEntriesKeys<'_> {}
pub struct MapEntriesValues<'a> {
inner: MapEntriesIter<'a>,
}
impl<'a> Iterator for MapEntriesValues<'a> {
type Item = &'a Value;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(_, value)| value)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl DoubleEndedIterator for MapEntriesValues<'_> {
fn next_back(&mut self) -> Option<Self::Item> {
self.inner.next_back().map(|(_, value)| value)
}
}
impl ExactSizeIterator for MapEntriesValues<'_> {
fn len(&self) -> usize {
self.inner.len()
}
}
impl FusedIterator for MapEntriesValues<'_> {}
enum IterMutStorage<'a> {
Empty,
Owned(indexmap::map::IterMut<'a, String, Value>),
Small(std::slice::IterMut<'a, (String, Value)>),
Shared(std::iter::Zip<indexmap::map::Keys<'a, String, ()>, std::slice::IterMut<'a, Value>>),
}
pub struct MapEntriesIterMut<'a> {
inner: IterMutStorage<'a>,
}
impl<'a> Iterator for MapEntriesIterMut<'a> {
type Item = (&'a String, &'a mut Value);
fn next(&mut self) -> Option<Self::Item> {
match &mut self.inner {
IterMutStorage::Empty => None,
IterMutStorage::Owned(iter) => iter.next(),
IterMutStorage::Small(iter) => iter.next().map(|(k, v)| (&*k, v)),
IterMutStorage::Shared(iter) => iter.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl DoubleEndedIterator for MapEntriesIterMut<'_> {
fn next_back(&mut self) -> Option<Self::Item> {
match &mut self.inner {
IterMutStorage::Empty => None,
IterMutStorage::Owned(iter) => iter.next_back(),
IterMutStorage::Small(iter) => iter.next_back().map(|(k, v)| (&*k, v)),
IterMutStorage::Shared(iter) => iter.next_back(),
}
}
}
impl ExactSizeIterator for MapEntriesIterMut<'_> {
fn len(&self) -> usize {
match &self.inner {
IterMutStorage::Empty => 0,
IterMutStorage::Owned(iter) => iter.len(),
IterMutStorage::Small(iter) => iter.len(),
IterMutStorage::Shared(iter) => iter.len(),
}
}
}
impl FusedIterator for MapEntriesIterMut<'_> {}
pub struct MapEntriesValuesMut<'a> {
inner: MapEntriesIterMut<'a>,
}
impl<'a> Iterator for MapEntriesValuesMut<'a> {
type Item = &'a mut Value;
fn next(&mut self) -> Option<Self::Item> {
self.inner.next().map(|(_, value)| value)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
}
impl DoubleEndedIterator for MapEntriesValuesMut<'_> {
fn next_back(&mut self) -> Option<Self::Item> {
self.inner.next_back().map(|(_, value)| value)
}
}
impl ExactSizeIterator for MapEntriesValuesMut<'_> {
fn len(&self) -> usize {
self.inner.len()
}
}
impl FusedIterator for MapEntriesValuesMut<'_> {}
impl<'a> IntoIterator for &'a MapEntries {
type Item = (&'a String, &'a Value);
type IntoIter = MapEntriesIter<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a> IntoIterator for &'a mut MapEntries {
type Item = (&'a String, &'a mut Value);
type IntoIter = MapEntriesIterMut<'a>;
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
pub struct MapEntriesIntoIter {
inner: IntoIterStorage,
}
enum IntoIterStorage {
Empty,
Owned(indexmap::map::IntoIter<String, Value>),
Small(std::vec::IntoIter<(String, Value)>),
}
impl Iterator for MapEntriesIntoIter {
type Item = (String, Value);
fn next(&mut self) -> Option<Self::Item> {
match &mut self.inner {
IntoIterStorage::Empty => None,
IntoIterStorage::Owned(iter) => iter.next(),
IntoIterStorage::Small(iter) => iter.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl DoubleEndedIterator for MapEntriesIntoIter {
fn next_back(&mut self) -> Option<Self::Item> {
match &mut self.inner {
IntoIterStorage::Empty => None,
IntoIterStorage::Owned(iter) => iter.next_back(),
IntoIterStorage::Small(iter) => iter.next_back(),
}
}
}
impl ExactSizeIterator for MapEntriesIntoIter {
fn len(&self) -> usize {
match &self.inner {
IntoIterStorage::Empty => 0,
IntoIterStorage::Owned(iter) => iter.len(),
IntoIterStorage::Small(iter) => iter.len(),
}
}
}
impl FusedIterator for MapEntriesIntoIter {}
impl IntoIterator for MapEntries {
type Item = (String, Value);
type IntoIter = MapEntriesIntoIter;
fn into_iter(self) -> Self::IntoIter {
MapEntriesIntoIter {
inner: match self.storage {
Storage::Empty => IntoIterStorage::Empty,
Storage::Small(entries) => IntoIterStorage::Small(entries.into_iter()),
other => IntoIterStorage::Owned(Self { storage: other }.into_ordered().into_iter()),
},
}
}
}
#[derive(Default)]
pub(crate) struct MapShapePool {
entries: FxHashMap<u64, Weak<KeyShape>>,
}
impl MapShapePool {
pub(crate) fn seal(&mut self, entries: &mut MapEntries) -> bool {
if entries.is_shared() {
return true;
}
if entries.is_empty() {
if matches!(entries.storage, Storage::Small(_)) {
entries.storage = Storage::Empty;
}
return false;
}
if !(1..=MAX_SHAPE_KEYS).contains(&entries.len()) {
return false;
}
let mut hash = FxHasher::default();
entries.len().hash(&mut hash);
for key in entries.keys() {
key.len().hash(&mut hash);
key.hash(&mut hash);
}
self.seal_with_fingerprint(entries, hash.finish())
}
fn seal_with_fingerprint(&mut self, entries: &mut MapEntries, fingerprint: u64) -> bool {
if entries.is_shared() {
return true;
}
if !(1..=MAX_SHAPE_KEYS).contains(&entries.len()) {
return false;
}
let existing = self
.entries
.get(&fingerprint)
.and_then(Weak::upgrade)
.filter(|shape| shape.keys.keys().eq(entries.keys()));
let old = std::mem::replace(&mut entries.storage, Storage::Empty);
let owned = MapEntries { storage: old }.into_iter();
let mut values = Vec::with_capacity(owned.len());
let shape = if let Some(shape) = existing {
for (_, value) in owned {
values.push(value);
}
shape
} else {
let mut keys = OrderedMap::with_capacity_and_hasher(owned.len(), FxBuildHasher);
for (key, value) in owned {
keys.insert(key, ());
values.push(value);
}
let shape = Rc::new(KeyShape { keys });
if self.entries.len() >= MAX_POOL_ENTRIES && !self.entries.contains_key(&fingerprint) {
self.entries.clear();
}
self.entries.insert(fingerprint, Rc::downgrade(&shape));
shape
};
entries.storage = Storage::Shared { shape, values };
true
}
}
#[cfg(test)]
#[path = "../../tests/private/map_entries_test.rs"]
mod tests;