make_index.c revision 148871
1148871Scperciva/*- 2148871Scperciva * Copyright 2005 Colin Percival 3148871Scperciva * All rights reserved 4148871Scperciva * 5148871Scperciva * Redistribution and use in source and binary forms, with or without 6148871Scperciva * modification, are permitted providing that the following conditions 7148871Scperciva * are met: 8148871Scperciva * 1. Redistributions of source code must retain the above copyright 9148871Scperciva * notice, this list of conditions and the following disclaimer. 10148871Scperciva * 2. Redistributions in binary form must reproduce the above copyright 11148871Scperciva * notice, this list of conditions and the following disclaimer in the 12148871Scperciva * documentation and/or other materials provided with the distribution. 13148871Scperciva * 14148871Scperciva * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 15148871Scperciva * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16148871Scperciva * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17148871Scperciva * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 18148871Scperciva * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19148871Scperciva * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20148871Scperciva * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21148871Scperciva * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 22148871Scperciva * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 23148871Scperciva * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 24148871Scperciva * POSSIBILITY OF SUCH DAMAGE. 25148871Scperciva */ 26148871Scperciva 27148871Scperciva#include <sys/cdefs.h> 28148871Scperciva__FBSDID("$FreeBSD: head/usr.sbin/portsnap/make_index/make_index.c 148871 2005-08-08 20:10:06Z cperciva $"); 29148871Scperciva 30148871Scperciva#include <err.h> 31148871Scperciva#include <stdio.h> 32148871Scperciva#include <stdlib.h> 33148871Scperciva#include <string.h> 34148871Scperciva 35148871Scpercivastruct port; 36148871Scperciva 37148871Scpercivatypedef union { 38148871Scperciva char * name; 39148871Scperciva struct port * p; 40148871Scperciva} DEP; 41148871Scperciva 42148871Scpercivatypedef struct port { 43148871Scperciva char * pkgname; 44148871Scperciva char * portdir; 45148871Scperciva char * prefix; 46148871Scperciva char * comment; 47148871Scperciva char * pkgdescr; 48148871Scperciva char * maintainer; 49148871Scperciva char * categories; 50148871Scperciva size_t n_edep; 51148871Scperciva DEP * edep; 52148871Scperciva size_t n_pdep; 53148871Scperciva DEP * pdep; 54148871Scperciva size_t n_fdep; 55148871Scperciva DEP * fdep; 56148871Scperciva size_t n_bdep; 57148871Scperciva DEP * bdep; 58148871Scperciva size_t n_rdep; 59148871Scperciva DEP * rdep; 60148871Scperciva char * www; 61148871Scperciva int recursed; 62148871Scperciva} PORT; 63148871Scperciva 64148871Scpercivastatic void usage(void); 65148871Scpercivastatic char * strdup2(const char *str); 66148871Scpercivastatic DEP * makelist(char * str, size_t * n); 67148871Scpercivastatic PORT * portify(char * line); 68148871Scpercivastatic int portcompare(char * a, char * b); 69148871Scpercivastatic void heapifyports(PORT **pp, size_t size, size_t pos); 70148871Scpercivastatic PORT * findport(PORT ** pp, size_t st, size_t en, char * name); 71148871Scpercivastatic void translateport(PORT ** pp, size_t pplen, PORT * p); 72148871Scpercivastatic DEP * recurse_one(DEP * d, size_t * nd); 73148871Scpercivastatic void recurse(PORT * p); 74148871Scpercivastatic void heapifypkgs(DEP * d, size_t size, size_t pos); 75148871Scpercivastatic void sortpkgs(DEP * d, size_t nd); 76148871Scpercivastatic void printport(PORT * p); 77148871Scperciva 78148871Scpercivastatic void 79148871Scpercivausage(void) 80148871Scperciva{ 81148871Scperciva 82148871Scperciva fprintf(stderr, "usage: make_index file\n"); 83148871Scperciva exit(1); 84148871Scperciva /* NOTREACHED */ 85148871Scperciva} 86148871Scperciva 87148871Scpercivastatic char * 88148871Scpercivastrdup2(const char *str) 89148871Scperciva{ 90148871Scperciva char * r; 91148871Scperciva 92148871Scperciva r = strdup(str); 93148871Scperciva if (r == NULL) 94148871Scperciva err(1, "strdup"); 95148871Scperciva return r; 96148871Scperciva} 97148871Scperciva 98148871Scperciva/* Take a space-separated list and return an array of (char *) */ 99148871Scpercivastatic DEP * 100148871Scpercivamakelist(char * str, size_t * n) 101148871Scperciva{ 102148871Scperciva DEP * d; 103148871Scperciva size_t i; 104148871Scperciva 105148871Scperciva /* No depends at all? */ 106148871Scperciva if (str[0] == 0) { 107148871Scperciva *n = 0; 108148871Scperciva return NULL; 109148871Scperciva } 110148871Scperciva 111148871Scperciva /* Count the number of fields */ 112148871Scperciva *n = 1; 113148871Scperciva for (i = 0; str[i] != 0; i++) 114148871Scperciva if (str[i] == ' ') 115148871Scperciva (*n)++; 116148871Scperciva 117148871Scperciva /* Allocate and fill an array */ 118148871Scperciva d = malloc(*n * sizeof(DEP)); 119148871Scperciva for (i = 0; i < *n; i++) { 120148871Scperciva d[i].name = strdup2(strsep(&str, " ")); 121148871Scperciva 122148871Scperciva /* Strip trailing slashes */ 123148871Scperciva if (d[i].name[strlen(d[i].name) - 1] == '/') 124148871Scperciva d[i].name[strlen(d[i].name) - 1] = 0; 125148871Scperciva } 126148871Scperciva 127148871Scperciva return d; 128148871Scperciva} 129148871Scperciva 130148871Scperciva/* Take a port's describe line and split it into fields */ 131148871Scpercivastatic PORT * 132148871Scpercivaportify(char * line) 133148871Scperciva{ 134148871Scperciva PORT * p; 135148871Scperciva size_t i, n; 136148871Scperciva 137148871Scperciva /* Verify that line has the right number of fields */ 138148871Scperciva for (n = i = 0; line[i] != 0; i++) 139148871Scperciva if (line[i] == '|') 140148871Scperciva n++; 141148871Scperciva if (n != 12) 142148871Scperciva errx(1, "Port describe line is corrupt:\n%s\n", line); 143148871Scperciva 144148871Scperciva p = malloc(sizeof(PORT)); 145148871Scperciva if (p == NULL) 146148871Scperciva err(1, "malloc(PORT)"); 147148871Scperciva 148148871Scperciva p->pkgname = strdup2(strsep(&line, "|")); 149148871Scperciva p->portdir = strdup2(strsep(&line, "|")); 150148871Scperciva p->prefix = strdup2(strsep(&line, "|")); 151148871Scperciva p->comment = strdup2(strsep(&line, "|")); 152148871Scperciva p->pkgdescr = strdup2(strsep(&line, "|")); 153148871Scperciva p->maintainer = strdup2(strsep(&line, "|")); 154148871Scperciva p->categories = strdup2(strsep(&line, "|")); 155148871Scperciva p->edep = makelist(strsep(&line, "|"), &p->n_edep); 156148871Scperciva p->pdep = makelist(strsep(&line, "|"), &p->n_pdep); 157148871Scperciva p->fdep = makelist(strsep(&line, "|"), &p->n_fdep); 158148871Scperciva p->bdep = makelist(strsep(&line, "|"), &p->n_bdep); 159148871Scperciva p->rdep = makelist(strsep(&line, "|"), &p->n_rdep); 160148871Scperciva p->www = strdup2(strsep(&line, "|")); 161148871Scperciva 162148871Scperciva p->recursed = 0; 163148871Scperciva 164148871Scperciva /* 165148871Scperciva * line will now be equal to NULL -- we counted the field 166148871Scperciva * separators at the top of the function. 167148871Scperciva */ 168148871Scperciva 169148871Scperciva return p; 170148871Scperciva} 171148871Scperciva 172148871Scperciva/* Returns -1, 0, or 1 based on a comparison of the portdir strings */ 173148871Scpercivastatic int 174148871Scpercivaportcompare(char * a, char * b) 175148871Scperciva{ 176148871Scperciva size_t i; 177148871Scperciva 178148871Scperciva /* Find first non-matching position */ 179148871Scperciva for (i = 0; ; i++) { 180148871Scperciva if (a[i] != b[i]) 181148871Scperciva break; 182148871Scperciva if (a[i] == 0) /* End of strings */ 183148871Scperciva return 0; 184148871Scperciva } 185148871Scperciva 186148871Scperciva /* One string is a prefix of the other */ 187148871Scperciva if (a[i] == 0) 188148871Scperciva return -1; 189148871Scperciva if (b[i] == 0) 190148871Scperciva return 1; 191148871Scperciva 192148871Scperciva /* One string has a category which is a prefix of the other */ 193148871Scperciva if (a[i] == '/') 194148871Scperciva return -1; 195148871Scperciva if (b[i] == '/') 196148871Scperciva return 1; 197148871Scperciva 198148871Scperciva /* The two strings are simply different */ 199148871Scperciva if (a[i] < b[i]) 200148871Scperciva return -1; 201148871Scperciva else 202148871Scperciva return 1; 203148871Scperciva} 204148871Scperciva 205148871Scperciva/* Heapify (PORT *) number pos in a pseudo-heap pp[0]..pp[size - 1] */ 206148871Scpercivastatic void 207148871Scpercivaheapifyports(PORT **pp, size_t size, size_t pos) 208148871Scperciva{ 209148871Scperciva size_t i = pos; 210148871Scperciva PORT * tmp; 211148871Scperciva 212148871Scpercivatop: 213148871Scperciva /* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */ 214148871Scperciva if ((2 * pos + 1 < size) && 215148871Scperciva (portcompare(pp[i]->portdir, pp[2 * pos + 1]->portdir) < 0)) 216148871Scperciva i = 2 * pos + 1; 217148871Scperciva if ((2 * pos + 2 < size) && 218148871Scperciva (portcompare(pp[i]->portdir, pp[2 * pos + 2]->portdir) < 0)) 219148871Scperciva i = 2 * pos + 2; 220148871Scperciva 221148871Scperciva /* If necessary, swap elements and iterate down the tree. */ 222148871Scperciva if (i != pos) { 223148871Scperciva tmp = pp[pos]; 224148871Scperciva pp[pos] = pp[i]; 225148871Scperciva pp[i] = tmp; 226148871Scperciva pos = i; 227148871Scperciva goto top; 228148871Scperciva } 229148871Scperciva} 230148871Scperciva 231148871Scperciva/* Translate a port directory name into a (PORT *), and free the name */ 232148871Scpercivastatic PORT * 233148871Scpercivafindport(PORT ** pp, size_t st, size_t en, char * name) 234148871Scperciva{ 235148871Scperciva size_t mid; 236148871Scperciva int r; 237148871Scperciva 238148871Scperciva if (st == en) 239148871Scperciva errx(1, "Unresolved dependency: %s", name); 240148871Scperciva 241148871Scperciva mid = (st + en) / 2; 242148871Scperciva r = portcompare(pp[mid]->portdir, name); 243148871Scperciva 244148871Scperciva if (r == 0) { 245148871Scperciva free(name); 246148871Scperciva return pp[mid]; 247148871Scperciva } else if (r < 0) 248148871Scperciva return findport(pp, mid + 1, en, name); 249148871Scperciva else 250148871Scperciva return findport(pp, st, mid, name); 251148871Scperciva} 252148871Scperciva 253148871Scperciva/* Translate all depends from names into PORT *s */ 254148871Scpercivastatic void 255148871Scpercivatranslateport(PORT ** pp, size_t pplen, PORT * p) 256148871Scperciva{ 257148871Scperciva size_t i; 258148871Scperciva 259148871Scperciva for (i = 0; i < p->n_edep; i++) 260148871Scperciva p->edep[i].p = findport(pp, 0, pplen, p->edep[i].name); 261148871Scperciva for (i = 0; i < p->n_pdep; i++) 262148871Scperciva p->pdep[i].p = findport(pp, 0, pplen, p->pdep[i].name); 263148871Scperciva for (i = 0; i < p->n_fdep; i++) 264148871Scperciva p->fdep[i].p = findport(pp, 0, pplen, p->fdep[i].name); 265148871Scperciva for (i = 0; i < p->n_bdep; i++) 266148871Scperciva p->bdep[i].p = findport(pp, 0, pplen, p->bdep[i].name); 267148871Scperciva for (i = 0; i < p->n_rdep; i++) 268148871Scperciva p->rdep[i].p = findport(pp, 0, pplen, p->rdep[i].name); 269148871Scperciva} 270148871Scperciva 271148871Scperciva/* Recurse on one specific depends list */ 272148871Scpercivastatic DEP * 273148871Scpercivarecurse_one(DEP * d, size_t * nd) 274148871Scperciva{ 275148871Scperciva size_t i, j, k, n, N; 276148871Scperciva 277148871Scperciva N = n = *nd; 278148871Scperciva for (i = 0; i < n; i++) { 279148871Scperciva recurse(d[i].p); 280148871Scperciva for (j = 0; j < d[i].p->n_rdep; j++) { 281148871Scperciva for (k = 0; k < N; k++) { 282148871Scperciva if (d[i].p->rdep[j].p == d[k].p) 283148871Scperciva break; 284148871Scperciva } 285148871Scperciva if (k == N) { 286148871Scperciva N++; 287148871Scperciva if (N >= *nd) { 288148871Scperciva *nd += *nd; 289148871Scperciva d = realloc(d, *nd * sizeof(DEP)); 290148871Scperciva if (d == NULL) 291148871Scperciva err(1, "realloc(d)"); 292148871Scperciva } 293148871Scperciva d[k].p = d[i].p->rdep[j].p; 294148871Scperciva } 295148871Scperciva } 296148871Scperciva } 297148871Scperciva *nd = N; 298148871Scperciva 299148871Scperciva return d; 300148871Scperciva} 301148871Scperciva 302148871Scperciva/* Recurse on the depends lists */ 303148871Scpercivastatic void 304148871Scpercivarecurse(PORT * p) 305148871Scperciva{ 306148871Scperciva if (p->recursed != 0) 307148871Scperciva return; 308148871Scperciva p->recursed = 1; 309148871Scperciva 310148871Scperciva p->edep = recurse_one(p->edep, &p->n_edep); 311148871Scperciva p->pdep = recurse_one(p->pdep, &p->n_pdep); 312148871Scperciva p->fdep = recurse_one(p->fdep, &p->n_fdep); 313148871Scperciva p->bdep = recurse_one(p->bdep, &p->n_bdep); 314148871Scperciva p->rdep = recurse_one(p->rdep, &p->n_rdep); 315148871Scperciva} 316148871Scperciva 317148871Scperciva/* Heapify an element in a package list */ 318148871Scpercivastatic void 319148871Scpercivaheapifypkgs(DEP * d, size_t size, size_t pos) 320148871Scperciva{ 321148871Scperciva size_t i = pos; 322148871Scperciva PORT * tmp; 323148871Scperciva 324148871Scpercivatop: 325148871Scperciva /* Find the largest value out of {pos, 2*pos+1, 2*pos+2} */ 326148871Scperciva if ((2 * pos + 1 < size) && 327148871Scperciva (strcmp(d[i].p->pkgname, d[2 * pos + 1].p->pkgname) < 0)) 328148871Scperciva i = 2 * pos + 1; 329148871Scperciva if ((2 * pos + 2 < size) && 330148871Scperciva (strcmp(d[i].p->pkgname, d[2 * pos + 2].p->pkgname) < 0)) 331148871Scperciva i = 2 * pos + 2; 332148871Scperciva 333148871Scperciva /* If necessary, swap elements and iterate down the tree. */ 334148871Scperciva if (i != pos) { 335148871Scperciva tmp = d[pos].p; 336148871Scperciva d[pos].p = d[i].p; 337148871Scperciva d[i].p = tmp; 338148871Scperciva pos = i; 339148871Scperciva goto top; 340148871Scperciva } 341148871Scperciva} 342148871Scperciva 343148871Scperciva/* Sort a list of dependent packages in alphabetical order */ 344148871Scpercivastatic void 345148871Scpercivasortpkgs(DEP * d, size_t nd) 346148871Scperciva{ 347148871Scperciva size_t i; 348148871Scperciva PORT * tmp; 349148871Scperciva 350148871Scperciva if (nd == 0) 351148871Scperciva return; 352148871Scperciva 353148871Scperciva for (i = nd; i > 0; i--) 354148871Scperciva heapifypkgs(d, nd, i - 1); /* Build a heap */ 355148871Scperciva for (i = nd - 1; i > 0; i--) { 356148871Scperciva tmp = d[0].p; /* Extract elements */ 357148871Scperciva d[0].p = d[i].p; 358148871Scperciva d[i].p = tmp; 359148871Scperciva heapifypkgs(d, i, 0); /* And re-heapify */ 360148871Scperciva } 361148871Scperciva} 362148871Scperciva 363148871Scperciva/* Output an index line for the given port. */ 364148871Scpercivastatic void 365148871Scpercivaprintport(PORT * p) 366148871Scperciva{ 367148871Scperciva size_t i; 368148871Scperciva 369148871Scperciva sortpkgs(p->edep, p->n_edep); 370148871Scperciva sortpkgs(p->pdep, p->n_pdep); 371148871Scperciva sortpkgs(p->fdep, p->n_fdep); 372148871Scperciva sortpkgs(p->bdep, p->n_bdep); 373148871Scperciva sortpkgs(p->rdep, p->n_rdep); 374148871Scperciva 375148871Scperciva printf("%s|%s|%s|%s|%s|%s|%s|", 376148871Scperciva p->pkgname, p->portdir, p->prefix, p->comment, p->pkgdescr, 377148871Scperciva p->maintainer, p->categories); 378148871Scperciva for (i = 0; i < p->n_bdep; i++) 379148871Scperciva printf("%s%s", i ? " " : "", p->bdep[i].p->pkgname); 380148871Scperciva printf("|"); 381148871Scperciva for (i = 0; i < p->n_rdep; i++) 382148871Scperciva printf("%s%s", i ? " " : "", p->rdep[i].p->pkgname); 383148871Scperciva printf("|"); 384148871Scperciva printf("%s|", p->www); 385148871Scperciva for (i = 0; i < p->n_edep; i++) 386148871Scperciva printf("%s%s", i ? " " : "", p->edep[i].p->pkgname); 387148871Scperciva printf("|"); 388148871Scperciva for (i = 0; i < p->n_pdep; i++) 389148871Scperciva printf("%s%s", i ? " " : "", p->pdep[i].p->pkgname); 390148871Scperciva printf("|"); 391148871Scperciva for (i = 0; i < p->n_fdep; i++) 392148871Scperciva printf("%s%s", i ? " " : "", p->fdep[i].p->pkgname); 393148871Scperciva printf("\n"); 394148871Scperciva} 395148871Scperciva 396148871Scperciva/* 397148871Scperciva * Algorithm: 398148871Scperciva * 1. Suck in all the data, splitting into fields. 399148871Scperciva * 2. Sort the ports according to port directory. 400148871Scperciva * 3. Using a binary search, translate each dependency from a 401148871Scperciva * port directory name into a pointer to a port. 402148871Scperciva * 4. Recursively follow dependencies, expanding the lists of 403148871Scperciva * pointers as needed (using realloc). 404148871Scperciva * 5. Iterate through the ports, printing them out (remembering 405148871Scperciva * to list the dependent ports in alphabetical order). 406148871Scperciva */ 407148871Scperciva 408148871Scpercivaint 409148871Scpercivamain(int argc, char *argv[]) 410148871Scperciva{ 411148871Scperciva FILE * f; 412148871Scperciva char * line; 413148871Scperciva size_t linelen; 414148871Scperciva PORT ** pp; /* Array of pointers to PORTs */ 415148871Scperciva PORT * tmp; 416148871Scperciva size_t pplen; /* Allocated size of array */ 417148871Scperciva size_t i; 418148871Scperciva 419148871Scperciva if (argc != 2) 420148871Scperciva usage(); 421148871Scperciva if ((f = fopen(argv[1], "r")) == NULL) 422148871Scperciva err(1, "fopen(%s)", argv[1]); 423148871Scperciva 424148871Scperciva pplen = 1024; 425148871Scperciva if ((pp = malloc(pplen * sizeof(PORT *))) == NULL) 426148871Scperciva err(1, "malloc(pp)"); 427148871Scperciva 428148871Scperciva /* 429148871Scperciva * 1. Suck in all the data, splitting into fields. 430148871Scperciva */ 431148871Scperciva for(i = 0; (line = fgetln(f, &linelen)) != NULL; i++) { 432148871Scperciva if (line[linelen - 1] != '\n') 433148871Scperciva errx(1, "Unterminated line encountered"); 434148871Scperciva line[linelen - 1] = 0; 435148871Scperciva 436148871Scperciva /* Enlarge array if needed */ 437148871Scperciva if (i >= pplen) { 438148871Scperciva pplen *= 2; 439148871Scperciva if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL) 440148871Scperciva err(1, "realloc(pp)"); 441148871Scperciva } 442148871Scperciva 443148871Scperciva pp[i] = portify(line); 444148871Scperciva } 445148871Scperciva /* Reallocate to the correct size */ 446148871Scperciva pplen = i; 447148871Scperciva if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL) 448148871Scperciva err(1, "realloc(pp)"); 449148871Scperciva 450148871Scperciva /* Make sure we actually reached the EOF */ 451148871Scperciva if (!feof(f)) 452148871Scperciva err(1, "fgetln(%s)", argv[1]); 453148871Scperciva /* Close the describes file */ 454148871Scperciva if (fclose(f) != 0) 455148871Scperciva err(1, "fclose(%s)", argv[1]); 456148871Scperciva 457148871Scperciva /* 458148871Scperciva * 2. Sort the ports according to port directory. 459148871Scperciva */ 460148871Scperciva for (i = pplen; i > 0; i--) 461148871Scperciva heapifyports(pp, pplen, i - 1); /* Build a heap */ 462148871Scperciva for (i = pplen - 1; i > 0; i--) { 463148871Scperciva tmp = pp[0]; /* Extract elements */ 464148871Scperciva pp[0] = pp[i]; 465148871Scperciva pp[i] = tmp; 466148871Scperciva heapifyports(pp, i, 0); /* And re-heapify */ 467148871Scperciva } 468148871Scperciva 469148871Scperciva /* 470148871Scperciva * 3. Using a binary search, translate each dependency from a 471148871Scperciva * port directory name into a pointer to a port. 472148871Scperciva */ 473148871Scperciva for (i = 0; i < pplen; i++) 474148871Scperciva translateport(pp, pplen, pp[i]); 475148871Scperciva 476148871Scperciva /* 477148871Scperciva * 4. Recursively follow dependencies, expanding the lists of 478148871Scperciva * pointers as needed (using realloc). 479148871Scperciva */ 480148871Scperciva for (i = 0; i < pplen; i++) 481148871Scperciva recurse(pp[i]); 482148871Scperciva 483148871Scperciva /* 484148871Scperciva * 5. Iterate through the ports, printing them out (remembering 485148871Scperciva * to list the dependent ports in alphabetical order). 486148871Scperciva */ 487148871Scperciva for (i = 0; i < pplen; i++) 488148871Scperciva printport(pp[i]); 489148871Scperciva 490148871Scperciva return 0; 491148871Scperciva} 492