use crate::LruCache;
use crate::entry::EntryPtr;
use std::iter::FusedIterator;
use std::marker::PhantomData;
pub struct Iter<'a, K, V> {
next: EntryPtr<K, V>,
next_back: EntryPtr<K, V>,
lifetime: PhantomData<&'a ()>
}
impl<'a, K, V> Iter<'a, K, V> {
pub(crate) fn new<S>(cache: &LruCache<K, V, S>) -> Iter<K, V> {
if cache.is_empty() {
Iter {
next: unsafe { EntryPtr::null() },
next_back: unsafe { EntryPtr::null() },
lifetime: PhantomData
}
}
else {
Iter {
next: cache.seal.get().prev,
next_back: cache.seal.get().next,
lifetime: PhantomData
}
}
}
}
impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<(&'a K, &'a V)> {
if self.next.is_null() {
None
}
else {
let entry = unsafe { self.next.get_extended() };
if self.next == self.next_back {
self.next = unsafe { EntryPtr::null() };
}
else {
self.next = entry.prev;
}
unsafe { Some((entry.key(), entry.value())) }
}
}
}
impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Iter<'a, K, V> {
fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
if self.next.is_null() {
None
}
else {
let entry = unsafe { self.next_back.get_extended() };
if self.next_back == self.next {
self.next = unsafe { EntryPtr::null() };
}
else {
self.next_back = entry.next;
}
unsafe { Some((entry.key(), entry.value())) }
}
}
}
impl<'a, K: 'a, V: 'a> FusedIterator for Iter<'a, K, V> { }
pub struct Keys<'a, K, V> {
iter: Iter<'a, K, V>
}
impl<'a, K, V> Keys<'a, K, V> {
pub(crate) fn new<S>(cache: &'a LruCache<K, V, S>) -> Keys<'a, K, V> {
Keys {
iter: Iter::new(cache)
}
}
}
impl<'a, K: 'a, V: 'a> Iterator for Keys<'a, K, V> {
type Item = &'a K;
fn next(&mut self) -> Option<&'a K> {
self.iter.next().map(|(k, _)| k)
}
}
impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Keys<'a, K, V> {
fn next_back(&mut self) -> Option<&'a K> {
self.iter.next_back().map(|(k, _)| k)
}
}
impl<'a, K: 'a, V: 'a> FusedIterator for Keys<'a, K, V> { }
pub struct Values<'a, K, V> {
iter: Iter<'a, K, V>
}
impl<'a, K, V> Values<'a, K, V> {
pub(crate) fn new<S>(cache: &'a LruCache<K, V, S>) -> Values<'a, K, V> {
Values {
iter: Iter::new(cache)
}
}
}
impl<'a, K: 'a, V: 'a> Iterator for Values<'a, K, V> {
type Item = &'a V;
fn next(&mut self) -> Option<&'a V> {
self.iter.next().map(|(_, v)| v)
}
}
impl<'a, K: 'a, V: 'a> DoubleEndedIterator for Values<'a, K, V> {
fn next_back(&mut self) -> Option<&'a V> {
self.iter.next_back().map(|(_, v)| v)
}
}
impl<'a, K: 'a, V: 'a> FusedIterator for Values<'a, K, V> { }
struct TakingIterator<K, V> {
next: EntryPtr<K, V>,
next_back: EntryPtr<K, V>,
}
impl<K, V> TakingIterator<K, V> {
fn new<S>(cache: &LruCache<K, V, S>) -> TakingIterator<K, V> {
if cache.is_empty() {
TakingIterator {
next: unsafe { EntryPtr::null() },
next_back: unsafe { EntryPtr::null() }
}
}
else {
TakingIterator {
next: cache.seal.get().prev,
next_back: cache.seal.get().next
}
}
}
}
impl<K, V> Iterator for TakingIterator<K, V> {
type Item = (K, V);
fn next(&mut self) -> Option<(K, V)> {
if self.next.is_null() {
None
}
else {
unsafe {
let entry = self.next.read();
if self.next == self.next_back {
self.next = EntryPtr::null();
}
else {
self.next = entry.prev;
}
Some(entry.into_key_value())
}
}
}
}
impl<K, V> DoubleEndedIterator for TakingIterator<K, V> {
fn next_back(&mut self) -> Option<(K, V)> {
if self.next.is_null() {
None
}
else {
unsafe {
let entry = self.next_back.read();
if self.next_back == self.next {
self.next = EntryPtr::null();
}
else {
self.next_back = entry.next;
}
Some(entry.into_key_value())
}
}
}
}
pub struct Drain<'a, K, V, S> {
iterator: TakingIterator<K, V>,
cache: &'a mut LruCache<K, V, S>
}
impl<'a, K, V, S> Drain<'a, K, V, S> {
pub(crate) fn new(cache: &'a mut LruCache<K, V, S>) -> Drain<'a, K, V, S> {
Drain {
iterator: TakingIterator::new(cache),
cache
}
}
}
impl<'a, K, V, S> Iterator for Drain<'a, K, V, S> {
type Item = (K, V);
fn next(&mut self) -> Option<(K, V)> {
self.iterator.next()
}
}
impl<'a, K, V, S> DoubleEndedIterator for Drain<'a, K, V, S> {
fn next_back(&mut self) -> Option<(K, V)> {
self.iterator.next_back()
}
}
impl<'a, K, V, S> Drop for Drain<'a, K, V, S> {
fn drop(&mut self) {
for _ in self.by_ref() { }
self.cache.seal.get_mut().next = self.cache.seal;
self.cache.seal.get_mut().prev = self.cache.seal;
self.cache.current_size = 0;
self.cache.table.clear_no_drop();
}
}
impl<'a, K, V, S> FusedIterator for Drain<'a, K, V, S> { }
pub struct IntoIter<K, V, S> {
iterator: TakingIterator<K, V>,
cache: LruCache<K, V, S>
}
impl<K, V, S> IntoIter<K, V, S> {
pub(crate) fn new(cache: LruCache<K, V, S>) -> IntoIter<K, V, S> {
IntoIter {
iterator: TakingIterator::new(&cache),
cache
}
}
}
impl<K, V, S> Iterator for IntoIter<K, V, S> {
type Item = (K, V);
fn next(&mut self) -> Option<(K, V)> {
self.iterator.next()
}
}
impl<K, V, S> DoubleEndedIterator for IntoIter<K, V, S> {
fn next_back(&mut self) -> Option<(K, V)> {
self.iterator.next_back()
}
}
impl<K, V, S> Drop for IntoIter<K, V, S> {
fn drop(&mut self) {
for _ in self.by_ref() { }
self.cache.table.clear_no_drop();
}
}
pub struct IntoKeys<K, V, S> {
into_iter: IntoIter<K, V, S>
}
impl<K, V, S> IntoKeys<K, V, S> {
pub(crate) fn new(cache: LruCache<K, V, S>) -> IntoKeys<K, V, S> {
IntoKeys {
into_iter: IntoIter::new(cache)
}
}
}
impl<K, V, S> Iterator for IntoKeys<K, V, S> {
type Item = K;
fn next(&mut self) -> Option<K> {
self.into_iter.next().map(|(k, _)| k)
}
}
impl<K, V, S> DoubleEndedIterator for IntoKeys<K, V, S> {
fn next_back(&mut self) -> Option<K> {
self.into_iter.next_back().map(|(k, _)| k)
}
}
pub struct IntoValues<K, V, S> {
into_iter: IntoIter<K, V, S>
}
impl<K, V, S> IntoValues<K, V, S> {
pub(crate) fn new(cache: LruCache<K, V, S>) -> IntoValues<K, V, S> {
IntoValues {
into_iter: IntoIter::new(cache)
}
}
}
impl<K, V, S> Iterator for IntoValues<K, V, S> {
type Item = V;
fn next(&mut self) -> Option<V> {
self.into_iter.next().map(|(_, v)| v)
}
}
impl<K, V, S> DoubleEndedIterator for IntoValues<K, V, S> {
fn next_back(&mut self) -> Option<V> {
self.into_iter.next_back().map(|(_, v)| v)
}
}
#[cfg(test)]
mod tests {
use std::sync::{Arc, Mutex};
use crate::{HeapSize, LruCache};
use crate::tests::{large_test_cache, singleton_test_cache};
#[test]
fn iter_works_for_larger_cache() {
let cache = large_test_cache();
let mut iter = cache.iter();
assert_eq!(Some((&"hello", &"world")), iter.next());
assert_eq!(Some((&"good morning", &"jupiter")), iter.next_back());
assert_eq!(Some((&"hi", &"venus")), iter.next_back());
assert_eq!(Some((&"ahoy", &"mars")), iter.next_back());
assert_eq!(Some((&"greetings", &"moon")), iter.next());
assert_eq!(None, iter.next_back());
assert_eq!(None, iter.next());
}
#[test]
fn forward_iter_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut iter = cache.iter();
assert_eq!(Some((&"hello", &"world")), iter.next());
assert_eq!(None, iter.next());
}
#[test]
fn backward_iter_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut iter = cache.iter();
assert_eq!(Some((&"hello", &"world")), iter.next_back());
assert_eq!(None, iter.next_back());
}
#[test]
fn forward_keys_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut keys = cache.keys();
assert_eq!(Some(&"hello"), keys.next());
assert_eq!(None, keys.next());
}
#[test]
fn backward_keys_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut keys = cache.keys();
assert_eq!(Some(&"hello"), keys.next_back());
assert_eq!(None, keys.next_back());
}
#[test]
fn forward_values_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut values = cache.values();
assert_eq!(Some(&"world"), values.next());
assert_eq!(None, values.next());
}
#[test]
fn backward_values_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut values = cache.values();
assert_eq!(Some(&"world"), values.next_back());
assert_eq!(None, values.next_back());
}
#[test]
fn separated_iters_zip_to_pair_iter() {
let cache = large_test_cache();
let pair_iter_collected = cache.iter().collect::<Vec<_>>();
let zip_iter_collected = cache.keys()
.zip(cache.values())
.collect::<Vec<_>>();
assert_eq!(pair_iter_collected, zip_iter_collected);
}
#[test]
fn separated_into_iters_zip_to_pair_into_iter() {
let cache = large_test_cache();
let pair_iter_collected =
cache.clone().into_iter().collect::<Vec<_>>();
let zip_iter_collected = cache.clone().into_keys()
.zip(cache.into_values())
.collect::<Vec<_>>();
assert_eq!(pair_iter_collected, zip_iter_collected);
}
#[test]
fn drain_clears_cache() {
let mut cache = LruCache::new(1024);
cache.insert("hello", "world").unwrap();
cache.insert("greetings", "moon").unwrap();
cache.drain().next();
assert_eq!(0, cache.len());
assert_eq!(0, cache.current_size());
assert!(cache.peek_lru().is_none());
assert!(cache.peek_mru().is_none());
assert!(cache.get("hello").is_none());
}
fn test_owning_iterator<I>(mut iter: I)
where
I: Iterator<Item = (&'static str, &'static str)> + DoubleEndedIterator
{
assert_eq!(Some(("hello", "world")), iter.next());
assert_eq!(Some(("good morning", "jupiter")), iter.next_back());
assert_eq!(Some(("hi", "venus")), iter.next_back());
assert_eq!(Some(("ahoy", "mars")), iter.next_back());
assert_eq!(Some(("greetings", "moon")), iter.next());
assert_eq!(None, iter.next_back());
assert_eq!(None, iter.next());
}
#[test]
fn drain_returns_entries() {
let mut cache = large_test_cache();
let drain = cache.drain();
test_owning_iterator(drain);
}
#[test]
fn into_iter_returns_entries() {
let cache = large_test_cache();
let into_iter = cache.into_iter();
test_owning_iterator(into_iter);
}
#[test]
fn forward_into_iter_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut into_iter = cache.into_iter();
assert_eq!(Some(("hello", "world")), into_iter.next());
assert_eq!(None, into_iter.next());
}
#[test]
fn backward_into_iter_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut into_iter = cache.into_iter();
assert_eq!(Some(("hello", "world")), into_iter.next_back());
assert_eq!(None, into_iter.next_back());
}
#[test]
fn forward_into_keys_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut into_keys = cache.into_keys();
assert_eq!(Some("hello"), into_keys.next());
assert_eq!(None, into_keys.next());
}
#[test]
fn backward_into_keys_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut into_keys = cache.into_keys();
assert_eq!(Some("hello"), into_keys.next_back());
assert_eq!(None, into_keys.next_back());
}
#[test]
fn forward_into_values_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut into_values = cache.into_values();
assert_eq!(Some("world"), into_values.next());
assert_eq!(None, into_values.next());
}
#[test]
fn backward_into_values_works_for_singleton_cache() {
let cache = singleton_test_cache();
let mut into_values = cache.into_values();
assert_eq!(Some("world"), into_values.next_back());
assert_eq!(None, into_values.next_back());
}
#[derive(Debug)]
struct DropObserver {
drop_counter: Arc<Mutex<u32>>
}
impl HeapSize for DropObserver {
fn heap_size(&self) -> usize {
0
}
}
impl Drop for DropObserver {
fn drop(&mut self) {
*self.drop_counter.lock().unwrap() += 1;
}
}
fn setup_cache_with_drop_counter() -> (LruCache<i32, DropObserver>, Arc<Mutex<u32>>) {
let drop_counter = Arc::new(Mutex::new(0));
let mut cache = LruCache::new(1024);
cache.insert(0, DropObserver { drop_counter: Arc::clone(&drop_counter) })
.unwrap();
cache.insert(1, DropObserver { drop_counter: Arc::clone(&drop_counter) })
.unwrap();
(cache, drop_counter)
}
#[test]
fn into_iter_drops_remaining_elements_if_dropped() {
let (cache, drop_counter) = setup_cache_with_drop_counter();
let mut into_iter = cache.into_iter();
into_iter.next();
assert_eq!(1, *drop_counter.lock().unwrap());
drop(into_iter);
assert_eq!(2, *drop_counter.lock().unwrap());
}
#[test]
fn into_keys_drops_remaining_elements_if_dropped() {
let (cache, drop_counter) = setup_cache_with_drop_counter();
let mut into_keys = cache.into_keys();
into_keys.next();
assert_eq!(1, *drop_counter.lock().unwrap());
drop(into_keys);
assert_eq!(2, *drop_counter.lock().unwrap());
}
#[test]
fn into_values_drops_remaining_elements_if_dropped() {
let (cache, drop_counter) = setup_cache_with_drop_counter();
let mut into_values = cache.into_values();
into_values.next();
assert_eq!(1, *drop_counter.lock().unwrap());
drop(into_values);
assert_eq!(2, *drop_counter.lock().unwrap());
}
#[test]
fn drain_drops_remaining_elements_if_dropped() {
let (mut cache, drop_counter) = setup_cache_with_drop_counter();
let mut drain = cache.drain();
drain.next();
assert_eq!(1, *drop_counter.lock().unwrap());
drop(drain);
assert_eq!(2, *drop_counter.lock().unwrap());
assert!(cache.is_empty());
}
fn assert_is_empty<T, I>(mut iterator: I)
where
I: Iterator<Item = T> + DoubleEndedIterator
{
assert!(iterator.next().is_none());
assert!(iterator.next_back().is_none());
}
#[test]
fn empty_cache_builds_empty_iterators() {
let mut cache: LruCache<&str, &str> = LruCache::new(1024);
assert_is_empty(cache.iter());
assert_is_empty(cache.keys());
assert_is_empty(cache.values());
assert_is_empty(cache.drain());
assert_is_empty(cache.clone().into_iter());
assert_is_empty(cache.clone().into_keys());
assert_is_empty(cache.into_values());
}
}