git.cworth.org Git - tar/blob - src/names.c

   1 /* Various processing of names.
   2
   3    Copyright (C) 1988, 1992, 1994, 1996, 1997, 1998, 1999, 2000, 2001,
   4    2003, 2004, 2005, 2006, 2007, 2009 Free Software Foundation, Inc.
   5
   6    This program is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by the
   8    Free Software Foundation; either version 3, or (at your option) any later
   9    version.
  10
  11    This program is distributed in the hope that it will be useful, but
  12    WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
  14    Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License along
  17    with this program; if not, write to the Free Software Foundation, Inc.,
  18    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 #include <system.h>
  21
  22 #include <fnmatch.h>
  23 #include <hash.h>
  24 #include <quotearg.h>
  25
  26 #include "common.h"
  27 \f
  28 /* User and group names.  */
  29
  30 struct group *getgrnam ();
  31 struct passwd *getpwnam ();
  32 #if ! HAVE_DECL_GETPWUID
  33 struct passwd *getpwuid ();
  34 #endif
  35 #if ! HAVE_DECL_GETGRGID
  36 struct group *getgrgid ();
  37 #endif
  38
  39 /* Make sure you link with the proper libraries if you are running the
  40    Yellow Peril (thanks for the good laugh, Ian J.!), or, euh... NIS.
  41    This code should also be modified for non-UNIX systems to do something
  42    reasonable.  */
  43
  44 static char *cached_uname;
  45 static char *cached_gname;
  46
  47 static uid_t cached_uid;        /* valid only if cached_uname is not empty */
  48 static gid_t cached_gid;        /* valid only if cached_gname is not empty */
  49
  50 /* These variables are valid only if nonempty.  */
  51 static char *cached_no_such_uname;
  52 static char *cached_no_such_gname;
  53
  54 /* These variables are valid only if nonzero.  It's not worth optimizing
  55    the case for weird systems where 0 is not a valid uid or gid.  */
  56 static uid_t cached_no_such_uid;
  57 static gid_t cached_no_such_gid;
  58
  59 static void register_individual_file (char const *name);
  60
  61 /* Given UID, find the corresponding UNAME.  */
  62 void
  63 uid_to_uname (uid_t uid, char **uname)
  64 {
  65   struct passwd *passwd;
  66
  67   if (uid != 0 && uid == cached_no_such_uid)
  68     {
  69       *uname = xstrdup ("");
  70       return;
  71     }
  72
  73   if (!cached_uname || uid != cached_uid)
  74     {
  75       passwd = getpwuid (uid);
  76       if (passwd)
  77         {
  78           cached_uid = uid;
  79           assign_string (&cached_uname, passwd->pw_name);
  80         }
  81       else
  82         {
  83           cached_no_such_uid = uid;
  84           *uname = xstrdup ("");
  85           return;
  86         }
  87     }
  88   *uname = xstrdup (cached_uname);
  89 }
  90
  91 /* Given GID, find the corresponding GNAME.  */
  92 void
  93 gid_to_gname (gid_t gid, char **gname)
  94 {
  95   struct group *group;
  96
  97   if (gid != 0 && gid == cached_no_such_gid)
  98     {
  99       *gname = xstrdup ("");
 100       return;
 101     }
 102
 103   if (!cached_gname || gid != cached_gid)
 104     {
 105       group = getgrgid (gid);
 106       if (group)
 107         {
 108           cached_gid = gid;
 109           assign_string (&cached_gname, group->gr_name);
 110         }
 111       else
 112         {
 113           cached_no_such_gid = gid;
 114           *gname = xstrdup ("");
 115           return;
 116         }
 117     }
 118   *gname = xstrdup (cached_gname);
 119 }
 120
 121 /* Given UNAME, set the corresponding UID and return 1, or else, return 0.  */
 122 int
 123 uname_to_uid (char const *uname, uid_t *uidp)
 124 {
 125   struct passwd *passwd;
 126
 127   if (cached_no_such_uname
 128       && strcmp (uname, cached_no_such_uname) == 0)
 129     return 0;
 130
 131   if (!cached_uname
 132       || uname[0] != cached_uname[0]
 133       || strcmp (uname, cached_uname) != 0)
 134     {
 135       passwd = getpwnam (uname);
 136       if (passwd)
 137         {
 138           cached_uid = passwd->pw_uid;
 139           assign_string (&cached_uname, passwd->pw_name);
 140         }
 141       else
 142         {
 143           assign_string (&cached_no_such_uname, uname);
 144           return 0;
 145         }
 146     }
 147   *uidp = cached_uid;
 148   return 1;
 149 }
 150
 151 /* Given GNAME, set the corresponding GID and return 1, or else, return 0.  */
 152 int
 153 gname_to_gid (char const *gname, gid_t *gidp)
 154 {
 155   struct group *group;
 156
 157   if (cached_no_such_gname
 158       && strcmp (gname, cached_no_such_gname) == 0)
 159     return 0;
 160
 161   if (!cached_gname
 162       || gname[0] != cached_gname[0]
 163       || strcmp (gname, cached_gname) != 0)
 164     {
 165       group = getgrnam (gname);
 166       if (group)
 167         {
 168           cached_gid = group->gr_gid;
 169           assign_string (&cached_gname, gname);
 170         }
 171       else
 172         {
 173           assign_string (&cached_no_such_gname, gname);
 174           return 0;
 175         }
 176     }
 177   *gidp = cached_gid;
 178   return 1;
 179 }
 180
 181 \f
 182 struct name *
 183 make_name (const char *file_name)
 184 {
 185   struct name *p = xzalloc (sizeof (*p));
 186   if (!file_name)
 187     file_name = "";
 188   p->name = xstrdup (file_name);
 189   p->length = strlen (p->name);
 190   return p;
 191 }
 192
 193 void
 194 free_name (struct name *p)
 195 {
 196   if (p)
 197     {
 198       free (p->name);
 199       free (p->caname);
 200       free (p);
 201     }
 202 }
 203
 204 \f
 205 /* Names from the command call.  */
 206
 207 static struct name *namelist;   /* first name in list, if any */
 208 static struct name *nametail;   /* end of name list */
 209
 210 /* File name arguments are processed in two stages: first a
 211    name_array (see below) is filled, then the names from it
 212    are moved into the namelist.
 213
 214    This awkward process is needed only to implement --same-order option,
 215    which is meant to help process large archives on machines with
 216    limited memory.  With this option on, namelist contains at most one
 217    entry, which diminishes the memory consumption.
 218
 219    However, I very much doubt if we still need this -- Sergey */
 220
 221 /* A name_array element contains entries of three types: */
 222
 223 #define NELT_NAME  0   /* File name */
 224 #define NELT_CHDIR 1   /* Change directory request */
 225 #define NELT_FMASK 2   /* Change fnmatch options request */
 226
 227 struct name_elt        /* A name_array element. */
 228 {
 229   char type;           /* Element type, see NELT_* constants above */
 230   union
 231   {
 232     const char *name;  /* File or directory name */
 233     int matching_flags;/* fnmatch options if type == NELT_FMASK */
 234   } v;
 235 };
 236
 237 static struct name_elt *name_array;  /* store an array of names */
 238 static size_t allocated_names;   /* how big is the array? */
 239 static size_t names;             /* how many entries does it have? */
 240 static size_t name_index;        /* how many of the entries have we scanned? */
 241
 242 /* Check the size of name_array, reallocating it as necessary.  */
 243 static void
 244 check_name_alloc ()
 245 {
 246   if (names == allocated_names)
 247     {
 248       if (allocated_names == 0)
 249         allocated_names = 10; /* Set initial allocation */
 250       name_array = x2nrealloc (name_array, &allocated_names,
 251                                sizeof (name_array[0]));
 252     }
 253 }
 254
 255 /* Add to name_array the file NAME with fnmatch options MATCHING_FLAGS */
 256 void
 257 name_add_name (const char *name, int matching_flags)
 258 {
 259   static int prev_flags = 0; /* FIXME: Or EXCLUDE_ANCHORED? */
 260   struct name_elt *ep;
 261
 262   check_name_alloc ();
 263   ep = &name_array[names++];
 264   if (prev_flags != matching_flags)
 265     {
 266       ep->type = NELT_FMASK;
 267       ep->v.matching_flags = matching_flags;
 268       prev_flags = matching_flags;
 269       check_name_alloc ();
 270       ep = &name_array[names++];
 271     }
 272   ep->type = NELT_NAME;
 273   ep->v.name = name;
 274 }
 275
 276 /* Add to name_array a chdir request for the directory NAME */
 277 void
 278 name_add_dir (const char *name)
 279 {
 280   struct name_elt *ep;
 281   check_name_alloc ();
 282   ep = &name_array[names++];
 283   ep->type = NELT_CHDIR;
 284   ep->v.name = name;
 285 }
 286
 287 \f
 288 /* Names from external name file.  */
 289
 290 static char *name_buffer;       /* buffer to hold the current file name */
 291 static size_t name_buffer_length; /* allocated length of name_buffer */
 292
 293 /* Set up to gather file names for tar.  They can either come from a
 294    file or were saved from decoding arguments.  */
 295 void
 296 name_init (void)
 297 {
 298   name_buffer = xmalloc (NAME_FIELD_SIZE + 2);
 299   name_buffer_length = NAME_FIELD_SIZE;
 300 }
 301
 302 void
 303 name_term (void)
 304 {
 305   free (name_buffer);
 306   free (name_array);
 307 }
 308
 309 static int matching_flags; /* exclude_fnmatch options */
 310
 311 /* Get the next NELT_NAME element from name_array.  Result is in
 312    static storage and can't be relied upon across two calls.
 313
 314    If CHANGE_DIRS is true, treat any entries of type NELT_CHDIR as
 315    the request to change to the given directory.
 316
 317    Entries of type NELT_FMASK cause updates of the matching_flags
 318    value. */
 319 struct name_elt *
 320 name_next_elt (int change_dirs)
 321 {
 322   static struct name_elt entry;
 323   const char *source;
 324   char *cursor;
 325
 326   while (name_index != names)
 327     {
 328       struct name_elt *ep;
 329       size_t source_len;
 330
 331       ep = &name_array[name_index++];
 332       if (ep->type == NELT_FMASK)
 333         {
 334           matching_flags = ep->v.matching_flags;
 335           continue;
 336         }
 337
 338       source = ep->v.name;
 339       source_len = strlen (source);
 340       if (name_buffer_length < source_len)
 341         {
 342           do
 343             {
 344               name_buffer_length *= 2;
 345               if (! name_buffer_length)
 346                 xalloc_die ();
 347             }
 348           while (name_buffer_length < source_len);
 349
 350           free (name_buffer);
 351           name_buffer = xmalloc (name_buffer_length + 2);
 352         }
 353       strcpy (name_buffer, source);
 354
 355       /* Zap trailing slashes.  */
 356
 357       cursor = name_buffer + strlen (name_buffer) - 1;
 358       while (cursor > name_buffer && ISSLASH (*cursor))
 359         *cursor-- = '\0';
 360
 361       if (change_dirs && ep->type == NELT_CHDIR)
 362         {
 363           if (chdir (name_buffer) < 0)
 364             chdir_fatal (name_buffer);
 365         }
 366       else
 367         {
 368           if (unquote_option)
 369             unquote_string (name_buffer);
 370           if (incremental_option)
 371             register_individual_file (name_buffer);
 372           entry.type = ep->type;
 373           entry.v.name = name_buffer;
 374           return &entry;
 375         }
 376     }
 377
 378   return NULL;
 379 }
 380
 381 const char *
 382 name_next (int change_dirs)
 383 {
 384   struct name_elt *nelt = name_next_elt (change_dirs);
 385   return nelt ? nelt->v.name : NULL;
 386 }
 387
 388 /* Gather names in a list for scanning.  Could hash them later if we
 389    really care.
 390
 391    If the names are already sorted to match the archive, we just read
 392    them one by one.  name_gather reads the first one, and it is called
 393    by name_match as appropriate to read the next ones.  At EOF, the
 394    last name read is just left in the buffer.  This option lets users
 395    of small machines extract an arbitrary number of files by doing
 396    "tar t" and editing down the list of files.  */
 397
 398 void
 399 name_gather (void)
 400 {
 401   /* Buffer able to hold a single name.  */
 402   static struct name *buffer = NULL;
 403
 404   struct name_elt *ep;
 405
 406   if (same_order_option)
 407     {
 408       static int change_dir;
 409
 410       while ((ep = name_next_elt (0)) && ep->type == NELT_CHDIR)
 411         change_dir = chdir_arg (xstrdup (ep->v.name));
 412
 413       if (ep)
 414         {
 415           free_name (buffer);
 416           buffer = make_name (ep->v.name);
 417           buffer->change_dir = change_dir;
 418           buffer->next = 0;
 419           buffer->found_count = 0;
 420           buffer->matching_flags = matching_flags;
 421           buffer->directory = NULL;
 422           buffer->parent = NULL;
 423           buffer->cmdline = true;
 424
 425           namelist = nametail = buffer;
 426         }
 427       else if (change_dir)
 428         addname (0, change_dir, false, NULL);
 429     }
 430   else
 431     {
 432       /* Non sorted names -- read them all in.  */
 433       int change_dir = 0;
 434
 435       for (;;)
 436         {
 437           int change_dir0 = change_dir;
 438           while ((ep = name_next_elt (0)) && ep->type == NELT_CHDIR)
 439             change_dir = chdir_arg (xstrdup (ep->v.name));
 440
 441           if (ep)
 442             addname (ep->v.name, change_dir, true, NULL);
 443           else
 444             {
 445               if (change_dir != change_dir0)
 446                 addname (NULL, change_dir, false, NULL);
 447               break;
 448             }
 449         }
 450     }
 451 }
 452
 453 /*  Add a name to the namelist.  */
 454 struct name *
 455 addname (char const *string, int change_dir, bool cmdline, struct name *parent)
 456 {
 457   struct name *name = make_name (string);
 458
 459   name->prev = nametail;
 460   name->next = NULL;
 461   name->found_count = 0;
 462   name->matching_flags = matching_flags;
 463   name->change_dir = change_dir;
 464   name->directory = NULL;
 465   name->parent = parent;
 466   name->cmdline = cmdline;
 467
 468   if (nametail)
 469     nametail->next = name;
 470   else
 471     namelist = name;
 472   nametail = name;
 473   return name;
 474 }
 475
 476 /* Find a match for FILE_NAME (whose string length is LENGTH) in the name
 477    list.  */
 478 static struct name *
 479 namelist_match (char const *file_name, size_t length)
 480 {
 481   struct name *p;
 482
 483   for (p = namelist; p; p = p->next)
 484     {
 485       if (p->name[0]
 486           && exclude_fnmatch (p->name, file_name, p->matching_flags))
 487         return p;
 488     }
 489
 490   return NULL;
 491 }
 492
 493 void
 494 remname (struct name *name)
 495 {
 496   struct name *p;
 497
 498   if ((p = name->prev) != NULL)
 499     p->next = name->next;
 500   else
 501     namelist = name->next;
 502
 503   if ((p = name->next) != NULL)
 504     p->prev = name->prev;
 505   else
 506     nametail = name->prev;
 507 }
 508
 509 /* Return true if and only if name FILE_NAME (from an archive) matches any
 510    name from the namelist.  */
 511 bool
 512 name_match (const char *file_name)
 513 {
 514   size_t length = strlen (file_name);
 515
 516   while (1)
 517     {
 518       struct name *cursor = namelist;
 519
 520       if (!cursor)
 521         return true;
 522
 523       if (cursor->name[0] == 0)
 524         {
 525           chdir_do (cursor->change_dir);
 526           namelist = NULL;
 527           nametail = NULL;
 528           return true;
 529         }
 530
 531       cursor = namelist_match (file_name, length);
 532       if (cursor)
 533         {
 534           if (!(ISSLASH (file_name[cursor->length]) && recursion_option)
 535               || cursor->found_count == 0)
 536             cursor->found_count++; /* remember it matched */
 537           if (starting_file_option)
 538             {
 539               free (namelist);
 540               namelist = NULL;
 541               nametail = NULL;
 542             }
 543           chdir_do (cursor->change_dir);
 544
 545           /* We got a match.  */
 546           return ISFOUND (cursor);
 547         }
 548
 549       /* Filename from archive not found in namelist.  If we have the whole
 550          namelist here, just return 0.  Otherwise, read the next name in and
 551          compare it.  If this was the last name, namelist->found_count will
 552          remain on.  If not, we loop to compare the newly read name.  */
 553
 554       if (same_order_option && namelist->found_count)
 555         {
 556           name_gather ();       /* read one more */
 557           if (namelist->found_count)
 558             return false;
 559         }
 560       else
 561         return false;
 562     }
 563 }
 564
 565 /* Returns true if all names from the namelist were processed.
 566    P is the stat_info of the most recently processed entry.
 567    The decision is postponed until the next entry is read if:
 568
 569    1) P ended with a slash (i.e. it was a directory)
 570    2) P matches any entry from the namelist *and* represents a subdirectory
 571    or a file lying under this entry (in the terms of directory structure).
 572
 573    This is necessary to handle contents of directories. */
 574 bool
 575 all_names_found (struct tar_stat_info *p)
 576 {
 577   struct name const *cursor;
 578   size_t len;
 579
 580   if (!p->file_name || occurrence_option == 0 || p->had_trailing_slash)
 581     return false;
 582   len = strlen (p->file_name);
 583   for (cursor = namelist; cursor; cursor = cursor->next)
 584     {
 585       if ((cursor->name[0] && !WASFOUND (cursor))
 586           || (len >= cursor->length && ISSLASH (p->file_name[cursor->length])))
 587         return false;
 588     }
 589   return true;
 590 }
 591
 592 static void
 593 regex_usage_warning (const char *name)
 594 {
 595   static int warned_once = 0;
 596
 597   if (warn_regex_usage && fnmatch_pattern_has_wildcards (name, 0))
 598     {
 599       warned_once = 1;
 600       WARN ((0, 0,
 601              _("Pattern matching characters used in file names")));
 602       WARN ((0, 0,
 603              _("Use --wildcards to enable pattern matching,"
 604                " or --no-wildcards to suppress this warning")));
 605     }
 606 }
 607
 608 /* Print the names of things in the namelist that were not matched.  */
 609 void
 610 names_notfound (void)
 611 {
 612   struct name const *cursor;
 613
 614   for (cursor = namelist; cursor; cursor = cursor->next)
 615     if (!WASFOUND (cursor) && cursor->name[0])
 616       {
 617         regex_usage_warning (cursor->name);
 618         if (cursor->found_count == 0)
 619           ERROR ((0, 0, _("%s: Not found in archive"),
 620                   quotearg_colon (cursor->name)));
 621         else
 622           ERROR ((0, 0, _("%s: Required occurrence not found in archive"),
 623                   quotearg_colon (cursor->name)));
 624       }
 625
 626   /* Don't bother freeing the name list; we're about to exit.  */
 627   namelist = NULL;
 628   nametail = NULL;
 629
 630   if (same_order_option)
 631     {
 632       const char *name;
 633
 634       while ((name = name_next (1)) != NULL)
 635         {
 636           regex_usage_warning (name);
 637           ERROR ((0, 0, _("%s: Not found in archive"),
 638                   quotearg_colon (name)));
 639         }
 640     }
 641 }
 642 \f
 643 /* Sorting name lists.  */
 644
 645 /* Sort *singly* linked LIST of names, of given LENGTH, using COMPARE
 646    to order names.  Return the sorted list.  Note that after calling
 647    this function, the `prev' links in list elements are messed up.
 648
 649    Apart from the type `struct name' and the definition of SUCCESSOR,
 650    this is a generic list-sorting function, but it's too painful to
 651    make it both generic and portable
 652    in C.  */
 653
 654 static struct name *
 655 merge_sort_sll (struct name *list, int length,
 656                 int (*compare) (struct name const*, struct name const*))
 657 {
 658   struct name *first_list;
 659   struct name *second_list;
 660   int first_length;
 661   int second_length;
 662   struct name *result;
 663   struct name **merge_point;
 664   struct name *cursor;
 665   int counter;
 666
 667 # define SUCCESSOR(name) ((name)->next)
 668
 669   if (length == 1)
 670     return list;
 671
 672   if (length == 2)
 673     {
 674       if ((*compare) (list, SUCCESSOR (list)) > 0)
 675         {
 676           result = SUCCESSOR (list);
 677           SUCCESSOR (result) = list;
 678           SUCCESSOR (list) = 0;
 679           return result;
 680         }
 681       return list;
 682     }
 683
 684   first_list = list;
 685   first_length = (length + 1) / 2;
 686   second_length = length / 2;
 687   for (cursor = list, counter = first_length - 1;
 688        counter;
 689        cursor = SUCCESSOR (cursor), counter--)
 690     continue;
 691   second_list = SUCCESSOR (cursor);
 692   SUCCESSOR (cursor) = 0;
 693
 694   first_list = merge_sort_sll (first_list, first_length, compare);
 695   second_list = merge_sort_sll (second_list, second_length, compare);
 696
 697   merge_point = &result;
 698   while (first_list && second_list)
 699     if ((*compare) (first_list, second_list) < 0)
 700       {
 701         cursor = SUCCESSOR (first_list);
 702         *merge_point = first_list;
 703         merge_point = &SUCCESSOR (first_list);
 704         first_list = cursor;
 705       }
 706     else
 707       {
 708         cursor = SUCCESSOR (second_list);
 709         *merge_point = second_list;
 710         merge_point = &SUCCESSOR (second_list);
 711         second_list = cursor;
 712       }
 713   if (first_list)
 714     *merge_point = first_list;
 715   else
 716     *merge_point = second_list;
 717
 718   return result;
 719
 720 #undef SUCCESSOR
 721 }
 722
 723 /* Sort doubly linked LIST of names, of given LENGTH, using COMPARE
 724    to order names.  Return the sorted list.  */
 725 static struct name *
 726 merge_sort (struct name *list, int length,
 727             int (*compare) (struct name const*, struct name const*))
 728 {
 729   struct name *head, *p, *prev;
 730   head = merge_sort_sll (list, length, compare);
 731   /* Fixup prev pointers */
 732   for (prev = NULL, p = head; p; prev = p, p = p->next)
 733     p->prev = prev;
 734   return head;
 735 }
 736
 737 /* A comparison function for sorting names.  Put found names last;
 738    break ties by string comparison.  */
 739
 740 static int
 741 compare_names_found (struct name const *n1, struct name const *n2)
 742 {
 743   int found_diff = WASFOUND (n2) - WASFOUND (n1);
 744   return found_diff ? found_diff : strcmp (n1->name, n2->name);
 745 }
 746
 747 /* Simple comparison by names. */
 748 static int
 749 compare_names (struct name const *n1, struct name const *n2)
 750 {
 751   return strcmp (n1->name, n2->name);
 752 }
 753
 754 \f
 755 /* Add all the dirs under NAME, which names a directory, to the namelist.
 756    If any of the files is a directory, recurse on the subdirectory.
 757    DEVICE is the device not to leave, if the -l option is specified.
 758    CMDLINE is true, if the NAME appeared on the command line. */
 759
 760 static void
 761 add_hierarchy_to_namelist (struct name *name, dev_t device, bool cmdline)
 762 {
 763   const char *buffer;
 764
 765   name_fill_directory (name, device, cmdline);
 766   buffer = directory_contents (name->directory);
 767   if (buffer)
 768     {
 769       struct name *child_head = NULL, *child_tail = NULL;
 770       size_t name_length = name->length;
 771       size_t allocated_length = (name_length >= NAME_FIELD_SIZE
 772                                  ? name_length + NAME_FIELD_SIZE
 773                                  : NAME_FIELD_SIZE);
 774       char *namebuf = xmalloc (allocated_length + 1);
 775                                 /* FIXME: + 2 above?  */
 776       const char *string;
 777       size_t string_length;
 778       int change_dir = name->change_dir;
 779
 780       strcpy (namebuf, name->name);
 781       if (! ISSLASH (namebuf[name_length - 1]))
 782         {
 783           namebuf[name_length++] = '/';
 784           namebuf[name_length] = '\0';
 785         }
 786
 787       for (string = buffer; *string; string += string_length + 1)
 788         {
 789           string_length = strlen (string);
 790           if (*string == 'D')
 791             {
 792               struct name *np;
 793
 794               if (allocated_length <= name_length + string_length)
 795                 {
 796                   do
 797                     {
 798                       allocated_length *= 2;
 799                       if (! allocated_length)
 800                         xalloc_die ();
 801                     }
 802                   while (allocated_length <= name_length + string_length);
 803
 804                   namebuf = xrealloc (namebuf, allocated_length + 1);
 805                 }
 806               strcpy (namebuf + name_length, string + 1);
 807               np = addname (namebuf, change_dir, false, name);
 808               if (!child_head)
 809                 child_head = np;
 810               else
 811                 child_tail->sibling = np;
 812               child_tail = np;
 813               add_hierarchy_to_namelist (np, device, false);
 814             }
 815         }
 816
 817       free (namebuf);
 818       name->child = child_head;
 819     }
 820 }
 821 \f
 822 /* Auxiliary functions for hashed table of struct name's. */
 823
 824 static size_t
 825 name_hash (void const *entry, size_t n_buckets)
 826 {
 827   struct name const *name = entry;
 828   return hash_string (name->caname, n_buckets);
 829 }
 830
 831 /* Compare two directories for equality of their names. */
 832 static bool
 833 name_compare (void const *entry1, void const *entry2)
 834 {
 835   struct name const *name1 = entry1;
 836   struct name const *name2 = entry2;
 837   return strcmp (name1->caname, name2->caname) == 0;
 838 }
 839
 840 \f
 841 /* Rebase `name' member of CHILD and all its siblings to
 842    the new PARENT. */
 843 static void
 844 rebase_child_list (struct name *child, struct name *parent)
 845 {
 846   size_t old_prefix_len = child->parent->length;
 847   size_t new_prefix_len = parent->length;
 848   char *new_prefix = parent->name;
 849
 850   for (; child; child = child->sibling)
 851     {
 852       size_t size = child->length - old_prefix_len + new_prefix_len;
 853       char *newp = xmalloc (size + 1);
 854       strcpy (newp, new_prefix);
 855       strcat (newp, child->name + old_prefix_len);
 856       free (child->name);
 857       child->name = newp;
 858       child->length = size;
 859
 860       rebase_directory (child->directory,
 861                         child->parent->name, old_prefix_len,
 862                         new_prefix, new_prefix_len);
 863     }
 864 }
 865
 866 /* Collect all the names from argv[] (or whatever), expand them into a
 867    directory tree, and sort them.  This gets only subdirectories, not
 868    all files.  */
 869
 870 void
 871 collect_and_sort_names (void)
 872 {
 873   struct name *name;
 874   struct name *next_name, *prev_name;
 875   int num_names;
 876   struct stat statbuf;
 877   Hash_table *nametab;
 878
 879   name_gather ();
 880
 881   if (!namelist)
 882     addname (".", 0, false, NULL);
 883
 884   if (listed_incremental_option)
 885     {
 886       switch (chdir_count ())
 887         {
 888         case 0:
 889           break;
 890
 891         case 1:
 892           if (namelist->change_dir == 0)
 893             USAGE_ERROR ((0, 0,
 894                           _("Using -C option inside file list is not "
 895                             "allowed with --listed-incremental")));
 896           break;
 897
 898         default:
 899           USAGE_ERROR ((0, 0,
 900                         _("Only one -C option is allowed with "
 901                           "--listed-incremental")));
 902         }
 903
 904       read_directory_file ();
 905     }
 906
 907   num_names = 0;
 908   for (name = namelist; name; name = name->next, num_names++)
 909     {
 910       if (name->found_count || name->directory)
 911         continue;
 912       if (name->matching_flags & EXCLUDE_WILDCARDS)
 913         /* NOTE: EXCLUDE_ANCHORED is not relevant here */
 914         /* FIXME: just skip regexps for now */
 915         continue;
 916       chdir_do (name->change_dir);
 917
 918       if (name->name[0] == 0)
 919         continue;
 920
 921       if (deref_stat (dereference_option, name->name, &statbuf) != 0)
 922         {
 923           stat_diag (name->name);
 924           continue;
 925         }
 926       if (S_ISDIR (statbuf.st_mode))
 927         {
 928           name->found_count++;
 929           add_hierarchy_to_namelist (name, statbuf.st_dev, true);
 930         }
 931     }
 932
 933   namelist = merge_sort (namelist, num_names, compare_names);
 934
 935   num_names = 0;
 936   nametab = hash_initialize (0, 0,
 937                              name_hash,
 938                              name_compare, NULL);
 939   for (name = namelist; name; name = next_name)
 940     {
 941       next_name = name->next;
 942       name->caname = normalize_filename (name->name);
 943       if (prev_name)
 944         {
 945           struct name *p = hash_lookup (nametab, name);
 946           if (p)
 947             {
 948               /* Keep the one listed in the command line */
 949               if (!name->parent)
 950                 {
 951                   if (p->child)
 952                     rebase_child_list (p->child, name);
 953                   /* FIXME: remove_directory (p->caname); ? */
 954                   remname (p);
 955                   free_name (p);
 956                   num_names--;
 957                 }
 958               else
 959                 {
 960                   if (name->child)
 961                     rebase_child_list (name->child, p);
 962                   /* FIXME: remove_directory (name->caname); ? */
 963                   remname (name);
 964                   free_name (name);
 965                   continue;
 966                 }
 967             }
 968         }
 969       name->found_count = 0;
 970       if (!hash_insert (nametab, name))
 971         xalloc_die ();
 972       prev_name = name;
 973       num_names++;
 974     }
 975   nametail = prev_name;
 976   hash_free (nametab);
 977
 978   namelist = merge_sort (namelist, num_names, compare_names_found);
 979
 980   if (listed_incremental_option)
 981     {
 982       for (name = namelist; name && name->name[0] == 0; name++)
 983         ;
 984       if (name)
 985         append_incremental_renames (name->directory);
 986     }
 987 }
 988
 989 /* This is like name_match, except that
 990     1. It returns a pointer to the name it matched, and doesn't set FOUND
 991     in structure. The caller will have to do that if it wants to.
 992     2. If the namelist is empty, it returns null, unlike name_match, which
 993     returns TRUE. */
 994 struct name *
 995 name_scan (const char *file_name)
 996 {
 997   size_t length = strlen (file_name);
 998
 999   while (1)
1000     {
1001       struct name *cursor = namelist_match (file_name, length);
1002       if (cursor)
1003         return cursor;
1004
1005       /* Filename from archive not found in namelist.  If we have the whole
1006          namelist here, just return 0.  Otherwise, read the next name in and
1007          compare it.  If this was the last name, namelist->found_count will
1008          remain on.  If not, we loop to compare the newly read name.  */
1009
1010       if (same_order_option && namelist && namelist->found_count)
1011         {
1012           name_gather ();       /* read one more */
1013           if (namelist->found_count)
1014             return 0;
1015         }
1016       else
1017         return 0;
1018     }
1019 }
1020
1021 /* This returns a name from the namelist which doesn't have ->found
1022    set.  It sets ->found before returning, so successive calls will
1023    find and return all the non-found names in the namelist.  */
1024 struct name *gnu_list_name;
1025
1026 struct name const *
1027 name_from_list ()
1028 {
1029   if (!gnu_list_name)
1030     gnu_list_name = namelist;
1031   while (gnu_list_name
1032          && (gnu_list_name->found_count || gnu_list_name->name[0] == 0))
1033     gnu_list_name = gnu_list_name->next;
1034   if (gnu_list_name)
1035     {
1036       gnu_list_name->found_count++;
1037       chdir_do (gnu_list_name->change_dir);
1038       return gnu_list_name;
1039     }
1040   return NULL;
1041 }
1042
1043 void
1044 blank_name_list (void)
1045 {
1046   struct name *name;
1047
1048   gnu_list_name = 0;
1049   for (name = namelist; name; name = name->next)
1050     name->found_count = 0;
1051 }
1052
1053 /* Yield a newly allocated file name consisting of FILE_NAME concatenated to
1054    NAME, with an intervening slash if FILE_NAME does not already end in one. */
1055 char *
1056 new_name (const char *file_name, const char *name)
1057 {
1058   size_t file_name_len = strlen (file_name);
1059   size_t namesize = strlen (name) + 1;
1060   int slash = file_name_len && ! ISSLASH (file_name[file_name_len - 1]);
1061   char *buffer = xmalloc (file_name_len + slash + namesize);
1062   memcpy (buffer, file_name, file_name_len);
1063   buffer[file_name_len] = '/';
1064   memcpy (buffer + file_name_len + slash, name, namesize);
1065   return buffer;
1066 }
1067
1068 /* Return nonzero if file NAME is excluded.  */
1069 bool
1070 excluded_name (char const *name)
1071 {
1072   return excluded_file_name (excluded, name + FILE_SYSTEM_PREFIX_LEN (name));
1073 }
1074 \f
1075 static Hash_table *individual_file_table;
1076
1077 static void
1078 register_individual_file (char const *name)
1079 {
1080   struct stat st;
1081
1082   if (deref_stat (dereference_option, name, &st) != 0)
1083     return; /* Will be complained about later */
1084   if (S_ISDIR (st.st_mode))
1085     return;
1086
1087   hash_string_insert (&individual_file_table, name);
1088 }
1089
1090 bool
1091 is_individual_file (char const *name)
1092 {
1093   return hash_string_lookup (individual_file_table, name);
1094 }
1095
1096 \f
1097
1098 /* Return the size of the prefix of FILE_NAME that is removed after
1099    stripping NUM leading file name components.  NUM must be
1100    positive.  */
1101
1102 size_t
1103 stripped_prefix_len (char const *file_name, size_t num)
1104 {
1105   char const *p = file_name + FILE_SYSTEM_PREFIX_LEN (file_name);
1106   while (ISSLASH (*p))
1107     p++;
1108   while (*p)
1109     {
1110       bool slash = ISSLASH (*p);
1111       p++;
1112       if (slash)
1113         {
1114           if (--num == 0)
1115             return p - file_name;
1116           while (ISSLASH (*p))
1117             p++;
1118         }
1119     }
1120   return -1;
1121 }
1122 \f
1123 /* Return nonzero if NAME contains ".." as a file name component.  */
1124 bool
1125 contains_dot_dot (char const *name)
1126 {
1127   char const *p = name + FILE_SYSTEM_PREFIX_LEN (name);
1128
1129   for (;; p++)
1130     {
1131       if (p[0] == '.' && p[1] == '.' && (ISSLASH (p[2]) || !p[2]))
1132         return 1;
1133
1134       while (! ISSLASH (*p))
1135         {
1136           if (! *p++)
1137             return 0;
1138         }
1139     }
1140 }