The highest tagged major version is
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
- Variables
- type Bitmap
- func (b *Bitmap) Add(a ...uint64) (changed bool, err error)
- func (b *Bitmap) AddN(a ...uint64) (changed int, err error)
- func (b *Bitmap) Any() bool
- func (b *Bitmap) BitwiseEqual(c *Bitmap) (bool, error)
- func (b *Bitmap) Check() error
- func (b *Bitmap) Clone() *Bitmap
- func (b *Bitmap) Contains(v uint64) bool
- func (b *Bitmap) Count() (n uint64)
- func (b *Bitmap) CountRange(start, end uint64) (n uint64)
- func (b *Bitmap) Difference(other *Bitmap) *Bitmap
- func (b *Bitmap) DirectAdd(v uint64) bool
- func (b *Bitmap) DirectAddN(a ...uint64) (changed int)
- func (b *Bitmap) DirectRemoveN(a ...uint64) (changed int)
- func (b *Bitmap) Flip(start, end uint64) *Bitmap
- func (b *Bitmap) ForEach(fn func(uint64))
- func (b *Bitmap) ForEachRange(start, end uint64, fn func(uint64))
- func (b *Bitmap) Freeze() *Bitmap
- func (b *Bitmap) ImportRoaringBits(data []byte, clear bool, log bool, rowSize uint64) (changed int, rowSet map[uint64]int, err error)
- func (b *Bitmap) Info() bitmapInfo
- func (b *Bitmap) Intersect(other *Bitmap) *Bitmap
- func (b *Bitmap) IntersectionCount(other *Bitmap) uint64
- func (b *Bitmap) Iterator() *Iterator
- func (b *Bitmap) Max() uint64
- func (b *Bitmap) Min() (uint64, bool)
- func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap
- func (b *Bitmap) Ops() (ops int, opN int)
- func (b *Bitmap) Optimize()
- func (b *Bitmap) PreferMapping(preferred bool)
- func (b *Bitmap) RemapRoaringStorage(data []byte) (mappedAny bool, returnErr error)
- func (b *Bitmap) Remove(a ...uint64) (changed bool, err error)
- func (b *Bitmap) RemoveN(a ...uint64) (changed int, err error)
- func (b *Bitmap) SetOps(ops int, opN int)
- func (b *Bitmap) Shift(n int) (*Bitmap, error)
- func (b *Bitmap) Size() int
- func (b *Bitmap) Slice() []uint64
- func (b *Bitmap) SliceRange(start, end uint64) []uint64
- func (b *Bitmap) Union(others ...*Bitmap) *Bitmap
- func (b *Bitmap) UnionInPlace(others ...*Bitmap)
- func (b *Bitmap) UnmarshalBinary(data []byte) error
- func (b *Bitmap) WriteTo(w io.Writer) (n int64, err error)
- func (b *Bitmap) Xor(other *Bitmap) *Bitmap
- type Container
- func NewContainer() *Container
- func NewContainerArray(set []uint16) *Container
- func NewContainerArrayCopy(set []uint16) *Container
- func NewContainerArrayN(set []uint16, n int32) *Container
- func NewContainerBitmap(n int, bitmap []uint64) *Container
- func NewContainerBitmapN(bitmap []uint64, n int32) *Container
- func NewContainerRun(set []interval16) *Container
- func NewContainerRunCopy(set []interval16) *Container
- func NewContainerRunN(set []interval16, n int32) *Container
- func (c *Container) Clone() (out *Container)
- func (c *Container) Contains(v uint16) bool
- func (c *Container) Freeze() *Container
- func (c *Container) Mapped() bool
- func (c *Container) N() int32
- func (c *Container) Repair()
- func (c *Container) String() string
- func (c *Container) Thaw() *Container
- func (c *Container) Update(typ byte, n int32, mapped bool)
- func (c *Container) UpdateOrMake(typ byte, n int32, mapped bool) *Container
- func (c *Container) WriteTo(w io.Writer) (n int64, err error)
- type ContainerIterator
- type Containers
- type ErrorList
- type Iterator
Constants ¶
const ArrayMaxSize = 4096
ArrayMaxSize represents the maximum size of array containers.
const ( // MagicNumber is an identifier, in bytes 0-1 of the file. MagicNumber = uint32(12348) )
Variables ¶
var NewFileBitmap func(a ...uint64) *Bitmap = NewBTreeBitmap
NewFileBitmap returns a Bitmap with an initial set of values, used for file storage. By default, this is a copy of NewBitmap, but is replaced with B+Tree in server/enterprise.go
Functions ¶
This section is empty.
Types ¶
type Bitmap ¶
type Bitmap struct {
Containers Containers
// 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 NewBTreeBitmap ¶ added in v1.3.0
func NewSliceBitmap ¶ added in v1.4.0
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 (*Bitmap) Add ¶
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 ¶ added in v1.3.0
AddN adds values to the bitmap, appending them all to the op log in a batched write. It returns the number of changed bits.
func (*Bitmap) BitwiseEqual ¶ added in v1.4.0
CompareEquality 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) Clone ¶
Clone returns a heap allocated copy of the bitmap. Note: The OpWriter IS NOT copied to the new bitmap.
func (*Bitmap) CountRange ¶
CountRange returns the number of bits set between [start, end).
func (*Bitmap) Difference ¶
Difference returns the difference of b and other.
func (*Bitmap) DirectAdd ¶ added in v1.2.0
DirectAdd adds a value to the bitmap by bypassing the op log. TODO(2.0) deprecate in favor of DirectAddN.
func (*Bitmap) DirectAddN ¶ added in v1.3.0
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 ¶ added in v1.3.0
DirectRemoveN behaves analgously to DirectAddN.
func (*Bitmap) Flip ¶ added in v0.4.0
Flip performs a logical negate of the bits in the range [start,end].
func (*Bitmap) ForEachRange ¶
ForEachRange executes fn for each value in the bitmap between [start, end).
func (*Bitmap) Freeze ¶ added in v1.4.0
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 ¶ added in v1.4.0
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) IntersectionCount ¶
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) Max ¶
Max returns the highest value in the bitmap. Returns zero if the bitmap is empty.
func (*Bitmap) Min ¶ added in v1.4.0
Min returns the lowest value in the bitmap. Second return value is true if containers exist in the bitmap.
func (*Bitmap) OffsetRange ¶
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 ¶ added in v1.4.0
Ops returns the number of write ops the bitmap is aware of in its ops log, and their total bit count.
func (*Bitmap) Optimize ¶ added in v0.6.0
func (b *Bitmap) Optimize()
Optimize converts array and bitmap containers to run containers as necessary.
func (*Bitmap) PreferMapping ¶ added in v1.4.0
func (*Bitmap) RemapRoaringStorage ¶ added in v1.4.0
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 ¶
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) SetOps ¶ added in v1.4.0
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) SliceRange ¶
SliceRange returns a slice of integers between [start, end).
func (*Bitmap) UnionInPlace ¶ added in v1.2.0
UnionInPlace returns the bitwise union of b and others, modifying b in place.
func (*Bitmap) UnmarshalBinary ¶
UnmarshalBinary decodes b from a binary-encoded byte slice. data can be in either official roaring format or Pilosa's roaring format.
type Container ¶ added in v0.10.0
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.
func NewContainer ¶ added in v0.10.0
func NewContainer() *Container
NewContainer returns a new instance of container. This trivial function may later become more interesting.
func NewContainerArray ¶ added in v1.3.0
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 ¶ added in v1.4.0
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 ¶ added in v1.4.0
NewContainerArrayN returns an array container using the specified set of values, but overriding n.
func NewContainerBitmap ¶ added in v1.3.0
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 ¶ added in v1.4.0
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 ¶ added in v1.3.0
func NewContainerRun(set []interval16) *Container
NewContainerRun creates a new run container using a provided (possibly nil) slice of intervals.
func NewContainerRunCopy ¶ added in v1.4.0
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 ¶ added in v1.4.0
NewContainerRunN creates a new run array using a provided (possibly nil) slice of intervals. It overrides n using the provided value.
func (*Container) Freeze ¶ added in v1.4.0
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 be copied.
func (*Container) Mapped ¶ added in v0.10.0
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) Repair ¶ added in v1.2.0
func (c *Container) Repair()
Repair repairs the cardinality of c if it has been corrupted by optimized operations.
func (*Container) Thaw ¶ added in v1.4.0
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) Update ¶ added in v0.10.0
Update updates the container if possible. It is an error to call Update on a frozen container.
func (*Container) UpdateOrMake ¶ added in v1.4.0
UpdateOrMake updates the container, yielding a new container if necessary.
type ContainerIterator ¶ added in v0.10.0
type Containers ¶ added in v0.10.0
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)
// PutContainerValues updates an existing container at key.
// If a container does not exist for key, a new one is allocated.
// TODO(2.0) make n int32
PutContainerValues(key uint64, typ byte, n int, mapped bool)
// 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 Contiterator 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 ¶
Append appends an error to the list. If err is an ErrorList then all errors are appended.
func (*ErrorList) AppendWithPrefix ¶
AppendWithPrefix appends an error to the list and includes a prefix.
Source Files