[webkit-dev] HTML5 & MathML3 entities

[Maciej Stachowiak]

On Jul 10, 2010, at 11:10 AM, Sausset François wrote:

> I just saw that when looking at the code by myself.
> What do you exactly mean by a prefix tree?

The data structure commonly called a "Trie" is a prefix tree:
http://en.wikipedia.org/wiki/Trie

This data structure not only lets you tell if a particular key is present, but it also lets you check if a string you have could possibly be the prefix of any valid key.

I think it is challenging, though, to make a trie structure that can be a compile-time constant, and building one dynamically will cost runtime memory per-process (whereas constant data would be in the data segment and shared).

Another possibility is to make an array of all the entity names in sorted order. Then lookup can use a binary search, and on a failed lookup, looking to either side of the last key checked should determine whether it is a valid prefix.

I expect binary search would be slower than Trie lookup, though I don't know by how much.

Regards,
Maciej