path: root/vendor/github.com/syndtr/goleveldb/leveldb/cache/lru.go

// 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
}