Radix (Radix v0.2.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 is based on a longest prefix match.

Examples

iex> t = new()
...>     |> put(<<1, 1, 1>>, "1.1.1/24")
...>     |> put(<<1, 1, 1, 0::6>>, "1.1.1.0/30")
...>     |> put(<<1, 1, 1, 1::1>>, "1.1.1.128/25")
...>     |> put(<<255>>, "255/8")
iex>
iex>
iex> # longest prefix match
iex>
iex> lookup(t, <<1, 1, 1, 255>>)
{<<1, 1, 1, 1::1>>, "1.1.1.128/25"}
iex>
iex>
iex> # more specific matches (includes search key if present)
iex>
iex> more(t, <<1, 1, 1>>)
[{<<1, 1, 1, 0::size(6)>>, "1.1.1.0/30"}, {<<1, 1, 1>>, "1.1.1/24"}, {<<1, 1, 1, 1::size(1)>>, "1.1.1.128/25"}]
iex>
iex>
iex> # less specific matches (includes search key if present)
iex>
iex> less(t, <<1, 1, 1, 3>>)
[{<<1, 1, 1, 0::size(6)>>, "1.1.1.0/30"}, {<<1, 1, 1>>, "1.1.1/24"}]
iex>
iex> # exact match
iex> get(t, <<1, 1, 1, 0::6>>)
{<<1, 1, 1, 0::6>>, "1.1.1.0/30"}
iex>
iex> get(t, <<1, 1, 1, 0>>)
nil
iex>
iex> dot(t) |> (&File.write("assets/readme.dot", &1)).()

The radix tree above 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

count(tree)

Counts the number of entries by traversing given tree.

delete(tree, key)

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

dot(tree, opts \\ [])

Given a tree, 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)

Say whether given tree is empty or not.

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

Fetches the key,value-pair for a specific 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)

Get the key,value-pair whose key equals the given search key.

keys(tree)

Returns all keys from the radix tree.

less(tree, key)

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

lookup(tree, key)

Get the key,value-pair whose key is the longest prefix of key.

merge(tree1, tree2)

Merges two radix trees into one.

merge(tree1, tree2, fun)

Merges two radix trees into one.

more(tree, key)

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

new()

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

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

Extract key,value-pairs from tree into a new radix tree.

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

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

to_list(tree)

Return all key,value-pairs as a flat list.

update(tree, key, default, fun)

Lookup given search key in tree and update the value of matched key with the given function.

values(tree)

Returns all values from 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.

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

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()

Delete 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()]

Given a tree, 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")
["digraph Radix {\n  labelloc=\"t\";\n  label=\"example\";\n  rankdir=\"TB\";\n  ranksep=\"0.5 equally\";\n",
  "N4 [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n    <TR><TD PORT=\"N4\" BGCOLOR=\"green\">leaf</TD></TR>\n    <TR><TD>128.0/16</TD></TR>\n  </TABLE>\n  >, shape=\"plaintext\"];\n",
  "N2 [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n    <TR><TD PORT=\"N2\" BGCOLOR=\"green\">leaf</TD></TR>\n    <TR><TD>1.1.128/17</TD></TR>\n  </TABLE>\n  >, shape=\"plaintext\"];\n",
  "N1 [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n    <TR><TD PORT=\"N1\" BGCOLOR=\"green\">leaf</TD></TR>\n    <TR><TD>0.0/16</TD></TR>\n  </TABLE>\n  >, shape=\"plaintext\"];\n",
  "N3:R -> N2;\n",
  "N3:L -> N1;\n",
  "N3 [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n    <TR><TD PORT=\"N3\" COLSPAN=\"2\" BGCOLOR=\"yellow\">bit 7</TD></TR>\n    <TR><TD PORT=\"L\">0</TD><TD PORT=\"R\">1</TD></TR>\n  </TABLE>\n>, shape=\"plaintext\"];\n",
  "N5:R -> N4;\n",
  "N5:L -> N3;\n",
  "N5 [label=<\n  <TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n    <TR><TD PORT=\"N5\" COLSPAN=\"2\" BGCOLOR=\"orange\">bit 0</TD></TR>\n    <TR><TD PORT=\"L\">0</TD><TD PORT=\"R\">1</TD></TR>\n  </TABLE>\n>, shape=\"plaintext\"];\n",
  "}"]
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()

Say whether given tree is empty or not.

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 specific 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>
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>
iex> fetch!(t, <<2>>)
** (KeyError) key not found <<0b10>>
iex>
iex> fetch!(t, <<1, 1, 1>>, match: :lpm)
{<<1, 1>>, 2}

get(tree, key, default \\ nil)

Specs

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

Get the key,value-pair whose key equals the given search key.

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>>, "oops")
"oops"

keys(tree)

Specs

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

Returns 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>
iex> keys(t)
[<<1, 1, 1, 0::1>>, <<1, 1, 1>>, <<1, 1, 1, 1::1>>, <<3>>]

less(tree, key)

Specs

less(tree(), key()) :: [{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.

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

lookup(tree, key)

Specs

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

Get the key,value-pair whose key is the longest prefix of key.

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.

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

more(tree, key)

Specs

more(tree(), key()) :: [{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>
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>>)
[]

new()

Specs

new() :: tree()

Return 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> t = new([{<<1, 1, 1>>, "1.1.1.0/24"}, {<<1, 1, 1, 1::1>>, "1.1.1.128/25"}])
iex> pop(t, <<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}
}

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.

Examples

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.

Examples

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>
iex> # get values
iex>
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()}

Extract key,value-pairs 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>
iex> keys(t1)
[<<0>>, <<2>>]
iex>
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>
iex> keys(t1)
[<<0>>, <<2>>]
iex>
iex> keys(t2)
[<<1>>, <<3>>]

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

Specs

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

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

# 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()}]

Return all key,value-pairs as a flat list.

Example

iex> tree = 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"}
...>  ])
iex> to_list(tree)
[
  {<<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, default, fun)

Specs

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

Lookup given search key in tree and update the value of matched key with the given function.

If key has a longest prefix match in tree then its 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.

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 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>
iex> # get values
iex>
iex> values(t)
["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

Note that leaf/0 might be nil.

Example

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