Find Part Process

If then current branch does not have a child then no Branch is returned.

To find the child Branch with a given Key the Key is first prepared by forming a Hash of the requested Key, and the Key Letter.

The Key Letter is the first eight bytes of the Key if the Letter Branch if that is present.  By preparing this 64 bit value a single compare can be made for the name as if it does match then it can be assumed the complete name will match since.  This can be assumed since the ‘@’ is one byte and the subsequent UTF8 character is a maximum of four bytes.  With a null terminator the value is three to six bytes.

Starting with the first child Branch and iterating through all siblings a first compare is done with the Hash.  If a match occurs a complete compare is made with the Key to ensure this is not a result of a hash collision.  If a complete match is successful the Branch is returned.

A second compare is made with the Key Letter to the Branch_Key.  If this is a match then the find process is essentially started again from the current Branch but using the next letter as the Key Letter.  If that returns a Branch then it is returned.

If both comparisons return false then if a sibling is present the process continues with the sibling.

Example: “/Verb,Bulk”

Assuming the current Branch is “/Verb” and the “Bulk” child (“/Verb,Bulk”) is sought first the hash is calculated for “Bulk” and the Key Letter is formed (“@B”).

A hash compare is made with first child (“/Verb,@A”) which fails.  Then a Key Letter compare is made which also fails.  The process continues with the sibling.

A hash compare is made with the sibling (“/Verb,@B”) which fails.  Then a Key Letter compare is made which matches.  A call is made to start the same process using the already calculated hash but the next Key Letter (“@u”).

A hash compare is made with first child (“/Verb,Branch”) which fails.  Then a Key Letter compare is made which also fails.  The process continues with the sibling.

A hash compare is made with the sibling (“/Verb,Bulk”) which matches.  Then a full compare is made of the Key which also matches and therefore this Branch is returned.

Example: “/Verb,Agent” as child of “/Verb”

Assuming the current Branch is “/Verb” and the “Agent” child (“/Verb,Agent”) is sought first the hash is calculated for “Agent” and the Key Letter is formed (“@A”).

We are assuming “/Verb,Agent” is the sibling of “/Verb,@C” for this example therefore it will also be assumed “/Verb,@A” does not exist and “/Verb,@B” is the first child of “/Verb”.

A hash compare is made with first child (“/Verb,@B”) which fails.  Then a Key Letter compare is made which also fails.  The process continues with the sibling.

A hash compare is made with next sibling (“/Verb,@C”) which fails.  Then a Key Letter compare is made which also fails.  The process continues with the sibling.

A hash compare is made with next sibling (“/Verb,Agent”) which matches.  Then a full compare is made of the Key which also matches and therefore this Branch is returned.

Example: “/Verb,Agent” as child of “/Verb,@A”

Assuming the current Branch is “/Verb” and the “Agent” child (“/Verb,Agent”) is sought first the hash is calculated for “Agent” and the Key Letter is formed (“@A”).

A hash compare is made with the first child (“/Verb,@A”) which matches.  A call is made to start the same process using the already calculated hash but the next Key Letter (“@g”).

A hash compare is made with first child (“/Verb,Agent”) which matches.  Then a full compare is made of the Key which also matches and therefore this Branch is returned.

Notes

For speed the bulk of comparisons are made using value compares, such as the 32 bit hash or 64 bit Key Letter.  Since the vast majority of compares will return false, iteration through siblings is very fast.  False positive matches will be extremely rare as it will require two siblings with identical 32 bit hash values.

Siblings are always in binary order.

The entire sibling list is iterated through until a match or the end.  This is done since the list will typically be short compared to a comparison for less-than which may be expensive.

While it is typical, it is not required that a given Branch be a child of a Letter Branch.  Therefore in the example “/Verb,Agent” can be either the child of “@A” or the sibling of “@C”.  It must appear only once and precedence is not defined.