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