lru.go

Documentation: github.com/syndtr/goleveldb/leveldb/cache

     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  	rn.remove()
   146  	r.used -= n.Size()
   147  	n.CacheData = nil
   148  	r.mu.Unlock()
   149  
   150  	rn.h.Release()
   151  }
   152  
   153  // NewLRU create a new LRU-cache.
   154  func NewLRU(capacity int) Cacher {
   155  	r := &lru{capacity: capacity}
   156  	r.reset()
   157  	return r
   158  }
   159
View as plain text