Why do you use a sstree instead of a key/value pair? about rain HOT 3 CLOSED

IPv4 address range is 32 bits and the memory cost of storing each address separately in a map would be too high.
For the same reason blocklists are usually distributed in CIDR format. Segment tree is a data structure to allow fast (O(logn)) lookups within stored ranges.

Segment tree: https://en.wikipedia.org/wiki/Segment_tree

Original implementation: https://github.com/toberndo/go-stree

Example list source: https://www.iblocklist.com/lists?fileformat=cidr&archiveformat=gz

Doc:

I don't use Discord but you can email me for other questions.

from rain.

Cool, thanks. I will email you.

One cool thing about golang is that keys don't need to be strings.

So your key could easily be a 32bit int, though you lose 1 byte in the bool. But then each of your tree nodes use 2x 8byte for the left, right pointers.

map[int32]bool{ ipA: true, ipB: true }

Now perhaps your blocklist is not used much hence not an issue.

Was playing with rain on the command like to see how it works....really cool. Works like a charm.

from rain.

The memory space is one part of the problem. The other one is searching. How do you check if an address is blocked by one of the ranges in the blocklist with a map type?

from rain.