Struct BitArray

postgres/parser/utils/bitarray.go:57–88

BitArray implements a bit string of arbitrary length. This uses a packed encoding (i.e. groups of 64 bits at a time) for memory efficiency and speed of bitwise operations (enables use of full machine registers for comparisons and logical operations), akin to the big.nat type. There is something fa

// For portability, the size of the backing word is guaranteed to be 64
// bits.
type BitArray struct {
	// words is the backing array.
	//
	// The leftmost bits in the literal representation are placed in the
	// MSB of each word.
	//
	// The last word contain the rightmost bits in the literal
	// representation, right-padded. For example if there are 3 bits
	// to store, the 3 MSB bits of the last word will be set and the
	// remaining LSB bits will be set to zero.
	//
	// The number of stored bits is actually:
	//   0 if lastBitsUsed = 0  or len(word) == 0
	//   otherwise, (len(words)-1)*numBitsPerWord + lastBitsUsed
	//
	// TODO(jutin, nathan): consider using the trick in bytes.Buffer of
	// keeping a static [1]word which word can initially point to to
	// avoid heap allocations in the common case of small arrays.
	words []word

	// lastBitsUsed is the number of bits in the last word that
	// participate in the value stored. It can only be zero
	// for empty bit arrays; otherwise it's always between 1 and
	// numBitsPerWord.
	//
	// For example:
	// - 0 bits in array: len(words) == 0, lastBitsUsed = 0
	// - 1 bits in array: len(words) == 1, lastBitsUsed = 1
	// - 64 bits in array: len(words) == 1, lastBitsUsed = 64
	// - 65 bits in array: len(words) == 2, lastBitsUsed = 1
	lastBitsUsed uint8
}

type word = uint64