vendor/github.com/syndtr/goleveldb/leveldb/cache/lru.go

   1 // Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
   2 // All rights reserved.
   3 //
   4 // Use of this source code is governed by a BSD-style license that can be
   5 // found in the LICENSE file.
   6
   7 package cache
   8
   9 import (
  10         "sync"
  11         "unsafe"
  12 )
  13
  14 type lruNode struct {
  15         n   *Node
  16         h   *Handle
  17         ban bool
  18
  19         next, prev *lruNode
  20 }
  21
  22 func (n *lruNode) insert(at *lruNode) {
  23         x := at.next
  24         at.next = n
  25         n.prev = at
  26         n.next = x
  27         x.prev = n
  28 }
  29
  30 func (n *lruNode) remove() {
  31         if n.prev != nil {
  32                 n.prev.next = n.next
  33                 n.next.prev = n.prev
  34                 n.prev = nil
  35                 n.next = nil
  36         } else {
  37                 panic("BUG: removing removed node")
  38         }
  39 }
  40
  41 type lru struct {
  42         mu       sync.Mutex
  43         capacity int
  44         used     int
  45         recent   lruNode
  46 }
  47
  48 func (r *lru) reset() {
  49         r.recent.next = &r.recent
  50         r.recent.prev = &r.recent
  51         r.used = 0
  52 }
  53
  54 func (r *lru) Capacity() int {
  55         r.mu.Lock()
  56         defer r.mu.Unlock()
  57         return r.capacity
  58 }
  59
  60 func (r *lru) SetCapacity(capacity int) {
  61         var evicted []*lruNode
  62
  63         r.mu.Lock()
  64         r.capacity = capacity
  65         for r.used > r.capacity {
  66                 rn := r.recent.prev
  67                 if rn == nil {
  68                         panic("BUG: invalid LRU used or capacity counter")
  69                 }
  70                 rn.remove()
  71                 rn.n.CacheData = nil
  72                 r.used -= rn.n.Size()
  73                 evicted = append(evicted, rn)
  74         }
  75         r.mu.Unlock()
  76
  77         for _, rn := range evicted {
  78                 rn.h.Release()
  79         }
  80 }
  81
  82 func (r *lru) Promote(n *Node) {
  83         var evicted []*lruNode
  84
  85         r.mu.Lock()
  86         if n.CacheData == nil {
  87                 if n.Size() <= r.capacity {
  88                         rn := &lruNode{n: n, h: n.GetHandle()}
  89                         rn.insert(&r.recent)
  90                         n.CacheData = unsafe.Pointer(rn)
  91                         r.used += n.Size()
  92
  93                         for r.used > r.capacity {
  94                                 rn := r.recent.prev
  95                                 if rn == nil {
  96                                         panic("BUG: invalid LRU used or capacity counter")
  97                                 }
  98                                 rn.remove()
  99                                 rn.n.CacheData = nil
 100                                 r.used -= rn.n.Size()
 101                                 evicted = append(evicted, rn)
 102                         }
 103                 }
 104         } else {
 105                 rn := (*lruNode)(n.CacheData)
 106                 if !rn.ban {
 107                         rn.remove()
 108                         rn.insert(&r.recent)
 109                 }
 110         }
 111         r.mu.Unlock()
 112
 113         for _, rn := range evicted {
 114                 rn.h.Release()
 115         }
 116 }
 117
 118 func (r *lru) Ban(n *Node) {
 119         r.mu.Lock()
 120         if n.CacheData == nil {
 121                 n.CacheData = unsafe.Pointer(&lruNode{n: n, ban: true})
 122         } else {
 123                 rn := (*lruNode)(n.CacheData)
 124                 if !rn.ban {
 125                         rn.remove()
 126                         rn.ban = true
 127                         r.used -= rn.n.Size()
 128                         r.mu.Unlock()
 129
 130                         rn.h.Release()
 131                         rn.h = nil
 132                         return
 133                 }
 134         }
 135         r.mu.Unlock()
 136 }
 137
 138 func (r *lru) Evict(n *Node) {
 139         r.mu.Lock()
 140         rn := (*lruNode)(n.CacheData)
 141         if rn == nil || rn.ban {
 142                 r.mu.Unlock()
 143                 return
 144         }
 145         n.CacheData = nil
 146         r.mu.Unlock()
 147
 148         rn.h.Release()
 149 }
 150
 151 func (r *lru) EvictNS(ns uint64) {
 152         var evicted []*lruNode
 153
 154         r.mu.Lock()
 155         for e := r.recent.prev; e != &r.recent; {
 156                 rn := e
 157                 e = e.prev
 158                 if rn.n.NS() == ns {
 159                         rn.remove()
 160                         rn.n.CacheData = nil
 161                         r.used -= rn.n.Size()
 162                         evicted = append(evicted, rn)
 163                 }
 164         }
 165         r.mu.Unlock()
 166
 167         for _, rn := range evicted {
 168                 rn.h.Release()
 169         }
 170 }
 171
 172 func (r *lru) EvictAll() {
 173         r.mu.Lock()
 174         back := r.recent.prev
 175         for rn := back; rn != &r.recent; rn = rn.prev {
 176                 rn.n.CacheData = nil
 177         }
 178         r.reset()
 179         r.mu.Unlock()
 180
 181         for rn := back; rn != &r.recent; rn = rn.prev {
 182                 rn.h.Release()
 183         }
 184 }
 185
 186 func (r *lru) Close() error {
 187         return nil
 188 }
 189
 190 // NewLRU create a new LRU-cache.
 191 func NewLRU(capacity int) Cacher {
 192         r := &lru{capacity: capacity}
 193         r.reset()
 194         return r
 195 }