forked from nats-io/nats-server
/
rand_evict.go
43 lines (39 loc) · 901 Bytes
/
rand_evict.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Copyright 2012-2013 Apcera Inc. All rights reserved.
package hashmap
import (
"math/rand"
"time"
)
// We use init to setup the random number generator
func init() {
rand.Seed(time.Now().UnixNano())
}
// RemoveRandom can be used for a random policy eviction.
// This is stochastic but very fast and does not impede
// performance like LRU, LFU or even ARC based implementations.
func (h *HashMap) RemoveRandom() {
if h.used == 0 {
return
}
index := (rand.Int()) & int(h.msk)
// Walk forward til we find an entry
for i := index; i < len(h.bkts); i++ {
e := &h.bkts[i]
if *e != nil {
*e = (*e).next
h.used -= 1
return
}
}
// If we are here we hit end and did not remove anything,
// use the index and walk backwards.
for i := index; i >= 0; i-- {
e := &h.bkts[i]
if *e != nil {
*e = (*e).next
h.used -= 1
return
}
}
panic("Should not reach here..")
}