make_index.c revision 148885 
1/*-
2 * Copyright 2005 Colin Percival
3 * All rights reserved
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted providing that the following conditions
7 * are met:
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.
13 *
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.
25 */
26
27#include <sys/cdefs.h>
28__FBSDID("$FreeBSD: head/usr.sbin/portsnap/make_index/make_index.c 148885 2005-08-09 09:49:01Z cperciva $");
29
30#include <err.h>
31#include <stdio.h>
32#include <stdlib.h>
33#include <string.h>
34
35struct port;
36
37typedef union {
38	char * name;
39	struct port * p;
40} DEP;
41
42typedef struct port {
43	char * pkgname;
44	char * portdir;
45	char * prefix;
46	char * comment;
47	char * pkgdescr;
48	char * maintainer;
49	char * categories;
50	size_t n_edep;
51	DEP * edep;
52	size_t n_pdep;
53	DEP * pdep;
54	size_t n_fdep;
55	DEP * fdep;
56	size_t n_bdep;
57	DEP * bdep;
58	size_t n_rdep;
59	DEP * rdep;
60	char * www;
61	int recursed;
62} PORT;
63
64static void usage(void);
65static char * strdup2(const char *str);
66static DEP * makelist(char * str, size_t * n);
67static PORT * portify(char * line);
68static int portcompare(char * a, char * b);
69static void heapifyports(PORT **pp, size_t size, size_t pos);
70static PORT * findport(PORT ** pp, size_t st, size_t en, char * name);
71static void translateport(PORT ** pp, size_t pplen, PORT * p);
72static DEP * recurse_one(DEP * d, size_t * nd);
73static void recurse(PORT * p);
74static void heapifypkgs(DEP * d, size_t size, size_t pos);
75static void sortpkgs(DEP * d, size_t nd);
76static void printport(PORT * p);
77
78static void
79usage(void)
80{
81
82	fprintf(stderr, "usage: make_index file\n");
83	exit(1);
84	/* NOTREACHED */
85}
86
87static char *
88strdup2(const char *str)
89{
90	char * r;
91
92	r = strdup(str);
93	if (r == NULL)
94		err(1, "strdup");
95	return r;
96}
97
98/* Take a space-separated list and return an array of (char *) */
99static DEP *
100makelist(char * str, size_t * n)
101{
102	DEP * d;
103	size_t i;
104
105	/* No depends at all? */
106	if (str[0] == 0) {
107		*n = 0;
108		return NULL;
109	}
110
111	/* Count the number of fields */
112	*n = 1;
113	for (i = 0; str[i] != 0; i++)
114		if (str[i] == ' ')
115			(*n)++;
116
117	/* Allocate and fill an array */
118	d = malloc(*n * sizeof(DEP));
119	if (d == NULL)
120		err(1, "malloc(DEP)");
121	for (i = 0; i < *n; i++) {
122		d[i].name = strdup2(strsep(&str, " "));
123
124		/* Strip trailing slashes */
125		if (d[i].name[strlen(d[i].name) - 1] == '/')
126			d[i].name[strlen(d[i].name) - 1] = 0;
127	}
128
129	return d;
130}
131
132/* Take a port's describe line and split it into fields */
133static PORT *
134portify(char * line)
135{
136	PORT * p;
137	size_t i, n;
138
139	/* Verify that line has the right number of fields */
140	for (n = i = 0; line[i] != 0; i++)
141		if (line[i] == '|')
142			n++;
143	if (n != 12)
144		errx(1, "Port describe line is corrupt:\n%s\n", line);
145
146	p = malloc(sizeof(PORT));
147	if (p == NULL)
148		err(1, "malloc(PORT)");
149
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, "|"));
163
164	p->recursed = 0;
165
166	/*
167	 * line will now be equal to NULL -- we counted the field
168	 * separators at the top of the function.
169	 */
170
171	return p;
172}
173
174/* Returns -1, 0, or 1 based on a comparison of the portdir strings */
175static int
176portcompare(char * a, char * b)
177{
178	size_t i;
179
180	/* Find first non-matching position */
181	for (i = 0; ; i++) {
182		if (a[i] != b[i])
183			break;
184		if (a[i] == 0)			/* End of strings */
185			return 0;
186	}
187
188	/* One string is a prefix of the other */
189	if (a[i] == 0)
190		return -1;
191	if (b[i] == 0)
192		return 1;
193
194	/* One string has a category which is a prefix of the other */
195	if (a[i] == '/')
196		return -1;
197	if (b[i] == '/')
198		return 1;
199
200	/* The two strings are simply different */
201	if (a[i] < b[i])
202		return -1;
203	else
204		return 1;
205}
206
207/* Heapify (PORT *) number pos in a pseudo-heap pp[0]..pp[size - 1] */
208static void
209heapifyports(PORT **pp, size_t size, size_t pos)
210{
211	size_t i = pos;
212	PORT * tmp;
213
214top:
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))
218		i = 2 * pos + 1;
219	if ((2 * pos + 2 < size) &&
220	    (portcompare(pp[i]->portdir, pp[2 * pos + 2]->portdir) < 0))
221		i = 2 * pos + 2;
222
223	/* If necessary, swap elements and iterate down the tree. */
224	if (i != pos) {
225		tmp = pp[pos];
226		pp[pos] = pp[i];
227		pp[i] = tmp;
228		pos = i;
229		goto top;
230	}
231}
232
233/* Translate a port directory name into a (PORT *), and free the name */
234static PORT *
235findport(PORT ** pp, size_t st, size_t en, char * name)
236{
237	size_t mid;
238	int r;
239
240	if (st == en)
241		errx(1, "Unresolved dependency: %s", name);
242
243	mid = (st + en) / 2;
244	r = portcompare(pp[mid]->portdir, name);
245
246	if (r == 0) {
247		free(name);
248		return pp[mid];
249	} else if (r < 0)
250		return findport(pp, mid + 1, en, name);
251	else
252		return findport(pp, st, mid, name);
253}
254
255/* Translate all depends from names into PORT *s */
256static void
257translateport(PORT ** pp, size_t pplen, PORT * p)
258{
259	size_t i;
260
261	for (i = 0; i < p->n_edep; i++)
262		p->edep[i].p = findport(pp, 0, pplen, p->edep[i].name);
263	for (i = 0; i < p->n_pdep; i++)
264		p->pdep[i].p = findport(pp, 0, pplen, p->pdep[i].name);
265	for (i = 0; i < p->n_fdep; i++)
266		p->fdep[i].p = findport(pp, 0, pplen, p->fdep[i].name);
267	for (i = 0; i < p->n_bdep; i++)
268		p->bdep[i].p = findport(pp, 0, pplen, p->bdep[i].name);
269	for (i = 0; i < p->n_rdep; i++)
270		p->rdep[i].p = findport(pp, 0, pplen, p->rdep[i].name);
271}
272
273/* Recurse on one specific depends list */
274static DEP *
275recurse_one(DEP * d, size_t * nd)
276{
277	size_t i, j, k, n, N;
278
279	N = n = *nd;
280	for (i = 0; i < n; i++) {
281		recurse(d[i].p);
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)
285					break;
286			}
287			if (k == N) {
288				N++;
289				if (N >= *nd) {
290					*nd += *nd;
291					d = realloc(d, *nd * sizeof(DEP));
292					if (d == NULL)
293						err(1, "realloc(d)");
294				}
295				d[k].p = d[i].p->rdep[j].p;
296			}
297		}
298	}
299	*nd = N;
300
301	return d;
302}
303
304/* Recurse on the depends lists */
305static void
306recurse(PORT * p)
307{
308	if (p->recursed != 0)
309		return;
310	p->recursed = 1;
311
312	p->edep = recurse_one(p->edep, &p->n_edep);
313	p->pdep = recurse_one(p->pdep, &p->n_pdep);
314	p->fdep = recurse_one(p->fdep, &p->n_fdep);
315	p->bdep = recurse_one(p->bdep, &p->n_bdep);
316	p->rdep = recurse_one(p->rdep, &p->n_rdep);
317}
318
319/* Heapify an element in a package list */
320static void
321heapifypkgs(DEP * d, size_t size, size_t pos)
322{
323	size_t i = pos;
324	PORT * tmp;
325
326top:
327	/* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */
328	if ((2 * pos + 1 < size) &&
329	    (strcmp(d[i].p->pkgname, d[2 * pos + 1].p->pkgname) < 0))
330		i = 2 * pos + 1;
331	if ((2 * pos + 2 < size) &&
332	    (strcmp(d[i].p->pkgname, d[2 * pos + 2].p->pkgname) < 0))
333		i = 2 * pos + 2;
334
335	/* If necessary, swap elements and iterate down the tree. */
336	if (i != pos) {
337		tmp = d[pos].p;
338		d[pos].p = d[i].p;
339		d[i].p = tmp;
340		pos = i;
341		goto top;
342	}
343}
344
345/* Sort a list of dependent packages in alphabetical order */
346static void
347sortpkgs(DEP * d, size_t nd)
348{
349	size_t i;
350	PORT * tmp;
351
352	if (nd == 0)
353		return;
354
355	for (i = nd; i > 0; i--)
356		heapifypkgs(d, nd, i - 1);	/* Build a heap */
357	for (i = nd - 1; i > 0; i--) {
358		tmp = d[0].p;			/* Extract elements */
359		d[0].p = d[i].p;
360		d[i].p = tmp;
361		heapifypkgs(d, i, 0);		/* And re-heapify */
362	}
363}
364
365/* Output an index line for the given port. */
366static void
367printport(PORT * p)
368{
369	size_t i;
370
371	sortpkgs(p->edep, p->n_edep);
372	sortpkgs(p->pdep, p->n_pdep);
373	sortpkgs(p->fdep, p->n_fdep);
374	sortpkgs(p->bdep, p->n_bdep);
375	sortpkgs(p->rdep, p->n_rdep);
376
377	printf("%s|%s|%s|%s|%s|%s|%s|",
378	    p->pkgname, p->portdir, p->prefix, p->comment, p->pkgdescr,
379	    p->maintainer, p->categories);
380	for (i = 0; i < p->n_bdep; i++)
381		printf("%s%s", i ? " " : "", p->bdep[i].p->pkgname);
382	printf("|");
383	for (i = 0; i < p->n_rdep; i++)
384		printf("%s%s", i ? " " : "", p->rdep[i].p->pkgname);
385	printf("|");
386	printf("%s|", p->www);
387	for (i = 0; i < p->n_edep; i++)
388		printf("%s%s", i ? " " : "", p->edep[i].p->pkgname);
389	printf("|");
390	for (i = 0; i < p->n_pdep; i++)
391		printf("%s%s", i ? " " : "", p->pdep[i].p->pkgname);
392	printf("|");
393	for (i = 0; i < p->n_fdep; i++)
394		printf("%s%s", i ? " " : "", p->fdep[i].p->pkgname);
395	printf("\n");
396}
397
398/*
399 * Algorithm:
400 * 1. Suck in all the data, splitting into fields.
401 * 2. Sort the ports according to port directory.
402 * 3. Using a binary search, translate each dependency from a
403 * port directory name into a pointer to a port.
404 * 4. Recursively follow dependencies, expanding the lists of
405 * pointers as needed (using realloc).
406 * 5. Iterate through the ports, printing them out (remembering
407 * to list the dependent ports in alphabetical order).
408 */
409
410int
411main(int argc, char *argv[])
412{
413	FILE * f;
414	char * line;
415	size_t linelen;
416	PORT ** pp;	/* Array of pointers to PORTs */
417	PORT * tmp;
418	size_t pplen;	/* Allocated size of array */
419	size_t i;
420
421	if (argc != 2)
422		usage();
423	if ((f = fopen(argv[1], "r")) == NULL)
424		err(1, "fopen(%s)", argv[1]);
425
426	pplen = 1024;
427	if ((pp = malloc(pplen * sizeof(PORT *))) == NULL)
428		err(1, "malloc(pp)");
429
430	/*
431	 * 1. Suck in all the data, splitting into fields.
432	 */
433	for(i = 0; (line = fgetln(f, &linelen)) != NULL; i++) {
434		if (line[linelen - 1] != '\n')
435			errx(1, "Unterminated line encountered");
436		line[linelen - 1] = 0;
437
438		/* Enlarge array if needed */
439		if (i >= pplen) {
440			pplen *= 2;
441			if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL)
442				err(1, "realloc(pp)");
443		}
444
445		pp[i] = portify(line);
446	}
447	/* Reallocate to the correct size */
448	pplen = i;
449	if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL)
450		err(1, "realloc(pp)");
451
452	/* Make sure we actually reached the EOF */
453	if (!feof(f))
454		err(1, "fgetln(%s)", argv[1]);
455	/* Close the describes file */
456	if (fclose(f) != 0)
457		err(1, "fclose(%s)", argv[1]);
458
459	/*
460	 * 2. Sort the ports according to port directory.
461	 */
462	for (i = pplen; i > 0; i--)
463		heapifyports(pp, pplen, i - 1);	/* Build a heap */
464	for (i = pplen - 1; i > 0; i--) {
465		tmp = pp[0];			/* Extract elements */
466		pp[0] = pp[i];
467		pp[i] = tmp;
468		heapifyports(pp, i, 0);		/* And re-heapify */
469	}
470
471	/*
472	 * 3. Using a binary search, translate each dependency from a
473	 * port directory name into a pointer to a port.
474	 */
475	for (i = 0; i < pplen; i++)
476		translateport(pp, pplen, pp[i]);
477
478	/*
479	 * 4. Recursively follow dependencies, expanding the lists of
480	 * pointers as needed (using realloc).
481	 */
482	for (i = 0; i < pplen; i++)
483		recurse(pp[i]);
484
485	/*
486	 * 5. Iterate through the ports, printing them out (remembering
487	 * to list the dependent ports in alphabetical order).
488	 */
489	for (i = 0; i < pplen; i++)
490		printport(pp[i]);
491
492	return 0;
493}
494