rdv.go

Documentation: github.com/dgryski/go-rendezvous

     1  package rendezvous
     2  
     3  type Rendezvous struct {
     4  	nodes map[string]int
     5  	nstr  []string
     6  	nhash []uint64
     7  	hash  Hasher
     8  }
     9  
    10  type Hasher func(s string) uint64
    11  
    12  func New(nodes []string, hash Hasher) *Rendezvous {
    13  	r := &Rendezvous{
    14  		nodes: make(map[string]int, len(nodes)),
    15  		nstr:  make([]string, len(nodes)),
    16  		nhash: make([]uint64, len(nodes)),
    17  		hash:  hash,
    18  	}
    19  
    20  	for i, n := range nodes {
    21  		r.nodes[n] = i
    22  		r.nstr[i] = n
    23  		r.nhash[i] = hash(n)
    24  	}
    25  
    26  	return r
    27  }
    28  
    29  func (r *Rendezvous) Lookup(k string) string {
    30  	// short-circuit if we're empty
    31  	if len(r.nodes) == 0 {
    32  		return ""
    33  	}
    34  
    35  	khash := r.hash(k)
    36  
    37  	var midx int
    38  	var mhash = xorshiftMult64(khash ^ r.nhash[0])
    39  
    40  	for i, nhash := range r.nhash[1:] {
    41  		if h := xorshiftMult64(khash ^ nhash); h > mhash {
    42  			midx = i + 1
    43  			mhash = h
    44  		}
    45  	}
    46  
    47  	return r.nstr[midx]
    48  }
    49  
    50  func (r *Rendezvous) Add(node string) {
    51  	r.nodes[node] = len(r.nstr)
    52  	r.nstr = append(r.nstr, node)
    53  	r.nhash = append(r.nhash, r.hash(node))
    54  }
    55  
    56  func (r *Rendezvous) Remove(node string) {
    57  	// find index of node to remove
    58  	nidx := r.nodes[node]
    59  
    60  	// remove from the slices
    61  	l := len(r.nstr)
    62  	r.nstr[nidx] = r.nstr[l]
    63  	r.nstr = r.nstr[:l]
    64  
    65  	r.nhash[nidx] = r.nhash[l]
    66  	r.nhash = r.nhash[:l]
    67  
    68  	// update the map
    69  	delete(r.nodes, node)
    70  	moved := r.nstr[nidx]
    71  	r.nodes[moved] = nidx
    72  }
    73  
    74  func xorshiftMult64(x uint64) uint64 {
    75  	x ^= x >> 12 // a
    76  	x ^= x << 25 // b
    77  	x ^= x >> 27 // c
    78  	return x * 2685821657736338717
    79  }
    80
View as plain text