Create a digraph.difference_update() method and use it to amortize the

cost of removing nodes from the digraph.order list. (trunk r9992)

svn path=/main/branches/2.1.2/; revision=9993

2 files changed, 30 insertions, 6 deletions

diff --git a/bin/emerge b/bin/emerge
index 5ced41356..053a3f6a2 100755
--- a/bin/emerge
+++ b/bin/emerge
@@ -3459,16 +3459,18 @@ class depgraph(object):
 		# otherwise they slow down merge order calculation. Don't remove
 		# non-root nodes since they help optimize merge order in some cases
 		# such as revdep-rebuild.
+		removed_nodes = set()
 		while True:
-			removed_something = False
 			for node in mygraph.root_nodes():
 				if not isinstance(node, Package) or \
 					node.installed or node.onlydeps:
-					self.spinner.update()
-					mygraph.remove(node)
-					removed_something = True
-			if not removed_something:
+					removed_nodes.add(node)
+			if removed_nodes:
+				self.spinner.update()
+				mygraph.difference_update(removed_nodes)
+			if not removed_nodes:
 				break
+			removed_nodes.clear()
 		self._merge_order_bias(mygraph)
 		def cmp_circular_bias(n1, n2):
 			"""
@@ -3818,6 +3820,8 @@ class depgraph(object):
 			prefer_asap = True
 			accept_root_node = False
 
+			mygraph.difference_update(selected_nodes)
+
 			for node in selected_nodes:
 
 				# Handle interactions between blockers
@@ -3853,7 +3857,7 @@ class depgraph(object):
 
 				if node[-1] != "nomerge":
 					retlist.append(node)
-				mygraph.remove(node)
+
 				if isinstance(node, Uninstall):
 					# Include satisfied blockers in the merge list so
 					# that the user can see why the package had to be
diff --git a/pym/portage.py b/pym/portage.py
index f11e8877e..9dd0ecd92 100644
--- a/pym/portage.py
+++ b/pym/portage.py
@@ -391,6 +391,26 @@ class digraph:
 		del self.nodes[node]
 		self.order.remove(node)
 
+	def difference_update(self, t):
+		"""
+		Remove all given nodes from node_set. This is more efficient
+		than multiple calls to the remove() method.
+		"""
+		if isinstance(t, (list, tuple)) or \
+			not hasattr(t, "__contains__"):
+			t = frozenset(t)
+		order = []
+		for node in self.order:
+			if node not in t:
+				order.append(node)
+				continue
+			for parent in self.nodes[node][1]:
+				del self.nodes[parent][0][node]
+			for child in self.nodes[node][0]:
+				del self.nodes[child][1][node]
+			del self.nodes[node]
+		self.order = order
+
 	def remove_edge(self, child, parent):
 		"""
 		Remove edge in the direction from child to parent. Note that it is