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
Constants ¶
const BitsPerWord = 64
BitsPerWord is the number of bits in a machine word.
const Log2BitsPerWord = uint(6)
Log2BitsPerWord is log_2(BitsPerWord).
Variables ¶
This section is empty.
Functions ¶
func ClearInterval ¶ added in v0.0.11
ClearInterval clears the bits at all positions in [startIdx, limitIdx) in a []uintptr bitset.
func NewClearBits ¶ added in v0.0.11
NewClearBits creates a []uintptr bitset with capacity for at least nBit bits, and all bits clear.
func NewSetBits ¶ added in v0.0.11
NewSetBits creates a []uintptr bitset with capacity for at least nBit bits, and all bits at positions [0, nBit) set.
func SetInterval ¶ added in v0.0.11
SetInterval sets the bits at all positions in [startIdx, limitIdx) in a []uintptr bitset.
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.
Source Files