[erlang-questions] IP search optimization

[Sid Muller]

> Sent: Friday, November 20, 2015 at 3:52 PM
> From: "Geoff Cant" <nem@REDACTED>
> To: "Sid Muller" <sid5@REDACTED>
> Cc: Erlang <erlang-questions@REDACTED>
> Subject: Re: [erlang-questions] IP search optimization
>
> Hi Sid, are you writing an open source library for this functionality? I need exactly the same thing and was going to sit down to write it.
> 
> With CIDR blocks, you can always calculate the lower and upper address in a range.
> 
> > -type ip4() :: <<_:32/bits>>.
> > -type ip4_mask() :: 0..32.
> > -type ip4_cidr() :: {ip4(), ip4_mask()}.
> > -spec to_range(ip4_cidr()) -> {Low::ip4(), High::ip4()}.
> > to_range({<<CIDR:4/binary>>, Mask})
> >   when 0 =< Mask,
> >        Mask =< 32 ->
> >     HostBits = 32 - Mask,
> >     {<<CIDR:Mask/bits, 0:HostBits/integer>>,
> >      <<CIDR:Mask/bits, 16#FFFFFFFF:HostBits/integer>>}.
> 
> If you pre-convert your CIDR list into a range list, you can then select all the matching cidrs by comparing Low =< IP, IP =< High, and returning the CIDR with the largest mask (if you do longest-prefix wins), or the first in order if you’re doing an ordered CIDR match.
> 
> Pre-converting CIDR -> Range will let you use ets:select - and might be reasonably efficient in an ordered_set table if you’ve got large numbers of CIDRs. I think if your ets key is {Low, High}, and it’s an ordered_set table, the first result from a matching select will be the one with the longest Mask anyway (as {<<192,168,0,0>>, <<192,168,0,255>>} <  {<<192,168,0,0>>, <<192,168,255,255>>} — i.e. 192.168.0.0/24 < 192.168.0.0/16 when converted to a range tuple).
> 
> > IP = something,
> > Matching = ets:select(cidr_table, ets:fun2ms(fun (#record{range={Low, High}}) when Low =< IP, IP =< High) -> object() end)).
> 
> 
> Anyway - I’m either going to write something like this in the next couple of weeks, or use yours if it’s public and suitable :)

Hi Geoff,

check out Adam's response, the 9 liner prev() does the job really well.