orderedcode

README

orderedcode

orderedcode provides a byte encoding of a sequence of typed items. The resulting bytes can be lexicographically compared to yield the same ordering as item-wise comparison on the original sequences.

This is particularly useful for specifying the order of rows in a database with lexicographically ordered string keys, such as Bigtable.

See the package documentation in orderedcode.go for details and examples.

Documentation

Overview

Package orderedcode provides a byte encoding of a sequence of typed items. The resulting bytes can be lexicographically compared to yield the same ordering as item-wise comparison on the original sequences.

More precisely, suppose:

• A is the encoding of the sequence of items [A_1..A_n],
• B is the encoding of the sequence of items [B_1..B_n],
• For each i, A_i and B_i have the same type.

Then comparing A versus B lexicographically is the same as comparing the vectors [A_1..A_n] and [B_1..B_n] lexicographically.

Furthermore, if i < j then [A_1..A_i]'s encoding is a prefix of [A_1..A_j]'s encoding.

The order-maintaining and prefix properties described above are useful for generating keys for databases like Bigtable.

Call Append(buffer, item1, ..., itemN) to construct the encoded bytes. The valid item types are:

• string,
• struct{}, which is an 'infinity' that sorts greater than any other string,
• orderedcode.StringOrInfinity, which is a union type,
• TrailingString,
• float64,
• int64,
• uint64.

As a convenience, orderedcode.Infinity is a value of type struct{}. For example, to encode a sequence of two strings, an 'infinity' and an uint64:

buf, err := orderedcode.Append(
	nil, "foo", "bar", orderedcode.Infinity, uint64(42))
if err != nil {
	return err
}
key := string(buf)

Alternatively, encoding can be done in multiple steps:

var buf []byte
// Ignore errors, for demonstration purposes.
buf, _ = orderedcode.Append(buf, "foo")
buf, _ = orderedcode.Append(buf, "bar")
buf, _ = orderedcode.Append(buf, orderedcode.Infinity)
buf, _ = orderedcode.Append(buf, uint64(42))
key := string(buf)

Call Parse(encoded, &item1, ..., &itemN) to deconstruct an encoded string. The valid argument types are the pointers to the valid encoding types. For example:

var (
	s1, s2    string
	infinity3 struct{}
	u4        uint64
)
remainingKey, err := orderedcode.Parse(key, &s1, &s2, &infinity3, &u4)

Alternatively:

var (
	x1, x2, x3 orderedcode.StringOrInfinity
	u4         uint64
)
remainingKey, err := orderedcode.Parse(key, &x1, &x2, &x3, &u4)

A TrailingString is a string that, if present, must be the last item appended or parsed. It is not mandatory to use a TrailingString; it is valid for the last item to be a standard string or any other type listed above. A TrailingString simply allows a more efficient encoding while retaining the lexicographic order-maintaining property. If used, you cannot append a TrailingString and parse the result as a standard string, or as a StringOrInfinity. For example:

key, err := orderedcode.Append(
	nil, "first", "middle", orderedcode.TrailingString("last"))
if err != nil {
	return err
}
var (
	s1, s2 string
	t3     orderedcode.TrailingString
)
remainingKey, err := orderedcode.Parse(string(key), &s1, &s2, &t3)
if err != nil {
	return err
}
fmt.Printf("trailing string: got s1=%q s2=%q t3=%q\n", s1, s2, t3)

The same sequence of types should be used for encoding and decoding (although StringOrInfinity can substitute for either a string or a struct{}, but not for a TrailingString). The wire format is not fully self-describing: "\x00\x01\x04\x03\x02\x00\x01" is a valid encoding of both ["", "\x04\x03\x02"] and [uint64(0), uint64(4), uint64(0x20001)]. Decoding into a pointer of the wrong type may return corrupt data and no error.

Each item can optionally be encoded in decreasing order. If the i'th item is and the lexicographic comparison of A and B comes down to A_i versus B_i, then A < B will equal A_i > B_i.

To encode in decreasing order, wrap the item in an orderedcode.Decr value. To decode, wrap the item pointer in an orderedcode.Decr. For example:

key, err := orderedcode.Append(nil, "foo", orderedcode.Decr("bar"))
if err != nil {
	return err
}
var s1, s2 string
_, err := orderedcode.Parse(string(key), &s1, orderedcode.Decr(&s2))
if err != nil {
	return err
}
fmt.Printf("round trip: got s1=%q s2=%q\n", s1, s2)

Each item's ordering is independent from other items, but the same ordering should be used to encode and decode the i'th item.

Index

• Variables
• func Append(buf []byte, items ...interface{}) ([]byte, error)
• func Decr(val interface{}) interface{}
• func Parse(encoded string, items ...interface{}) (remaining string, err error)
• type StringOrInfinity
• type TrailingString

Variables

var Infinity struct{}

Infinity is an encodable value that sorts greater than any other string.

Functions

func Append

func Append(buf []byte, items ...interface{}) ([]byte, error)

Append appends the encoded representations of items to buf. Items can have different underlying types, but each item must have type T or be the value Decr(somethingOfTypeT), for T in the set: string, struct{}, StringOrInfinity, TrailingString, float64, int64 or uint64.

func Decr

func Decr(val interface{}) interface{}

Decr wraps a value so that it is encoded or decoded in decreasing order.

func Parse

func Parse(encoded string, items ...interface{}) (remaining string, err error)

Parse parses the next len(items) of their respective types and returns any remaining encoded data. Items can have different underlying types, but each item must have type *T or be the value Decr(somethingOfTypeStarT), for T in the set: string, struct{}, StringOrInfinity, TrailingString, float64, int64 or uint64.

Types

type StringOrInfinity

type StringOrInfinity struct {
	String   string
	Infinity bool
}

StringOrInfinity is a union type. If Infinity is true, String must be "", and the value represents an 'infinity' that is greater than any other string. Otherwise, the value is the String string.

type TrailingString

type TrailingString string

TrailingString is a string that, if present, must be the last item appended or parsed.