Intel Extensible Firmware Interface - Manual (Page 752)

Extensible Firmware Interface Specification
17-12 12/01/02 Version 1.10
5. If a string comparison with an internal node or leaf node fails (mismatch occurs before the
“Level + 1”th character is reached or MAX_MATCH_LENGTH is exceeded), then a “split”
operation is performed as follows:
Suppose a comparison is being performed with a level 9 Node, at position 350, and the current
position is 1005. If the sixth character at position 350 is an “x” and the sixth character at
position 1005 is a “y,” then a mismatch will occur. In this case, a new internal node and a new
child node are inserted into the tree, as depicted in Figure 17-6.
Level: 9
Pos: 350
a) Original State
OM13178
Level: 5
Pos: 1005
Pos: 1005
"x"
Level: 9
Pos: 350
b) Node "Split"
Figure 17-6. Node Split
The b) portion of Figure 17-6 has two new inserted nodes, which reflects the new string
information that was found at the current position. The process splits the old node into two child
nodes, and that is why this operation is called a “split.”
17.3.2.4 Deleting String Info
The String Info Log will grow as more and more string information is logged. The size of the
String Info Log must be limited, so outdated information must be removed on a regular basis.
A sliding window is maintained behind the current position, and the searches are always limited
within the range of the sliding window. Each time the current position is advanced, outdated string
information that falls outside the sliding window should be removed from the tree. The search for
outdated string information is simplified by always updating the nodes’ “position” attribute when
searching for matching strings.