cache/replacement_policies/tree_plru_rp.hh

34  * The victim is chosen using a tree of bit timestamps.
36  * A tree contains consists of leafs that represent the direction to take when
39  * Let's assume each tree contains 8 replacement data entries. For example, if
40  * these entries are named from A to H, and the tree's bits are:
51  * grandparents, etc would be updated, and we'd end up with the following tree:
66  * Consecutive calls to instantiateEntry() use the same tree up to numLeaves.
67  * When numLeaves replacement datas have been created, a new tree is generated,
86      * Instead of implementing the tree itself with pointers, it is implemented
88      * tree, and its parent. Index 0 represents the root, 1 is its left node,
101      * Notice that the replacement data entries are not represented in the tree
119      * Holds the latest temporary tree instance created by instantiateEntry().
126      * data shares its tree with other entries.
131          * Theoretical index of this replacement data in the tree. In practice,
132          * the corresponding node does not exist, as the tree stores only the
138          * Shared tree pointer. A tree is shared between numLeaves nodes, so
142         std::shared_ptr<PLRUTree> tree;
147          * @param index Index of the corresponding entry in the tree.
148          * @param tree The shared tree pointer.
150         TreePLRUReplData(const uint64_t index, std::shared_ptr<PLRUTree> tree);
169      * Makes tree leaf of replacement data the LRU (tree bits point to it).
178      * Makes tree leaf of replacement data the MRU.
196      * candidates share the same replacement data tree.
206      * function use the same tree up to numLeaves. When numLeaves replacement
207      * data have been created, a new tree is generated, and the counter is