Expand description
Random access into a WTF-8 buffer.
WTF-8 is variable width, so a buffer’s n-th code point can only be found by
decoding the n-1 before it: Wtf8’s iterators are sequential, and
resolving an index through them is O(n). Code that indexes the same string
repeatedly – a regex scan restarting at successive positions, say – then
walks the whole buffer once per index, which is quadratic in its length.
Wtf8Index is the side table that makes the lookup O(1): one 24-byte
group per 64 code points, so 0.375 bytes per code point. It is a cache, and
holds no state of its own beyond the buffer’s shape – building it twice for
the same buffer yields the same table.
The layout is PyPy’s UTF8_INDEX_STORAGE (rpython/rlib/rutf8.py).
Structs§
- Wtf8
Index - A code-point-index to byte-offset table for one WTF-8 buffer.