Struct TreeOrderedIndexMap 

pub(crate) struct TreeOrderedIndexMap {
    map: DomRefCell<HashMapTracedValues<Atom, TreeOrderedIndexMapEntry, FxBuildHasher>>,
    might_need_rebuild_for_layout: Cell<bool>,
    index_type: IndexType,
}

A data structure that tracks the use of an identifier type in the DOM. Currently this is meant for tracking elements that share an id or name attribute.

The core problem this structure is trying to solve is that elements with the same id and ‘name’ often need to be accessed in document order, yet calculating the order of elements is expensive. This structure makes calculation of that ordering as cheap as possible by delaying it until the last moment before it is needed.

The goal here is to mitigate the situation where many elements on a page share the same identifier. Maintaining an in-order map in that case has very negative performance characteristics. This map solves that problem, making the optimal case still O(1). It’s actually not very common that a normal page needs the elements in order during script execution.

Each entry in the map holds a cached ordering, initially valid if there is only a single element that has a particular id or name. When another element is added to the map which shares that identifier, the cache is invalidated and count of elements is maintained. Only when needing to access the ordered representation of the elements with the identifier do we walk the DOM, collecting the various elements in order.

There is one unfortunate penalty we have to pay due to Servo’s rooting design: layout that might match elements by id does need elements in order. Before layout or running any query selectors, we need to resolve all unresolved entries in the map. In the end though, this is still just a single walk over the DOM. This is only run when a map entry becomes invalid due to to an element sharing an id being added or removed.

Fields

map: DomRefCell<HashMapTracedValues<Atom, TreeOrderedIndexMapEntry, FxBuildHasher>>

It is safe to use FxHash for these maps as Atoms are string_cache items that will have the hash computed from a u32.

might_need_rebuild_for_layout: Cell<bool>

Whether or not this map might need to be resolved for layout or for calls to Self::for_each.

index_type: IndexType

The IndexType that this TreeOrderedIndexMap uses, which is either the id or name attribute.

Implementations

impl TreeOrderedIndexMap

pub(crate) fn name() -> Self

pub(crate) fn id() -> Self

pub(crate) fn add(&self, key: &Atom, element: &Element)

Add an entry to this map from the key (an id or name attribute value) to Element. If this is the first time this key is used, then the map will be able to map to the entry without having to resolve ordering.

pub(crate) fn remove(&self, key: &Atom)

Remove an entry from the map with key (an id or name attribute value). If there are more elements that share the same key, the entry will need resoluton before use. Removal of the last element for an entry will remove it from the map.

pub(crate) fn get( &self, no_gc: &NoGC, scope: &Node, key: &Atom, ) -> Option<DomRoot<Element>>

Get the first element that has this key from the DOM, possibly resolving the ordering of unresolved entries.

Note: This should never be used during layout as it does rooting and unrooting.

pub(crate) fn get_all( &self, no_gc: &NoGC, scope: &Node, key: &Atom, ) -> Ref<'_, [Dom<Element>]>

Get all of the entries in the map, in DOM order that share a particular key. If the entry for this key is unresolved, it will be resolved.

Note: This should never be used during layout as it does rooting and unrooting.

pub(crate) fn for_each( &self, no_gc: &NoGC, scope: &Node, callback: impl FnMut(&Atom, &[Dom<Element>]), )

Run the given callback against every (key, elements) tuple in this map. This will resolve all unresolved entries in the map.

Note: This should never be used during layout as it does rooting and unrooting.

pub(crate) fn get_all_for_layout(&self, key: &Atom) -> &[LayoutDom<'_, Element>]

Get all of the entries in the map, in DOM order that share a particular key. This will not resolve any entries. It is an error to call this before an entry is resolved.

fn resolve_one( no_gc: &NoGC, scope: &Node, key: &Atom, entry: &mut TreeOrderedIndexMapEntry, index_type: IndexType, )

Resolve a single entry in the map that has more than one element associated with it. This will walk the DOM and gather all of the elements that have this id/name associated with them in DOM order.

pub(crate) fn resolve_all(&self, no_gc: &NoGC, scope: &Node)

Resolve all entries in the map, meaning the next access will not need any resolution. This should be called before any layout activity that accesses the map.

Trait Implementations

impl MallocSizeOf for TreeOrderedIndexMap

fn size_of(&self, ops: &mut MallocSizeOfOps) -> usize

Measure the heap usage of all descendant heap-allocated structures, but not the space taken up by the value itself.

impl Traceable for TreeOrderedIndexMap

unsafe fn trace(&self, tracer: *mut JSTracer)

Trace self.