git.gag.com Git - debian/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 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 2, 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 /* Names from the command call.  */
 183
 184 static struct name *namelist;   /* first name in list, if any */
 185 static struct name **nametail = &namelist;      /* end of name list */
 186 static const char **name_array; /* store an array of names */
 187 static int allocated_names;     /* how big is the array? */
 188 static int names;               /* how many entries does it have? */
 189 static int name_index;          /* how many of the entries have we scanned? */
 190
 191 /* Initialize structures.  */
 192 void
 193 init_names (void)
 194 {
 195   allocated_names = 10;
 196   name_array = xmalloc (sizeof (const char *) * allocated_names);
 197   names = 0;
 198 }
 199
 200 /* Add NAME at end of name_array, reallocating it as necessary.  */
 201 void
 202 name_add (const char *name)
 203 {
 204   if (names == allocated_names)
 205     {
 206       allocated_names *= 2;
 207       name_array =
 208         xrealloc (name_array, sizeof (const char *) * allocated_names);
 209     }
 210   name_array[names++] = name;
 211 }
 212 \f
 213 /* Names from external name file.  */
 214
 215 static char *name_buffer;       /* buffer to hold the current file name */
 216 static size_t name_buffer_length; /* allocated length of name_buffer */
 217
 218 /* FIXME: I should better check more closely.  It seems at first glance that
 219    is_pattern is only used when reading a file, and ignored for all
 220    command line arguments.  */
 221
 222 static inline int
 223 is_pattern (const char *string)
 224 {
 225   return strchr (string, '*') || strchr (string, '[') || strchr (string, '?');
 226 }
 227
 228 /* Set up to gather file names for tar.  They can either come from a
 229    file or were saved from decoding arguments.  */
 230 void
 231 name_init (void)
 232 {
 233   name_buffer = xmalloc (NAME_FIELD_SIZE + 2);
 234   name_buffer_length = NAME_FIELD_SIZE;
 235 }
 236
 237 void
 238 name_term (void)
 239 {
 240   free (name_buffer);
 241   free (name_array);
 242 }
 243
 244 /* Get the next name from ARGV or the file of names.  Result is in
 245    static storage and can't be relied upon across two calls.
 246
 247    If CHANGE_DIRS is true, treat a filename of the form "-C" as
 248    meaning that the next filename is the name of a directory to change
 249    to.  If filename_terminator is NUL, CHANGE_DIRS is effectively
 250    always false.  */
 251 char *
 252 name_next (int change_dirs)
 253 {
 254   const char *source;
 255   char *cursor;
 256   int chdir_flag = 0;
 257
 258   if (filename_terminator == '\0')
 259     change_dirs = 0;
 260
 261   while (name_index != names)
 262     {
 263       size_t source_len;
 264       source = name_array[name_index++];
 265       source_len = strlen (source);
 266       if (name_buffer_length < source_len)
 267         {
 268           do
 269             {
 270               name_buffer_length *= 2;
 271               if (! name_buffer_length)
 272                 xalloc_die ();
 273             }
 274           while (name_buffer_length < source_len);
 275
 276           free (name_buffer);
 277           name_buffer = xmalloc (name_buffer_length + 2);
 278         }
 279       strcpy (name_buffer, source);
 280
 281       /* Zap trailing slashes.  */
 282
 283       cursor = name_buffer + strlen (name_buffer) - 1;
 284       while (cursor > name_buffer && ISSLASH (*cursor))
 285         *cursor-- = '\0';
 286
 287       if (chdir_flag)
 288         {
 289           if (chdir (name_buffer) < 0)
 290             chdir_fatal (name_buffer);
 291           chdir_flag = 0;
 292         }
 293       else if (change_dirs && strcmp (name_buffer, "-C") == 0)
 294         chdir_flag = 1;
 295       else
 296         {
 297           if (unquote_option)
 298             unquote_string (name_buffer);
 299           if (incremental_option)
 300             register_individual_file (name_buffer);
 301           return name_buffer;
 302         }
 303     }
 304
 305   return 0;
 306 }
 307
 308 /* Gather names in a list for scanning.  Could hash them later if we
 309    really care.
 310
 311    If the names are already sorted to match the archive, we just read
 312    them one by one.  name_gather reads the first one, and it is called
 313    by name_match as appropriate to read the next ones.  At EOF, the
 314    last name read is just left in the buffer.  This option lets users
 315    of small machines extract an arbitrary number of files by doing
 316    "tar t" and editing down the list of files.  */
 317
 318 void
 319 name_gather (void)
 320 {
 321   /* Buffer able to hold a single name.  */
 322   static struct name *buffer;
 323   static size_t allocated_size;
 324
 325   char const *name;
 326
 327   if (same_order_option)
 328     {
 329       static int change_dir;
 330
 331       if (allocated_size == 0)
 332         {
 333           allocated_size = offsetof (struct name, name) + NAME_FIELD_SIZE + 1;
 334           buffer = xmalloc (allocated_size);
 335           /* FIXME: This memset is overkill, and ugly...  */
 336           memset (buffer, 0, allocated_size);
 337         }
 338
 339       while ((name = name_next (0)) && strcmp (name, "-C") == 0)
 340         {
 341           char const *dir = name_next (0);
 342           if (! dir)
 343             FATAL_ERROR ((0, 0, _("Missing file name after -C")));
 344           change_dir = chdir_arg (xstrdup (dir));
 345         }
 346
 347       if (name)
 348         {
 349           size_t needed_size;
 350           buffer->length = strlen (name);
 351           needed_size = offsetof (struct name, name) + buffer->length + 1;
 352           if (allocated_size < needed_size)
 353             {
 354               do
 355                 {
 356                   allocated_size *= 2;
 357                   if (! allocated_size)
 358                     xalloc_die ();
 359                 }
 360               while (allocated_size < needed_size);
 361
 362               buffer = xrealloc (buffer, allocated_size);
 363             }
 364           buffer->change_dir = change_dir;
 365           strcpy (buffer->name, name);
 366           buffer->next = 0;
 367           buffer->found_count = 0;
 368
 369           namelist = buffer;
 370           nametail = &namelist->next;
 371         }
 372       else if (change_dir)
 373         addname (0, change_dir);
 374     }
 375   else
 376     {
 377       /* Non sorted names -- read them all in.  */
 378       int change_dir = 0;
 379
 380       for (;;)
 381         {
 382           int change_dir0 = change_dir;
 383           while ((name = name_next (0)) && strcmp (name, "-C") == 0)
 384             {
 385               char const *dir = name_next (0);
 386               if (! dir)
 387                 FATAL_ERROR ((0, 0, _("Missing file name after -C")));
 388               change_dir = chdir_arg (xstrdup (dir));
 389             }
 390           if (name)
 391             addname (name, change_dir);
 392           else
 393             {
 394               if (change_dir != change_dir0)
 395                 addname (0, change_dir);
 396               break;
 397             }
 398         }
 399     }
 400 }
 401
 402 /*  Add a name to the namelist.  */
 403 struct name *
 404 addname (char const *string, int change_dir)
 405 {
 406   size_t length = string ? strlen (string) : 0;
 407   struct name *name = xmalloc (offsetof (struct name, name) + length + 1);
 408
 409   if (string)
 410     {
 411       name->fake = 0;
 412       strcpy (name->name, string);
 413     }
 414   else
 415     {
 416       name->fake = 1;
 417
 418       /* FIXME: This initialization (and the byte of memory that it
 419          initializes) is probably not needed, but we are currently in
 420          bug-fix mode so we'll leave it in for now.  */
 421       name->name[0] = 0;
 422     }
 423
 424   name->next = 0;
 425   name->length = length;
 426   name->found_count = 0;
 427   name->regexp = 0;             /* assume not a regular expression */
 428   name->firstch = 1;            /* assume first char is literal */
 429   name->change_dir = change_dir;
 430   name->dir_contents = 0;
 431
 432   if (string && is_pattern (string))
 433     {
 434       name->regexp = 1;
 435       if (string[0] == '*' || string[0] == '[' || string[0] == '?')
 436         name->firstch = 0;
 437     }
 438
 439   *nametail = name;
 440   nametail = &name->next;
 441   return name;
 442 }
 443
 444 /* Find a match for FILE_NAME (whose string length is LENGTH) in the name
 445    list.  */
 446 static struct name *
 447 namelist_match (char const *file_name, size_t length)
 448 {
 449   struct name *p;
 450
 451   for (p = namelist; p; p = p->next)
 452     {
 453       /* If first chars don't match, quick skip.  */
 454
 455       if (p->firstch && p->name[0] != file_name[0])
 456         continue;
 457
 458       if (p->regexp
 459           ? fnmatch (p->name, file_name, recursion_option) == 0
 460           : (p->length <= length
 461              && (file_name[p->length] == '\0'
 462                  || (ISSLASH (file_name[p->length]) && recursion_option))
 463              && memcmp (file_name, p->name, p->length) == 0))
 464         return p;
 465     }
 466
 467   return 0;
 468 }
 469
 470 /* Return true if and only if name FILE_NAME (from an archive) matches any
 471    name from the namelist.  */
 472 int
 473 name_match (const char *file_name)
 474 {
 475   size_t length = strlen (file_name);
 476
 477   while (1)
 478     {
 479       struct name *cursor = namelist;
 480
 481       if (!cursor)
 482         return 1;
 483
 484       if (cursor->fake)
 485         {
 486           chdir_do (cursor->change_dir);
 487           namelist = 0;
 488           nametail = &namelist;
 489           return 1;
 490         }
 491
 492       cursor = namelist_match (file_name, length);
 493       if (cursor)
 494         {
 495           if (!(ISSLASH (file_name[cursor->length]) && recursion_option)
 496               || cursor->found_count == 0)
 497             cursor->found_count++; /* remember it matched */
 498           if (starting_file_option)
 499             {
 500               free (namelist);
 501               namelist = 0;
 502               nametail = &namelist;
 503             }
 504           chdir_do (cursor->change_dir);
 505
 506           /* We got a match.  */
 507           return ISFOUND (cursor);
 508         }
 509
 510       /* Filename from archive not found in namelist.  If we have the whole
 511          namelist here, just return 0.  Otherwise, read the next name in and
 512          compare it.  If this was the last name, namelist->found_count will
 513          remain on.  If not, we loop to compare the newly read name.  */
 514
 515       if (same_order_option && namelist->found_count)
 516         {
 517           name_gather ();       /* read one more */
 518           if (namelist->found_count)
 519             return 0;
 520         }
 521       else
 522         return 0;
 523     }
 524 }
 525
 526 /* Returns true if all names from the namelist were processed.
 527    P is the stat_info of the most recently processed entry.
 528    The decision is postponed until the next entry is read if:
 529
 530    1) P ended with a slash (i.e. it was a directory)
 531    2) P matches any entry from the namelist *and* represents a subdirectory
 532    or a file lying under this entry (in the terms of directory structure).
 533
 534    This is necessary to handle contents of directories. */
 535 bool
 536 all_names_found (struct tar_stat_info *p)
 537 {
 538   struct name const *cursor;
 539   size_t len;
 540
 541   if (!p->file_name || occurrence_option == 0 || p->had_trailing_slash)
 542     return false;
 543   len = strlen (p->file_name);
 544   for (cursor = namelist; cursor; cursor = cursor->next)
 545     {
 546       if (cursor->regexp
 547           || (!WASFOUND(cursor) && !cursor->fake)
 548           || (len >= cursor->length && ISSLASH (p->file_name[cursor->length])))
 549         return false;
 550     }
 551   return true;
 552 }
 553
 554 /* Print the names of things in the namelist that were not matched.  */
 555 void
 556 names_notfound (void)
 557 {
 558   struct name const *cursor;
 559
 560   for (cursor = namelist; cursor; cursor = cursor->next)
 561     if (!WASFOUND(cursor) && !cursor->fake)
 562       {
 563         if (cursor->found_count == 0)
 564           ERROR ((0, 0, _("%s: Not found in archive"),
 565                   quotearg_colon (cursor->name)));
 566         else
 567           ERROR ((0, 0, _("%s: Required occurrence not found in archive"),
 568                   quotearg_colon (cursor->name)));
 569       }
 570
 571   /* Don't bother freeing the name list; we're about to exit.  */
 572   namelist = 0;
 573   nametail = &namelist;
 574
 575   if (same_order_option)
 576     {
 577       char *name;
 578
 579       while ((name = name_next (1)) != NULL)
 580         ERROR ((0, 0, _("%s: Not found in archive"),
 581                 quotearg_colon (name)));
 582     }
 583 }
 584 \f
 585 /* Sorting name lists.  */
 586
 587 /* Sort linked LIST of names, of given LENGTH, using COMPARE to order
 588    names.  Return the sorted list.  Apart from the type `struct name'
 589    and the definition of SUCCESSOR, this is a generic list-sorting
 590    function, but it's too painful to make it both generic and portable
 591    in C.  */
 592
 593 static struct name *
 594 merge_sort (struct name *list, int length,
 595             int (*compare) (struct name const*, struct name const*))
 596 {
 597   struct name *first_list;
 598   struct name *second_list;
 599   int first_length;
 600   int second_length;
 601   struct name *result;
 602   struct name **merge_point;
 603   struct name *cursor;
 604   int counter;
 605
 606 # define SUCCESSOR(name) ((name)->next)
 607
 608   if (length == 1)
 609     return list;
 610
 611   if (length == 2)
 612     {
 613       if ((*compare) (list, SUCCESSOR (list)) > 0)
 614         {
 615           result = SUCCESSOR (list);
 616           SUCCESSOR (result) = list;
 617           SUCCESSOR (list) = 0;
 618           return result;
 619         }
 620       return list;
 621     }
 622
 623   first_list = list;
 624   first_length = (length + 1) / 2;
 625   second_length = length / 2;
 626   for (cursor = list, counter = first_length - 1;
 627        counter;
 628        cursor = SUCCESSOR (cursor), counter--)
 629     continue;
 630   second_list = SUCCESSOR (cursor);
 631   SUCCESSOR (cursor) = 0;
 632
 633   first_list = merge_sort (first_list, first_length, compare);
 634   second_list = merge_sort (second_list, second_length, compare);
 635
 636   merge_point = &result;
 637   while (first_list && second_list)
 638     if ((*compare) (first_list, second_list) < 0)
 639       {
 640         cursor = SUCCESSOR (first_list);
 641         *merge_point = first_list;
 642         merge_point = &SUCCESSOR (first_list);
 643         first_list = cursor;
 644       }
 645     else
 646       {
 647         cursor = SUCCESSOR (second_list);
 648         *merge_point = second_list;
 649         merge_point = &SUCCESSOR (second_list);
 650         second_list = cursor;
 651       }
 652   if (first_list)
 653     *merge_point = first_list;
 654   else
 655     *merge_point = second_list;
 656
 657   return result;
 658
 659 #undef SUCCESSOR
 660 }
 661
 662 /* A comparison function for sorting names.  Put found names last;
 663    break ties by string comparison.  */
 664
 665 static int
 666 compare_names (struct name const *n1, struct name const *n2)
 667 {
 668   int found_diff = WASFOUND(n2) - WASFOUND(n1);
 669   return found_diff ? found_diff : strcmp (n1->name, n2->name);
 670 }
 671 \f
 672 /* Add all the dirs under NAME, which names a directory, to the namelist.
 673    If any of the files is a directory, recurse on the subdirectory.
 674    DEVICE is the device not to leave, if the -l option is specified.  */
 675
 676 static void
 677 add_hierarchy_to_namelist (struct name *name, dev_t device)
 678 {
 679   char *file_name = name->name;
 680   char *buffer = get_directory_contents (file_name, device);
 681
 682   if (! buffer)
 683     name->dir_contents = "\0\0\0\0";
 684   else
 685     {
 686       size_t name_length = name->length;
 687       size_t allocated_length = (name_length >= NAME_FIELD_SIZE
 688                                  ? name_length + NAME_FIELD_SIZE
 689                                  : NAME_FIELD_SIZE);
 690       char *namebuf = xmalloc (allocated_length + 1);
 691                                 /* FIXME: + 2 above?  */
 692       char *string;
 693       size_t string_length;
 694       int change_dir = name->change_dir;
 695
 696       name->dir_contents = buffer;
 697       strcpy (namebuf, file_name);
 698       if (! ISSLASH (namebuf[name_length - 1]))
 699         {
 700           namebuf[name_length++] = '/';
 701           namebuf[name_length] = '\0';
 702         }
 703
 704       for (string = buffer; *string; string += string_length + 1)
 705         {
 706           string_length = strlen (string);
 707           if (*string == 'D')
 708             {
 709               if (allocated_length <= name_length + string_length)
 710                 {
 711                   do
 712                     {
 713                       allocated_length *= 2;
 714                       if (! allocated_length)
 715                         xalloc_die ();
 716                     }
 717                   while (allocated_length <= name_length + string_length);
 718
 719                   namebuf = xrealloc (namebuf, allocated_length + 1);
 720                 }
 721               strcpy (namebuf + name_length, string + 1);
 722               add_hierarchy_to_namelist (addname (namebuf, change_dir),
 723                                          device);
 724             }
 725         }
 726
 727       free (namebuf);
 728     }
 729 }
 730 \f
 731 /* Collect all the names from argv[] (or whatever), expand them into a
 732    directory tree, and sort them.  This gets only subdirectories, not
 733    all files.  */
 734
 735 void
 736 collect_and_sort_names (void)
 737 {
 738   struct name *name;
 739   struct name *next_name;
 740   int num_names;
 741   struct stat statbuf;
 742
 743   name_gather ();
 744
 745   if (listed_incremental_option)
 746     read_directory_file ();
 747
 748   if (!namelist)
 749     addname (".", 0);
 750
 751   for (name = namelist; name; name = next_name)
 752     {
 753       next_name = name->next;
 754       if (name->found_count || name->dir_contents)
 755         continue;
 756       if (name->regexp)         /* FIXME: just skip regexps for now */
 757         continue;
 758       chdir_do (name->change_dir);
 759       if (name->fake)
 760         continue;
 761
 762       if (deref_stat (dereference_option, name->name, &statbuf) != 0)
 763         {
 764           stat_diag (name->name);
 765           continue;
 766         }
 767       if (S_ISDIR (statbuf.st_mode))
 768         {
 769           name->found_count++;
 770           add_hierarchy_to_namelist (name, statbuf.st_dev);
 771         }
 772     }
 773
 774   num_names = 0;
 775   for (name = namelist; name; name = name->next)
 776     num_names++;
 777   namelist = merge_sort (namelist, num_names, compare_names);
 778
 779   for (name = namelist; name; name = name->next)
 780     name->found_count = 0;
 781 }
 782
 783 /* This is like name_match, except that it returns a pointer to the
 784    name it matched, and doesn't set FOUND in structure.  The caller
 785    will have to do that if it wants to.  Oh, and if the namelist is
 786    empty, it returns null, unlike name_match, which returns TRUE.  */
 787 struct name *
 788 name_scan (const char *file_name)
 789 {
 790   size_t length = strlen (file_name);
 791
 792   while (1)
 793     {
 794       struct name *cursor = namelist_match (file_name, length);
 795       if (cursor)
 796         return cursor;
 797
 798       /* Filename from archive not found in namelist.  If we have the whole
 799          namelist here, just return 0.  Otherwise, read the next name in and
 800          compare it.  If this was the last name, namelist->found_count will
 801          remain on.  If not, we loop to compare the newly read name.  */
 802
 803       if (same_order_option && namelist && namelist->found_count)
 804         {
 805           name_gather ();       /* read one more */
 806           if (namelist->found_count)
 807             return 0;
 808         }
 809       else
 810         return 0;
 811     }
 812 }
 813
 814 /* This returns a name from the namelist which doesn't have ->found
 815    set.  It sets ->found before returning, so successive calls will
 816    find and return all the non-found names in the namelist.  */
 817 struct name *gnu_list_name;
 818
 819 char *
 820 name_from_list (void)
 821 {
 822   if (!gnu_list_name)
 823     gnu_list_name = namelist;
 824   while (gnu_list_name && (gnu_list_name->found_count || gnu_list_name->fake))
 825     gnu_list_name = gnu_list_name->next;
 826   if (gnu_list_name)
 827     {
 828       gnu_list_name->found_count++;
 829       chdir_do (gnu_list_name->change_dir);
 830       return gnu_list_name->name;
 831     }
 832   return 0;
 833 }
 834
 835 void
 836 blank_name_list (void)
 837 {
 838   struct name *name;
 839
 840   gnu_list_name = 0;
 841   for (name = namelist; name; name = name->next)
 842     name->found_count = 0;
 843 }
 844
 845 /* Yield a newly allocated file name consisting of FILE_NAME concatenated to
 846    NAME, with an intervening slash if FILE_NAME does not already end in one.  */
 847 char *
 848 new_name (const char *file_name, const char *name)
 849 {
 850   size_t file_name_len = strlen (file_name);
 851   size_t namesize = strlen (name) + 1;
 852   int slash = file_name_len && ! ISSLASH (file_name[file_name_len - 1]);
 853   char *buffer = xmalloc (file_name_len + slash + namesize);
 854   memcpy (buffer, file_name, file_name_len);
 855   buffer[file_name_len] = '/';
 856   memcpy (buffer + file_name_len + slash, name, namesize);
 857   return buffer;
 858 }
 859
 860 /* Return nonzero if file NAME is excluded.  */
 861 bool
 862 excluded_name (char const *name)
 863 {
 864   return excluded_filename (excluded, name + FILE_SYSTEM_PREFIX_LEN (name));
 865 }
 866 \f
 867 /* Hash tables of strings.  */
 868
 869 /* Calculate the hash of a string.  */
 870 static size_t
 871 hash_string_hasher (void const *name, size_t n_buckets)
 872 {
 873   return hash_string (name, n_buckets);
 874 }
 875
 876 /* Compare two strings for equality.  */
 877 static bool
 878 hash_string_compare (void const *name1, void const *name2)
 879 {
 880   return strcmp (name1, name2) == 0;
 881 }
 882
 883 /* Return zero if TABLE contains a copy of STRING; otherwise, insert a
 884    copy of STRING to TABLE and return 1.  */
 885 static bool
 886 hash_string_insert (Hash_table **table, char const *string)
 887 {
 888   Hash_table *t = *table;
 889   char *s = xstrdup (string);
 890   char *e;
 891
 892   if (! ((t
 893           || (*table = t = hash_initialize (0, 0, hash_string_hasher,
 894                                             hash_string_compare, 0)))
 895          && (e = hash_insert (t, s))))
 896     xalloc_die ();
 897
 898   if (e == s)
 899     return 1;
 900   else
 901     {
 902       free (s);
 903       return 0;
 904     }
 905 }
 906
 907 /* Return 1 if TABLE contains STRING.  */
 908 static bool
 909 hash_string_lookup (Hash_table const *table, char const *string)
 910 {
 911   return table && hash_lookup (table, string);
 912 }
 913 \f
 914 /* Names to avoid dumping.  */
 915 static Hash_table *avoided_name_table;
 916
 917 /* Remember to not archive NAME.  */
 918 void
 919 add_avoided_name (char const *name)
 920 {
 921   hash_string_insert (&avoided_name_table, name);
 922 }
 923
 924 /* Should NAME be avoided when archiving?  */
 925 bool
 926 is_avoided_name (char const *name)
 927 {
 928   return hash_string_lookup (avoided_name_table, name);
 929 }
 930
 931 \f
 932 static Hash_table *individual_file_table;
 933
 934 static void
 935 register_individual_file (char const *name)
 936 {
 937   struct stat st;
 938
 939   if (deref_stat (dereference_option, name, &st) != 0)
 940     return; /* Will be complained about later */
 941   if (S_ISDIR (st.st_mode))
 942     return;
 943
 944   hash_string_insert (&individual_file_table, name);
 945 }
 946
 947 bool
 948 is_individual_file (char const *name)
 949 {
 950   return hash_string_lookup (individual_file_table, name);
 951 }
 952
 953 \f
 954
 955 static Hash_table *prefix_table[2];
 956
 957 /* Return true if file names of some members in the archive were stripped off
 958    their leading components. We could have used
 959         return prefix_table[0] || prefix_table[1]
 960    but the following seems to be safer: */
 961 bool
 962 removed_prefixes_p (void)
 963 {
 964   return (prefix_table[0] && hash_get_n_entries (prefix_table[0]) != 0)
 965          || (prefix_table[1] && hash_get_n_entries (prefix_table[1]) != 0);
 966 }
 967
 968 /* Return a safer suffix of FILE_NAME, or "." if it has no safer
 969    suffix.  Check for fully specified file names and other atrocities.
 970    Warn the user if we do not return NAME.  If LINK_TARGET is 1,
 971    FILE_NAME is the target of a hard link, not a member name.  */
 972
 973 char *
 974 safer_name_suffix (char const *file_name, bool link_target)
 975 {
 976   char const *p;
 977
 978   if (absolute_names_option)
 979     p = file_name;
 980   else
 981     {
 982       /* Skip file system prefixes, leading file name components that contain
 983          "..", and leading slashes.  */
 984
 985       size_t prefix_len = FILE_SYSTEM_PREFIX_LEN (file_name);
 986
 987       for (p = file_name + prefix_len; *p; )
 988         {
 989           if (p[0] == '.' && p[1] == '.' && (ISSLASH (p[2]) || !p[2]))
 990             prefix_len = p + 2 - file_name;
 991
 992           do
 993             {
 994               char c = *p++;
 995               if (ISSLASH (c))
 996                 break;
 997             }
 998           while (*p);
 999         }
1000
1001       for (p = file_name + prefix_len; ISSLASH (*p); p++)
1002         continue;
1003       prefix_len = p - file_name;
1004
1005       if (prefix_len)
1006         {
1007           char *prefix = alloca (prefix_len + 1);
1008           memcpy (prefix, file_name, prefix_len);
1009           prefix[prefix_len] = '\0';
1010
1011           if (hash_string_insert (&prefix_table[link_target], prefix))
1012             {
1013               static char const *const diagnostic[] =
1014               {
1015                 N_("Removing leading `%s' from member names"),
1016                 N_("Removing leading `%s' from hard link targets")
1017               };
1018               WARN ((0, 0, _(diagnostic[link_target]), prefix));
1019             }
1020         }
1021     }
1022
1023   if (! *p)
1024     {
1025       if (p == file_name)
1026         {
1027           static char const *const diagnostic[] =
1028           {
1029             N_("Substituting `.' for empty member name"),
1030             N_("Substituting `.' for empty hard link target")
1031           };
1032           WARN ((0, 0, "%s", _(diagnostic[link_target])));
1033         }
1034
1035       p = ".";
1036     }
1037
1038   return (char *) p;
1039 }
1040 \f
1041 /* Return the size of the prefix of FILE_NAME that is removed after
1042    stripping NUM leading file name components.  NUM must be
1043    positive.  */
1044
1045 size_t
1046 stripped_prefix_len (char const *file_name, size_t num)
1047 {
1048   char const *p = file_name + FILE_SYSTEM_PREFIX_LEN (file_name);
1049   while (ISSLASH (*p))
1050     p++;
1051   while (*p)
1052     {
1053       bool slash = ISSLASH (*p);
1054       p++;
1055       if (slash)
1056         {
1057           if (--num == 0)
1058             return p - file_name;
1059           while (ISSLASH (*p))
1060             p++;
1061         }
1062     }
1063   return -1;
1064 }
1065 \f
1066 /* Return nonzero if NAME contains ".." as a file name component.  */
1067 bool
1068 contains_dot_dot (char const *name)
1069 {
1070   char const *p = name + FILE_SYSTEM_PREFIX_LEN (name);
1071
1072   for (;; p++)
1073     {
1074       if (p[0] == '.' && p[1] == '.' && (ISSLASH (p[2]) || !p[2]))
1075         return 1;
1076
1077       do
1078         {
1079           if (! *p++)
1080             return 0;
1081         }
1082       while (! ISSLASH (*p));
1083     }
1084 }