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.
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.
18 nonces := make([]uint64, 0, numNonces)
19 for i := 0; i < numNonces; i++ {
20 nonces = append(nonces, uint64(i))
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},
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])
45 // Ensure the limited number of most recent entries in the list
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])
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,
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
71 // This check needs at least 2 entries.
73 origLruIndex := numNonces - test.limit
74 mruNonceMap.Add(nonces[origLruIndex])
76 mruNonceMap.Add(uint64(numNonces) + 1)
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])
86 // Ensure the entry that should've become the new lru
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])
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])
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
116 // Create new mru nonce map and add the nonces.
117 mruNonceMap := newMruNonceMap(uint(2))
118 mruNonceMap.Add(nonce1)
119 mruNonceMap.Add(nonce2)
121 // Ensure the stringer gives the expected result. Since map iteration
122 // is not ordered, either entry could be first, so account for both
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)
133 // BenchmarkMruNonceList performs basic benchmarks on the most recently used
135 func BenchmarkMruNonceList(b *testing.B) {
136 // Create a bunch of fake nonces to use in benchmarking the mru nonce
140 nonces := make([]uint64, 0, numNonces)
141 for i := 0; i < numNonces; i++ {
142 nonces = append(nonces, uint64(i))
146 // Benchmark the add plus evicition code.
148 mruNonceMap := newMruNonceMap(uint(limit))
149 for i := 0; i < b.N; i++ {
150 mruNonceMap.Add(nonces[i%numNonces])