[apparmor] [PATCH 03/20] Rework depth first traversal of expr trees

[John Johansen]

On 11/05/2010 03:24 AM, Kees Cook wrote:
> Hi John,
> 
> On Fri, Nov 05, 2010 at 01:50:59AM -0400, John Johansen wrote:
>> Rework the depth first traversal of expr trees, to remove the use of the
>> unneeded visited table, and give a little speed up and cleanup.
>> ...
>> +        while (dynamic_cast<InnerNode *>(node)) {
>> +	    pos.push(node->child[0]);
>> +            node = node->child[0];
>> +        }
>> ...
>> +        Node *last = pos.top();
>> +	pos.pop();
>> +
>> +	if (!pos.empty()) {
>> +  	    /* no need to dynamic cast, as we just popped a node so the top node
>> +	     * must be an inner node */
>> +	    InnerNode *node = (InnerNode *)(pos.top());
>> +
>> +	    if (node->child[1] && node->child[1] != last) {
>> +		push_left(node->child[1]);
>> +	    }
>>  	}
>>      }
>>  };
> 
> Looks like some whitespace intermix in this one. As for the content, what
okay, fixed

> was "visited" actually tracking? The change here isn't entirely obvious to
> me.
> 
visited was tracking whether we had done the left side of the tree and come back
through the parent.  Ie keeping the visit order of, left, right, parent but that
information already exists

It is replaced by

+	    if (node->child[1] && node->child[1] != last) {
+		push_left(node->child[1]);
+	    }

which is if we have a right node and our right node wasn't the last node visited
then visit that subtree, other wise its the parents turn.