Hash Table

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 dht implements a distributed hash table that satisfies the dms3 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 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.

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 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 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://git.parallelcoin.io/dev/tview. It uses types and constants from that package (e.g. colors and keyboard values). This package does not process mouse input (yet).

Package merkletree is an implementation of a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree). It provides methods to create a tree and generate and verify proofs. The hashing algorithm for the tree is selectable between BLAKE2b and Keccak256, or you can supply your own. This implementation includes advanced features salting and pollarding. Salting is the act of adding a piece of data to each value in the Merkle tree as it is initially hashed to form the leaves, which helps avoid rainbow table attacks on leaf hashes presented as part of proofs. Pollarding is the act of providing the root plus all branches to a certain height which can be used to reduce the size of proofs. This is useful when multiple proofs are presented against the same tree as it can reduce the overall size. Creating a Merkle tree requires a list of values that are each byte arrays. Once a tree has been created proofs can be generated using the tree's GenerateProof() function. The package includes a function VerifyProof() to verify a generated proof given only the data to prove, proof and the pollard of the relevant Merkle tree. This allows for efficient verification of proofs without requiring the entire Merkle tree to be stored or recreated. The tree pads its values to the next highest power of 2; values not supplied are treated as null with a value hash of 0. This can be seen graphically by generating a DOT representation of the graph with DOT(). If salting is enabled it appends an 4-byte value to each piece of data. The value is the binary representation of the index in big-endian form. Note that if there are more than 2^32 values in the tree the salt will wrap, being modulo 2^32 Package merkletree is an implementation of a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree). It provides methods to create a tree and generate and verify proofs. The hashing algorithm for the tree is selectable between BLAKE2b and Keccak256, or you can supply your own. This implementation includes advanced features salting and pollarding. Salting is the act of adding a piece of data to each value in the Merkle tree as it is initially hashed to form the leaves, which helps avoid rainbow table attacks on leaf hashes presented as part of proofs. Pollarding is the act of providing the root plus all branches to a certain height which can be used to reduce the size of proofs. This is useful when multiple proofs are presented against the same tree as it can reduce the overall size. Creating a Merkle tree requires a list of values that are each byte arrays. Once a tree has been created proofs can be generated using the tree's GenerateProof() function. The package includes a function VerifyProof() to verify a generated proof given only the data to prove, proof and the pollard of the relevant Merkle tree. This allows for efficient verification of proofs without requiring the entire Merkle tree to be stored or recreated. The tree pads its values to the next highest power of 2; values not supplied are treated as null with a value hash of 0. This can be seen graphically by generating a DOT representation of the graph with DOT(). If salting is enabled it appends an 4-byte value to each piece of data. The value is the binary representation of the index in big-endian form. Note that if there are more than 2^32 values in the tree the salt will wrap, being modulo 2^32

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 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 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() (see its 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. 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 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() (see its 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. 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 cuckoo provides a Cuckoo Filter (Practically Better Than Bloom). 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. Implementation is based heavily on whitepaper: "Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf).

Package store provides a disk-backed data structure for use in storing []byte values referenced by 128 bit keys with options for replication. It can handle billions of keys (as memory allows) and full concurrent access across many cores. All location information about each key is stored in memory for speed, but values are stored on disk with the exception of recently written data being buffered first and batched to disk later. This has been written with SSDs in mind, but spinning drives should work also; though storing toc files (Table Of Contents, key location information) on a separate disk from values files is recommended in that case. Each key is two 64bit values, known as keyA and keyB uint64 values. These are usually created by a hashing function of the key name, but that duty is left outside this package. Each modification is recorded with an int64 timestamp that is the number of microseconds since the Unix epoch (see github.com/gholt/brimtime.TimeToUnixMicro). With a write and delete for the exact same timestamp, the delete wins. This allows a delete to be issued for a specific write without fear of deleting any newer write. Internally, each modification is stored with a uint64 timestamp that is equivalent to (brimtime.TimeToUnixMicro(time.Now())<<8) with the lowest 8 bits used to indicate deletions and other bookkeeping items. This means that the allowable time range is 1970-01-01 00:00:00 +0000 UTC (+1 microsecond because all zeroes indicates a missing item) to 4253-05-31 22:20:37.927935 +0000 UTC. There are constants TIMESTAMPMICRO_MIN and TIMESTAMPMICRO_MAX available for bounding usage. There are background tasks for: * TombstoneDiscard: This will discard older tombstones (deletion markers). Tombstones are kept for Config.TombstoneAge seconds and are used to ensure a replicated older value doesn't resurrect a deleted value. But, keeping all tombstones for all time is a waste of resources, so they are discarded over time. Config.TombstoneAge controls how long they should be kept and should be set to an amount greater than several replication passes. * PullReplication: This will continually send out pull replication requests for all the partitions the ValueStore is responsible for, as determined by the Config.MsgRing. The other responsible parties will respond to these requests with data they have that was missing from the pull replication request. Bloom filters are used to reduce bandwidth which has the downside that a very small percentage of items may be missed each pass. A moving salt is used with each bloom filter so that after a few passes there is an exceptionally high probability that all items will be accounted for. * PushReplication: This will continually send out any data for any partitions the ValueStore is *not* responsible for, as determined by the Config.MsgRing. The responsible parties will respond to these requests with acknowledgements of the data they received, allowing the requester to discard the out of place data. * Compaction: TODO description. * Audit: This will verify the data on disk has not been corrupted. It will slowly read data over time and validate checksums. If it finds issues, it will try to remove affected entries the in-memory location map so that replication from other stores will send the information they have and the values will get re-stored locally. In cases where the affected entries cannot be determined, it will make a callback requesting the store be shutdown and restarted; this restart will result in the affected keys being missing and therefore replicated in by other stores. Note that if the disk gets filled past a configurable threshold, any external writes other than deletes will result in error. Internal writes such as compaction and removing successfully push-replicated data will continue. There is also a modified form of ValueStore called GroupStore that expands the primary key to two 128 bit keys and offers a Lookup method which retrieves all matching items for the first key.

Package emacs contains infrastructure to write dynamic modules for Emacs in Go. See Emacs Dynamic Modules and Writing Dynamically-Loaded Modules for background on Emacs modules. To build an Emacs module, you have to build your Go code as a shared C library, e.g., using go build ‑buildmode=c‑shared. If you import the emacs package, the shared library is loadable as an Emacs module. This package contains high-level as well as lower-level functions. The high-level functions help reducing boilerplate when exporting functions to Emacs and calling Emacs functions from Go. The lower-level functions are more type-safe, support more exotic use cases, and have less overhead. At the highest level, use the Export function to export Go functions to Emacs, and the Import function to import Emacs functions so that they can be called from Go. These functions automatically convert between Go and Emacs types as necessary. This export functionality is unrelated to exported Go names or the Cgo export functionality. Functions exported to Emacs don’t have to be exported in the Go or Cgo sense. The automatic type conversion behaves as follows. Go bool values are become the Emacs symbols nil and t. When converting to Go bool, only nil becomes false, any other value becomes true. This matches the Emacs convention that all non-nil values represent a logically true value. Go integral values become Emacs integer values and vice versa. Go floating-point values become Emacs floating-point values and vice versa. Go strings become Emacs strings and vice versa. Go []byte arrays and slices become Emacs unibyte strings. Emacs unibyte strings become Go []byte slices. Other Go arrays and slices become Emacs vectors. Emacs vectors become Go slices. Go maps become Emacs hash tables and vice versa. All types that implement In can be converted to Emacs. All types that implement Out can be converted from Emacs. You can implement In or Out yourself to extend the type conversion machinery. A reflect.Value behaves like its underlying value. Functions exported via Export don’t have a documentation string by default. To add one, pass a Doc value to Export. Since argument names aren’t available at runtime, the documentation by default lacks argument names. Use Usage to add argument names. As an alternative to Import, you can call functions directly using Env.Invoke. Env.Invoke uses the same autoconversion rules as Import, but allows you to specify an arbitrary function value. At a slightly lower level, you can use Env.Call and Env.CallOut to call Emacs functions. These functions use the In and Out interfaces to convert from and to Emacs values. The primary disadvantage of this approach is that you can’t use primitive types like int or string directly. Use wrapper types like Int and String instead. On the other hand, Env.Call and Env.CallOut are more type-safe than [Invoke]. If you use [Call] or [CallOut], the compiler will detect unsupported types. By contrast, when using Export, Import, or [Invoke], they will only be detected at runtime and cause runtime panics or errors. To reduce boilerplate when using Env.Call and Env.CallOut, this package contains several convenience types that implement In or Out. Most primitive types have corresponding wrapper types, such as Int, Float, or String. Types such as List, Cons, or Hash allow you to pass common Lisp structures without much boilerplate. There are also some destructuring types such as ListOut or Uncons. At an even lower level, you can use ExportFunc, ImportFunc, and Env.Funcall as alternatives to Export, Import, and Env.Call, respectively. They have the same behavior, but don’t do any type conversion at all. The fundamental types for interacting with Emacs are Env and Value. They represent Emacs module environments and values as described in Writing Module Functions. These types are opaque, and their zero values are invalid. You can’t use Env and Value values once they are no longer live. This is described in Writing Module Functions and Conversion Between Lisp and Module Values. As a best practice, don’t let these values escape exported functions. You also can’t interact with Emacs from other threads, cf. Writing Module Functions. These rules are a bit subtle, but you are usually on the safe side if you don’t store Env and Value values in struct fields or global variables, and don’t pass them to other goroutines. All functions in this package translate between Go errors and Emacs nonlocal exits. See Nonlocal Exits in Modules. This package represents Emacs nonlocal exits as ordinary Go errors. Each call to a function fetches and clears nonlocal exit information after the actual call and converts it to an error of type Signal or Throw. This means that the Go bindings don’t exhibit the saturating error behavior described at Nonlocal Exits in Modules. Instead, they behave like normal Go functions: an erroneous return doesn’t affect future function calls. When returning from an exported function, this package converts errors back to Emacs nonlocal exits. If you return a Signal or Error, Emacs will raise a signal using the signal function. If you return a Throw, Emacs will throw to a catch using the throw function. If you return any other type of error, Emacs will signal an error of type go‑error, with the error string as signal data. You can define your own error symbols using DefineError. There are also a couple of factory functions for builtin errors such as WrongTypeArgument and OverflowError. You can use Var to define a dynamic variable. This package intentionally doesn’t support wrapping pointers to arbitrary Go values in Emacs user pointer objects. Attempting to do that wouldn’t work well with Go’s garbage collection and CGo’s pointer-passing rules; see Passing pointers. Instead, prefer using handles, e.g. simple integers as map keys. See the “Handles” example. A long-running operation should periodically call Env.ProcessInput to process pending input and to check whether the user wants to quit the operation. If so, you should cancel the operation as soon as possible. See the documentation of Env.ProcessInput for a concrete example. As an alternative, this package provides limited support for asynchronous operations. Such operations are represented using the AsyncHandle type. You can use the Async type to create and manage asynchronous operations. Async requires a way to notify Emacs about a pending asynchronous result; this package supports notification using pipes or sockets. If you want to run code while Emacs is loading the module, use OnInit to register initialization functions. Loading the module will call all initialization functions in order. You can use ERTTest to define ERT tests backed by Go functions. This works similar to Export, but defines ERT tests instead of functions.

Package kht provides an implementation of a keyed hash tree. A keyed hash tree is a hash tree which uses a keyed hash algorithm (e.g., HMAC), used to derive block-level keys for encrypting large files. The notion of a keyed hash tree comes from Rajendran, Li, et al's papers on Horus, a large-scale encrypted storage system (http://www.ssrc.ucsc.edu/pub/rajendran11-pdsw.html and https://www.usenix.org/conference/fast13/technical-sessions/presentation/li_yan). A keyed hash tree with a branching factor of 2 has log2(maxSize/blockSize) levels, each with increasing numbers of keys. The root node (the top of the diagram) uses the tree's root key, and the leaf nodes (the bottom of the diagram) contain the keys used to encrypt the corresponding blocks of data. The nodes are not materialized, which means a keyed hash table takes a very small amount of memory (~100 bytes), and deriving block keys is very fast (~8μs for each 1KiB block of a 2GiB tree with a branching factor of 1024 using HMAC-SHA-256).

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

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

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 ommitting 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 apporach 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 dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with Coral and S/Kademlia modifications. Package dht implements a distributed hash table that satisfies the ipfs routing interface. This DHT is modeled after kademlia with Coral and S/Kademlia modifications.

Holographic storage for distributed applications. A holochain is a monotonic distributed hash table (DHT) where every node enforces validation rules on data before publishing that data against the signed chains where the data originated. In other words, a holochain functions very much like a blockchain without bottlenecks when it comes to enforcing validation rules, but is designed to be fully distributed with each node only needing to hold a small portion of the data instead of everything needing a full copy of a global ledger. This makes it feasible to run blockchain-like applications on devices as lightweight as mobile phones. There are two modes to participate in a holochain: as a **chain author**, and as a **DHT node**. We expect most installations will be doing both things and acting as full peers in a P2P data system. However, each could be run in a separate container, communicating only by network interface. Your chain is your signed, sequential record of the data you create to share on the holochain. Depending on the holochain's validation rules, this data may also be immutable and non-repudiable. Your local chain/data-store follows this pattern: For serving data shared across the network. When your node receives a request from another node to publish DHT data, it will first validate the signatures, chain links, and any other application specific data integrity in the entity's source chain who is publishing the data. See http://github.com/metacurrency/holochain for installation instructions, project status, and developer information. Holochains are a distributed data store: DHT tightly bound to signed hash chains for provenance and data integrity.

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

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

Package hamt is the unifying package between the 32bit and 64bit implementations of Hash Array Mapped Tries (HAMT). HAMT datastructure make an efficient hashed map data structure. You can `import hamt "github.com/lleo/go-hamt"` then instantiate either a hamt32 or hamt64 datastructure with the `hamt.NewHamt32()` or `hamt.NewHamt64()` functions. Both datastructures have the same exported API defined by the Hamt interface. Given how wide a HAMT node is (either 32 or 64 nodes wide) HAMT datastructures not very deep; either 6, for 32bit, or 10, for 64bit implementations, nodes deep. This neans HAMTs are effectively O(1) for Search, Insertions, and Deletions. Both 32 and 64 bit implementations of HAMTs are of fixed depth is because they are [Tries](https://en.wikipedia.org/wiki/Trie). The key of a Trie is split into n-number smaller indecies and each node from the root uses each successive index. In the case of a this HAMT implementation the key is hashed into a 30 or 60 bit number. In the case of the stringkey we take the []byte slice of the string and feed it to hash.fnv.New32() or New64() hash generator. Since these generate 32 and 64 bit hash values respectively and we need 30 and 60 bit values, we use the [xor-fold technique](http://www.isthe.com/chongo/tech/comp/fnv/index.html#xor-fold) to "fold" the high 2 or 4 bits of the 32 and 64 bit hash values into 30 and 60 bit values for our needs. We want 30 and 60 bit values because they split nicely into six 5bit and ten 6bit values respectively. Each of these 5 and 6 bit values become the indexies of our Trie nodes with a maximum depth of 6 or 10 respectively. Further 5 bits indexes into a 32 entry table nodes for 32 bit HAMTs and 6 bit index into 64 entry table nodes for 64 bit HAMTs; isn't that symmetrical :). For a this HAMT implementation, when key/value pair must be created, deleted, or changed the key is hashed into a 30 or 60 bit value (described above) and that hash30 or hash60 value represents a path of 5 or 6 bit values to place a leaf containing the key, value pair. For a Get() or Del() operation we lookup the deepest node along that pate that is not-nil. For a Put() operation we lookup the deepest location that is nil and not beyond the lenth of the path. You may implement your own Key type by implementeding the Key interface defined in "github.com/lleo/go-hamt/key" or you may used the example StringKey interface described in "github.com/lleo/go-hamt/stringkey".

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 perceptive implements perceptual hash algorithms for comparing images. Perceptual hash algorithms are a family of comparable hash functions which generate distinct (but not unique) fingerprints, these fingerprints are then comparable. Perceptual hash algorithms are mainly used for detecting duplicates of the same files, in a way that standard and cryptographic hashes generally fail. The following perceptual hash algorithms are implemented: - Average Hash (Ahash) - Fast but generates a huge number of false positives. - Difference Hash (Dhash) - Fast and very few false positives. Below are some examples on how to use the library: You can also use the perceptual hash algorithms directly, this is good if you want to store the hashes in a database or some look up table: When performing a Hamming distance on two hashes from Ahash or Dhash, the distance output has the following meaning: - A distance of 0 means that the images are likely the same. - A distance between 1-10 indicates the images are likely a variation of each other. - A distance greater than 10 indicates the images are likely different.

Package key contains a single Key interface. The key package was created to prevent cicular dependencies between "github.com/lleo/go-hamt" and either "github.com/lleo/go-hamt/hamt32", "github.com/lleo/go-hamt/hamt64", "github.com/lleo/go-hamt-functional/hamt32", or "github.com/lleo/go-hamt-functional/hamt64" Additionally, the "github.com/lleo/go-hamt-key" provides a Base structure. The Base structure if added to a derivative key type will provide the k.Hash30() and k.Hash60() methods. Base needs to be populated by the derivative key constructor calling the k.Initialize([]byte) method. Any key created using the Key interface must be read-only after construction. The Hash30() returns a special type HashVal30. Which really just an alias for uint32 that stores a 30 bit hash value, but it provides methods for viewing the 30 bit hash30 value. For instance the hv.Index() method will pull out the 5 bit integer values, as a uint, for each depth of the Hamt datastructure that is really the index into a table. Also, there are methods to produce string representations of the underlying 30 bit hash value. The Hash60() returns a special type HashVal60. Which really just an alias for uint64 that stores a 60 bit hash value, but it provides methods for viewing the 60 bit hash60 value. For instance the hv.Index() method will pull out the 5 bit integer values, as a uint, for each depth of the Hamt datastructure that is really the index into a table. Also, there are methods to produce string representations of the underlying 60 bit hash value. The key package is also used by the functional HAMT variation in "github.com/lleo/go-hamt-functional".

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 lww implements a Last-Writer-Wins (LWW) Element Set data structure. In distributed computing, a conflict-free replicated data type (CRDT) is a type of specially-designed data structure used to achieve strong eventual consistency (SEC) and monotonicity (absence of rollbacks). One type of data structure used in implementing CRDT is LWW-element-set. LWW-element-set is a set that its elements have timestamp. Add and remove will save the timestamp along with data in two different sets for each element. Queries over LWW-set will check both add and remove timestamps to decide about state of each element is being existed to removed from the list. lww package implements LWW data structure in a modular way. It defines a TimedSet interface for underlying storage. lww package includes two storage underlying. Set is one implementation of TimedSet. It uses Go maps to store data. It is a fast but volatile implementation. Maps in theory have worse Big O of O(n) for different operations, but in practice they are almost reliable for O(1) as long as hash function and hash table implementations are good enough. Set is the default underlying for LWW if no other TimedSet are attached to AddSet or RemoveSet. Maps are by nature vulnerable to concurrent access. To avoid race problems Set uses a sync.RWMutex as its locking mechanism. RedisSet is another implementation of TimedSet included in lww package. It uses Redis Sorted Sets to store data. Redis nature of atomic operations makes it immune to race problem and there is no need to any extra lock mechanism. But it introduces other complexities. To keep the lww simple, handling of Redis connection for both AddSet and RemoveSet in case of RedisSet is passed to client. It is practical as Redis setup can vary based on application and client might want handle complex connection handling. To add a new underlying you need to implement the necessary methods in your structure. They are defined in TimedSet interface. Assuming you do that and they work as expected you can initialize LWW like: Note that in theory AddSet and RemoveSet can have different underlying attached. This might be useful in applications which can predict higher magnitude of Adds compared to Removes. In that case application can implementation different types of TimedSet to optimize the setup There is also a an underlying implementation that mixes two Map and Redis implementations. It is available at https://github.com/kavehmz/qset. That implementation is more practical as it will be as fast as internal maps but persistent and sharable through a redis server.

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