Werner's Miscellanea
Sign in or create your account | Project List | Help
Werner's Miscellanea Git Source Tree
Root/
Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 13 years 4 months ago. By Werner Almesberger, qpkg: added James S. Plank's red-black trees | |
---|---|
1 | #include <stdlib.h> |
2 | #include <stdio.h> |
3 | #include <string.h> |
4 | #include <ctype.h> |
5 | #include <assert.h> |
6 | |
7 | #include "id.h" |
8 | #include "qpkg.h" |
9 | #include "util.h" |
10 | |
11 | |
12 | struct list { |
13 | const struct ref *refs; |
14 | struct list *next; |
15 | }; |
16 | |
17 | |
18 | static struct pkg **best = NULL; |
19 | static struct pkg **stack = NULL; |
20 | static int n_best; /* undefined if best == NULL */ |
21 | static int n_stack = 0; |
22 | static int stack_max = 0; |
23 | |
24 | |
25 | #define ID2S(id) (int) (id)->len, (id)->s |
26 | |
27 | |
28 | static int epoch(const char **s, const struct id *id) |
29 | { |
30 | const char *end = id->s+id->len; |
31 | int n = 0; |
32 | |
33 | while (*s != end && isdigit(**s)) { |
34 | n = 10*n+**s-'0'; |
35 | (*s)++; |
36 | } |
37 | if (*s == id->s || (*s != end && **s == ':')) |
38 | return n; |
39 | *s = id->s; |
40 | return 0; |
41 | } |
42 | |
43 | |
44 | static int comp_versions(const struct id *va, const struct id *vb) |
45 | { |
46 | int epoch_a = 0, epoch_b = 0; |
47 | const char *a = va->s; |
48 | const char *b = vb->s; |
49 | const char *ea = a+va->len; |
50 | const char *eb = b+vb->len; |
51 | |
52 | epoch_a = epoch(&a, va); |
53 | epoch_b = epoch(&b, vb); |
54 | if (epoch_a != epoch_b) |
55 | return epoch_a-epoch_b; |
56 | |
57 | while (1) { |
58 | if (a == ea || b == eb) |
59 | return (a != ea)-(b != eb); |
60 | if (isdigit(*a) && isdigit(*b)) { |
61 | int na = 0, nb = 0; |
62 | |
63 | while (a != ea && isdigit(*a)) { |
64 | na = na*10+*a-'0'; |
65 | a++; |
66 | } |
67 | while (b != eb && isdigit(*b)) { |
68 | nb = nb*10+*b-'0'; |
69 | b++; |
70 | } |
71 | if (na == nb) |
72 | continue; |
73 | |
74 | return na-nb; |
75 | } |
76 | if (*a > *b) |
77 | return 1; |
78 | if (*a < *b) |
79 | return 1; |
80 | a++; |
81 | b++; |
82 | } |
83 | } |
84 | |
85 | |
86 | static void done(void) |
87 | { |
88 | int size; |
89 | |
90 | if (best && n_best <= n_stack) |
91 | return; |
92 | free(best); |
93 | size = sizeof(*stack)*(n_stack+1); |
94 | best = alloc_size(size); |
95 | memcpy(best, stack, sizeof(*stack)*n_stack); |
96 | n_best = n_stack; |
97 | best[n_best] = NULL; |
98 | } |
99 | |
100 | |
101 | static void push(struct pkg *pkg) |
102 | { |
103 | //fprintf(stderr, "push %.*s\n", ID2S(pkg->id)); |
104 | if (n_stack == stack_max) { |
105 | stack_max = (stack_max+1)*2; |
106 | stack = realloc(stack, sizeof(*stack)*stack_max); |
107 | if (!stack) { |
108 | perror("realloc"); |
109 | exit(1); |
110 | } |
111 | |
112 | } |
113 | stack[n_stack++] = pkg; |
114 | assert(!pkg->mark && !pkg->installed); |
115 | pkg->mark = 1; |
116 | } |
117 | |
118 | |
119 | static void pop(void) |
120 | { |
121 | assert(n_stack); |
122 | n_stack--; |
123 | stack[n_stack]->mark = 0; |
124 | } |
125 | |
126 | |
127 | static int satisfies(const struct pkg *pkg, const struct ref *ref) |
128 | { |
129 | int cmp; |
130 | |
131 | if (pkg->id != ref->pkg) |
132 | return 0; |
133 | if (!ref->version) |
134 | return 1; |
135 | assert(pkg->version); |
136 | cmp = comp_versions(pkg->version, ref->version); |
137 | //fprintf(stderr, "%.*s <%d> %.*s\n", |
138 | // ID2S(pkg->version), cmp, ID2S(ref->version)); |
139 | switch (ref->relop) { |
140 | case rel_eq: |
141 | return !cmp; |
142 | case rel_ge: |
143 | return cmp >= 0; |
144 | case rel_lt: |
145 | return cmp < 0; |
146 | default: |
147 | abort(); |
148 | } |
149 | } |
150 | |
151 | |
152 | static int conflicts(const struct pkg *pkg, const struct list *conf) |
153 | { |
154 | /* @@@ */ |
155 | return 0; |
156 | } |
157 | |
158 | |
159 | static void resolve(struct list *next_dep, const struct ref *dep, |
160 | struct list *conf) |
161 | { |
162 | static int level = 0; |
163 | struct list more_deps; |
164 | struct list more_conf = { |
165 | .next = conf |
166 | }; |
167 | struct pkg *pkg; |
168 | |
169 | while (!dep) { |
170 | if (!next_dep) { |
171 | done(); |
172 | return; |
173 | } |
174 | dep = next_dep->refs; |
175 | next_dep = next_dep->next; |
176 | } |
177 | for (pkg = dep->pkg->value; pkg; pkg = pkg->more) { |
178 | if (best && n_stack == n_best) |
179 | return; |
180 | #if 0 |
181 | fprintf(stderr, "%*s", level, ""); |
182 | fprintf(stderr, "%.*s %p", ID2S(pkg->id), pkg); |
183 | if (pkg->version) |
184 | fprintf(stderr, " %.*s", ID2S(pkg->version)); |
185 | if (pkg->mark) fprintf(stderr, " +"); |
186 | if (pkg->installed) fprintf(stderr, " ***"); |
187 | fprintf(stderr, "\n"); |
188 | #endif |
189 | if (!satisfies(pkg, dep)) |
190 | continue; |
191 | if (pkg->installed || pkg->mark) { |
192 | assert(!conflicts(pkg, conf)); |
193 | resolve(next_dep, dep->next, conf); |
194 | continue; |
195 | } |
196 | if (conflicts(pkg, conf)) |
197 | continue; |
198 | level++; |
199 | push(pkg); |
200 | more_deps.refs = pkg->depends; |
201 | more_deps.next = next_dep; |
202 | more_conf.refs = pkg->conflicts; |
203 | more_conf.next = conf; |
204 | resolve(&more_deps, dep->next, &more_conf); |
205 | next_dep = more_deps.next; |
206 | pop(); |
207 | level--; |
208 | } |
209 | } |
210 | |
211 | |
212 | struct pkg **prereq(struct pkg *pkg) |
213 | { |
214 | struct list deps = { |
215 | .refs = pkg->depends, |
216 | .next = NULL |
217 | }; |
218 | |
219 | #if 0 |
220 | /* make sure we don't return NULL if all dependencies are met */ |
221 | if (!stack) { |
222 | stack = alloc_type(struct pkg *); |
223 | stack_max = 1; |
224 | } |
225 | #endif |
226 | /* @@@ make list of pre-existing conflicts */ |
227 | resolve(&deps, NULL, NULL); |
228 | free(stack); |
229 | return best; |
230 | } |
231 |
Branches:
master