Package trix is a stackable tree data structure that has many different uses.
Package treelock implements a read/write locking mechanism for arbitrary tree structures.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package splaytree implements the splay tree data structure, which is a self-balancing binary search tree, that is, it adapts its internal tree structure to how it is being used in order to optimize future operations.
Package treenode provides a set of functions for working with the https://leetcode.com/ binary tree structure TreeNode
Package hamt is just a trivial front door to the hamt32 and hamt64 packages which really contain the HAMT implementations. Those HAMT implementations are identical in every way but the size of the computed hash, called Hashval. Those are either uint32 or uint64 values for hamt32 and hamt64 respectively. This package merely implements New(), New32() and New64() functions and the table option constants FixedTables, SparseTables, HybridTables, and the map TableOptionName (eg. hamt.TableOptionName[hamt.FixedTables] == "FixedTables"). There are several choices to make: Hashval hamt32 versus hamt64, FixedTables versus SparseTables versus HybridTables, and Functional versus Transient. Then there is a hidden choice; you can change the source code constant, NumIndexBits, to a value other than the current setting of 5. The New() function makes all the recommended choices for you. That is it uses the 64 bit hashVal (aka hamt64), functional behavior, and hybrid tables. Just use hamt64. I implemnted both before I really understood HAMT. I was conflating 32 bit hash values with 32 wide branching factor (that was just a feature of the other implmentations I was looking at). While 32bit FNV hash values are still pretty random I have seen plenty of collisions in my tests. I have never seen 64bit FNV hash values collide and in the current state of computing having 64bit CPUs as the norm. I recommend using hamt64. If you are on 32bit CPUs then maybe you could choose hamt32. Tables is the name I use to for the interior (aka non-leaf) nodes of the hamt data structure. Those tables being the indexed arrays from the Hash-indexed Array Mapped Tries (HAMT) name. This is the classic speed versus memory choice with a twist. The facts to consider are: The tree is indexed by essentially random values (the parts of the hash value of the key), so the tree is going to be "balanced" to a statistical likelihood. The inner branching nodes will be very densely populated, and the outer branching nodes will be very sparsely populated. FixedTables are fastest to access and modify, because it is a simple matter of getting and setting preallocated fixed sized arrays. However, they will be wasting most of their allocated space most of the time. SparseTables are slowest because we always have to calculate bit counts of bit arrays for get or set type operations. Further, inserting or removing values is a matter of manipulating slice values. On the other hand, given the way slice memory allocation works, they will usually waste less than half their allocated memory. According to tests, HybridTables setting behaves precisely the way we want it to behave. For a test set of data with 3,149,824 KeyVal pairs, he distribution of tables comes in two groups: tables with 25-32 entries and tables with 1-11 entries. There are no tables outside those two groupings. The 25-32 entry tables are all fixed tables and the 1-11 entry tables are all sparse tables. Of the sparse tables %40.1 have 1 or 2 entries, %85.4 have 4 or less and %99.7 have 8 or less entries. Given sparse tables start at capacity of 2 and capacity grows by doubling, the sparse tables are efficiently packed. The conclusion from this test data is that HybridTables setting is an excellent fit for memory efficiency. Benchmarks show that fixed table hamts are slower than hybrid table hamts for Put operations and comparable for Get & Del operations. I conclude that is due to the massive over use of memory in fixed tables. This conclusion is partly due to the fact that the Put operation differntial between fixed and hybrid table hamts is twice as large for functional versus transient hamt behavior. Clearly HybridTables table option for my HAMT data structure is the best choice. The bottom line is that writing to transient behavior in a multiple threads almost guarantees problems unless you implement a locking solution (and that can be hard to do in a performant manner). On the other hand, given that HamtFunctional behavior returns a new HamtFunctional data structure upon any modification, HamtFunctional data structures are inherently thread safe. On your third hand, the copy-on-write strategy of HamtFunctional is inherently slower than modify-in-place strategy of HamtTransient. How much slower? For large hamt data structures (~3 million key/value pairs) the transient Put operation takes ~1000ns, where the functional Put op takes ~3200ns. Which really isn't that bad because they are within the same order of magnitude and it is already fast. Using the transient behavior begs the question: why not use the Go builtin map? Of course, the reason is obvious if your key must be a slice; Go map keys can not be slices. The ability to implement a reasonably efficient functional behavior for HAMTs is the point of this library. The hamt transient speed is definitely is slower than Go's builtin map: 435 vs 130 ns/Get; 950 vs 235 ns/Put; 900 vs 175 ns/Del; 235 vs 23 ns/KeyVal iterate. The point of this library is to implement the functional map-like behavior, so that is what I assume you will use it for. The transient behavior is useful for faster single threaded bulk operations then transform it back to the functional behavior. Both hamt32 and hamt64 have a constant NumIndexBits which determines all the other constants defining the HAMT structures. For both hamt32 and hamt64, the NumIndexBits constant is set to 5. You can manually change the source code to set NumIndexBits to some uint other than 5. IndexBits is set to 5 because that is how other people do it. NumIndexBits determines the branching factor (IndexLimit) and the depth (DepthLimit) of the HAMT data structure. Given IndexBits=5 IndexLimit=32, and DepthLimit=6 for hamt32 and DepthLimit=12 for hamt64.
Package Ki provides the base element of GoKi Trees: Ki = Tree in Japanese, and "Key" in English -- powerful tree structures supporting scenegraphs, programs, parsing, etc.
Package skipper provides an HTTP routing library with flexible configuration as well as a runtime update of the routing rules. Skipper works as an HTTP reverse proxy that is responsible for mapping incoming requests to multiple HTTP backend services, based on routes that are selected by the request attributes. At the same time, both the requests and the responses can be augmented by a filter chain that is specifically defined for each route. Skipper can load and update the route definitions from multiple data sources without being restarted. It provides a default executable command with a few built-in filters, however, its primary use case is to be extended with custom filters, predicates or data sources. For futher information read 'Extending Skipper'. Skipper took the core design and inspiration from Vulcand: https://github.com/mailgun/vulcand. Skipper is 'go get' compatible. If needed, create a 'go workspace' first: Get the Skipper packages: Create a file with a route: Optionally, verify the syntax of the file: Start Skipper and make an HTTP request: The core of Skipper's request processing is implemented by a reverse proxy in the 'proxy' package. The proxy receives the incoming request, forwards it to the routing engine in order to receive the most specific matching route. When a route matches, the request is forwarded to all filters defined by it. The filters can modify the request or execute any kind of program logic. Once the request has been processed by all the filters, it is forwarded to the backend endpoint of the route. The response from the backend goes once again through all the filters in reverse order. Finally, it is mapped as the response of the original incoming request. Besides the default proxying mechanism, it is possible to define routes without a real network backend endpoint. One of these cases is called a 'shunt' backend, in which case one of the filters needs to handle the request providing its own response (e.g. the 'static' filter). Actually, filters themselves can instruct the request flow to shunt by calling the Serve(*http.Response) method of the filter context. Another case of a route without a network backend is the 'loopback'. A loopback route can be used to match a request, modified by filters, against the lookup tree with different conditions and then execute a different route. One example scenario can be to use a single route as an entry point to execute some calculation to get an A/B testing decision and then matching the updated request metadata for the actual destination route. This way the calculation can be executed for only those requests that don't contain information about a previously calculated decision. For further details, see the 'proxy' and 'filters' package documentation. Finding a request's route happens by matching the request attributes to the conditions in the route's definitions. Such definitions may have the following conditions: - method - path (optionally with wildcards) - path regular expressions - host regular expressions - headers - header regular expressions It is also possible to create custom predicates with any other matching criteria. The relation between the conditions in a route definition is 'and', meaning, that a request must fulfill each condition to match a route. For further details, see the 'routing' package documentation. Filters are applied in order of definition to the request and in reverse order to the response. They are used to modify request and response attributes, such as headers, or execute background tasks, like logging. Some filters may handle the requests without proxying them to service backends. Filters, depending on their implementation, may accept/require parameters, that are set specifically to the route. For further details, see the 'filters' package documentation. Each route has one of the following backends: HTTP endpoint, shunt or loopback. Backend endpoints can be any HTTP service. They are specified by their network address, including the protocol scheme, the domain name or the IP address, and optionally the port number: e.g. "https://www.example.org:4242". (The path and query are sent from the original request, or set by filters.) A shunt route means that Skipper handles the request alone and doesn't make requests to a backend service. In this case, it is the responsibility of one of the filters to generate the response. A loopback route executes the routing mechanism on current state of the request from the start, including the route lookup. This way it serves as a form of an internal redirect. Route definitions consist of the following: - request matching conditions (predicates) - filter chain (optional) - backend (either an HTTP endpoint or a shunt) The eskip package implements the in-memory and text representations of route definitions, including a parser. (Note to contributors: in order to stay compatible with 'go get', the generated part of the parser is stored in the repository. When changing the grammar, 'go generate' needs to be executed explicitly to update the parser.) For further details, see the 'eskip' package documentation Skipper's route definitions of Skipper are loaded from one or more data sources. It can receive incremental updates from those data sources at runtime. It provides three different data clients: - Innkeeper: the Innkeeper service implements a storage for large sets of Skipper routes, with an HTTP+JSON API, OAuth2 authentication and role management. See the 'innkeeper' package and https://github.com/zalando/innkeeper. - etcd: Skipper can load routes and receive updates from etcd clusters (https://github.com/coreos/etcd). See the 'etcd' package. - static file: package eskipfile implements a simple data client, which can load route definitions from a static file in eskip format. Currently, it loads the routes on startup. It doesn't support runtime updates. Skipper can use additional data sources, provided by extensions. Sources must implement the DataClient interface in the routing package. Skipper can be started with the default executable command 'skipper', or as a library built into an application. The easiest way to start Skipper as a library is to execute the 'Run' function of the current, root package. Each option accepted by the 'Run' function is wired in the default executable as well, as a command line flag. E.g. EtcdUrls becomes -etcd-urls as a comma separated list. For command line help, enter: An additional utility, eskip, can be used to verify, print, update and delete routes from/to files or etcd (Innkeeper on the roadmap). See the cmd/eskip command package, and/or enter in the command line: Skipper doesn't use dynamically loaded plugins, however, it can be used as a library, and it can be extended with custom predicates, filters and/or custom data sources. To create a custom predicate, one needs to implement the PredicateSpec interface in the routing package. Instances of the PredicateSpec are used internally by the routing package to create the actual Predicate objects as referenced in eskip routes, with concrete arguments. Example, randompredicate.go: In the above example, a custom predicate is created, that can be referenced in eskip definitions with the name 'Random': To create a custom filter we need to implement the Spec interface of the filters package. 'Spec' is the specification of a filter, and it is used to create concrete filter instances, while the raw route definitions are processed. Example, hellofilter.go: The above example creates a filter specification, and in the routes where they are included, the filter instances will set the 'X-Hello' header for each and every response. The name of the filter is 'hello', and in a route definition it is referenced as: The easiest way to create a custom Skipper variant is to implement the required filters (as in the example above) by importing the Skipper package, and starting it with the 'Run' command. Example, hello.go: A file containing the routes, routes.eskip: Start the custom router: The 'Run' function in the root Skipper package starts its own listener but it doesn't provide the best composability. The proxy package, however, provides a standard http.Handler, so it is possible to use it in a more complex solution as a building block for routing. Skipper provides detailed logging of failures, and access logs in Apache log format. Skipper also collects detailed performance metrics, and exposes them on a separate listener endpoint for pulling snapshots. For details, see the 'logging' and 'metrics' packages documentation. The router's performance depends on the environment and on the used filters. Under ideal circumstances, and without filters, the biggest time factor is the route lookup. Skipper is able to scale to thousands of routes with logarithmic performance degradation. However, this comes at the cost of increased memory consumption, due to storing the whole lookup tree in a single structure. Benchmarks for the tree lookup can be run by: In case more aggressive scale is needed, it is possible to setup Skipper in a cascade model, with multiple Skipper instances for specific route segments.
Package dirtree provides basic traversal, search, and string conversion functionality for a directory tree-like structure.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package suture provides Erlang-like supervisor trees. This implements Erlang-esque supervisor trees, as adapted for Go. This is intended to be an industrial-strength implementation, but it has not yet been deployed in a hostile environment. (It's headed there, though.) Supervisor Tree -> SuTree -> suture -> holds your code together when it's trying to fall apart. Why use Suture? Suture has 100% test coverage, and is golint clean. This doesn't prove it free of bugs, but it shows I care. A blog post describing the design decisions is available at http://www.jerf.org/iri/post/2930 . To idiomatically use Suture, create a Supervisor which is your top level "application" supervisor. This will often occur in your program's "main" function. Create "Service"s, which implement the Service interface. .Add() them to your Supervisor. Supervisors are also services, so you can create a tree structure here, depending on the exact combination of restarts you want to create. As a special case, when adding Supervisors to Supervisors, the "sub" supervisor will have the "super" supervisor's Log function copied. This allows you to set one log function on the "top" supervisor, and have it propagate down to all the sub-supervisors. This also allows libraries or modules to provide Supervisors without having to commit their users to a particular logging method. Finally, as what is probably the last line of your main() function, call .Serve() on your top level supervisor. This will start all the services you've defined. See the Example for an example, using a simple service that serves out incrementing integers.
Package gossip specifies a basic search DSL and provides parsing functions to convert raw text search queries into structured search query trees.
Package encoding provides a few of the encoding structures that are missing from the Go x/text/encoding tree.
Package formtree creates a tree of form values from a url.Values or any other type derived from map[string][]string . (One use of the url.Values type is http.Request.PostForm). The created tree has the kind of structure that json.Unmarshal builds when unmarhsalling to an empty interface. The leaf nodes of the tree have type string or []string and are the values taken from the original map. Keys (e.g. html form field names used as the keys in http.Request.PostForm) are interpreted in the same way that Gorilla Schema interprets them when populating a struct, so the form value that had the the key would be located at (pseudocode) Using formtree, the syntax would be or if there might be multiple values that share that key.
Package flatpack implements a mechanism to convert arbitrary Go data, possibly including unexported fields and shared and/or cyclic substructure, into and back from a purely tree-structured datastructure without unexported fields that can be serialised using encoding.json or the like.
Package sortb provides a data structure to store sorted generic values using a balanced binary search tree.
tree provides balanced tree structure which acts as external index for sort.Interface and could be used for searching like sort.Search Insertion of duplicates is done in stable order. So that, tree could be used as stable sort (aka binary tree sort). Limitation: index is limited to int32, so that maximum size is 2**31-1
Package qlookup is tool for looking up a data like-tree and create a new structure for every match key.
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 kdtree implements a k-d tree data structure.
Package trie implements trie tree (or prefix tree) data structure useful for things like prefix search/autocompletion.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package trie contains an implementation of the trie data structure (also called "prefix tree" or "radix tree").
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package sops manages JSON, YAML and BINARY documents to be encrypted or decrypted. This package should not be used directly. Instead, Sops users should install the command line client via `go get -u go.mozilla.org/sops/v3/cmd/sops`, or use the decryption helper provided at `go.mozilla.org/sops/v3/decrypt`. We do not guarantee API stability for any package other than `go.mozilla.org/sops/v3/decrypt`. A Sops document is a Tree composed of a data branch with arbitrary key/value pairs and a metadata branch with encryption and integrity information. In JSON and YAML formats, the structure of the cleartext tree is preserved, keys are stored in cleartext and only values are encrypted. Keeping the values in cleartext provides better readability when storing Sops documents in version controls, and allows for merging competing changes on documents. This is a major difference between Sops and other encryption tools that store documents as encrypted blobs. In BINARY format, the cleartext data is treated as a single blob and the encrypted document is in JSON format with a single `data` key and a single encrypted value. Sops allows operators to encrypt their documents with multiple master keys. Each of the master key defined in the document is able to decrypt it, allowing users to share documents amongst themselves without sharing keys, or using a PGP key as a backup for KMS. In practice, this is achieved by generating a data key for each document that is used to encrypt all values, and encrypting the data with each master key defined. Being able to decrypt the data key gives access to the document. The integrity of each document is guaranteed by calculating a Message Authentication Code (MAC) that is stored encrypted by the data key. When decrypting a document, the MAC should be recalculated and compared with the MAC stored in the document to verify that no fraudulent changes have been applied. The MAC covers keys and values as well as their ordering.
Package treemux provides an HTTP request multiplexer that routes using a tree structure.
Package tree provides a data structure of a mutable tree with constant leaves and version counters.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package kdtree implements a k-d tree data structure.
Package actTree implements a double-linked tree data structure.
Package hamt is the front-end for a 32bit and 64bit implementations of a functional Hash Array Mapped Trie (HAMT) datastructure. In this case, functional means immutable and persistent. The term "immutable" means that the datastructure is is never changed after construction. Where "persistent" means that when that immutable datastructure is modified, is is based on the previous datastructure. In other words the new datastructure is not a copy with the modification applied. In stead, that new datastructure shares all un-modified parts of the previouse datastructure and only the changed parts are copied and modified; unchanged parts of the datastructure are shared between the old and new version. A HAMT structure is a tree with a fixed & wide branching factor. Trees make and excellent datastructure to be immutable and persistent. Our HAMT starts with a root branch. Branches are called tables, because they are represented as tables with the "branching factor" number of entries. These entries may be one of three types of nodes: further branches (aka tables) or key/val entries (aka leafs) or emtpy (aka nil). A HAMT is a key/val indexing datastructure. Rather than indexing the datastructure on the key directly, which could result in a rather deep tree datastructure. We generate a hash value of the key, and split the hash value into a fixed number of indexes into fixed size arrays. This results in a tree with a maximum depth and a wide branching factor. For example, we can use a key type of a string. Hash that string into a 32 bit hash value. Coerce that 32 bit value into a 30 bit value. Then split that 30 bit hash value into six 5 bit values. Those 5 bit values will index perfectly into tree nodes with 32 wide branching factor. Now we have tree with a string for the key that is AT MOST six levels deep, in other words O(1) lookup and modification operations. Lets call the number of hash bits H (for hash value). The number of parts the hash value can be split into we'll call D (for depth). The width of each table (aka branching factor) is 2^B; I think of B as "bits per level". The relationship of H:D:B is given by H/B = D. I've implemented in hamt32 (H=30, D=6, B=5) and hamt64 is (H=60, D=10, B=6). We could call the branching factor W for "width" of each tree node. However W is superfluous, because it can be derived from B (aka W=2^B). The number in hamt32 is the branching factor W=2^B=32; from H=30,D=6,B=5 . The number in hamt64 is the branching factor W=2^B=64; from H=60,D=10,B=6 . HAMTs are [Tries](https://en.wikipedia.org/wiki/Trie), because when we are trying to find a location to Get, Put, or Delete a key/value pair we mearly have to walk the "hash path" till we find a non-branching node. The HashPath is the H bit hash value, split into a ordered sequence of B bit integer values that is, at most, D entry tries long. Lets start with a concrete example of a hamt32 (aka H=30,D=6,B=5). Given the string "ewyx" the Hash30() HashVal30 is 0x11a01c5e. Converted into six descreet 5 bit values (from lowest bit to highest) you get 30, 2, 7, 0 26, and 8. This library prints them out from HashVal30.String() as "/30/02/07/00/26/08"; The hash path from lowest to highest bit. That string, "/30/02/07/00/26/08", is the "hash path". Looking up where to find this entry we look up the 30th index of the root of the tree, if that entry is another branch we look up the 2nd index of that next branch. We continue (7th, 0th et al) until we find a non-branch entry. The non-branch entry can be a leaf or empty. Just to be pedantic the go-hamt-key API calculates the indexes by depth as follows: Now we know how to find the candidate location or entry for our operation. That operation can be either a straight lookup, called with h.Get(k); or it can be an insertion of a key/value pair, called with h.Put(k,v); or lastly it can be a deletion operation, called with h.Del(k). For either hamt32.Hamt or hamt64.Hamt value we have three primary operations: h.Get(), h.Put(), and h.Del(). Only h.Put() and h.Del() modify the HAMT. When they modify a table, first the table is copied, then the modification is made to the copy. Next the parent table must be copied so that the new table's entry in the copied parent may be modified. This is continued to the root table and the HAMT structure itself is copied. This is the h.persist() call. Hence, h.Put() and h.Del() return the new HAMT structure as well as any other return values specific to h.Put() or h.Del(). Given that Get() makes no modification of the HAMT structure, it only returns a boolean indicating the key was found in the HAMT and the key's value. Put() returns a copy of the HAMT and a boolean indicating whether a new entry was added (true) or a current entry was updated (false). Del() returns a boolean value indicating if the key was found, and if true what the value of the deleted key was, and the new HAMT structure. If the Del() didn't find the key (a false return value) key's value data is nil and the HAMT value is the current HAMT.
Package karytree implements a recursive k-ary tree data structure.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
Package asciitree pretty-prints hierarchical node data structures as ASCII trees.
Author: jim teeuwen <jimteeuwen@gmail.com> Dependencies: go-pkg-xmlx (http://github.com/jteeuwen/go-pkg-xmlx) This package allows us to fetch Rss and Atom feeds from the internet. They are parsed into an object tree which is a hyvrid of both the RSS and Atom standards. Supported feeds are: The package allows us to maintain cache timeout management. This prevents us from querying the servers for feed updates too often and risk ip bams. Appart from setting a cache timeout manually, the package also optionally adheres to the TTL, SkipDays and SkipHours values specied in the feeds themselves. Note that the TTL, SkipDays and SkipHour fields are only part of the RSS spec. For Atom feeds, we use the CacheTimeout in the Feed struct. Because the object structure is a hybrid between both RSS and Atom specs, not all fields will be filled when requesting either an RSS or Atom feed. I have tried to create as many shared fields as possiblem but some of them simply do not occur in either the RSS or Atom spec.
Package toml is a TOML parser and manipulation library. This version supports the specification as described in https://github.com/toml-lang/toml/blob/master/versions/en/toml-v0.5.0.md Go-toml can marshal and unmarshal TOML documents from and to data structures. Go-toml can operate on a TOML document as a tree. Use one of the Load* functions to parse TOML data and obtain a Tree instance, then one of its methods to manipulate the tree. The package github.com/skyzyx/go-toml/query implements a system similar to JSONPath to quickly retrieve elements of a TOML document using a single expression. See the package documentation for more information. Package civil implements types for civil time, a time-zone-independent representation of time that follows the rules of the proleptic Gregorian calendar with exactly 24-hour days, 60-minute hours, and 60-second minutes. Because they lack location information, these types do not represent unique moments or intervals of time. Use time.Time for that purpose.
Package wavelet provides the Wavelet Tree, a succinct data structure.
Package skipper provides an HTTP routing library with flexible configuration as well as a runtime update of the routing rules. Skipper works as an HTTP reverse proxy that is responsible for mapping incoming requests to multiple HTTP backend services, based on routes that are selected by the request attributes. At the same time, both the requests and the responses can be augmented by a filter chain that is specifically defined for each route. Optionally, it can provide circuit breaker mechanism individually for each backend host. Skipper can load and update the route definitions from multiple data sources without being restarted. It provides a default executable command with a few built-in filters, however, its primary use case is to be extended with custom filters, predicates or data sources. For further information read 'Extending Skipper'. Skipper took the core design and inspiration from Vulcand: https://github.com/mailgun/vulcand. Skipper is 'go get' compatible. If needed, create a 'go workspace' first: Get the Skipper packages: Create a file with a route: Optionally, verify the syntax of the file: Start Skipper and make an HTTP request: The core of Skipper's request processing is implemented by a reverse proxy in the 'proxy' package. The proxy receives the incoming request, forwards it to the routing engine in order to receive the most specific matching route. When a route matches, the request is forwarded to all filters defined by it. The filters can modify the request or execute any kind of program logic. Once the request has been processed by all the filters, it is forwarded to the backend endpoint of the route. The response from the backend goes once again through all the filters in reverse order. Finally, it is mapped as the response of the original incoming request. Besides the default proxying mechanism, it is possible to define routes without a real network backend endpoint. One of these cases is called a 'shunt' backend, in which case one of the filters needs to handle the request providing its own response (e.g. the 'static' filter). Actually, filters themselves can instruct the request flow to shunt by calling the Serve(*http.Response) method of the filter context. Another case of a route without a network backend is the 'loopback'. A loopback route can be used to match a request, modified by filters, against the lookup tree with different conditions and then execute a different route. One example scenario can be to use a single route as an entry point to execute some calculation to get an A/B testing decision and then matching the updated request metadata for the actual destination route. This way the calculation can be executed for only those requests that don't contain information about a previously calculated decision. For further details, see the 'proxy' and 'filters' package documentation. Finding a request's route happens by matching the request attributes to the conditions in the route's definitions. Such definitions may have the following conditions: - method - path (optionally with wildcards) - path regular expressions - host regular expressions - headers - header regular expressions It is also possible to create custom predicates with any other matching criteria. The relation between the conditions in a route definition is 'and', meaning, that a request must fulfill each condition to match a route. For further details, see the 'routing' package documentation. Filters are applied in order of definition to the request and in reverse order to the response. They are used to modify request and response attributes, such as headers, or execute background tasks, like logging. Some filters may handle the requests without proxying them to service backends. Filters, depending on their implementation, may accept/require parameters, that are set specifically to the route. For further details, see the 'filters' package documentation. Each route has one of the following backends: HTTP endpoint, shunt, loopback or dynamic. Backend endpoints can be any HTTP service. They are specified by their network address, including the protocol scheme, the domain name or the IP address, and optionally the port number: e.g. "https://www.example.org:4242". (The path and query are sent from the original request, or set by filters.) A shunt route means that Skipper handles the request alone and doesn't make requests to a backend service. In this case, it is the responsibility of one of the filters to generate the response. A loopback route executes the routing mechanism on current state of the request from the start, including the route lookup. This way it serves as a form of an internal redirect. A dynamic route means that the final target will be defined in a filter. One of the filters in the chain must set the target backend url explicitly. Route definitions consist of the following: - request matching conditions (predicates) - filter chain (optional) - backend The eskip package implements the in-memory and text representations of route definitions, including a parser. (Note to contributors: in order to stay compatible with 'go get', the generated part of the parser is stored in the repository. When changing the grammar, 'go generate' needs to be executed explicitly to update the parser.) For further details, see the 'eskip' package documentation Skipper has filter implementations of basic auth and OAuth2. It can be integrated with tokeninfo based OAuth2 providers. For details, see: https://godoc.org/github.com/zalando/skipper/filters/auth. Skipper's route definitions of Skipper are loaded from one or more data sources. It can receive incremental updates from those data sources at runtime. It provides three different data clients: - Kubernetes: Skipper can be used as part of a Kubernetes Ingress Controller implementation together with https://github.com/zalando-incubator/kube-ingress-aws-controller . In this scenario, Skipper uses the Kubernetes API's Ingress extensions as a source for routing. For a complete deployment example, see more details in: https://github.com/zalando-incubator/kubernetes-on-aws/ . - Innkeeper: the Innkeeper service implements a storage for large sets of Skipper routes, with an HTTP+JSON API, OAuth2 authentication and role management. See the 'innkeeper' package and https://github.com/zalando/innkeeper. - etcd: Skipper can load routes and receive updates from etcd clusters (https://github.com/coreos/etcd). See the 'etcd' package. - static file: package eskipfile implements a simple data client, which can load route definitions from a static file in eskip format. Currently, it loads the routes on startup. It doesn't support runtime updates. Skipper can use additional data sources, provided by extensions. Sources must implement the DataClient interface in the routing package. Skipper provides circuit breakers, configured either globally, based on backend hosts or based on individual routes. It supports two types of circuit breaker behavior: open on N consecutive failures, or open on N failures out of M requests. For details, see: https://godoc.org/github.com/zalando/skipper/circuit. Skipper can be started with the default executable command 'skipper', or as a library built into an application. The easiest way to start Skipper as a library is to execute the 'Run' function of the current, root package. Each option accepted by the 'Run' function is wired in the default executable as well, as a command line flag. E.g. EtcdUrls becomes -etcd-urls as a comma separated list. For command line help, enter: An additional utility, eskip, can be used to verify, print, update and delete routes from/to files or etcd (Innkeeper on the roadmap). See the cmd/eskip command package, and/or enter in the command line: Skipper doesn't use dynamically loaded plugins, however, it can be used as a library, and it can be extended with custom predicates, filters and/or custom data sources. To create a custom predicate, one needs to implement the PredicateSpec interface in the routing package. Instances of the PredicateSpec are used internally by the routing package to create the actual Predicate objects as referenced in eskip routes, with concrete arguments. Example, randompredicate.go: In the above example, a custom predicate is created, that can be referenced in eskip definitions with the name 'Random': To create a custom filter we need to implement the Spec interface of the filters package. 'Spec' is the specification of a filter, and it is used to create concrete filter instances, while the raw route definitions are processed. Example, hellofilter.go: The above example creates a filter specification, and in the routes where they are included, the filter instances will set the 'X-Hello' header for each and every response. The name of the filter is 'hello', and in a route definition it is referenced as: The easiest way to create a custom Skipper variant is to implement the required filters (as in the example above) by importing the Skipper package, and starting it with the 'Run' command. Example, hello.go: A file containing the routes, routes.eskip: Start the custom router: The 'Run' function in the root Skipper package starts its own listener but it doesn't provide the best composability. The proxy package, however, provides a standard http.Handler, so it is possible to use it in a more complex solution as a building block for routing. Skipper provides detailed logging of failures, and access logs in Apache log format. Skipper also collects detailed performance metrics, and exposes them on a separate listener endpoint for pulling snapshots. For details, see the 'logging' and 'metrics' packages documentation. The router's performance depends on the environment and on the used filters. Under ideal circumstances, and without filters, the biggest time factor is the route lookup. Skipper is able to scale to thousands of routes with logarithmic performance degradation. However, this comes at the cost of increased memory consumption, due to storing the whole lookup tree in a single structure. Benchmarks for the tree lookup can be run by: In case more aggressive scale is needed, it is possible to setup Skipper in a cascade model, with multiple Skipper instances for specific route segments.
Package antlr implements the Go version of the ANTLR 4 runtime. ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It's widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build parse trees and also generates a listener interface (or visitor) that makes it easy to respond to the recognition of phrases of interest. ANTLR supports the generation of code in a number of target languages, and the generated code is supported by a runtime library, written specifically to support the generated code in the target language. This library is the runtime for the Go target. To generate code for the go target, it is generally recommended to place the source grammar files in a package of their own, and use the `.sh` script method of generating code, using the go generate directive. In that same directory it is usual, though not required, to place the antlr tool that should be used to generate the code. That does mean that the antlr tool JAR file will be checked in to your source code control though, so you are free to use any other way of specifying the version of the ANTLR tool to use, such as aliasing in `.zshrc` or equivalent, or a profile in your IDE, or configuration in your CI system. Here is a general template for an ANTLR based recognizer in Go: Make sure that the package statement in your grammar file(s) reflects the go package they exist in. The generate.go file then looks like this: And the generate.sh file will look similar to this: depending on whether you want visitors or listeners or any other ANTLR options. From the command line at the root of your package “myproject” you can then simply issue the command: Copyright (c) 2012-2022 The ANTLR Project. All rights reserved. Use of this file is governed by the BSD 3-clause license, which can be found in the LICENSE.txt file in the project root.
fxml - FreeStyle XML Parser This package provides a simple parser which reads a XML document and output a tree structure, which does not need a pre-defined “struct”, hence the name “FreeStyle”.
This package is the root package of the govmomi library. The library is structured as follows: The minimal usable functionality is available through the vim25 package. It contains subpackages that contain generated types, managed objects, and all available methods. The vim25 package is entirely independent of the other packages in the govmomi tree -- it has no dependencies on its peers. The vim25 package itself contains a client structure that is passed around throughout the entire library. It abstracts a session and its immutable state. See the vim25 package for more information. The session package contains an abstraction for the session manager that allows a user to login and logout. It also provides access to the current session (i.e. to determine if the user is in fact logged in) The object package contains wrappers for a selection of managed objects. The constructors of these objects all take a *vim25.Client, which they pass along to derived objects, if applicable. The govc package contains the govc CLI. The code in this tree is not intended to be used as a library. Any functionality that govc contains that _could_ be used as a library function but isn't, _should_ live in a root level package. Other packages, such as "event", "guest", or "license", provide wrappers for the respective subsystems. They are typically not needed in normal workflows so are kept outside the object package.
File Structures 2 This is a follow up to my crufty http://github.com/timtadh/file-structures work. That system has some endemic problems: 1. It uses the read/write interface to files. This means that it needs to do block management and cache management. In theory this can be very fast but it is also very challenging in Go. 2. Because it uses read/write it has to do buffer management. Largely, the system punts on this problem and allows go to handle the buffer management through the normal memory management system. This doesn't work especially well for the use case of file-structures. File Structures 2 is an experiment to bring Memory Mapped IO to the world of Go. The hypotheses are: 1. The operating system is good at page management generally. While, we know more about how to manage the structure of B+Trees, VarChar stores, and Linear Hash tables than the OS there is no indication that from Go you can acheive better performance. Therefore, I hypothesize that leaving it to the OS will lead to a smaller working set and a faster data structure in general. 2. You can make Memory Mapping performant in Go. There are many challenges here. The biggest of which is that there are no dynamically size array TYPES in go. The size of the array is part of the type, you have to use slices. This creates complications when hooking up structures which contain slices to mmap allocated blocks of memory. I hypothesize that this repository can acheive good (enough) performance here. The major components of this project: 1. fmap - a memory mapped file inteface. Part C part Go. Uses cgo. 2. bptree - a B+ Tree with duplicate key support (fixed size keys, variable length values) written on top of fmap. 3. slice - used by fmap and bptree to completely violate memory and type safety of Go. 4. errors - just a simple error package which maintains a stack trace with every error.
Package goavl provides a generic implementation of the AVL Tree data structure.
Package rbtree implements the self balancing Red-Black Tree data structure with a concise key-value interface.
Package kdtree implements a k-d tree data structure.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.
This package is the root package of the govmomi library. The library is structured as follows: The minimal usable functionality is available through the vim25 package. It contains subpackages that contain generated types, managed objects, and all available methods. The vim25 package is entirely independent of the other packages in the govmomi tree -- it has no dependencies on its peers. The vim25 package itself contains a client structure that is passed around throughout the entire library. It abstracts a session and its immutable state. See the vim25 package for more information. The session package contains an abstraction for the session manager that allows a user to login and logout. It also provides access to the current session (i.e. to determine if the user is in fact logged in) The object package contains wrappers for a selection of managed objects. The constructors of these objects all take a *vim25.Client, which they pass along to derived objects, if applicable. The govc package contains the govc CLI. The code in this tree is not intended to be used as a library. Any functionality that govc contains that _could_ be used as a library function but isn't, _should_ live in a root level package. Other packages, such as "event", "guest", or "license", provide wrappers for the respective subsystems. They are typically not needed in normal workflows so are kept outside the object package.
Package gographviz provides parsing for the DOT grammar into an abstract syntax tree representing a graph, analysis of the abstract syntax tree into a more usable structure, and writing back of this structure into the DOT format.