Package jline.api.cache

Class Cache_cost_pathcheck

java.lang.Object

jline.api.cache.Cache_cost_pathcheck

public final class Cache_cost_pathcheck
extends Object

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	Cache_cost_pathcheck.BlockedPair	One (item, list) pair that is size-feasible for the list but unreachable because an intermediate list on the promotion path rejects the item.

Method Summary

Modifier and Type	Method	Description
static List<Cache_cost_pathcheck.BlockedPair>	cache_cost_pathcheck(Matrix gamma, Matrix sigma, Matrix k, int[] parent)	Detects promotion paths blocked by storage cost caps.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Details

cache_cost_pathcheck

public static List<Cache_cost_pathcheck.BlockedPair> cache_cost_pathcheck(Matrix gamma,
 Matrix sigma,
 Matrix k,
 int[] parent)

Detects promotion paths blocked by storage cost caps. The constrained normalizing constant E(m,k) of Casale-Gast, IEEE/ACM Trans. Networking 29(2), 2021, Sec. IX, sums over every size-feasible state, while under RR-C(m) an item only reaches list j one list at a time along the path from the miss list. A cap on an intermediate list therefore makes size-feasible states unreachable and E(m,k) normalizes over states the cache never visits. An empty report is a necessary, not sufficient, condition for the two sets to agree.

Parameters:

gamma - Cache access factors (n x h).

sigma - Item storage costs (sizes), one per item.

k - Per-list storage cost caps, one per list.

parent - Parent list of each list, 0-based with -1 for lists rooted in the miss list.

Returns:

the blocked pairs, empty when the screen finds none.