qlrumap 0.1.0

//! The `LruMap` is a data structure that mimics a small subset of the standard
//! `HashMap` but with the added feature that it keeps track of the least
//! recently used nodes and optionally supports setting a Time-To-Live duration
//! which can be used to drain nodes that have timed out.
//!
//! # Internals
//! The `LruMap` is implemented on top of [`hashbrown`]'s [`RawTable`].  The
//! _least recently used_ property is implemented using a manually maintained
//! doubly linked list.
//!
//! ## Structure
//! Simplified, the `LruMap` internally keeps track of the LRU linked list and
//! the hash table.
//!
//! _Keys_ in the `LruMap` are handled no different than in a regular
//! `HashMap`, but the application _values_ are wrapped in a `LruNode`, which
//! are nodes in the linked list.
//!
//! This allows the `LruMap` to [whenever the application looks up value using
//! a key] quickly (it only needs to update the link pointers) move the
//! corresponding value's node to the beginning of the LRU list.
//!
//! Sometimes it's necessary to access a map entry (key, value) with an LRU
//! node as a starting point (such as when removing the oldest node), which
//! involved finding the matching (key, value) entry given the value.  One
//! solution would be to scan the entire internal `RawTable` for the `LruNode`
//! pointer, but for a large table this could be slow.  To speed this up the
//! `LruNode` stores its _key hash_, allowing it to use [`RawTable::find()`] to
//! search only the keys with the matching hash.

use std::{
  alloc::{alloc, dealloc, Layout},
  borrow::Borrow,
  hash::Hash,
  iter::FusedIterator,
  marker::PhantomData,
  mem::ManuallyDrop,
  time::Duration
};

use hashbrown::raw::{RawIter, RawTable};

pub type DefaultHashBuilder = ahash::RandomState;

#[cfg(not(feature = "sn_fake_clock"))]
use std::time::Instant;

#[cfg(feature = "sn_fake_clock")]
use sn_fake_clock::FakeClock as Instant;


#[cfg_attr(feature = "inline-more", inline)]
pub(crate) fn make_hasher<K, Q, V>(
  hash_builder: &DefaultHashBuilder
) -> impl Fn(&(Q, V)) -> u64 + '_
where
  K: Borrow<Q>,
  Q: Hash
{
  move |val| make_hash::<K, Q>(hash_builder, &val.0)
}


#[cfg_attr(feature = "inline-more", inline)]
#[allow(clippy::extra_unused_type_parameters)]
pub(crate) fn make_hash<K, Q>(
  hash_builder: &DefaultHashBuilder,
  val: &Q
) -> u64
where
  K: Borrow<Q>,
  Q: Hash + ?Sized
{
  hash_builder.hash_one(val)
}

#[cfg_attr(feature = "inline-more", inline)]
fn equivalent_key<Q, K, V>(k: &Q) -> impl Fn(&(K, V)) -> bool + '_
where
  K: Borrow<Q>,
  Q: ?Sized + Eq
{
  move |x| k.eq(x.0.borrow())
}

#[cfg_attr(feature = "inline-more", inline)]
pub(crate) fn make_insert_hash<K>(
  hash_builder: &DefaultHashBuilder,
  val: &K
) -> u64
where
  K: Hash
{
  hash_builder.hash_one(val)
}


/// A node in the LRU list.
struct LruNode<V> {
  /// Link to the next (older) node.
  next: *mut LruNode<V>,

  /// Link to the previous (younger) node.
  prev: *mut LruNode<V>,

  /// The absolute time when this node expires.
  /// If `std::time::Instant::now() > timeout` then the node has expired.
  timeout: Instant,

  /// The key's hash.
  keyhash: u64,

  /// Where the map's owned values are stored.
  value: ManuallyDrop<V>
}


/// Internal representation of the `LruMap`.
struct InnerLruMap<K, V>
where
  K: Eq + Hash
{
  /// The hash builder used to generate key hashes.
  hash_builder: DefaultHashBuilder,

  /// `hashbrown`'s internal storage.
  table: RawTable<(K, *mut LruNode<V>)>,

  marker: PhantomData<LruNode<V>>,

  /// The least recently used (youngest) node.
  lru_head: *mut LruNode<V>,

  /// The oldest node.
  lru_tail: *mut LruNode<V>
}


impl<K, V> InnerLruMap<K, V>
where
  K: Eq + Hash
{
  /// Unlink a node from the chain of nodes.
  ///
  /// Updates head/tail pointers as needed.
  ///
  /// It is the responsibility of the caller to ensure that the node is
  /// removed from the `RawTable` as well.
  fn unlink_node(&mut self, n: *mut LruNode<V>) {
    //
    // Check if the node is the head
    //
    if n == self.lru_head {
      // Set the chain head to the "next" entry.  Note that "next" can be null,
      // in case this is the final node.
      self.lru_head = unsafe { (*self.lru_head).next };
      if self.lru_head.is_null() {
        // No head remains, which means the list is empty, so the tail must be
        // set to null as well.
        self.lru_tail = std::ptr::null_mut();
      } else {
        // There's still a head -- make sure it doesn't link back to anythhing.
        unsafe {
          (*self.lru_head).prev = std::ptr::null_mut();
        }
      }

      return;
    }

    //
    // Check if the node is the tail
    //
    if n == self.lru_tail {
      // Note: Don't need to handle the case that this is the only node, since
      //       it is handled in the head case above.

      // Make the previous second-to-last node the new tail
      self.lru_tail = unsafe { (*self.lru_tail).prev };
      unsafe {
        // Make new tail it doesn't link forward to anything.
        (*self.lru_tail).next = std::ptr::null_mut();
      }

      return;
    }

    //
    // If this point is reached the node is neither the head nor tail
    //

    // Make next node point back to previous node and previous node point to
    // next node.
    unsafe {
      (*(*n).prev).next = (*n).next;
      (*(*n).next).prev = (*n).prev;
    }
  }

  /// Given a node in the lru list, move the node to the beginning of the list.
  fn move_to_front(&mut self, n: *mut LruNode<V>) {
    // Special case: If this node is already the head then just return
    if n == self.lru_head {
      return;
    }

    // Special case: This is the last node
    // Note: This is not lru_head, because the that has already been checked
    //       above.
    if n == self.lru_tail {
      unsafe {
        // Make the second-to last node the new tail.
        self.lru_tail = (*n).prev;

        // Terminate the new last node
        (*self.lru_tail).next = std::ptr::null_mut();

        // Point node to the old head
        (*n).next = self.lru_head;

        // Make the old head point back to new head
        (*(*n).next).prev = n;

        // Make node the new head
        self.lru_head = n;

        // Node is now head, and thus must have a null previous pointer
        (*n).prev = std::ptr::null_mut();
      }
      return;
    }

    // Neither head nor tail
    unsafe {
      // Make sure n's previous node points to n's next, and n's next points
      // to n's previous.
      (*(*n).prev).next = (*n).next;
      (*(*n).next).prev = (*n).prev;

      // Make old head link back to n
      (*self.lru_head).prev = n;

      // Make n link forward to old head, and n not link backward
      (*n).next = self.lru_head;
      (*n).prev = std::ptr::null_mut();

      // Make n the new head
      self.lru_head = n;
    }
  }


  /// Remove an hash table entry by a node.
  ///
  /// The key's hash is taken from the supplied node.
  fn remove_by_node_ptr(
    &mut self,
    node: *mut LruNode<V>
  ) -> Option<(K, *mut LruNode<V>)> {
    let hash = unsafe { (*node).keyhash };
    match self.table.find(hash, |(_k, n)| node == *n) {
      Some(bucket) => {
        self.unlink_node(node);
        Some(unsafe { self.table.remove(bucket).0 })
      }
      None => None
    }
  }


  /// Remove key/value pair from the inner table.
  ///
  /// The `LruNode` is unlinked.
  #[cfg_attr(feature = "inline-more", inline)]
  fn remove<Q>(&mut self, k: &Q) -> Option<(K, *mut LruNode<V>)>
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    let hash = make_hash::<K, Q>(&self.hash_builder, k);
    if let Some((k, n)) = self.table.remove_entry(hash, equivalent_key(k)) {
      self.unlink_node(n);
      Some((k, n))
    } else {
      None
    }
  }
}


/// A `HashMap` which maintains an internal least recently used nodes list.
pub struct LruMap<K, V>
where
  K: Eq + Hash
{
  inner: InnerLruMap<K, V>,

  /// Time-To-Live for `HashMap` entries.
  ttl: Option<Duration>
}

#[expect(clippy::non_send_fields_in_send_ty)]
unsafe impl<K, V> Send for LruMap<K, V> where K: Hash + Eq {}

unsafe impl<K, V> Sync for LruMap<K, V> where K: Hash + Eq {}


impl<K, V> LruMap<K, V>
where
  K: Eq + Hash
{
  /// Create a new LRU `HashMap`, without node expiry TTL.
  #[must_use]
  pub fn new() -> Self {
    Self {
      inner: InnerLruMap {
        hash_builder: DefaultHashBuilder::default(),
        table: RawTable::new(),
        marker: PhantomData,
        lru_head: std::ptr::null_mut(),
        lru_tail: std::ptr::null_mut()
      },
      ttl: None
    }
  }


  /// Create a new LRU `HashMap`, with node TTL's.
  ///
  /// An `LruMap` with a TTL can call [`LruMap::drain_timedout()`] to return an
  /// iterator that will return items that have become stale.
  #[must_use]
  pub fn with_ttl(dur: Duration) -> Self {
    Self {
      inner: InnerLruMap {
        hash_builder: DefaultHashBuilder::default(),
        table: RawTable::new(),
        marker: PhantomData,
        lru_head: std::ptr::null_mut(),
        lru_tail: std::ptr::null_mut()
      },
      ttl: Some(dur)
    }
  }


  /// Return `true` if the container is empty.  Return `false` otherwise.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// assert_eq!(map.is_empty(), true);
  /// map.insert(1, 1);
  /// assert_eq!(map.is_empty(), false);
  /// ```
  #[must_use]
  pub fn is_empty(&self) -> bool {
    self.len() == 0
  }


  /// Return the number of elements in the container.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// assert_eq!(map.len(), 0);
  /// map.insert(1, 1);
  /// assert_eq!(map.len(), 1);
  /// ```
  #[must_use]
  pub fn len(&self) -> usize {
    self.inner.table.len()
  }


  /// Remove all nodes from the `LruMap`.
  pub fn clear(&mut self) {
    self.inner.table.clear();
    self.clear_lru_chain();
  }


  /// Drop the lru chain.
  ///
  /// This will properly drop all the values.
  fn clear_lru_chain(&mut self) {
    // remember head
    let mut head = self.inner.lru_head;

    // unlink chain
    self.inner.lru_head = std::ptr::null_mut();
    self.inner.lru_tail = std::ptr::null_mut();

    // release chain
    while !head.is_null() {
      // Remember the next node
      let next = unsafe { (*head).next };

      drop_node(head);

      // Set current head to the stored next node.
      // next can be null, which would mean all nodes have been released.
      head = next;
    }
  }


  /// Add a new entry to the container.  New nodes will be the least recently
  /// used node.
  ///
  /// Adding a new node:
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// assert_eq!(map.len(), 1);
  /// ```
  ///
  /// Adding an already existing key will replace the value, and return the old
  /// one:
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// // Create a new LruMap, and insert a test node, make sure length == 1.
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// assert_eq!(map.len(), 1);
  ///
  /// // Insert another value, with the same key, make sure length is
  /// // unchanged and make sure the returned value is the old value.
  /// let v = map.insert(1, 2);
  /// assert_eq!(map.len(), 1);
  /// assert_eq!(v, Some(1));
  ///
  /// // Make sure the stored value is the new value.
  /// let v = map.get(&1);
  /// assert_eq!(v, Some(&2));
  /// ```
  pub fn insert(&mut self, key: K, value: V) -> Option<V> {
    // Calculate a timeout
    let croaktime = self
      .ttl
      .map_or_else(Instant::now, |ttl| Instant::now() + ttl);

    //
    // If this key already exists then update the existing entry.  Otherwise
    // create a new LruNode for it.
    //
    if let Some((_k, n)) = self.get_inner_mut(&key) {
      //
      // The key already exist in the map; reuse the LruNode.
      //
      let n = *n;

      // Move node to front
      self.inner.move_to_front(n);

      // update nodes' timeout & value
      let v = unsafe {
        // Extract the old value so that it can be returned
        let v = ManuallyDrop::take(&mut (*n).value);

        // Store the new value
        (*n).value = ManuallyDrop::new(value);

        // Update timestamp
        (*n).timeout = croaktime;

        v
      };

      Some(v)
    } else {
      // Create a new LruNode

      // Generate key's hash
      let hash = make_insert_hash(&self.inner.hash_builder, &key);

      // Allocate node
      let layout = Layout::new::<LruNode<V>>();
      let ptr = unsafe { alloc(layout) };

      let p = ptr.cast::<LruNode<V>>();

      unsafe {
        (*p).keyhash = hash;

        if self.inner.lru_head.is_null() {
          // Have no head previously -- make this the head and tail
          (*p).next = std::ptr::null_mut();
          self.inner.lru_head = p;
          self.inner.lru_tail = p;
        } else {
          // Already have a head

          // Make new node link forward to old head
          (*p).next = self.inner.lru_head;

          // Make old head link backward to new node
          (*(*p).next).prev = p;

          // Make new node the head
          self.inner.lru_head = p;
        }
        (*p).prev = std::ptr::null_mut();
        (*p).timeout = croaktime;

        // This assignment is problematic if the value field isn't
        // ManuallyDrop, since rust will try to drop the old value (which
        // doesn't exist).
        (*p).value = ManuallyDrop::new(value);
      }

      // Insert new node into inner hash map
      self.inner.table.insert(
        hash,
        (key, p),
        make_hasher::<K, _, *mut LruNode<V>>(&self.inner.hash_builder)
      );
      None
    }
  }


  /// Given a node, make sure it's at the beginning of the lru list, and
  /// update its timeout, if a ttl is set.
  ///
  /// It is the responsibility of the caller to ensure that `n` must is a node
  /// in the lru chain.
  fn touch_node(&mut self, n: *mut LruNode<V>) {
    // Update node timeout if a ttl is used
    if let Some(ttl) = self.ttl {
      let croaktime = Instant::now() + ttl;
      unsafe {
        (*n).timeout = croaktime;
      }
    }

    self.inner.move_to_front(n);
  }


  #[inline]
  fn get_inner<Q>(&self, k: &Q) -> Option<&(K, *mut LruNode<V>)>
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    if self.inner.table.is_empty() {
      None
    } else {
      let hash = make_hash::<K, Q>(&self.inner.hash_builder, k);
      self.inner.table.get(hash, equivalent_key(k))
    }
  }


  /// Given a reference to a key return a reference to the value associated
  /// with it. The map entry will be moved to the front of the internal lru
  /// list. If the `LruMap` has a TTL configured, the node's timeout will be
  /// reset.
  #[inline]
  pub fn get<Q>(&mut self, k: &Q) -> Option<&V>
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    // Avoid `Option::map` because it bloats LLVM IR.
    match self.get_inner(k) {
      Some((_, n)) => {
        let n = unsafe { &mut *(*n) };

        self.touch_node(n);

        Some(&n.value)
      }
      None => None
    }
  }


  /// Given a reference to a key return a mutable reference to the value
  /// associated with it. The map entry will be moved to the front of the
  /// internal lru list. If the `LruMap` has a TTL configured, the node's
  /// timeout will be reset.
  #[cfg_attr(feature = "inline-more", inline)]
  pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    // Avoid `Option::map` because it bloats LLVM IR.
    match self.get_inner_mut(k) {
      Some(&mut (_, ref mut v)) => {
        let n = unsafe { &mut *(*v) };

        self.touch_node(n);

        Some(&mut n.value)
      }
      None => None
    }
  }


  #[inline]
  fn get_inner_mut<Q>(&mut self, k: &Q) -> Option<&mut (K, *mut LruNode<V>)>
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    if self.is_empty() {
      None
    } else {
      let hash = make_hash::<K, Q>(&self.inner.hash_builder, k);
      self.inner.table.get_mut(hash, equivalent_key(k))
    }
  }


  /// Remove a node from the map based on its key.  Returns the value if its
  /// key was found in the map.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// let v = map.remove(&1);
  /// assert_eq!(v, Some(1));
  /// assert!(map.is_empty());
  /// ```
  pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    if let Some((_k, n)) = self.inner.remove(k) {
      Some(into_node_value(n))
    } else {
      None
    }
  }


  /// Move a node to the front of the LRU list given a key.
  ///
  /// Returns `true` if the key exists in the map.  Returns `false` otherwise.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  /// assert_eq!(map.oldest(), Some((&1, &1)));
  /// map.touch(&1);
  /// assert_eq!(map.oldest(), Some((&2, &2)));
  /// ```
  pub fn touch<Q>(&mut self, k: &Q) -> bool
  where
    K: Borrow<Q>,
    Q: ?Sized + Hash + Eq
  {
    self.get(k).is_some()
  }


  /// Remove and return the oldest node.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  /// assert_eq!(map.pop(), Some((1, 1)));
  /// assert_eq!(map.pop(), Some((2, 2)));
  /// assert_eq!(map.pop(), None);
  /// assert!(map.is_empty());
  /// ```
  pub fn pop(&mut self) -> Option<(K, V)> {
    // Early exit if there are no nodes
    if self.is_empty() {
      return None;
    }

    // ToDo: The None case should never happen due to the is_empty() check
    // above.
    self
      .inner
      .remove_by_node_ptr(self.inner.lru_tail)
      .map(|(k, n)| (k, into_node_value(n)))
  }


  /// Remove and return the youngest node.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  /// assert_eq!(map.pop_youngest(), Some((2, 2)));
  /// assert_eq!(map.pop_youngest(), Some((1, 1)));
  /// assert_eq!(map.pop_youngest(), None);
  /// assert!(map.is_empty());
  /// ```
  pub fn pop_youngest(&mut self) -> Option<(K, V)> {
    // Early exit if there are no nodes
    if self.is_empty() {
      return None;
    }

    self
      .inner
      .remove_by_node_ptr(self.inner.lru_head)
      .map(|(k, n)| (k, into_node_value(n)))
  }


  /// Get the least recently used (youngest) node.
  ///
  /// Does not update the node's timestamp.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  /// assert_eq!(map.youngest(), Some((&2, &2)));
  /// ```
  #[must_use]
  pub fn youngest(&self) -> Option<(&K, &V)> {
    let hash = unsafe { (*self.inner.lru_head).keyhash };
    self.lookup_key(hash, self.inner.lru_head).map(|k| {
      let v: &V = unsafe { &(*self.inner.lru_head).value };
      (k, v)
    })
  }


  /// Get the oldest node.
  ///
  /// Does not update the node's timestamp.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  /// assert_eq!(map.oldest(), Some((&1, &1)));
  /// ```
  #[must_use]
  pub fn oldest(&self) -> Option<(&K, &V)> {
    let hash = unsafe { (*self.inner.lru_tail).keyhash };
    self.lookup_key(hash, self.inner.lru_tail).map(|k| {
      let v: &V = unsafe { &(*self.inner.lru_tail).value };
      (k, v)
    })
  }

  /// Given a key hash and a node pointer, return a reference to its key.
  fn lookup_key(&self, hash: u64, node: *mut LruNode<V>) -> Option<&K> {
    match self.inner.table.get(hash, |(_, n)| &node == n) {
      Some((key, _)) => Some(key),
      None => None
    }
  }

  /// Returns an iterator visiting all key-value pairs in order from
  /// youngest to oldest. The iterator element type is `(&'a K, &'a V)`.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert("a", 1);
  /// map.insert("b", 2);
  /// map.insert("c", 3);
  ///
  /// // The iterator will yield items from youngest to oldest.
  /// let mut iter = map.iter();
  /// assert_eq!(iter.next(), Some((&"c", &3)));
  /// assert_eq!(iter.next(), Some((&"b", &2)));
  /// assert_eq!(iter.next(), Some((&"a", &1)));
  /// assert_eq!(iter.next(), None);
  /// ```
  #[must_use]
  pub const fn iter(&self) -> Iter<'_, K, V> {
    Iter {
      map: self,
      node: self.inner.lru_head
    }
  }


  /// Returns a mutable iterator visiting all key-value pairs in order from
  /// youngest to oldest. The iterator element type is `(&'a K, &'a mut V)`.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert("a", 1);
  /// map.insert("b", 2);
  ///
  /// for (k, v) in map.iter_mut() {
  ///   if *k == "a" {
  ///     *v = 10;
  ///   }
  /// }
  ///
  /// assert_eq!(map.get(&"a"), Some(&10));
  /// ```
  pub const fn iter_mut(&mut self) -> IterMut<'_, K, V> {
    IterMut {
      map: self,
      node: self.inner.lru_head,
      marker: PhantomData
    }
  }


  /// Return an iterator that will yield all the elements of the `LruMap`.
  ///
  /// The iterator will remove elements from the map and return them as the
  /// iterator is progressed.  If the [`Drain`] iterator is dropped before the
  /// `LruMap` has been drained, the remaining entries will be removed.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, "elena");
  /// map.insert(2, "sully");
  /// let v: Vec<(i32, &str)> = map.drain().collect();
  /// assert!(map.is_empty());
  /// assert_eq!(v.len(), 2)
  /// ```
  pub fn drain(&mut self) -> Drain<'_, K, V> {
    Drain {
      iter: unsafe { self.inner.table.iter() },
      inner_map: &mut self.inner
    }
  }


  /// Return an iterator that will yield all the elements of the `LruMap`,
  /// ordered.
  ///
  /// The youngest node will be returned first.
  ///
  /// If the [`DrainOrdered`] iterator is dropped before the `LruMap` has been
  /// drained, the remaining entries will be removed.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, "elena");
  /// map.insert(2, "chloe");
  /// map.insert(3, "drake");
  ///
  /// // make second entry the youngest
  /// map.touch(&2);
  ///
  /// let v: Vec<(u32, &str)> = map.drain_ordered().collect();
  /// assert_eq!(v[0], (2, "chloe"));
  /// assert_eq!(v[1], (3, "drake"));
  /// assert_eq!(v[2], (1, "elena"));
  ///
  /// assert!(map.is_empty());
  /// ```
  pub const fn drain_ordered(&mut self) -> DrainOrdered<'_, K, V> {
    DrainOrdered {
      inner_map: &mut self.inner
    }
  }


  /// Drain nodes using a closure to validate notes to be drained.
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  /// map.insert(3, 3);
  /// let mut it = map.drain_filter(|k, v| {
  ///   // drain second element
  ///   *k == 2 && *v == 2
  /// });
  ///
  /// assert_eq!(it.next(), Some((2, 2)));
  /// assert_eq!(it.next(), None);
  /// drop(it);
  ///
  /// assert_eq!(map.len(), 2);
  /// assert_eq!(map.oldest(), Some((&1, &1)));
  /// assert_eq!(map.youngest(), Some((&3, &3)));
  /// ```
  #[cfg_attr(feature = "inline-more", inline)]
  pub fn drain_filter<F>(&mut self, f: F) -> DrainFilter<'_, K, V, F>
  where
    F: FnMut(&K, &mut V) -> bool
  {
    DrainFilter {
      f,
      iter: unsafe { self.inner.table.iter() },
      inner_map: &mut self.inner
    }
  }


  /// Drain entries that have timed out.
  ///
  /// To cap the number of elements in the `LruMap` and also remove stale
  /// elements in one call, use [`LruMap::drain_old()`].
  ///
  /// # Notes
  /// - The timestamp used to check if nodes have expired is generated and
  ///   stored in the iterator when it is created.  This implies that
  ///   expiration candidacy is effectively determined when `drain_timeout()`
  ///   is called, and not when the iterator's `next()` method is called.
  // ToDo: fail if ttl is not set?  Would need Result<>
  pub fn drain_timedout(&mut self) -> DrainTimedout<'_, K, V> {
    DrainTimedout {
      now: Instant::now(),
      inner_map: &mut self.inner
    }
  }


  /// Cap the number of entries in the map.
  ///
  /// Creates a draining iterator which will return the oldest entries until
  /// there are `lim` remaining entries in the map.
  ///
  /// To cap the number of elements in the `LruMap` and also remove stale
  /// elements in one call, use [`LruMap::drain_old()`].
  ///
  /// ```
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::new();
  /// map.insert(1, 1);
  /// map.insert(2, 2);
  ///
  /// let mut drain = map.drain_overflow(2);
  /// assert_eq!(drain.next(), None);
  /// drop(drain);
  ///
  /// map.insert(3, 3);
  ///
  /// let mut drain = map.drain_overflow(2);
  /// assert_eq!(drain.next(), Some((1, 1)));
  /// assert_eq!(drain.next(), None);
  /// ```
  pub fn drain_overflow(&mut self, lim: usize) -> DrainOverflow<'_, K, V> {
    let nodes = self.len();

    let remain = nodes.saturating_sub(lim);
    DrainOverflow {
      remain,
      inner_map: &mut self.inner
    }
  }


  /// Remove old entries and return them in an iterator.
  ///
  /// If the `cap` parameter is set then the oldest node will be removed
  /// until the number of elements is equal to or lower than this value.
  ///
  /// ```
  /// use std::time::Duration;
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::with_ttl(Duration::from_secs(10));
  /// map.insert(1, "elena");
  /// map.insert(2, "chloe");
  /// map.insert(3, "drake");
  ///
  /// map.touch(&1);
  /// map.touch(&2);
  ///
  /// // Limit map to 2 entries, use current time as expiry
  /// let mut drain = map.drain_old(Some(2));
  ///
  /// assert_eq!(drain.next(), Some((3, "drake")));
  /// assert_eq!(drain.next(), None);
  /// ```
  pub fn drain_old(&mut self, cap: Option<usize>) -> DrainOld<'_, K, V> {
    let nodes = self.len();

    // Calculate the remaining number of nodes to drain in order to reach
    // requested cap.
    let remain = cap.map_or(0, |lim| nodes.saturating_sub(lim));

    DrainOld {
      now: Instant::now(),
      remain,
      inner_map: &mut self.inner
    }
  }


  /// Remove old entries.
  ///
  /// If the `cap` parameter is set then the oldest node will be removed
  /// until the number of elements is equal to or lower than this value.
  ///
  /// ```
  /// use std::time::Duration;
  /// use qlrumap::LruMap;
  ///
  /// let mut map = LruMap::with_ttl(Duration::from_secs(10));
  /// map.insert(1, "elena");
  /// map.insert(2, "chloe");
  /// map.insert(3, "drake");
  ///
  /// map.touch(&1);
  /// map.touch(&2);
  ///
  /// // Limit map to 2 entries, use current time as expiry
  /// map.remove_old(Some(2));
  ///
  /// assert_eq!(map.len(), 2);
  /// ```
  pub fn remove_old(&mut self, cap: Option<usize>) {
    let nodes = self.len();

    // Calculate the remaining number of nodes to drain in order to reach
    // requested cap.
    let remain = cap.map_or(0, |lim| nodes.saturating_sub(lim));

    let drain = DrainOld {
      now: Instant::now(),
      remain,
      inner_map: &mut self.inner
    };

    // Drain to /dev/null
    //while let Some(_) = drain.next() {}
    for _ in drain {}
  }
}

impl<K, V> Default for LruMap<K, V>
where
  K: Eq + Hash
{
  fn default() -> Self {
    Self::new()
  }
}

impl<K, V> Drop for LruMap<K, V>
where
  K: Eq + Hash
{
  fn drop(&mut self) {
    // The lru chain must be manually released -- because pointers.
    self.clear_lru_chain();
  }
}


fn drop_node<T>(n: *mut LruNode<T>) {
  let layout = Layout::new::<LruNode<T>>();
  unsafe {
    if std::mem::needs_drop::<T>() {
      ManuallyDrop::drop(&mut (*n).value);
    }

    let p = n.cast::<u8>();
    dealloc(p, layout);
  }
}

/// Given a raw pointer to an [`LruNode`], extract its `T` value.
fn into_node_value<T>(n: *mut LruNode<T>) -> T {
  let v = unsafe { ManuallyDrop::take(&mut (*n).value) };

  let p = n.cast::<u8>();
  let layout = Layout::new::<LruNode<T>>();
  unsafe {
    dealloc(p, layout);
  }

  v
}

impl<'a, K, V> IntoIterator for &'a LruMap<K, V>
where
  K: Eq + Hash
{
  type Item = (&'a K, &'a V);
  type IntoIter = Iter<'a, K, V>;

  fn into_iter(self) -> Self::IntoIter {
    self.iter()
  }
}

impl<'a, K, V> IntoIterator for &'a mut LruMap<K, V>
where
  K: Eq + Hash
{
  type Item = (&'a K, &'a mut V);
  type IntoIter = IterMut<'a, K, V>;

  fn into_iter(self) -> Self::IntoIter {
    self.iter_mut()
  }
}

impl<K, V> IntoIterator for LruMap<K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);
  type IntoIter = IntoIter<K, V>;

  fn into_iter(self) -> Self::IntoIter {
    IntoIter { inner: self }
  }
}


/// A consuming iterator over the entries of an `LruMap` from youngest to
/// oldest.
pub struct IntoIter<K, V>
where
  K: Eq + Hash
{
  inner: LruMap<K, V>
}

impl<K, V> Iterator for IntoIter<K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);

  fn next(&mut self) -> Option<Self::Item> {
    self.inner.pop_youngest()
  }
}


/// An iterator over the entries of a `LruMap` from youngest to oldest.
pub struct Iter<'a, K, V>
where
  K: Eq + Hash
{
  map: &'a LruMap<K, V>,
  node: *mut LruNode<V>
}

impl<'a, K, V> Iterator for Iter<'a, K, V>
where
  K: Eq + Hash
{
  type Item = (&'a K, &'a V);

  fn next(&mut self) -> Option<Self::Item> {
    if self.node.is_null() {
      return None;
    }

    // This is safe because the iterator's lifetime is tied to the map's,
    // ensuring the node pointers are valid throughout the iteration.
    unsafe {
      let current_node = &*self.node;

      // Advance the pointer to the next node for the next iteration
      self.node = current_node.next;

      // Use the node's stored hash to look up its corresponding key in the
      // map. The value is available directly from the node.
      self
        .map
        .lookup_key(
          current_node.keyhash,
          std::ptr::from_ref(current_node).cast_mut()
        )
        .map(|key| (key, &*current_node.value))
    }
  }
}


/// A mutable iterator over the entries of a `LruMap` from youngest to oldest.
pub struct IterMut<'a, K, V>
where
  K: Eq + Hash
{
  map: &'a LruMap<K, V>,
  node: *mut LruNode<V>,
  marker: PhantomData<&'a mut LruMap<K, V>>
}

impl<'a, K, V> Iterator for IterMut<'a, K, V>
where
  K: Eq + Hash
{
  type Item = (&'a K, &'a mut V);

  fn next(&mut self) -> Option<Self::Item> {
    if self.node.is_null() {
      return None;
    }

    // This is safe because the iterator's lifetime is tied to the map's,
    // ensuring the node pointers are valid.
    unsafe {
      let current_node = &mut *self.node;

      // Advance the pointer to the next node for the next iteration.
      self.node = current_node.next;

      // The key is found via an immutable lookup on the map, while the value
      // is provided via a mutable reference from the node itself. This is safe
      // because the key and value are stored in separate locations.
      self
        .map
        .lookup_key(
          current_node.keyhash,
          std::ptr::from_mut(current_node).cast()
        )
        .map(|key| (key, &mut *current_node.value))
    }
  }
}


/// A draining [`Iterator`] that will on each iteration return ownership of
/// the key/value pair of the next entry in the map.
///
/// The order of the returned objects is determined by the internal map
/// storage.
pub struct Drain<'a, K, V>
where
  K: Eq + Hash
{
  iter: RawIter<(K, *mut LruNode<V>)>,
  inner_map: &'a mut InnerLruMap<K, V>
}

impl<K, V> Iterator for Drain<'_, K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);

  #[cfg_attr(feature = "inline-more", inline)]
  fn next(&mut self) -> Option<Self::Item> {
    unsafe {
      (self.iter).next().map(|item| {
        let (k, n) = self.inner_map.table.remove(item).0;
        self.inner_map.unlink_node(n);
        (k, into_node_value(n))
      })
    }
  }

  #[inline]
  fn size_hint(&self) -> (usize, Option<usize>) {
    (0, self.iter.size_hint().1)
  }
}

impl<K, V> Drop for Drain<'_, K, V>
where
  K: Eq + Hash
{
  #[cfg_attr(feature = "inline-more", inline)]
  fn drop(&mut self) {
    //  while let Some((_k, _v)) = self.next() {}

    for (_k, _v) in self.by_ref() {}
  }
}

impl<K, V> FusedIterator for Drain<'_, K, V> where K: Eq + Hash {}


/// A draining [`Iterator`] that will on each iteration call a closure which,
/// if it returns true, will drain (remove and return) the current key/value
/// pair.
///
/// The order of the returned objects is determined by the internal map
/// storage.
pub struct DrainFilter<'a, K, V, F>
where
  K: Eq + Hash,
  F: FnMut(&K, &mut V) -> bool
{
  f: F,
  iter: RawIter<(K, *mut LruNode<V>)>,
  inner_map: &'a mut InnerLruMap<K, V>
}

impl<K, V, F> Iterator for DrainFilter<'_, K, V, F>
where
  K: Eq + Hash,
  F: FnMut(&K, &mut V) -> bool
{
  type Item = (K, V);

  #[cfg_attr(feature = "inline-more", inline)]
  fn next(&mut self) -> Option<Self::Item> {
    unsafe {
      for item in &mut self.iter {
        let &mut (ref key, ref mut value) = item.as_mut();

        if (self.f)(key, &mut (*(*value)).value) {
          let (k, n) = self.inner_map.table.remove(item).0;
          self.inner_map.unlink_node(n);
          return Some((k, into_node_value(n)));
        }
      }
    }

    None
  }

  #[inline]
  fn size_hint(&self) -> (usize, Option<usize>) {
    (0, self.iter.size_hint().1)
  }
}

impl<K, V, F> Drop for DrainFilter<'_, K, V, F>
where
  K: Eq + Hash,
  F: FnMut(&K, &mut V) -> bool
{
  #[cfg_attr(feature = "inline-more", inline)]
  fn drop(&mut self) {
    // Make sure any remaining inner values are properly dropped
    //while let Some((_k, _v)) = self.next() {}
    for (_k, _v) in self.by_ref() {}
  }
}

impl<K, V, F> FusedIterator for DrainFilter<'_, K, V, F>
where
  K: Eq + Hash,
  F: FnMut(&K, &mut V) -> bool
{
}


pub struct DrainTimedout<'a, K, V>
where
  K: Eq + Hash
{
  now: Instant,
  inner_map: &'a mut InnerLruMap<K, V>
}

impl<K, V> Iterator for DrainTimedout<'_, K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);

  #[cfg_attr(feature = "inline-more", inline)]
  fn next(&mut self) -> Option<Self::Item> {
    unsafe {
      // Inspect the tail node, which - if not null - is the oldest node.
      let n = self.inner_map.lru_tail;

      // If lru_tail is null it means the list is empty.
      if n.is_null() {
        return None;
      }

      // If current time has passed node's timeout then remove node, otherwise
      // return None.
      // This is ok because the lru list is sorted, which means the iterator is
      // done when a non-timed out node is enocuntered.
      if self.now >= (*n).timeout {
        self
          .inner_map
          .remove_by_node_ptr(n)
          .map(|(k, n)| (k, into_node_value(n)))
      } else {
        None
      }
    }
  }
}

impl<K, V> Drop for DrainTimedout<'_, K, V>
where
  K: Eq + Hash
{
  /// When a drain iterator is dropped, make sure any remaining nodes are
  /// explicitly dropped.
  fn drop(&mut self) {
    loop {
      let n = self.inner_map.lru_tail;
      if n.is_null() {
        // container is empty
        break;
      }
      unsafe {
        if self.now >= (*self.inner_map.lru_tail).timeout {
          if let Some((_k, n)) = self.inner_map.remove_by_node_ptr(n) {
            let v = into_node_value(n);
            drop(v);
          }
        } else {
          // Rached a node which is not timed out, so abort
          break;
        }
      }
    }
  }
}

impl<K, V> FusedIterator for DrainTimedout<'_, K, V> where K: Eq + Hash {}


pub struct DrainOverflow<'a, K, V>
where
  K: Eq + Hash
{
  remain: usize,
  inner_map: &'a mut InnerLruMap<K, V>
}

impl<K, V> Iterator for DrainOverflow<'_, K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);

  #[cfg_attr(feature = "inline-more", inline)]
  fn next(&mut self) -> Option<Self::Item> {
    if self.remain == 0 {
      return None;
    }

    // Inspect the tail node, which - if not null - is the oldest node.
    let n = self.inner_map.lru_tail;

    // If lru_tail is null it means the list is empty.
    if n.is_null() {
      return None;
    }

    match self.inner_map.remove_by_node_ptr(n) {
      Some((k, n)) => {
        self.remain -= 1;
        Some((k, into_node_value(n)))
      }
      None => None
    }
  }
}

impl<K, V> Drop for DrainOverflow<'_, K, V>
where
  K: Eq + Hash
{
  fn drop(&mut self) {
    while self.remain > 0 {
      let n = self.inner_map.lru_tail;

      // If n is null it means there are no more nodes to process.  But this
      // should not be possible if remain > 0.
      debug_assert!(!n.is_null());

      if let Some((_k, n)) = self.inner_map.remove_by_node_ptr(n) {
        self.remain -= 1;
        let v = into_node_value(n);
        drop(v);
      }
    }
  }
}

impl<K, V> FusedIterator for DrainOverflow<'_, K, V> where K: Eq + Hash {}


/// Iterator that removes and returns every element in the `LruMap`.
///
/// If the iterator is dropped before the `LruMap` has been completely drained,
/// the remaining elements will be implicitly dropped.
pub struct DrainOrdered<'a, K, V>
where
  K: Eq + Hash
{
  inner_map: &'a mut InnerLruMap<K, V>
}

impl<K, V> Iterator for DrainOrdered<'_, K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);

  #[cfg_attr(feature = "inline-more", inline)]
  fn next(&mut self) -> Option<Self::Item> {
    // Inspect the head node, which - if not null - is the youngest node.
    let n = self.inner_map.lru_head;

    // If lru_head is null it means the list is empty.
    if n.is_null() {
      return None;
    }

    // Remove and return current head
    self
      .inner_map
      .remove_by_node_ptr(n)
      .map(|(k, n)| (k, into_node_value(n)))
  }
}

impl<K, V> Drop for DrainOrdered<'_, K, V>
where
  K: Eq + Hash
{
  /// When a drain iterator is dropped, make sure any remaining nodes are
  /// explicitly dropped.
  fn drop(&mut self) {
    loop {
      let n = self.inner_map.lru_head;
      if n.is_null() {
        // container is empty
        break;
      }
      if let Some((_k, n)) = self.inner_map.remove_by_node_ptr(n) {
        let v = into_node_value(n);
        drop(v);
      }
    }
  }
}

impl<K, V> FusedIterator for DrainOrdered<'_, K, V> where K: Eq + Hash {}


pub struct DrainOld<'a, K, V>
where
  K: Eq + Hash
{
  remain: usize,
  now: Instant,
  inner_map: &'a mut InnerLruMap<K, V>
}

impl<K, V> Iterator for DrainOld<'_, K, V>
where
  K: Eq + Hash
{
  type Item = (K, V);

  #[cfg_attr(feature = "inline-more", inline)]
  fn next(&mut self) -> Option<Self::Item> {
    // Inspect the tail node, which - if not null - is the oldest node.
    let n = self.inner_map.lru_tail;

    // If lru_tail is null it means the list is empty.
    if n.is_null() {
      return None;
    }

    if self.remain > 0 {
      if let Some((k, n)) = self.inner_map.remove_by_node_ptr(n) {
        self.remain -= 1;
        Some((k, into_node_value(n)))
      } else {
        // This should never be possible; remain should never reach 0 as long
        // as nodes remain.
        None
      }
    } else if self.now >= unsafe { (*n).timeout } {
      // If current time has passed node's timeout then remove node,
      // otherwise return None.
      // This is ok because the lru list is sorted, which means the iterator
      // is done when a non-timed out node is enocuntered.
      self
        .inner_map
        .remove_by_node_ptr(n)
        .map(|(k, n)| (k, into_node_value(n)))
    } else {
      None
    }
  }
}

impl<K, V> Drop for DrainOld<'_, K, V>
where
  K: Eq + Hash
{
  /// If the iterator is dropped before exhausted, implicitly drain the
  /// remainder.
  fn drop(&mut self) {
    for (_k, _v) in self.by_ref() {}
  }
}

impl<K, V> FusedIterator for DrainOld<'_, K, V> where K: Eq + Hash {}


#[cfg(test)]
mod tests {
  use super::LruMap;

  #[test]
  fn replace() {
    let mut lrumap = LruMap::<usize, usize>::new();
    lrumap.insert(1, 2);
    assert_eq!(lrumap.len(), 1);

    let o = lrumap.insert(1, 3);
    assert_eq!(lrumap.len(), 1);
    assert_eq!(o, Some(2));
    assert_eq!(lrumap.get(&1), Some(&3));
  }

  #[test]
  fn oldest() {
    let mut lrumap = LruMap::<usize, usize>::new();
    lrumap.insert(1, 2);
    lrumap.insert(2, 4);
    lrumap.insert(3, 6);
    assert_eq!(lrumap.len(), 3);

    let n = lrumap.oldest();
    assert_eq!(n, Some((&1, &2)));

    let o = lrumap.pop();
    assert_eq!(o, Some((1, 2)));
  }

  // Compile-time test -- this test does not really need to run.  It exists
  // just to ensure that the Send marker trait is implemented for LruMap.
  #[test]
  fn send() {
    let mut lrumap = LruMap::<usize, &str>::new();
    lrumap.insert(1, "elena");

    let handle = std::thread::spawn(|| {
      lrumap.insert(2, "drake");
      lrumap
    });

    let lrumap = handle.join().unwrap();

    assert_eq!(lrumap.len(), 2);
  }


  // Compile-time test -- this test does not really need to run.  It exists
  // just to ensure that the Sync marker trait is implemented for LruMap.
  #[test]
  fn sync() {
    use std::sync::Arc;

    let mut lrumap = LruMap::<usize, &str>::new();
    lrumap.insert(1, "chloe");

    let lrumap = Arc::new(lrumap);

    let _handle = std::thread::spawn({
      let lrumap = lrumap.clone();
      move || {
        let _ = lrumap.len();
      }
    });
  }
}

// vim: set ft=rust et sw=2 ts=2 sts=2 cinoptions=2 tw=79 :