3 ms·
I've never really groked tries, so bad for me. But I've built a few IP lookup tables. For one, I only needed to know a true/false given an ipv4 address (does g
by toast0 2y ago
I've never really groked tries, so bad for me. But I've built a few IP lookup tables.
For one, I only needed to know a true/false given an ipv4 address (does geolocation of the ip indicate within a specific set of countries), and the lookup needed to be fast and easy.
If you look at every address, a simple boolean array will be too big, 2^29 bytes with 2^3 values per byte covers the address space, but half a gig of memory is too much. Otoh, geolocation by country is unlikely to be more specific than a /24, 2^21 bytes with 2^3 values per byte is only 2 meg of memory devoted to a very fast lookup; less in actual use if you mmap without large pages, because parts of the range will never page in.
That approach isn't great if your value is larger than a boolean or you need ipv6 (you can use /48s as your maximum prefix length, but there's quite a lot of /48s).
If you want a compact table, you can store an ordered set of (low ip, value), and access the table by finding the nearest value equal or less than the observed ip. I used Erlang's ets with ordered set and the ets:prev(Table, IP + 1) which uses a binary tree under the hood, but anything that can handle 128 bit integer should work.
Building the table is a bit of work, because you've got to take inputs of like X.Y.0.0/16 -> A and then X.Y.6.0/24 -> B and turn that into X.Y.0.0 -> A, X.Y.6.0 -> B, X.Y.7.0 -> A ... but all that transformation happens offline.
I think you're more likely to have a language built in for a binary tree than a trie, but some languages have neither.