package assetcache

// makeRoom evicts entries until a reservation of need bytes fits the budget
// beside what the store holds and has promised (used + reserved + need <=
// Budget), or until nothing is left to evict. Each round takes the least
// recently used entry of the app furthest over its share. Bytes that open
// Readers hold stay counted (drop keeps them), so room can stay short; the
// caller's budget check decides. Reserve calls it only for a reservation
// that fits once room is made, and Open with need 0 to bring a store found
// over its budget back under. It is called without s.mu held and takes s.mu
// only to choose a victim, never across the deletion.
func (s *Store) makeRoom(need int64) {
	var failed map[*entry]bool // victims drop could not delete; not chosen again
	for {
		s.mu.Lock()
		if s.used <= s.cfg.Budget-s.reserved-need {
			s.mu.Unlock()
			return
		}
		victim := s.victimLocked(failed)
		s.mu.Unlock()
		if victim == nil {
			return
		}
		if !s.drop(victim) {
			if failed == nil {
				failed = make(map[*entry]bool)
			}
			failed[victim] = true
		}
	}
}

// victimLocked returns the least recently used entry, outside skip, of the
// app with the largest bytes - share, or nil when no entry qualifies. Equal
// excess goes to the app whose candidate was used longest ago. The caller
// holds s.mu.
func (s *Store) victimLocked(skip map[*entry]bool) *entry {
	share := s.shareOf(len(s.apps))
	var victim *entry
	var victimOver int64
	for _, app := range s.apps {
		var cand *entry
		for el := app.lru.Back(); el != nil; el = el.Prev() {
			if e := el.Value.(*entry); !skip[e] {
				cand = e
				break
			}
		}
		if cand == nil {
			continue
		}
		over := app.bytes - share
		if victim == nil || over > victimOver || (over == victimOver && cand.used < victim.used) {
			victim, victimOver = cand, over
		}
	}
	return victim
}

// shareOf is the bytes each of apps apps may hold before eviction takes
// from them: the budget divided among them, never more than a quarter of it
// for one app.
func (s *Store) shareOf(apps int) int64 {
	if apps < 1 {
		apps = 1
	}
	share := s.cfg.Budget / int64(apps)
	if limit := s.cfg.Budget / 4; share > limit {
		share = limit
	}
	return share
}

// Retain deletes every entry whose key keep rejects and returns how many it
// deleted. keep is called without any store lock held, once per entry that
// was indexed when Retain began; an entry committed meanwhile is not judged.
// An entry a Reader holds is deleted like any other: its files go at once
// and its bytes stay counted until the Reader closes. Retain first retries
// the unlinks that failed earlier, so a sweep frees their disk even when
// there is no entry left for it to judge.
func (s *Store) Retain(keep func(Key) bool) int {
	s.retryStuck()
	s.mu.Lock()
	all := make([]*entry, 0, len(s.entries))
	for _, e := range s.entries {
		all = append(all, e)
	}
	s.mu.Unlock()
	n := 0
	for _, e := range all {
		if !keep(e.meta.Key) && s.drop(e) {
			n++
		}
	}
	return n
}