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

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}

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::/32", "rock"},
  {"acdc:1976::/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"

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

Specs

get_and_update(
  t(),
  prefix(),
  (nil | {bitstring(), any()} -> {any(), any()} | :pop)
) ::
  {any(), t()}

Updates a key,value-pair in trie by invoking fun with the result of an exact match.

The callback fun is called with:

• {bits, original_value} if an exact match was found, or
• nil, in case the search prefix is not present in the trie

where bits are the actual bits of given prefix as retrieved from the corresponding radix tree in given trie.

The callback function should return:

• {current_value, new_value}, or
• :pop.

When {current_value, new_value} is returned:

• the new_value is stored in the trie under given prefix, and
• {current_value, trie} is returned.

When the callback passes back :pop:

• the {prefix, original_value}-pair is deleted from the trie, and
• {original_value, trie} is returned.

If the callback passes back :pop when its argument was nil then {nil, trie} is returned, where trie is unchanged.

If something similar is required, but based on a longest prefix match, perhaps Iptrie.update/3 or Iptrie.update/4 is better suited.

Example

iex> counter = fn {_, v} -> {v, v + 1}
...>   nil -> {0, 1}
...> end
iex> ipt = new()
iex> {org, ipt} = get_and_update(ipt, "1.1.1.1", counter)
iex> org
0
iex> get(ipt, "1.1.1.1")
{"1.1.1.1", 1}
iex> {org, ipt} = get_and_update(ipt, "1.1.1.1/24", counter)
iex> org
0
iex> get(ipt, "1.1.1.0/24")
{"1.1.1.0/24", 1}
iex> {org, ipt} = get_and_update(ipt, "1.1.1.0/24", fn _ -> :pop end)
iex> org
1
iex> get(ipt, "1.1.1.0/24")
nil

# aggregate stats on a /24
iex> count = fn {_, v} -> {v, v + 1}
...>   nil -> {0, 1}
...> end
iex> track = fn ip -> Pfx.new(ip) |> Pfx.keep(24) end
iex>
iex> ipt = new()
iex> {_, ipt} = get_and_update(ipt, track.("1.1.1.1"), count)
iex> {_, ipt} = get_and_update(ipt, track.({1, 1, 1, 2}), count)
iex> {_, ipt} = get_and_update(ipt, track.("acdc::/64"), count)
iex> {org, ipt} = get_and_update(ipt, track.({{1, 1, 1, 3}, 32}), count)
iex> org
2
iex> get(ipt, "1.1.1.0/24")
{"1.1.1.0/24", 3}
iex> get(ipt, "acdc::/24")
{"acdc::/24", 1}

# note that Pfx.keep({1, 1, 1, 2}, 24) yields {1, 1, 1, 0} since its
# return value mimics its argument and thus results in a full prefix,
# hence the need for track.(ip)

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

iana_special(Pfx.prefix(), atom() | nil) :: nil | map() | any()

See Iptrie.Iana.lookup/2.

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

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(), Keyword.t()) :: [{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, unless the option :exclude is set to true, the search key will be included in the result if present. Any other value for :exclude is interpreted as false, which means the default action is to include the search key, if present.

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")
[]
#
# exclusive search
#
iex> less(ipt, "1.1.1.0/30", exclude: true)
[{"1.1.1.0/25", "A25-lower"}]

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::/32", 3}
iex>
iex> lookup(ipt, "3.3.3.3")
nil
iex> lookup(ipt, "3.3.3.300")
** (ArgumentError) expected an 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}

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::/32", "acdc:2021::/32"]
 iex> values(t) |> Enum.sum()
 1 + 7 + 3 + 4 + 6

Specs

minimize(t()) :: t()

Minimizes a trie by pruning and removing more specific prefixes, where possible.

Two neighbours storing the same value are be combined when there is no parent. If there is a parent that also stores the same value, the neighbors are deleted. In case the parent stores a different value, the neighbours remain in the tree.

Any other more specific prefixes that store the same value as a less specific prefix are removed from the tree.

For more control on handling values encountered, use minimize/2.

Examples

Both neighbouring /25s are combined (no parent) and the /26 is removed as well.

iex> [{"1.1.1.0/26", true}, {"1.1.1.0/25", true}, {"1.1.1.128/25", true}]
...> |> new()
...> |> minimize()
...> |> to_list()
...> |> Enum.map(fn {k, v} -> {"#{k}", v} end)
[{"1.1.1.0/24", true}]

The /25s cannot be combined since their parent exists and has a different value.

iex> [{"1.1.1.0/24", false}, {"1.1.1.0/25", true}, {"1.1.1.128/25", true}]
...> |> new()
...> |> minimize()
...> |> to_list()
...> |> Enum.map(fn {k,v} -> {"#{k}", v} end)
[{"1.1.1.0/25", true}, {"1.1.1.0/24", false}, {"1.1.1.128/25", true}]

Only 1.1.1.128/25 can be combined with 1.1.1.0/24.

iex> [{"1.1.1.0/24", 1}, {"1.1.1.0/25", 0}, {"1.1.1.128/25", 1}]
...> |> new()
...> |> minimize()
...> |> to_list()
...> |> Enum.map(fn {k,v} -> {"#{k}", v} end)
[{"1.1.1.0/25", 0}, {"1.1.1.0/24", 1}]

Works across all types of radix trees in the Iptrie.t/0.

iex> [
...> {"1.1.1.0/25", 4},
...> {"acdc:1975::/32", 6},
...> {"1.1.1.128/25", 4},
...> {"acdc::/16", 6},
...> {"ac-dc-00-00-00-00/16", 48},
...> {"ac-dc-19-75-00-00/32", 48}
...> ]
...> |> new()
...> |> minimize()
...> |> to_list()
...> |> Enum.map(fn {k, v} -> {"#{k}", v} end)
[
  {"1.1.1.0/24", 4},
  {"AC-DC-00-00-00-00/16", 48},
  {"acdc::/16", 6}
]

Specs

minimize(t(), function()) :: t()

Minimizes a trie by pruning and removing more specific prefixes, where possible.

fun has function signature (any, any) -> {:ok, any} | nil. Whenever prefixes are found that could be combined, fun is called with their values.

If fun returns nil, nothing happens.

In case of a less and a more specific prefix and an {:ok, value}, the value is stored under the less specific prefix and the more specific prefix is deleted. fun is called with the less specific prefix's value as its first argument and the more specific prefix's value as its second argument.

In case of two neighbours, a non-existing parent and an {:ok, value}, the value is stored under the parent and the two neighbors are deleted. fun is called with the leftmost neighbour's value as its first argument while the second argument is the rightmost neighbour's value.

Examples

Summarize statistics to their least specific prefix.

iex> f = fn v1, v2 -> {:ok, v1 + v2} end
iex> [{"1.1.1.0/26", 10}, {"1.1.1.0/25", 20}, {"1.1.1.128/25", 30}]
...> |> new()
...> |> minimize(f)
...> |> to_list()
...> |> Enum.map(fn {k, v} -> {"#{k}", v} end)
[{"1.1.1.0/24", 60}]

Same, but this time the least specific prefix is also present in the tree.

iex> f = fn v1, v2 -> {:ok, v1 + v2} end
iex> [{"1.1.1.0/24", 12}, {"1.1.1.0/26", 10}, {"1.1.1.0/25", 10}, {"1.1.1.128/25", 10}]
...> |> new()
...> |> minimize(f)
...> |> to_list()
...> |> Enum.map(fn {k, v} -> {"#{k}", v} end)
[{"1.1.1.0/24", 42}]

Specs

more(t(), prefix(), Keyword.t()) :: [{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, unless the option :exclude is set to true the search key, if present, will be included in the results. Any other value for :exclude is ignored, which means the default action is to include the search key (if present).

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.1.0/24", "A24")
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.0/24", "A24"},
  {"1.1.1.128/25", "A25-upper"}
]
#
# exclusive search
#
iex> more(ipt, "1.1.1.0/24", exclude: true)
[
  {"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"}]}

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

prune(t(), (tuple() -> nil | {:ok, any()}), Keyword.t()) :: t()

Prunes given trie by calling fun on neighboring prefixes, possibly replacing them with their parent.

The callback fun is invoked with either a 5- or a 6-tuple:

• {p0, p1, v1, p2, v2} for neighboring p1, p2, their parent p0 is not in trie
• {p0, v0, p1, v1, p2, v2} for the parent, its value and that of its two neighboring children.

The callback decides what happens by returning either:

• {:ok, value}, value will be stored under p0 and the neighboring prefixes p1, p2 are deleted
• nil (or anything else really), in which case the tree is not changed.

Examples

iex> adder = fn
...>   {_p0, _p1, v1, _p2, v2} -> {:ok, v1 + v2}
...>   {_p0, v0, _p1, v1, _p2, v2} -> {:ok, v0 + v1 + v2}
...> end
iex> ipt = new()
...> |> put("1.1.1.0/26", 0)
...> |> put("1.1.1.64/26", 1)
...> |> put("1.1.1.128/26", 2)
...> |> put("1.1.1.192/26", 3)
iex> prune(ipt, adder)
...> |> to_list()
...> |> Enum.map(fn {p, v} -> {"#{p}", v} end)
[
  {"1.1.1.0/25", 1},
  {"1.1.1.128/25", 5}
]
iex>
iex> prune(ipt, adder, recurse: true)
...> |> to_list()
...> |> Enum.map(fn {p, v} -> {"#{p}", v} end)
[{"1.1.1.0/24", 6}]

# summerize all /24's inside 10.10.0.0/16
# -> only 10.10.40.0/24 is missing
iex> slash24s = Pfx.partition("10.10.0.0/16", 24)
...> |> Enum.with_index()
...> |> new()
...> |> delete("10.10.40.0/24")
iex>
iex> prune(slash24s, fn _ -> {:ok, 0} end, recurse: true)
...> |> to_list()
...> |> Enum.map(fn {p, v} -> {"#{p}", v} end)
[
  {"10.10.0.0/19", 0},
  {"10.10.32.0/21", 0},
  {"10.10.41.0/24", 41},
  {"10.10.42.0/23", 0},
  {"10.10.44.0/22", 0},
  {"10.10.48.0/20", 0},
  {"10.10.64.0/18", 0},
  {"10.10.128.0/17", 0}
]

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()
...> |> put([{"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"}

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::/32" => 3,
  "acdc:2021::/32" => 4
}

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

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}