func (s *Shard) decrementTTLCount(n uint64) {
	if s.ttlCount-n > s.ttlCount {
		atomic.StoreUint64(&s.ttlCount, 0)
	} else {
		atomic.AddUint64(&s.ttlCount, ^uint64(n-1))
	}
	atomic.AddUint64(&s.counters.evictions, n)
}
decrementTTLCount decrements the Bicache.ttlCount
value by n. Even though these operations are atomic,
this method should only be called when the shard is locked
for other consistency reasons.
package bicache
import (
	"container/list"
	"context"
	"errors"
	"log"
	"math"
	"sort"
	"sync"
	"sync/atomic"
	"time"
	"github.com/jamiealquiza/bicache/v2/sll"
	"github.com/jamiealquiza/tachymeter"
)
type Bicache struct {
	shards     []*Shard
	autoEvict  bool
	ShardCount uint32
	Size       int
	paused     uint32
	done       context.CancelFunc
}
type Shard struct {
	sync.RWMutex
	cacheMap      map[string]*entry
	mfuCache      *sll.Sll
	mruCache      *sll.Sll
	mfuCap        uint
	mruCap        uint
	autoEvict     bool
	ttlCount      uint64
	ttlMap        map[string]time.Time
	counters      *counters
	nearestExpire time.Time
	noOverflow    bool
}
type counters struct {
	hits      uint64
	misses    uint64
	evictions uint64
	overflows uint64
}
type Config struct {
	MFUSize    uint
	MRUSize    uint
	AutoEvict  uint
	EvictLog   bool
	ShardCount int
	NoOverflow bool
}
type entry struct {
	node  *sll.Node
	state uint8  
}
type cacheData struct {
	k string
	v interface{}
}
type Stats struct {
	MFUSize    uint    
	MRUSize    uint    
	MFUUsedP   uint    
	MRUUsedP   uint    
	MFUMaxSize uint    
	MRUMaxSize uint    
	Hits       uint64  
	Misses     uint64  
	Evictions  uint64  
	Overflows  uint64  
}
func New(c *Config) (*Bicache, error) {
	if (c.ShardCount & (c.ShardCount - 1)) != 0 {
		return nil, errors.New("Shard count must be a power of 2")
	}
	if c.MRUSize <= 0 {
		return nil, errors.New("MRU size must be > 0")
	}
	if c.ShardCount == 0 {
		c.ShardCount = 512
	}
	shards := make([]*Shard, c.ShardCount)
	mfuSize := int(math.Ceil(float64(c.MFUSize) / float64(c.ShardCount)))
	mruSize := int(math.Ceil(float64(c.MRUSize) / float64(c.ShardCount)))
	for i := 0; i < c.ShardCount; i++ {
		shards[i] = &Shard{
			cacheMap:      make(map[string]*entry, mfuSize+mruSize),
			mfuCache:      sll.New(),
			mruCache:      sll.New(),
			mfuCap:        uint(mfuSize),
			mruCap:        uint(mruSize),
			ttlMap:        make(map[string]time.Time),
			counters:      &counters{},
			nearestExpire: time.Now(),
			noOverflow:    c.NoOverflow,
		}
	}
	ctx, cf := context.WithCancel(context.Background())
	cache := &Bicache{
		shards:     shards,
		ShardCount: uint32(c.ShardCount),
		Size:       (mfuSize + mruSize) * c.ShardCount,
		done:       cf,
	}
	if c.AutoEvict > 0 {
		cache.autoEvict = true
		iter := time.Duration(c.AutoEvict)
		go bgAutoEvict(ctx, cache, iter, c)
	}
	return cache, nil
}
func (b *Bicache) Close() {
	b.done()
}
func bgAutoEvict(ctx context.Context, b *Bicache, iter time.Duration, c *Config) {
	ttlTachy := tachymeter.New(&tachymeter.Config{Size: c.ShardCount})
	promoTachy := tachymeter.New(&tachymeter.Config{Size: c.ShardCount})
	interval := time.NewTicker(time.Millisecond * iter)
	var evicted int
	var start time.Time
	defer interval.Stop()
	var ttlStats, promoStats *tachymeter.Metrics
	for {
		select {
		case <-ctx.Done():
			return
		case <-interval.C:
			if atomic.LoadUint32(&b.paused) == 1 {
				if c.EvictLog {
					log.Printf("[Bicache] Evictions Paused")
				}
				continue
			}
			for _, s := range b.shards {
				start = time.Now()
				evicted = 0
				if s.nearestExpire.Before(start.Add(iter)) {
					evicted = s.evictTTL()
				}
				if c.EvictLog && evicted > 0 {
					ttlTachy.AddTime(time.Since(start))
				}
				start = time.Now()
				s.promoteEvict()
				if c.EvictLog {
					promoTachy.AddTime(time.Since(start))
				}
			}
			ttlStats = ttlTachy.Calc()
			promoStats = promoTachy.Calc()
			if c.EvictLog {
				if ttlStats.Count > 0 {
					log.Printf("[Bicache EvictTTL] cumulative: %s | min: %s | max: %s\n",
						ttlStats.Time.Cumulative, ttlStats.Time.Min, ttlStats.Time.Max)
				}
				log.Printf("[Bicache PromoteEvict] cumulative: %s | min: %s | max: %s\n",
					promoStats.Time.Cumulative, promoStats.Time.Min, promoStats.Time.Max)
			}
			ttlTachy.Reset()
			promoTachy.Reset()
		}
	}
}
func (b *Bicache) Stats() *Stats {
	stats := &Stats{}
	var mfuCap, mruCap float64
	for _, s := range b.shards {
		s.RLock()
		stats.MFUSize += s.mfuCache.Len()
		stats.MRUSize += s.mruCache.Len()
		s.RUnlock()
		mfuCap += float64(s.mfuCap)
		mruCap += float64(s.mruCap)
		stats.Hits += atomic.LoadUint64(&s.counters.hits)
		stats.Misses += atomic.LoadUint64(&s.counters.misses)
		stats.Evictions += atomic.LoadUint64(&s.counters.evictions)
		stats.Overflows += atomic.LoadUint64(&s.counters.overflows)
	}
	stats.MFUMaxSize = uint(mfuCap)
	stats.MRUMaxSize = uint(mruCap)
	stats.MRUUsedP = uint(float64(stats.MRUSize) / mruCap * 100)
	if mfuCap > 0 {
		stats.MFUUsedP = uint(float64(stats.MFUSize) / mfuCap * 100)
	} else {
		stats.MFUUsedP = 0
	}
	return stats
}
func (s *Shard) evictTTL() int {
	if atomic.LoadUint64(&s.ttlCount) == 0 {
		return 0
	}
	expired := list.New()
	nearestExpire := time.Now().Add(time.Second * 2147483647)
	s.RLock()
	now := time.Now()
	for k, ttl := range s.ttlMap {
		if now.After(ttl) {
			_ = expired.PushBack(k)
		} else {
			if ttl.Before(nearestExpire) {
				nearestExpire = ttl
			}
		}
	}
	s.RUnlock()
	s.Lock()
	var evicted int
	for k := expired.Front(); k != nil; k = k.Next() {
		if n, exists := s.cacheMap[k.Value.(string)]; exists {
			delete(s.cacheMap, k.Value.(string))
			delete(s.ttlMap, k.Value.(string))
			switch n.state {
			case 0:
				s.mruCache.Remove(n.node)
			case 1:
				s.mfuCache.Remove(n.node)
			}
			evicted++
		}
	}
	s.nearestExpire = nearestExpire
	s.Unlock()
	s.decrementTTLCount(uint64(evicted))
	return evicted
}
func (s *Shard) promoteEvict() {
	mruOverflow := int(s.mruCache.Len() - s.mruCap)
	if mruOverflow <= 0 {
		return
	}
	if s.mfuCap == 0 {
		s.Lock()
		s.evictFromMRUTail(mruOverflow)
		s.Unlock()
		return
	}
	mruToPromoteEvict := s.mruCache.HighScores(mruOverflow)
	s.Lock()
	sort.Sort(sort.Reverse(mruToPromoteEvict))
	mfuFree := int(s.mfuCap - s.mfuCache.Len())
	if mfuFree < 0 {
		mfuFree = 0
	}
	var promoted int
	var canPromote int
	if int(mfuFree) >= mruOverflow {
		canPromote = mruOverflow
	} else {
		canPromote = mfuFree
	}
	if canPromote == 0 {
		goto promoteByScore
	}
	if canPromote > 0 {
		for _, node := range mruToPromoteEvict[:canPromote] {
			if node.Score < 2 {
				break
			}
			s.mruCache.Remove(node)
			s.mfuCache.PushTailNode(node)
			s.cacheMap[node.Value.(*cacheData).k].state = 1
			promoted++
		}
		if promoted == mruOverflow {
			s.Unlock()
			return
		}
	}
promoteByScore:
	s.Unlock()
	mruOverflow -= promoted
	remainderPosition := promoted
	var promotedByScore int
	bottomMFU := s.mfuCache.LowScores(mruOverflow)
	if len(bottomMFU) == 0 || bottomMFU[0].Score >= mruToPromoteEvict[remainderPosition].Score {
		goto evictFromMRUTail
	}
	s.Lock()
scorePromote:
	for _, mruNode := range mruToPromoteEvict[remainderPosition:] {
		for i, mfuNode := range bottomMFU {
			if mruNode.Score > mfuNode.Score {
				s.mfuCache.Remove(mfuNode)
				s.mruCache.PushHeadNode(mfuNode)
				s.cacheMap[mfuNode.Value.(*cacheData).k].state = 0
				s.mruCache.Remove(mruNode)
				s.mfuCache.PushTailNode(mruNode)
				s.cacheMap[mruNode.Value.(*cacheData).k].state = 1
				promotedByScore++
				bottomMFU = append(bottomMFU[:i], bottomMFU[i+1:]...)
				break
			}
			if i == len(bottomMFU)-1 {
				break scorePromote
			}
		}
	}
	s.Unlock()
evictFromMRUTail:
	s.Lock()
	toEvict := mruOverflow - promotedByScore
	if toEvict > 0 {
		s.evictFromMRUTail(toEvict)
	}
	s.Unlock()
}
func (s *Shard) evictFromMRUTail(n int) {
	ttlStart := len(s.ttlMap)
	for i := 0; i < n; i++ {
		node := s.mruCache.Tail()
		delete(s.cacheMap, node.Value.(*cacheData).k)
		delete(s.ttlMap, node.Value.(*cacheData).k)
		s.mruCache.RemoveTail()
	}
	ttlEvicted := ttlStart - len(s.ttlMap)
	s.decrementTTLCount(uint64(ttlEvicted))
	atomic.AddUint64(&s.counters.evictions, uint64(n-ttlEvicted))
}