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