From 83eb257e26eb271f2d4c5bfae1425a47fcddc406 Mon Sep 17 00:00:00 2001 From: Zac Medico Date: Wed, 11 Mar 2009 06:44:38 +0000 Subject: Make digraph store a single priority list for each edge instead of two identical lists. (trunk r12767) svn path=/main/branches/2.1.6/; revision=13011 --- 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 dbc19f8ed..82fc57431 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