Replacer

source: bluebase/pf/replacer.py

---

class PfReplacer

Bases: ABC

An abstract base class for replacers that select eviction candidate keys.

abstractmethod add(key: object) → None

Add a key.

abstractmethod remove(key: object) → None

Remove a key.

abstractmethod touch(key: object) → None

Notify the replacer that a key has been accessed.

abstractmethod candidates() → Iterator

Yield eviction candidate keys in priority order.

class PfRandomReplacer(*, seed: int = 0)

Bases: PfReplacer

A replacer that selects eviction candidate keys using a random policy.

Variables:

• seed (int) – the random seed

• rng (random.Random) – the random number generator

• set – the container holding the currently managed keys

add(key: object) → None

Add a key.

remove(key: object) → None

Remove a key.

touch(key: object) → None

Notify the replacer that a key has been accessed.

Under the random policy, this should do nothing.

candidates() → Iterator

Yield eviction candidate keys in random order.

class PfFifoReplacer

Bases: PfReplacer

A replacer that selects eviction candidate keys using a FIFO policy.

Variables:

keys (collections.OrderedDict[object, None]) – the container holding the currently managed keys

add(key: object) → None

Add a key.

remove(key: object) → None

Remove a key.

touch(key: object) → None

Notify the replacer that a key has been accessed.

Under the FIFO policy implemented by OrderedDict, this should do nothing.

candidates() → Iterator

Yield eviction candidate keys in FIFO order.

class PfClockReplacer(*, chance: int = 2)

Bases: PfReplacer

A replacer that selects eviction candidate keys using the Clock algorithm.

Variables:

• chance (int) – the maximum grace count used by the Clock algorithm

• slots (list[object | None]) – the container holding the currently managed keys

• counter (list[int]) – the grace counts corresponding to the slots

• find (dict[object, int]) – a mapping from each key to its slot index

• frees (list[int]) – the indices of free slots

• hand (int) – the slot index currently pointed to by the clock hand

add(key: object) → None

Add a key.

remove(key: object) → None

Remove a key.

touch(key: object) → None

Notify the replacer that a key has been accessed.

Under the Clock algorithm, this increases the remaining grace count of the key.

candidates() → Iterator

Yield eviction candidate keys according to the Clock algorithm.

class PfLruReplacer

Bases: PfReplacer

A replacer that selects eviction candidate keys using an LRU policy.

Variables:

keys (collections.OrderedDict[object, None]) – the container holding the currently managed keys

assignmentadd(key: object) → None

Add a key.

Hint

When using either dict or OrderedDict, the insertion order is preserved.

assignmentremove(key: object) → None

Remove a key.

Hint

It should not raise an exception even if the key is not found.

assignmenttouch(key: object) → None

Notify the replacer that a key has been accessed.

Under the LRU policy, this gives the key the lowest eviction priority.

Hint

This can be implemented easily using OrderedDict. This kind of data structure is abstractly known as a position list.

assignmentcandidates() → Iterator

Yield eviction candidate keys in LRU order.

Hint

If add and touch are implemented correctly, this should be easy to implement.