Struct midenc_hir::OrderedArenaMap

pub struct OrderedArenaMap<K: EntityRef, V> { /* private fields */ }

OrderedArenaMap is an extension of ArenaMap that provides for arbitrary ordering of keys/values

This is done using an intrusive linked list alongside an ArenaMap. The list is used to link one key/value pair to the next, so any ordering you wish to implement is possible. This is particularly useful for layout of blocks in a function, or instructions within blocks, as you can precisely position them relative to other blocks/instructions.

Because the linked list is intrusive, it is virtually free in terms of space, but comes with the standard overhead for traversals. That said, there are a couple of niceties that give it good overall performance:

• It is a doubly-linked list, so you can traverse equally efficiently front-to-back or back-to-front,
• It has O(1) indexing; given a key, we can directly obtain a reference to a node, and with that, obtain a cursor over the list starting at that node.

Implementations

impl<K: EntityRef, V> OrderedArenaMap<K, V>

pub fn new() -> Self

pub fn is_empty(&self) -> bool

Returns true if this OrderedArenaMap is empty

pub fn len(&self) -> usize

Returns the total number of actively linked items in the map

pub fn contains(&self, key: K) -> bool

Returns true if this map contains the given key and its value has been linked

pub fn get(&self, key: K) -> Option<&V>

Returns a reference to the value associated with the given key, if present and linked

pub fn get_mut(&mut self, key: K) -> Option<&mut V>

Returns a mutable reference to the value associated with the given key, if present and linked

pub fn create(&mut self) -> K

Allocates a key, but does not link the data

pub fn append(&mut self, key: K, value: V)

Used with create when ready to associate data with the allocated key, linking it in to the end of the list

pub fn insert_before(&mut self, key: K, before: K, value: V)

Like append, but inserts the node before before in the list

NOTE: This function will panic if before is not present in the list

pub fn insert_after(&mut self, key: K, after: K, value: V)

Like append, but inserts the node after after in the list

NOTE: This function will panic if after is not present in the list

pub fn push(&mut self, value: V) -> K

Allocates a key and links data in the same operation

pub fn push_after(&mut self, after: K, value: V) -> K

Like push, but inserts the node after after in the list

NOTE: This function will panic if after is not present in the list

pub fn remove(&mut self, key: K)

Unlinks the value associated with the given key from this map

NOTE: Removal does not result in deallocation of the underlying data, this happens when the map is dropped. To perform early garbage collection, you can clone the map, and drop the original.

pub fn first(&self) -> Option<&LayoutNode<K, V>>

Returns the first node in the map

pub fn last(&self) -> Option<&LayoutNode<K, V>>

Returns the last node in the map

pub fn cursor(&self) -> Cursor<'_, LayoutAdapter<K, V>>

Returns a cursor which can be used to traverse the map in order (front to back)

pub fn cursor_mut(&mut self) -> CursorMut<'_, LayoutAdapter<K, V>>

Returns a cursor which can be used to traverse the map mutably, in order (front to back)

pub fn cursor_at(&self, key: K) -> Cursor<'_, LayoutAdapter<K, V>>

Returns a cursor which can be used to traverse the map in order (front to back), starting at the key given.

pub fn cursor_mut_at(&mut self, key: K) -> CursorMut<'_, LayoutAdapter<K, V>>

Returns a cursor which can be used to traverse the map mutably, in order (front to back), starting at the key given.

pub fn iter(&self) -> OrderedArenaMapIter<'_, K, V>

Returns an iterator over the key/value pairs in the map.

The iterator is double-ended, so can be used to traverse the map front-to-back, or back-to-front

pub fn keys(&self) -> impl Iterator<Item = K> + '_

Returns an iterator over the keys in the map, in order (front to back)

pub fn values(&self) -> impl Iterator<Item = &V>

Returns an iterator over the values in the map, in order (front to back)

Trait Implementations

impl<K: EntityRef, V: Clone> Clone for OrderedArenaMap<K, V>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: EntityRef, V> Default for OrderedArenaMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: EntityRef, V> Drop for OrderedArenaMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K: EntityRef, V> Index<K> for OrderedArenaMap<K, V>

type Output = V

The returned type after indexing.

fn index(&self, index: K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K: EntityRef, V> IndexMut<K> for OrderedArenaMap<K, V>

fn index_mut(&mut self, index: K) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.