proposal: add a trie type for efficient route lookups using netaddr.IP{,Prefix} (originally by @mdlayher)

[ckaznocha]

This intended to be a continuation of: https://github.com/inetaf/netaddr/issues/139. Since that repo has been archived, bringing it over here.

I noticed @bradfitz published tailscale/art recently. I'm wondering that is ready and still appropriate for use here?

[bradfitz]

Yeah, we're currently starting investigations of that, doing some measurements.

[aromatt]

I've been looking for an IP/CIDR trie implementation that uses netip.Prefixes as keys and generics for values - not for route lookups, but for more general use.

I need a variety of queries, e.g.:

• query by prefix (as opposed to single IP)
• get the shortest prefix parent of an IP or prefix
• get all descendants of a prefix

It looks like a lot of work has gone into tailscale/art, but it's designed to solve a more specific problem as efficiently as possible.

I'm commenting here in case anyone else (at Tailscale or otherwise) has ever needed something similar, and either has a solution or is interested in one. In case it doesn't exist yet, I'm about to start working on it at aromatt/netipmap.