Root/qpkg/TODO

Source at commit 0bc4b6046baa19f393ea3ebd6064178a080cfe35 created 8 years 9 months ago.
By Werner Almesberger, qpkg: added detection of cyclic dependencies
1Still left to do
2================
3
4- check whether introducing a new package would cause a conflict
5
6- compile the list of conflicts of installed packages
7
8- handle Provides:
9
10- if there are multiple choices, try to prefer more recent versions
11
12- sort prerequisites such that they can be installed in the specified order
13
14- consider Architecture:
15
16  Update: we parse and record it now but don't use it yet.
17
18- what to do with explicit and implicit replacement ?
19
20- if we can't resolve the prerequisites, give at least a hint of what one
21  can do to improve the situation
22
23- check database for internal consistency
24
25  Update: added detection of cyclic dependencies (in progress)
26
27- implement keyword search
28
29- consider also supporting the similar but not identical (parent ?) format
30  of /var/lib/dpkg/status and /var/lib/apt/lists/*Packages
31
32
33Done
34====
35
36- optimize the search trees. Right now, we have 81812 calls to make_id
37  for 14601 packages, resulting in 7420560 calls to comp_id.
38
39  There can be at most 2 new identifiers per package (package name and
40  version), so a perfectly balanced tree should have a depth of no more
41  than 14. If we assume that each call to make_id searches to the bottom,
42  we'd get 1145368 calls to comp_id, about 15% of the current number.
43
44  So the tree is clearly degenerated.
45
46  Update: after switching to red-black trees, we get only 1497604 calls
47  to comp_id. This is 130% of the "good case" estimate above. Insertion
48  of a new node is currently done with two lookups, so we'll get rid of
49  some more lookups after further optimization.
50
51  Update: after merging the two lookups per new node into one, we're at
52  1172642 calls to comp_id, or 102% of the predicted "good case".
53

Archive Download this file

Branches:
master



interactive