Documentation ¶
Overview ¶
Package space defines abstract notions of points and ranges. It's used in Akutan to describe the keys and hashes that servers host.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ImplementPoint = []Point{ Key(""), Hash64(0), Infinity, }
ImplementPoint is a list of types that implement Point in this package. This serves as documentation and as a compile-time check.
Functions ¶
Types ¶
type Hash64 ¶
type Hash64 uint64
Hash64 is a type of Point in a 64-bit hash-space.
type InfinitePoint ¶
type InfinitePoint struct{}
InfinitePoint is a sentinel for the largest possible Point value. It's commonly used as being the end of an entire space.
var Infinity InfinitePoint
Infinity is an instance of InfinitePoint, for convenience.
func (InfinitePoint) Less ¶
func (a InfinitePoint) Less(b Point) bool
Less implements Point.Less by always returning false.
type Key ¶
type Key string
Key is a type of Point in a lexically-ordered string key-space.
type PartitionedRange ¶
type PartitionedRange struct { // The first point of each subrange, in sorted order. StartPoints[i] represents // the subrange from StartPoints[i] to StartPoints[i+1]. The last entry // represents the subrange from itself to End. StartPoints []Point // Just past the final point in the overall range. End Point }
A PartitionedRange is a compressed representation of a split up range. The entire range is StartPoints[0] to End. It's partitioned at the boundaries given by StartPoints[1:], so the number of subranges is len(StartPoints).
func (*PartitionedRange) Find ¶
func (ranges *PartitionedRange) Find(point Point) int
Find returns the index of the subrange containing 'point'. It returns -1 if the point falls outside OverallRange().
Example ¶
ranges := PartitionedRange{ StartPoints: []Point{Key("d"), Key("m"), Key("t")}, End: Key("x"), } fmt.Print( ranges.Find(Key("diego")), ranges.Find(Key("alice")), ranges.Find(Key("raymond")), ranges.Find(Key("zara")), ranges.Find(Key("taylor")), ranges.Find(Key("simon")), )
Output: 0 -1 1 -1 2 1
func (*PartitionedRange) Get ¶
func (ranges *PartitionedRange) Get(i int) Range
Get returns the i-th subrange.
Example ¶
ranges := PartitionedRange{ StartPoints: []Point{Key("d"), Key("m"), Key("t")}, End: Key("x"), } fmt.Printf("%+v\n", ranges.Get(0)) fmt.Printf("%+v\n", ranges.Get(2))
Output: {Start:d End:m} {Start:t End:x}
func (*PartitionedRange) OverallRange ¶
func (ranges *PartitionedRange) OverallRange() Range
OverallRange returns the range from the first point of the first subrange to the end point of the last subrange.
Example ¶
ranges := PartitionedRange{ StartPoints: []Point{Key("d"), Key("m"), Key("t")}, End: Key("x"), } fmt.Printf("%+v\n", ranges.OverallRange())
Output: {Start:d End:x}
type Point ¶
type Point interface { // Less compares point values. It returns true if this point has a strictly // smaller value than 'other', false otherwise. Less(other Point) bool }
A Point is a location in a space. For example, a hash value in a hash-space is a Point. In this package, Hash64 and Key implement Point.
type Range ¶
type Range struct { // The first Point in the range. Start Point // Just past the last Point in the range. End Point }
A Range is an interval from the Start point up to but excluding the End point.