tor-browser

freelist.rs (7682B)

---

/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

//! A generic backing store for caches.
//!
//! `FreeList` is a simple vector-backed data structure where each entry in the
//! vector contains an Option<T>. It maintains an index-based (rather than
//! pointer-based) free list to efficiently locate the next unused entry. If all
//! entries are occupied, insertion appends a new element to the vector.
//!
//! It also supports both strong and weak handle semantics. There is exactly one
//! (non-Clonable) strong handle per occupied entry, which must be passed by
//! value into `free()` to release an entry. Strong handles can produce an
//! unlimited number of (Clonable) weak handles, which are used to perform
//! lookups which may fail of the entry has been freed. A per-entry epoch ensures
//! that weak handle lookups properly fail even if the entry has been freed and
//! reused.
//!
//! TODO(gw): Add an occupied list head, for fast iteration of the occupied list
//! to implement retain() style functionality.

use std::{fmt, u32};
use std::marker::PhantomData;

#[derive(Debug, Copy, Clone, MallocSizeOf, PartialEq)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct Epoch(u32);

impl Epoch {
   /// Mints a new epoch.
   ///
   /// We start at 1 so that 0 is always an invalid epoch.
   fn new() -> Self {
       Epoch(1)
   }

   /// Returns an always-invalid epoch.
   fn invalid() -> Self {
       Epoch(0)
   }
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
#[derive(MallocSizeOf)]
pub struct FreeListHandle<M> {
   index: u32,
   epoch: Epoch,
   _marker: PhantomData<M>,
}

/// More-compact textual representation for debug logging.
impl<M> fmt::Debug for FreeListHandle<M> {
   fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
       f.debug_struct("StrongHandle")
           .field("index", &self.index)
           .field("epoch", &self.epoch.0)
           .finish()
   }
}

impl<M> FreeListHandle<M> {
   pub fn weak(&self) -> WeakFreeListHandle<M> {
       WeakFreeListHandle {
           index: self.index,
           epoch: self.epoch,
           _marker: PhantomData,
       }
   }

   pub fn invalid() -> Self {
       Self {
           index: 0,
           epoch: Epoch::invalid(),
           _marker: PhantomData,
       }
   }

   /// Returns true if this handle and the supplied weak handle reference
   /// the same underlying location in the freelist.
   pub fn matches(&self, weak_handle: &WeakFreeListHandle<M>) -> bool {
       self.index == weak_handle.index &&
       self.epoch == weak_handle.epoch
   }
}

impl<M> Clone for WeakFreeListHandle<M> {
   fn clone(&self) -> Self {
       WeakFreeListHandle {
           index: self.index,
           epoch: self.epoch,
           _marker: PhantomData,
       }
   }
}

impl<M> PartialEq for WeakFreeListHandle<M> {
   fn eq(&self, other: &Self) -> bool {
       self.index == other.index && self.epoch == other.epoch
   }
}

#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
#[derive(MallocSizeOf)]
pub struct WeakFreeListHandle<M> {
   index: u32,
   epoch: Epoch,
   _marker: PhantomData<M>,
}

/// More-compact textual representation for debug logging.
impl<M> fmt::Debug for WeakFreeListHandle<M> {
   fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
       f.debug_struct("WeakHandle")
           .field("index", &self.index)
           .field("epoch", &self.epoch.0)
           .finish()
   }
}

impl<M> WeakFreeListHandle<M> {
   /// Returns an always-invalid handle.
   pub fn invalid() -> Self {
       Self {
           index: 0,
           epoch: Epoch::invalid(),
           _marker: PhantomData,
       }
   }
}

#[derive(Debug, MallocSizeOf)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
struct Slot<T> {
   next: Option<u32>,
   epoch: Epoch,
   value: Option<T>,
}

#[derive(Debug, MallocSizeOf)]
#[cfg_attr(feature = "capture", derive(Serialize))]
#[cfg_attr(feature = "replay", derive(Deserialize))]
pub struct FreeList<T, M> {
   slots: Vec<Slot<T>>,
   free_list_head: Option<u32>,
   active_count: usize,
   _marker: PhantomData<M>,
}

impl<T, M> FreeList<T, M> {
   /// Mints a new `FreeList` with no entries.
   ///
   /// Triggers a 1-entry allocation.
   pub fn new() -> Self {
       // We guarantee that we never have zero entries by starting with one
       // free entry. This allows WeakFreeListHandle::invalid() to work
       // without adding any additional branches.
       let first_slot = Slot {
           next: None,
           epoch: Epoch::new(),
           value: None,
       };
       FreeList {
           slots: vec![first_slot],
           free_list_head: Some(0),
           active_count: 0,
           _marker: PhantomData,
       }
   }

   pub fn clear(&mut self) {
       self.slots.truncate(1);
       self.slots[0] = Slot {
           next: None,
           epoch: Epoch::new(),
           value: None,
       };
       self.free_list_head = Some(0);
       self.active_count = 0;
   }

   #[allow(dead_code)]
   pub fn get(&self, id: &FreeListHandle<M>) -> &T {
       self.slots[id.index as usize].value.as_ref().unwrap()
   }

   #[allow(dead_code)]
   pub fn get_mut(&mut self, id: &FreeListHandle<M>) -> &mut T {
       self.slots[id.index as usize].value.as_mut().unwrap()
   }

   pub fn get_opt(&self, id: &WeakFreeListHandle<M>) -> Option<&T> {
       let slot = &self.slots[id.index as usize];
       if slot.epoch == id.epoch {
           slot.value.as_ref()
       } else {
           None
       }
   }

   pub fn get_opt_mut(&mut self, id: &WeakFreeListHandle<M>) -> Option<&mut T> {
       let slot = &mut self.slots[id.index as usize];
       if slot.epoch == id.epoch {
           slot.value.as_mut()
       } else {
           None
       }
   }

   pub fn insert(&mut self, item: T) -> FreeListHandle<M> {
       self.active_count += 1;

       match self.free_list_head {
           Some(free_index) => {
               let slot = &mut self.slots[free_index as usize];

               // Remove from free list.
               self.free_list_head = slot.next;
               slot.next = None;
               slot.value = Some(item);

               FreeListHandle {
                   index: free_index,
                   epoch: slot.epoch,
                   _marker: PhantomData,
               }
           }
           None => {
               let index = self.slots.len() as u32;
               let epoch = Epoch::new();

               self.slots.push(Slot {
                   next: None,
                   epoch,
                   value: Some(item),
               });

               FreeListHandle {
                   index,
                   epoch,
                   _marker: PhantomData,
               }
           }
       }
   }

   pub fn free(&mut self, id: FreeListHandle<M>) -> T {
       self.active_count -= 1;
       let slot = &mut self.slots[id.index as usize];
       slot.next = self.free_list_head;
       slot.epoch = Epoch(slot.epoch.0 + 1);
       self.free_list_head = Some(id.index);
       slot.value.take().unwrap()
   }

   #[allow(dead_code)]
   pub fn len(&self) -> usize {
       self.active_count
   }
}