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