Skip to content

Import a qp-trie implementation

Tony Finch requested to merge fanf-qp-import into main

This is a foundation for future work that will, in stages, replace uses of BIND's rbt with this qp-trie.

The qp-trie is not a 1-for-1 replacement for the rbt: the rbt stores names as part of its structure, whereas the qp-trie does not; but the qp-trie has built-in support for multiversion concurrency, which the rbt does not.

Some of the functionality we will need has not been included; these features will be added based on what BIND needs, possibly using code from other existing qp-trie implementations.

  • Garbage collector performance statistics are missing.

  • Fancy searches are missing, such as longest match and nearest match.

  • Iteration is missing.

  • Search for update is missing, for cases where the caller needs to know if the value object is mutable or not.

Edited by Tony Finch

Merge request reports