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 ¶
const BitsPerWord = 64
BitsPerWord is the number of bits in a machine word.
Variables ¶
This section is empty.
Functions ¶
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.