#[cfg(feature = "serde")]
mod serde;
mod entry;
mod iter;
use core::iter::{IntoIterator, Iterator};
use iter::*;
pub use entry::*;
#[derive(Clone)]
pub struct IntMap<V> {
cache: Vec<Vec<(u64, V)>>,
size: u32,
mod_mask: u64,
count: usize,
load_factor: usize,
}
impl<V> IntMap<V> {
pub fn new() -> Self {
IntMap::with_capacity(4)
}
pub fn with_capacity(capacity: usize) -> Self {
let mut map = IntMap {
cache: Vec::new(),
size: 0,
count: 0,
mod_mask: 0,
load_factor: 909, };
map.increase_cache();
while map.lim() < capacity {
map.increase_cache();
}
map
}
pub fn set_load_factor(&mut self, load_factor: f32) {
self.load_factor = (load_factor * 1000.) as usize;
self.ensure_load_rate();
}
pub fn get_load_factor(&self) -> f32 {
self.load_factor as f32 / 1000.
}
pub fn reserve(&mut self, additional: usize) {
let capacity = (self.count + additional).next_power_of_two();
while self.lim() < capacity {
self.increase_cache();
}
}
pub fn insert(&mut self, key: u64, value: V) -> Option<V> {
let ix = self.calc_index(key);
let vals = &mut self.cache[ix];
let pos = vals.iter().position(|kv| kv.0 == key);
let old = if let Some(pos) = pos {
Some(vals.swap_remove(pos).1)
} else {
self.count += 1;
None
};
vals.push((key, value));
if (self.count & 4) == 4 {
self.ensure_load_rate();
}
old
}
pub fn insert_checked(&mut self, key: u64, value: V) -> bool {
let ix = self.calc_index(key);
let vals = &mut self.cache[ix];
if vals.iter().any(|kv| kv.0 == key) {
return false;
}
self.count += 1;
vals.push((key, value));
if (self.count & 4) == 4 {
self.ensure_load_rate();
}
true
}
pub fn get(&self, key: u64) -> Option<&V> {
let ix = self.calc_index(key);
let vals = &self.cache[ix];
vals.iter().find_map(|kv| (kv.0 == key).then(|| &kv.1))
}
pub fn get_mut(&mut self, key: u64) -> Option<&mut V> {
let ix = self.calc_index(key);
let vals = &mut self.cache[ix];
return vals
.iter_mut()
.find_map(|kv| (kv.0 == key).then(move || &mut kv.1));
}
pub fn remove(&mut self, key: u64) -> Option<V> {
let ix = self.calc_index(key);
let vals = &mut self.cache[ix];
for i in 0..vals.len() {
let peek = vals[i].0;
if peek == key {
self.count -= 1;
let kv = vals.swap_remove(i);
return Some(kv.1);
}
}
None
}
pub fn contains_key(&self, key: u64) -> bool {
self.get(key).is_some()
}
pub fn clear(&mut self) {
for vals in &mut self.cache {
vals.clear();
}
self.count = 0;
}
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(u64, &V) -> bool,
{
let mut removed = 0;
for vals in &mut self.cache {
vals.retain(|(k, v)| {
let keep = (f)(*k, v);
if !keep {
removed += 1;
}
keep
});
}
self.count -= removed;
}
pub fn is_empty(&self) -> bool {
self.count == 0
}
pub fn iter(&self) -> Iter<u64, V> {
Iter::new(&self.cache)
}
pub fn iter_mut(&mut self) -> IterMut<u64, V> {
IterMut::new(&mut self.cache)
}
pub fn keys(&self) -> Keys<u64, V> {
Keys { inner: self.iter() }
}
pub fn values(&self) -> Values<u64, V> {
Values { inner: self.iter() }
}
pub fn values_mut(&mut self) -> ValuesMut<u64, V> {
ValuesMut {
inner: self.iter_mut(),
}
}
pub fn drain(&mut self) -> Drain<u64, V> {
Drain::new(&mut self.cache, &mut self.count)
}
#[inline(always)]
fn hash_u64(seed: u64) -> u64 {
let a = 11400714819323198549u64;
a.wrapping_mul(seed)
}
#[inline(always)]
pub(crate) fn calc_index(&self, key: u64) -> usize {
let hash = Self::hash_u64(key);
(hash & self.mod_mask) as usize
}
#[inline(always)]
fn lim(&self) -> usize {
2u64.pow(self.size) as usize
}
fn increase_cache(&mut self) {
self.size += 1;
let new_lim = self.lim();
self.mod_mask = (new_lim as u64) - 1;
let mut vec: Vec<Vec<(u64, V)>> = (0..new_lim).map(|_| Vec::new()).collect();
std::mem::swap(&mut self.cache, &mut vec);
for k in vec.into_iter().flatten() {
let ix = self.calc_index(k.0);
let vals = &mut self.cache[ix];
vals.push(k);
}
debug_assert!(
self.cache.len() == self.lim(),
"cache vector the wrong length, lim: {:?} cache: {:?}",
self.lim(),
self.cache.len()
);
}
#[inline]
fn ensure_load_rate(&mut self) {
while ((self.count * 1000) / self.cache.len()) > self.load_factor {
self.increase_cache();
}
}
pub fn len(&self) -> usize {
self.count as usize
}
pub fn load(&self) -> u64 {
self.cache.iter().filter(|vals| !vals.is_empty()).count() as u64
}
pub fn load_rate(&self) -> f64 {
(self.count as f64) / (self.cache.len() as f64) * 100f64
}
pub fn capacity(&self) -> usize {
self.cache.len()
}
pub fn assert_count(&self) -> bool {
let count = self.cache.iter().flatten().count();
self.count == count
}
pub fn collisions(&self) -> IntMap<u64> {
let mut map = IntMap::new();
for s in self.cache.iter() {
let key = s.len() as u64;
if key > 1 {
if !map.contains_key(key) {
map.insert(key, 1);
} else {
let counter = map.get_mut(key).unwrap();
*counter += 1;
}
}
}
map
}
pub fn entry(&mut self, key: u64) -> Entry<V> {
Entry::new(key, self)
}
}
impl<V> Default for IntMap<V> {
fn default() -> Self {
Self::new()
}
}
impl<V> PartialEq for IntMap<V>
where
V: PartialEq,
{
fn eq(&self, other: &IntMap<V>) -> bool {
self.iter().all(|(k, a)| other.get(*k) == Some(a))
&& other.iter().all(|(k, a)| self.get(*k) == Some(a))
}
}
impl<V> Eq for IntMap<V> where V: Eq {}
impl<V> std::fmt::Debug for IntMap<V>
where
V: std::fmt::Debug,
{
fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
fmt.debug_map().entries(self.iter()).finish()
}
}