gcs

Documentation

Index

• Constants
• Variables
• type Filter
  • func FromBytes(N uint32, P uint8, d []byte) (*Filter, error)
  • func FromNBytes(P uint8, d []byte) (*Filter, error)
  • func FromNPBytes(d []byte) (*Filter, error)
  • func FromPBytes(N uint32, d []byte) (*Filter, error)
  • func NewFilter(P uint8, key [KeySize]byte, data [][]byte) (*Filter, error)
  • func (f *Filter) Bytes() []byte
  • func (f *Filter) Match(key [KeySize]byte, data []byte) bool
  • func (f *Filter) MatchAny(key [KeySize]byte, data [][]byte) bool
  • func (f *Filter) N() uint32
  • func (f *Filter) NBytes() []byte
  • func (f *Filter) NPBytes() []byte
  • func (f *Filter) P() uint8
  • func (f *Filter) PBytes() []byte

Constants

const KeySize = 16

KeySize is the size of the byte array required for key material for the SipHash keyed hash function.

Variables

var (
	// ErrNTooBig signifies that the filter can't handle N items.
	ErrNTooBig = errors.New("N does not fit in uint32")

	// ErrPTooBig signifies that the filter can't handle `1/2**P`
	// collision probability.
	ErrPTooBig = errors.New("P is too large")

	// ErrNoData signifies that an empty slice was passed.
	ErrNoData = errors.New("no data provided")

	// ErrMisserialized signifies a filter was misserialized and is missing the
	// N and/or P parameters of a serialized filter.
	ErrMisserialized = errors.New("misserialized filter")
)

Types

type Filter

type Filter struct {
	// contains filtered or unexported fields
}

Filter describes an immutable filter that can be built from a set of data elements, serialized, deserialized, and queried in a thread-safe manner. The serialized form is compressed as a Golomb Coded Set (GCS), but does not include N or P to allow the user to encode the metadata separately if necessary. The hash function used is SipHash, a keyed function; the key used in building the filter is required in order to match filter values and is not included in the serialized form.

func FromBytes

func FromBytes(N uint32, P uint8, d []byte) (*Filter, error)

FromBytes deserializes a GCS filter from a known N, P, and serialized filter as returned by Bytes().

func FromNBytes

func FromNBytes(P uint8, d []byte) (*Filter, error)

FromNBytes deserializes a GCS filter from a known P, and serialized N and filter as returned by NBytes().

func FromNPBytes

func FromNPBytes(d []byte) (*Filter, error)

FromNPBytes deserializes a GCS filter from a serialized N, P, and filter as returned by NPBytes().

func FromPBytes

func FromPBytes(N uint32, d []byte) (*Filter, error)

FromPBytes deserializes a GCS filter from a known N, and serialized P and filter as returned by NBytes().

func NewFilter

func NewFilter(P uint8, key [KeySize]byte, data [][]byte) (*Filter, error)

NewFilter builds a new GCS filter with the collision probability of `1/(2**P)`, key `key`, and including every `[]byte` in `data` as a member of the set.

func (*Filter) Bytes

func (f *Filter) Bytes() []byte

Bytes returns the serialized format of the GCS filter, which does not include N or P (returned by separate methods) or the key used by SipHash.

func (*Filter) Match

func (f *Filter) Match(key [KeySize]byte, data []byte) bool

Match checks whether a []byte value is likely (within collision probability) to be a member of the set represented by the filter.

func (*Filter) MatchAny

func (f *Filter) MatchAny(key [KeySize]byte, data [][]byte) bool

MatchAny checks whether any []byte value is likely (within collision probability) to be a member of the set represented by the filter faster than calling Match() for each value individually.

func (*Filter) N

func (f *Filter) N() uint32

N returns the length of the data to build the filter

func (*Filter) NBytes

func (f *Filter) NBytes() []byte

NBytes returns the serialized format of the GCS filter with N, which does not include P (returned by a separate method) or the key used by SipHash.

func (*Filter) NPBytes

func (f *Filter) NPBytes() []byte

NPBytes returns the serialized format of the GCS filter with N and P, which does not include the key used by SipHash.

func (*Filter) P

func (f *Filter) P() uint8

P returns the filter's collision probability as a negative power of 2 (that is, a collision probability of `1/2**20` is represented as 20).

func (*Filter) PBytes

func (f *Filter) PBytes() []byte

PBytes returns the serialized format of the GCS filter with P, which does not include N (returned by a separate method) or the key used by SipHash.