Trie

Package trie contains radix tree implementation in golang (without any dependencies). Copyright 2021, Mikhail Vitsen (@porfirion) https://github.com/porfirion/trie Trie maps `[]byte` prefixes to `interface{}` values. It can be used for efficient search of substrings or bulk prefix checking. Trie is created by or by convenience constructors: or Two common operations are: but also handy method

Package cidranger provides utility to store CIDR blocks and perform ip inclusion tests against it. To create a new instance of the path-compressed trie: To insert or remove an entry (any object that satisfies the RangerEntry interface): If you desire for any value to be attached to the entry, simply create custom struct that satisfies the RangerEntry interface: To test whether an IP is contained in the constructed networks ranger: To get a list of CIDR blocks in constructed ranger that contains IP: To get a list of all IPv4/IPv6 rangers respectively:

Package router is a trie based high performance HTTP request router. A trivial example is: The router matches incoming requests by the request method and the path. If a handler is registered for this path and method, the router delegates the request to that function. For the methods GET, POST, PUT, PATCH, DELETE and OPTIONS shortcut functions exist to register handles, for all other methods router.Handle can be used. The registered path, against which the router matches incoming requests, can contain two types of parameters: Named parameters are dynamic path segments. They match anything until the next '/' or the path end: Catch-all parameters match anything until the path end, including the directory index (the '/' before the catch-all). Since they match anything until the end, catch-all parameters must always be the final path element. The value of parameters is saved in ctx.UserValue(<key>), consisting each of a key and a value. The slice is passed to the Handle func as a third parameter. To retrieve the value of a parameter,gets by the name of the parameter

Package clevergo is a trie based high performance HTTP request router.

Package vestigo implements a performant, stand-alone, HTTP compliant URL Router for go web applications. Vestigo utilizes a simple radix trie for url route indexing and search, and puts any URL parameters found in a request in the request's Form, much like PAT. Vestigo boasts standards compliance regarding the proper behavior when methods are not allowed on a given resource as well as when a resource isn't found. vestigo also includes built in CORS support on a global and per resource capability.

Package trie implements a minimal and powerful trie based url path router (or mux) for Go.

Trie is a prefix index package for golang. Branch - A Branch might have a LeafValue or not and might have other Branches splitting off. It has a flag `End` that marks the end of a term that has been inserted. Entry - an entry refers to a _complete_ term that is inserted, removed from, or matched in the index. It requires `End` on the Branch to be set to `true`, which makes it different from a Prefix - which does not require the Branch to have End set to `true` to match.

Trie is a prefix index package for golang. Branch - A Branch might have a LeafValue or not and might have other Branches splitting off. It has a flag `End` that marks the end of a term that has been inserted. Entry - an entry refers to a _complete_ term that is inserted, removed from, or matched in the index. It requires `End` on the Branch to be set to `true`, which makes it different from a Prefix - which does not require the Branch to have End set to `true` to match.

Package cedar-go implements double-array trie. It is a golang port of cedar (http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar) which is written in C++ by Naoki Yoshinaga. Currently cedar-go implements the `reduced` verion of cedar. This package is not thread safe if there is one goroutine doing insertions or deletions. key must be `[]byte` without zero items, while value must be integer in the range [0, 2<<63-2] or [0, 2<<31-2] depends on the platform.

Package hamt provides a reference implementation of the IPLD HAMT used in the Filecoin blockchain. It includes some optional flexibility such that it may be used for other purposes outside of Filecoin. HAMT is a "hash array mapped trie" https://en.wikipedia.org/wiki/Hash_array_mapped_trie. This implementation extends the standard form by including buckets for the key/value pairs at storage leaves and CHAMP mutation semantics https://michael.steindorfer.name/publications/oopsla15.pdf. The CHAMP invariant and mutation rules provide us with the ability to maintain canonical forms given any set of keys and their values, regardless of insertion order and intermediate data insertion and deletion. Therefore, for any given set of keys and their values, a HAMT using the same parameters and CHAMP semantics, the root node should always produce the same content identifier (CID). The HAMT algorithm hashes incoming keys and uses incrementing subsections of that hash digest at each level of its tree structure to determine the placement of either the entry or a link to a child node of the tree. A `bitWidth` determines the number of bits of the hash to use for index calculation at each level of the tree such that the root node takes the first `bitWidth` bits of the hash to calculate an index and as we move lower in the tree, we move along the hash by `depth x bitWidth` bits. In this way, a sufficiently randomizing hash function will generate a hash that provides a new index at each level of the data structure. An index comprising `bitWidth` bits will generate index values of `[ 0, 2^bitWidth )`. So a `bitWidth` of 8 will generate indexes of 0 to 255 inclusive. Each node in the tree can therefore hold up to `2^bitWidth` elements of data, which we store in an array. In the this HAMT and the IPLD HashMap we store entries in buckets. A `Set(key, value)` mutation where the index generated at the root node for the hash of key denotes an array index that does not yet contain an entry, we create a new bucket and insert the key / value pair entry. In this way, a single node can theoretically hold up to `2^bitWidth x bucketSize` entries, where `bucketSize` is the maximum number of elements a bucket is allowed to contain ("collisions"). In practice, indexes do not distribute with perfect randomness so this maximum is theoretical. Entries stored in the node's buckets are stored in key-sorted order. This HAMT implementation: • Fixes the `bucketSize` to 3. • Defaults the `bitWidth` to 8, however within Filecoin it uses 5 • Defaults the hash algorithm to the 64-bit variant of Murmur3-x64 The algorithm used here is identical to that of the IPLD HashMap algorithm specified at https://github.com/ipld/specs/blob/master/data-structures/hashmap.md. The specific parameters used by Filecoin and the DAG-CBOR block layout differ from the specification and are defined at https://github.com/ipld/specs/blob/master/data-structures/hashmap.md#Appendix-Filecoin-hamt-variant.

Package hamt provides a reference implementation of the IPLD HAMT used in the Filecoin blockchain. It includes some optional flexibility such that it may be used for other purposes outside of Filecoin. HAMT is a "hash array mapped trie" https://en.wikipedia.org/wiki/Hash_array_mapped_trie. This implementation extends the standard form by including buckets for the key/value pairs at storage leaves and CHAMP mutation semantics https://michael.steindorfer.name/publications/oopsla15.pdf. The CHAMP invariant and mutation rules provide us with the ability to maintain canonical forms given any set of keys and their values, regardless of insertion order and intermediate data insertion and deletion. Therefore, for any given set of keys and their values, a HAMT using the same parameters and CHAMP semantics, the root node should always produce the same content identifier (CID). The HAMT algorithm hashes incoming keys and uses incrementing subsections of that hash digest at each level of its tree structure to determine the placement of either the entry or a link to a child node of the tree. A `bitWidth` determines the number of bits of the hash to use for index calculation at each level of the tree such that the root node takes the first `bitWidth` bits of the hash to calculate an index and as we move lower in the tree, we move along the hash by `depth x bitWidth` bits. In this way, a sufficiently randomizing hash function will generate a hash that provides a new index at each level of the data structure. An index comprising `bitWidth` bits will generate index values of `[ 0, 2^bitWidth )`. So a `bitWidth` of 8 will generate indexes of 0 to 255 inclusive. Each node in the tree can therefore hold up to `2^bitWidth` elements of data, which we store in an array. In the this HAMT and the IPLD HashMap we store entries in buckets. A `Set(key, value)` mutation where the index generated at the root node for the hash of key denotes an array index that does not yet contain an entry, we create a new bucket and insert the key / value pair entry. In this way, a single node can theoretically hold up to `2^bitWidth x bucketSize` entries, where `bucketSize` is the maximum number of elements a bucket is allowed to contain ("collisions"). In practice, indexes do not distribute with perfect randomness so this maximum is theoretical. Entries stored in the node's buckets are stored in key-sorted order. This HAMT implementation: • Fixes the `bucketSize` to 3. • Defaults the `bitWidth` to 8, however within Filecoin it uses 5 • Defaults the hash algorithm to the 64-bit variant of Murmur3-x64 The algorithm used here is identical to that of the IPLD HashMap algorithm specified at https://github.com/ipld/specs/blob/master/data-structures/hashmap.md. The specific parameters used by Filecoin and the DAG-CBOR block layout differ from the specification and are defined at https://github.com/ipld/specs/blob/master/data-structures/hashmap.md#Appendix-Filecoin-hamt-variant.

Implementation of an R-Way Trie data structure. A Trie has a root Node which is the base of the tree. Each subsequent Node has a letter and children, which are nodes that have letter values associated with them.

Implementation of an R-Way Trie data structure. A Trie has a root Node which is the base of the tree. Each subsequent Node has a letter and children, which are nodes that have letter values associated with them.

Package cedar implements double-array trie. It is a golang port of cedar (http://www.tkl.iis.u-tokyo.ac.jp/~ynaga/cedar) which is written in C++ by Naoki Yoshinaga. Currently cedar-go implements the `reduced` verion of cedar. This package is not thread safe if there is one goroutine doing insertions or deletions. key must be `[]byte` without zero items, while value must be integer in the range [0, 2<<63-2] or [0, 2<<31-2] depends on the platform.