use std::collections::HashMap;
use std::hash::{BuildHasher, RandomState};
use std::mem::size_of;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::{Arc, Weak};
use crate::error::Error;
use crate::limits::{Charge, HASH_TABLE_SHARES, Meter, heap_cost};
const NONE: usize = usize::MAX;
pub(crate) const REGISTRY: usize = 0;
pub(crate) const FILES: usize = 1;
#[derive(Debug)]
pub(crate) struct Flag {
set: AtomicBool,
id: usize,
next: AtomicUsize,
log: Arc<Fired>,
}
impl Flag {
pub(crate) fn changed(&self) -> bool {
self.set.load(Ordering::Acquire)
}
pub(crate) fn id(&self) -> usize {
self.id
}
fn fire(&self) {
if self.set.swap(true, Ordering::AcqRel) {
return;
}
let mut head = self.log.head.load(Ordering::Acquire);
loop {
self.next.store(head, Ordering::Relaxed);
#[cfg(test)]
hook(Point::Pushing);
match self.log.head.compare_exchange_weak(
head,
self.id,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return,
Err(now) => head = now,
}
}
}
}
#[derive(Debug)]
pub(crate) struct Fired {
head: AtomicUsize,
}
pub(crate) const FLAG: u64 = heap_cost((size_of::<Flag>() + 2 * size_of::<usize>()) as u64)
+ 2 * size_of::<Arc<Flag>>() as u64;
pub(crate) const FIRED: u64 = heap_cost((size_of::<Fired>() + 2 * size_of::<usize>()) as u64)
+ heap_cost(4 * size_of::<Arc<Flag>>() as u64);
pub(crate) const WATCH_SHARE: u64 = HASH_TABLE_SHARES
* (size_of::<u64>() + size_of::<Vec<Weak<Flag>>>() + 1) as u64
+ 2 * (size_of::<Weak<Flag>>() + size_of::<u64>()) as u64;
#[derive(Debug, Default)]
pub(crate) struct Table {
map: HashMap<u64, Vec<Weak<Flag>>>,
room: usize,
}
impl Table {
pub(crate) fn notify(&mut self, hash: u64) {
let Some(flags) = self.map.remove(&hash) else {
return;
};
for flag in flags {
if let Some(flag) = flag.upgrade() {
#[cfg(test)]
hook(Point::Upgraded);
flag.fire();
}
}
}
fn add(&mut self, hashes: &[u64], flag: &Arc<Flag>) {
for &h in hashes {
self.map.entry(h).or_default().push(Arc::downgrade(flag));
}
self.room = self.room.max(self.map.capacity());
}
fn end(&mut self, hashes: &[u64], mine: &Arc<Fired>) {
for h in hashes {
if let Some(flags) = self.map.get_mut(h) {
flags.retain(|f| f.upgrade().is_some_and(|f| !Arc::ptr_eq(&f.log, mine)));
if flags.is_empty() {
self.map.remove(h);
} else if flags.capacity() > 2 * flags.len() + 4 {
flags.shrink_to(2 * flags.len());
}
}
}
let len = self.map.len();
if self.room > 3 * len + 8 {
self.map.shrink_to(len);
self.room = self.map.capacity();
}
}
#[cfg(test)]
pub(crate) fn room(&self) -> (usize, usize, Vec<(usize, usize)>) {
let lists = self.map.values().map(|l| (l.len(), l.capacity())).collect();
(self.map.len(), self.room, lists)
}
}
pub(crate) trait Under: Sync {
fn with_table(&self, f: &mut dyn FnMut(&mut Table));
}
#[derive(Debug, Default)]
pub(crate) struct Watches {
state: RandomState,
#[cfg(test)]
walks: AtomicUsize,
}
impl Watches {
pub(crate) fn start<'a>(&'a self, meter: &Arc<Meter>, locks: [&'a dyn Under; 2]) -> Walk<'a> {
#[cfg(test)]
self.walks.fetch_add(1, Ordering::SeqCst);
Walk {
watches: self,
locks,
hashes: [Vec::new(), Vec::new()],
log: None,
flags: Vec::new(),
charge: Charge::zero(meter),
}
}
pub(crate) fn hash(&self, key: &[u8]) -> u64 {
self.state.hash_one(key)
}
#[cfg(test)]
pub(crate) fn walks(&self) -> usize {
self.walks.load(Ordering::SeqCst)
}
}
pub(crate) struct Walk<'a> {
watches: &'a Watches,
locks: [&'a dyn Under; 2],
hashes: [Vec<u64>; 2],
log: Option<Arc<Fired>>,
flags: Vec<Arc<Flag>>,
charge: Charge,
}
impl Walk<'_> {
pub(crate) fn hash(&self, key: &[u8]) -> u64 {
self.watches.hash(key)
}
pub(crate) fn watch(&mut self, keys: &[(usize, u64)]) -> Result<Arc<Flag>, Error> {
let n = u64::try_from(keys.len()).unwrap_or(u64::MAX);
let first = if self.log.is_none() { FIRED } else { 0 };
self.charge.grow(
WATCH_SHARE
.saturating_mul(n)
.saturating_add(FLAG)
.saturating_add(first),
)?;
let log = self
.log
.get_or_insert_with(|| {
Arc::new(Fired {
head: AtomicUsize::new(NONE),
})
})
.clone();
let flag = Arc::new(Flag {
set: AtomicBool::new(false),
id: self.flags.len(),
next: AtomicUsize::new(NONE),
log,
});
self.flags.push(flag.clone());
for (at, (lock, mine)) in self.locks.iter().zip(&mut self.hashes).enumerate() {
let start = mine.len();
mine.extend(keys.iter().filter(|(l, _)| *l == at).map(|(_, h)| *h));
if let Some(added) = mine.get(start..).filter(|a| !a.is_empty()) {
lock.with_table(&mut |t| t.add(added, &flag));
}
}
Ok(flag)
}
pub(crate) fn fired(&self) -> impl Iterator<Item = usize> + '_ {
let mut at = self
.log
.as_ref()
.map_or(NONE, |l| l.head.swap(NONE, Ordering::AcqRel));
std::iter::from_fn(move || {
let id = at;
at = self.flags.get(id)?.next.load(Ordering::Acquire);
Some(id)
})
}
#[cfg(test)]
pub(crate) fn charged(&self) -> u64 {
self.charge.bytes()
}
#[cfg(test)]
pub(crate) fn flags_room(&self) -> usize {
self.flags.capacity()
}
}
impl Drop for Walk<'_> {
fn drop(&mut self) {
if let Some(log) = &self.log {
for at in [REGISTRY, FILES] {
let (Some(lock), Some(hashes)) = (self.locks.get(at), self.hashes.get_mut(at))
else {
continue;
};
if hashes.is_empty() {
continue;
}
hashes.sort_unstable();
hashes.dedup();
lock.with_table(&mut |t| t.end(hashes, log));
#[cfg(test)]
hook(Point::Ended(at));
}
}
#[cfg(test)]
self.watches.walks.fetch_sub(1, Ordering::SeqCst);
}
}
#[cfg(test)]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Point {
Upgraded,
Pushing,
Ended(usize),
}
#[cfg(test)]
pub(crate) type PointFn = std::rc::Rc<dyn Fn(Point)>;
#[cfg(test)]
thread_local! {
static HOOK: std::cell::RefCell<Option<PointFn>> = const { std::cell::RefCell::new(None) };
}
#[cfg(test)]
pub(crate) fn set_hook(f: Option<PointFn>) {
HOOK.with(|h| *h.borrow_mut() = f);
}
#[cfg(test)]
fn hook(at: Point) {
let f = HOOK.with(|h| h.borrow().clone());
if let Some(f) = f {
f(at);
}
}
#[cfg(test)]
mod tests;