1 /* $NetBSD: spec.c,v 1.75 2009/04/11 14:32:51 apb Exp $ */ 2 3 /*- 4 * Copyright (c) 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided 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 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32 /*- 33 * Copyright (c) 2001-2004 The NetBSD Foundation, Inc. 34 * All rights reserved. 35 * 36 * This code is derived from software contributed to The NetBSD Foundation 37 * by Luke Mewburn of Wasabi Systems. 38 * 39 * Redistribution and use in source and binary forms, with or without 40 * modification, are permitted provided that the following conditions 41 * are met: 42 * 1. Redistributions of source code must retain the above copyright 43 * notice, this list of conditions and the following disclaimer. 44 * 2. Redistributions in binary form must reproduce the above copyright 45 * notice, this list of conditions and the following disclaimer in the 46 * documentation and/or other materials provided with the distribution. 47 * 48 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 49 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 50 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 51 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 52 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 53 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 54 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 55 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 56 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 57 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 58 * POSSIBILITY OF SUCH DAMAGE. 59 */ 60 61 #if HAVE_NBTOOL_CONFIG_H 62 #include "nbtool_config.h" 63 #endif 64 65 #include <sys/cdefs.h> 66 #if defined(__RCSID) && !defined(lint) 67 #if 0 68 static char sccsid[] = "@(#)spec.c 8.2 (Berkeley) 4/28/95"; 69 #else 70 __RCSID("$NetBSD: spec.c,v 1.75 2009/04/11 14:32:51 apb Exp $"); 71 #endif 72 #endif /* not lint */ 73 74 #include <sys/param.h> 75 #include <sys/stat.h> 76 77 #include <ctype.h> 78 #include <errno.h> 79 #include <grp.h> 80 #include <pwd.h> 81 #include <stdio.h> 82 #include <stdlib.h> 83 #include <string.h> 84 #include <unistd.h> 85 #include <vis.h> 86 #include <util.h> 87 88 #include "extern.h" 89 #include "pack_dev.h" 90 91 size_t mtree_lineno; /* Current spec line number */ 92 int mtree_Mflag; /* Merge duplicate entries */ 93 int mtree_Wflag; /* Don't "whack" permissions */ 94 int mtree_Sflag; /* Sort entries */ 95 96 static dev_t parsedev(char *); 97 static void replacenode(NODE *, NODE *); 98 static void set(char *, NODE *); 99 static void unset(char *, NODE *); 100 static void addchild(NODE *, NODE *); 101 static int nodecmp(const NODE *, const NODE *); 102 103 #define REPLACEPTR(x,v) do { if ((x)) free((x)); (x) = (v); } while (0) 104 105 NODE * 106 spec(FILE *fp) 107 { 108 NODE *centry, *last, *pathparent, *cur; 109 char *p, *e, *next; 110 NODE ginfo, *root; 111 char *buf, *tname, *ntname; 112 size_t tnamelen, plen; 113 114 root = NULL; 115 centry = last = NULL; 116 tname = NULL; 117 tnamelen = 0; 118 memset(&ginfo, 0, sizeof(ginfo)); 119 for (mtree_lineno = 0; 120 (buf = fparseln(fp, NULL, &mtree_lineno, NULL, 121 FPARSELN_UNESCCOMM)); 122 free(buf)) { 123 /* Skip leading whitespace. */ 124 for (p = buf; *p && isspace((unsigned char)*p); ++p) 125 continue; 126 127 /* If nothing but whitespace, continue. */ 128 if (!*p) 129 continue; 130 131 #ifdef DEBUG 132 fprintf(stderr, "line %lu: {%s}\n", 133 (u_long)mtree_lineno, p); 134 #endif 135 /* Grab file name, "$", "set", or "unset". */ 136 next = buf; 137 while ((p = strsep(&next, " \t")) != NULL && *p == '\0') 138 continue; 139 if (p == NULL) 140 mtree_err("missing field"); 141 142 if (p[0] == '/') { 143 if (strcmp(p + 1, "set") == 0) 144 set(next, &ginfo); 145 else if (strcmp(p + 1, "unset") == 0) 146 unset(next, &ginfo); 147 else 148 mtree_err("invalid specification `%s'", p); 149 continue; 150 } 151 152 if (strcmp(p, "..") == 0) { 153 /* Don't go up, if haven't gone down. */ 154 if (root == NULL) 155 goto noparent; 156 if (last->type != F_DIR || last->flags & F_DONE) { 157 if (last == root) 158 goto noparent; 159 last = last->parent; 160 } 161 last->flags |= F_DONE; 162 continue; 163 164 noparent: mtree_err("no parent node"); 165 } 166 167 plen = strlen(p) + 1; 168 if (plen > tnamelen) { 169 if ((ntname = realloc(tname, plen)) == NULL) 170 mtree_err("realloc: %s", strerror(errno)); 171 tname = ntname; 172 tnamelen = plen; 173 } 174 if (strunvis(tname, p) == -1) 175 mtree_err("strunvis failed on `%s'", p); 176 p = tname; 177 178 pathparent = NULL; 179 if (strchr(p, '/') != NULL) { 180 cur = root; 181 for (; (e = strchr(p, '/')) != NULL; p = e+1) { 182 if (p == e) 183 continue; /* handle // */ 184 *e = '\0'; 185 if (strcmp(p, ".") != 0) { 186 while (cur && 187 strcmp(cur->name, p) != 0) { 188 cur = cur->next; 189 } 190 } 191 if (cur == NULL || cur->type != F_DIR) { 192 mtree_err("%s: %s", tname, 193 "missing directory in specification"); 194 } 195 *e = '/'; 196 pathparent = cur; 197 cur = cur->child; 198 } 199 if (*p == '\0') 200 mtree_err("%s: empty leaf element", tname); 201 } 202 203 if ((centry = calloc(1, sizeof(NODE) + strlen(p))) == NULL) 204 mtree_err("%s", strerror(errno)); 205 *centry = ginfo; 206 centry->lineno = mtree_lineno; 207 strcpy(centry->name, p); 208 #define MAGIC "?*[" 209 if (strpbrk(p, MAGIC)) 210 centry->flags |= F_MAGIC; 211 set(next, centry); 212 213 if (root == NULL) { 214 /* 215 * empty tree 216 */ 217 if (strcmp(centry->name, ".") != 0 || 218 centry->type != F_DIR) 219 mtree_err( 220 "root node must be the directory `.'"); 221 last = root = centry; 222 root->parent = root; 223 } else if (pathparent != NULL) { 224 /* 225 * full path entry; add or replace 226 */ 227 centry->parent = pathparent; 228 addchild(pathparent, centry); 229 last = centry; 230 } else if (strcmp(centry->name, ".") == 0) { 231 /* 232 * duplicate "." entry; always replace 233 */ 234 replacenode(root, centry); 235 } else if (last->type == F_DIR && !(last->flags & F_DONE)) { 236 /* 237 * new relative child in current dir; 238 * add or replace 239 */ 240 centry->parent = last; 241 addchild(last, centry); 242 last = centry; 243 } else { 244 /* 245 * new relative child in parent dir 246 * (after encountering ".." entry); 247 * add or replace 248 */ 249 centry->parent = last->parent; 250 addchild(last->parent, centry); 251 last = centry; 252 } 253 } 254 return (root); 255 } 256 257 void 258 free_nodes(NODE *root) 259 { 260 NODE *cur, *next; 261 262 if (root == NULL) 263 return; 264 265 next = NULL; 266 for (cur = root; cur != NULL; cur = next) { 267 next = cur->next; 268 free_nodes(cur->child); 269 REPLACEPTR(cur->slink, NULL); 270 REPLACEPTR(cur->md5digest, NULL); 271 REPLACEPTR(cur->rmd160digest, NULL); 272 REPLACEPTR(cur->sha1digest, NULL); 273 REPLACEPTR(cur->sha256digest, NULL); 274 REPLACEPTR(cur->sha384digest, NULL); 275 REPLACEPTR(cur->sha512digest, NULL); 276 REPLACEPTR(cur->tags, NULL); 277 REPLACEPTR(cur, NULL); 278 } 279 } 280 281 /* 282 * dump_nodes -- 283 * dump the NODEs from `cur', based in the directory `dir'. 284 * if pathlast is none zero, print the path last, otherwise print 285 * it first. 286 */ 287 void 288 dump_nodes(const char *dir, NODE *root, int pathlast) 289 { 290 NODE *cur; 291 char path[MAXPATHLEN]; 292 const char *name; 293 char *str; 294 char *p, *q; 295 296 for (cur = root; cur != NULL; cur = cur->next) { 297 if (cur->type != F_DIR && !matchtags(cur)) 298 continue; 299 300 if (snprintf(path, sizeof(path), "%s%s%s", 301 dir, *dir ? "/" : "", cur->name) 302 >= (int)sizeof(path)) 303 mtree_err("Pathname too long."); 304 305 if (!pathlast) 306 printf("%s ", vispath(path)); 307 308 #define MATCHFLAG(f) ((keys & (f)) && (cur->flags & (f))) 309 if (MATCHFLAG(F_TYPE)) 310 printf("type=%s ", nodetype(cur->type)); 311 if (MATCHFLAG(F_UID | F_UNAME)) { 312 if (keys & F_UNAME && 313 (name = user_from_uid(cur->st_uid, 1)) != NULL) 314 printf("uname=%s ", name); 315 else 316 printf("uid=%u ", cur->st_uid); 317 } 318 if (MATCHFLAG(F_GID | F_GNAME)) { 319 if (keys & F_GNAME && 320 (name = group_from_gid(cur->st_gid, 1)) != NULL) 321 printf("gname=%s ", name); 322 else 323 printf("gid=%u ", cur->st_gid); 324 } 325 if (MATCHFLAG(F_MODE)) 326 printf("mode=%#o ", cur->st_mode); 327 if (MATCHFLAG(F_DEV) && 328 (cur->type == F_BLOCK || cur->type == F_CHAR)) 329 printf("device=%#llx ", (long long)cur->st_rdev); 330 if (MATCHFLAG(F_NLINK)) 331 printf("nlink=%d ", cur->st_nlink); 332 if (MATCHFLAG(F_SLINK)) 333 printf("link=%s ", vispath(cur->slink)); 334 if (MATCHFLAG(F_SIZE)) 335 printf("size=%lld ", (long long)cur->st_size); 336 if (MATCHFLAG(F_TIME)) 337 printf("time=%lld.%ld ", 338 (long long)cur->st_mtimespec.tv_sec, 339 cur->st_mtimespec.tv_nsec); 340 if (MATCHFLAG(F_CKSUM)) 341 printf("cksum=%lu ", cur->cksum); 342 if (MATCHFLAG(F_MD5)) 343 printf("md5=%s ", cur->md5digest); 344 if (MATCHFLAG(F_RMD160)) 345 printf("rmd160=%s ", cur->rmd160digest); 346 if (MATCHFLAG(F_SHA1)) 347 printf("sha1=%s ", cur->sha1digest); 348 if (MATCHFLAG(F_SHA256)) 349 printf("sha256=%s ", cur->sha256digest); 350 if (MATCHFLAG(F_SHA384)) 351 printf("sha384=%s ", cur->sha384digest); 352 if (MATCHFLAG(F_SHA512)) 353 printf("sha512=%s ", cur->sha512digest); 354 if (MATCHFLAG(F_FLAGS)) { 355 str = flags_to_string(cur->st_flags, "none"); 356 printf("flags=%s ", str); 357 free(str); 358 } 359 if (MATCHFLAG(F_IGN)) 360 printf("ignore "); 361 if (MATCHFLAG(F_OPT)) 362 printf("optional "); 363 if (MATCHFLAG(F_TAGS)) { 364 /* don't output leading or trailing commas */ 365 p = cur->tags; 366 while (*p == ',') 367 p++; 368 q = p + strlen(p); 369 while(q > p && q[-1] == ',') 370 q--; 371 printf("tags=%.*s ", (int)(q - p), p); 372 } 373 puts(pathlast ? vispath(path) : ""); 374 375 if (cur->child) 376 dump_nodes(path, cur->child, pathlast); 377 } 378 } 379 380 /* 381 * vispath -- 382 * strsvis(3) encodes path, which must not be longer than MAXPATHLEN 383 * characters long, and returns a pointer to a static buffer containing 384 * the result. 385 */ 386 char * 387 vispath(const char *path) 388 { 389 const char extra[] = { ' ', '\t', '\n', '\\', '#', '\0' }; 390 static char pathbuf[4*MAXPATHLEN + 1]; 391 392 strsvis(pathbuf, path, VIS_CSTYLE, extra); 393 return(pathbuf); 394 } 395 396 397 static dev_t 398 parsedev(char *arg) 399 { 400 #define MAX_PACK_ARGS 3 401 u_long numbers[MAX_PACK_ARGS]; 402 char *p, *ep, *dev; 403 int argc; 404 pack_t *pack; 405 dev_t result; 406 const char *error = NULL; 407 408 if ((dev = strchr(arg, ',')) != NULL) { 409 *dev++='\0'; 410 if ((pack = pack_find(arg)) == NULL) 411 mtree_err("unknown format `%s'", arg); 412 argc = 0; 413 while ((p = strsep(&dev, ",")) != NULL) { 414 if (*p == '\0') 415 mtree_err("missing number"); 416 numbers[argc++] = strtoul(p, &ep, 0); 417 if (*ep != '\0') 418 mtree_err("invalid number `%s'", 419 p); 420 if (argc > MAX_PACK_ARGS) 421 mtree_err("too many arguments"); 422 } 423 if (argc < 2) 424 mtree_err("not enough arguments"); 425 result = (*pack)(argc, numbers, &error); 426 if (error != NULL) 427 mtree_err("%s", error); 428 } else { 429 result = (dev_t)strtoul(arg, &ep, 0); 430 if (*ep != '\0') 431 mtree_err("invalid device `%s'", arg); 432 } 433 return (result); 434 } 435 436 static void 437 replacenode(NODE *cur, NODE *new) 438 { 439 440 #define REPLACE(x) cur->x = new->x 441 #define REPLACESTR(x) REPLACEPTR(cur->x,new->x) 442 443 if (cur->type != new->type) { 444 if (mtree_Mflag) { 445 /* 446 * merge entries with different types; we 447 * don't want children retained in this case. 448 */ 449 REPLACE(type); 450 free_nodes(cur->child); 451 cur->child = NULL; 452 } else { 453 mtree_err( 454 "existing entry for `%s', type `%s'" 455 " does not match type `%s'", 456 cur->name, nodetype(cur->type), 457 nodetype(new->type)); 458 } 459 } 460 461 REPLACE(st_size); 462 REPLACE(st_mtimespec); 463 REPLACESTR(slink); 464 if (cur->slink != NULL) { 465 if ((cur->slink = strdup(new->slink)) == NULL) 466 mtree_err("memory allocation error"); 467 if (strunvis(cur->slink, new->slink) == -1) 468 mtree_err("strunvis failed on `%s'", new->slink); 469 free(new->slink); 470 } 471 REPLACE(st_uid); 472 REPLACE(st_gid); 473 REPLACE(st_mode); 474 REPLACE(st_rdev); 475 REPLACE(st_flags); 476 REPLACE(st_nlink); 477 REPLACE(cksum); 478 REPLACESTR(md5digest); 479 REPLACESTR(rmd160digest); 480 REPLACESTR(sha1digest); 481 REPLACESTR(sha256digest); 482 REPLACESTR(sha384digest); 483 REPLACESTR(sha512digest); 484 REPLACESTR(tags); 485 REPLACE(lineno); 486 REPLACE(flags); 487 free(new); 488 } 489 490 static void 491 set(char *t, NODE *ip) 492 { 493 int type, value, len; 494 gid_t gid; 495 uid_t uid; 496 char *kw, *val, *md, *ep; 497 void *m; 498 499 while ((kw = strsep(&t, "= \t")) != NULL) { 500 if (*kw == '\0') 501 continue; 502 if (strcmp(kw, "all") == 0) 503 mtree_err("invalid keyword `all'"); 504 ip->flags |= type = parsekey(kw, &value); 505 if (!value) 506 /* Just set flag bit (F_IGN and F_OPT) */ 507 continue; 508 while ((val = strsep(&t, " \t")) != NULL && *val == '\0') 509 continue; 510 if (val == NULL) 511 mtree_err("missing value"); 512 switch (type) { 513 case F_CKSUM: 514 ip->cksum = strtoul(val, &ep, 10); 515 if (*ep) 516 mtree_err("invalid checksum `%s'", val); 517 break; 518 case F_DEV: 519 ip->st_rdev = parsedev(val); 520 break; 521 case F_FLAGS: 522 if (strcmp("none", val) == 0) 523 ip->st_flags = 0; 524 else if (string_to_flags(&val, &ip->st_flags, NULL) 525 != 0) 526 mtree_err("invalid flag `%s'", val); 527 break; 528 case F_GID: 529 ip->st_gid = (gid_t)strtoul(val, &ep, 10); 530 if (*ep) 531 mtree_err("invalid gid `%s'", val); 532 break; 533 case F_GNAME: 534 if (mtree_Wflag) /* don't parse if whacking */ 535 break; 536 if (gid_from_group(val, &gid) == -1) 537 mtree_err("unknown group `%s'", val); 538 ip->st_gid = gid; 539 break; 540 case F_MD5: 541 if (val[0]=='0' && val[1]=='x') 542 md=&val[2]; 543 else 544 md=val; 545 if ((ip->md5digest = strdup(md)) == NULL) 546 mtree_err("memory allocation error"); 547 break; 548 case F_MODE: 549 if ((m = setmode(val)) == NULL) 550 mtree_err("cannot set file mode `%s' (%s)", 551 val, strerror(errno)); 552 ip->st_mode = getmode(m, 0); 553 free(m); 554 break; 555 case F_NLINK: 556 ip->st_nlink = (nlink_t)strtoul(val, &ep, 10); 557 if (*ep) 558 mtree_err("invalid link count `%s'", val); 559 break; 560 case F_RMD160: 561 if (val[0]=='0' && val[1]=='x') 562 md=&val[2]; 563 else 564 md=val; 565 if ((ip->rmd160digest = strdup(md)) == NULL) 566 mtree_err("memory allocation error"); 567 break; 568 case F_SHA1: 569 if (val[0]=='0' && val[1]=='x') 570 md=&val[2]; 571 else 572 md=val; 573 if ((ip->sha1digest = strdup(md)) == NULL) 574 mtree_err("memory allocation error"); 575 break; 576 case F_SIZE: 577 ip->st_size = (off_t)strtoll(val, &ep, 10); 578 if (*ep) 579 mtree_err("invalid size `%s'", val); 580 break; 581 case F_SLINK: 582 if ((ip->slink = strdup(val)) == NULL) 583 mtree_err("memory allocation error"); 584 if (strunvis(ip->slink, val) == -1) 585 mtree_err("strunvis failed on `%s'", val); 586 break; 587 case F_TAGS: 588 len = strlen(val) + 3; /* "," + str + ",\0" */ 589 if ((ip->tags = malloc(len)) == NULL) 590 mtree_err("memory allocation error"); 591 snprintf(ip->tags, len, ",%s,", val); 592 break; 593 case F_TIME: 594 ip->st_mtimespec.tv_sec = 595 (time_t)strtoll(val, &ep, 10); 596 if (*ep != '.') 597 mtree_err("invalid time `%s'", val); 598 val = ep + 1; 599 ip->st_mtimespec.tv_nsec = strtol(val, &ep, 10); 600 if (*ep) 601 mtree_err("invalid time `%s'", val); 602 break; 603 case F_TYPE: 604 ip->type = parsetype(val); 605 break; 606 case F_UID: 607 ip->st_uid = (uid_t)strtoul(val, &ep, 10); 608 if (*ep) 609 mtree_err("invalid uid `%s'", val); 610 break; 611 case F_UNAME: 612 if (mtree_Wflag) /* don't parse if whacking */ 613 break; 614 if (uid_from_user(val, &uid) == -1) 615 mtree_err("unknown user `%s'", val); 616 ip->st_uid = uid; 617 break; 618 case F_SHA256: 619 if (val[0]=='0' && val[1]=='x') 620 md=&val[2]; 621 else 622 md=val; 623 if ((ip->sha256digest = strdup(md)) == NULL) 624 mtree_err("memory allocation error"); 625 break; 626 case F_SHA384: 627 if (val[0]=='0' && val[1]=='x') 628 md=&val[2]; 629 else 630 md=val; 631 if ((ip->sha384digest = strdup(md)) == NULL) 632 mtree_err("memory allocation error"); 633 break; 634 case F_SHA512: 635 if (val[0]=='0' && val[1]=='x') 636 md=&val[2]; 637 else 638 md=val; 639 if ((ip->sha512digest = strdup(md)) == NULL) 640 mtree_err("memory allocation error"); 641 break; 642 default: 643 mtree_err( 644 "set(): unsupported key type 0x%x (INTERNAL ERROR)", 645 type); 646 /* NOTREACHED */ 647 } 648 } 649 } 650 651 static void 652 unset(char *t, NODE *ip) 653 { 654 char *p; 655 656 while ((p = strsep(&t, " \t")) != NULL) { 657 if (*p == '\0') 658 continue; 659 ip->flags &= ~parsekey(p, NULL); 660 } 661 } 662 663 /* 664 * addchild -- 665 * Add the centry node as a child of the pathparent node. If 666 * centry is a duplicate, call replacenode(). If centry is not 667 * a duplicate, insert it into the linked list referenced by 668 * pathparent->child. Keep the list sorted if Sflag is set. 669 */ 670 static void 671 addchild(NODE *pathparent, NODE *centry) 672 { 673 NODE *cur, *insertpos; 674 int cmp; 675 676 cur = pathparent->child; 677 if (cur == NULL) { 678 /* centry is pathparent's first and only child node so far */ 679 pathparent->child = centry; 680 return; 681 } 682 683 /* 684 * pathparent already has at least one other child, so add the 685 * centry node to the list. 686 * 687 * To keep the list sorted, the new centry node will be 688 * inserted just after the existing insertpos node, if any; 689 * otherwise it will be inserted at the start of the list. 690 */ 691 insertpos = NULL; 692 for (; cur != NULL; cur = cur->next) { 693 cmp = nodecmp(centry, cur); 694 if (cmp == 0) { 695 /* existing entry; replace */ 696 replacenode(cur, centry); 697 break; 698 } else if (cmp > 0) { 699 /* centry appears after cur in sort order */ 700 insertpos = cur; 701 } 702 if ((mtree_Sflag && cmp < 0) || cur->next == NULL) { 703 /* 704 * centry appears before cur in sort order, 705 * or we reached the end of the list; insert 706 * centry either just after insertpos, or at the 707 * beginning of the list. If we are not sorting, 708 * then always append to the list. 709 */ 710 if (!mtree_Sflag) 711 insertpos = cur; 712 if (insertpos) { 713 centry->next = insertpos->next; 714 insertpos->next = centry; 715 centry->prev = insertpos; 716 if (centry->next) 717 centry->next->prev = centry; 718 } else { 719 pathparent->child->prev = centry; 720 centry->next = pathparent->child; 721 pathparent->child = centry; 722 } 723 break; 724 } 725 } 726 return; 727 } 728 729 /* 730 * nodecmp -- 731 * used as a comparison function by addchild() to control the order 732 * in which entries appear within a list of sibling nodes. We make 733 * directories sort after non-directories, but otherwise sort in 734 * strcmp() order. 735 * 736 * Keep this in sync with dcmp() in create.c. 737 */ 738 static int 739 nodecmp(const NODE *a, const NODE *b) 740 { 741 742 if ((a->type & F_DIR) != 0) { 743 if ((b->type & F_DIR) == 0) 744 return 1; 745 } else if ((b->type & F_DIR) != 0) 746 return -1; 747 return strcmp(a->name, b->name); 748 } 749