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$"); 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, char * from); 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, char * from) 236{ 237 size_t mid; 238 int r; 239 240 if (st == en) 241 errx(1, "%s: no entry for %s", from, 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, from); 251 else 252 return findport(pp, st, mid, name, from); 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, 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); 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 switch (p->recursed) { 309 case 0: 310 /* First time we've seen this port */ 311 p->recursed = 1; 312 break; 313 case 1: 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); 317 case 2: 318 /* This port has already been recursed */ 319 return; 320 } 321 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); 327 328 /* Finished recursing on this port */ 329 p->recursed = 2; 330} 331 332/* Heapify an element in a package list */ 333static void 334heapifypkgs(DEP * d, size_t size, size_t pos) 335{ 336 size_t i = pos; 337 PORT * tmp; 338 339top: 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)) 343 i = 2 * pos + 1; 344 if ((2 * pos + 2 < size) && 345 (strcmp(d[i].p->pkgname, d[2 * pos + 2].p->pkgname) < 0)) 346 i = 2 * pos + 2; 347 348 /* If necessary, swap elements and iterate down the tree. */ 349 if (i != pos) { 350 tmp = d[pos].p; 351 d[pos].p = d[i].p; 352 d[i].p = tmp; 353 pos = i; 354 goto top; 355 } 356} 357 358/* Sort a list of dependent packages in alphabetical order */ 359static void 360sortpkgs(DEP * d, size_t nd) 361{ 362 size_t i; 363 PORT * tmp; 364 365 if (nd == 0) 366 return; 367 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 */ 372 d[0].p = d[i].p; 373 d[i].p = tmp; 374 heapifypkgs(d, i, 0); /* And re-heapify */ 375 } 376} 377 378/* Output an index line for the given port. */ 379static void 380printport(PORT * p) 381{ 382 size_t i; 383 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); 389 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); 395 printf("|"); 396 for (i = 0; i < p->n_rdep; i++) 397 printf("%s%s", i ? " " : "", p->rdep[i].p->pkgname); 398 printf("|"); 399 printf("%s|", p->www); 400 for (i = 0; i < p->n_edep; i++) 401 printf("%s%s", i ? " " : "", p->edep[i].p->pkgname); 402 printf("|"); 403 for (i = 0; i < p->n_pdep; i++) 404 printf("%s%s", i ? " " : "", p->pdep[i].p->pkgname); 405 printf("|"); 406 for (i = 0; i < p->n_fdep; i++) 407 printf("%s%s", i ? " " : "", p->fdep[i].p->pkgname); 408 printf("\n"); 409} 410 411/* 412 * Algorithm: 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). 422 */ 423 424int 425main(int argc, char *argv[]) 426{ 427 FILE * f; 428 char * line; 429 size_t linelen; 430 PORT ** pp; /* Array of pointers to PORTs */ 431 PORT * tmp; 432 size_t pplen; /* Allocated size of array */ 433 size_t i; 434 435 if (argc != 2) 436 usage(); 437 if ((f = fopen(argv[1], "r")) == NULL) 438 err(1, "fopen(%s)", argv[1]); 439 440 pplen = 1024; 441 if ((pp = malloc(pplen * sizeof(PORT *))) == NULL) 442 err(1, "malloc(pp)"); 443 444 /* 445 * 1. Suck in all the data, splitting into fields. 446 */ 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; 451 452 /* Enlarge array if needed */ 453 if (i >= pplen) { 454 pplen *= 2; 455 if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL) 456 err(1, "realloc(pp)"); 457 } 458 459 pp[i] = portify(line); 460 } 461 /* Reallocate to the correct size */ 462 pplen = i; 463 if ((pp = realloc(pp, pplen * sizeof(PORT *))) == NULL) 464 err(1, "realloc(pp)"); 465 466 /* Make sure we actually reached the EOF */ 467 if (!feof(f)) 468 err(1, "fgetln(%s)", argv[1]); 469 /* Close the describes file */ 470 if (fclose(f) != 0) 471 err(1, "fclose(%s)", argv[1]); 472 473 /* 474 * 1a. If there are no ports, there is no INDEX. 475 */ 476 if (pplen == 0) 477 return 0; 478 479 /* 480 * 2. Sort the ports according to port directory. 481 */ 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 */ 486 pp[0] = pp[i]; 487 pp[i] = tmp; 488 heapifyports(pp, i, 0); /* And re-heapify */ 489 } 490 491 /* 492 * 3. Using a binary search, translate each dependency from a 493 * port directory name into a pointer to a port. 494 */ 495 for (i = 0; i < pplen; i++) 496 translateport(pp, pplen, pp[i]); 497 498 /* 499 * 4. Recursively follow dependencies, expanding the lists of 500 * pointers as needed (using realloc). 501 */ 502 for (i = 0; i < pplen; i++) 503 recurse(pp[i]); 504 505 /* 506 * 5. Iterate through the ports, printing them out (remembering 507 * to list the dependent ports in alphabetical order). 508 */ 509 for (i = 0; i < pplen; i++) 510 printport(pp[i]); 511 512 return 0; 513} 514