Root/qpkg/prereq.c

Source at commit 2787a45c436c35fc6fd0ed452903ad045fe9571d created 9 years 20 days 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
12struct list {
13    const struct ref *refs;
14    struct list *next;
15};
16
17
18static struct pkg **best = NULL;
19static struct pkg **stack = NULL;
20static int n_best; /* undefined if best == NULL */
21static int n_stack = 0;
22static int stack_max = 0;
23
24
25#define ID2S(id) (int) (id)->len, (id)->s
26
27
28static 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
44static 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
86static 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
101static 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
119static void pop(void)
120{
121    assert(n_stack);
122    n_stack--;
123    stack[n_stack]->mark = 0;
124}
125
126
127static 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
152static int conflicts(const struct pkg *pkg, const struct list *conf)
153{
154    /* @@@ */
155    return 0;
156}
157
158
159static void resolve(struct list *next_dep, const struct ref *dep,
160    struct list *conf)
161{
162static 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
181fprintf(stderr, "%*s", level, "");
182fprintf(stderr, "%.*s %p", ID2S(pkg->id), pkg);
183if (pkg->version)
184fprintf(stderr, " %.*s", ID2S(pkg->version));
185if (pkg->mark) fprintf(stderr, " +");
186if (pkg->installed) fprintf(stderr, " ***");
187fprintf(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;
198level++;
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();
207level--;
208    }
209}
210
211
212struct 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

Archive Download this file

Branches:
master



interactive