mirror of
https://github.com/featurebasedb/featurebase.git
synced 2026-09-12 15:51:01 +00:00
82a975fd2a
Turns out we sometimes modify returned nodes. Handle this better, but also fix up some cases where we were generating node lists we didn't really need to answer simple questions.
51 lines
1.6 KiB
Go
51 lines
1.6 KiB
Go
// Copyright 2017 Pilosa Corp.
|
|
//
|
|
// 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.
|
|
|
|
package topology
|
|
|
|
// Hasher represents an interface to hash integers into buckets.
|
|
type Hasher interface {
|
|
// Hashes the key into a number between [0,N).
|
|
Hash(key uint64, n int) int
|
|
Name() string
|
|
}
|
|
|
|
// Jmphasher represents an implementation of jmphash. Implements Hasher.
|
|
type Jmphasher struct{}
|
|
|
|
// Hash returns the integer hash for the given key.
|
|
func (h *Jmphasher) Hash(key uint64, n int) int {
|
|
b, j := int64(-1), int64(0)
|
|
for j < int64(n) {
|
|
b = j
|
|
key = key*uint64(2862933555777941757) + 1
|
|
j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
|
|
}
|
|
return int(b)
|
|
}
|
|
|
|
// Name returns the name of this hash.
|
|
func (h *Jmphasher) Name() string {
|
|
return "jump-hash"
|
|
}
|
|
|
|
// PrimaryNode yields the node that would be selected as the primary from
|
|
// a list, for a given ID. It assumes the list is already in the
|
|
// expected order, as from Noder.Nodes().
|
|
func PrimaryNode(nodes []*Node, hasher Hasher) *Node {
|
|
if len(nodes) == 0 {
|
|
return nil
|
|
}
|
|
return nodes[hasher.Hash(0, len(nodes))]
|
|
}
|