Why do you use a sstree instead of a key/value pair?

[ruralcoder]

Hi Cenkati,

Been thinking of a project around torrent and since I love golang, i came across your project. Thank you!

I only had a small question on the use of trees. Why not use a key/value pair with O(1) access and free dedup. Just curious (not a bug)

rain/internal/blocklist/blocklist.go

Line 21 in 2ae49b7

tree stree.Stree

I would love to talk to you about torrent. I have tons of questions. Do you use discord or any other platform??

[cenkalti]

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:

rain/torrent/config.go

Line 42 in 2ae49b7

// URL to the blocklist file in CIDR format.

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

[ruralcoder]

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.

[cenkalti]

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?