2 * Copyright 2005 Colin Percival
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted providing that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
22 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
23 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
27 #include <sys/cdefs.h>
28 __FBSDID("$FreeBSD$");
64 static void usage(void);
65 static char * strdup2(const char *str);
66 static DEP * makelist(char * str, size_t * n);
67 static PORT * portify(char * line);
68 static int portcompare(char * a, char * b);
69 static void heapifyports(PORT **pp, size_t size, size_t pos);
70 static PORT * findport(PORT ** pp, size_t st, size_t en, char * name, char * from);
71 static void translateport(PORT ** pp, size_t pplen, PORT * p);
72 static DEP * recurse_one(DEP * d, size_t * nd);
73 static void recurse(PORT * p);
74 static void heapifypkgs(DEP * d, size_t size, size_t pos);
75 static void sortpkgs(DEP * d, size_t nd);
76 static void printport(PORT * p);
82 fprintf(stderr, "usage: make_index file\n");
88 strdup2(const char *str)
98 /* Take a space-separated list and return an array of (char *) */
100 makelist(char * str, size_t * n)
105 /* No depends at all? */
111 /* Count the number of fields */
113 for (i = 0; str[i] != 0; i++)
117 /* Allocate and fill an array */
118 d = malloc(*n * sizeof(DEP));
120 err(1, "malloc(DEP)");
121 for (i = 0; i < *n; i++) {
122 d[i].name = strdup2(strsep(&str, " "));
124 /* Strip trailing slashes */
125 if (d[i].name[strlen(d[i].name) - 1] == '/')
126 d[i].name[strlen(d[i].name) - 1] = 0;
132 /* Take a port's describe line and split it into fields */
139 /* Verify that line has the right number of fields */
140 for (n = i = 0; line[i] != 0; i++)
144 errx(1, "Port describe line is corrupt:\n%s\n", line);
146 p = malloc(sizeof(PORT));
148 err(1, "malloc(PORT)");
150 p->pkgname = strdup2(strsep(&line, "|"));
151 p->portdir = strdup2(strsep(&line, "|"));
152 p->prefix = strdup2(strsep(&line, "|"));
153 p->comment = strdup2(strsep(&line, "|"));
154 p->pkgdescr = strdup2(strsep(&line, "|"));
155 p->maintainer = strdup2(strsep(&line, "|"));
156 p->categories = strdup2(strsep(&line, "|"));
157 p->edep = makelist(strsep(&line, "|"), &p->n_edep);
158 p->pdep = makelist(strsep(&line, "|"), &p->n_pdep);
159 p->fdep = makelist(strsep(&line, "|"), &p->n_fdep);
160 p->bdep = makelist(strsep(&line, "|"), &p->n_bdep);
161 p->rdep = makelist(strsep(&line, "|"), &p->n_rdep);
162 p->www = strdup2(strsep(&line, "|"));
167 * line will now be equal to NULL -- we counted the field
168 * separators at the top of the function.
174 /* Returns -1, 0, or 1 based on a comparison of the portdir strings */
176 portcompare(char * a, char * b)
180 /* Find first non-matching position */
184 if (a[i] == 0) /* End of strings */
188 /* One string is a prefix of the other */
194 /* One string has a category which is a prefix of the other */
200 /* The two strings are simply different */
207 /* Heapify (PORT *) number pos in a pseudo-heap pp[0]..pp[size - 1] */
209 heapifyports(PORT **pp, size_t size, size_t pos)
215 /* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */
216 if ((2 * pos + 1 < size) &&
217 (portcompare(pp[i]->portdir, pp[2 * pos + 1]->portdir) < 0))
219 if ((2 * pos + 2 < size) &&
220 (portcompare(pp[i]->portdir, pp[2 * pos + 2]->portdir) < 0))
223 /* If necessary, swap elements and iterate down the tree. */
233 /* Translate a port directory name into a (PORT *), and free the name */
235 findport(PORT ** pp, size_t st, size_t en, char * name, char * from)
241 errx(1, "%s: no entry for %s", from, name);
244 r = portcompare(pp[mid]->portdir, name);
250 return findport(pp, mid + 1, en, name, from);
252 return findport(pp, st, mid, name, from);
255 /* Translate all depends from names into PORT *s */
257 translateport(PORT ** pp, size_t pplen, PORT * p)
261 for (i = 0; i < p->n_edep; i++)
262 p->edep[i].p = findport(pp, 0, pplen, p->edep[i].name, p->portdir);
263 for (i = 0; i < p->n_pdep; i++)
264 p->pdep[i].p = findport(pp, 0, pplen, p->pdep[i].name, p->portdir);
265 for (i = 0; i < p->n_fdep; i++)
266 p->fdep[i].p = findport(pp, 0, pplen, p->fdep[i].name, p->portdir);
267 for (i = 0; i < p->n_bdep; i++)
268 p->bdep[i].p = findport(pp, 0, pplen, p->bdep[i].name, p->portdir);
269 for (i = 0; i < p->n_rdep; i++)
270 p->rdep[i].p = findport(pp, 0, pplen, p->rdep[i].name, p->portdir);
273 /* Recurse on one specific depends list */
275 recurse_one(DEP * d, size_t * nd)
277 size_t i, j, k, n, N;
280 for (i = 0; i < n; i++) {
282 for (j = 0; j < d[i].p->n_rdep; j++) {
283 for (k = 0; k < N; k++) {
284 if (d[i].p->rdep[j].p == d[k].p)
291 d = realloc(d, *nd * sizeof(DEP));
293 err(1, "realloc(d)");
295 d[k].p = d[i].p->rdep[j].p;
304 /* Recurse on the depends lists */
308 switch (p->recursed) {
310 /* First time we've seen this port */
314 /* We're in the middle of recursing this port */
315 errx(1, "Circular dependency loop found: %s"
316 " depends upon itself.\n", p->pkgname);
318 /* This port has already been recursed */
322 p->edep = recurse_one(p->edep, &p->n_edep);
323 p->pdep = recurse_one(p->pdep, &p->n_pdep);
324 p->fdep = recurse_one(p->fdep, &p->n_fdep);
325 p->bdep = recurse_one(p->bdep, &p->n_bdep);
326 p->rdep = recurse_one(p->rdep, &p->n_rdep);
328 /* Finished recursing on this port */
332 /* Heapify an element in a package list */
334 heapifypkgs(DEP * d, size_t size, size_t pos)
340 /* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */
341 if ((2 * pos + 1 < size) &&
342 (strcmp(d[i].p->pkgname, d[2 * pos + 1].p->pkgname) < 0))
344 if ((2 * pos + 2 < size) &&
345 (strcmp(d[i].p->pkgname, d[2 * pos + 2].p->pkgname) < 0))
348 /* If necessary, swap elements and iterate down the tree. */
358 /* Sort a list of dependent packages in alphabetical order */
360 sortpkgs(DEP * d, size_t nd)
368 for (i = nd; i > 0; i--)
369 heapifypkgs(d, nd, i - 1); /* Build a heap */
370 for (i = nd - 1; i > 0; i--) {
371 tmp = d[0].p; /* Extract elements */
374 heapifypkgs(d, i, 0); /* And re-heapify */
378 /* Output an index line for the given port. */
384 sortpkgs(p->edep, p->n_edep);
385 sortpkgs(p->pdep, p->n_pdep);
386 sortpkgs(p->fdep, p->n_fdep);
387 sortpkgs(p->bdep, p->n_bdep);
388 sortpkgs(p->rdep, p->n_rdep);
390 printf("%s|%s|%s|%s|%s|%s|%s|",
391 p->pkgname, p->portdir, p->prefix, p->comment, p->pkgdescr,
392 p->maintainer, p->categories);
393 for (i = 0; i < p->n_bdep; i++)
394 printf("%s%s", i ? " " : "", p->bdep[i].p->pkgname);
396 for (i = 0; i < p->n_rdep; i++)
397 printf("%s%s", i ? " " : "", p->rdep[i].p->pkgname);
399 printf("%s|", p->www);
400 for (i = 0; i < p->n_edep; i++)
401 printf("%s%s", i ? " " : "", p->edep[i].p->pkgname);
403 for (i = 0; i < p->n_pdep; i++)
404 printf("%s%s", i ? " " : "", p->pdep[i].p->pkgname);
406 for (i = 0; i < p->n_fdep; i++)
407 printf("%s%s", i ? " " : "", p->fdep[i].p->pkgname);
413 * 1. Suck in all the data, splitting into fields.
414 * 1a. If there are no ports, there is no INDEX.
415 * 2. Sort the ports according to port directory.
416 * 3. Using a binary search, translate each dependency from a
417 * port directory name into a pointer to a port.
418 * 4. Recursively follow dependencies, expanding the lists of
419 * pointers as needed (using realloc).
420 * 5. Iterate through the ports, printing them out (remembering
421 * to list the dependent ports in alphabetical order).
425 main(int argc, char *argv[])
430 PORT ** pp; /* Array of pointers to PORTs */
432 size_t pplen; /* Allocated size of array */
437 if ((f = fopen(argv[1], "r")) == NULL)
438 err(1, "fopen(%s)", argv[1]);
441 if ((pp = malloc(pplen * sizeof(PORT *))) == NULL)
442 err(1, "malloc(pp)");
445 * 1. Suck in all the data, splitting into fields.
447 for(i = 0; (line = fgetln(f, &linelen)) != NULL; i++) {
448 if (line[linelen - 1] != '\n')
449 errx(1, "Unterminated line encountered");
450 line[linelen - 1] = 0;
452 /* Enlarge array if needed */
455 if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL)
456 err(1, "realloc(pp)");
459 pp[i] = portify(line);
461 /* Reallocate to the correct size */
463 if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL)
464 err(1, "realloc(pp)");
466 /* Make sure we actually reached the EOF */
468 err(1, "fgetln(%s)", argv[1]);
469 /* Close the describes file */
471 err(1, "fclose(%s)", argv[1]);
474 * 1a. If there are no ports, there is no INDEX.
480 * 2. Sort the ports according to port directory.
482 for (i = pplen; i > 0; i--)
483 heapifyports(pp, pplen, i - 1); /* Build a heap */
484 for (i = pplen - 1; i > 0; i--) {
485 tmp = pp[0]; /* Extract elements */
488 heapifyports(pp, i, 0); /* And re-heapify */
492 * 3. Using a binary search, translate each dependency from a
493 * port directory name into a pointer to a port.
495 for (i = 0; i < pplen; i++)
496 translateport(pp, pplen, pp[i]);
499 * 4. Recursively follow dependencies, expanding the lists of
500 * pointers as needed (using realloc).
502 for (i = 0; i < pplen; i++)
506 * 5. Iterate through the ports, printing them out (remembering
507 * to list the dependent ports in alphabetical order).
509 for (i = 0; i < pplen; i++)