From c8898f40c614eab5262c28a5f11b27a56f898fa1 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Fri, 6 Mar 2009 04:29:56 +0000 Subject: Make digraph store a single priority list for each edge instead of two identical lists. svn path=/main/trunk/; revision=12767 --- pym/portage/__init__.py | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) (limited to 'pym') diff --git a/pym/portage/__init__.py b/pym/portage/__init__.py index c60f7eb37..4db58bb0f 100644 --- a/pym/portage/__init__.py +++ b/pym/portage/__init__.py @@ -368,11 +368,11 @@ class digraph(object): self.nodes[parent] = ({}, {}, parent) self.order.append(parent) - priorities = self.nodes[node][1].setdefault(parent, []) - priorities.append(priority) - priorities.sort() - - priorities = self.nodes[parent][0].setdefault(node, []) + priorities = self.nodes[node][1].get(parent) + if priorities is None: + priorities = [] + self.nodes[node][1][parent] = priorities + self.nodes[parent][0][node] = priorities priorities.append(priority) priorities.sort() @@ -560,13 +560,22 @@ class digraph(object): def clone(self): clone = digraph() clone.nodes = {} + memo = {} for children, parents, node in self.nodes.itervalues(): children_clone = {} for child, priorities in children.iteritems(): - children_clone[child] = priorities[:] + priorities_clone = memo.get(id(priorities)) + if priorities_clone is None: + priorities_clone = priorities[:] + memo[id(priorities)] = priorities_clone + children_clone[child] = priorities_clone parents_clone = {} for parent, priorities in parents.iteritems(): - parents_clone[parent] = priorities[:] + priorities_clone = memo.get(id(priorities)) + if priorities_clone is None: + priorities_clone = priorities[:] + memo[id(priorities)] = priorities_clone + parents_clone[parent] = priorities_clone clone.nodes[node] = (children_clone, parents_clone, node) clone.order = self.order[:] return clone -- cgit v1.2.3-1-g7c22