summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorXavier Chantry <shiningxc@gmail.com>2009-09-03 22:34:39 +0200
committerAaron Griffin <aaronmgriffin@gmail.com>2009-09-18 13:19:08 -0700
commitfe4152a6949a9ec3132d1a1c08335f370989198f (patch)
treecbb76089311408bb830d82ab554698aaff5d5d1b
parentea827b50d0c65b4ba9f2e2d3c0761572915e6b03 (diff)
improve compute_dep algorithm
The compute_dep function I wrote for the more informative hierarchy output was very inefficient. It's much better now (10s -> 0.5s) on my box, and I get exactly the same results :) Now the big majority of the time is again spent on parsing pkgbuilds. Signed-off-by: Xavier Chantry <shiningxc@gmail.com> Signed-off-by: Aaron Griffin <aaronmgriffin@gmail.com>
-rwxr-xr-xcron-jobs/check_archlinux/check_packages.py35
1 files changed, 16 insertions, 19 deletions
diff --git a/cron-jobs/check_archlinux/check_packages.py b/cron-jobs/check_archlinux/check_packages.py
index 96f3181..9ffdac5 100755
--- a/cron-jobs/check_archlinux/check_packages.py
+++ b/cron-jobs/check_archlinux/check_packages.py
@@ -205,26 +205,22 @@ def verify_deps(name,repo,deps):
return (pkg_deps,missdeps,hierarchy)
-def compute_deplist_aux(pkg,deplist):
- newdeplist = []
- list = []
- if pkgdeps.has_key(pkg):
- list.extend(pkgdeps[pkg])
- if makepkgdeps.has_key(pkg):
- list.extend(makepkgdeps[pkg])
- for dep in list:
- if dep not in deplist:
- newdeplist.append(dep)
- deplist.append(dep)
- for dep in newdeplist:
- deplist2 = compute_deplist_aux(dep,deplist)
- for dep2 in deplist2:
- if dep2 not in deplist:
- deplist.append(dep2)
- return deplist
-
def compute_deplist(pkg):
- return compute_deplist_aux(pkg,[])
+ list = []
+ stack = [pkg]
+ while stack != []:
+ dep = stack.pop()
+ if pkgdeps.has_key(dep):
+ for dep2 in pkgdeps[dep]:
+ if dep2 not in list:
+ list.append(dep2)
+ stack.append(dep2)
+ if makepkgdeps.has_key(dep):
+ for dep2 in makepkgdeps[dep]:
+ if dep2 not in list:
+ list.append(dep2)
+ stack.append(dep2)
+ return list
def check_hierarchy(deph):
hierarchy = []
@@ -471,6 +467,7 @@ for name,pkg in repopkgs.iteritems():
missing_makedeps.extend(missdeps)
makedeph.extend(hierarchy)
+print "==> checking hierarchy"
dep_hierarchy = check_hierarchy(deph)
makedep_hierarchy = check_hierarchy(makedeph)