Hash Table

Package tview implements rich widgets for terminal based user interfaces. The widgets provided with this package are useful for data exploration and data entry. The package implements the following widgets: The package also provides Application which is used to poll the event queue and draw widgets on screen. The following is a very basic example showing a box with the title "Hello, world!": First, we create a box primitive with a border and a title. Then we create an application, set the box as its root primitive, and run the event loop. The application exits when the application's Application.Stop function is called or when Ctrl-C is pressed. You will find more demos in the "demos" subdirectory. It also contains a presentation (written using tview) which gives an overview of the different widgets and how they can be used. Throughout this package, styles are specified using the tcell.Style type. Styles specify colors with the tcell.Color type. Functions such as tcell.GetColor, tcell.NewHexColor, and tcell.NewRGBColor can be used to create colors from W3C color names or RGB values. The tcell.Style type also allows you to specify text attributes such as "bold" or "underline" or a URL which some terminals use to display hyperlinks. Almost all strings which are displayed may contain style tags. A style tag's content is always wrapped in square brackets. In its simplest form, a style tag specifies the foreground color of the text. Colors in these tags are W3C color names or six hexadecimal digits following a hash tag. Examples: A style tag changes the style of the characters following that style tag. There is no style stack and no nesting of style tags. Style tags are used in almost everything from box titles, list text, form item labels, to table cells. In a TextView, this functionality has to be switched on explicitly. See the TextView documentation for more information. A style tag's full format looks like this: Each of the four fields can be left blank and trailing fields can be omitted. (Empty square brackets "[]", however, are not considered style tags.) Fields that are not specified will be left unchanged. A field with just a dash ("-") means "reset to default". You can specify the following flags to turn on certain attributes (some flags may not be supported by your terminal): Use uppercase letters to turn off the corresponding attribute, for example, "B" to turn off bold. Uppercase letters have no effect if the attribute was not previously set. Setting a URL allows you to turn a piece of text into a hyperlink in some terminals. Specify a dash ("-") to specify the end of the hyperlink. Hyperlinks must only contain single-byte characters (e.g. ASCII) and they may not contain bracket characters ("[" or "]"). Examples: In the rare event that you want to display a string such as "[red]" or "[#00ff1a]" without applying its effect, you need to put an opening square bracket before the closing square bracket. Note that the text inside the brackets will be matched less strictly than region or colors tags. I.e. any character that may be used in color or region tags will be recognized. Examples: You can use the Escape() function to insert brackets automatically where needed. When primitives are instantiated, they are initialized with colors taken from the global Styles variable. You may change this variable to adapt the look and feel of the primitives to your preferred style. Note that most terminals will not report information about their color theme. This package therefore does not support using the terminal's color theme. The default style is a dark theme and you must change the Styles variable to switch to a light (or other) theme. This package supports all unicode characters supported by your terminal. If your terminal supports mouse events, you can enable mouse support for your application by calling Application.EnableMouse. Note that this may interfere with your terminal's default mouse behavior. Mouse support is disabled by default. Many functions in this package are not thread-safe. For many applications, this is not an issue: If your code makes changes in response to key events, the corresponding callback function will execute in the main goroutine and thus will not cause any race conditions. (Exceptions to this are documented.) If you access your primitives from other goroutines, however, you will need to synchronize execution. The easiest way to do this is to call Application.QueueUpdate or Application.QueueUpdateDraw (see the function documentation for details): One exception to this is the io.Writer interface implemented by TextView. You can safely write to a TextView from any goroutine. See the TextView documentation for details. You can also call Application.Draw from any goroutine without having to wrap it in Application.QueueUpdate. And, as mentioned above, key event callbacks are executed in the main goroutine and thus should not use Application.QueueUpdate as that may lead to deadlocks. It is also not necessary to call Application.Draw from such callbacks as it will be called automatically. All widgets listed above contain the Box type. All of Box's functions are therefore available for all widgets, too. Please note that if you are using the functions of Box on a subclass, they will return a *Box, not the subclass. This is a Golang limitation. So while tview supports method chaining in many places, these chains must be broken when using Box's functions. Example: You will need to call Box.SetBorder separately: All widgets also implement the Primitive interface. The tview package's rendering is based on version 2 of https://github.com/gdamore/tcell. It uses types and constants from that package (e.g. colors, styles, and keyboard values).

Package consistent provides a consistent hashing function. Consistent hashing is often used to distribute requests to a changing set of servers. For example, say you have some cache servers cacheA, cacheB, and cacheC. You want to decide which cache server to use to look up information on a user. You could use a typical hash table and hash the user id to one of cacheA, cacheB, or cacheC. But with a typical hash table, if you add or remove a server, almost all keys will get remapped to different results, which basically could bring your service to a grinding halt while the caches get rebuilt. With a consistent hash, adding or removing a server drastically reduces the number of keys that get remapped. Read more about consistent hashing on wikipedia: http://en.wikipedia.org/wiki/Consistent_hashing

Package consistent provides a consistent hashing function. Consistent hashing is often used to distribute requests to a changing set of servers. For example, say you have some cache servers cacheA, cacheB, and cacheC. You want to decide which cache server to use to look up information on a user. You could use a typical hash table and hash the user id to one of cacheA, cacheB, or cacheC. But with a typical hash table, if you add or remove a server, almost all keys will get remapped to different results, which basically could bring your service to a grinding halt while the caches get rebuilt. With a consistent hash, adding or removing a server drastically reduces the number of keys that get remapped. Read more about consistent hashing on wikipedia: http://en.wikipedia.org/wiki/Consistent_hashing

Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with S/Kademlia modifications.

Package cuckoo provides a Cuckoo Filter, a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space. Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%). For details about the algorithm and citations please use this article: "Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) Note: This implementation uses a a static bucket size of 4 fingerprints and a fingerprint size of 1 byte based on my understanding of an optimal bucket/fingerprint/size ratio from the aforementioned paper.

Package dht implements a Distributed Hash Table (DHT) part of the BitTorrent protocol, as specified by BEP 5: http://www.bittorrent.org/beps/bep_0005.html BitTorrent uses a "distributed hash table" (DHT) for storing peer contact information for "trackerless" torrents. In effect, each peer becomes a tracker. The protocol is based on Kademila DHT protocol and is implemented over UDP. Please note the terminology used to avoid confusion. A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. The DHT is composed of nodes and stores the location of peers. BitTorrent clients include a DHT node, which is used to contact other nodes in the DHT to get the location of peers to download from using the BitTorrent protocol. Standard use involves creating a Server, and calling Announce on it with the details of your local torrent client and infohash of interest.

Package pointer implements Andersen's analysis, an inclusion-based pointer analysis algorithm first described in (Andersen, 1994). A pointer analysis relates every pointer expression in a whole program to the set of memory locations to which it might point. This information can be used to construct a call graph of the program that precisely represents the destinations of dynamic function and method calls. It can also be used to determine, for example, which pairs of channel operations operate on the same channel. The package allows the client to request a set of expressions of interest for which the points-to information will be returned once the analysis is complete. In addition, the client may request that a callgraph is constructed. The example program in example_test.go demonstrates both of these features. Clients should not request more information than they need since it may increase the cost of the analysis significantly. Our algorithm is INCLUSION-BASED: the points-to sets for x and y will be related by pts(y) ⊇ pts(x) if the program contains the statement y = x. It is FLOW-INSENSITIVE: it ignores all control flow constructs and the order of statements in a program. It is therefore a "MAY ALIAS" analysis: its facts are of the form "P may/may not point to L", not "P must point to L". It is FIELD-SENSITIVE: it builds separate points-to sets for distinct fields, such as x and y in struct { x, y *int }. It is mostly CONTEXT-INSENSITIVE: most functions are analyzed once, so values can flow in at one call to the function and return out at another. Only some smaller functions are analyzed with consideration of their calling context. It has a CONTEXT-SENSITIVE HEAP: objects are named by both allocation site and context, so the objects returned by two distinct calls to f: are distinguished up to the limits of the calling context. It is a WHOLE PROGRAM analysis: it requires SSA-form IR for the complete Go program and summaries for native code. See the (Hind, PASTE'01) survey paper for an explanation of these terms. The analysis is fully sound when invoked on pure Go programs that do not use reflection or unsafe.Pointer conversions. In other words, if there is any possible execution of the program in which pointer P may point to object O, the analysis will report that fact. By default, the "reflect" library is ignored by the analysis, as if all its functions were no-ops, but if the client enables the Reflection flag, the analysis will make a reasonable attempt to model the effects of calls into this library. However, this comes at a significant performance cost, and not all features of that library are yet implemented. In addition, some simplifying approximations must be made to ensure that the analysis terminates; for example, reflection can be used to construct an infinite set of types and values of those types, but the analysis arbitrarily bounds the depth of such types. Most but not all reflection operations are supported. In particular, addressable reflect.Values are not yet implemented, so operations such as (reflect.Value).Set have no analytic effect. The pointer analysis makes no attempt to understand aliasing between the operand x and result y of an unsafe.Pointer conversion: It is as if the conversion allocated an entirely new object: The analysis cannot model the aliasing effects of functions written in languages other than Go, such as runtime intrinsics in C or assembly, or code accessed via cgo. The result is as if such functions are no-ops. However, various important intrinsics are understood by the analysis, along with built-ins such as append. The analysis currently provides no way for users to specify the aliasing effects of native code. ------------------------------------------------------------------------ The remaining documentation is intended for package maintainers and pointer analysis specialists. Maintainers should have a solid understanding of the referenced papers (especially those by H&L and PKH) before making making significant changes. The implementation is similar to that described in (Pearce et al, PASTE'04). Unlike many algorithms which interleave constraint generation and solving, constructing the callgraph as they go, this implementation for the most part observes a phase ordering (generation before solving), with only simple (copy) constraints being generated during solving. (The exception is reflection, which creates various constraints during solving as new types flow to reflect.Value operations.) This improves the traction of presolver optimisations, but imposes certain restrictions, e.g. potential context sensitivity is limited since all variants must be created a priori. A type is said to be "pointer-like" if it is a reference to an object. Pointer-like types include pointers and also interfaces, maps, channels, functions and slices. We occasionally use C's x->f notation to distinguish the case where x is a struct pointer from x.f where is a struct value. Pointer analysis literature (and our comments) often uses the notation dst=*src+offset to mean something different than what it means in Go. It means: for each node index p in pts(src), the node index p+offset is in pts(dst). Similarly *dst+offset=src is used for store constraints and dst=src+offset for offset-address constraints. Nodes are the key datastructure of the analysis, and have a dual role: they represent both constraint variables (equivalence classes of pointers) and members of points-to sets (things that can be pointed at, i.e. "labels"). Nodes are naturally numbered. The numbering enables compact representations of sets of nodes such as bitvectors (or BDDs); and the ordering enables a very cheap way to group related nodes together. For example, passing n parameters consists of generating n parallel constraints from caller+i to callee+i for 0<=i<n. The zero nodeid means "not a pointer". For simplicity, we generate flow constraints even for non-pointer types such as int. The pointer equivalence (PE) presolver optimization detects which variables cannot point to anything; this includes not only all variables of non-pointer types (such as int) but also variables of pointer-like types if they are always nil, or are parameters to a function that is never called. Each node represents a scalar part of a value or object. Aggregate types (structs, tuples, arrays) are recursively flattened out into a sequential list of scalar component types, and all the elements of an array are represented by a single node. (The flattening of a basic type is a list containing a single node.) Nodes are connected into a graph with various kinds of labelled edges: simple edges (or copy constraints) represent value flow. Complex edges (load, store, etc) trigger the creation of new simple edges during the solving phase. Conceptually, an "object" is a contiguous sequence of nodes denoting an addressable location: something that a pointer can point to. The first node of an object has a non-nil obj field containing information about the allocation: its size, context, and ssa.Value. Objects include: Many objects have no Go types. For example, the func, map and chan type kinds in Go are all varieties of pointers, but their respective objects are actual functions (executable code), maps (hash tables), and channels (synchronized queues). Given the way we model interfaces, they too are pointers to "tagged" objects with no Go type. And an *ssa.Global denotes the address of a global variable, but the object for a Global is the actual data. So, the types of an ssa.Value that creates an object is "off by one indirection": a pointer to the object. The individual nodes of an object are sometimes referred to as "labels". For uniformity, all objects have a non-zero number of fields, even those of the empty type struct{}. (All arrays are treated as if of length 1, so there are no empty arrays. The empty tuple is never address-taken, so is never an object.) An tagged object has the following layout: The T node's typ field is the dynamic type of the "payload": the value v which follows, flattened out. The T node's obj has the otTagged flag. Tagged objects are needed when generalizing across types: interfaces, reflect.Values, reflect.Types. Each of these three types is modelled as a pointer that exclusively points to tagged objects. Tagged objects may be indirect (obj.flags ⊇ {otIndirect}) meaning that the value v is not of type T but *T; this is used only for reflect.Values that represent lvalues. (These are not implemented yet.) Variables of the following "scalar" types may be represented by a single node: basic types, pointers, channels, maps, slices, 'func' pointers, interfaces. Pointers: Nothing to say here, oddly. Basic types (bool, string, numbers, unsafe.Pointer): Currently all fields in the flattening of a type, including non-pointer basic types such as int, are represented in objects and values. Though non-pointer nodes within values are uninteresting, non-pointer nodes in objects may be useful (if address-taken) because they permit the analysis to deduce, in this example, that p points to s.x. If we ignored such object fields, we could only say that p points somewhere within s. All other basic types are ignored. Expressions of these types have zero nodeid, and fields of these types within aggregate other types are omitted. unsafe.Pointers are not modelled as pointers, so a conversion of an unsafe.Pointer to *T is (unsoundly) treated equivalent to new(T). Channels: An expression of type 'chan T' is a kind of pointer that points exclusively to channel objects, i.e. objects created by MakeChan (or reflection). 'chan T' is treated like *T. *ssa.MakeChan is treated as equivalent to new(T). *ssa.Send and receive (*ssa.UnOp(ARROW)) and are equivalent to store Maps: An expression of type 'map[K]V' is a kind of pointer that points exclusively to map objects, i.e. objects created by MakeMap (or reflection). map K[V] is treated like *M where M = struct{k K; v V}. *ssa.MakeMap is equivalent to new(M). *ssa.MapUpdate is equivalent to *y=x where *y and x have type M. *ssa.Lookup is equivalent to y=x.v where x has type *M. Slices: A slice []T, which dynamically resembles a struct{array *T, len, cap int}, is treated as if it were just a *T pointer; the len and cap fields are ignored. *ssa.MakeSlice is treated like new([1]T): an allocation of a *ssa.Index on a slice is equivalent to a load. *ssa.IndexAddr on a slice returns the address of the sole element of the slice, i.e. the same address. *ssa.Slice is treated as a simple copy. Functions: An expression of type 'func...' is a kind of pointer that points exclusively to function objects. A function object has the following layout: There may be multiple function objects for the same *ssa.Function due to context-sensitive treatment of some functions. The first node is the function's identity node. Associated with every callsite is a special "targets" variable, whose pts() contains the identity node of each function to which the call may dispatch. Identity words are not otherwise used during the analysis, but we construct the call graph from the pts() solution for such nodes. The following block of contiguous nodes represents the flattened-out types of the parameters ("P-block") and results ("R-block") of the function object. The treatment of free variables of closures (*ssa.FreeVar) is like that of global variables; it is not context-sensitive. *ssa.MakeClosure instructions create copy edges to Captures. A Go value of type 'func' (i.e. a pointer to one or more functions) is a pointer whose pts() contains function objects. The valueNode() for an *ssa.Function returns a singleton for that function. Interfaces: An expression of type 'interface{...}' is a kind of pointer that points exclusively to tagged objects. All tagged objects pointed to by an interface are direct (the otIndirect flag is clear) and concrete (the tag type T is not itself an interface type). The associated ssa.Value for an interface's tagged objects may be an *ssa.MakeInterface instruction, or nil if the tagged object was created by an instrinsic (e.g. reflection). Constructing an interface value causes generation of constraints for all of the concrete type's methods; we can't tell a priori which ones may be called. TypeAssert y = x.(T) is implemented by a dynamic constraint triggered by each tagged object O added to pts(x): a typeFilter constraint if T is an interface type, or an untag constraint if T is a concrete type. A typeFilter tests whether O.typ implements T; if so, O is added to pts(y). An untagFilter tests whether O.typ is assignable to T,and if so, a copy edge O.v -> y is added. ChangeInterface is a simple copy because the representation of tagged objects is independent of the interface type (in contrast to the "method tables" approach used by the gc runtime). y := Invoke x.m(...) is implemented by allocating contiguous P/R blocks for the callsite and adding a dynamic rule triggered by each tagged object added to pts(x). The rule adds param/results copy edges to/from each discovered concrete method. (Q. Why do we model an interface as a pointer to a pair of type and value, rather than as a pair of a pointer to type and a pointer to value? A. Control-flow joins would merge interfaces ({T1}, {V1}) and ({T2}, {V2}) to make ({T1,T2}, {V1,V2}), leading to the infeasible and type-unsafe combination (T1,V2). Treating the value and its concrete type as inseparable makes the analysis type-safe.) Type parameters: Type parameters are not directly supported by the analysis. Calls to generic functions will be left as if they had empty bodies. Users of the package are expected to use the ssa.InstantiateGenerics builder mode when building code that uses or depends on code containing generics. reflect.Value: A reflect.Value is modelled very similar to an interface{}, i.e. as a pointer exclusively to tagged objects, but with two generalizations. 1. a reflect.Value that represents an lvalue points to an indirect (obj.flags ⊇ {otIndirect}) tagged object, which has a similar layout to an tagged object except that the value is a pointer to the dynamic type. Indirect tagged objects preserve the correct aliasing so that mutations made by (reflect.Value).Set can be observed. Indirect objects only arise when an lvalue is derived from an rvalue by indirection, e.g. the following code: Whether indirect or not, the concrete type of the tagged object corresponds to the user-visible dynamic type, and the existence of a pointer is an implementation detail. (NB: indirect tagged objects are not yet implemented) 2. The dynamic type tag of a tagged object pointed to by a reflect.Value may be an interface type; it need not be concrete. This arises in code such as this: pts(eface) is a singleton containing an interface{}-tagged object. That tagged object's payload is an interface{} value, i.e. the pts of the payload contains only concrete-tagged objects, although in this example it's the zero interface{} value, so its pts is empty. reflect.Type: Just as in the real "reflect" library, we represent a reflect.Type as an interface whose sole implementation is the concrete type, *reflect.rtype. (This choice is forced on us by go/types: clients cannot fabricate types with arbitrary method sets.) rtype instances are canonical: there is at most one per dynamic type. (rtypes are in fact large structs but since identity is all that matters, we represent them by a single node.) The payload of each *rtype-tagged object is an *rtype pointer that points to exactly one such canonical rtype object. We exploit this by setting the node.typ of the payload to the dynamic type, not '*rtype'. This saves us an indirection in each resolution rule. As an optimisation, *rtype-tagged objects are canonicalized too. Aggregate types: Aggregate types are treated as if all directly contained aggregates are recursively flattened out. Structs: *ssa.Field y = x.f creates a simple edge to y from x's node at f's offset. *ssa.FieldAddr y = &x->f requires a dynamic closure rule to create The nodes of a struct consist of a special 'identity' node (whose type is that of the struct itself), followed by the nodes for all the struct's fields, recursively flattened out. A pointer to the struct is a pointer to its identity node. That node allows us to distinguish a pointer to a struct from a pointer to its first field. Field offsets are logical field offsets (plus one for the identity node), so the sizes of the fields can be ignored by the analysis. (The identity node is non-traditional but enables the distinction described above, which is valuable for code comprehension tools. Typical pointer analyses for C, whose purpose is compiler optimization, must soundly model unsafe.Pointer (void*) conversions, and this requires fidelity to the actual memory layout using physical field offsets.) *ssa.Field y = x.f creates a simple edge to y from x's node at f's offset. *ssa.FieldAddr y = &x->f requires a dynamic closure rule to create Arrays: We model an array by an identity node (whose type is that of the array itself) followed by a node representing all the elements of the array; the analysis does not distinguish elements with different indices. Effectively, an array is treated like struct{elem T}, a load y=x[i] like y=x.elem, and a store x[i]=y like x.elem=y; the index i is ignored. A pointer to an array is pointer to its identity node. (A slice is also a pointer to an array's identity node.) The identity node allows us to distinguish a pointer to an array from a pointer to one of its elements, but it is rather costly because it introduces more offset constraints into the system. Furthermore, sound treatment of unsafe.Pointer would require us to dispense with this node. Arrays may be allocated by Alloc, by make([]T), by calls to append, and via reflection. Tuples (T, ...): Tuples are treated like structs with naturally numbered fields. *ssa.Extract is analogous to *ssa.Field. However, tuples have no identity field since by construction, they cannot be address-taken. There are three kinds of function call: Cases 1 and 2 apply equally to methods and standalone functions. Static calls: A static call consists three steps: A static function call is little more than two struct value copies between the P/R blocks of caller and callee: Context sensitivity: Static calls (alone) may be treated context sensitively, i.e. each callsite may cause a distinct re-analysis of the callee, improving precision. Our current context-sensitivity policy treats all intrinsics and getter/setter methods in this manner since such functions are small and seem like an obvious source of spurious confluences, though this has not yet been evaluated. Dynamic function calls: Dynamic calls work in a similar manner except that the creation of copy edges occurs dynamically, in a similar fashion to a pair of struct copies in which the callee is indirect: (Recall that the function object's P- and R-blocks are contiguous.) Interface method invocation: For invoke-mode calls, we create a params/results block for the callsite and attach a dynamic closure rule to the interface. For each new tagged object that flows to the interface, we look up the concrete method, find its function object, and connect its P/R blocks to the callsite's P/R blocks, adding copy edges to the graph during solving. Recording call targets: The analysis notifies its clients of each callsite it encounters, passing a CallSite interface. Among other things, the CallSite contains a synthetic constraint variable ("targets") whose points-to solution includes the set of all function objects to which the call may dispatch. It is via this mechanism that the callgraph is made available. Clients may also elect to be notified of callgraph edges directly; internally this just iterates all "targets" variables' pts(·)s. We implement Hash-Value Numbering (HVN), a pre-solver constraint optimization described in Hardekopf & Lin, SAS'07. This is documented in more detail in hvn.go. We intend to add its cousins HR and HU in future. The solver is currently a naive Andersen-style implementation; it does not perform online cycle detection, though we plan to add solver optimisations such as Hybrid- and Lazy- Cycle Detection from (Hardekopf & Lin, PLDI'07). It uses difference propagation (Pearce et al, SQC'04) to avoid redundant re-triggering of closure rules for values already seen. Points-to sets are represented using sparse bit vectors (similar to those used in LLVM and gcc), which are more space- and time-efficient than sets based on Go's built-in map type or dense bit vectors. Nodes are permuted prior to solving so that object nodes (which may appear in points-to sets) are lower numbered than non-object (var) nodes. This improves the density of the set over which the PTSs range, and thus the efficiency of the representation. Partly thanks to avoiding map iteration, the execution of the solver is 100% deterministic, a great help during debugging. Andersen, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. dissertation. DIKU, University of Copenhagen. David J. Pearce, Paul H. J. Kelly, and Chris Hankin. 2004. Efficient field-sensitive pointer analysis for C. In Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering (PASTE '04). ACM, New York, NY, USA, 37-42. http://doi.acm.org/10.1145/996821.996835 David J. Pearce, Paul H. J. Kelly, and Chris Hankin. 2004. Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis. Software Quality Control 12, 4 (December 2004), 311-337. http://dx.doi.org/10.1023/B:SQJO.0000039791.93071.a2 David Grove and Craig Chambers. 2001. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst. 23, 6 (November 2001), 685-746. http://doi.acm.org/10.1145/506315.506316 Ben Hardekopf and Calvin Lin. 2007. The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation (PLDI '07). ACM, New York, NY, USA, 290-299. http://doi.acm.org/10.1145/1250734.1250767 Ben Hardekopf and Calvin Lin. 2007. Exploiting pointer and location equivalence to optimize pointer analysis. In Proceedings of the 14th international conference on Static Analysis (SAS'07), Hanne Riis Nielson and Gilberto Filé (Eds.). Springer-Verlag, Berlin, Heidelberg, 265-280. Atanas Rountev and Satish Chandra. 2000. Off-line variable substitution for scaling points-to analysis. In Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation (PLDI '00). ACM, New York, NY, USA, 47-56. DOI=10.1145/349299.349310 http://doi.acm.org/10.1145/349299.349310 This program demonstrates how to use the pointer analysis to obtain a conservative call-graph of a Go program. It also shows how to compute the points-to set of a variable, in this case, (C).f's ch parameter.

Package dht implements a Distributed Hash Table (DHT) part of the BitTorrent protocol, as specified by BEP 5: http://www.bittorrent.org/beps/bep_0005.html BitTorrent uses a "distributed hash table" (DHT) for storing peer contact information for "trackerless" torrents. In effect, each peer becomes a tracker. The protocol is based on Kademila DHT protocol and is implemented over UDP. Please note the terminology used to avoid confusion. A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. The DHT is composed of nodes and stores the location of peers. BitTorrent clients include a DHT node, which is used to contact other nodes in the DHT to get the location of peers to download from using the BitTorrent protocol. Standard use involves creating a Server, and calling Announce on it with the details of your local torrent client and infohash of interest.

Package jump implements the "jump consistent hash" algorithm. Example Reference C++ implementation[1] Jump consistent hash works by computing when its output changes as the number of buckets increases. Let ch(key, num_buckets) be the consistent hash for the key when there are num_buckets buckets. Clearly, for any key, k, ch(k, 1) is 0, since there is only the one bucket. In order for the consistent hash function to balanced, ch(k, 2) will have to stay at 0 for half the keys, k, while it will have to jump to 1 for the other half. In general, ch(k, n+1) has to stay the same as ch(k, n) for n/(n+1) of the keys, and jump to n for the other 1/(n+1) of the keys. Here are examples of the consistent hash values for three keys, k1, k2, and k3, as num_buckets goes up: A linear time algorithm can be defined by using the formula for the probability of ch(key, j) jumping when j increases. It essentially walks across a row of this table. Given a key and number of buckets, the algorithm considers each successive bucket, j, from 1 to num_buckets­1, and uses ch(key, j) to compute ch(key, j+1). At each bucket, j, it decides whether to keep ch(k, j+1) the same as ch(k, j), or to jump its value to j. In order to jump for the right fraction of keys, it uses a pseudo­random number generator with the key as its seed. To jump for 1/(j+1) of keys, it generates a uniform random number between 0.0 and 1.0, and jumps if the value is less than 1/(j+1). At the end of the loop, it has computed ch(k, num_buckets), which is the desired answer. In code: We can convert this to a logarithmic time algorithm by exploiting that ch(key, j+1) is usually unchanged as j increases, only jumping occasionally. The algorithm will only compute the destinations of jumps ­­ the j’s for which ch(key, j+1) ≠ ch(key, j). Also notice that for these j’s, ch(key, j+1) = j. To develop the algorithm, we will treat ch(key, j) as a random variable, so that we can use the notation for random variables to analyze the fractions of keys for which various propositions are true. That will lead us to a closed form expression for a pseudo­random variable whose value gives the destination of the next jump. Suppose that the algorithm is tracking the bucket numbers of the jumps for a particular key, k. And suppose that b was the destination of the last jump, that is, ch(k, b) ≠ ch(k, b+1), and ch(k, b+1) = b. Now, we want to find the next jump, the smallest j such that ch(k, j+1) ≠ ch(k, b+1), or equivalently, the largest j such that ch(k, j) = ch(k, b+1). We will make a pseudo­random variable whose value is that j. To get a probabilistic constraint on j, note that for any bucket number, i, we have j ≥ i if and only if the consistent hash hasn’t changed by i, that is, if and only if ch(k, i) = ch(k, b+1). Hence, the distribution of j must satisfy Fortunately, it is easy to compute that probability. Notice that since P( ch(k, 10) = ch(k, 11) ) is 10/11, and P( ch(k, 11) = ch(k, 12) ) is 11/12, then P( ch(k, 10) = ch(k, 12) ) is 10/11 * 11/12 = 10/12. In general, if n ≥ m, P( ch(k, n) = ch(k, m) ) = m / n. Thus for any i > b, Now, we generate a pseudo­random variable, r, (depending on k and j) that is uniformly distributed between 0 and 1. Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+1) / i. Solving the inequality for i yields P(j ≥ i) iff i ≤ (b+1) / r. Since i is a lower bound on j, j will equal the largest i for which P(j ≥ i), thus the largest i satisfying i ≤ (b+1) / r. Thus, by the definition of the floor function, j = floor((b+1) / r). Using this formula, jump consistent hash finds ch(key, num_buckets) by choosing successive jump destinations until it finds a position at or past num_buckets. It then knows that the previous jump destination is the answer. To turn this into the actual code of figure 1, we need to implement random. We want it to be fast, and yet to also to have well distributed successive values. We use a 64­bit linear congruential generator; the particular multiplier we use produces random numbers that are especially well distributed in higher dimensions (i.e., when successive random values are used to form tuples). We use the key as the seed. (For keys that don’t fit into 64 bits, a 64 bit hash of the key should be used.) The congruential generator updates the seed on each iteration, and the code derives a double from the current seed. Tests show that this generator has good speed and distribution. It is worth noting that unlike the algorithm of Karger et al., jump consistent hash does not require the key to be hashed if it is already an integer. This is because jump consistent hash has an embedded pseudorandom number generator that essentially rehashes the key on every iteration. The hash is not especially good (i.e., linear congruential), but since it is applied repeatedly, additional hashing of the input key is not necessary. [1] http://arxiv.org/pdf/1406.2294v1.pdf

Package tview implements rich widgets for terminal based user interfaces. The widgets provided with this package are useful for data exploration and data entry. The package implements the following widgets: The package also provides Application which is used to poll the event queue and draw widgets on screen. The following is a very basic example showing a box with the title "Hello, world!": First, we create a box primitive with a border and a title. Then we create an application, set the box as its root primitive, and run the event loop. The application exits when the application's Stop() function is called or when Ctrl-C is pressed. If we have a primitive which consumes key presses, we call the application's SetFocus() function to redirect all key presses to that primitive. Most primitives then offer ways to install handlers that allow you to react to any actions performed on them. You will find more demos in the "demos" subdirectory. It also contains a presentation (written using tview) which gives an overview of the different widgets and how they can be used. Throughout this package, colors are specified using the tcell.Color type. Functions such as tcell.GetColor(), tcell.NewHexColor(), and tcell.NewRGBColor() can be used to create colors from W3C color names or RGB values. Almost all strings which are displayed can contain color tags. Color tags are W3C color names or six hexadecimal digits following a hash tag, wrapped in square brackets. Examples: A color tag changes the color of the characters following that color tag. This applies to almost everything from box titles, list text, form item labels, to table cells. In a TextView, this functionality has to be switched on explicitly. See the TextView documentation for more information. Color tags may contain not just the foreground (text) color but also the background color and additional flags. In fact, the full definition of a color tag is as follows: Each of the three fields can be left blank and trailing fields can be omitted. (Empty square brackets "[]", however, are not considered color tags.) Colors that are not specified will be left unchanged. A field with just a dash ("-") means "reset to default". You can specify the following flags (some flags may not be supported by your terminal): Examples: In the rare event that you want to display a string such as "[red]" or "[#00ff1a]" without applying its effect, you need to put an opening square bracket before the closing square bracket. Note that the text inside the brackets will be matched less strictly than region or colors tags. I.e. any character that may be used in color or region tags will be recognized. Examples: You can use the Escape() function to insert brackets automatically where needed. When primitives are instantiated, they are initialized with colors taken from the global Styles variable. You may change this variable to adapt the look and feel of the primitives to your preferred style. This package supports unicode characters including wide characters. Many functions in this package are not thread-safe. For many applications, this may not be an issue: If your code makes changes in response to key events, it will execute in the main goroutine and thus will not cause any race conditions. If you access your primitives from other goroutines, however, you will need to synchronize execution. The easiest way to do this is to call Application.QueueUpdate() or Application.QueueUpdateDraw() (see the function documentation for details): One exception to this is the io.Writer interface implemented by TextView. You can safely write to a TextView from any goroutine. See the TextView documentation for details. You can also call Application.Draw() from any goroutine without having to wrap it in QueueUpdate(). And, as mentioned above, key event callbacks are executed in the main goroutine and thus should not use QueueUpdate() as that may lead to deadlocks. All widgets listed above contain the Box type. All of Box's functions are therefore available for all widgets, too. All widgets also implement the Primitive interface. The tview package is based on https://github.com/derailed/tcell. It uses types and constants from that package (e.g. colors and keyboard values). This package does not process mouse input (yet).

Package mph is a Go implementation of the compress, hash and displace (CHD) minimal perfect hash algorithm. See http://cmph.sourceforge.net/papers/esa09.pdf for details. To create and serialize a hash table: To read from the hash table: MMAP is also indirectly supported, by deserializing from a byte slice and slicing the keys and values. See https://github.com/alecthomas/mph for source.

Package tview implements rich widgets for terminal based user interfaces. The widgets provided with this package are useful for data exploration and data entry. The package implements the following widgets: The package also provides Application which is used to poll the event queue and draw widgets on screen. The following is a very basic example showing a box with the title "Hello, world!": First, we create a box primitive with a border and a title. Then we create an application, set the box as its root primitive, and run the event loop. The application exits when the application's Stop() function is called or when Ctrl-C is pressed. If we have a primitive which consumes key presses, we call the application's SetFocus() function to redirect all key presses to that primitive. Most primitives then offer ways to install handlers that allow you to react to any actions performed on them. You will find more demos in the "demos" subdirectory. It also contains a presentation (written using tview) which gives an overview of the different widgets and how they can be used. Throughout this package, colors are specified using the tcell.Color type. Functions such as tcell.GetColor(), tcell.NewHexColor(), and tcell.NewRGBColor() can be used to create colors from W3C color names or RGB values. Almost all strings which are displayed can contain color tags. Color tags are W3C color names or six hexadecimal digits following a hash tag, wrapped in square brackets. Examples: A color tag changes the color of the characters following that color tag. This applies to almost everything from box titles, list text, form item labels, to table cells. In a TextView, this functionality has to be switched on explicitly. See the TextView documentation for more information. Color tags may contain not just the foreground (text) color but also the background color and additional flags. In fact, the full definition of a color tag is as follows: Each of the three fields can be left blank and trailing fields can be omitted. (Empty square brackets "[]", however, are not considered color tags.) Colors that are not specified will be left unchanged. A field with just a dash ("-") means "reset to default". You can specify the following flags (some flags may not be supported by your terminal): Examples: In the rare event that you want to display a string such as "[red]" or "[#00ff1a]" without applying its effect, you need to put an opening square bracket before the closing square bracket. Note that the text inside the brackets will be matched less strictly than region or colors tags. I.e. any character that may be used in color or region tags will be recognized. Examples: You can use the Escape() function to insert brackets automatically where needed. When primitives are instantiated, they are initialized with colors taken from the global Styles variable. You may change this variable to adapt the look and feel of the primitives to your preferred style. This package supports unicode characters including wide characters. Many functions in this package are not thread-safe. For many applications, this may not be an issue: If your code makes changes in response to key events, it will execute in the main goroutine and thus will not cause any race conditions. If you access your primitives from other goroutines, however, you will need to synchronize execution. The easiest way to do this is to call Application.QueueUpdate() or Application.QueueUpdateDraw() (see the function documentation for details): One exception to this is the io.Writer interface implemented by TextView. You can safely write to a TextView from any goroutine. See the TextView documentation for details. You can also call Application.Draw() from any goroutine without having to wrap it in QueueUpdate(). And, as mentioned above, key event callbacks are executed in the main goroutine and thus should not use QueueUpdate() as that may lead to deadlocks. All widgets listed above contain the Box type. All of Box's functions are therefore available for all widgets, too. All widgets also implement the Primitive interface. There is also the Focusable interface which is used to override functions in subclassing types. The tview package is based on https://github.com/diamondburned/tcell. It uses types and constants from that package (e.g. colors and keyboard values). This package does not process mouse input (yet).

Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with S/Kademlia modifications.

Package topk implements the Filtered Space-Saving TopK streaming algorithm The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table. Licensed under the MIT license.

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 dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with S/Kademlia modifications. Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after Kademlia with S/Kademlia modifications. package query implement a query manager to drive concurrent workers to query the DHT. A query is setup with a target key, a queryFunc tasked to communicate with a peer, and a set of initial peers. As the query progress, queryFunc can return closer peers that will be used to navigate closer to the target key in the DHT until an answer is reached.

Package cuckoo provides a Cuckoo Filter, a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space. Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%). "Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf)

Offheap An off-heap hash-table for Go (golang). Originally called go-offheap-hashtable, but now shortened to just offheap. The purpose here is to have a hash table that can work away from Go's Garbage Collector, to avoid long GC pause times. We accomplish this by writing our own Malloc() and Free() implementation (see malloc.go) which requests memory directly from the OS. The keys, values, and entire hash table is kept on off-heap storage. This storage can also optionally be backed by memory mapped file for speedy persistence and fast startup times. Initial HashTable implementation inspired by the public domain C++ code of See also for performance studies of the C++ code. The implementation is mostly in offheap.go, read that to start. Maps pointer-sized integers to Cell structures, which in turn hold Val_t as well as Key_t structures. Uses open addressing with linear probing. This makes it very cache friendly and thus very fast. In the t.Cells array, UnHashedKey = 0 is reserved to indicate an unused cell. Actual value for key 0 (if any) is stored in t.ZeroCell. The hash table automatically doubles in size when it becomes 75% full. The hash table never shrinks in size, even after Clear(), unless you explicitly call Compact(). Basic operations: Lookup(), Insert(), DeleteKey(). These are the equivalent of the builtin map[uint64]interface{}. As an example of how to specialize for a map[string]*Cell equivalent, see the following functions in the bytekey.go file: Example use: Note that this library is only a starting point of source code, and not intended to be used without customization. Users of the HashTable will have to customize it by changing the definitions of Key_t and Val_t to suite their needs. On Save(), serialization of the HashTable itself is done using msgpack to write bytes to the first page (4k bytes) of the memory mapped file. This uses github.com/tinylib/msgp which is a blazing fast msgpack serialization library. It is fast because it avoids reflection and pre-computes the serializations (using go generate based inspection of your go source). If you need to serialize your values into the Val_t, I would suggest evaluating the msgp for serialization and deserialization. The author, Philip Hofer, has done a terrific job and put alot of effort into tuning it for performance. If you are still pressed for speed, consider also omitting the field labels using the '//msgp:tuple MyValueType' annotation. As Mr. Hofer says, "For smaller objects, tuple encoding can yield serious performance improvements." [https://github.com/tinylib/msgp/wiki/Preprocessor-Directives]. Related ideas: https://gist.github.com/mish15/9822474 (using CGO) CGO note: the cgo-malloc branch of this github repo has an implementation that uses CGO to call the malloc/calloc/free functions in the C stdlib. Using CGO gives up the save-to-disk instantly feature and creates a portability issue where you have linked against a specific version of the C stdlib. However if you are making/destroying alot of tables, the CGO approach may be faster. This is because calling malloc and free in the standard C library are much faster than making repeated system calls to mmap(). more related ideas: https://groups.google.com/forum/#!topic/golang-nuts/kCQP6S6ZGh0 not fully off-heap, but using a slice instead of a map appears to help GC quite alot too: https://github.com/cespare/kvcache/blob/master/refmap.go

Package merkleTree is a generic Merkle Tree implementation, for provably publishing lots of data under one succinct tree root. Install: Design: This package outputs a MerkleTree with two types of nodes: interior index nodes, or iNodes, and exterior data nodes, of Leaf nodes. The inodes consist of tables that map prefixes to child pointers. The leafs map a full hash to a "value". This is best demonstrated with a simple example. Let's say you are storing the key-value pair (`0123456789abcdef`, {"name" : "max"}) in the Merkle tree. Let's say that the shape of the tree is to have 256 children per inode. Then this key-value pair might be stored under the path Meaning at the root node, we take the first 256-bits of the needed key to get a prefix `01`, and look that up in the node's pointer table to get a child pointer, which is `aabbccdd`. This is a hash of an iNode, which we can fetch from storage, verify it matches the hash, and then recursively apply the same algorithm to find the next step in the path. The leaf node has a sparse table of long-hashes (which are the keys) that map to the values actually stored in the tree. Implementation: All nodes are encoded with msgpack before being hashed or written to store. See `types.go` for the exactly layout of the msgpack objects. Usage: To construct a new Tree from scratch, you need to specify three parameters: A Config, which specifies the shape of the Tree. That is, how many children per interior Node, and how big leaves can get before a new level of the tree is introduced. Also, the hash function to use for hashing nodes into pointers. A StorageEngine, which determines how to load and store tree Nodes from storage, and how to load and store the root hash of the Merkle tree. An array of KeyValuePairs, the things actually stored in the Merkle tree.

Package mph implements a minimal perfect hash table over strings.

Package tview implements rich widgets for terminal based user interfaces. The widgets provided with this package are useful for data exploration and data entry. The package implements the following widgets: The package also provides Application which is used to poll the event queue and draw widgets on screen. The following is a very basic example showing a box with the title "Hello, world!": First, we create a box primitive with a border and a title. Then we create an application, set the box as its root primitive, and run the event loop. The application exits when the application's Stop() function is called or when Ctrl-C is pressed. If we have a primitive which consumes key presses, we call the application's SetFocus() function to redirect all key presses to that primitive. Most primitives then offer ways to install handlers that allow you to react to any actions performed on them. You will find more demos in the "demos" subdirectory. It also contains a presentation (written using tview) which gives an overview of the different widgets and how they can be used. Throughout this package, colors are specified using the tcell.Color type. Functions such as tcell.GetColor(), tcell.NewHexColor(), and tcell.NewRGBColor() can be used to create colors from W3C color names or RGB values. Almost all strings which are displayed can contain color tags. Color tags are W3C color names or six hexadecimal digits following a hash tag, wrapped in square brackets. Examples: A color tag changes the color of the characters following that color tag. This applies to almost everything from box titles, list text, form item labels, to table cells. In a TextView, this functionality has to be switched on explicitly. See the TextView documentation for more information. Color tags may contain not just the foreground (text) color but also the background color and additional flags. In fact, the full definition of a color tag is as follows: Each of the three fields can be left blank and trailing fields can be omitted. (Empty square brackets "[]", however, are not considered color tags.) Colors that are not specified will be left unchanged. A field with just a dash ("-") means "reset to default". You can specify the following flags (some flags may not be supported by your terminal): Examples: In the rare event that you want to display a string such as "[red]" or "[#00ff1a]" without applying its effect, you need to put an opening square bracket before the closing square bracket. Note that the text inside the brackets will be matched less strictly than region or colors tags. I.e. any character that may be used in color or region tags will be recognized. Examples: You can use the Escape() function to insert brackets automatically where needed. When primitives are instantiated, they are initialized with colors taken from the global Styles variable. You may change this variable to adapt the look and feel of the primitives to your preferred style. This package supports unicode characters including wide characters. Many functions in this package are not thread-safe. For many applications, this may not be an issue: If your code makes changes in response to key events, it will execute in the main goroutine and thus will not cause any race conditions. If you access your primitives from other goroutines, however, you will need to synchronize execution. The easiest way to do this is to call Application.QueueUpdate() or Application.QueueUpdateDraw() (see the function documentation for details): One exception to this is the io.Writer interface implemented by TextView. You can safely write to a TextView from any goroutine. See the TextView documentation for details. You can also call Application.Draw() from any goroutine without having to wrap it in QueueUpdate(). And, as mentioned above, key event callbacks are executed in the main goroutine and thus should not use QueueUpdate() as that may lead to deadlocks. All widgets listed above contain the Box type. All of Box's functions are therefore available for all widgets, too. All widgets also implement the Primitive interface. There is also the Focusable interface which is used to override functions in subclassing types. The tview package is based on https://github.com/gdamore/tcell. It uses types and constants from that package (e.g. colors and keyboard values). This package does not process mouse input (yet).

Package consistent provides a consistent hashing function. Consistent hashing is often used to distribute requests to a changing set of servers. For example, say you have some cache servers cacheA, cacheB, and cacheC. You want to decide which cache server to use to look up information on a user. You could use a typical hash table and hash the user id to one of cacheA, cacheB, or cacheC. But with a typical hash table, if you add or remove a server, almost all keys will get remapped to different results, which basically could bring your service to a grinding halt while the caches get rebuilt. With a consistent hash, adding or removing a server drastically reduces the number of keys that get remapped. Read more about consistent hashing on wikipedia: http://en.wikipedia.org/wiki/Consistent_hashing

Package consistent provides a consistent hashing function. Consistent hashing is often used to distribute requests to a changing set of servers. For example, say you have some cache servers cacheA, cacheB, and cacheC. You want to decide which cache server to use to look up information on a user. You could use a typical hash table and hash the user id to one of cacheA, cacheB, or cacheC. But with a typical hash table, if you add or remove a server, almost all keys will get remapped to different results, which basically could bring your service to a grinding halt while the caches get rebuilt. With a consistent hash, adding or removing a server drastically reduces the number of keys that get remapped. Read more about consistent hashing on wikipedia: http://en.wikipedia.org/wiki/Consistent_hashing

Package cuckoo provides an implementation of a high-performance, memory efficient hash table that supports fast and safe concurrent access by multiple threads. The default version of the hash table uses string keys and interface{} values. For faster performance and fewer annoying typecasting issues, copy this code and change the valuetype appropriately.

Package dendrite implements a distributed hash table (DHT) based on Chord Protocol. Included sub-package 'dtable' is built on top of dendrite and implements distributed in-memory key/value database, with replication and failover support, with query interface to Get() or Set() items with different consistency levels. For better key distribution, dendrite allows configurable number of virtual nodes per instance (vnodes). The number of replicas in dtable is also configurable. Calling application can bootstrap the cluster, or join existing one by connecting to any of existing nodes (must be manually specified). Node discovery is not part of the implementation. Use consul (consul.io) or something else for that purpose. Chord protocol defines ring stabilization. In dendrite, stabilization period is configurable. Node to node (network) communication is built on top of ZeroMQ sockets over TCP for speed, clustering and reliability. Dendrite starts configurable number of goroutines (default: 10) for load balanced serving of remote requests, but scales that number up and down depending on the load (aka prefork model). All messages sent through dendrite are encapsulated in ChordMsg structure, where first byte indicates message type, and actual data follows. Data part is serialized with protocol buffers. Dendrite can be extended through two interfaces: TransportHook allows other packages to provide additional message types, decoders and handlers, while DelegateHook can be used to capture chord events that dendrite emits:

Package gmaj implements the Chord distributed hash table. 1. Port over tests from original code 2. Timeout connections and make an RPC function for disconnecting nodes to remove themselves from the connMap of other nodes 3. Make sure nil values in RPC methods are handled properly 4. Logging 5. Dockerize 6. Easy deployment 7. Write example app that just uses client

Package consistent provides a consistent hashing function. Consistent hashing is often used to distribute requests to a changing set of servers. For example, say you have some cache servers cacheA, cacheB, and cacheC. You want to decide which cache server to use to look up information on a user. You could use a typical hash table and hash the user id to one of cacheA, cacheB, or cacheC. But with a typical hash table, if you add or remove a server, almost all keys will get remapped to different results, which basically could bring your service to a grinding halt while the caches get rebuilt. With a consistent hash, adding or removing a server drastically reduces the number of keys that get remapped. Read more about consistent hashing on wikipedia: http://en.wikipedia.org/wiki/Consistent_hashing

Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with S/Kademlia modifications.

Package tview implements rich widgets for terminal based user interfaces. The widgets provided with this package are useful for data exploration and data entry. The package implements the following widgets: The package also provides Application which is used to poll the event queue and draw widgets on screen. The following is a very basic example showing a box with the title "Hello, world!": First, we create a box primitive with a border and a title. Then we create an application, set the box as its root primitive, and run the event loop. The application exits when the application's Stop() function is called or when Ctrl-C is pressed. If we have a primitive which consumes key presses, we call the application's SetFocus() function to redirect all key presses to that primitive. Most primitives then offer ways to install handlers that allow you to react to any actions performed on them. You will find more demos in the "demos" subdirectory. It also contains a presentation (written using tview) which gives an overview of the different widgets and how they can be used. Throughout this package, colors are specified using the tcell.Color type. Functions such as tcell.GetColor(), tcell.NewHexColor(), and tcell.NewRGBColor() can be used to create colors from W3C color names or RGB values. Almost all strings which are displayed can contain color tags. Color tags are W3C color names or six hexadecimal digits following a hash tag, wrapped in square brackets. Examples: A color tag changes the color of the characters following that color tag. This applies to almost everything from box titles, list text, form item labels, to table cells. In a TextView, this functionality has to be switched on explicitly. See the TextView documentation for more information. Color tags may contain not just the foreground (text) color but also the background color and additional flags. In fact, the full definition of a color tag is as follows: Each of the three fields can be left blank and trailing fields can be omitted. (Empty square brackets "[]", however, are not considered color tags.) Colors that are not specified will be left unchanged. A field with just a dash ("-") means "reset to default". You can specify the following flags (some flags may not be supported by your terminal): Examples: In the rare event that you want to display a string such as "[red]" or "[#00ff1a]" without applying its effect, you need to put an opening square bracket before the closing square bracket. Note that the text inside the brackets will be matched less strictly than region or colors tags. I.e. any character that may be used in color or region tags will be recognized. Examples: You can use the Escape() function to insert brackets automatically where needed. When primitives are instantiated, they are initialized with colors taken from the global Styles variable. You may change this variable to adapt the look and feel of the primitives to your preferred style. This package supports unicode characters including wide characters. Many functions in this package are not thread-safe. For many applications, this may not be an issue: If your code makes changes in response to key events, it will execute in the main goroutine and thus will not cause any race conditions. If you access your primitives from other goroutines, however, you will need to synchronize execution. The easiest way to do this is to call Application.QueueUpdate() or Application.QueueUpdateDraw() (see the function documentation for details): One exception to this is the io.Writer interface implemented by TextView. You can safely write to a TextView from any goroutine. See the TextView documentation for details. You can also call Application.Draw() from any goroutine without having to wrap it in QueueUpdate(). And, as mentioned above, key event callbacks are executed in the main goroutine and thus should not use QueueUpdate() as that may lead to deadlocks. All widgets listed above contain the Box type. All of Box's functions are therefore available for all widgets, too. All widgets also implement the Primitive interface. The tview package is based on https://github.com/gdamore/tcell. It uses types and constants from that package (e.g. colors and keyboard values). This package does not process mouse input (yet).

Set3 is an efficient set implementation in plain Go. Unlike many other set implementations, Set3 does not rely on Go's internal map data structure. Instead, it implements a hash set based on the "Fast, Efficient, Cache-friendly Hash Table" found in Abseil, Google's C++ libraries. As a result, Set3 is 10%-20% faster and the data structure uses 40% less memory than implementations based on `map[type]struct{}`.

Package rudd defines a concrete type for Binary Decision Diagrams (BDD), a data structure used to efficiently represent Boolean functions over a fixed set of variables or, equivalently, sets of Boolean vectors with a fixed size. Each BDD has a fixed number of variables, Varnum, declared when it is initialized (using the method New) and each variable is represented by an (integer) index in the interval [0..Varnum), called a level. Our library support the creation of multiple BDD with possibly different number of variables. Most operations over BDD return a Node; that is a pointer to a "vertex" in the BDD that includes a variable level, and the address of the low and high branch for this node. We use integer to represent the address of Nodes, with the convention that 1 (respectively 0) is the address of the constant function True (respectively False). For the most part, data structures and algorithms implemented in this library are a direct adaptation of those found in the C-library BuDDy, developed by Jorn Lind-Nielsen; we even implemented the same examples than in the BuDDy distribution for benchmarks and regression testing. We provide two possible implementations for BDD that can be selected using build tags. Our default implementation (without build tag) use a standard Go runtime hashmap to encode a "unicity table". When building your executable with the build tag `buddy`, the API will switch to an implementation that is very close to the one of the BuDDy library; based on a specialized data-structure that mix a dynamic array with a hash table. To get access to better statistics about caches and garbage collection, as well as to unlock logging of some operations, you can also compile your executable with the build tag `debug`. The library is written in pure Go, without the need for CGo or any other dependencies. Like with MuDDy, a ML interface to BuDDy, we piggyback on the garbage collection mechanism offered by our host language (in our case Go). We take care of BDD resizing and memory management directly in the library, but "external" references to BDD nodes made by user code are automatically managed by the Go runtime. Unlike MuDDy, we do not provide an interface, but a genuine reimplementation of BDD in Go. As a consequence, we do not suffer from FFI overheads when calling from Go into C. The following is an example of a callback handler, used in a call to Allnodes, that counts the number of active nodes in the whole BDD. The following is an example of a callback handler, used in a call to Allsat, that counts the number of possible assignments (such that we do not count don't care twice). This example shows the basic usage of the package: create a BDD, compute some expressions and output the result.

Package cuckoo implements a cuckoo hash table. With the correct options this data structure can achieve 5X more storage efficiency over Go's builtin map with similar performance. See the "README.md" file for all the details. Edit the file "kv_default.go" to define the types for you Key and Value. Demonstrate how to create a cuckoo table and insert, lookup, and delete elemebts

Package Authaus is an authentication and authorization system. Authaus brings together the following pluggable components: Any of these five components can be swapped out, and in fact the fourth, and fifth ones (Role Groups and User Store) are entirely optional. A typical setup is to use LDAP as an Authenticator, and Postgres as a Session, Permit, and Role Groups database. Your session database does not need to be particularly performant, since Authaus maintains an in-process cache of session keys and their associated tokens. Authaus was NOT designed to be a "Facebook Scale" system. The target audience is a system of perhaps 100,000 users. There is nothing fundamentally limiting about the API of Authaus, but the internals certainly have not been built with millions of users in mind. The intended usage model is this: Authaus is intended to be embedded inside your security system, and run as a standalone HTTP service (aka a REST service). This HTTP service CAN be open to the wide world, but it's also completely OK to let it listen only to servers inside your DMZ. Authaus only gives you the skeleton and some examples of HTTP responders. It's up to you to flesh out the details of your authentication HTTP interface, and whether you'd like that to face the world, or whether it should only be accessible via other services that you control. At startup, your services open an HTTP connection to the Authaus service. This connection will typically live for the duration of the service. For every incoming request, you peel off whatever authentication information is associated with that request. This is either a session key, or a username/password combination. Let's call it the authorization information. You then ask Authaus to tell you WHO this authorization information belongs to, as well as WHAT this authorization information allows the requester to do (ie Authentication and Authorization). Authaus responds either with a 401 (Unauthorized), 403 (Forbidden), or a 200 (OK) and a JSON object that tells you the identity of the agent submitting this request, as well the permissions that this agent posesses. It's up to your individual services to decide what to do with that information. It should be very easy to expose Authaus over a protocol other than HTTP, since Authaus is intended to be easy to embed. The HTTP API is merely an illustrative example. A `Session Key` is the long random number that is typically stored as a cookie. A `Permit` is a set of roles that has been granted to a user. Authaus knows nothing about the contents of a permit. It simply treats it as a binary blob, and when writing it to an SQL database, encodes it as base64. The interpretation of the permit is application dependent. Typically, a Permit will hold information such as "Allowed to view billing information", or "Allowed to paint your bathroom yellow". Authaus does have a built-in module called RoleGroupDB, which has its own interpretation of what a Permit is, but you do not need to use this. A `Token` is the result of a successful authentication. It stores the identity of a user, an expiry date, and a Permit. A token will usually be retrieved by a session key. However, you can also perform a once-off authentication, which also yields you a token, which you will typically throw away when you are finished with it. All public methods of the `Central` object are callable from multiple threads. Reader-Writer locks are used in all of the caching systems. The number of concurrent connections is limited only by the limits of the Go runtime, and the performance limits that are inherent to the simple reader-writer locks used to protect shared state. Authaus must be deployed as a single process (which implies running on a single logical machine). The sole reason why it must run on only one process and not more, is because of the state that lives inside the various Authaus caches. Were it not for these caches, then there would be nothing preventing you from running Authaus on as many machines as necessary. The cached state stored inside the Authaus server is: If you wanted to make Authaus runnable across multiple processes, then you would need to implement a cache invalidation system for these caches. Authaus makes no attempt to mitigate DOS attacks. The most sane approach in this domain seems to be this (http://security.stackexchange.com/questions/12101/prevent-denial-of-service-attacks-against-slow-hashing-functions). The password database (created via NewAuthenticationDB_SQL) stores password hashes using the scrypt key derivation system (http://www.tarsnap.com/scrypt.html). Internally, we store our hash in a format that can later be extended, should we wish to double-hash the passwords, etc. The hash is 65 bytes and looks like this: The first byte of the hash is a version number of the hash. The remaining 64 bytes are the salt and the hash itself. At present, only one version is supported, which is version 1. It consists of 32 bytes of salt, and 32 bytes of scrypt'ed hash, with scrypt parameters N=256 r=8 p=1. Note that the parameter N=256 is quite low, meaning that it is possible to compute this in approximately 1 millisecond (1,000,000 nanoseconds) on a 2009-era Intel Core i7. This is a deliberate tradeoff. On the same CPU, a SHA256 hash takes about 500 nanoseconds to compute, so we are still making it 2000 times harder to brute force the passwords than an equivalent system storing only a SHA256 salted hash. This discussion is only of relevance in the event that the password table is compromised. No cookie signing mechanism is implemented. Cookies are not presently transmitted with Secure:true. This must change. The LDAP Authenticator is extremely simple, and provides only one function: Authenticate a user against an LDAP system (often this means Active Directory, AKA a Windows Domain). It calls the LDAP "Bind" method, and if that succeeds for the given identity/password, then the user is considered authenticated. We take care not to allow an "anonymous bind", which many LDAP servers allow when the password is blank. The Session Database runs on Postgres. It stores a table of sessions, where each row contains the following information: When a permit is altered with Authaus, then all existing sessions have their permits altered transparently. For example, imagine User X is logged in, and his administrator grants him a new permission. User X does not need to log out and log back in again in order for his new permissions to be reflected. His new permissions will be available immediately. Similarly, if a password is changed with Authaus, then all sessions are invalidated. Do take note though, that if a password is changed through an external mechanism (such as with LDAP), then Authaus will have no way of knowing this, and will continue to serve up sessions that were authenticated with the old password. This is a problem that needs addressing. You can limit the number of concurrent sessions per user to 1, by setting MaxActiveSessions.ConfigSessionDB to 1. This setting may only be zero or one. Zero, which is the default, means an unlimited number of concurrent sessions per user. Authaus will always place your Session Database behind its own Session Cache. This session cache is a very simple single-process in-memory cache of recent sessions. The limit on the number of entries in this cache is hard-coded, and that should probably change. The Permit database runs on Postgres. It stores a table of permits, which is simply a 1:1 mapping from Identity -> Permit. The Permit is just an array of bytes, which we store base64 encoded, inside a text field. This part of the system doesn't care how you interpret that blob. The Role Group Database is an entirely optional component of Authaus. The other components of Authaus (Authenticator, PermitDB, SessionDB) do not understand your Permits. To them, a Permit is simply an arbitrary array of bytes. The Role Group Database is a component that adds a specific meaning to a permit blob. Let's see what that specific meaning looks like... The built-in Role Group Database interprets a permit blob as a string of 32-bit integer IDs: These 32-bit integer IDs refer to "role groups" inside a database table. The "role groups" table might look like this: The Role Group IDs use 32-bit indices, because we assume that you are not going to create more than 2^32 different role groups. The worst case we assume here is that of an automated system that creates 100,000 roles per day. Such a system would run for more than 100 years, given a 32-bit ID. These constraints are extraordinary, suggesting that we do not even need 32 bits, but could even get away with just a 16-bit group ID. However, we expect the number of groups to be relatively small. Our aim here, arbitrary though it may be, is to fit the permit and identity into a single ethernet packet, which one can reasonably peg at 1500 bytes. 1500 / 4 = 375. We assume that no sane human administrator will assign 375 security groups to any individual. We expect the number of groups assigned to any individual to be in the range of 1 to 20. This makes 375 a gigantic buffer. OAuth support in Authaus is limited to a very simple scenario: * You wish to allow your users to login using an OAuth service - thereby outsourcing the Authentication to that external service, and using it to populate the email address of your users. OAuth was developed in order to work with Microsoft Azure Active Directory, however it should be fairly easy to extend the code to be able to handle other OAuth providers. Inside the database are two tables related to OAuth: oauthchallenge: The challenge table holds OAuth sessions which have been started, and which are expected to either succeed or fail within the next few minutes. The default timeout for a challenge is 5 minutes. A challenge record is usually created the moment the user clicks on the "Sign in with Microsoft" button on your site, and it tracks that authentication attempt. oauthsession: The session table holds OAuth sessions which have successfully authenticated, and also the token that was retrieved by a successful authorization. If a token has expired, then it is refreshed and updated in-place, inside the oauthsession table. An OAuth login follows this sequence of events: 1. User clicks on a "Signin with X" button on your login page 2. A record is created in the oauthchallenge table, with a unique ID. This ID is a secret known only to the authaus server and the OAuth server. It is used as the `state` parameter in the OAuth login mechanism. 3. The HTTP call which prompts #2 return a redirect URL (eg via an HTTP 302 response), which redirects the user's browser to the OAuth website, so that the user can either grant or refuse access. If the user refuses, or fails to login, then the login sequence ends here. 4. Upon successful authorization with the OAuth system, the OAuth website redirects the user back to your website, to a URL such as example.com/auth/oauth/finish, and you'll typically want Authaus to handle this request directly (via HttpHandlerOAuthFinish). Authaus will extract the secrets from the URL, perform any validations necessary, and then move the record from the oauthchallenge table, into the oauthsession table. While 'moving' the record over, it will also add any additional information that was provided by the successful authentication, such as the token provided by the OAuth provider. 5. Authaus makes an API call to the OAuth system, to retrieve the email address and name of the person that just logged in, using the token just received. 6. If that email address does not exist inside authuserstore, then create a new user record for this identity. 7. Log the user into Authaus, by creating a record inside authsession, for the relevant identity. Inside the authsession table, store a link to the oauthsession record, so that there is a 1:1 link from the authsession table, to the oauthsession table (ie Authaus Session to OAuth Token). 8. Return an Authaus session cookie to the browser, thereby completing the login. Although we only use our OAuth token a single time, during login, to retrieve the user's email address and name, we retain the OAuth token, and so we maintain the ability to make other API calls on behalf of that user. This hasn't proven necessary yet, but it seems like a reasonable bit of future-proofing. See the guidelines at the top of all_test.go for testing instructions.

Package bbhash implements BBHash - a new algorithm for creating fast, minimal perfect hash functions as described in: https://arxiv.org/abs/1702.03154. This implementation builds the perfect hash table concurrently if the number of keys are larger than 'MinParallelKeys'. Additionally, BBHash instances can be marshaled and unmarshaled from byte buffers. This package also implements a constant database (read only) built on top of BBHash. The DB supports constant time lookups of arbitrary keys from the disk.

Package topk implements the Filtered Space-Saving TopK streaming algorithm The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table. Licensed under the MIT license.

Package tview implements rich widgets for terminal based user interfaces. The widgets provided with this package are useful for data exploration and data entry. The package implements the following widgets: The package also provides Application which is used to poll the event queue and draw widgets on screen. The following is a very basic example showing a box with the title "Hello, world!": First, we create a box primitive with a border and a title. Then we create an application, set the box as its root primitive, and run the event loop. The application exits when the application's Stop() function is called or when Ctrl-C is pressed. If we have a primitive which consumes key presses, we call the application's SetFocus() function to redirect all key presses to that primitive. Most primitives then offer ways to install handlers that allow you to react to any actions performed on them. You will find more demos in the "demos" subdirectory. It also contains a presentation (written using tview) which gives an overview of the different widgets and how they can be used. Throughout this package, colors are specified using the tcell.Color type. Functions such as tcell.GetColor(), tcell.NewHexColor(), and tcell.NewRGBColor() can be used to create colors from W3C color names or RGB values. Almost all strings which are displayed can contain color tags. Color tags are W3C color names or six hexadecimal digits following a hash tag, wrapped in square brackets. Examples: A color tag changes the color of the characters following that color tag. This applies to almost everything from box titles, list text, form item labels, to table cells. In a TextView, this functionality has to be switched on explicitly. See the TextView documentation for more information. Color tags may contain not just the foreground (text) color but also the background color and additional flags. In fact, the full definition of a color tag is as follows: Each of the three fields can be left blank and trailing fields can be omitted. (Empty square brackets "[]", however, are not considered color tags.) Colors that are not specified will be left unchanged. A field with just a dash ("-") means "reset to default". You can specify the following flags (some flags may not be supported by your terminal): Examples: In the rare event that you want to display a string such as "[red]" or "[#00ff1a]" without applying its effect, you need to put an opening square bracket before the closing square bracket. Note that the text inside the brackets will be matched less strictly than region or colors tags. I.e. any character that may be used in color or region tags will be recognized. Examples: You can use the Escape() function to insert brackets automatically where needed. When primitives are instantiated, they are initialized with colors taken from the global Styles variable. You may change this variable to adapt the look and feel of the primitives to your preferred style. This package supports unicode characters including wide characters. Many functions in this package are not thread-safe. For many applications, this may not be an issue: If your code makes changes in response to key events, it will execute in the main goroutine and thus will not cause any race conditions. If you access your primitives from other goroutines, however, you will need to synchronize execution. The easiest way to do this is to call Application.QueueUpdate() or Application.QueueUpdateDraw() (see the function documentation for details): One exception to this is the io.Writer interface implemented by TextView. You can safely write to a TextView from any goroutine. See the TextView documentation for details. You can also call Application.Draw() from any goroutine without having to wrap it in QueueUpdate(). And, as mentioned above, key event callbacks are executed in the main goroutine and thus should not use QueueUpdate() as that may lead to deadlocks. All widgets listed above contain the Box type. All of Box's functions are therefore available for all widgets, too. All widgets also implement the Primitive interface. There is also the Focusable interface which is used to override functions in subclassing types. The tview package is based on https://maunium.net/go/tcell. It uses types and constants from that package (e.g. colors and keyboard values). This package does not process mouse input (yet).

Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with S/Kademlia modifications.

Package topk implements the Filtered Space-Saving TopK streaming algorithm The original Space-Saving algorithm: https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf The Filtered Space-Saving enhancement: http://www.l2f.inesc-id.pt/~fmmb/wiki/uploads/Work/misnis.ref0a.pdf This implementation follows the algorithm of the FSS paper, but not the suggested implementation. Specifically, we use a heap instead of a sorted list of monitored items, and since we are also using a map to provide O(1) access on update also don't need the c_i counters in the hash table. Licensed under the MIT license.

Package dht implements a Distributed Hash Table (DHT) part of the BitTorrent protocol, as specified by BEP 5: http://www.bittorrent.org/beps/bep_0005.html BitTorrent uses a "distributed hash table" (DHT) for storing peer contact information for "trackerless" torrents. In effect, each peer becomes a tracker. The protocol is based on Kademila DHT protocol and is implemented over UDP. Please note the terminology used to avoid confusion. A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. The DHT is composed of nodes and stores the location of peers. BitTorrent clients include a DHT node, which is used to contact other nodes in the DHT to get the location of peers to download from using the BitTorrent protocol. Standard use involves creating a Server, and calling Announce on it with the details of your local torrent client and infohash of interest.