vendor/github.com/hashicorp/golang-lru/lru_test.go

   1 package lru
   2
   3 import (
   4         "math/rand"
   5         "testing"
   6 )
   7
   8 func BenchmarkLRU_Rand(b *testing.B) {
   9         l, err := New(8192)
  10         if err != nil {
  11                 b.Fatalf("err: %v", err)
  12         }
  13
  14         trace := make([]int64, b.N*2)
  15         for i := 0; i < b.N*2; i++ {
  16                 trace[i] = rand.Int63() % 32768
  17         }
  18
  19         b.ResetTimer()
  20
  21         var hit, miss int
  22         for i := 0; i < 2*b.N; i++ {
  23                 if i%2 == 0 {
  24                         l.Add(trace[i], trace[i])
  25                 } else {
  26                         _, ok := l.Get(trace[i])
  27                         if ok {
  28                                 hit++
  29                         } else {
  30                                 miss++
  31                         }
  32                 }
  33         }
  34         b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss))
  35 }
  36
  37 func BenchmarkLRU_Freq(b *testing.B) {
  38         l, err := New(8192)
  39         if err != nil {
  40                 b.Fatalf("err: %v", err)
  41         }
  42
  43         trace := make([]int64, b.N*2)
  44         for i := 0; i < b.N*2; i++ {
  45                 if i%2 == 0 {
  46                         trace[i] = rand.Int63() % 16384
  47                 } else {
  48                         trace[i] = rand.Int63() % 32768
  49                 }
  50         }
  51
  52         b.ResetTimer()
  53
  54         for i := 0; i < b.N; i++ {
  55                 l.Add(trace[i], trace[i])
  56         }
  57         var hit, miss int
  58         for i := 0; i < b.N; i++ {
  59                 _, ok := l.Get(trace[i])
  60                 if ok {
  61                         hit++
  62                 } else {
  63                         miss++
  64                 }
  65         }
  66         b.Logf("hit: %d miss: %d ratio: %f", hit, miss, float64(hit)/float64(miss))
  67 }
  68
  69 func TestLRU(t *testing.T) {
  70         evictCounter := 0
  71         onEvicted := func(k interface{}, v interface{}) {
  72                 if k != v {
  73                         t.Fatalf("Evict values not equal (%v!=%v)", k, v)
  74                 }
  75                 evictCounter++
  76         }
  77         l, err := NewWithEvict(128, onEvicted)
  78         if err != nil {
  79                 t.Fatalf("err: %v", err)
  80         }
  81
  82         for i := 0; i < 256; i++ {
  83                 l.Add(i, i)
  84         }
  85         if l.Len() != 128 {
  86                 t.Fatalf("bad len: %v", l.Len())
  87         }
  88
  89         if evictCounter != 128 {
  90                 t.Fatalf("bad evict count: %v", evictCounter)
  91         }
  92
  93         for i, k := range l.Keys() {
  94                 if v, ok := l.Get(k); !ok || v != k || v != i+128 {
  95                         t.Fatalf("bad key: %v", k)
  96                 }
  97         }
  98         for i := 0; i < 128; i++ {
  99                 _, ok := l.Get(i)
 100                 if ok {
 101                         t.Fatalf("should be evicted")
 102                 }
 103         }
 104         for i := 128; i < 256; i++ {
 105                 _, ok := l.Get(i)
 106                 if !ok {
 107                         t.Fatalf("should not be evicted")
 108                 }
 109         }
 110         for i := 128; i < 192; i++ {
 111                 l.Remove(i)
 112                 _, ok := l.Get(i)
 113                 if ok {
 114                         t.Fatalf("should be deleted")
 115                 }
 116         }
 117
 118         l.Get(192) // expect 192 to be last key in l.Keys()
 119
 120         for i, k := range l.Keys() {
 121                 if (i < 63 && k != i+193) || (i == 63 && k != 192) {
 122                         t.Fatalf("out of order key: %v", k)
 123                 }
 124         }
 125
 126         l.Purge()
 127         if l.Len() != 0 {
 128                 t.Fatalf("bad len: %v", l.Len())
 129         }
 130         if _, ok := l.Get(200); ok {
 131                 t.Fatalf("should contain nothing")
 132         }
 133 }
 134
 135 // test that Add returns true/false if an eviction occurred
 136 func TestLRUAdd(t *testing.T) {
 137         evictCounter := 0
 138         onEvicted := func(k interface{}, v interface{}) {
 139                 evictCounter++
 140         }
 141
 142         l, err := NewWithEvict(1, onEvicted)
 143         if err != nil {
 144                 t.Fatalf("err: %v", err)
 145         }
 146
 147         if l.Add(1, 1) == true || evictCounter != 0 {
 148                 t.Errorf("should not have an eviction")
 149         }
 150         if l.Add(2, 2) == false || evictCounter != 1 {
 151                 t.Errorf("should have an eviction")
 152         }
 153 }
 154
 155 // test that Contains doesn't update recent-ness
 156 func TestLRUContains(t *testing.T) {
 157         l, err := New(2)
 158         if err != nil {
 159                 t.Fatalf("err: %v", err)
 160         }
 161
 162         l.Add(1, 1)
 163         l.Add(2, 2)
 164         if !l.Contains(1) {
 165                 t.Errorf("1 should be contained")
 166         }
 167
 168         l.Add(3, 3)
 169         if l.Contains(1) {
 170                 t.Errorf("Contains should not have updated recent-ness of 1")
 171         }
 172 }
 173
 174 // test that Contains doesn't update recent-ness
 175 func TestLRUContainsOrAdd(t *testing.T) {
 176         l, err := New(2)
 177         if err != nil {
 178                 t.Fatalf("err: %v", err)
 179         }
 180
 181         l.Add(1, 1)
 182         l.Add(2, 2)
 183         contains, evict := l.ContainsOrAdd(1, 1)
 184         if !contains {
 185                 t.Errorf("1 should be contained")
 186         }
 187         if evict {
 188                 t.Errorf("nothing should be evicted here")
 189         }
 190
 191         l.Add(3, 3)
 192         contains, evict = l.ContainsOrAdd(1, 1)
 193         if contains {
 194                 t.Errorf("1 should not have been contained")
 195         }
 196         if !evict {
 197                 t.Errorf("an eviction should have occurred")
 198         }
 199         if !l.Contains(1) {
 200                 t.Errorf("now 1 should be contained")
 201         }
 202 }
 203
 204 // test that Peek doesn't update recent-ness
 205 func TestLRUPeek(t *testing.T) {
 206         l, err := New(2)
 207         if err != nil {
 208                 t.Fatalf("err: %v", err)
 209         }
 210
 211         l.Add(1, 1)
 212         l.Add(2, 2)
 213         if v, ok := l.Peek(1); !ok || v != 1 {
 214                 t.Errorf("1 should be set to 1: %v, %v", v, ok)
 215         }
 216
 217         l.Add(3, 3)
 218         if l.Contains(1) {
 219                 t.Errorf("should not have updated recent-ness of 1")
 220         }
 221 }