src/mem/stack_dist_calc.cc

61     // Create a root node. Node type variable in the topmost layer
79             // each map entry contains an index and a node
96 // the node sums till the root. It also deletes the nodes that
99 StackDistCalc::updateSum(Node* node, bool from_left,
105     // Make a copy of the node variables and work on them
106     // as a node may be deleted by this function
107     uint64_t node_sum_l = node->sumLeft;
108     uint64_t node_sum_r = node->sumRight;
109     bool node_left = node->isLeftNode;
110     bool node_discard_left = node->discardLeft;
111     bool node_discard_right = node->discardRight;
112     uint64_t node_n_index = node->nodeIndex;
113     Node* node_parent_ptr = node->parent;
118         // right_sum of the node is not greater than the
120         // for example a node in layer 3 (tree[3]) can at most
124                  "Error in sum left of level %ul, node index %ull, "
128                  "Error in sum right of level %ul, node index %ull, "
152     // Update the node variables with new values
153     node->nodeIndex = node_n_index;
154     node->sumLeft = node_sum_l;
155     node->sumRight = node_sum_r;
156     node->isLeftNode = node_left;
157     node->discardLeft = node_discard_left;
158     node->discardRight = node_discard_right;
160     // Delete the node if it is not required anymore
163         delete node;
173     // root node is reached
188 StackDistCalc::updateSumsLeavesToRoot(Node* node, bool is_new_leaf)
194         node->sumLeft = 1;
195         updateSum(node->parent,
196                   node->isLeftNode, node->sumLeft,
201         node->sumLeft = 0;
202         stack_dist = updateSum(node->parent,
203                                   node->isLeftNode, 0,
211 // the node sums till the root.
213 StackDistCalc::getSum(Node* node, bool from_left, uint64_t sum_from_below,
220         stack_dist += node->sumRight;
224     // root node is reached
225     if (node->parent) {
226         stack_dist = getSum(node->parent, node->isLeftNode,
227                             node->sumLeft + node->sumRight,
236 StackDistCalc::getSumsLeavesToRoot(Node* node) const
238     return  getSum(node->parent, node->isLeftNode, 0, 0, 0);
245 // OP1. moving the root node one layer up if index counter
255         // OP1. moving the root node one layer up if index counter
258         // new tree layer above and create a new Root node in it.
259         // After the root is created the old node
261         // newly created root node. The sum_l of this new root node
262         // becomes the sum_l + sum_r of the old node.
268         // Create a new root node
274         // Update its discard left flag if the node below has
287         // point to newly created root node
324             // intermediate node if required. Link the parent_ptr of
325             // the new node to the parent in the above layer.
329                 // a new node at that layer is created
350 // a new node. A feature to mark an old node in the tree is
367     // Default value of isMarked flag for each node.
395         // determine if this node was marked earlier
414             // At odd values of index counter, a new right-type node is
415             // added to the leaf layer, else a left-type node is added
419         // Add new leaf node in the leaf layer (tree[0])
425         // Point the parent pointer to the intermediate node above
429         // addition of this new leaf node.
435             // last node in the link of parent pointers is the root node.
436             // It takes a leaf node as an argument and traveses upwards till
458 // no new node is added. It can be used to mark a previous access
463     // Default value of isMarked flag for each node.
483         // Mark the leaf node if required
514 StackDistCalc::sanityCheckTree(const Node* node, uint64_t level) const
516     const Node* next_up = node->parent;
520         panic_if(!next_up, "Sanity check failed for node %ull \n",
521                  node->nodeIndex);
525     panic_if(next_up->parent, "Sanity check failed for node %ull \n",
526              node->nodeIndex);
567     Node* node;
575         node = it->second;
576         uint64_t r_index = node->nodeIndex;