vendor/github.com/btcsuite/btcd/peer/mruinvmap.go

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