Element ID

Element ID

ID mapping is managed by the TreeScope.

TreeScope::m_elementsById is a DocumentOrderedMap that maps elements to a string.

getElementById

DocumentOrderedMap::m_map is a cache for the first node with a given key. i.e. getElementById just returns the element in this map if it exists.

If it doesn't exist, we then look at DocumentOrderedMap::m_duplicateCounts. DocumentOrderedMap::m_duplicateCounts is the count of all elements with a given key excluding the one referenced in DocumentOrderedMap::m_map, if any. If the duplicate count is zero an element with the given ID doesn't exist. DocumentOrderedMap::m_map is a HashCountedSet.

If DocumentOrderedMap::m_duplicateCounts contains the ID we are looking for, we then traverse all the nodes in the scope and return the first one matching the ID. This element will be cached in DocumentOrderedMap::m_map so the next time will be fast.

Mozilla's case

ID lookup is performed through nsDocument::mIdentifierMap.

    /* mIdentifierMap works as follows for IDs:
     * 1) Attribute changes affect the table immediately (removing and adding
     *    entries as needed).
     * 2) Removals from the DOM affect the table immediately
     * 3) Additions to the DOM always update existing entries for names, and add
     *    new ones for IDs.
     */
    nsTHashtable<nsIdentifierMapEntry> mIdentifierMap;

nsIdentifierMapEntry::mIdContentList contains the list of elements with the same id. They are already sorted, so all GetIdElement() needs to do is return nsIdentifierMapEntry::mIdContentList[0].