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.
14 // mruNonceMap provides a concurrency safe map that is limited to a maximum
15 // number of items with eviction for the oldest entry when the limit is
17 type mruNonceMap struct {
19 nonceMap map[uint64]*list.Element // nearly O(1) lookups
20 nonceList *list.List // O(1) insert, update, delete
24 // String returns the map as a human-readable string.
26 // This function is safe for concurrent access.
27 func (m *mruNonceMap) String() string {
31 lastEntryNum := len(m.nonceMap) - 1
33 buf := bytes.NewBufferString("[")
34 for nonce := range m.nonceMap {
35 buf.WriteString(fmt.Sprintf("%d", nonce))
36 if curEntry < lastEntryNum {
43 return fmt.Sprintf("<%d>%s", m.limit, buf.String())
46 // Exists returns whether or not the passed nonce is in the map.
48 // This function is safe for concurrent access.
49 func (m *mruNonceMap) Exists(nonce uint64) bool {
51 _, exists := m.nonceMap[nonce]
57 // Add adds the passed nonce to the map and handles eviction of the oldest item
58 // if adding the new item would exceed the max limit. Adding an existing item
59 // makes it the most recently used item.
61 // This function is safe for concurrent access.
62 func (m *mruNonceMap) Add(nonce uint64) {
66 // When the limit is zero, nothing can be added to the map, so just
72 // When the entry already exists move it to the front of the list
73 // thereby marking it most recently used.
74 if node, exists := m.nonceMap[nonce]; exists {
75 m.nonceList.MoveToFront(node)
79 // Evict the least recently used entry (back of the list) if the the new
80 // entry would exceed the size limit for the map. Also reuse the list
81 // node so a new one doesn't have to be allocated.
82 if uint(len(m.nonceMap))+1 > m.limit {
83 node := m.nonceList.Back()
84 lru := node.Value.(uint64)
86 // Evict least recently used item.
87 delete(m.nonceMap, lru)
89 // Reuse the list node of the item that was just evicted for the
92 m.nonceList.MoveToFront(node)
93 m.nonceMap[nonce] = node
97 // The limit hasn't been reached yet, so just add the new item.
98 node := m.nonceList.PushFront(nonce)
99 m.nonceMap[nonce] = node
102 // Delete deletes the passed nonce from the map (if it exists).
104 // This function is safe for concurrent access.
105 func (m *mruNonceMap) Delete(nonce uint64) {
107 if node, exists := m.nonceMap[nonce]; exists {
108 m.nonceList.Remove(node)
109 delete(m.nonceMap, nonce)
114 // newMruNonceMap returns a new nonce map that is limited to the number of
115 // entries specified by limit. When the number of entries exceeds the limit,
116 // the oldest (least recently used) entry will be removed to make room for the
118 func newMruNonceMap(limit uint) *mruNonceMap {
120 nonceMap: make(map[uint64]*list.Element),
121 nonceList: list.New(),