Struct cranelift_entity::EntityList

pub struct EntityList<T: EntityRef + ReservedValue> { /* private fields */ }

A small list of entity references allocated from a pool.

An EntityList<T> type provides similar functionality to Vec<T>, but with some important differences in the implementation:

1. Memory is allocated from a ListPool<T> instead of the global heap.
2. The footprint of an entity list is 4 bytes, compared with the 24 bytes for Vec<T>.
3. An entity list doesn’t implement Drop, leaving it to the pool to manage memory.

The list pool is intended to be used as a LIFO allocator. After building up a larger data structure with many list references, the whole thing can be discarded quickly by clearing the pool.

Safety

Entity lists are not as safe to use as Vec<T>, but they never jeopardize Rust’s memory safety guarantees. These are the problems to be aware of:

• If you lose track of an entity list, its memory won’t be recycled until the pool is cleared. This can cause the pool to grow very large with leaked lists.
• If entity lists are used after their pool is cleared, they may contain garbage data, and modifying them may corrupt other lists in the pool.
• If an entity list is used with two different pool instances, both pools are likely to become corrupted.

Entity lists can be cloned, but that operation should only be used as part of cloning the whole function they belong to. Cloning an entity list does not allocate new memory for the clone. It creates an alias of the same memory.

Entity lists cannot be hashed and compared for equality because it’s not possible to compare the contents of the list without the pool reference.

Implementation

The EntityList itself is designed to have the smallest possible footprint. This is important because it is used inside very compact data structures like InstructionData. The list contains only a 32-bit index into the pool’s memory vector, pointing to the first element of the list.

The pool is just a single Vec<T> containing all of the allocated lists. Each list is represented as three contiguous parts:

1. The number of elements in the list.
2. The list elements.
3. Excess capacity elements.

The total size of the three parts is always a power of two, and the excess capacity is always as small as possible. This means that shrinking a list may cause the excess capacity to shrink if a smaller power-of-two size becomes available.

Both growing and shrinking a list may cause it to be reallocated in the pool vector.

The index stored in an EntityList points to part 2, the list elements. The value 0 is reserved for the empty list which isn’t allocated in the vector.

Implementations

impl<T: EntityRef + ReservedValue> EntityList<T>

pub fn new() -> Self

Create a new empty list.

Examples found in repository

src/list.rs (line 279)

    pub fn from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self {
        let len = slice.len();
        if len == 0 {
            return Self::new();
        }

        let block = pool.alloc(sclass_for_length(len));
        pool.data[block] = T::new(len);
        pool.data[block + 1..=block + len].copy_from_slice(slice);

        Self {
            index: (block + 1) as u32,
            unused: PhantomData,
        }
    }

    /// Returns `true` if the list has a length of 0.
    pub fn is_empty(&self) -> bool {
        // 0 is a magic value for the empty list. Any list in the pool array must have a positive
        // length.
        self.index == 0
    }

    /// Get the number of elements in the list.
    pub fn len(&self, pool: &ListPool<T>) -> usize {
        // Both the empty list and any invalidated old lists will return `None`.
        pool.len_of(self).unwrap_or(0)
    }

    /// Returns `true` if the list is valid
    pub fn is_valid(&self, pool: &ListPool<T>) -> bool {
        // We consider an empty list to be valid
        self.is_empty() || pool.len_of(self) != None
    }

    /// Get the list as a slice.
    pub fn as_slice<'a>(&self, pool: &'a ListPool<T>) -> &'a [T] {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => &[],
            Some(len) => &pool.data[idx..idx + len],
        }
    }

    /// Get a single element from the list.
    pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
        self.as_slice(pool).get(index).cloned()
    }

    /// Get the first element from the list.
    pub fn first(&self, pool: &ListPool<T>) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            Some(pool.data[self.index as usize])
        }
    }

    /// Get the list as a mutable slice.
    pub fn as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T] {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => &mut [],
            Some(len) => &mut pool.data[idx..idx + len],
        }
    }

    /// Get a mutable reference to a single element from the list.
    pub fn get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T> {
        self.as_mut_slice(pool).get_mut(index)
    }

    /// Create a deep clone of the list, which does not alias the original list.
    pub fn deep_clone(&self, pool: &mut ListPool<T>) -> Self {
        match pool.len_of(self) {
            None => return Self::new(),
            Some(len) => {
                let src = self.index as usize;
                let block = pool.alloc(sclass_for_length(len));
                pool.data[block] = T::new(len);
                pool.data.copy_within(src..src + len, block + 1);

                Self {
                    index: (block + 1) as u32,
                    unused: PhantomData,
                }
            }
        }
    }

    /// Removes all elements from the list.
    ///
    /// The memory used by the list is put back in the pool.
    pub fn clear(&mut self, pool: &mut ListPool<T>) {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => debug_assert_eq!(idx, 0, "Invalid pool"),
            Some(len) => pool.free(idx - 1, sclass_for_length(len)),
        }
        // Switch back to the empty list representation which has no storage.
        self.index = 0;
    }

    /// Take all elements from this list and return them as a new list. Leave this list empty.
    ///
    /// This is the equivalent of `Option::take()`.
    pub fn take(&mut self) -> Self {
        mem::replace(self, Default::default())
    }

    /// Appends an element to the back of the list.
    /// Returns the index where the element was inserted.
    pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => {
                // This is an empty list. Allocate a block and set length=1.
                debug_assert_eq!(idx, 0, "Invalid pool");
                let block = pool.alloc(sclass_for_length(1));
                pool.data[block] = T::new(1);
                pool.data[block + 1] = element;
                self.index = (block + 1) as u32;
                0
            }
            Some(len) => {
                // Do we need to reallocate?
                let new_len = len + 1;
                let block;
                if is_sclass_min_length(new_len) {
                    // Reallocate, preserving length + all old elements.
                    let sclass = sclass_for_length(len);
                    block = pool.realloc(idx - 1, sclass, sclass + 1, len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
                pool.data[block + new_len] = element;
                pool.data[block] = T::new(new_len);
                len
            }
        }
    }

    /// Grow list by adding `count` reserved-value elements at the end.
    ///
    /// Returns a mutable slice representing the whole list.
    fn grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T] {
        let idx = self.index as usize;
        let new_len;
        let block;
        match pool.len_of(self) {
            None => {
                // This is an empty list. Allocate a block.
                debug_assert_eq!(idx, 0, "Invalid pool");
                if count == 0 {
                    return &mut [];
                }
                new_len = count;
                block = pool.alloc(sclass_for_length(new_len));
                self.index = (block + 1) as u32;
            }
            Some(len) => {
                // Do we need to reallocate?
                let sclass = sclass_for_length(len);
                new_len = len + count;
                let new_sclass = sclass_for_length(new_len);
                if new_sclass != sclass {
                    block = pool.realloc(idx - 1, sclass, new_sclass, len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
            }
        }
        pool.data[block] = T::new(new_len);
        &mut pool.data[block + 1..block + 1 + new_len]
    }

    /// Constructs a list from an iterator.
    pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = Self::new();
        list.extend(elements, pool);
        list
    }

pub fn from_slice(slice: &[T], pool: &mut ListPool<T>) -> Self

Create a new list with the contents initialized from a slice.

pub fn is_empty(&self) -> bool

Returns true if the list has a length of 0.

Examples found in repository

src/list.rs (line 308)

    pub fn is_valid(&self, pool: &ListPool<T>) -> bool {
        // We consider an empty list to be valid
        self.is_empty() || pool.len_of(self) != None
    }

    /// Get the list as a slice.
    pub fn as_slice<'a>(&self, pool: &'a ListPool<T>) -> &'a [T] {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => &[],
            Some(len) => &pool.data[idx..idx + len],
        }
    }

    /// Get a single element from the list.
    pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
        self.as_slice(pool).get(index).cloned()
    }

    /// Get the first element from the list.
    pub fn first(&self, pool: &ListPool<T>) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            Some(pool.data[self.index as usize])
        }
    }

pub fn len(&self, pool: &ListPool<T>) -> usize

Get the number of elements in the list.

pub fn is_valid(&self, pool: &ListPool<T>) -> bool

Returns true if the list is valid

pub fn as_slice<'a>(&self, pool: &'a ListPool<T>) -> &'a [T]

Get the list as a slice.

Examples found in repository

src/list.rs (line 322)

    pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T> {
        self.as_slice(pool).get(index).cloned()
    }

pub fn get(&self, index: usize, pool: &ListPool<T>) -> Option<T>

Get a single element from the list.

pub fn first(&self, pool: &ListPool<T>) -> Option<T>

Get the first element from the list.

pub fn as_mut_slice<'a>(&'a mut self, pool: &'a mut ListPool<T>) -> &'a mut [T]

Get the list as a mutable slice.

Examples found in repository

src/list.rs (line 345)

    pub fn get_mut<'a>(&'a mut self, index: usize, pool: &'a mut ListPool<T>) -> Option<&'a mut T> {
        self.as_mut_slice(pool).get_mut(index)
    }

    /// Create a deep clone of the list, which does not alias the original list.
    pub fn deep_clone(&self, pool: &mut ListPool<T>) -> Self {
        match pool.len_of(self) {
            None => return Self::new(),
            Some(len) => {
                let src = self.index as usize;
                let block = pool.alloc(sclass_for_length(len));
                pool.data[block] = T::new(len);
                pool.data.copy_within(src..src + len, block + 1);

                Self {
                    index: (block + 1) as u32,
                    unused: PhantomData,
                }
            }
        }
    }

    /// Removes all elements from the list.
    ///
    /// The memory used by the list is put back in the pool.
    pub fn clear(&mut self, pool: &mut ListPool<T>) {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => debug_assert_eq!(idx, 0, "Invalid pool"),
            Some(len) => pool.free(idx - 1, sclass_for_length(len)),
        }
        // Switch back to the empty list representation which has no storage.
        self.index = 0;
    }

    /// Take all elements from this list and return them as a new list. Leave this list empty.
    ///
    /// This is the equivalent of `Option::take()`.
    pub fn take(&mut self) -> Self {
        mem::replace(self, Default::default())
    }

    /// Appends an element to the back of the list.
    /// Returns the index where the element was inserted.
    pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize {
        let idx = self.index as usize;
        match pool.len_of(self) {
            None => {
                // This is an empty list. Allocate a block and set length=1.
                debug_assert_eq!(idx, 0, "Invalid pool");
                let block = pool.alloc(sclass_for_length(1));
                pool.data[block] = T::new(1);
                pool.data[block + 1] = element;
                self.index = (block + 1) as u32;
                0
            }
            Some(len) => {
                // Do we need to reallocate?
                let new_len = len + 1;
                let block;
                if is_sclass_min_length(new_len) {
                    // Reallocate, preserving length + all old elements.
                    let sclass = sclass_for_length(len);
                    block = pool.realloc(idx - 1, sclass, sclass + 1, len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
                pool.data[block + new_len] = element;
                pool.data[block] = T::new(new_len);
                len
            }
        }
    }

    /// Grow list by adding `count` reserved-value elements at the end.
    ///
    /// Returns a mutable slice representing the whole list.
    fn grow<'a>(&'a mut self, count: usize, pool: &'a mut ListPool<T>) -> &'a mut [T] {
        let idx = self.index as usize;
        let new_len;
        let block;
        match pool.len_of(self) {
            None => {
                // This is an empty list. Allocate a block.
                debug_assert_eq!(idx, 0, "Invalid pool");
                if count == 0 {
                    return &mut [];
                }
                new_len = count;
                block = pool.alloc(sclass_for_length(new_len));
                self.index = (block + 1) as u32;
            }
            Some(len) => {
                // Do we need to reallocate?
                let sclass = sclass_for_length(len);
                new_len = len + count;
                let new_sclass = sclass_for_length(new_len);
                if new_sclass != sclass {
                    block = pool.realloc(idx - 1, sclass, new_sclass, len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
            }
        }
        pool.data[block] = T::new(new_len);
        &mut pool.data[block + 1..block + 1 + new_len]
    }

    /// Constructs a list from an iterator.
    pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = Self::new();
        list.extend(elements, pool);
        list
    }

    /// Appends multiple elements to the back of the list.
    pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
    where
        I: IntoIterator<Item = T>,
    {
        let iterator = elements.into_iter();
        let (len, upper) = iterator.size_hint();
        // On most iterators this check is optimized down to `true`.
        if upper == Some(len) {
            let data = self.grow(len, pool);
            let offset = data.len() - len;
            for (src, dst) in iterator.zip(data[offset..].iter_mut()) {
                *dst = src;
            }
        } else {
            for x in iterator {
                self.push(x, pool);
            }
        }
    }

    /// Inserts an element as position `index` in the list, shifting all elements after it to the
    /// right.
    pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>) {
        // Increase size by 1.
        self.push(element, pool);

        // Move tail elements.
        let seq = self.as_mut_slice(pool);
        if index < seq.len() {
            let tail = &mut seq[index..];
            for i in (1..tail.len()).rev() {
                tail[i] = tail[i - 1];
            }
            tail[0] = element;
        } else {
            debug_assert_eq!(index, seq.len());
        }
    }

    /// Removes the last element from the list.
    fn remove_last(&mut self, len: usize, pool: &mut ListPool<T>) {
        // Check if we deleted the last element.
        if len == 1 {
            self.clear(pool);
            return;
        }

        // Do we need to reallocate to a smaller size class?
        let mut block = self.index as usize - 1;
        if is_sclass_min_length(len) {
            let sclass = sclass_for_length(len);
            block = pool.realloc(block, sclass, sclass - 1, len);
            self.index = (block + 1) as u32;
        }

        // Finally adjust the length.
        pool.data[block] = T::new(len - 1);
    }

    /// Removes the element at position `index` from the list. Potentially linear complexity.
    pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>) {
        let len;
        {
            let seq = self.as_mut_slice(pool);
            len = seq.len();
            debug_assert!(index < len);

            // Copy elements down.
            for i in index..len - 1 {
                seq[i] = seq[i + 1];
            }
        }

        self.remove_last(len, pool);
    }

    /// Removes the element at `index` in constant time by switching it with the last element of
    /// the list.
    pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>) {
        let seq = self.as_mut_slice(pool);
        let len = seq.len();
        debug_assert!(index < len);
        if index != len - 1 {
            seq.swap(index, len - 1);
        }

        self.remove_last(len, pool);
    }

pub fn get_mut<'a>(
    &'a mut self,
    index: usize,
    pool: &'a mut ListPool<T>
) -> Option<&'a mut T>

Get a mutable reference to a single element from the list.

pub fn deep_clone(&self, pool: &mut ListPool<T>) -> Self

Create a deep clone of the list, which does not alias the original list.

pub fn clear(&mut self, pool: &mut ListPool<T>)

Removes all elements from the list.

The memory used by the list is put back in the pool.

Examples found in repository

src/list.rs (line 508)

    fn remove_last(&mut self, len: usize, pool: &mut ListPool<T>) {
        // Check if we deleted the last element.
        if len == 1 {
            self.clear(pool);
            return;
        }

        // Do we need to reallocate to a smaller size class?
        let mut block = self.index as usize - 1;
        if is_sclass_min_length(len) {
            let sclass = sclass_for_length(len);
            block = pool.realloc(block, sclass, sclass - 1, len);
            self.index = (block + 1) as u32;
        }

        // Finally adjust the length.
        pool.data[block] = T::new(len - 1);
    }

    /// Removes the element at position `index` from the list. Potentially linear complexity.
    pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>) {
        let len;
        {
            let seq = self.as_mut_slice(pool);
            len = seq.len();
            debug_assert!(index < len);

            // Copy elements down.
            for i in index..len - 1 {
                seq[i] = seq[i + 1];
            }
        }

        self.remove_last(len, pool);
    }

    /// Removes the element at `index` in constant time by switching it with the last element of
    /// the list.
    pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>) {
        let seq = self.as_mut_slice(pool);
        let len = seq.len();
        debug_assert!(index < len);
        if index != len - 1 {
            seq.swap(index, len - 1);
        }

        self.remove_last(len, pool);
    }

    /// Shortens the list down to `len` elements.
    ///
    /// Does nothing if the list is already shorter than `len`.
    pub fn truncate(&mut self, new_len: usize, pool: &mut ListPool<T>) {
        if new_len == 0 {
            self.clear(pool);
            return;
        }

        match pool.len_of(self) {
            None => return,
            Some(len) => {
                if len <= new_len {
                    return;
                }

                let block;
                let idx = self.index as usize;
                let sclass = sclass_for_length(len);
                let new_sclass = sclass_for_length(new_len);
                if sclass != new_sclass {
                    block = pool.realloc(idx - 1, sclass, new_sclass, new_len + 1);
                    self.index = (block + 1) as u32;
                } else {
                    block = idx - 1;
                }
                pool.data[block] = T::new(new_len);
            }
        }
    }

pub fn take(&mut self) -> Self

Take all elements from this list and return them as a new list. Leave this list empty.

This is the equivalent of Option::take().

pub fn push(&mut self, element: T, pool: &mut ListPool<T>) -> usize

Appends an element to the back of the list. Returns the index where the element was inserted.

Examples found in repository

src/list.rs (line 480)

    pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
    where
        I: IntoIterator<Item = T>,
    {
        let iterator = elements.into_iter();
        let (len, upper) = iterator.size_hint();
        // On most iterators this check is optimized down to `true`.
        if upper == Some(len) {
            let data = self.grow(len, pool);
            let offset = data.len() - len;
            for (src, dst) in iterator.zip(data[offset..].iter_mut()) {
                *dst = src;
            }
        } else {
            for x in iterator {
                self.push(x, pool);
            }
        }
    }

    /// Inserts an element as position `index` in the list, shifting all elements after it to the
    /// right.
    pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>) {
        // Increase size by 1.
        self.push(element, pool);

        // Move tail elements.
        let seq = self.as_mut_slice(pool);
        if index < seq.len() {
            let tail = &mut seq[index..];
            for i in (1..tail.len()).rev() {
                tail[i] = tail[i - 1];
            }
            tail[0] = element;
        } else {
            debug_assert_eq!(index, seq.len());
        }
    }

pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Selfwhere
    I: IntoIterator<Item = T>,

Constructs a list from an iterator.

pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)where
    I: IntoIterator<Item = T>,

Appends multiple elements to the back of the list.

Examples found in repository

src/list.rs (line 460)

    pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = Self::new();
        list.extend(elements, pool);
        list
    }

pub fn insert(&mut self, index: usize, element: T, pool: &mut ListPool<T>)

Inserts an element as position index in the list, shifting all elements after it to the right.

pub fn remove(&mut self, index: usize, pool: &mut ListPool<T>)

Removes the element at position index from the list. Potentially linear complexity.

pub fn swap_remove(&mut self, index: usize, pool: &mut ListPool<T>)

Removes the element at index in constant time by switching it with the last element of the list.

pub fn truncate(&mut self, new_len: usize, pool: &mut ListPool<T>)

Shortens the list down to len elements.

Does nothing if the list is already shorter than len.

pub fn grow_at(&mut self, index: usize, count: usize, pool: &mut ListPool<T>)

Grow the list by inserting count elements at index.

The new elements are not initialized, they will contain whatever happened to be in memory. Since the memory comes from the pool, this will be either zero entity references or whatever where in a previously deallocated list.

Trait Implementations

impl<T: Clone + EntityRef + ReservedValue> Clone for EntityList<T>

fn clone(&self) -> EntityList<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + EntityRef + ReservedValue> Debug for EntityList<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: EntityRef + ReservedValue> Default for EntityList<T>

Create an empty list.

fn default() -> Self

Returns the “default value” for a type.

impl<T: Hash + EntityRef + ReservedValue> Hash for EntityList<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where
    H: Hasher,
    Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: PartialEq + EntityRef + ReservedValue> PartialEq<EntityList<T>> for EntityList<T>

fn eq(&self, other: &EntityList<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Copy + EntityRef + ReservedValue> Copy for EntityList<T>

impl<T: EntityRef + ReservedValue> StructuralPartialEq for EntityList<T>