Root/qpkg/prereq.c

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

Archive Download this file

Branches:
master



interactive