vendor/github.com/btcsuite/btcd/peer/mrunoncemap.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         "bytes"
   9         "container/list"
  10         "fmt"
  11         "sync"
  12 )
  13
  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
  16 // exceeded.
  17 type mruNonceMap struct {
  18         mtx       sync.Mutex
  19         nonceMap  map[uint64]*list.Element // nearly O(1) lookups
  20         nonceList *list.List               // O(1) insert, update, delete
  21         limit     uint
  22 }
  23
  24 // String returns the map as a human-readable string.
  25 //
  26 // This function is safe for concurrent access.
  27 func (m *mruNonceMap) String() string {
  28         m.mtx.Lock()
  29         defer m.mtx.Unlock()
  30
  31         lastEntryNum := len(m.nonceMap) - 1
  32         curEntry := 0
  33         buf := bytes.NewBufferString("[")
  34         for nonce := range m.nonceMap {
  35                 buf.WriteString(fmt.Sprintf("%d", nonce))
  36                 if curEntry < lastEntryNum {
  37                         buf.WriteString(", ")
  38                 }
  39                 curEntry++
  40         }
  41         buf.WriteString("]")
  42
  43         return fmt.Sprintf("<%d>%s", m.limit, buf.String())
  44 }
  45
  46 // Exists returns whether or not the passed nonce is in the map.
  47 //
  48 // This function is safe for concurrent access.
  49 func (m *mruNonceMap) Exists(nonce uint64) bool {
  50         m.mtx.Lock()
  51         _, exists := m.nonceMap[nonce]
  52         m.mtx.Unlock()
  53
  54         return exists
  55 }
  56
  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.
  60 //
  61 // This function is safe for concurrent access.
  62 func (m *mruNonceMap) Add(nonce uint64) {
  63         m.mtx.Lock()
  64         defer m.mtx.Unlock()
  65
  66         // When the limit is zero, nothing can be added to the map, so just
  67         // return.
  68         if m.limit == 0 {
  69                 return
  70         }
  71
  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)
  76                 return
  77         }
  78
  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)
  85
  86                 // Evict least recently used item.
  87                 delete(m.nonceMap, lru)
  88
  89                 // Reuse the list node of the item that was just evicted for the
  90                 // new item.
  91                 node.Value = nonce
  92                 m.nonceList.MoveToFront(node)
  93                 m.nonceMap[nonce] = node
  94                 return
  95         }
  96
  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
 100 }
 101
 102 // Delete deletes the passed nonce from the map (if it exists).
 103 //
 104 // This function is safe for concurrent access.
 105 func (m *mruNonceMap) Delete(nonce uint64) {
 106         m.mtx.Lock()
 107         if node, exists := m.nonceMap[nonce]; exists {
 108                 m.nonceList.Remove(node)
 109                 delete(m.nonceMap, nonce)
 110         }
 111         m.mtx.Unlock()
 112 }
 113
 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
 117 // new entry.
 118 func newMruNonceMap(limit uint) *mruNonceMap {
 119         m := mruNonceMap{
 120                 nonceMap:  make(map[uint64]*list.Element),
 121                 nonceList: list.New(),
 122                 limit:     limit,
 123         }
 124         return &m
 125 }