bitset

README

bitset

NOTE: This is a fork/vendoring of http://github.com/jrick/bitset for Decred

bitset is a package providing efficient bitset implementations for Go.

Documentation

[] (http://godoc.org/github.com/jrick/bitset)

Full go doc style documentation for the project can be viewed online without installing this package by using the GoDoc site here: http://godoc.org/github.com/jrick/bitset

You can also view the documentation locally once the package is installed with the godoc tool by running godoc -http=":6060" and pointing your browser to http://localhost:6060/pkg/github.com/jrick/bitset

Installation

$ go get github.com/jrick/bitset

License

bitset is licensed under the liberal ISC license.

Documentation

Overview

Package bitset provides bitset implementations for bit packing binary values into pointers and bytes.

A bitset, while logically equivalent to a []bool, is often preferable over a []bool due to the space and time efficiency of bit packing binary values. They are typically more space efficient than a []bool since (although implementation specifc) bools are typically byte size. Using a bitset in place of a []bool can therefore result in at least an 8x reduction in memory usage. While bitsets introduce bitshifting overhead for gets and sets unnecessary for a []bool, they may still more performant than a []bool due to the smaller data structure being more cache friendly.

This package contains three bitset implementations: Pointers for efficiency, Bytes for situations where bitsets must be serialized or deserialized, and Sparse for when memory efficiency is the most important factor when working with sparse datasets.

Index

• type BitSet
• type Bytes
  • func NewBytes(numBits int) Bytes
  • func (s Bytes) Get(i int) bool
  • func (s *Bytes) Grow(numBits int)
  • func (s Bytes) Set(i int)
  • func (s Bytes) SetBool(i int, b bool)
  • func (s Bytes) Unset(i int)
• type Pointers
  • func NewPointers(numBits int) Pointers
  • func (p Pointers) Get(i int) bool
  • func (p *Pointers) Grow(numBits int)
  • func (p Pointers) Set(i int)
  • func (p Pointers) SetBool(i int, b bool)
  • func (p Pointers) Unset(i int)
• type Sparse
  • func (s Sparse) Get(i int) bool
  • func (s Sparse) Set(i int)
  • func (s Sparse) SetBool(i int, b bool)
  • func (s Sparse) Unset(i int)

Types

type BitSet

type BitSet interface {
	Get(i int) bool
	Set(i int)
	Unset(i int)
	SetBool(i int, b bool)
}

BitSet defines the method set of a bitset. Bitsets allow for bit packing of binary values to pointers or bytes for space and time efficiency.

The Grow methods of Pointers and Bytes are not part of this interface.

type Bytes

type Bytes []byte

Bytes represents a bitset backed by a bytes slice. Bytes bitsets, while designed for efficiency, are slightly less efficient to use than Pointers bitsets, since pointer-sized data is faster to manipulate. However, Bytes have the nice property of easily and portably being (de)serialized to or from an io.Reader or io.Writer. Like a Pointers, Bytes bitsets do not automatically grow for indexed values outside of the allocated range. The Grow method is provided if it is necessary to grow a Bytes bitset beyond its initial allocation.

The len of a Bytes is the number of bytes in the set. Multiplying by eight will result in the number of bits the set can hold.

func NewBytes

func NewBytes(numBits int) Bytes

NewBytes returns a new bitset that is capable of holding numBits number of binary values. All bytes in the bitset are zeroed and each bit is therefore considered unset.

func (Bytes) Get

func (s Bytes) Get(i int) bool

Get returns whether the bit at index i is set or not. This method will panic if the index results in a byte index that exceeds the number of bytes held by the bitset.

func (*Bytes) Grow

func (s *Bytes) Grow(numBits int)

Grow ensures that the bitset s is large enough to hold numBits number of bits, potentially appending to and/or reallocating the slice if the current length is not sufficient.

func (Bytes) Set

func (s Bytes) Set(i int)

Set sets the bit at index i. This method will panic if the index results in a byte index that exceeds the number of a bytes held by the bitset.

func (Bytes) SetBool

func (s Bytes) SetBool(i int, b bool)

SetBool sets or unsets the bit at index i depending on the value of b. This method will panic if the index results in a byte index that exceeds the nubmer of bytes held by the bitset.

func (Bytes) Unset

func (s Bytes) Unset(i int)

Unset unsets the bit at index i. This method will panc if the index results in a byte index that exceeds the number of bytes held by the bitset.

type Pointers

type Pointers []uintptr

Pointers represents a bitset backed by a uintptr slice. Pointers bitsets are designed for efficiency and do not automatically grow for indexed values outside of the allocated range. The Grow method is provided if it is necessary to grow a Pointers bitset beyond its initial allocation.

The len of a Pointers is the number of pointers in the set. Multiplying by the machine pointer size will result in the number of bits the set can hold.

func NewPointers

func NewPointers(numBits int) Pointers

NewPointers returns a new bitset that is capable of holding numBits number of binary values. All pointers in the bitset are zeroed and each bit is therefore considered unset.

func (Pointers) Get

func (p Pointers) Get(i int) bool

Get returns whether the bit at index i is set or not. This method will panic if the index results in a pointer index that exceeds the number of pointers held by the bitset.

func (*Pointers) Grow

func (p *Pointers) Grow(numBits int)

Grow ensures that the bitset w is large enough to hold numBits number of bits, potentially appending to and/or reallocating the slice if the current length is not sufficient.

func (Pointers) Set

func (p Pointers) Set(i int)

Set sets the bit at index i. This method will panic if the index results in a pointer index that exceeds the number of pointers held by the bitset.

func (Pointers) SetBool

func (p Pointers) SetBool(i int, b bool)

SetBool sets or unsets the bit at index i depending on the value of b. This method will panic if the index results in a pointer index that exceeds the number of pointers held by the bitset.

func (Pointers) Unset

func (p Pointers) Unset(i int)

Unset unsets the bit at index i. This method will panic if the index results in a pointer index that exceeds the number of pointers held by the bitset.

type Sparse

type Sparse map[int]uintptr

Sparse is a memory efficient bitset for sparsly-distributed set bits. Unlike a Pointers or Bytes which requires each pointer or byte between 0 and the highest index to be allocated, a Sparse only holds the pointers which contain set bits. Additionally, Sparse is the only BitSet implementation from this package which will dynamically expand and shrink as bits are set and unset.

As the map is unordered and there is no obvious way to (de)serialize this structure, no byte implementation is provided, and all map values are machine pointer-sized.

As Sparse bitsets are backed by a map, getting and setting bits are orders of magnitude slower than other slice-backed bitsets and should only be used with sparse datasets and when memory efficiency is a top concern. It is highly recommended to benchmark this type against the other bitsets using realistic sample data before using this type in an application.

New Sparse bitsets can be created using the builtin make function.

func (Sparse) Get

func (s Sparse) Get(i int) bool

Get returns whether the bit at index i is set or not.

func (Sparse) Set

func (s Sparse) Set(i int)

Set sets the bit at index i. A map insert is performed if if no bits of the associated pointer have been previously set.

func (Sparse) SetBool

func (s Sparse) SetBool(i int, b bool)

SetBool sets the bit at index i if b is true, otherwise the bit is unset. see the comments for the get and set methods for the memory allocation rules that are followed when getting or setting bits in a Sparse bitset.

func (Sparse) Unset

func (s Sparse) Unset(i int)

Unset unsets the bit at index i. If all bits for a given pointer have are unset, the pointer is removed from the map, and future calls to Get will return false for all bits from this pointer.