Radix (Radix v0.5.0) View Source

A bitwise radix tree for prefix based matching on bitstring keys of any length.

Radix provides a radix tree whose radius is 2, has path-compression and no one-way branching. Entries consist of {key, value}-pairs whose insertion/deletion is always based on an exact key-match. Retrieval can be either exact or based on a longest prefix match.

Example

iex> t = new()
...>     |> put(<<1, 1, 1>>, "1.1.1.0/24")
...>     |> put(<<1, 1, 1, 0::6>>, "1.1.1.0/30")
...>     |> put(<<1, 1, 1, 1::6>>, "1.1.1.4/30")
...>     |> put(<<1, 1, 1, 1::1>>, "1.1.1.128/25")
...>     |> put(<<255>>, "255/8")
iex>
iex> # longest prefix match
iex> lookup(t, <<1, 1, 1, 255>>)
{<<1, 1, 1, 1::1>>, "1.1.1.128/25"}
iex>
iex> # more specific matches (includes search key if present)
iex> more(t, <<1, 1, 1>>)
[
  {<<1, 1, 1, 1::size(6)>>, "1.1.1.4/30"},
  {<<1, 1, 1, 0::size(6)>>, "1.1.1.0/30"},
  {<<1, 1, 1>>, "1.1.1.0/24"},
  {<<1, 1, 1, 1::size(1)>>, "1.1.1.128/25"}
]
iex> # less specific matches (includes search key if present)
iex> less(t, <<1, 1, 1, 3>>)
[
  {<<1, 1, 1, 0::size(6)>>, "1.1.1.0/30"},
  {<<1, 1, 1>>, "1.1.1.0/24"}
]
iex> # exact match
iex> get(t, <<1, 1, 1, 0::6>>)
{<<1, 1, 1, 0::6>>, "1.1.1.0/30"}
iex> get(t, <<2, 2, 2, 2>>)
nil
iex> pruner = fn
...>   {_k0, _k1, _v1, _k2, _v2} -> {:ok, "new parent"}
...>   {_k0, _v0, _k1, _v1, _k2, _v2} -> {:ok, "updated parent"}
...> end
iex> keys(t)
[
  <<1, 1, 1, 0::size(6)>>,
  <<1, 1, 1>>,
  <<1, 1, 1, 1::size(6)>>,
  <<1, 1, 1, 1::size(1)>>,
  <<255>>
]
iex> prune(t, pruner)
...> |> keys()
[
  <<1, 1, 1, 0::size(5)>>,
  <<1, 1, 1>>,
  <<1, 1, 1, 1::size(1)>>,
  <<255>>
]
iex> prune(t, pruner)
...> |> dot()
...> |> (&File.write("assets/readme.dot", &1)).()

The radix tree above, after pruning, looks something like this:

Radix

The tree is represented by two types of nodes:

internal node, as a {bit, left, right}-tuple, and
leaf node, which is either nil or a non-empty list of {key,value}-pairs

The bit denotes the bit position to check in a key during a tree traversal, where 0 means go left and 1 means go right. A bit beyond a key's length is considered to be 0. Path-compression means not all bits are checked during tree traversal, only those that differentiate the keys stored below the current internal node. Hence, branches are formed as keys with different patterns are stored in the tree.

The leaf node can have a list of {key, value}-pairs where all longer keys have all shorter keys as their prefix. In other words, they all agree on the bits that were checked to arrive at that node. The key is stored alongside the value since, due to path-compression, a final match is needed to ensure a correct match. Hence, retrieval functions return the {key, value}-pair, rather than just the value, since the stored key is not always equal to the given search key (e.g. when doing a longest prefix match).

Since binaries are bitstrings too, they work as well:

iex> t = new([{"A.new", "new"}, {"A.newer", "newer"}, {"B.newest", "newest"}])
iex> more(t, "A.") |> Enum.reverse()
[{"A.new", "new"}, {"A.newer", "newer"}]
#
iex> lookup(t, "A.newest")
{"A.new", "new"}
#
iex> more(t, "C.")
[]

Link to this section Summary

Types

acc()

A user supplied accumulator.

key()

A bitstring used as a key to index into the radix tree.

leaf()

A radix leaf node.

tree()

An internal radix tree node.

value()

Any value to be stored in the radix tree.

Functions

adjacencies(tree)

Returns a map where two neighboring key,value-pairs present in tree, are stored under their 'parent' key.

count(tree)

Counts the number of entries by traversing given tree.

delete(tree, key)

Deletes the entry from the tree for a specific key using an exact match.

dot(tree, opts \\ [])

Returns a list of lines describing the tree as a graphviz digraph.

drop(tree, keys)

Drops the given keys from the radix tree using an exact match.

empty?(tree)

Returns true if tree is empty, false otherwise.

fetch(tree, key, opts \\ [])

Fetches the key,value-pair for a key in the given tree.

fetch!(tree, key, opts \\ [])

Fetches the key,value-pair for a specific key in the given tree.

get(tree, key, default \\ nil)

Returns the key,value-pair whose key equals the given search key, or default.

get_and_update(tree, key, fun)

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

keys(tree)

Returns a list of all keys from the radix tree.

less(tree, key, opts \\ [])

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

lookup(tree, key)

Returns the key,value-pair whose key is the longest prefix of key, or nil.

merge(tree1, tree2)

Merges two radix trees into one.

merge(tree1, tree2, fun)

Merges two radix trees into one, resolving conflicts through fun.

minimize(tree, fun)

Minimizes a radix tree by removing more specific keys and pruning adjacent keys, where allowed.

more(tree, key, opts \\ [])

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

new()

Returns a new, empty radix tree.

new(elements)

Return a new radix tree, initialized using given list of {key, value}-pairs.

pop(tree, key, opts \\ [])

Removes the value associated with key and returns the matched key,value-pair and the new tree.

prune(tree, fun, opts \\ [])

Prunes given tree by invoking fun on adjacent keys.

put(tree, elements)

Stores the key,value-pairs from elements in the radix tree.

put(tree, key, value)

Stores the key,value-pair under key in the radix tree.

reduce(tree, acc, fun)

Invokes fun for each key,value-pair in the radix tree with the accumulator.

split(tree, keys, opts \\ [])

Extracts the key,value-pairs associated with keys from tree into a new radix tree.

take(tree, keys, opts \\ [])

Returns a new tree with all the key,value-pairs whose key are in keys.

to_list(tree)

Returns all key,value-pairs in tree as a flat list.

update(tree, key, fun)

Updates a key,value-pair in tree by invoking fun after a longest prefix match lookup.

update(tree, key, default, fun)

Looks up the longest prefix match for given search key in tree and updates its value through fun.

values(tree)

Returns all values stored in the radix tree.

walk(tree, acc, fun, order \\ :inorder)

Invokes fun on all (internal and leaf) nodes of the radix tree using either :inorder, :preorder or :postorder traversal.

Link to this section Types

acc()

Specs

acc() :: any()

A user supplied accumulator.

key()

Specs

key() :: bitstring()

A bitstring used as a key to index into the radix tree.

During tree traversals, bit positions in the key are checked in order to decide whether to go left (0) or right (1). During these checks, bits beyond the current key's length always evaluate to 0. Bit positions are zero-indexed, with bit 0 being the most significant bit.

leaf()

Specs

leaf() :: [{key(), value()}] | nil

A radix leaf node.

A leaf is either nil or a list of key,value-pairs sorted on key-length in descending order. All keys in a leaf have the other, shorter keys, as their prefix.

tree()

Specs

tree() :: {non_neg_integer(), tree() | leaf(), tree() | leaf()}

An internal radix tree node.

An internal node is a three element tuple: {bit, left, right}, where:

bit is the bit position to check in a key
left is a subtree with keys whose bit is 0
right is a subtree with keys whose bit is 1

The keys stored below any given internal node, all agree on the bits checked to arrive at that particular node.

Branches in the tree are only created when storing a new key,value-pair in the tree whose key does not agree with the leaf found during traversal.

This path-compression means not all bits in a key are checked while traversing the tree, only those which differentiate the keys stored below the current internal node. Hence, a final match is needed to ensure a correct match.

value()

Specs

value() :: any()

Any value to be stored in the radix tree.

Link to this section Functions

adjacencies(tree)

Specs

adjacencies(tree()) :: map()

Returns a map where two neighboring key,value-pairs present in tree, are stored under their 'parent' key.

The parent key is 1 bit shorter than that of the two neighboring keys and stores:

{key1, val1, key2, val2}, or
{key1, val1, key2, val2, val3}

If the parent key exists in the tree as well, its value is included as the fifth-element in the resulting tuple.

Example

iex> tree = new()
...> |> put(<<1, 1, 1, 0::6>>, "1.1.1.0/30")
...> |> put(<<1, 1, 1, 1::6>>, "1.1.1.4/30")
...> |> put(<<1, 1, 1, 2::6>>, "1.1.1.8/30")
...> |> put(<<1, 1, 1, 3::6>>, "1.1.1.12/30")
...> |> put(<<1, 1, 1, 1::5>>, "1.1.1.8/29")
iex> adjacencies(tree)
%{
  <<1, 1, 1, 0::5>> => {
    <<1, 1, 1, 0::6>>, "1.1.1.0/30",
    <<1, 1, 1, 1::6>>, "1.1.1.4/30"
  },
  <<1, 1, 1, 1::5>> => {
    <<1, 1, 1, 2::6>>, "1.1.1.8/30",
    <<1, 1, 1, 3::6>>, "1.1.1.12/30",
    "1.1.1.8/29"}
}

count(tree)

Specs

count(tree()) :: non_neg_integer()

Counts the number of entries by traversing given tree.

Example

iex> new([{<<>>, nil}, {<<1>>, 1}, {<<2>>, 2}])
...> |> count
3

delete(tree, key)

Specs

delete(tree(), key()) :: tree()

Deletes the entry from the tree for a specific key using an exact match.

If key does not exist, the tree is returned unchanged.

Example

iex> elms = [{<<1,1>>, 16}, {<<1,1,0>>, 24}, {<<1,1,1,1>>, 32}]
iex> t = new(elms)
iex> t
{0, {23, [{<<1, 1, 0>>, 24}, {<<1, 1>>, 16}],
         [{<<1, 1, 1, 1>>, 32}]
     },
  nil}
iex> delete(t, <<1, 1, 0>>)
{0, {23, [{<<1, 1>>, 16}],
         [{<<1, 1, 1, 1>>, 32}]
     },
  nil}

dot(tree, opts \\ [])

Specs

dot(
  tree(),
  keyword()
) :: [String.t()]

Returns a list of lines describing the tree as a graphviz digraph.

Options include:

:label, defaults to "radix")
:labelloc, defaults to "t"
:rankdir, defaults to "TB"
:ranksep, defaults to "0.5 equally"
:rootcolor, defaults to "orange"
:nodecolor, defaults to "yellow"
:leafcolor, defaults to "green"
:kv_tostr, defaults to an internal function that converts key to dotted decimal string (cidr style)

If supplied via :kv_tostr, the function's signature must be ({key/0, value/0}) :: String.t/0 and where the resulting string must be HTML-escaped. See html-entities.

Works best for smaller trees.

Example

iex> t = new()
...> |> put(<<0, 0>>, "left")
...> |> put(<<1, 1, 1::1>>, "left")
...> |> put(<<128, 0>>, "right")
iex> g = dot(t, label: "example")
iex> File.write("assets/example.dot", g)
:ok

which, after converting with dot, yields the following image:

example

drop(tree, keys)

Specs

drop(tree(), [key()]) :: tree()

Drops the given keys from the radix tree using an exact match.

Any key's that don't exist in the tree, are ignored.

Example

iex> elms = [{<<1, 1>>, 16}, {<<1, 1, 0>>, 24}, {<<1, 1, 1, 1>>, 32}]
iex> t = new(elms)
iex> t
{0, {23, [{<<1, 1, 0>>, 24}, {<<1, 1>>, 16}],
         [{<<1, 1, 1, 1>>, 32}]
     },
  nil}
iex> drop(t, [<<1, 1>>, <<1, 1, 1, 1>>])
{0, [{<<1, 1, 0>>, 24}], nil}

empty?(tree)

Specs

empty?(tree()) :: boolean()

Returns true if tree is empty, false otherwise.

Example

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

fetch(tree, key, opts \\ [])

Specs

fetch(tree(), key(), keyword()) :: {:ok, {key(), value()}} | :error

Fetches the key,value-pair for a key in the given tree.

Returns {:ok, {key, value}} or :error when key is not in the tree. By default an exact match is used, specify match: :lpm to fetch based on a longest prefix match.

Example

iex> t = new([{<<>>, 0}, {<<1>>, 1}, {<<1, 1>>, 2}])
iex> fetch(t, <<1, 1>>)
{:ok, {<<1, 1>>, 2}}
iex> fetch(t, <<2>>)
:error
iex> fetch(t, <<2>>, match: :lpm)
{:ok, {<<>>, 0}}

fetch!(tree, key, opts \\ [])

Specs

fetch!(tree(), key(), keyword()) :: {key(), value()}

Fetches the key,value-pair for a specific key in the given tree.

Returns the {key, value}-pair itself, or raises a KeyError if key is not in the tree. By default an exact match is used, specify match: :lpm to fetch based on a longest prefix match.

Example

iex> t = new([{<<1>>, 1}, {<<1, 1>>, 2}])
iex> fetch!(t, <<1, 1>>)
{<<1, 1>>, 2}
iex> fetch!(t, <<2>>)
** (KeyError) key not found <<0b10>>
iex> fetch!(t, <<1, 1, 1>>, match: :lpm)
{<<1, 1>>, 2}

get(tree, key, default \\ nil)

Specs

get(tree(), key(), any()) :: {key(), value()} | any()

Returns the key,value-pair whose key equals the given search key, or default.

If key is not a bitstring or not present in the radix tree, default is returned. If default is not provided, nil is used.

Example

iex> elements = [{<<1, 1>>, 16}, {<<1, 1, 1>>, 24}, {<<1, 1, 1, 1>>, 32}]
iex> t = new(elements)
iex> get(t, <<1, 1, 1>>)
{<<1, 1, 1>>, 24}
iex> get(t, <<1, 1>>)
{<<1, 1>>, 16}
iex> get(t, <<1, 1, 0::1>>)
nil
iex> get(t, <<1, 1, 0::1>>, :notfound)
:notfound

get_and_update(tree, key, fun)

Specs

get_and_update(
  tree(),
  key(),
  (nil | {key(), value()} -> {value(), value()} | :pop)
) ::
  {value(), tree()}

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

The callback fun is called with:

{key, original_value} if an exact match was found, or
nil, in case the key is not present in tree

The callback function should return:

{current_value, new_value}, or
:pop.

When {current_value, new_value} is returned, the new_value is stored under key and {current_value, tree} is returned. When the callback passes back :pop, the {key, original_value}-pair is deleted from the tree and {original_value, tree} is returned.

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

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

Examples

# update stats, get org value and store new value
iex> count = fn nil -> {0, 1}; {_key, val} -> {val, val+1} end
iex> t = new([{<<1,1,1>>, 1}, {<<2, 2, 2>>, 2}])
iex> {org, t} = get_and_update(t, <<1, 1, 1>>, count)
iex> org
1
iex> get(t, <<1, 1, 1>>)
{<<1, 1, 1>>, 2}
iex> {org, t} = get_and_update(t, <<3, 3>>, count)
iex> org
0
iex> get(t, <<3, 3>>)
{<<3, 3>>, 1}

# modify `count` callback so we get the new value back + updated tree
iex> count = fn nil -> {1, 1}; {_key, val} -> {val+1, val+1} end
iex> t = new([{<<1,1,1>>, 1}, {<<2, 2, 2>>, 2}])
iex> {new, t} = get_and_update(t, <<1, 1, 1>>, count)
iex> new
2
iex> get(t, <<1, 1, 1>>)
{<<1, 1, 1>>, 2}
iex> {new, t} = get_and_update(t, <<3, 3>>, count)
iex> new
1
iex> get(t, <<3, 3>>)
{<<3, 3>>, 1}

# returning :pop deletes the key
iex> once = fn nil -> {0, 1}; {_k, _v} -> :pop end
iex> t = new([{<<1, 1>>, 1}])
iex> {val, t} = get_and_update(t, <<2, 2>>, once)
iex> val
0
iex> get(t, <<2, 2>>)
{<<2, 2>>, 1}
iex> {val, t} = get_and_update(t, <<1, 1>>, once)
iex> val
1
iex> get(t, <<1, 1>>)
nil

keys(tree)

Specs

keys(tree()) :: [key()]

Returns a list of all keys from the radix tree.

Example

iex> t = new([
...>  {<<1, 1, 1, 0::1>>, "1.1.1.0/25"},
...>  {<<1, 1, 1, 1::1>>, "1.1.1.128/25"},
...>  {<<1, 1, 1>>, "1.1.1.0/24"},
...>  {<<3>>, "3.0.0.0/8"},
...>  ])
iex> keys(t)
[<<1, 1, 1, 0::1>>, <<1, 1, 1>>, <<1, 1, 1, 1::1>>, <<3>>]

less(tree, key, opts \\ [])

Specs

less(tree(), key(), Keyword.t()) :: [{key(), value()}]

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

Collects key,value-pairs where the stored key is the same or less specific. Optionally exclude the search key from the results by providing option :exclude as true.

Example

# include search for less specifics
iex> elements = [
...>  {<<1, 1>>, 16},
...>  {<<1, 1, 0>>, 24},
...>  {<<1, 1, 0, 0>>, 32},
...>  {<<1, 1, 1, 1>>, 32}
...> ]
iex> t = new(elements)
iex> less(t, <<1, 1, 1, 1>>)
[{<<1, 1, 1, 1>>, 32}, {<<1, 1>>, 16}]
iex> less(t, <<1, 1, 0>>)
[{<<1, 1, 0>>, 24}, {<<1, 1>>, 16}]
iex> less(t, <<2, 2>>)
[]
#
# exclusive search for less specifics
#
iex> less(t, <<1, 1, 0, 0>>, exclude: true)
[{<<1, 1, 0>>, 24}, {<<1, 1>>, 16}]
#
# search key itself does not have to exist in the tree
iex> less(t, <<1, 1, 0, 25>>)
[{<<1, 1, 0>>, 24}, {<<1, 1>>, 16}]

lookup(tree, key)

Specs

lookup(tree(), key()) :: {key(), value()} | nil

Returns the key,value-pair whose key is the longest prefix of key, or nil.

Returns {key, value} or nil if there was no match.

Example

iex> elms = [{<<1, 1>>, 16}, {<<1, 1, 0>>, 24}, {<<1, 1, 0, 0::1>>, 25}]
iex> t = new(elms)
iex> lookup(t, <<1, 1, 0, 127>>)
{<<1, 1, 0, 0::1>>, 25}
iex> lookup(t, <<1, 1, 0, 128>>)
{<<1, 1, 0>>, 24}
iex> lookup(t, <<1, 1, 1, 1>>)
{<<1, 1>>, 16}
iex> lookup(t, <<2, 2, 2, 2>>)
nil

merge(tree1, tree2)

Specs

merge(tree(), tree()) :: tree()

Merges two radix trees into one.

Adds all key,value-pairs of tree2 to tree1, overwriting any existing entries.

Example

iex> tree1 = new([{<<0>>, 0}, {<<1>>, 1}])
iex> tree2 = new([{<<0>>, nil}, {<<2>>, 2}])
iex> merge(tree1, tree2)
...> |> to_list()
[{<<0>>, nil}, {<<1>>, 1}, {<<2>>, 2}]

merge(tree1, tree2, fun)

Specs

merge(tree(), tree(), (key(), value(), value() -> value())) :: tree()

Merges two radix trees into one, resolving conflicts through fun.

Adds all key,value-pairs of tree2 to tree1, resolving conflicts through given fun. Its arguments are the conflicting key/0 and the value/0 found in tree1 and the value/0 found in tree2.

Example

# keep values of tree1, like merge(tree2, tree1)
iex> tree1 = new([{<<0>>, 0}, {<<1>>, 1}])
iex> tree2 = new([{<<0>>, nil}, {<<2>>, 2}])
iex> merge(tree1, tree2, fn _k, v1, _v2 -> v1 end)
...> |> to_list()
[{<<0>>, 0}, {<<1>>, 1}, {<<2>>, 2}]

minimize(tree, fun)

Specs

minimize(tree(), function()) :: tree()

Minimizes a radix tree by removing more specific keys and pruning adjacent keys, where allowed.

The radix tree is traversed and a new tree is built. Whenever two keys can be combined fun/2 is called with the values stored under the keys to be combined.. If that returns {:ok, value} that value will be stored on the least specific key. That means more specific keys are effectively deleted from the tree and any remaining neighbouring keys are combined to their parent key and the more specific neighbours are deleted.

Examples

Combine neighbouring keys when they store the same value.

iex> f = fn v1, v2 -> if v1 == v2, do: {:ok, v1} end
iex> [{<<1, 0>>, 0}, {<<1, 1>>, 0}]
...> |> new()
...> |> minimize(f)
...> |> to_list()
[{<<1, 0::size(7)>>, 0}]

Remove more specific keys if they have the same value as some less specific key.

iex> f = fn v1, v2 -> if v1 == v2, do: {:ok, v1} end
iex> [{<<1>>, 0}, {<<1, 0>>, 0}, {<<1, 0, 1>>, 0}]
...> |> new()
...> |> minimize(f)
...> |> to_list()
[{<<1>>, 0}]

Summarize statistics keeping the least specific key.

iex> f = fn v1, v2 -> {:ok, v1 + v2} end
iex> [{<<1>>, 12}, {<<1, 0::size(7)>>, 10}, {<<1, 0>>, 10}, {<<1, 1>>, 10}]
...> |> new()
...> |> minimize(f)
...> |> to_list()
[{<<1>>, 42}]

more(tree, key, opts \\ [])

Specs

more(tree(), key(), Keyword.t()) :: [{key(), value()}]

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

Collects key,value-pairs where the stored key is the same or more specific.

Example

iex> elements = [
...>  {<<1, 1>>, 16},
...>  {<<1, 1, 0>>, 24},
...>  {<<1, 1, 0, 0>>, 32},
...>  {<<1, 1, 1, 1>>, 32}
...> ]
iex> t = new(elements)
iex> more(t, <<1, 1, 0>>)
[{<<1, 1, 0, 0>>, 32}, {<<1, 1, 0>>, 24}]
iex> more(t, <<1, 1, 1>>)
[{<<1, 1, 1, 1>>, 32}]
iex> more(t, <<2>>)
[]
#
# exclusive search for more specifics
#
iex> more(t, <<1, 1, 0>>, exclude: true)
[{<<1, 1, 0, 0>>, 32}]
#
# search key itself does not have to exist
#
iex> more(t, <<1>>)
[{<<1, 1, 1, 1>>, 32}, {<<1, 1, 0, 0>>, 32}, {<<1, 1, 0>>, 24}, {<<1, 1>>, 16}]

new()

Specs

new() :: tree()

Returns a new, empty radix tree.

Example

iex> new()
{0, nil, nil}

new(elements)

Specs

new([{key(), value()}]) :: tree()

Return a new radix tree, initialized using given list of {key, value}-pairs.

Example

iex> elements = [{<<1, 1>>, 16}, {<<1, 1, 1, 1>>, 32}, {<<1, 1, 0>>, 24}]
iex> new(elements)
{0,
  {23, [{<<1, 1, 0>>, 24}, {<<1, 1>>, 16}],
       [{<<1, 1, 1, 1>>, 32}]},
  nil
}

pop(tree, key, opts \\ [])

Specs

pop(tree(), key(), keyword()) :: {value(), tree()}

Removes the value associated with key and returns the matched key,value-pair and the new tree.

Options include:

default: value, returned if key could not be matched (defaults to nil)
match: :lpm, specifies a longest prefix match instead of an exact match

If given search key was not matched, the tree is unchanged and the key,value-pair will be the search key and the default value.

Examples

# pop an existing element
iex> new([{<<0>>, 0}, {<<1>>, 1}, {<<2>>, 2}])
...> |> pop(<<1>>)
{
  {<<1>>, 1},
  {0, {6, [{<<0>>, 0}], [{<<2>>, 2}]}, nil}
}

# pop non-existing, using a default
iex> new([{<<0>>, 0}, {<<1>>, 1}, {<<2>>, 2}])
...> |> pop(<<3>>, default: :notfound)
{
  {<<3>>, :notfound},
  {0, {6, {7, [{<<0>>, 0}], [{<<1>>, 1}]}, [{<<2>>, 2}]}, nil}
}

# pop using longest prefix match
iex> new([{<<1, 1, 1>>, "1.1.1.0/24"}, {<<1, 1, 1, 1::1>>, "1.1.1.128/25"}])
...> |> pop(<<1, 1, 1, 255>>, match: :lpm)
{
  {<<1, 1, 1, 1::1>>, "1.1.1.128/25"},
  {0, [{<<1, 1, 1>>, "1.1.1.0/24"}], nil}
}

prune(tree, fun, opts \\ [])

Specs

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

Prunes given tree by invoking fun on adjacent keys.

The callback fun is called with a 5- or 6-element tuple:

{k0, k1, v1, k2, v2}, for two adjacent keys k1 and k2 and absent parent k0
{k0, v0, k1, v1, k2, v2}, for two adjacent keys k1 and k2 with v0 as parent k0's value

If fun returns {:ok, value} the children k1 and k2 are deleted from tree and value is stored under the parent key k0, overwriting any existing value.

Optionally specify recurse: true to keep pruning as long as pruning changes the tree.

Examples

iex> adder = fn {_k0, _k1, v1, _k2, v2} -> {:ok, v1 + v2}
...>            {_k0, v0, _k1, v1, _k2, v2} -> {:ok, v0 + v1 + v2}
...>         end
iex> t = new()
...> |> put(<<1, 1, 1, 0::1>>, 1)
...> |> put(<<1, 1, 1, 1::1>>, 2)
...> |> put(<<1, 1, 0>>, 3)
iex> # prune, once
iex> prune(t, adder)
{0, {23, [{<<1, 1, 0>>, 3}], [{<<1, 1, 1>>, 3}]}, nil}
iex>  # prune, recursively
iex> prune(t, adder, recurse: true)
{0, [{<<1, 1, 0::size(7)>>, 6}], nil}

iex> adder = fn {_k0, _k1, v1, _k2, v2} -> {:ok, v1 + v2}
...>            {_k0, v0, _k1, v1, _k2, v2} -> {:ok, v0 + v1 + v2}
...>         end
iex> new(for x <- 0..255, do: {<<x>>, x})
...> |> prune(adder, recurse: true)
{0, [{<<>>, 32640}], nil}
iex> Enum.sum(0..255)
32640

put(tree, elements)

Specs

put(tree(), [{key(), value()}]) :: tree()

Stores the key,value-pairs from elements in the radix tree.

Any existing key's will have their value's replaced.

Example

iex> elements = [{<<1, 1>>, "1.1.0.0/16"}, {<<1, 1, 1, 1>>, "1.1.1.1"}]
iex> new()
...> |> put(elements)
{0,
  {23, [{<<1, 1>>, "1.1.0.0/16"}],
       [{<<1, 1, 1, 1>>, "1.1.1.1"}]},
  nil
}

put(tree, key, value)

Specs

put(tree(), key(), value()) :: tree()

Stores the key,value-pair under key in the radix tree.

Any existing key will have its value replaced.

Example

iex> t = new()
...>  |> put(<<1, 1>>, "1.1.0.0/16")
...>  |> put(<<1, 1, 1, 1>>, "x.x.x.x")
iex> t
{0,
  {23, [{<<1, 1>>, "1.1.0.0/16"}],
       [{<<1, 1, 1, 1>>, "x.x.x.x"}]},
  nil
}
iex> put(t, <<1, 1, 1, 1>>, "1.1.1.1")
{0,
  {23, [{<<1, 1>>, "1.1.0.0/16"}],
       [{<<1, 1, 1, 1>>, "1.1.1.1"}]},
  nil
}

reduce(tree, acc, fun)

Specs

reduce(tree(), acc(), (key(), value(), acc() -> acc())) :: acc()

Invokes fun for each key,value-pair in the radix tree with the accumulator.

The initial value of the accumulator is acc. The function is invoked for each key,value-pair in the radix tree with the accumulator in a depth-first fashion. The result returned by the function is used as the accumulator for the next iteration. The function returns the last accumulator.

fun's signature is (key/0, value/0, acc/0) -> acc/0.

Example

iex> t = new([
...>  {<<1, 1, 1, 0::1>>, "1.1.1.0/25"},
...>  {<<1, 1, 1, 1::1>>, "1.1.1.128/25"},
...>  {<<1, 1, 1>>, "1.1.1.0/24"},
...>  {<<3>>, "3.0.0.0/8"},
...>  ])
iex> f = fn _key, value, acc -> [value | acc] end
iex> reduce(t, [], f) |> Enum.reverse()
["1.1.1.0/25", "1.1.1.0/24", "1.1.1.128/25", "3.0.0.0/8"]

split(tree, keys, opts \\ [])

Specs

split(
  tree(),
  [key()],
  keyword()
) :: {tree(), tree()}

Extracts the key,value-pairs associated with keys from tree into a new radix tree.

Returns the new tree and the old tree with the key,value-pairs removed. By default an exact match is used, specify match: :lpm to match based on a longest prefix match.

If none of the given keys match, the new tree will be empty and the old tree unchanged.

Examples

iex> tree = new([{<<0>>, 0}, {<<1>>, 1}, {<<2>>, 2}, {<<3>>, 3}])
iex> {t1, t2} = split(tree, [<<0>>, <<2>>])
iex> keys(t1)
[<<0>>, <<2>>]
iex> keys(t2)
[<<1>>, <<3>>]

iex> tree = new([{<<0>>, 0}, {<<1>>, 1}, {<<2>>, 2}, {<<3>>, 3}])
iex> {t1, t2} = split(tree, [<<0, 0>>, <<2, 0>>], match: :lpm)
iex> keys(t1)
[<<0>>, <<2>>]
iex> keys(t2)
[<<1>>, <<3>>]

take(tree, keys, opts \\ [])

Specs

take(
  tree(),
  [key()],
  keyword()
) :: tree()

Returns a new tree with all the key,value-pairs whose key are in keys.

If a key in keys does not exist in tree, it is ignored.

By default keys are matched exactly, use the option match: :lpm to use longest prefix matching.

Examples

iex> new([{<<>>, nil}, {<<0>>, 0}, {<<1>>, 1}, {<<128>>, 128}, {<<255>>, 255}])
...> |> take([<<>>, <<1>>, <<255>>])
...> |> to_list()
[{<<>>, nil}, {<<1>>, 1}, {<<255>>, 255}]

# using longest prefix match
iex> new([{<<>>, nil}, {<<0>>, 0}, {<<1>>, 1}, {<<128>>, 128}, {<<255>>, 255}])
...> |> take([<<2, 2, 2, 2>>, <<1, 1, 1, 1>>, <<255, 255, 0, 0>>], match: :lpm)
...> |> to_list()
[{<<>>, nil}, {<<1>>, 1}, {<<255>>, 255}]

to_list(tree)

Specs

to_list(tree()) :: [{key(), value()}]

Returns all key,value-pairs in tree as a flat list.

Example

iex> new([
...>  {<<1, 1, 1, 0::1>>, "1.1.1.0/25"},
...>  {<<1, 1, 1, 1::1>>, "1.1.1.128/25"},
...>  {<<3>>, "3.0.0.0/8"},
...>  {<<1, 1, 1>>, "1.1.1.0/24"}
...>  ])
...> |> to_list()
[
  {<<1, 1, 1, 0::1>>, "1.1.1.0/25"},
  {<<1, 1, 1>>, "1.1.1.0/24"},
  {<<1, 1, 1, 1::1>>, "1.1.1.128/25"},
  {<<3>>, "3.0.0.0/8"}
]

update(tree, key, fun)

Specs

update(
  tree(),
  key(),
  ({key()} | {key(), value()} -> nil | {:ok, key(), value()})
) :: tree()

Updates a key,value-pair in tree by invoking fun after a longest prefix match lookup.

After a longest prefix match lookup for given search key, the callback fun is called with:

{matched_key, value}, in case there was a match
{original_key}, in case there was no match

If the callback fun returns

{:ok, new_key, new_value}, then new_value will be stored under new_key in the given tree
anything else will return the tree unchanged.

Note that when new_key differs from matched_key, the latter is not deleted from the tree. Because of the longest prefix match, the matched_key is provided to the callback fun.

The main use case is for when dealing with full keys and doing statistics on some less specific level. If an exact match is required, Radix.get_and_update/3 might be a better fit.

Examples

iex> max24bits = fn key when bit_size(key) > 24 ->
...>                  <<bits::bitstring-size(24), _::bitstring>> = key; <<bits::bitstring>>
...>                key -> key
...>             end
iex>
iex> counter = fn {k, v} -> {:ok, k, v + 1}
...>              {k} -> {:ok, max24bits.(k), 1}
...>           end
iex> new()
...> |> update(<<1, 1, 1, 1>>, counter)
...> |> update(<<1, 1, 1, 128>>, counter)
...> |> update(<<1, 1, 1, 255>>, counter)
{0, [{<<1, 1, 1>>, 3}], nil}

# only interested in known prefixes
iex> counter = fn {k, v} -> {:ok, k, v + 1}
...>               _discard -> nil
...>           end
iex> new()
...> |> put(<<1, 1, 1>>, 0)
...> |> update(<<1, 1, 1, 1>>, counter)
...> |> update(<<1, 1, 1, 2>>, counter)
...> |> update(<<2, 2, 2, 2>>, counter)
{0, [{<<1, 1, 1>>, 2}], nil}

update(tree, key, default, fun)

Specs

update(tree(), key(), value(), (value() -> value())) :: tree()

Looks up the longest prefix match for given search key in tree and updates its value through fun.

If key has a longest prefix match in tree then the associated value is passed to fun and its result is used as the updated value of the matching key. If key cannot be matched the {key, default}-pair is inserted in the tree without calling fun.

Example

iex> t = new()
iex> t = update(t, <<1, 1, 1>>, 1, fn x -> x+1 end)
iex> t
{0, [{<<1, 1, 1>>, 1}], nil}
iex> t = update(t, <<1, 1, 1, 0>>, 1, fn x -> x+1 end)
iex> t
{0, [{<<1, 1, 1>>, 2}], nil}
iex> t = update(t, <<1, 1, 1, 255>>, 1, fn x -> x+1 end)
iex> t
{0, [{<<1, 1, 1>>, 3}], nil}

values(tree)

Specs

values(tree()) :: [value()]

Returns all values stored in the radix tree.

Example

iex> new([
...>  {<<1, 1, 1, 0::1>>, "1.1.1.0/25"},
...>  {<<1, 1, 1, 1::1>>, "1.1.1.128/25"},
...>  {<<1, 1, 1>>, "1.1.1.0/24"},
...>  {<<3>>, "3.0.0.0/8"},
...>  ])
...> |> values()
["1.1.1.0/25", "1.1.1.0/24", "1.1.1.128/25", "3.0.0.0/8"]

walk(tree, acc, fun, order \\ :inorder)

Specs

walk(tree(), acc(), (acc(), tree() | leaf() -> acc()), atom()) :: acc()

Invokes fun on all (internal and leaf) nodes of the radix tree using either :inorder, :preorder or :postorder traversal.

fun should have the signatures:

(acc/0, tree/0) -> acc/0
(acc/0, leaf/0) -> acc/0

Examples

Get all values in the tree.

iex> t = new([{<<1>>, 1}, {<<2>>, 2}, {<<3>>, 3}, {<<128>>, 128}])
iex> f = fn
...>   (acc, {_bit, _left, _right}) -> acc
...>   (acc, leaf) -> acc ++ Enum.map(leaf, fn {_k, v} -> v end)
...> end
iex> walk(t, [], f)
[1, 2, 3, 128]

Get all the keys in the tree

iex> t = new([{<<1>>, 1}, {<<2>>, 2}, {<<3>>, 3}, {<<128>>, 128}])
iex> f = fn
...>   (acc, {_bit, _left, _right}) -> acc
...>   (acc, leaf) -> acc ++ Enum.map(leaf, fn {k, _v} -> k end)
...> end
iex> walk(t, [], f)
[<<1>>, <<2>>, <<3>>, <<128>>]