1 package peer
2 3 import (
4 "bytes"
5 "container/list"
6 "fmt"
7 "sync"
8 )
9 10 // mruNonceMap provides a concurrency safe map that is limited to a maximum number of items with eviction for the oldest
11 // entry when the limit is exceeded.
12 type mruNonceMap struct {
13 mtx sync.Mutex
14 nonceMap map[uint64]*list.Element // nearly O(1) lookups
15 nonceList *list.List // O(1) insert, update, delete
16 limit uint
17 }
18 19 // String returns the map as a human-readable string. This function is safe for concurrent access.
20 func (m *mruNonceMap) String() string {
21 m.mtx.Lock()
22 defer m.mtx.Unlock()
23 lastEntryNum := len(m.nonceMap) - 1
24 curEntry := 0
25 buf := bytes.NewBufferString("[")
26 for nonce := range m.nonceMap {
27 buf.WriteString(fmt.Sprintf("%d", nonce))
28 if curEntry < lastEntryNum {
29 buf.WriteString(", ")
30 }
31 curEntry++
32 }
33 buf.WriteString("]")
34 return fmt.Sprintf("<%d>%s", m.limit, buf.String())
35 }
36 37 // Exists returns whether or not the passed Nonce is in the map.
38 //
39 // This function is safe for concurrent access.
40 func (m *mruNonceMap) Exists(nonce uint64) bool {
41 m.mtx.Lock()
42 _, exists := m.nonceMap[nonce]
43 m.mtx.Unlock()
44 return exists
45 }
46 47 // Add adds the passed Nonce to the map and handles eviction of the oldest item if adding the new item would exceed the
48 // max limit. Adding an existing item makes it the most recently used item.
49 //
50 // This function is safe for concurrent access.
51 func (m *mruNonceMap) Add(nonce uint64) {
52 m.mtx.Lock()
53 defer m.mtx.Unlock()
54 // When the limit is zero, nothing can be added to the map, so just return.
55 if m.limit == 0 {
56 return
57 }
58 // When the entry already exists move it to the front of the list thereby marking it most recently used.
59 if node, exists := m.nonceMap[nonce]; exists {
60 m.nonceList.MoveToFront(node)
61 return
62 }
63 // Evict the least recently used entry (back of the list) if the the new entry would exceed the size limit for the
64 // map. Also reuse the list node so a new one doesn't have to be allocated.
65 if uint(len(m.nonceMap))+1 > m.limit {
66 node := m.nonceList.Back()
67 lru := node.Value.(uint64)
68 // Evict least recently used item.
69 delete(m.nonceMap, lru)
70 // Reuse the list node of the item that was just evicted for the new item.
71 node.Value = nonce
72 m.nonceList.MoveToFront(node)
73 m.nonceMap[nonce] = node
74 return
75 }
76 // The limit hasn't been reached yet, so just add the new item.
77 node := m.nonceList.PushFront(nonce)
78 m.nonceMap[nonce] = node
79 }
80 81 // Delete deletes the passed Nonce from the map (if it exists).
82 //
83 // This function is safe for concurrent access.
84 func (m *mruNonceMap) Delete(nonce uint64) {
85 m.mtx.Lock()
86 if node, exists := m.nonceMap[nonce]; exists {
87 m.nonceList.Remove(node)
88 delete(m.nonceMap, nonce)
89 }
90 m.mtx.Unlock()
91 }
92 93 // newMruNonceMap returns a new Nonce map that is limited to the number of entries specified by limit. When the number
94 // of entries exceeds the limit, the oldest (least recently used) entry will be removed to make room for the new entry.
95 func newMruNonceMap(limit uint) *mruNonceMap {
96 m := mruNonceMap{
97 nonceMap: make(map[uint64]*list.Element),
98 nonceList: list.New(),
99 limit: limit,
100 }
101 return &m
102 }
103