roaring

package
v0.10.0 Latest Latest
Warning

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

 Go to latest Published: May 15, 2018 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

Package roaring implements roaring bitmaps with support for incremental changes.

Index

Constants

View Source 
const (

	//ContainerArray indicates a container of bit position values
	ContainerArray = byte(1)

	//ContainerBitmap indicates a container of bits packed in a uint64 array block
	ContainerBitmap = byte(2)

	//ContainerRun  indicates a container of run encoded bits
	ContainerRun = byte(3)
)
View Source 
const ArrayMaxSize = 4096

ArrayMaxSize represents the maximum size of array containers.

View Source 
const RunMaxSize = 2048

RunMaxSize represents the maximum size of run length encoded containers.

Variables

View Source 
var NewFileBitmap func(a ...uint64) *Bitmap = NewBitmap

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

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

Bitmap represents a roaring bitmap.

func NewBitmap 

func NewBitmap(a ...uint64) *Bitmap

NewBitmap returns a Bitmap with an initial set of values.

func (*Bitmap) Add 

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

Add adds values to the bitmap.

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) Flip added in v0.4.0 

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))

ForEach executes fn for each value in the bitmap.

func (*Bitmap) ForEachRange 

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

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

func (*Bitmap) Info 

func (b *Bitmap) Info() 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) 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) Max 

func (b *Bitmap) Max() uint64

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

func (*Bitmap) OffsetRange 

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

OffsetRange returns a new bitmap with a containers offset by start.

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) Remove 

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

Remove removes values from 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(other *Bitmap) *Bitmap

Union returns the bitwise union of b and other.

func (*Bitmap) UnmarshalBinary 

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

UnmarshalBinary decodes b from a binary-encoded byte slice.

func (*Bitmap) WriteTo 

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

WriteTo writes b to w.

func (*Bitmap) Xor added in v0.4.0 

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

Xor returns the bitwise exclusive or of b and other.

type BitmapInfo 

type BitmapInfo struct {
	OpN        int
	Containers []ContainerInfo
}

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

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.

func (*Container) Clone added in v0.10.0 

func (c *Container) Clone() *Container

Clone returns a copy of c.

func (*Container) Mapped added in v0.10.0 

func (c *Container) Mapped() bool

Mapped returns true if the container is mapped directly to a byte slice

func (*Container) Optimize added in v0.10.0 

func (c *Container) Optimize()

Optimize converts the container to the type which will take up the least amount of space.

func (*Container) Update added in v0.10.0 

func (c *Container) Update(containerType byte, n int, mapped bool)

Update updates the container

func (*Container) WriteTo added in v0.10.0 

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)
	N       int            // number of bits
	Alloc   int            // memory used
	Pointer unsafe.Pointer // offset within the mmap
}

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

type ContainerIterator added in v0.10.0 

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

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.
	PutContainerValues(key uint64, containerType 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

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

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

	// 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)
}

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 Iterator 

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

Iterator represents an iterator over a Bitmap.

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 SliceContainers added in v0.10.0 

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

func NewSliceContainers added in v0.10.0 

func NewSliceContainers() *SliceContainers

func (*SliceContainers) Clone added in v0.10.0 

func (sc *SliceContainers) Clone() Containers

func (*SliceContainers) Get added in v0.10.0 

func (sc *SliceContainers) Get(key uint64) *Container

func (*SliceContainers) GetOrCreate added in v0.10.0 

func (sc *SliceContainers) GetOrCreate(key uint64) *Container

func (*SliceContainers) Iterator added in v0.10.0 

func (sc *SliceContainers) Iterator(key uint64) (citer ContainerIterator, found bool)

func (*SliceContainers) Last added in v0.10.0 

func (sc *SliceContainers) Last() (key uint64, c *Container)

func (*SliceContainers) Put added in v0.10.0 

func (sc *SliceContainers) Put(key uint64, c *Container)

func (*SliceContainers) PutContainerValues added in v0.10.0 

func (sc *SliceContainers) PutContainerValues(key uint64, containerType byte, n int, mapped bool)

func (*SliceContainers) Remove added in v0.10.0 

func (sc *SliceContainers) Remove(key uint64)

func (*SliceContainers) Size added in v0.10.0 

func (sc *SliceContainers) Size() int

type SliceIterator added in v0.10.0 

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

func (*SliceIterator) Next added in v0.10.0 

func (si *SliceIterator) Next() bool

func (*SliceIterator) Value added in v0.10.0 

func (si *SliceIterator) Value() (uint64, *Container)

Source Files

View all Source files

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.