use super::scratch::Pooled;
use crate::linear::occurrences::{OccId, OccSet};
use crate::linear::proofs::NodeId;
use crate::linear::search::memory::{Account, bytes_of};
use std::hash::{BuildHasher as _, Hasher as _};
use std::sync::Mutex;
#[derive(Debug, Default)]
pub(super) struct Key {
pub(super) theta: u64,
pub(super) members: Pooled<OccId>,
}
impl Key {
pub(super) fn assign(&mut self, zones: Zones<'_>) {
self.theta = zones.theta;
self.members.clear();
self.members.extend_from_slice(zones.members);
}
pub(super) fn zones(&self) -> Zones<'_> {
Zones {
theta: self.theta,
members: &self.members,
}
}
}
#[derive(Clone, Copy, Debug)]
pub(super) struct Zones<'a> {
pub(super) theta: u64,
pub(super) members: &'a [OccId],
}
pub(super) const REPEATED: u32 = 1 << 31;
pub(super) fn decoded(members: &[OccId]) -> impl Iterator<Item = (OccId, u32)> + '_ {
let mut words = members.iter().map(|o| o.get());
std::iter::from_fn(move || {
let word = words.next()?;
Some(if word & REPEATED == 0 {
(OccId::new(word), 1)
} else {
let copies = words.next().expect("a repeated member's count");
(OccId::new(word & !REPEATED), copies)
})
})
}
impl Zones<'_> {
pub(super) fn hash(self) -> u64 {
const K: u64 = 0xf135_7aea_2e62_a9c5;
let fold = |folded: u64, word: u64| (folded.rotate_left(26) ^ word).wrapping_mul(K);
let (pairs, rest) = self.members.as_chunks::<2>();
let mut folded = 0;
for [first, second] in pairs {
folded = fold(
folded,
u64::from(first.get()) | (u64::from(second.get()) << 32),
);
}
if let [last] = rest {
folded = fold(folded, u64::from(last.get()));
}
let mut hasher = crate::hash::BuildHasher::default().build_hasher();
hasher.write_u64(self.theta);
hasher.write_u64(folded);
hasher.write_usize(self.members.len());
hasher.finish()
}
pub(super) fn of(self, key: &Key) -> bool {
key.theta == self.theta && *key.members == *self.members
}
}
#[derive(Debug, Default)]
pub(super) struct Interner {
ids: crate::hash::HashMap<OccSet, u64>,
next: u64,
limit: usize,
charged: usize,
released: u64,
}
impl Interner {
pub(super) fn new(limit: usize) -> Self {
Self {
limit,
..Self::default()
}
}
pub(super) fn intern(&mut self, zone: &OccSet, account: &Account) -> u64 {
if self.limit != 0
&& let Some(&id) = self.ids.get(zone)
{
return id;
}
let id = self.next;
self.next += 1;
if self.limit == 0 {
return id;
}
if self.ids.len() >= self.limit {
self.release(account);
}
let set = size_of_val(zone.words());
let capacity = self.ids.capacity();
let buckets = if self.ids.len() < capacity {
0
} else {
Self::buckets(capacity + 1) - Self::buckets(capacity)
};
if account.spares(set + buckets) {
self.ids.insert(zone.clone(), id);
let bytes = self.ids.len() * set + Self::buckets(self.ids.capacity());
account.resize(self.charged, bytes);
self.charged = bytes;
}
id
}
fn buckets(capacity: usize) -> usize {
const GROUP: usize = 16;
let buckets = match capacity {
0 => return 0,
1..4 => 4,
4..8 => 8,
_ => (capacity * 8 / 7).next_power_of_two(),
};
buckets * (size_of::<(OccSet, u64)>() + 1) + GROUP
}
pub(super) fn release(&mut self, account: &Account) {
account.release(self.charged);
self.charged = 0;
self.ids = crate::hash::HashMap::default();
self.released += 1;
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Entry {
Proved(NodeId),
Failed(Failure),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Failure {
Complete,
Exhausted(u32),
Hereditary,
}
impl Entry {
fn code(self, stamp: u32) -> u64 {
match self {
Self::Proved(node) => u64::from(node.get()),
Self::Failed(Failure::Complete) => 1 << 32,
Self::Failed(Failure::Exhausted(left)) => {
(u64::from(stamp) << 34) | (2 << 32) | u64::from(left)
}
Self::Failed(Failure::Hereditary) => 3 << 32,
}
}
fn of(code: u64) -> Self {
match (code >> 32) & 3 {
0 => Self::Proved(NodeId::new(code as u32)),
1 => Self::Failed(Failure::Complete),
3 => Self::Failed(Failure::Hereditary),
_ => Self::Failed(Failure::Exhausted(code as u32)),
}
}
}
fn stamp(generation: u64) -> u32 {
(generation & ((1 << 30) - 1)) as u32
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Inserted {
Done,
Full,
NoRoom,
}
const HASH: usize = 0;
const ENTRY: usize = 2;
const THETA: usize = 4;
const MEMBERS: usize = 6;
const HEADER: usize = 7;
const CHUNK: usize = 1 << 18;
#[cfg(feature = "parallel")]
const SHARD_CHUNK: usize = 1 << 14;
fn read(words: &[u32], at: usize) -> u64 {
u64::from(words[at]) | (u64::from(words[at + 1]) << 32)
}
fn write(words: &mut [u32], at: usize, value: u64) {
words[at] = value as u32;
words[at + 1] = (value >> 32) as u32;
}
fn place(slots: &mut [u64], at: u64, hash: u64) {
let mask = slots.len() - 1;
let mut slot = hash as usize & mask;
while slots[slot] != 0 {
slot = (slot + 1) & mask;
}
slots[slot] = at + 1;
}
#[derive(Debug)]
pub(super) struct Memo {
slots: Vec<u64>,
chunks: Vec<Vec<u32>>,
current: usize,
chunk: usize,
most: usize,
len: usize,
limit: usize,
peak: usize,
hits: u64,
stamp: u32,
added: u64,
emptied: u64,
}
impl Memo {
pub(super) fn new(limit: usize) -> Self {
Self::with_chunk(limit, CHUNK)
}
fn with_chunk(limit: usize, most: usize) -> Self {
Self {
slots: Vec::new(),
chunks: Vec::new(),
current: 0,
chunk: 0,
most,
len: 0,
limit: limit.min(u32::MAX as usize - 1),
peak: 0,
hits: 0,
stamp: 0,
added: 0,
emptied: 0,
}
}
pub(super) fn begin(&mut self, generation: u64) {
self.stamp = stamp(generation);
if self.stamp == 0 && generation != 0 {
self.clear();
}
}
fn record(&self, at: u64) -> &[u32] {
let (chunk, start) = (&self.chunks[(at >> 32) as usize], at as u32 as usize);
&chunk[start..start + HEADER + chunk[start + MEMBERS] as usize]
}
fn record_mut(&mut self, at: u64) -> &mut [u32] {
let (chunk, start) = (&mut self.chunks[(at >> 32) as usize], at as u32 as usize);
let end = start + HEADER + chunk[start + MEMBERS] as usize;
&mut chunk[start..end]
}
fn matches(record: &[u32], key: Zones<'_>) -> bool {
let members = &record[HEADER..];
read(record, THETA) == key.theta
&& members.len() == key.members.len()
&& members.iter().zip(key.members).all(|(&m, o)| m == o.get())
}
fn find(&self, key: Zones<'_>, hash: u64) -> Option<u64> {
if self.slots.is_empty() {
return None;
}
let mask = self.slots.len() - 1;
let mut slot = hash as usize & mask;
loop {
let at = self.slots[slot].checked_sub(1)?;
let record = self.record(at);
if read(record, HASH) == hash && Self::matches(record, key) {
return Some(at);
}
slot = (slot + 1) & mask;
}
}
fn entry(&self, at: u64) -> Entry {
Entry::of(read(self.record(at), ENTRY))
}
#[cfg(test)]
fn insert(&mut self, key: &Key, entry: Entry, account: &Account) -> Inserted {
self.insert_hashed(key.zones(), key.zones().hash(), entry, account)
}
#[cfg(test)]
fn get(&mut self, key: &Key, remaining: u32) -> Option<Entry> {
self.get_hashed(key.zones(), key.zones().hash(), remaining)
}
fn stale(&self, at: u64) -> bool {
let code = read(self.record(at), ENTRY);
(code >> 32) & 3 == 2 && (code >> 34) as u32 != self.stamp
}
fn get_hashed(&mut self, key: Zones<'_>, hash: u64, remaining: u32) -> Option<Entry> {
let at = self.find(key, hash)?;
let entry = self.entry(at);
if let Entry::Failed(Failure::Exhausted(then)) = entry
&& (remaining > then || self.stale(at))
{
return None;
}
self.hits += 1;
Some(entry)
}
#[cfg(test)]
fn refuted(&mut self, key: &Key) -> bool {
self.refuted_hashed(key.zones(), key.zones().hash())
.is_some()
}
fn refuted_hashed(&mut self, key: Zones<'_>, hash: u64) -> Option<Failure> {
let refuted = self.find(key, hash).and_then(|at| match self.entry(at) {
Entry::Failed(failure @ (Failure::Complete | Failure::Hereditary)) => Some(failure),
_ => None,
});
self.hits += u64::from(refuted.is_some());
refuted
}
fn insert_hashed(
&mut self,
key: Zones<'_>,
hash: u64,
entry: Entry,
account: &Account,
) -> Inserted {
if self.limit == 0 {
return Inserted::Done;
}
if let Some(at) = self.find(key, hash) {
let old = self.entry(at);
debug_assert!(
!matches!(
(old, entry),
(
Entry::Proved(_),
Entry::Failed(Failure::Complete | Failure::Hereditary)
)
),
"a complete failure of a proved sequent"
);
let keep = match (old, entry) {
(
Entry::Failed(Failure::Exhausted(then)),
Entry::Failed(Failure::Exhausted(now)),
) => now <= then && !self.stale(at),
(Entry::Proved(_) | Entry::Failed(Failure::Hereditary), Entry::Failed(_)) => true,
(
Entry::Failed(Failure::Complete),
Entry::Failed(Failure::Complete | Failure::Exhausted(_)),
) => true,
_ => false,
};
if !keep {
let code = entry.code(self.stamp);
write(self.record_mut(at), ENTRY, code);
}
return Inserted::Done;
}
let words = HEADER + key.members.len();
let counted = u32::try_from(words).is_ok();
if self.len >= self.limit || !counted || !self.reserve(words, account) {
return if self.len == 0 {
Inserted::NoRoom
} else {
Inserted::Full
};
}
let chunk = &mut self.chunks[self.current];
let start = chunk.len();
debug_assert!(chunk.capacity() - start >= words, "a chunk with room");
chunk.resize(start + HEADER, 0);
write(chunk, start + HASH, hash);
write(chunk, start + ENTRY, entry.code(self.stamp));
write(chunk, start + THETA, key.theta);
chunk[start + MEMBERS] = key.members.len() as u32;
chunk.extend(key.members.iter().map(|o| o.get()));
self.len += 1;
self.added += 1;
place(
&mut self.slots,
((self.current as u64) << 32) | start as u64,
hash,
);
self.peak = self.peak.max(self.len);
Inserted::Done
}
fn reserve(&mut self, words: usize, account: &Account) -> bool {
if self.chunk == 0 {
let room = account.limit().saturating_sub(account.used()) / 16;
self.chunk = (room / size_of::<u32>() as u64).clamp(1, self.most as u64) as usize;
}
if (self.len + 1) * 2 > self.slots.len() {
let wider = (self.slots.len() * 2).max(16);
if !account.spares(wider * size_of::<u64>()) {
return false;
}
let narrower = bytes_of(&self.slots);
self.slots = vec![0; wider];
account.resize(narrower, bytes_of(&self.slots));
for (c, chunk) in self.chunks.iter().enumerate().take(self.current + 1) {
let mut start = 0;
while start < chunk.len() {
let at = ((c as u64) << 32) | start as u64;
place(&mut self.slots, at, read(chunk, start + HASH));
start += HEADER + chunk[start + MEMBERS] as usize;
}
}
}
let room = |chunk: &Vec<u32>| chunk.capacity() - chunk.len();
if self
.chunks
.get(self.current)
.is_some_and(|chunk| !chunk.is_empty() && room(chunk) < words)
{
self.current += 1;
}
match self.chunks.get_mut(self.current) {
Some(chunk) if room(chunk) >= words => true,
Some(chunk) => {
let (before, after) = (bytes_of(chunk), words * size_of::<u32>());
if !account.spares(after - before) {
return false;
}
chunk.reserve_exact(words);
account.resize(before, bytes_of(chunk));
true
}
None => {
let capacity = self.chunk.max(words);
if !account.spares(capacity * size_of::<u32>()) {
return false;
}
let chunk = Vec::with_capacity(capacity);
account.charge(bytes_of(&chunk));
self.chunks.push(chunk);
true
}
}
}
pub(super) fn clear(&mut self) {
self.emptied += u64::from(self.len > 0);
self.len = 0;
self.current = 0;
self.slots.fill(0);
for chunk in &mut self.chunks {
chunk.clear();
}
}
pub(super) fn release(&mut self, account: &Account) {
let held = bytes_of(&self.slots) + self.chunks.iter().map(bytes_of).sum::<usize>();
account.release(held);
self.emptied += u64::from(self.len > 0);
self.len = 0;
self.current = 0;
self.slots = Vec::new();
self.chunks = Vec::new();
}
pub(super) fn peak(&self) -> usize {
self.peak
}
pub(super) fn added(&self) -> u64 {
self.added
}
pub(super) fn emptied(&self) -> u64 {
self.emptied
}
pub(super) fn hits(&self) -> u64 {
self.hits
}
}
const SHARDS: usize = 64;
#[derive(Debug)]
pub(super) struct Shared {
shards: Box<[Mutex<Memo>]>,
zones: Mutex<Interner>,
}
impl Shared {
#[cfg(feature = "parallel")]
pub(super) fn new(limit: usize, zones: usize) -> Self {
let per_shard = limit.div_ceil(SHARDS);
Self {
shards: (0..SHARDS)
.map(|_| {
Mutex::new(Memo::with_chunk(
if limit == 0 { 0 } else { per_shard },
SHARD_CHUNK,
))
})
.collect(),
zones: Mutex::new(Interner::new(zones)),
}
}
fn shard(&self, hash: u64) -> std::sync::MutexGuard<'_, Memo> {
crate::linear::search::lock(&self.shards[(hash >> (64 - SHARDS.trailing_zeros())) as usize])
}
pub(super) fn get(&self, key: Zones<'_>, hash: u64, remaining: u32) -> Option<Entry> {
self.shard(hash).get_hashed(key, hash, remaining)
}
pub(super) fn refuted(&self, key: Zones<'_>, hash: u64) -> Option<Failure> {
self.shard(hash).refuted_hashed(key, hash)
}
pub(super) fn begin(&self, generation: u64) {
for shard in &self.shards {
crate::linear::search::lock(shard).begin(generation);
}
}
pub(super) fn added(&self) -> u64 {
self.shards
.iter()
.map(|s| crate::linear::search::lock(s).added())
.sum()
}
pub(super) fn emptied(&self) -> u64 {
let shards: u64 = self
.shards
.iter()
.map(|s| crate::linear::search::lock(s).emptied())
.sum();
shards + crate::linear::search::lock(&self.zones).released
}
pub(super) fn insert(&self, key: Zones<'_>, hash: u64, entry: Entry, account: &Account) {
let mut shard = self.shard(hash);
if shard.insert_hashed(key, hash, entry, account) == Inserted::Full {
shard.clear();
shard.insert_hashed(key, hash, entry, account);
}
}
pub(super) fn release(&self, account: &Account) {
for shard in &self.shards {
crate::linear::search::lock(shard).release(account);
}
crate::linear::search::lock(&self.zones).release(account);
}
pub(super) fn peak(&self) -> usize {
self.shards
.iter()
.map(|s| crate::linear::search::lock(s).peak())
.sum()
}
pub(super) fn hits(&self) -> u64 {
self.shards
.iter()
.map(|s| crate::linear::search::lock(s).hits())
.sum()
}
}
#[derive(Debug)]
pub(super) enum Table<'a> {
Own(Memo, Interner),
#[cfg_attr(
not(feature = "parallel"),
expect(dead_code, reason = "only a pool shares its memo")
)]
Shared(&'a Shared),
}
impl Table<'_> {
pub(super) fn own(limit: usize) -> Self {
Self::Own(Memo::new(limit), Interner::new(limit))
}
pub(super) fn intern(&mut self, zone: &OccSet, account: &Account) -> u64 {
match self {
Self::Own(_, zones) => zones.intern(zone, account),
Self::Shared(shared) => {
crate::linear::search::lock(&shared.zones).intern(zone, account)
}
}
}
pub(super) fn begin(&mut self, generation: u64) {
match self {
Self::Own(memo, _) => memo.begin(generation),
Self::Shared(shared) => shared.begin(generation),
}
}
pub(super) fn added(&self) -> u64 {
match self {
Self::Own(memo, _) => memo.added(),
Self::Shared(shared) => shared.added(),
}
}
pub(super) fn emptied(&self) -> u64 {
match self {
Self::Own(memo, zones) => memo.emptied() + zones.released,
Self::Shared(shared) => shared.emptied(),
}
}
pub(super) fn get(&mut self, key: Zones<'_>, hash: u64, remaining: u32) -> Option<Entry> {
match self {
Self::Own(memo, _) => memo.get_hashed(key, hash, remaining),
Self::Shared(shared) => shared.get(key, hash, remaining),
}
}
pub(super) fn refuted(&mut self, key: Zones<'_>, hash: u64) -> Option<Failure> {
match self {
Self::Own(memo, _) => memo.refuted_hashed(key, hash),
Self::Shared(shared) => shared.refuted(key, hash),
}
}
pub(super) fn insert(
&mut self,
key: Zones<'_>,
hash: u64,
entry: Entry,
account: &Account,
) -> Inserted {
match self {
Self::Own(memo, _) => memo.insert_hashed(key, hash, entry, account),
Self::Shared(shared) => {
shared.insert(key, hash, entry, account);
Inserted::Done
}
}
}
pub(super) fn clear(&mut self) {
if let Self::Own(memo, _) = self {
memo.clear();
}
}
pub(super) fn release(&mut self, account: &Account) {
match self {
Self::Own(memo, zones) => {
memo.release(account);
zones.release(account);
}
Self::Shared(shared) => shared.release(account),
}
}
pub(super) fn peak(&self) -> usize {
match self {
Self::Own(memo, _) => memo.peak(),
Self::Shared(shared) => shared.peak(),
}
}
pub(super) fn count_hit(&mut self, hash: u64) {
match self {
Self::Own(memo, _) => memo.hits += 1,
Self::Shared(shared) => shared.shard(hash).hits += 1,
}
}
pub(super) fn hits(&self) -> u64 {
match self {
Self::Own(memo, _) => memo.hits(),
Self::Shared(shared) => shared.hits(),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
fn key(theta: u64, members: &[u32]) -> Key {
let mut key = Key {
theta,
..Key::default()
};
key.members.extend(members.iter().map(|&o| OccId::new(o)));
key
}
#[test]
fn complete_failures_are_shared() {
let key = key(0, &[1]);
let account = Account::new(None);
let mut memo = Memo::new(10);
assert!(!memo.refuted(&key));
memo.insert(&key, Entry::Failed(Failure::Exhausted(1)), &account);
assert!(!memo.refuted(&key));
memo.insert(&key, Entry::Failed(Failure::Complete), &account);
assert!(memo.refuted(&key));
let mut proved = Memo::new(10);
proved.insert(&key, Entry::Proved(NodeId::new(4)), &account);
assert!(!proved.refuted(&key));
assert_eq!((memo.hits(), proved.hits()), (1, 0));
}
#[test]
fn cuts_hold_in_their_generation() {
let account = Account::new(None);
let mut memo = Memo::new(10);
let one = key(0, &[1]);
let cut = |left| Some(Entry::Failed(Failure::Exhausted(left)));
memo.begin(4);
memo.insert(&one, Entry::Failed(Failure::Exhausted(3)), &account);
memo.insert(&one, Entry::Failed(Failure::Exhausted(1)), &account);
assert_eq!(memo.get(&one, 2), cut(3));
memo.begin(5);
assert_eq!(memo.get(&one, 2), None, "a cut of the level before");
memo.insert(&one, Entry::Failed(Failure::Exhausted(1)), &account);
assert_eq!(memo.get(&one, 1), cut(1));
memo.begin(0);
memo.insert(&one, Entry::Failed(Failure::Exhausted(0)), &account);
memo.begin(1 << 30);
assert_eq!(memo.get(&one, 0), None, "the stamp is 0 again");
memo.insert(&one, Entry::Failed(Failure::Complete), &account);
memo.begin((1 << 30) + 1);
assert_eq!(memo.get(&one, 0), Some(Entry::Failed(Failure::Complete)));
}
#[test]
fn bounded_failures() {
let account = Account::new(None);
let mut memo = Memo::new(10);
let one = key(0, &[1]);
assert_eq!(memo.get(&one, 0), None);
memo.insert(&one, Entry::Failed(Failure::Exhausted(1)), &account);
assert_eq!(memo.get(&one, 2), None, "more copies left now");
assert_eq!(
memo.get(&one, 1),
Some(Entry::Failed(Failure::Exhausted(1)))
);
assert_eq!(
memo.get(&one, 0),
Some(Entry::Failed(Failure::Exhausted(1)))
);
memo.insert(&one, Entry::Failed(Failure::Exhausted(0)), &account);
assert_eq!(
memo.get(&one, 1),
Some(Entry::Failed(Failure::Exhausted(1))),
"a smaller budget does not weaken the entry"
);
memo.insert(&one, Entry::Failed(Failure::Exhausted(3)), &account);
assert_eq!(
memo.get(&one, 3),
Some(Entry::Failed(Failure::Exhausted(3)))
);
memo.insert(&one, Entry::Failed(Failure::Complete), &account);
assert_eq!(memo.get(&one, 100), Some(Entry::Failed(Failure::Complete)));
memo.insert(&one, Entry::Failed(Failure::Exhausted(5)), &account);
assert_eq!(
memo.get(&one, 100),
Some(Entry::Failed(Failure::Complete)),
"a complete failure stays"
);
let other = key(0, &[2]);
let proved = Entry::Proved(NodeId::new(7));
memo.insert(&other, proved, &account);
assert_eq!(memo.get(&other, 0), Some(proved));
memo.insert(&other, Entry::Failed(Failure::Exhausted(9)), &account);
assert_eq!(memo.get(&other, 0), Some(proved), "a proof stays");
assert_eq!(memo.hits(), 8);
assert_eq!(memo.peak(), 2);
}
#[test]
fn full_and_emptied() {
let entry = Entry::Failed(Failure::Complete);
let account = Account::new(None);
let mut memo = Memo::new(2);
assert_eq!(memo.insert(&key(0, &[1]), entry, &account), Inserted::Done);
assert_eq!(memo.insert(&key(0, &[2]), entry, &account), Inserted::Done);
assert_eq!(memo.insert(&key(0, &[1]), entry, &account), Inserted::Done);
assert_eq!(memo.insert(&key(0, &[3]), entry, &account), Inserted::Full);
let held = account.used();
memo.clear();
assert_eq!(memo.insert(&key(0, &[3]), entry, &account), Inserted::Done);
assert!(memo.refuted(&key(0, &[3])) && !memo.refuted(&key(0, &[1])));
assert_eq!(account.used(), held, "the emptied table keeps its memory");
memo.release(&account);
assert_eq!(account.used(), 0);
assert!(!memo.refuted(&key(0, &[3])));
let account = Account::new(Some(4096));
let mut memo = Memo::new(1000);
let fitted = (0..1000)
.take_while(|&member| {
memo.insert(&key(0, &[member]), entry, &account) == Inserted::Done
})
.count();
assert_eq!(fitted, 64, "entries in 4 KiB");
assert_eq!(memo.chunks.len(), 8);
assert!(!account.over() && !account.spares(2 * bytes_of(&memo.slots)));
assert_eq!(
memo.insert(&key(0, &[1000]), entry, &account),
Inserted::Full
);
memo.clear();
assert_eq!(
memo.insert(&key(0, &[1000]), entry, &account),
Inserted::Done
);
assert_eq!(memo.peak(), fitted);
let mut starved = Memo::new(100);
assert_eq!(
starved.insert(&key(0, &[0]), entry, &Account::new(Some(100))),
Inserted::NoRoom
);
}
#[test]
fn records() {
let account = Account::new(None);
let mut memo = Memo::with_chunk(1000, 64);
let long: Vec<u32> = (0..100).collect();
let keys: Vec<Key> = (0..3)
.flat_map(|round| {
let long = &long;
(0..60u32).map(move |n| match n {
0 => key(round, long),
1 => key(round, &[7 | REPEATED, 2]),
2 => key(round, &[]),
_ => key(round, &(0..=n % 9).map(|m| m * 3 + n).collect::<Vec<_>>()),
})
})
.collect();
for _ in 0..2 {
for (i, key) in keys.iter().enumerate() {
memo.insert(key, Entry::Failed(Failure::Exhausted(i as u32)), &account);
}
for (i, key) in keys.iter().enumerate() {
assert_eq!(
memo.get(key, 0),
Some(Entry::Failed(Failure::Exhausted(i as u32)))
);
}
assert_eq!(memo.get(&key(0, &[7]), 0), None);
assert_eq!(memo.get(&key(3, &[7, 7]), 0), None);
assert_eq!(memo.get(&key(0, &long[1..]), 0), None);
memo.clear();
assert_eq!(memo.get(&keys[1], 0), None);
}
assert!(memo.chunks.iter().any(|chunk| chunk.capacity() > 64));
assert_eq!(
account.used() as usize,
held(&memo),
"every chunk as charged"
);
let mut memo = Memo::with_chunk(1000, 64);
let account = Account::new(None);
memo.insert(&key(0, &[1]), Entry::Failed(Failure::Complete), &account);
memo.clear();
let entry = Entry::Failed(Failure::Exhausted(2));
memo.insert(&key(0, &long), entry, &account);
assert_eq!(memo.get(&key(0, &long), 0), Some(entry));
assert_eq!(memo.chunks.len(), 1);
assert_eq!(memo.chunks[0].capacity(), HEADER + long.len());
assert_eq!(account.used() as usize, held(&memo));
for theta in 0..30 {
memo.insert(&key(theta, &[]), entry, &account);
}
assert_eq!(memo.get(&key(29, &[]), 0), Some(entry));
assert_eq!(account.used() as usize, held(&memo));
}
fn held(memo: &Memo) -> usize {
bytes_of(&memo.slots) + memo.chunks.iter().map(bytes_of).sum::<usize>()
}
#[test]
fn a_key_is_its_words() {
let account = Account::new(None);
let mut memo = Memo::new(10);
let (own, member, zone) = (key(1, &[1, 2]), key(1, &[1, 3]), key(2, &[1, 2]));
let proved = Entry::Proved(NodeId::new(1));
memo.insert_hashed(own.zones(), 7, proved, &account);
assert_eq!(memo.get_hashed(own.zones(), 7, 0), Some(proved));
assert_eq!(memo.get_hashed(member.zones(), 7, 0), None);
assert_eq!(memo.get_hashed(zone.zones(), 7, 0), None);
assert!(own.zones().of(&own));
assert!(!member.zones().of(&own) && !zone.zones().of(&own));
}
#[cfg(feature = "parallel")]
#[test]
fn a_shared_memo_gives_everything_back() {
let account = Account::new(None);
let shared = Shared::new(100, 100);
for o in 0..50 {
let key = key(0, &[o]);
let complete = Entry::Failed(Failure::Complete);
shared.insert(key.zones(), key.zones().hash(), complete, &account);
}
Table::Shared(&shared).intern(&OccSet::of(64, [OccId::new(3)]), &account);
assert!(account.used() > 0);
shared.release(&account);
assert_eq!(account.used(), 0);
}
#[test]
fn interned_zones() {
let account = Account::new(None);
let zone = |members: &[u32]| OccSet::of(200, members.iter().map(|&o| OccId::new(o)));
let mut zones = Interner::new(2);
let a = zones.intern(&zone(&[1, 150]), &account);
let set = size_of_val(zone(&[1]).words());
let first = 4 * (size_of::<(OccSet, u64)>() + 1) + 16;
assert_eq!(account.used() as usize, set + first);
let b = zones.intern(&zone(&[1]), &account);
assert_ne!(a, b);
assert_eq!(zones.intern(&zone(&[1, 150]), &account), a);
assert_eq!(account.used() as usize, 2 * set + first);
let c = zones.intern(&zone(&[2]), &account);
assert!(![a, b].contains(&c), "a full table empties itself");
assert_ne!(zones.intern(&zone(&[1]), &account), b);
zones.release(&account);
assert_eq!(account.used(), 0);
assert!(zones.intern(&zone(&[1, 150]), &account) > c);
let mut none = Interner::new(0);
let first = none.intern(&zone(&[1]), &account);
assert_ne!(none.intern(&zone(&[1]), &account), first);
let bounded = Account::new(Some(4096));
let mut zones = Interner::new(1000);
let kept = (0..200)
.filter(|&o| {
zones.intern(&zone(&[o]), &bounded);
assert!(bounded.spares(0), "{} bytes held", bounded.used());
zones.ids.contains_key(&zone(&[o]))
})
.count();
assert!((8..100).contains(&kept), "{kept} zones kept");
}
}