Iptrie (Iptrie v0.4.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 prefix used as determined by their maxlen property after encoding it as a Pfx.t/0 struct. That way, IPv4 prefixes (maxlen: 32) use a different radix tree as opposed to IPv6 (maxlen: 128) or other types.

Iptrie has a bias towards IPv4, IPv6, EUI-48 and EUI-64, since it uses Pfx to convert arguments to a Pfx.t/0 struct. 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 arguments given, if possible.

IPv4/IPv6

iex> ipt = new()
...> |> put("1.2.3.0/24", "v4")
...> |> put("128.0.0.0/8", "v4-128")
...> |> put("acdc:1975::/32", "T.N.T")
...> |> put("acdc:1978::/32", "Powerage")
...> |> put("0.0.0.0/0", "v4 default")
...> |> put("::/0", "no dynamite")
iex>
iex> # 3 longest prefix matches that find the same prefix
iex> lookup(ipt, "1.2.3.128")
{"1.2.3.0/24", "v4"}
iex> lookup(ipt, {{1, 2, 3, 128}, 32})
{{{1, 2, 3, 0}, 24}, "v4"}
iex>
iex> lookup(ipt, %Pfx{bits: <<1, 2, 3, 128>>, maxlen: 32})
{%Pfx{bits: <<1, 2, 3>>, maxlen: 32}, "v4"}
iex>
iex> lookup(ipt, "acdc:1975::")
{"acdc:1975:0:0:0:0:0:0/32", "T.N.T"}
iex>
iex> # separate trees, separate default "routes"
iex> lookup(ipt, "10.11.12.13")
{"0.0.0.0/0", "v4 default"}
iex> lookup(ipt, "abba::")
{"0:0:0:0:0:0:0:0/0", "no dynamite"}
iex>
iex> # visualize the IPv4 & IPv6 radix trees
iex> kv32 = fn {k, v} -> "#{Pfx.new(k, 32)}<br/>#{v}" end
iex> radix(ipt, 32)
...> |> Radix.dot(label: "IPv4", kv_tostr: kv32)
...> |> (&File.write("img/ipv4.dot", &1)).()
iex> kv128 = fn {k, v} -> "#{Pfx.new(k, 128)}<br/>#{v}" end
iex> radix(ipt, 128)
...> |> Radix.dot(label: "IPv6", kv_tostr: kv128)
...> |> (&File.write("img/ipv6.dot", &1)).()

The radix trees in the example above look like this:

ipv4 ipv6

Others

Iptrie can also be used to do longest prefix match lookup for other types of prefixes, like e.g. MAC addresses:

iex> ipt = new()
...> |> put("00-22-72-00-00-00/24", "American Micro-Fuel Device")
...> |> put("00-d0-ef-00-00-00/24", "IGT")
...> |> put("08-61-95-00-00-00/24", "Rockwell Automation")
iex>
iex> lookup(ipt, "00-d0-ef-aa-bb-cc")
{"00-D0-EF-00-00-00/24", "IGT"}
iex>
iex> # longest match for partial prefix
iex> lookup(ipt, "08-61-95-11-22-00/40") |> elem(1)
"Rockwell Automation"
iex>
iex> kv48 = fn {k, v} -> "#{Pfx.new(k, 48)}<br/>#{v}" end
iex> radix(ipt, 48)
...> |> Radix.dot(label: "MAC OUI", kv_tostr: kv48)
...> |> (&File.write("img/mac.dot", &1)).()

mac

Iptrie recognizes EUI-48 and EUI-64 prefixes. Note that EUI-64 using ':' as punctuation might come out as an IPv6, in which case Pfx.from_mac/1 should be used to create a prefix before putting it in the trie.

Since prefixes are stored in specific radix trees based on the maxlen of given prefix, you could also mix IPv4, IPv6, EUI-48, EUI-64 prefixes and possibly others, in a single Iptrie.

Link to this section Summary

Types

A prefix represented as an Pfx.t/0 struct, an Pfx.ip_address/0, Pfx.ip_prefix/0 or a string in IPv4 CIDR, IPv6, EUI-48 or EUI-64 format.

t()

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

The type of a prefix is its maxlen property.

Functions

Returns the number of prefix,value-pairs in given trie.

Returns the number of prefix,value-pairs for given type in trie.

Deletes a prefix,value-pair from trie using an exact match for prefix.

Drops given prefixes from trie using an exact match.

Returns true if the given trie is empty, false otherwise.

Returns true if the radix tree for given type in trie is empty, false otherwise.

Fetches the prefix,value-pair for given prefix from trie.

Fetches the prefix,value-pair for given prefix from trie.

Returns a new Iptrie, keeping only the prefix,value-pairs for which fun returns truthy.

Finds a prefix,value-pair for given prefix from trie using a longest prefix match.

Finds a prefix,value-pair for given prefix from trie using a longest prefix match.

Returns the prefix,value-pair stored under given prefix in trie, using an exact match.

Returns true if given prefix is present in trie, false otherwise.

Returns true if trie has given type, false otherwise.

Returns all prefixes stored in all available radix trees in trie.

Returns the prefixes stored in the radix tree in trie for given type.

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

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

Merges trie1 and trie2 into a new Iptrie.

Merges trie1 and trie2 into a new Iptrie, resolving conflicts through fun.

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

Creates an new, empty Iptrie.

Creates a new Iptrie, populated via a list of prefix,value-pairs.

Removes the value associated with prefix and returns the matched prefix,value-pair and the new Iptrie.

Puts the prefix,value-pairs in elements into trie.

Puts value under prefix in trie.

Returns the Radix tree for given type in trie.

Invokes fun on all prefix,value-pairs in all radix trees in trie.

Invokes fun on each prefix,value-pair in the radix tree of given type in trie.

Splits trie into two Iptries using given list of prefixes.

Returns a new Iptrie containing only given prefixes that were found in trie.

Returns all prefix,value-pairs from all available radix trees in trie.

Returns the prefix,value-pairs from the radix trees in trie for given type.

Returns a list of types available in given trie.

Looks up prefix and update the matched entry, only if found.

Looks up prefix and, if found, update its value or insert the default under prefix.

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

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

Link to this section Types

Specs

prefix() :: Pfx.prefix()

A prefix represented as an Pfx.t/0 struct, an Pfx.ip_address/0, Pfx.ip_prefix/0 or a string in IPv4 CIDR, IPv6, EUI-48 or EUI-64 format.

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 (exact or longest prefix match) lookups of any type of prefix, it has a bias towards IP prefixes. So, any binaries (strings) are first interpreted as IPv4 CIDR/IPv6 strings and as EUI-48/64 string second, while tuples of address digits and/or {address-digits, length} are interpreted as IPv4 or IPv6 representations.

Specs

type() :: non_neg_integer()

The type of a prefix is its maxlen property.

Link to this section Functions

Specs

count(t()) :: non_neg_integer()

Returns the number of prefix,value-pairs in given trie.

Note that this requires traversal of radix tree(s) present in trie.

Example

iex> t = new([{"1.1.1.1", 1}, {"acdc::", 2}])
iex> count(t)
2

Specs

count(t(), type()) :: non_neg_integer()

Returns the number of prefix,value-pairs for given type in trie.

If trie has no radix tree of given type, 0 is returned. Use Iptrie.has_type?/2 to check if a trie holds a given type.

Example

iex> t = new([{"1.1.1.1", 1}, {"acdc::", 2}])
iex> count(t, 32)
1
iex> count(t, 128)
1
iex> types(t)
...> |> Enum.map(fn type -> {type, count(t, type)} end)
[{32, 1}, {128, 1}]

Specs

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

Deletes a prefix,value-pair from trie using an exact match for prefix.

If the prefix does not exist in the trie, the latter is returned unchanged.

Examples

iex> ipt = new()
...> |> put("1.1.1.0/24", "one")
...> |> put("2.2.2.0/24", "two")
iex>
iex> for pfx <- keys(ipt), do: "#{pfx}"
["1.1.1.0/24", "2.2.2.0/24"]
iex>
iex> ipt = delete(ipt, "1.1.1.0/24")
iex> for pfx <- keys(ipt), do: "#{pfx}"
["2.2.2.0/24"]

Specs

drop(t(), [prefix()]) :: t()

Drops given prefixes from trie using an exact match.

If a given prefix does not exist in trie it is ignored.

Example

# drop 2 existing prefixes and ignore the third
iex> t = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"11-22-33-00-00-00/24", 3}])
iex> t2 = drop(t, ["1.1.1.0/24", "11-22-33-00-00-00/24", "3.3.3.3"])
iex> for pfx <- keys(t2), do: "#{pfx}"
["2.2.2.0/24"]

Specs

empty?(t()) :: boolean()

Returns true if the given trie is empty, false otherwise.

Examples

 iex> t = new([{"1.1.1.1", 1}, {"11-22-33-44-55-66", 2}])
 iex> empty?(t)
 false

 iex> new() |> empty?()
 true

Specs

empty?(t(), type()) :: boolean()

Returns true if the radix tree for given type in trie is empty, false otherwise.

Example

 iex> t = new([{"1.1.1.1", 1}, {"11-22-33-44-55-66", 2}])
 iex> empty?(t, 32)
 false
 iex> empty?(t, 48)
 false
 iex> empty?(t, 128)
 true
Link to this function

fetch(trie, prefix, opts \\ [])

View Source

Specs

fetch(t(), prefix(), keyword()) :: {:ok, {prefix(), any()}} | {:error, atom()}

Fetches the prefix,value-pair for given prefix from trie.

Returns one of:

  • {:ok, {prefix, value}} in case of success
  • {:error, :notfound} if prefix is not present in trie
  • {:error, :einval} in case of an invalid prefix, and
  • {:error, :bad_trie} in case trie is not an Iptrie.t/0

Optionally fetches based on a longest prefix match by specifying match: :lpm.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", "one")
...> |> put("2.2.2.0/24", "two")
iex>
iex> fetch(ipt, "1.1.1.0/24")
{:ok, {"1.1.1.0/24", "one"}}
iex>
iex> fetch(ipt, "1.1.1.1")
{:error, :notfound}
iex>
iex> fetch(ipt, "1.1.1.1", match: :lpm)
{:ok, {"1.1.1.0/24", "one"}}
iex>
iex> fetch(ipt, "13.13.13.333")
{:error, :einval}
Link to this function

fetch!(trie, prefix, opts \\ [])

View Source

Specs

fetch!(t(), prefix(), keyword()) :: {prefix(), any()} | KeyError | ArgumentError

Fetches the prefix,value-pair for given prefix from trie.

In case of success, returns {prefix, value}. If prefix is not present, raises a KeyError. If prefix could not be encoded, raises an ArgumentError.

Optionally fetches based on a longest prefix match by specifying match: :lpm.

Example

iex> ipt = new()
...> |> put("10.10.10.0/24", "ten")
...> |> put("11.11.11.0/24", "eleven")
iex>
iex> fetch!(ipt, "10.10.10.0/24")
{"10.10.10.0/24", "ten"}
iex>
iex> fetch!(ipt, "11.11.11.11", match: :lpm)
{"11.11.11.0/24", "eleven"}
iex>
iex> fetch!(ipt, "12.12.12.12")
** (KeyError) prefix "12.12.12.12" not found

iex> ipt = new()
iex> fetch!(ipt, "13.13.13.333")
** (ArgumentError) expected a valid prefix, got "13.13.13.333"

Specs

filter(t(), (prefix(), any() -> boolean())) :: t()

Returns a new Iptrie, keeping only the prefix,value-pairs for which fun returns truthy.

The signature for fun is (prefix, value -> boolean), where the value is stored under prefix in the trie. Radix trees that are empty, are removed from the new Iptrie.

Example

iex> ipt = new()
...> |> put("acdc:1975::/32", "rock")
...> |> put("acdc:1976::/32", "rock")
...> |> put("abba:1975::/32", "pop")
...> |> put("abba:1976::/32", "pop")
...> |> put("1.1.1.0/24", "v4")
iex>
iex> filter(ipt, fn pfx, _value -> pfx.maxlen == 32 end)
...> |> to_list()
[{%Pfx{bits: <<1, 1, 1>>, maxlen: 32}, "v4"}]
iex>
iex> filter(ipt, fn _pfx, value -> value == "rock" end)
...> |> to_list()
...> |> Enum.map(fn {pfx, value} -> {"#{pfx}", value} end)
[
  {"acdc:1975:0:0:0:0:0:0/32", "rock"},
  {"acdc:1976:0:0:0:0:0:0/32", "rock"}
]

Specs

find(t(), prefix()) :: {:ok, {prefix(), any()}} | {:error, atom()}

Finds a prefix,value-pair for given prefix from trie using a longest prefix match.

Convenience wrapper for Iptrie.fetch/3 with match: :lpm.

Example

iex> ipt = new()
...> |> put("1.1.1.0/24", "one")
...> |> put("2.2.2.0/24", "two")
iex>
iex> find(ipt, "1.1.1.0/24")
{:ok, {"1.1.1.0/24", "one"}}
iex>
iex> find(ipt, "12.12.12.12")
{:error, :notfound}
iex>
iex> find(ipt, "13.13.13.333")
{:error, :einval}

Specs

find!(t(), prefix()) :: {prefix(), any()} | KeyError | ArgumentError

Finds a prefix,value-pair for given prefix from trie using a longest prefix match.

Convenience wrapper for Iptrie.fetch!/3 with match: :lpm.

Examples

iex> ipt = new()
...> |> put("10.10.10.0/24", "ten")
...> |> put("11.11.11.0/24", "eleven")
iex>
iex> find!(ipt, "10.10.10.0/24")
{"10.10.10.0/24", "ten"}
iex>
iex> find!(ipt, "10.10.10.10")
{"10.10.10.0/24", "ten"}
iex>
iex> find!(ipt, "12.12.12.12")
** (KeyError) prefix "12.12.12.12" not found

iex> ipt = new()
iex> find!(ipt, "13.13.13.333")
** (ArgumentError) expected a valid prefix, got "13.13.13.333"
Link to this function

get(trie, prefix, default \\ nil)

View Source

Specs

get(t(), prefix(), any()) :: {prefix(), any()} | any()

Returns the prefix,value-pair stored under given prefix in trie, using an exact match.

If prefix is not found, default is returned. If default is not provided, nil is used.

Example

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> get(ipt, "2.2.2.0/30")
nil
iex> get(ipt, "2.2.2.0/30", :notfound)
:notfound
Link to this function

has_prefix?(trie, prefix, opts \\ [])

View Source

Specs

has_prefix?(t(), prefix(), keyword()) :: boolean()

Returns true if given prefix is present in trie, false otherwise.

The check is done based on an exact match, unless the option match: :lpm is provided to match based on longest prefix match.

Example

iex> t = new([{"1.1.1.1", 1}, {"1.1.1.0/24", 2}, {"acdc::/16", 3}])
iex> has_prefix?(t, "1.1.1.2")
false
iex> has_prefix?(t, "1.1.1.2", match: :lpm)
true
iex> has_prefix?(t, "1.1.1.1")
true
iex> has_prefix?(t, "acdc::/16")
true

Specs

has_type?(t(), type()) :: boolean()

Returns true if trie has given type, false otherwise.

An Iptrie groups prefixes into radix trees by their maxlen property, also known as the type of prefix. Use Iptrie.types/1 to get a list of all available types.

Example

iex> t = new([{"1.1.1.1", 1}])
iex> has_type?(t, 32)
true
iex> has_type?(t, 128)
false

Specs

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

Returns all prefixes stored in all available radix trees in trie.

The prefixes are reconstructed as Pfx.t/0 by combining the stored bitstrings with the Radix-tree's type, that is the maxlen property associated with the radix tree whose keys are being retrieved.

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)
[
  %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}
]
iex>
iex> radix(ipt, 32) |> Radix.keys()
[
  <<1, 1, 1>>,
  <<2, 2, 2>>
]

Specs

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

Returns the prefixes stored in the radix tree in trie for given type.

Note that the Iptrie keys are returned as Pfx.t/0 structs.

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)
[]

Specs

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

Returns 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.

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")
[]

Specs

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

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

Returns nil if there is no match for search prefix.

Examples

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> lookup(ipt, "1.1.1.1")
{"1.1.1.0/24", 1}
iex> lookup(ipt, "acdc:1975:1::")
{"acdc:1975:0:0:0:0:0:0/32", 3}
iex>
iex> lookup(ipt, "3.3.3.3")
nil
iex> lookup(ipt, "3.3.3.300")
** (ArgumentError) expected a ipv4/ipv6 CIDR or EUI-48/64 string, got "3.3.3.300"

Specs

merge(t(), t()) :: t()

Merges trie1 and trie2 into a new Iptrie.

Adds all prefix,value-pairs of trie2 to trie1, overwriting any existing entries when prefixes match (based on exact match).

Example

iex> t1 = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}])
iex> t2 = new([{"2.2.2.0/24", 22}, {"3.3.3.0/24", 3}])
iex> t = merge(t1, t2)
iex> count(t)
3
iex> get(t, "1.1.1.0/24")
{"1.1.1.0/24", 1}
iex> get(t, "2.2.2.0/24")
{"2.2.2.0/24", 22}
iex> get(t, "3.3.3.0/24")
{"3.3.3.0/24", 3}
Link to this function

merge(trie1, trie2, fun)

View Source

Specs

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

Merges trie1 and trie2 into a new Iptrie, resolving conflicts through fun.

In cases where a prefix is present in both tries, the conflict is resolved by calling fun with the prefix (a Pfx.t/0), its value in trie1 and its value in trie2. The function's return value will be stored under the prefix in the merged trie.

Example

 iex> t1 = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"acdc:1975::/32", 3}])
 iex> t2 = new([{"3.3.3.0/24", 4}, {"2.2.2.0/24", 5}, {"acdc:2021::/32", 6}])
 iex> t = merge(t1, t2, fn _pfx, v1, v2 -> v1 + v2 end)
 iex> count(t)
 5
 iex> get(t, "2.2.2.0/24")
 {"2.2.2.0/24", 7}
 iex> for ip4 <- keys(t, 32), do: "#{ip4}"
 ["1.1.1.0/24", "2.2.2.0/24", "3.3.3.0/24"]
 iex> for ip6 <- keys(t, 128), do: "#{ip6}"
 ["acdc:1975:0:0:0:0:0:0/32", "acdc:2021:0:0:0:0:0:0/32"]
 iex> values(t) |> Enum.sum()
 1 + 7 + 3 + 4 + 6

Specs

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

Returns 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.

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"}
]

Specs

new() :: t()

Creates an new, empty Iptrie.

Example

iex> Iptrie.new()
%Iptrie{}

Specs

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

Creates a new Iptrie, populated via a list of prefix,value-pairs.

Example

iex> elements = [
...>  {"1.1.1.0/24", "net1"},
...>  {{{1, 1, 2, 0}, 24}, "net2"},
...>  {"acdc:1975::/32", "TNT"}
...> ]
iex> ipt = Iptrie.new(elements)
iex> radix(ipt, 32)
{0, {22, [{<<1, 1, 1>>, "net1"}], [{<<1, 1, 2>>, "net2"}]}, nil}
iex> radix(ipt, 128)
{0, nil, [{<<172, 220, 25, 117>>, "TNT"}]}
Link to this function

pop(trie, prefix, opts \\ [])

View Source

Specs

pop(t(), prefix(), keyword()) :: {{prefix(), any()}, t()}

Removes the value associated with prefix and returns the matched prefix,value-pair and the new Iptrie.

Options include:

  • default: value to return if prefix could not be matched (defaults to nil)
  • match: :lpm to match on longest prefix instead of an exact match

Examples

iex> t = new([{"1.1.1.0/24", 1}, {"1.1.1.99", 2}, {"acdc:1975::/32", 3}])
iex> {{"1.1.1.99", 2}, t2} = pop(t, "1.1.1.99")
iex> get(t2, "1.1.1.99")
nil

iex> t = new([{"1.1.1.0/24", 1}, {"1.1.1.99", 2}, {"acdc:1975::/32", 3}])
iex> # t is unchanged
iex> {{"1.1.1.33", :notfound}, ^t} = pop(t, "1.1.1.33", default: :notfound)

iex> t = new([{"1.1.1.0/24", 1}, {"1.1.1.99", 2}, {"acdc:1975::/32", 3}])
iex> # lpm match
iex> {{"1.1.1.0/24", 1}, t2} = pop(t, "1.1.1.33", match: :lpm)
iex> get(t2, "1.1.1.0/24")
nil

Specs

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

Puts the prefix,value-pairs in elements into trie.

This always uses an exact match for prefix, updating its value if it exists.

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"}
Link to this function

put(trie, prefix, value)

View Source

Specs

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

Puts value under prefix in trie.

This always uses an exact match for prefix, replacing its value if it exists.

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"}

Specs

radix(t(), type()) :: Radix.tree()

Returns the Radix tree for given type in trie.

If trie has no radix tree for given type it will return a new empty radix tree.

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> radix(ipt, 32)
{0, {6, [{<<1, 1, 1>>, 1}], [{<<2, 2, 2>>, 2}]}, nil}
iex>
iex> radix(ipt, 128)
{0, nil, {18, [{<<172, 220, 25, 117>>, 3}], [{<<172, 220, 32, 33>>, 4}]}}
iex> radix(ipt, 48)
{0, nil, nil}
iex>
iex> has_type?(ipt, 48)
false

Specs

reduce(t(), any(), (Pfx.t(), any(), any() -> any())) :: any()

Invokes fun on all prefix,value-pairs in all radix trees in trie.

The function fun is called with the prefix (a Pfx.t/0 struct), value and acc accumulator and should return an updated accumulator. The result is the last accumulator returned.

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> reduce(ipt, 0, fn _pfx, value, acc -> acc + value end)
10
iex>
iex> reduce(ipt, %{}, fn pfx, value, acc -> Map.put(acc, "#{pfx}", value) end)
%{
  "1.1.1.0/24" => 1,
  "2.2.2.0/24" => 2,
  "acdc:1975:0:0:0:0:0:0/32" => 3,
  "acdc:2021:0:0:0:0:0:0/32" => 4
}
Link to this function

reduce(trie, type, acc, fun)

View Source

Specs

reduce(t(), type(), any(), (Pfx.t(), any(), any() -> any())) :: any()

Invokes fun on each prefix,value-pair in the radix tree of given type in trie.

The function fun is called with the prefix (a Pfx.t/0 struct), value and acc accumulator and should return an updated accumulator. The result is the last accumulator returned.

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> reduce(ipt, 32, 0, fn _pfx, value, acc -> acc + value end)
3
iex> reduce(ipt, 48, 0, fn _pfx, value, acc -> acc + value end)
0
iex> reduce(ipt, 128, 0, fn _pfx, value, acc -> acc + value end)
7
Link to this function

split(trie, prefixes, opts \\ [])

View Source

Specs

split(t(), [prefix()], keyword()) :: {t(), t()}

Splits trie into two Iptries using given list of prefixes.

Returns a new trie with prefix,value-pairs that were matched by given prefixes and the old trie with those pairs removed. If a prefix was not found in given trie it is ignored.

By default an exact match is used, specify match: :lpm to use longest prefix match instead.

Examples

iex> t = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"3.3.3.0/30", 3}])
iex> {t2, t3} = split(t, ["2.2.2.0/24", "3.3.3.0/30"])
iex> count(t2)
2
iex> get(t2, "2.2.2.0/24")
{"2.2.2.0/24", 2}
iex> get(t2, "3.3.3.0/30")
{"3.3.3.0/30", 3}
iex> count(t3)
1
iex> get(t3, "1.1.1.0/24")
{"1.1.1.0/24", 1}

# use longest prefix match
iex> t = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"3.3.3.0/30", 3}])
iex> {t4, t5} = split(t, ["2.2.2.2", "3.3.3.3"], match: :lpm)
iex> count(t4)
2
iex> get(t4, "2.2.2.0/24")
{"2.2.2.0/24", 2}
iex> get(t4, "3.3.3.0/30")
{"3.3.3.0/30", 3}
iex> count(t5)
1
iex> get(t5, "1.1.1.0/24")
{"1.1.1.0/24", 1}
Link to this function

take(trie, prefixes, opts \\ [])

View Source

Specs

take(t(), [prefix()], keyword()) :: t()

Returns a new Iptrie containing only given prefixes that were found in trie.

If a given prefix does not exist, it is ignored. Optionally specifiy match: :lpm to use a longest prefix match instead of exact, which is the default.

Examples

iex> t = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"acdc::/16", 3}])
iex> t2 = take(t, ["1.1.1.0/24", "acdc::/16"])
iex> count(t2)
2
iex> get(t2, "1.1.1.0/24")
{"1.1.1.0/24", 1}
iex> get(t2, "acdc::/16")
{"acdc:0:0:0:0:0:0:0/16", 3}

# use longest match
iex> t = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"acdc::/16", 3}])
iex> t3 = take(t, ["1.1.1.1", "acdc:1975::1"], match: :lpm)
iex> count(t3)
2
iex> get(t3, "1.1.1.0/24")
{"1.1.1.0/24", 1}
iex> get(t3, "acdc::/16")
{"acdc:0:0:0:0:0:0:0/16", 3}

# ignore missing prefixes
iex> t = new([{"1.1.1.0/24", 1}, {"2.2.2.0/24", 2}, {"acdc::/16", 3}])
iex> t4 = take(t, ["1.1.1.1", "3.3.3.3"], match: :lpm)
iex> count(t4)
1
iex> get(t4, "1.1.1.0/24")
{"1.1.1.0/24", 1}

Specs

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

Returns all prefix,value-pairs from all available radix trees in trie.

Examples

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> to_list(ipt)
[
  {%Pfx{bits: <<1, 1, 1>>, maxlen: 32}, 1},
  {%Pfx{bits: <<2, 2, 2>>, maxlen: 32}, 2},
  {%Pfx{bits: <<0xacdc::16, 0x1975::16>>, maxlen: 128}, 3},
  {%Pfx{bits: <<0xacdc::16, 0x2021::16>>, maxlen: 128}, 4}
]

Specs

to_list(t(), type()) :: [{prefix(), any()}]

Returns the prefix,value-pairs from the radix trees in trie for given type.

If the radix tree for type does not exist, an empty list is returned.

Examples

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> to_list(ipt, 32)
[
  {%Pfx{bits: <<1, 1, 1>>, maxlen: 32}, 1},
  {%Pfx{bits: <<2, 2, 2>>, maxlen: 32}, 2}
]
iex> to_list(ipt, 128)
[
  {%Pfx{bits: <<0xacdc::16, 0x1975::16>>, maxlen: 128}, 3},
  {%Pfx{bits: <<0xacdc::16, 0x2021::16>>, maxlen: 128}, 4}
]
iex> to_list(ipt, 48)
[]

Specs

types(t()) :: [type()]

Returns a list of types available in given trie.

Example

iex> t = new([{"1.1.1.1", 1}, {"2001:db8::", 2}])
iex> types(t)
[32, 128]
Link to this function

update(trie, prefix, fun)

View Source

Specs

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

Looks up 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.

Examples

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
Link to this function

update(trie, prefix, default, fun)

View Source

Specs

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

Looks up prefix and, if found, update its value or insert the default under prefix.

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 under prefix and fun is not called.

Examples

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)
...> |> update("2.2.2.2", 0, fn x -> x + 1 end)
iex> lookup(ipt, "1.1.1.2")
{"1.1.1.0/24", 2}
iex>
iex> # probably not what you wanted:
iex> lookup(ipt, "2.2.2.2")
{"2.2.2.2", 0}

Specs

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

Returns 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]

Specs

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

Returns 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)
[]