vendor/github.com/btcsuite/btcd/peer/mrunoncemap_test.go

   1 // Copyright (c) 2015 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package peer
   6
   7 import (
   8         "fmt"
   9         "testing"
  10 )
  11
  12 // TestMruNonceMap ensures the mruNonceMap behaves as expected including
  13 // limiting, eviction of least-recently used entries, specific entry removal,
  14 // and existence tests.
  15 func TestMruNonceMap(t *testing.T) {
  16         // Create a bunch of fake nonces to use in testing the mru nonce code.
  17         numNonces := 10
  18         nonces := make([]uint64, 0, numNonces)
  19         for i := 0; i < numNonces; i++ {
  20                 nonces = append(nonces, uint64(i))
  21         }
  22
  23         tests := []struct {
  24                 name  string
  25                 limit int
  26         }{
  27                 {name: "limit 0", limit: 0},
  28                 {name: "limit 1", limit: 1},
  29                 {name: "limit 5", limit: 5},
  30                 {name: "limit 7", limit: 7},
  31                 {name: "limit one less than available", limit: numNonces - 1},
  32                 {name: "limit all available", limit: numNonces},
  33         }
  34
  35 testLoop:
  36         for i, test := range tests {
  37                 // Create a new mru nonce map limited by the specified test
  38                 // limit and add all of the test nonces.  This will cause
  39                 // evicition since there are more test nonces than the limits.
  40                 mruNonceMap := newMruNonceMap(uint(test.limit))
  41                 for j := 0; j < numNonces; j++ {
  42                         mruNonceMap.Add(nonces[j])
  43                 }
  44
  45                 // Ensure the limited number of most recent entries in the list
  46                 // exist.
  47                 for j := numNonces - test.limit; j < numNonces; j++ {
  48                         if !mruNonceMap.Exists(nonces[j]) {
  49                                 t.Errorf("Exists #%d (%s) entry %d does not "+
  50                                         "exist", i, test.name, nonces[j])
  51                                 continue testLoop
  52                         }
  53                 }
  54
  55                 // Ensure the entries before the limited number of most recent
  56                 // entries in the list do not exist.
  57                 for j := 0; j < numNonces-test.limit; j++ {
  58                         if mruNonceMap.Exists(nonces[j]) {
  59                                 t.Errorf("Exists #%d (%s) entry %d exists", i,
  60                                         test.name, nonces[j])
  61                                 continue testLoop
  62                         }
  63                 }
  64
  65                 // Readd the entry that should currently be the least-recently
  66                 // used entry so it becomes the most-recently used entry, then
  67                 // force an eviction by adding an entry that doesn't exist and
  68                 // ensure the evicted entry is the new least-recently used
  69                 // entry.
  70                 //
  71                 // This check needs at least 2 entries.
  72                 if test.limit > 1 {
  73                         origLruIndex := numNonces - test.limit
  74                         mruNonceMap.Add(nonces[origLruIndex])
  75
  76                         mruNonceMap.Add(uint64(numNonces) + 1)
  77
  78                         // Ensure the original lru entry still exists since it
  79                         // was updated and should've have become the mru entry.
  80                         if !mruNonceMap.Exists(nonces[origLruIndex]) {
  81                                 t.Errorf("MRU #%d (%s) entry %d does not exist",
  82                                         i, test.name, nonces[origLruIndex])
  83                                 continue testLoop
  84                         }
  85
  86                         // Ensure the entry that should've become the new lru
  87                         // entry was evicted.
  88                         newLruIndex := origLruIndex + 1
  89                         if mruNonceMap.Exists(nonces[newLruIndex]) {
  90                                 t.Errorf("MRU #%d (%s) entry %d exists", i,
  91                                         test.name, nonces[newLruIndex])
  92                                 continue testLoop
  93                         }
  94                 }
  95
  96                 // Delete all of the entries in the list, including those that
  97                 // don't exist in the map, and ensure they no longer exist.
  98                 for j := 0; j < numNonces; j++ {
  99                         mruNonceMap.Delete(nonces[j])
 100                         if mruNonceMap.Exists(nonces[j]) {
 101                                 t.Errorf("Delete #%d (%s) entry %d exists", i,
 102                                         test.name, nonces[j])
 103                                 continue testLoop
 104                         }
 105                 }
 106         }
 107 }
 108
 109 // TestMruNonceMapStringer tests the stringized output for the mruNonceMap type.
 110 func TestMruNonceMapStringer(t *testing.T) {
 111         // Create a couple of fake nonces to use in testing the mru nonce
 112         // stringer code.
 113         nonce1 := uint64(10)
 114         nonce2 := uint64(20)
 115
 116         // Create new mru nonce map and add the nonces.
 117         mruNonceMap := newMruNonceMap(uint(2))
 118         mruNonceMap.Add(nonce1)
 119         mruNonceMap.Add(nonce2)
 120
 121         // Ensure the stringer gives the expected result.  Since map iteration
 122         // is not ordered, either entry could be first, so account for both
 123         // cases.
 124         wantStr1 := fmt.Sprintf("<%d>[%d, %d]", 2, nonce1, nonce2)
 125         wantStr2 := fmt.Sprintf("<%d>[%d, %d]", 2, nonce2, nonce1)
 126         gotStr := mruNonceMap.String()
 127         if gotStr != wantStr1 && gotStr != wantStr2 {
 128                 t.Fatalf("unexpected string representation - got %q, want %q "+
 129                         "or %q", gotStr, wantStr1, wantStr2)
 130         }
 131 }
 132
 133 // BenchmarkMruNonceList performs basic benchmarks on the most recently used
 134 // nonce handling.
 135 func BenchmarkMruNonceList(b *testing.B) {
 136         // Create a bunch of fake nonces to use in benchmarking the mru nonce
 137         // code.
 138         b.StopTimer()
 139         numNonces := 100000
 140         nonces := make([]uint64, 0, numNonces)
 141         for i := 0; i < numNonces; i++ {
 142                 nonces = append(nonces, uint64(i))
 143         }
 144         b.StartTimer()
 145
 146         // Benchmark the add plus evicition code.
 147         limit := 20000
 148         mruNonceMap := newMruNonceMap(uint(limit))
 149         for i := 0; i < b.N; i++ {
 150                 mruNonceMap.Add(nonces[i%numNonces])
 151         }
 152 }