ad02d8f300
This modifies the entire repository to use the new formatting of doc comments in the upcoming Go 1.19 release. The primary motivating factors for this are: - Builds check that files are formatted per gofmt and that will no longer be true as of Go 1.19 without these changes - Separating all the updates into a single commit ensures these documentation only formatting changes do not clutter up diffs that actually change code For the most part, the changes are just the automated changes suggested by the Go 1.19 version of gofmt, but there are also a few cases where the comments were reworded a bit to play nicely with the new formatting requirements. For example, the new version of gofmt reformats and collapses nested lists where as the existing version does not. Thus, instances of nested lists have been changed to either eliminate them or use mixed markers which produce expect results. |
||
|---|---|---|
| .. | ||
| common_test.go | ||
| common.go | ||
| doc.go | ||
| immutable_test.go | ||
| immutable.go | ||
| mutable_test.go | ||
| mutable.go | ||
| README.md | ||
| treapiter_test.go | ||
| treapiter.go | ||
treap
Package treap implements a treap data structure that is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n). Both mutable and immutable variants are provided.
The mutable variant is typically faster since it is able to simply update the treap when modifications are made. However, a mutable treap is not safe for concurrent access without careful use of locking by the caller and care must be taken when iterating since it can change out from under the iterator.
The immutable variant works by creating a new version of the treap for all mutations by replacing modified nodes with new nodes that have updated values while sharing all unmodified nodes with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.
Package treap is licensed under the copyfree ISC license.
Usage
This package is only used internally in the database code and as such is not available for use outside of it.
License
Package treap is licensed under the copyfree ISC License.