bitset

Documentation

Overview

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

Index

• Constants
• func Clear(data []uintptr, bitIdx int)
• func ClearInterval(data []uintptr, startIdx, limitIdx int)
• func NewClearBits(nBit int) []uintptr
• func NewSetBits(nBit int) []uintptr
• func Set(data []uintptr, bitIdx int)
• func SetInterval(data []uintptr, startIdx, limitIdx int)
• func Test(data []uintptr, bitIdx int) bool
• type NonzeroWordScanner
  • func NewNonzeroWordScanner(data []uintptr, nNonzeroWord int) (NonzeroWordScanner, int)
  • func (s *NonzeroWordScanner) Next() int

Constants

const BitsPerWord = 64

BitsPerWord is the number of bits in a machine word.

const Log2BitsPerWord = uint(6)

Log2BitsPerWord is log_2(BitsPerWord).

Functions

func Clear

func Clear(data []uintptr, bitIdx int)

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

func ClearInterval

func ClearInterval(data []uintptr, startIdx, limitIdx int)

ClearInterval clears the bits at all positions in [startIdx, limitIdx) in a []uintptr bitset.

func NewClearBits

func NewClearBits(nBit int) []uintptr

NewClearBits creates a []uintptr bitset with capacity for at least nBit bits, and all bits clear.

func NewSetBits

func NewSetBits(nBit int) []uintptr

NewSetBits creates a []uintptr bitset with capacity for at least nBit bits, and all bits at positions [0, nBit) set.

func Set

func Set(data []uintptr, bitIdx int)

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

func SetInterval

func SetInterval(data []uintptr, startIdx, limitIdx int)

SetInterval sets the bits at all positions in [startIdx, limitIdx) in a []uintptr bitset.

func Test

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

Test returns true iff the given bit is set.

Types

type NonzeroWordScanner

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

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

func (s *NonzeroWordScanner) Next() int

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