| // Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com> |
| // All rights reserved. |
| // |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| package cache |
| |
| import ( |
| "sync" |
| "unsafe" |
| ) |
| |
| type lruNode struct { |
| n *Node |
| h *Handle |
| ban bool |
| |
| next, prev *lruNode |
| } |
| |
| func (n *lruNode) insert(at *lruNode) { |
| x := at.next |
| at.next = n |
| n.prev = at |
| n.next = x |
| x.prev = n |
| } |
| |
| func (n *lruNode) remove() { |
| if n.prev != nil { |
| n.prev.next = n.next |
| n.next.prev = n.prev |
| n.prev = nil |
| n.next = nil |
| } else { |
| panic("BUG: removing removed node") |
| } |
| } |
| |
| type lru struct { |
| mu sync.Mutex |
| capacity int |
| used int |
| recent lruNode |
| } |
| |
| func (r *lru) reset() { |
| r.recent.next = &r.recent |
| r.recent.prev = &r.recent |
| r.used = 0 |
| } |
| |
| func (r *lru) Capacity() int { |
| r.mu.Lock() |
| defer r.mu.Unlock() |
| return r.capacity |
| } |
| |
| func (r *lru) SetCapacity(capacity int) { |
| var evicted []*lruNode |
| |
| r.mu.Lock() |
| r.capacity = capacity |
| for r.used > r.capacity { |
| rn := r.recent.prev |
| if rn == nil { |
| panic("BUG: invalid LRU used or capacity counter") |
| } |
| rn.remove() |
| rn.n.CacheData = nil |
| r.used -= rn.n.Size() |
| evicted = append(evicted, rn) |
| } |
| r.mu.Unlock() |
| |
| for _, rn := range evicted { |
| rn.h.Release() |
| } |
| } |
| |
| func (r *lru) Promote(n *Node) { |
| var evicted []*lruNode |
| |
| r.mu.Lock() |
| if n.CacheData == nil { |
| if n.Size() <= r.capacity { |
| rn := &lruNode{n: n, h: n.GetHandle()} |
| rn.insert(&r.recent) |
| n.CacheData = unsafe.Pointer(rn) |
| r.used += n.Size() |
| |
| for r.used > r.capacity { |
| rn := r.recent.prev |
| if rn == nil { |
| panic("BUG: invalid LRU used or capacity counter") |
| } |
| rn.remove() |
| rn.n.CacheData = nil |
| r.used -= rn.n.Size() |
| evicted = append(evicted, rn) |
| } |
| } |
| } else { |
| rn := (*lruNode)(n.CacheData) |
| if !rn.ban { |
| rn.remove() |
| rn.insert(&r.recent) |
| } |
| } |
| r.mu.Unlock() |
| |
| for _, rn := range evicted { |
| rn.h.Release() |
| } |
| } |
| |
| func (r *lru) Ban(n *Node) { |
| r.mu.Lock() |
| if n.CacheData == nil { |
| n.CacheData = unsafe.Pointer(&lruNode{n: n, ban: true}) |
| } else { |
| rn := (*lruNode)(n.CacheData) |
| if !rn.ban { |
| rn.remove() |
| rn.ban = true |
| r.used -= rn.n.Size() |
| r.mu.Unlock() |
| |
| rn.h.Release() |
| rn.h = nil |
| return |
| } |
| } |
| r.mu.Unlock() |
| } |
| |
| func (r *lru) Evict(n *Node) { |
| r.mu.Lock() |
| rn := (*lruNode)(n.CacheData) |
| if rn == nil || rn.ban { |
| r.mu.Unlock() |
| return |
| } |
| n.CacheData = nil |
| r.mu.Unlock() |
| |
| rn.h.Release() |
| } |
| |
| func (r *lru) EvictNS(ns uint64) { |
| var evicted []*lruNode |
| |
| r.mu.Lock() |
| for e := r.recent.prev; e != &r.recent; { |
| rn := e |
| e = e.prev |
| if rn.n.NS() == ns { |
| rn.remove() |
| rn.n.CacheData = nil |
| r.used -= rn.n.Size() |
| evicted = append(evicted, rn) |
| } |
| } |
| r.mu.Unlock() |
| |
| for _, rn := range evicted { |
| rn.h.Release() |
| } |
| } |
| |
| func (r *lru) EvictAll() { |
| r.mu.Lock() |
| back := r.recent.prev |
| for rn := back; rn != &r.recent; rn = rn.prev { |
| rn.n.CacheData = nil |
| } |
| r.reset() |
| r.mu.Unlock() |
| |
| for rn := back; rn != &r.recent; rn = rn.prev { |
| rn.h.Release() |
| } |
| } |
| |
| func (r *lru) Close() error { |
| return nil |
| } |
| |
| // NewLRU create a new LRU-cache. |
| func NewLRU(capacity int) Cacher { |
| r := &lru{capacity: capacity} |
| r.reset() |
| return r |
| } |