Method murmurHashAppend

src/IECore/PathMatcher.cpp:803–830

Our hash is complicated by the fact that PathMatcher::Iterator doesn't guarantee the order of visiting child nodes in its tree (because it sorts using InternedString addresses for the fastest possible match() implementation). We therefore have to use a stack to keep track of our traversal through the tree, and output all the children at each level only after sorting them alphabetically.

// our traversal through the tree, and output all the children at each
// level only after sorting them alphabetically.
void IECore::murmurHashAppend( IECore::MurmurHash &h, const IECore::PathMatcher &data )
{
	HashStack stack;
	for( PathMatcher::RawIterator it = data.begin(), eIt = data.end(); it != eIt; ++it )
	{
		// The iterator is recursive, so we use a stack to keep
		// track of where we are. Resize the stack to match our
		// current depth. The required size has the +1 because
		// we need a stack entry for the root item.
		size_t requiredStackSize = it->size() + 1;
		if( requiredStackSize > stack.size() )
		{
			// Going a level deeper.
			stack.push( HashNodes() );
			assert( stack.size() == requiredStackSize );
		}
		else if( requiredStackSize < stack.size() )
		{
			// Returning from recursion to the child nodes.
			// Output the hashes for the children we visited
			// and stored on the stack previously.
			popHashNodes( stack, requiredStackSize, h );
		}

		stack.top().push_back( HashNode( it->size() ? it->back().c_str() : "", it.exactMatch() ) );
	}
	popHashNodes( stack, 0, h );
}