Combine three ways to speed up index-based searches in radix tries.
- Every path from trie root to the bottom ends in either a leaf or a NULL node. Every loop that walks a path from the root has to check both conditions with every iteration. Replace those NULL nodes with null-leaves, so that every loop can iterate until a leaf is encountered, and then distinguish null leaves from regular leaves once, outside the loop.
That only works for tries properly initialized; default, static zero-initialization no longer works.
- Every iteration invokes keybarr(), to see if the search is doomed to fail, and slot(), to determine how to continue. A simple calculation produces both results at once, eliminating some arithmetic and a branch point.
- There is a node field called 'clev'. It is always fetched and then multiplied by a constant. Saving the post-multiplication value instead saves an instruction per loop iteration.