roaring

package
v2.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 25, 2020 License: Apache-2.0 Imports: 15 Imported by: 2

README

The Fuzzer

For complete documentation on go-fuzz, please see: https://github.com/dvyukov/go-fuzz

The fuzzer in relation to the roaring package checks the Bitmap.UnmarshalBinary function found in roaring.go. In order to use the fuzzer, you can follow these steps:

cd $GOPATH/src/github.com/pilosa/pilosa/roaring

go-fuzz-build ./

You must now make the workdir/corpus directory. This is achieved by:

mkdir workdir/corpus

The fuzzer needs some input to start the fuzzing with. Copy some sample Pilosa fragments into the workdir/corpus folder. For example:

cp ~/.pilosa/my-index/my-field/views/standard/fragments/0 workdir/corpus

Once you have copied your sample inputs, you are ready to run the fuzzer:

go-fuzz -bin=roaring-fuzz.zip -workdir=workdir -func=FuzzBitmapUnmarshalBinary

Understanding the Fuzzer Output

The fuzzer will output something similar to the follwoing:

2015/04/25 12:39:53 workers: 8, corpus: 124 (12s ago), crashers: 37, restarts: 1/15, execs: 35342 (2941/sec), cover: 403, uptime: 12s

The most important part of the output is the crashers and cover. The crashers records how many combinations were discovered that fail and the cover tells you how much code is being accessed. For a complete explanation of the output, please see: https://github.com/dvyukov/go-fuzz.

The fuzzer will document the crashers in a folder labeled "crashers." It will record the fragment and the error that was produced in two separate files within this folder. This is the final product.

Happy Fuzzing!

Documentation

Overview

Package roaring implements roaring bitmaps with support for incremental changes.

Index

Constants

View Source 
const (
	// MagicNumber is an identifier, in bytes 0-1 of the file.
	MagicNumber = uint32(12348)

	MaxContainerVal = 0xffff
)
View Source 
const (
	ContainerNil    byte = iota // no container
	ContainerArray              // slice of bit position values
	ContainerBitmap             // slice of 1024 uint64s
	ContainerRun                // container of run-encoded bits
)
View Source 
const ArrayMaxSize = 4096

ArrayMaxSize represents the maximum size of array containers.

Variables

View Source 
var ContainerArchetypeNames = []string{
	"Empty",
	"Ary1",
	"Ary16",
	"Ary256",
	"Ary512",
	"Ary1024",
	"Ary4096",
	"RunFull",
	"RunSplit",
	"Run16",
	"Run16Small",
	"Run256",
	"Run256Small",
	"Run1024",
	"BM512",
	"BM1024",
	"BM4096",
	"BM4097",
	"BM32768",
	"BM65000",
}

ContainerArchetypeNames is the list of supported container archetypes used in some testing. This is exported for use in a benchmark-analysis tool.

View Source 
var NewFileBitmap = NewBTreeBitmap

NewFileBitmap returns a Bitmap with an initial set of values, used for file storage.

Functions

func ArrayCountRange added in v2.2.0 

func ArrayCountRange(array []uint16, start, end int32) (n int32)

func AsArray added in v2.2.0 

func AsArray(c *Container) []uint16

func AsBitmap added in v2.2.0 

func AsBitmap(c *Container) []uint64

func BinSearchRuns added in v2.2.0 

func BinSearchRuns(v uint16, a []Interval16) (int32, bool)

BinSearchRuns returns the index of the run containing v, and true, when v is contained; or the index of the next run starting after v, and false, when v is not contained.

func BitmapCountRange added in v2.2.0 

func BitmapCountRange(bitmap []uint64, start, end int32) int32

func BitmapsToRoaring 

func BitmapsToRoaring(bitmaps []*Bitmap) []byte

BitmapsToRoaring renders a series of non-overlapping bitmaps as a unified roaring file.

func CompareBitmapMap 

func CompareBitmapMap(b *Bitmap, vals map[uint64]struct{}) (bool, error)

CompareBitmapMap checks whether a bitmap has the same values in it that a provided map[uint64]struct{} has as keys.

func CompareBitmapSlice 

func CompareBitmapSlice(b *Bitmap, vals []uint64) (bool, error)

CompareBitmapSlice checks whether a bitmap has the same values in it that a provided slice does.

func ContainerType added in v2.2.0 

func ContainerType(c *Container) byte

func InitContainerArchetypes added in v2.3.0 

func InitContainerArchetypes() ([][]*Container, error)

InitContainerArchetypes ensures that createContainerArchetypes has been called, and returns the results of that one call.

func IntersectionAny added in v2.3.0 

func IntersectionAny(a, b *Container) bool

IntersectionAny checks whether two containers have any overlap without counting past the first bit found.

func IntersectionCount added in v2.4.0 

func IntersectionCount(x, y *Container) int32

func Merge added in v2.2.0 

func Merge(a, b []uint16)

func NewSliceContainers added in v2.2.0 

func NewSliceContainers() *sliceContainers

func RunCountRange added in v2.2.0 

func RunCountRange(runs []Interval16, start, end int32) (n int32)

RunCountRange returns the ranged bit count for RLE pairs.

Types

type AdvisoryError 

type AdvisoryError interface {
	error
	AdvisoryOnly()
}

AdvisoryError is used for the special case where we probably want to *report* an error reading a file, but don't want to actually count the file as not being read. For instance, a partial ops-log entry is *probably* harmless; we probably crashed while writing (?) and as such didn't report the write as successful. We hope.

type Bitmap 

type Bitmap struct {
	Containers Containers
	Source     Source

	// User-defined flags.
	Flags byte

	// Writer where operations are appended to.
	OpWriter io.Writer
	// contains filtered or unexported fields
}

Bitmap represents a roaring bitmap.

func Add added in v2.4.0 

func Add(x, y []*Bitmap) []*Bitmap

Add two BSI bitmaps producing a new BSI bitmap.

func InspectBinary 

func InspectBinary(data []byte, mapped bool, info *BitmapInfo) (b *Bitmap, mappedAny bool, err error)

InspectBinary reads a roaring bitmap, plus a possible ops log, and reports back on the contents, including distinguishing between the original ops log and the post-ops-log contents.

func NewBTreeBitmap 

func NewBTreeBitmap(a ...uint64) *Bitmap

func NewBitmap 

func NewBitmap(a ...uint64) *Bitmap

NewBitmap returns a Bitmap with an initial set of values.

func NewSliceBitmap 

func NewSliceBitmap(a ...uint64) *Bitmap

NewSliceBitmap makes a new bitmap, explicitly selecting the slice containers type, which performs better in cases where we expect a contiguous block of containers added in ascending order, such as when extracting a range from another bitmap.

func RoaringToBitmaps 

func RoaringToBitmaps(data []byte, shardWidth uint64) ([]*Bitmap, []uint64)

RoaringToBitmaps yields a series of bitmaps with specified shard keys, based on a single roaring file, with splits at multiples of shardWidth, which should be a multiple of container size.

func (*Bitmap) Add 

func (b *Bitmap) Add(a ...uint64) (changed bool, err error)

Add adds values to the bitmap. TODO(2.0) deprecate - use the more general AddN (though be aware that it modifies 'a' in place).

func (*Bitmap) AddN 

func (b *Bitmap) AddN(a ...uint64) (changed int, err error)

AddN adds values to the bitmap, appending them all to the op log in a batched write. It returns the number of changed bits. The input slice may be reordered, and the set of changed bits will end up in a[:changed].

func (*Bitmap) Any 

func (b *Bitmap) Any() bool

Any checks whether there are any set bits within the bitmap.

func (*Bitmap) BitwiseEqual 

func (b *Bitmap) BitwiseEqual(c *Bitmap) (bool, error)

BitwiseEqual is used mostly in test cases to confirm that two bitmaps came out the same. It does not expect corresponding opN, or OpWriter, but expects identical bit contents. It does not expect identical representations; a bitmap container can be identical to an array container. It returns a boolean value, and also an explanation for a false value.

func (*Bitmap) Check 

func (b *Bitmap) Check() error

Check performs a consistency check on the bitmap. Returns nil if consistent.

func (*Bitmap) Clone 

func (b *Bitmap) Clone() *Bitmap

Clone returns a heap allocated copy of the bitmap. Note: The OpWriter IS NOT copied to the new bitmap.

func (*Bitmap) Contains 

func (b *Bitmap) Contains(v uint64) bool

Contains returns true if v is in the bitmap.

func (*Bitmap) Count 

func (b *Bitmap) Count() (n uint64)

Count returns the number of bits set in the bitmap.

func (*Bitmap) CountRange 

func (b *Bitmap) CountRange(start, end uint64) (n uint64)

CountRange returns the number of bits set between [start, end).

func (*Bitmap) Difference 

func (b *Bitmap) Difference(other ...*Bitmap) *Bitmap

Difference returns the difference of b and other.

func (*Bitmap) DifferenceInPlace 

func (b *Bitmap) DifferenceInPlace(others ...*Bitmap)

DifferenceInPlace returns the bitwise difference of b and others, modifying b in place.

func (*Bitmap) DirectAdd 

func (b *Bitmap) DirectAdd(v uint64) bool

DirectAdd adds a value to the bitmap by bypassing the op log. TODO(2.0) deprecate in favor of DirectAddN.

func (*Bitmap) DirectAddN 

func (b *Bitmap) DirectAddN(a ...uint64) (changed int)

DirectAddN sets multiple bits in the bitmap, returning how many changed. It modifies the slice 'a' in place such that once it's complete a[:changed] will be list of changed bits. It is more efficient than repeated calls to DirectAdd for semi-dense sorted data because it reuses the container from the previous value if the new value has the same highbits instead of looking it up each time. TODO: if Containers implementations cached the last few Container objects returned from calls like Get and GetOrCreate, this optimization would be less useful.

func (*Bitmap) DirectRemoveN 

func (b *Bitmap) DirectRemoveN(a ...uint64) (changed int)

DirectRemoveN behaves analgously to DirectAddN.

func (*Bitmap) Flip 

func (b *Bitmap) Flip(start, end uint64) *Bitmap

Flip performs a logical negate of the bits in the range [start,end].

func (*Bitmap) ForEach 

func (b *Bitmap) ForEach(fn func(uint64) error) error

ForEach executes fn for each value in the bitmap.

func (*Bitmap) ForEachRange 

func (b *Bitmap) ForEachRange(start, end uint64, fn func(uint64) error) error

ForEachRange executes fn for each value in the bitmap between [start, end).

func (*Bitmap) Freeze 

func (b *Bitmap) Freeze() *Bitmap

Freeze returns a shallow copy of the bitmap. The new bitmap is a distinct bitmap, with a new Containers object, but the actual containers it holds are the same as the parent's containers, but have been frozen.

func (*Bitmap) ImportRoaringBits 

func (b *Bitmap) ImportRoaringBits(data []byte, clear bool, log bool, rowSize uint64) (changed int, rowSet map[uint64]int, err error)

ImportRoaringBits sets-or-clears bits based on a provided Roaring bitmap. This should be equivalent to unmarshalling the bitmap, then executing either `b = Union(b, newB)` or `b = Difference(b, newB)`, but with lower overhead. The log parameter controls whether to write to the op log; the answer should always be yes, except if you're calling using this to apply the op log.

If rowSize is non-zero, we should return a map of rows we altered, where "rows" are sets of rowSize containers. Otherwise the map isn't used. (This allows ImportRoaring to update caches; see fragment.go.)

func (*Bitmap) ImportRoaringRawIterator added in v2.2.0 

func (b *Bitmap) ImportRoaringRawIterator(itr RoaringIterator, clear bool, log bool, rowSize uint64) (changed int, rowSet map[uint64]int, err error)

func (*Bitmap) Info 

func (b *Bitmap) Info(includeContainers bool) BitmapInfo

Info returns stats for the bitmap.

func (*Bitmap) Intersect 

func (b *Bitmap) Intersect(other *Bitmap) *Bitmap

Intersect returns the intersection of b and other.

func (*Bitmap) IntersectInPlace 

func (b *Bitmap) IntersectInPlace(others ...*Bitmap)

IntersectInPlace returns the bitwise intersection of b and others, modifying b in place.

func (*Bitmap) IntersectionCount 

func (b *Bitmap) IntersectionCount(other *Bitmap) uint64

IntersectionCount returns the number of set bits that would result in an intersection between b and other. It is more efficient than actually intersecting the two and counting the result.

func (*Bitmap) Iterator 

func (b *Bitmap) Iterator() *Iterator

Iterator returns a new iterator for the bitmap.

func (*Bitmap) IteratorAt 

func (b *Bitmap) IteratorAt(start uint64) *Iterator

func (*Bitmap) Max 

func (b *Bitmap) Max() uint64

Max returns the highest value in the bitmap. Returns zero if the bitmap is empty.

func (*Bitmap) Min 

func (b *Bitmap) Min() (uint64, bool)

Min returns the lowest value in the bitmap. Second return value is true if containers exist in the bitmap.

func (*Bitmap) MinAt 

func (b *Bitmap) MinAt(start uint64) (uint64, bool)

MinAt returns the lowest value in the bitmap at least equal to its argument. Second return value is true if containers exist in the bitmap.

func (*Bitmap) OffsetRange 

func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap

OffsetRange returns a new bitmap with a containers offset by start. The containers themselves are shared, so they get frozen so it will be safe to interact with them.

func (*Bitmap) Ops 

func (b *Bitmap) Ops() (ops int, opN int)

Ops returns the number of write ops the bitmap is aware of in its ops log, and their total bit count.

func (*Bitmap) Optimize 

func (b *Bitmap) Optimize()

Optimize converts array and bitmap containers to run containers as necessary.

func (*Bitmap) PreferMapping 

func (b *Bitmap) PreferMapping(preferred bool)

func (*Bitmap) Put added in v2.2.0 

func (b *Bitmap) Put(key uint64, c *Container)

func (*Bitmap) RemapRoaringStorage 

func (b *Bitmap) RemapRoaringStorage(data []byte) (mappedAny bool, returnErr error)

RemapRoaringStorage tries to update all containers to refer to the roaring bitmap in the provided []byte. If any containers are marked as mapped, but do not match the provided storage, they will be unmapped. The boolean return indicates whether or not any containers were mapped to the given storage.

Regardless, after this function runs, no containers have mapped storage which does not refer to data; either they got mapped to the new storage, or storage was allocated for them.

func (*Bitmap) Remove 

func (b *Bitmap) Remove(a ...uint64) (changed bool, err error)

Remove removes values from the bitmap (writing to the op log if available). TODO(2.0) deprecate - use the more general RemoveN (though be aware that it modifies 'a' in place).

func (*Bitmap) RemoveN 

func (b *Bitmap) RemoveN(a ...uint64) (changed int, err error)

RemoveN behaves analagously to AddN.

func (*Bitmap) SanityCheckMapping 

func (b *Bitmap) SanityCheckMapping(from, to uintptr) (mappedIn int64, mappedOut int64, unmappedIn int64, errs int, err error)

SanityCheckMapping is a debugging function which checks whether containers are *correctly* recorded as mapped or unmapped.

func (*Bitmap) SetOps 

func (b *Bitmap) SetOps(ops int, opN int)

SetOps lets us reset the operation count in the weird case where we know we've changed an underlying file, without actually refreshing the bitmap.

func (*Bitmap) SetSource 

func (b *Bitmap) SetSource(s Source)

SetSource tells the bitmap what source to associate with new things it creates. This is possibly logically incorrect.

func (*Bitmap) Shift 

func (b *Bitmap) Shift(n int) (*Bitmap, error)

Shift shifts the contents of b by 1.

NOTE: This method is unsupported. See the `Shift()` method on `Row` in `row.go`.

func (*Bitmap) Size 

func (b *Bitmap) Size() int

Size returns the number of bytes required for the bitmap.

func (*Bitmap) Slice 

func (b *Bitmap) Slice() []uint64

Slice returns a slice of all integers in the bitmap.

func (*Bitmap) SliceRange 

func (b *Bitmap) SliceRange(start, end uint64) []uint64

SliceRange returns a slice of integers between [start, end).

func (*Bitmap) Union 

func (b *Bitmap) Union(others ...*Bitmap) *Bitmap

Union returns the bitwise union of b and others as a new bitmap.

func (*Bitmap) UnionInPlace 

func (b *Bitmap) UnionInPlace(others ...*Bitmap)

UnionInPlace returns the bitwise union of b and others, modifying b in place.

func (*Bitmap) UnmarshalBinary 

func (b *Bitmap) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary reads Pilosa's format, or upstream roaring (mostly; it may not handle some edge cases), and decodes them into the given bitmap, replacing the existing contents.

func (*Bitmap) WriteTo 

func (b *Bitmap) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes b to w.

func (*Bitmap) Xor 

func (b *Bitmap) Xor(other *Bitmap) *Bitmap

Xor returns the bitwise exclusive or of b and other.

type BitmapInfo 

type BitmapInfo struct {
	OpN            int
	Ops            int
	OpDetails      []OpInfo `json:"OpDetails,omitempty"`
	BitCount       uint64
	ContainerCount int
	Containers     []ContainerInfo `json:"Containers,omitempty"`   // The containers found in the bitmap originally
	OpContainers   []ContainerInfo `json:"OpContainers,omitempty"` // The containers resulting from ops log changes.
	From, To       uintptr         // if set, indicates the address range used when unpacking
}

BitmapInfo represents a point-in-time snapshot of bitmap stats.

type BitmapIteratorFinder added in v2.2.0 

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

func (*BitmapIteratorFinder) Close added in v2.2.0 

func (bif *BitmapIteratorFinder) Close()

func (*BitmapIteratorFinder) FindIterator added in v2.2.0 

func (bif *BitmapIteratorFinder) FindIterator(seek uint64) (ContainerIterator, bool)

type Container 

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

Container represents a Container for uint16 integers.

These are used for storing the low bits of numbers in larger sets of uint64. The high bits are stored in a Container's key which is tracked by a separate data structure. Integers in a Container can be encoded in one of three ways - the encoding used is usually whichever is most compact, though any Container type should be able to encode any set of integers safely. For containers with less than 4,096 values, an array is often used. Containers with long runs of integers would use run length encoding, and more random data usually uses bitmap encoding.

The Container type has somewhat magical semantics. Containers can be marked as "frozen" by the Freeze method, after which, nothing should ever modify that specific container object again, no matter what. Because of this, but also sometimes for Even More Esoteric Reasons, *no* container method should ever be assumed to be genuinely modifying the container it was called on, and *every* container method that might modify a container should return the "modified" *Container, which *may point to a different object*. The caller should always use this resulting container, and if you're storing a *Container in a data structure, you need to update the data structure's pointer too.

A nil *Container is a valid empty container.

In general, operations on containers which produce new containers *may* yield new containers, and *may* yield their operands.

The reason for all of this is to allow containers to have copy-on-write semantics, which allow us to reduce memory usage dramatically, and GC load even more dramatically.

func ConvertArrayToBitmap added in v2.2.0 

func ConvertArrayToBitmap(c *Container) *Container

func ConvertRunToBitmap added in v2.2.0 

func ConvertRunToBitmap(c *Container) *Container

func Difference added in v2.2.0 

func Difference(a, b *Container) *Container

func NewContainer 

func NewContainer() *Container

NewContainer returns a new instance of container. This trivial function may later become more interesting.

func NewContainerArray 

func NewContainerArray(set []uint16) *Container

NewContainerArray returns an array container using the provided set of values. It's okay if the slice is nil; that's a length of zero.

func NewContainerArrayCopy 

func NewContainerArrayCopy(set []uint16) *Container

NewContainerArrayCopy returns an array container using the provided set of values. It's okay if the slice is nil; that's a length of zero. It copies the provided slice to new storage.

func NewContainerArrayN 

func NewContainerArrayN(set []uint16, n int32) *Container

NewContainerArrayN returns an array container using the specified set of values, but overriding n. This is deprecated. It never worked in the first place. The provided value of n is ignored and instead derived from the set length.

func NewContainerBitmap 

func NewContainerBitmap(n int, bitmap []uint64) *Container

NewContainerBitmap makes a bitmap container using the provided bitmap, or an empty one if provided bitmap is nil. If the provided bitmap is too short, it will be padded. This function's API is wrong; it should have been written as NewContainerBitmapN, and this should not take the n argument, but I did it wrong initially and now that would be a breaking change.

func NewContainerBitmapN 

func NewContainerBitmapN(bitmap []uint64, n int32) *Container

NewContainerBitmapN makes a bitmap container using the provided bitmap, or an empty one if provided bitmap is nil. If the provided bitmap is too short, it will be padded. The container's count is specified directly.

func NewContainerRun 

func NewContainerRun(set []Interval16) *Container

NewContainerRun creates a new run container using a provided (possibly nil) slice of intervals.

func NewContainerRunCopy 

func NewContainerRunCopy(set []Interval16) *Container

NewContainerRunCopy creates a new run container using a provided (possibly nil) slice of intervals. It copies the provided slice to new storage.

func NewContainerRunN 

func NewContainerRunN(set []Interval16, n int32) *Container

NewContainerRunN creates a new run array using a provided (possibly nil) slice of intervals. It overrides n using the provided value.

func Optimize added in v2.2.0 

func Optimize(c *Container) *Container

Optimize yields a container with the same bits as c, but adjusted to the smallest-storage type by Roaring rules (thus, runs where that's smaller, otherwise arrays for N < 4096 and bitmaps for N >= 4096).

func Union added in v2.2.0 

func Union(a, b *Container) (c *Container)

func (*Container) Add added in v2.2.0 

func (c *Container) Add(v uint16) (newC *Container, added bool)

Add yields a container identical to c, but with the given bit set; added is true if the bit wasn't previously set. It is unspecified whether the original container is modified.

func (*Container) AsBitmap 

func (c *Container) AsBitmap(target []uint64) (out []uint64)

AsBitmap yields a 65k-bit bitmap, storing it in the target if a target is provided. The target should be zeroed, or this becomes an implicit union.

func (*Container) BitwiseCompare 

func (c *Container) BitwiseCompare(c2 *Container) error

BitwiseCompare reports whether two containers are equal. It returns an error describing any difference it finds. This is mostly intended for use in tests that expect equality.

func (*Container) CheckN added in v2.3.0 

func (c *Container) CheckN()

CheckN verifies that a container's cached count is correct, but there are two versions; this is the one which doesn't actually do anything, because the check is expensive. Which one you get is controlled by the roaringparanoia build tag.

func (*Container) Clone 

func (c *Container) Clone() (out *Container)

Clone returns a copy of c.

func (*Container) Contains 

func (c *Container) Contains(v uint16) bool

Contains returns true if v is in the container.

func (*Container) CountRange added in v2.2.0 

func (c *Container) CountRange(start, end int32) (n int32)

func (*Container) Difference added in v2.2.0 

func (c *Container) Difference(other *Container) *Container

func (*Container) Freeze 

func (c *Container) Freeze() *Container

Freeze returns an unmodifiable container identical to c. This might be c, now marked unmodifiable, or might be a new container. If c is currently marked as "mapped", referring to a backing store that's not a conventional Go pointer, the storage may (or may not) be copied. Do not call Freeze on a temporarily-corrupt container, such as one returned from UnionInPlace but on which you haven't since called Repair.

func (*Container) Mapped 

func (c *Container) Mapped() bool

Mapped returns the internal mapped field, which indicates whether the slice's backing store is believed to be associated with unwriteable mmapped space.

func (*Container) Max added in v2.2.0 

func (c *Container) Max() uint16

func (*Container) N 

func (c *Container) N() int32

N returns the 1-count of the container.

func (*Container) Remove added in v2.2.0 

func (c *Container) Remove(v uint16) (c2 *Container, removed bool)

Add yields a container identical to c, but with the given bit cleared; removed is true if the bit was previously set. It is unspecified whether the original container is modified.

func (*Container) Repair 

func (c *Container) Repair()

Repair repairs the cardinality of c if it has been corrupted by optimized operations.

func (*Container) SafeN added in v2.2.0 

func (c *Container) SafeN() (int32, bool)

SafeN returns N, true if it can, otherwise it returns 0, false. For instance, a container subject to in-place operations can not know its current N, and it's not meaningful or safe to query it until a repair, so you can use this to get N "if it's available".

func (*Container) SetMapped added in v2.2.0 

func (c *Container) SetMapped(mapped bool)

SetMapped marks a container as "mapped"; do this if you're setting a container's storage to something that it shouldn't write to, like mmapped memory.

func (*Container) String 

func (c *Container) String() string

func (*Container) Thaw 

func (c *Container) Thaw() *Container

Thaw returns a modifiable container identical to c. This may be c, or it may be a new container with distinct backing store.

func (*Container) UnionInPlace added in v2.2.0 

func (c *Container) UnionInPlace(other *Container) (r *Container)

UnionInPlace yields a container containing all the bits set in either c or other. It may, or may not, modify c. The resulting container's count, as returned by c.N(), may be incorrect; see (*Container).Repair(). Do not freeze a container produced by this operation before repairing it.

func (*Container) WriteTo 

func (c *Container) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes c to w.

type ContainerInfo 

type ContainerInfo struct {
	Key     uint64  // container key
	Type    string  // container type (array, bitmap, or run)
	Flags   string  // flag state
	N       int32   // number of bits
	Alloc   int     // memory used
	Pointer uintptr // address
	Mapped  bool    // whether this container thinks it is mmapped
}

ContainerInfo represents a point-in-time snapshot of container stats.

type ContainerIterator 

type ContainerIterator interface {
	Next() bool
	Value() (uint64, *Container)
	Close()
}

type Containers 

type Containers interface {
	// Get returns nil if the key does not exist.
	Get(key uint64) *Container

	// Put adds the container at key.
	Put(key uint64, c *Container)

	// Remove takes the container at key out.
	Remove(key uint64)

	// GetOrCreate returns the container at key, creating a new empty container if necessary.
	GetOrCreate(key uint64) *Container

	// Clone does a deep copy of Containers, including cloning all containers contained.
	Clone() Containers

	// Freeze creates a shallow copy of Containers, freezing all the containers
	// contained. The new copy is a distinct Containers, but the individual containers
	// are shared (but marked as frozen).
	Freeze() Containers

	// Last returns the highest key and associated container.
	Last() (key uint64, c *Container)

	// Size returns the number of containers stored.
	Size() int

	// Update calls fn (existing-container, existed), and expects
	// (new-container, write). If write is true, the container is used to
	// replace the given container.
	Update(key uint64, fn func(*Container, bool) (*Container, bool))

	// UpdateEvery calls fn (existing-container, existed), and expects
	// (new-container, write). If write is true, the container is used to
	// replace the given container.
	UpdateEvery(fn func(uint64, *Container, bool) (*Container, bool))

	// Iterator returns a ContainterIterator which after a call to Next(), a call to Value() will
	// return the first container at or after key. found will be true if a
	// container is found at key.
	Iterator(key uint64) (citer ContainerIterator, found bool)

	Count() uint64

	// Reset clears the containers collection to allow for recycling during snapshot
	Reset()
	// ResetN clears the collection but hints at a needed size.
	ResetN(int)

	// Repair will repair the cardinality of any containers whose cardinality were corrupted
	// due to optimized operations.
	Repair()
}

type ErrorList 

type ErrorList []error

ErrorList represents a list of errors.

func (*ErrorList) Append 

func (a *ErrorList) Append(err error)

Append appends an error to the list. If err is an ErrorList then all errors are appended.

func (*ErrorList) AppendWithPrefix 

func (a *ErrorList) AppendWithPrefix(err error, prefix string)

AppendWithPrefix appends an error to the list and includes a prefix.

func (ErrorList) Error 

func (a ErrorList) Error() string

type FileShouldBeTruncatedError 

type FileShouldBeTruncatedError interface {
	AdvisoryError
	SuggestedLength() int64
}

type Interval16 added in v2.2.0 

type Interval16 struct {
	Start uint16
	Last  uint16
}

func AsRuns added in v2.2.0 

func AsRuns(c *Container) []Interval16

type Iterator 

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

Iterator represents an iterator over a Bitmap.

func NewIterator added in v2.2.0 

func NewIterator(f IteratorFinder) *Iterator

NewIterator requires f as an IteratorFinder, it will crash if f is nil.

func (*Iterator) Close added in v2.2.0 

func (itr *Iterator) Close()

func (*Iterator) Next 

func (itr *Iterator) Next() (v uint64, eof bool)

Next returns the next value in the bitmap. Returns eof as true if there are no values left in the iterator.

func (*Iterator) Seek 

func (itr *Iterator) Seek(seek uint64)

Seek moves to the first value equal to or greater than `seek`.

type IteratorFinder added in v2.2.0 

type IteratorFinder interface {
	FindIterator(uint64) (ContainerIterator, bool)
	Close()
}

type OpInfo 

type OpInfo struct {
	Type string
	OpN  int
	Size int
}

OpInfo is a description of an op.

type RoaringIterator added in v2.2.0 

type RoaringIterator interface {
	// Len reports the number of containers total.
	Len() (count int64)
	// Next yields the information about the next container
	Next() (key uint64, cType byte, n int, length int, pointer *uint16, err error)
	// Remaining yields the bytes left over past the end of the roaring data,
	// which is typically an ops log in our case, and also its offset in case
	// we need to talk about truncation.
	Remaining() ([]byte, int64)

	// NextContainer is a helper that is used in place of Next(). It will
	// allocate a Container from the output of its internal call to Next(),
	// and return the key and container rc. If Next returns an error, then
	// NextContainer will return 0, nil.
	NextContainer() (key uint64, rc *Container)

	// Data returns the underlying data, esp for the Ops log.
	Data() []byte

	// Clone copies the iterator, preserving it at this point in the iteration.
	// It may well share much underlying data.
	Clone() RoaringIterator
}

RoaringIterator represents something which can iterate through a roaring bitmap and yield information about containers, including type, size, and the location of their data structures.

func NewRoaringIterator added in v2.2.0 

func NewRoaringIterator(data []byte) (RoaringIterator, error)

type Source 

type Source interface {
	ID() string
	Dead() bool
}

A Source represents the source a given bitmap gets its data from, such as a memory-mapped file. When combining bitmaps, we might track them together in a single combined-source of some sort.

func MergeSources 

func MergeSources(sources ...Source) Source

MergeSources combines sources. If you have two bitmaps, and you're combining them, then the combination's source is a combination of those two sources.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.