src/mem/stack_dist_calc.hh

53   * of incoming addresses based on the partial sum hierarchy tree
57   * A tree structure is maintained and updated at each transaction
58   * (unique or non-unique). The tree is implemented as an STL vector
59   * with layers of the form <map> Each layer in this tree is an
61   * of leaf, intermediate and root nodes. For example, in a tree with 3
62   * layers, tree[0][5] gives a leaf node pointer for key=5 tree[1][1]
63   * gives an intermediate node pointer for key=1 tree[2][0] gives the
64   * root node in the tree.
71   * mark an old node in the tree is added. This is useful if it is
83   * At every unique transaction a new leaf node is added at tree[0](leaf layer)
88   * At every non-unique transaction the tree is traversed from the
90   * from the tree, and the sums (to the right are collected) and
104   * just inspect the tree, and mark a leaf node (if mark flag is set). The
110   * At every non-unique transaction the tree is traversed from the
154   * Node Balancing: The tree structure is maintained by an
159   * tree and a new root node is initialized. The old node at the lower
172   * in both (tree and STL based dummy stack).
194      * @param level level in the tree the calling node is located
221      * @param level level in the tree the calling node is located
243      * updateTree is a tree balancing operation, which maintains the
244      * binary tree structure.
261      * @param level the level at which this node is located in the tree
276      * Query depth of the tree (tree[0] represents leaf layer while
277      * tree[treeDepth] represents the root layer, all layers in
282     uint64_t getTreeDepth() const { return tree.size() - 1; }
286      * This method prints top n entries in the tree based implementation as
296      * It is 10x slower than the tree based implemenation.
333      *  - Lookup the tree for the given address
334      *  - delete old node if found in tree
340      * @param addNewNode If true, a new node is added to the tree
394      * counter is incremented and a new leaf node is added in the tree
399     // Binary tree of partial sums
400     TreeType tree;
406     // level in the tree