fuchsia / third_party / github.com / docker / docker / refs/heads/upstream/19.03 / . / vendor / github.com / hashicorp / go-immutable-radix

tree: 93f71a339714aa4747b3f6ba6b93c83b6aae028a [path history] [tgz]

vendor/github.com/hashicorp/go-immutable-radix/README.md

Provides the `iradix`

package that implements an immutable radix tree. The package only provides a single `Tree`

implementation, optimized for sparse nodes.

As a radix tree, it provides the following:

- O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
- Minimum / Maximum value lookups
- Ordered iteration

A tree supports using a transaction to batch multiple updates (insert, delete) in a more efficient manner than performing each operation one at a time.

For a mutable variant, see go-radix.

The full documentation is available on Godoc.

Below is a simple example of usage

// Create a tree r := iradix.New() r, _, _ = r.Insert([]byte("foo"), 1) r, _, _ = r.Insert([]byte("bar"), 2) r, _, _ = r.Insert([]byte("foobar"), 2) // Find the longest prefix match m, _, _ := r.Root().LongestPrefix([]byte("foozip")) if string(m) != "foo" { panic("should be foo") }