chess/
cache_table.rs

1#[derive(Copy, Clone, PartialEq, PartialOrd)]
2struct CacheTableEntry<T: Copy + Clone + PartialEq + PartialOrd> {
3	hash: u64,
4	entry: T,
5}
6
7/// Store a cache of entries, each with an associated hash.
8pub struct CacheTable<T: Copy + Clone + PartialEq + PartialOrd> {
9	table: Box<[CacheTableEntry<T>]>,
10	mask: usize,
11}
12
13impl<T: Copy + Clone + PartialEq + PartialOrd> CacheTable<T> {
14	/// Create a new `CacheTable` with each associated entry initialized with a hash of '0'
15	/// Note: You must pass in a size where only 1 bit is set. (AKA: 2, 4, 8, 16, 1024, 65536,
16	/// etc.)
17	/// Panics when size is invalid.
18	#[inline]
19	pub fn new(size: usize, default: T) -> CacheTable<T> {
20		if size.count_ones() != 1 {
21			panic!("You cannot create a CacheTable with a non-binary number.");
22		}
23		let values = vec![CacheTableEntry { hash: 0, entry: default }; size];
24		CacheTable { table: values.into_boxed_slice(), mask: size - 1 }
25	}
26
27	/// Get a particular entry with the hash specified
28	#[inline]
29	pub fn get(&self, hash: u64) -> Option<T> {
30		let entry = unsafe { *self.table.get_unchecked((hash as usize) & self.mask) };
31		if entry.hash == hash { Some(entry.entry) } else { None }
32	}
33
34	/// Add (or overwrite) an entry with the associated hash
35	#[inline]
36	pub fn add(&mut self, hash: u64, entry: T) {
37		let e = unsafe { self.table.get_unchecked_mut((hash as usize) & self.mask) };
38		*e = CacheTableEntry { hash, entry };
39	}
40
41	/// Replace an entry in the hash table with a user-specified replacement policy specified by
42	/// `replace`. The `replace` closure is called with the previous entry occupying the hash table
43	/// slot, and returns true or false to specify whether the entry should be replaced. Note that
44	/// the previous entry may not have the same hash, but merely be the default initialization or
45	/// a hash collision with `hash`.
46	///
47	/// ```
48	/// use chess::CacheTable;
49	///
50	/// # fn main() {
51	///
52	/// let mut table: CacheTable<char> = CacheTable::new(256, 'a');
53	///
54	/// assert_eq!(table.get(5), None);
55	/// // Note that 'a' is the default initialization value.
56	/// table.replace_if(5, 'b', |old_entry| old_entry != 'a');
57	/// assert_eq!(table.get(5), None);
58	/// table.replace_if(5, 'c', |old_entry| old_entry == 'a');
59	/// assert_eq!(table.get(5), Some('c'));
60	/// table.replace_if(5, 'd', |old_entry| old_entry == 'c');
61	/// assert_eq!(table.get(5), Some('d'));
62	///
63	/// # }
64	/// ```
65	#[inline(always)]
66	pub fn replace_if<F: Fn(T) -> bool>(&mut self, hash: u64, entry: T, replace: F) {
67		let e = unsafe { self.table.get_unchecked_mut((hash as usize) & self.mask) };
68		if replace(e.entry) {
69			*e = CacheTableEntry { hash, entry };
70		}
71	}
72}
chess/cache_table.rs

chess/
cache_table.rs
