art
art copied to clipboard
tailscale
implementation of the Allotment Routing Table (ART) algorithm by Donald Knuth, as described in the paper by Yoichi Hariguchi
I would be interested in your opinion on **BART**. A similar algorithm to **ART**, at least the `baseIndex` function, but neither allotment nor path-compression, but popcount based level-compression combined with...
```go func (t *Table[T]) Get(addr netip.Addr) (lpm netip.Prefix, ret T, ok bool) ``` Often it is not only the value that is interesting but also the longest prefix that matched....
```go // ipv4AsUint returns ip as a uint32. func ipv4AsUint(ip netip.Addr) uint32 { bs := ip.As4() return binary.BigEndian.Uint32(bs[:]) } ``` One can argue about whether IPv4-mapped IPv6 addresses should be...
Diffing against the other PR, just so it only shows the differences. Sadly, right now, Overlaps is correct, but slower than netipx.IPset: about 40% slower for IPv4, and around 10x...
Roughly 4-8x faster than the naive netipx.IPSet implementation (which the benchmark below is comparing against). ``` │ old.txt │ new.txt │ │ sec/op │ sec/op vs base │ TableOverlapsPrefix/ipv4/10-32 211.70n...