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