swiss/bits.go at main · dolthub/swiss

This repository was archived by the owner on Mar 7, 2025. It is now read-only.

Repository navigation

History

// Licensed under the Apache License, Version 2.0 (the "License");

// you may not use this file except in compliance with the License.

// You may obtain a copy of the License at

// http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software

// distributed under the License is distributed on an "AS IS" BASIS,

// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

// See the License for the specific language governing permissions and

// limitations under the License.

//go:build !amd64 || nosimd

package swiss

import (

"math/bits"

"unsafe"

)

const (

groupSize = 8

maxAvgGroupLoad = 7

loBits uint64 = 0x0101010101010101

hiBits uint64 = 0x8080808080808080

)

type bitset uint64

func metaMatchH2(m *metadata, h h2) bitset {

// https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord

return hasZeroByte(castUint64(m) ^ (loBits * uint64(h)))

}

func metaMatchEmpty(m *metadata) bitset {

return hasZeroByte(castUint64(m) ^ hiBits)

}

func nextMatch(b *bitset) uint32 {

s := uint32(bits.TrailingZeros64(uint64(*b)))

*b &= ^(1 << s) // clear bit |s|

return s >> 3 // div by 8

}

func hasZeroByte(x uint64) bitset {

return bitset(((x - loBits) & ^(x)) & hiBits)

}

func castUint64(m *metadata) uint64 {

return *(*uint64)((unsafe.Pointer)(m))

}

FilesExpand file tree

bits.go

Latest commit

History

bits.go

File metadata and controls