Iptrie (Iptrie v0.1.0) View Source

IP lookup, with longest prefix match, for IPv4, IPv6 prefixes (and others).

Iptrie manages multiple Radix trees, one for each type of Pfx.t/0 prefix used as determined by their maxlen property. That way, IPv4 prefixes (maxlen: 32) use a different radix tree as opposed to e.g. IPv6 (maxlen: 128).

Iptrie has a bias towards IPv4 and IPv6 since it uses Pfx to convert arguments to a Pfx.t/0 struct. So, doing other types of prefixes will require the actual Pfx.t/0 structs as arguments for the various Iptrie functions.

Like Pfx, Iptrie tries to mirror the representation of results to the argument(s) given.

Example

iex> ipt = new()
...> |> put("1.2.3.0/24", "v4")
...> |> put("acdc:1975::/32", "T.N.T")
...> |> put("0.0.0.0/0", "v4 default")
...> |> put("::/0", "no dynamite")
...> |> put(%Pfx{bits: <<0xaa, 0xbb, 0xcc, 0xdd>>, maxlen: 48}, "some OUI")
iex>
iex> lookup(ipt, "1.2.3.128")
{"1.2.3.0/24", "v4"}
iex>
iex> # mirror digits representation
iex>
iex> lookup(ipt, {1, 2, 3, 128})
iex> {{{1, 2, 3, 0}, 24}, "v4"}
iex>
iex> lookup(ipt, "10.11.12.13")
{"0.0.0.0/0", "v4 default"}
iex>
iex> lookup(ipt, "acdc:1975::")
{"acdc:1975:0:0:0:0:0:0/32", "T.N.T"}
iex>
iex> lookup(ipt, "abba::")
{"0:0:0:0:0:0:0:0/0", "no dynamite"}
iex>
iex> # use %Pfx{}, since Iptrie only converts IPv4 / IPv6 representations
iex>
iex> lookup(ipt, %Pfx{bits: <<0xaa, 0xbb, 0xcc, 0xdd, 0xee>>, maxlen: 48})
{%Pfx{bits: <<0xAA, 0xBB, 0xCC, 0xDD>>, maxlen: 48}, "some OUI"}
iex>
iex> # uses three separate radix trees:
iex>
iex> Map.get(ipt, 32)
{0, {7, [{"", "v4 default"}], [{<<1, 2, 3>>, "v4"}]}, nil}
iex>
iex> Map.get(ipt, 128)
{0, [{"", "no dynamite"}], [{<<172, 220, 25, 117>>, "T.N.T"}]}
iex>
iex> Map.get(ipt, 48)
{0, nil, [{<<170, 187, 204, 221>>, "some OUI"}]}

Link to this section Summary

Types

prefix()

A prefix represented as an opague Pfx.t/0 struct, an Pfx.ip_address/0, Pfx.ip_prefix/0 or CIDR string.

t()

An Iptrie struct that contains a Radix tree per type of Pfx.t/0 used.

Functions

delete(trie, prefixes)

Delete one or more prefix, value-pair(s) from the trie using an exact match.

get(trie, prefixes)

Return one or more prefix,value-pair(s) using an exact match for given prefix(es).

keys(trie)

Return all the prefixes for all available radix trees in trie.

keys(trie, type)

Return the prefixes from the radix tree(s) in trie for given type.

less(trie, prefix)

Return all the prefix,value-pairs whose prefix is a prefix for the given search prefix.

lookup(trie, prefix)

Return the prefix,value-pair, whose prefix is the longest match for given search prefix.

more(trie, prefix)

Return all the prefix,value-pairs where the search prefix is a prefix for the stored prefix.

new()

Create an new, empty Iptrie.

new(elements)

Create a new Iptrie, populated via a list of {prefix/0, any/0}-pairs.

put(trie, elements)

Populate the trie with a list of {prefix,value}-pairs.

put(trie, prefix, value)

Puts value under prefix in the trie.

update(trie, prefix, fun)

Lookup prefix and update the matched entry, only if found.

update(trie, prefix, default, fun)

Lookup prefix and, if found, update its value or insert the default.

values(trie)

Return all the values stored in all radix trees in trie.

values(trie, type)

Return the values stored in the radix trees in trie for given type.

Link to this section Types

prefix()

Specs

prefix() :: Pfx.prefix()

A prefix represented as an opague Pfx.t/0 struct, an Pfx.ip_address/0, Pfx.ip_prefix/0 or CIDR string.

See: Pfx.

t()

Specs

t() :: %Iptrie{}

An Iptrie struct that contains a Radix tree per type of Pfx.t/0 used.

A prefix' type is determined by its maxlen property: IPv4 has maxlen: 32, IPv6 has maxlen: 128, MAC addresses have maxlen: 48 and so on.

Although Iptrie facilitates lpm lookups of any type of prefix, it has a bias towards IP prefixes. So, any binaries (strings) are interpreted as CIDR-strings and tuples of address digits and/or {address-digits, length) are interpreted as IPv4 or IPv6 representations.

Link to this section Functions

delete(trie, prefixes)

Specs

delete(t(), prefix()) :: t()

Delete one or more prefix, value-pair(s) from the trie using an exact match.

The list of prefixes to delete may contains all types, so all sorts of prefixes can be deleted from multiple radix trees in one go.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", "one")
...> |> put("2.2.2.0/24", "two")
iex>
iex> lookup(ipt, "1.1.1.1")
{"1.1.1.0/24", "one"}
iex>
iex> Map.get(ipt, 32) |> Radix.keys()
[<<1, 1, 1>>, <<2, 2, 2>>]
iex>
iex> ipt = delete(ipt, "1.1.1.0/24")
iex>
iex> lookup(ipt, "1.1.1.1")
nil
iex>
iex> Map.get(ipt, 32) |> Radix.keys()
[<<2, 2, 2>>]

iex> ipt = new()
...> |> put("1.1.1.0/24", "one")
...> |> put("2.2.2.0/24", "two")
...> |> put("abba:1973::/32", "Ring Ring")
...> |> put("acdc:1975::/32", "T.N.T")
iex>
iex> ipt = delete(ipt, ["1.1.1.0/24", "abba:1973::/32"])
iex>
iex> Map.get(ipt, 32) |> Radix.keys()
[<<2, 2, 2>>]
iex>
iex> Map.get(ipt, 128) |> Radix.keys()
[<<0xacdc::16, 0x1975::16>>]

get(trie, prefixes)

Specs

get(t(), prefix() | [prefix()]) :: {prefix(), any()} | nil | [{prefix(), any()}]

Return one or more prefix,value-pair(s) using an exact match for given prefix(es).

Examples

iex> ipt = new([{"1.1.1.0/30", "A"}, {"1.1.1.0/31", "B"}, {"1.1.1.0", "C"}])
iex>
iex> get(ipt, "1.1.1.0/31")
{"1.1.1.0/31", "B"}
iex>
iex> # or get a list of entries
iex>
iex> get(ipt, ["1.1.1.0/30", "1.1.1.0"])
[{"1.1.1.0/30", "A"}, {"1.1.1.0", "C"}]

keys(trie)

Specs

keys(t()) :: [prefix()]

Return all the prefixes for all available radix trees in trie.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", 1)
...> |> put("2.2.2.0/24", 2)
...> |> put("acdc:1975::/32", 3)
...> |> put("acdc:2021::/32", 4)
iex>
iex> keys(ipt)
...> |> Enum.map(fn x -> "#{x}" end)
[
  "1.1.1.0/24",
  "2.2.2.0/24",
  "acdc:1975:0:0:0:0:0:0/32",
  "acdc:2021:0:0:0:0:0:0/32"
]

keys(trie, type)

Specs

keys(t(), integer() | [integer()]) :: [prefix()]

Return the prefixes from the radix tree(s) in trie for given type.

Where type is a single maxlen or a list thereof.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", 1)
...> |> put("2.2.2.0/24", 2)
...> |> put("acdc:1975::/32", 3)
...> |> put("acdc:2021::/32", 4)
iex>
iex> keys(ipt, 32)
[
  %Pfx{bits: <<1, 1, 1>>, maxlen: 32},
  %Pfx{bits: <<2, 2, 2>>, maxlen: 32}
]
iex>
iex> keys(ipt, 128)
[
  %Pfx{bits: <<0xacdc::16, 0x1975::16>>, maxlen: 128},
  %Pfx{bits: <<0xacdc::16, 0x2021::16>>, maxlen: 128}
]
iex>
iex> keys(ipt, 48)
[]
iex>
iex> keys(ipt, [32, 48, 128])
[
  %Pfx{bits: <<1, 1, 1>>, maxlen: 32},
  %Pfx{bits: <<2, 2, 2>>, maxlen: 32},
  %Pfx{bits: <<0xacdc::16, 0x1975::16>>, maxlen: 128},
  %Pfx{bits: <<0xacdc::16, 0x2021::16>>, maxlen: 128}
]

less(trie, prefix)

Specs

less(t(), prefix()) :: [{prefix(), any()}]

Return all the prefix,value-pairs whose prefix is a prefix for the given search prefix.

This returns the less specific entries that enclose the given search prefix. Note that any bitstring is always a prefix of itself. So, if present, the search key will be included in the result.

If prefix is not present or not valid, or cannot be encoded as an Ipv4 op IPv6 Pfx.t/0, an empty list is returned.

Example

iex> ipt = new()
...> |> put("1.1.1.0/25", "A25-lower")
...> |> put("1.1.1.128/25", "A25-upper")
...> |> put("1.1.1.0/30", "A30")
...> |> put("1.1.2.0/24", "B24")
iex>
iex> less(ipt, "1.1.1.0/30")
[
  {"1.1.1.0/30", "A30"},
  {"1.1.1.0/25", "A25-lower"},
]
iex> less(ipt, "2.2.2.2")
[]

lookup(trie, prefix)

Specs

lookup(t(), prefix()) :: {prefix(), any()} | nil

Return the prefix,value-pair, whose prefix is the longest match for given search prefix.

Returns nil if there is no match for search prefix.
Silently ignores any errors when encoding the given search prefix by returning nil.

Example

more(trie, prefix)

Specs

more(t(), prefix()) :: [{prefix(), any()}]

Return all the prefix,value-pairs where the search prefix is a prefix for the stored prefix.

This returns the more specific entries that are enclosed by given search prefix. Note that any bitstring is always a prefix of itself. So, if present, the search prefix will be included in the result.

If prefix is not valid, or cannot be encoded as an Ipv4 op IPv6 t:Pfx.t, nil is returned.

Example

iex> ipt = new()
...> |> put("1.1.1.0/25", "A25-lower")
...> |> put("1.1.1.128/25", "A25-upper")
...> |> put("1.1.1.0/30", "A30")
...> |> put("1.1.2.0/24", "B24")
iex>
iex> more(ipt, "1.1.1.0/24")
[
  {"1.1.1.0/30", "A30"},
  {"1.1.1.0/25", "A25-lower"},
  {"1.1.1.128/25", "A25-upper"}
]

new()

Specs

new() :: t()

Create an new, empty Iptrie.

Example

iex> Iptrie.new()
%Iptrie{}

new(elements)

Specs

new([{prefix(), any()}]) :: t()

Create a new Iptrie, populated via a list of {prefix/0, any/0}-pairs.

Example

iex> ipt = Iptrie.new([{"1.1.1.0/24", "net1"}, {"acdc:1975::/32", "TNT"}])
iex> Map.get(ipt, 32)
{0, [{<<1, 1, 1>>, "net1"}], nil}
iex> Map.get(ipt, 128)
{0, nil, [{<<172, 220, 25, 117>>, "TNT"}]}

put(trie, elements)

Specs

put(t(), [{prefix(), any()}]) :: t()

Populate the trie with a list of {prefix,value}-pairs.

This always uses an exact match for prefix, updating its value if it exists. Any errors are silently ignored as the trie is always returned.

Example

iex> ipt = new([{"1.1.1.0/24", 0}, {"1.1.1.1", 0}, {"1.1.1.1", "x"}])
iex>
iex> get(ipt, "1.1.1.1")
{"1.1.1.1", "x"}

put(trie, prefix, value)

Specs

put(t(), prefix(), any()) :: t()

Puts value under prefix in the trie.

This always uses an exact match for prefix, replacing its value if it exists. Any errors are silently ignored as the tree is always returned.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", 0)
...> |> put("1.1.1.1", 1)
...> |> put("1.1.1.1", "x")
iex>
iex> get(ipt, "1.1.1.1")
{"1.1.1.1", "x"}

update(trie, prefix, fun)

Specs

update(t(), prefix(), (any() -> any())) :: t()

Lookup prefix and update the matched entry, only if found.

Uses longest prefix match, so search prefix is usually matched by some less specific prefix. If matched, fun is called on its value. If prefix had no longest prefix match, the trie is returned unchanged.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", 0)
...> |> update("1.1.1.0", fn x -> x + 1 end)
...> |> update("1.1.1.1", fn x -> x + 1 end)
...> |> update("2.2.2.2", fn x -> x + 1 end)
iex> get(ipt, "1.1.1.0/24")
{"1.1.1.0/24", 2}
iex> lookup(ipt, "2.2.2.2")
nil

update(trie, prefix, default, fun)

Specs

update(t(), prefix(), any(), (any() -> any())) :: t()

Lookup prefix and, if found, update its value or insert the default.

Uses longest prefix match, so search prefix is usually matched by some less specific prefix. If matched, fun is called on the entry's value. If prefix had no longest prefix match, the default is inserted and fun is not called.

Example

iex> ipt = new()
...> |> update("1.1.1.0/24", 0, fn x -> x + 1 end)
...> |> update("1.1.1.0", 0, fn x -> x + 1 end)
...> |> update("1.1.1.1", 0, fn x -> x + 1 end)
iex> lookup(ipt, "1.1.1.2")
{"1.1.1.0/24", 2}

values(trie)

Specs

values(t()) :: [any()]

Return all the values stored in all radix trees in trie.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", 1)
...> |> put("2.2.2.0/24", 2)
...> |> put("acdc:1975::/32", 3)
...> |> put("acdc:2021::/32", 4)
iex>
iex> values(ipt)
[1, 2, 3, 4]

values(trie, type)

Specs

values(t(), integer() | [integer()]) :: [any()]

Return the values stored in the radix trees in trie for given type.

Where type is a either single maxlen or a list thereof.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", 1)
...> |> put("2.2.2.0/24", 2)
...> |> put("acdc:1975::/32", 3)
...> |> put("acdc:2021::/32", 4)
iex>
iex> values(ipt, 32)
[1, 2]
iex>
iex> values(ipt, 128)
[3, 4]
iex>
iex> values(ipt, 48)
[]
iex>
iex> values(ipt, [32, 48, 128])
[1, 2, 3, 4]