package backoff

import (
	"container/list"
	"errors"
	"sync"
	"time"
)

const (
	Threshold = 5
	Base      = time.Second
	Cap       = 15 * time.Minute
	Entries   = 10000
)

var errNoEntries = errors.New("backoff: a table needs at least one entry")

type entry struct {
	key      string
	failures int
	until    time.Time
	in       *list.List
}

type Backoff struct {
	mu       sync.Mutex
	now      func() time.Time
	max      int
	entries  map[string]*list.Element
	counting *list.List
	reached  *list.List
	evicted  uint64
}

func New(now func() time.Time, max int) *Backoff {
	if max < 1 {
		panic(errNoEntries)
	}
	return &Backoff{now: now, max: max, entries: map[string]*list.Element{}, counting: list.New(), reached: list.New()}
}

func (b *Backoff) Locked(key string) bool {
	b.mu.Lock()
	defer b.mu.Unlock()
	el, ok := b.entries[key]
	if !ok {
		return false
	}
	e := el.Value.(*entry)
	e.in.MoveToFront(el)
	return b.now().Before(e.until)
}

func (b *Backoff) Fail(key string) {
	b.mu.Lock()
	defer b.mu.Unlock()
	el, ok := b.entries[key]
	if !ok {
		for len(b.entries) >= b.max {
			b.evict()
		}
		el = b.counting.PushFront(&entry{key: key, in: b.counting})
		b.entries[key] = el
	}
	e := el.Value.(*entry)
	e.in.MoveToFront(el)
	e.failures++
	if e.failures < Threshold {
		return
	}
	if e.in == b.counting {
		b.counting.Remove(el)
		e.in = b.reached
		b.entries[key] = b.reached.PushFront(e)
	}
	window := Cap
	if shift := e.failures - Threshold; shift < 20 {
		if w := Base << shift; w < Cap {
			window = w
		}
	}
	e.until = b.now().Add(window)
}

func (b *Backoff) evict() {
	victim := b.counting.Back()
	if victim == nil {
		victim = b.reached.Back()
	}
	e := victim.Value.(*entry)
	e.in.Remove(victim)
	delete(b.entries, e.key)
	b.evicted++
}

func (b *Backoff) Reset(key string) {
	b.mu.Lock()
	defer b.mu.Unlock()
	if el, ok := b.entries[key]; ok {
		el.Value.(*entry).in.Remove(el)
		delete(b.entries, key)
	}
}

func (b *Backoff) Len() int {
	b.mu.Lock()
	defer b.mu.Unlock()
	return len(b.entries)
}