diff options
Diffstat (limited to 'gfx/wr/webrender/src/freelist.rs')
| -rw-r--r-- | gfx/wr/webrender/src/freelist.rs | 264 |
1 files changed, 264 insertions, 0 deletions
diff --git a/gfx/wr/webrender/src/freelist.rs b/gfx/wr/webrender/src/freelist.rs new file mode 100644 index 0000000000..aa90aba03c --- /dev/null +++ b/gfx/wr/webrender/src/freelist.rs @@ -0,0 +1,264 @@ +/* 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 + } +} |