Also see “poptrie” [0] for an efficient way to do routing table-style lookups for CIDRs (longest prefix match). They basically use the “popcnt trick” to impleme

Also see “poptrie” [0] for an efficient way to do routing table-style lookups for CIDRs (longest prefix match). They basically use the “popcnt trick” to implement sparse arrays, use “direct indexing” for the first however many bits to reduce the number of indirections, and have a cool optimization specific to longest prefix match (“hole punching” in the paper). [0]: https://dl.acm.org/doi/10.1145/2829988.2787474 https://dl.acm.org/doi/10.1145/2829988.2787474