base: github.com/grailbio/base/bitset Index | Files

package bitset

import "github.com/grailbio/base/bitset"

Package bitset provides support for treating a []uintptr as a bitset. It's essentially a less-abstracted variant of github.com/willf/bitset.

Index

Package Files

bitset_amd64.go doc.go

Constants

const BitsPerWord = 64

BitsPerWord is the number of bits in a machine word.

func Clear Uses

func Clear(data []uintptr, bitIdx int)

Clear clears the given bit in a []uintptr bitset.

func Set Uses

func Set(data []uintptr, bitIdx int)

Set sets the given bit in a []uintptr bitset.

func Test Uses

func Test(data []uintptr, bitIdx int) bool

Test returns true iff the given bit is set.

type NonzeroWordScanner Uses

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

NonzeroWordScanner iterates over and clears the set bits in a bitset, with the somewhat unusual precondition that the number of nonzero words is known in advance. The 'BitsetScanner' name is being reserved for a scanner which expects the number of set bits to be known instead.

Note that, when many bits are set, a more complicated double-loop based around a function like willf/bitset.NextSetMany() has ~40% less overhead (at least with Go 1.10 on a Mac), and you can do even better with manual inlining of the iteration logic. As a consequence, it shouldn't be used when the bit iteration/clearing process is actually the dominant computational cost (and neither should NextSetMany(), manual inlining is 2-6x better without much more code, see bitsetManualInlineSubtask() in bitset_test.go for an example). However, it's a good choice everywhere else, outperforming the other scanners I'm aware of with similar ease of use, and maybe a future Go version will inline it properly.

func NewNonzeroWordScanner Uses

func NewNonzeroWordScanner(data []uintptr, nNonzeroWord int) (NonzeroWordScanner, int)

NewNonzeroWordScanner returns a NonzeroWordScanner for the given bitset, along with the position of the first bit. (This interface has been chosen to make for loops with properly-scoped variables easy to write.)

The bitset is expected to be nonempty; otherwise this will crash the program with an out-of-bounds slice access. Similarly, if nNonzeroWord is larger than the actual number of nonzero words, or initially <= 0, the standard for loop will crash the program. (If nNonzeroWord is smaller but >0, the last nonzero words will be ignored.)

func (*NonzeroWordScanner) Next Uses

func (s *NonzeroWordScanner) Next() int

Next returns the position of the next set bit, or -1 if there aren't any.

Package bitset imports 1 packages (graph) and is imported by 1 packages. Updated 2018-10-17. Refresh now. Tools for package owners.