use crate::core::core_types::NodeId;
use rustc_hash::{FxBuildHasher, FxHashMap};
pub enum IdMap {
Dense { min_id: i64, table: Vec<NodeId> },
Sparse(FxHashMap<i64, NodeId>),
}
const VACANT: NodeId = NodeId::MAX;
pub fn parse_canonical_int(name: &[u8]) -> Option<i64> {
if name.is_empty() || name.len() > 18 || (name.len() > 1 && name[0] == b'0') {
return None;
}
name.iter().try_fold(0_i64, |value, &b| {
b.is_ascii_digit().then(|| value * 10 + i64::from(b - b'0'))
})
}
impl IdMap {
#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
pub fn from_ids(ids: &[i64]) -> Result<Self, i64> {
let (Some(&min_id), Some(&max_id)) = (ids.iter().min(), ids.iter().max()) else {
return Ok(Self::Sparse(FxHashMap::default()));
};
let span = max_id.abs_diff(min_id).saturating_add(1);
let dense_limit = ids.len().saturating_mul(2).saturating_add(1024) as u64;
if span <= dense_limit {
let mut table = vec![VACANT; span as usize];
for (internal, &id) in ids.iter().enumerate() {
let slot = &mut table[id.abs_diff(min_id) as usize];
if *slot != VACANT {
return Err(id);
}
*slot = internal;
}
Ok(Self::Dense { min_id, table })
} else {
let mut map = FxHashMap::with_capacity_and_hasher(ids.len(), FxBuildHasher);
for (internal, &id) in ids.iter().enumerate() {
if map.insert(id, internal).is_some() {
return Err(id);
}
}
Ok(Self::Sparse(map))
}
}
#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
pub fn get(&self, id: i64) -> Option<NodeId> {
match self {
Self::Dense { min_id, table } => {
if id < *min_id {
return None;
}
table
.get(id.abs_diff(*min_id) as usize)
.copied()
.filter(|&i| i != VACANT)
}
Self::Sparse(map) => map.get(&id).copied(),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn dense_and_sparse_lookups() {
let dense = IdMap::from_ids(&[5, 3, 4]).unwrap();
assert!(matches!(dense, IdMap::Dense { .. }));
let sparse = IdMap::from_ids(&[i64::MIN, 0, i64::MAX]).unwrap();
assert!(matches!(sparse, IdMap::Sparse(_)));
assert_eq!(dense.get(5), Some(0));
assert_eq!(dense.get(3), Some(1));
assert_eq!(dense.get(2), None);
assert_eq!(dense.get(6), None);
assert_eq!(sparse.get(i64::MAX), Some(2));
assert_eq!(sparse.get(1), None);
}
#[test]
fn duplicates_are_reported() {
assert!(matches!(IdMap::from_ids(&[1, 2, 1]), Err(1)));
assert!(matches!(IdMap::from_ids(&[0, i64::MAX, 0]), Err(0)));
}
#[test]
fn empty_map() {
assert_eq!(IdMap::from_ids(&[]).unwrap().get(0), None);
}
}