contrib/tar/src/names.c

   1 /* Various processing of names.
   2
   3    Copyright 1988, 1992, 1994, 1996, 1997, 1998, 1999, 2000, 2001 Free
   4    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    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  19
  20 /* $FreeBSD: src/contrib/tar/src/names.c,v 1.2.2.1 2002/07/14 13:19:44 sobomax Exp $ */
  21
  22 #include "system.h"
  23
  24 #include <fnmatch.h>
  25 #include <grp.h>
  26 #include <hash.h>
  27 #include <pwd.h>
  28 #include <quotearg.h>
  29
  30 #include "common.h"
  31 \f
  32 /* User and group names.  */
  33
  34 struct group *getgrnam ();
  35 struct passwd *getpwnam ();
  36 #if ! HAVE_DECL_GETPWUID
  37 struct passwd *getpwuid ();
  38 #endif
  39 #if ! HAVE_DECL_GETGRGID
  40 struct group *getgrgid ();
  41 #endif
  42
  43 /* Make sure you link with the proper libraries if you are running the
  44    Yellow Peril (thanks for the good laugh, Ian J.!), or, euh... NIS.
  45    This code should also be modified for non-UNIX systems to do something
  46    reasonable.  */
  47
  48 static char cached_uname[UNAME_FIELD_SIZE];
  49 static char cached_gname[GNAME_FIELD_SIZE];
  50
  51 static uid_t cached_uid;        /* valid only if cached_uname is not empty */
  52 static gid_t cached_gid;        /* valid only if cached_gname is not empty */
  53
  54 /* These variables are valid only if nonempty.  */
  55 static char cached_no_such_uname[UNAME_FIELD_SIZE];
  56 static char cached_no_such_gname[GNAME_FIELD_SIZE];
  57
  58 /* These variables are valid only if nonzero.  It's not worth optimizing
  59    the case for weird systems where 0 is not a valid uid or gid.  */
  60 static uid_t cached_no_such_uid;
  61 static gid_t cached_no_such_gid;
  62
  63 /* Given UID, find the corresponding UNAME.  */
  64 void
  65 uid_to_uname (uid_t uid, char uname[UNAME_FIELD_SIZE])
  66 {
  67   struct passwd *passwd;
  68
  69   if (uid != 0 && uid == cached_no_such_uid)
  70     {
  71       *uname = '\0';
  72       return;
  73     }
  74
  75   if (!cached_uname[0] || uid != cached_uid)
  76     {
  77       passwd = getpwuid (uid);
  78       if (passwd)
  79         {
  80           cached_uid = uid;
  81           strncpy (cached_uname, passwd->pw_name, UNAME_FIELD_SIZE);
  82         }
  83       else
  84         {
  85           cached_no_such_uid = uid;
  86           *uname = '\0';
  87           return;
  88         }
  89     }
  90   strncpy (uname, cached_uname, UNAME_FIELD_SIZE);
  91 }
  92
  93 /* Given GID, find the corresponding GNAME.  */
  94 void
  95 gid_to_gname (gid_t gid, char gname[GNAME_FIELD_SIZE])
  96 {
  97   struct group *group;
  98
  99   if (gid != 0 && gid == cached_no_such_gid)
 100     {
 101       *gname = '\0';
 102       return;
 103     }
 104
 105   if (!cached_gname[0] || gid != cached_gid)
 106     {
 107       group = getgrgid (gid);
 108       if (group)
 109         {
 110           cached_gid = gid;
 111           strncpy (cached_gname, group->gr_name, GNAME_FIELD_SIZE);
 112         }
 113       else
 114         {
 115           cached_no_such_gid = gid;
 116           *gname = '\0';
 117           return;
 118         }
 119     }
 120   strncpy (gname, cached_gname, GNAME_FIELD_SIZE);
 121 }
 122
 123 /* Given UNAME, set the corresponding UID and return 1, or else, return 0.  */
 124 int
 125 uname_to_uid (char uname[UNAME_FIELD_SIZE], uid_t *uidp)
 126 {
 127   struct passwd *passwd;
 128
 129   if (cached_no_such_uname[0]
 130       && strncmp (uname, cached_no_such_uname, UNAME_FIELD_SIZE) == 0)
 131     return 0;
 132
 133   if (!cached_uname[0]
 134       || uname[0] != cached_uname[0]
 135       || strncmp (uname, cached_uname, UNAME_FIELD_SIZE) != 0)
 136     {
 137       passwd = getpwnam (uname);
 138       if (passwd)
 139         {
 140           cached_uid = passwd->pw_uid;
 141           strncpy (cached_uname, uname, UNAME_FIELD_SIZE);
 142         }
 143       else
 144         {
 145           strncpy (cached_no_such_uname, uname, UNAME_FIELD_SIZE);
 146           return 0;
 147         }
 148     }
 149   *uidp = cached_uid;
 150   return 1;
 151 }
 152
 153 /* Given GNAME, set the corresponding GID and return 1, or else, return 0.  */
 154 int
 155 gname_to_gid (char gname[GNAME_FIELD_SIZE], gid_t *gidp)
 156 {
 157   struct group *group;
 158
 159   if (cached_no_such_gname[0]
 160       && strncmp (gname, cached_no_such_gname, GNAME_FIELD_SIZE) == 0)
 161     return 0;
 162
 163   if (!cached_gname[0]
 164       || gname[0] != cached_gname[0]
 165       || strncmp (gname, cached_gname, GNAME_FIELD_SIZE) != 0)
 166     {
 167       group = getgrnam (gname);
 168       if (group)
 169         {
 170           cached_gid = group->gr_gid;
 171           strncpy (cached_gname, gname, GNAME_FIELD_SIZE);
 172         }
 173       else
 174         {
 175           strncpy (cached_no_such_gname, gname, GNAME_FIELD_SIZE);
 176           return 0;
 177         }
 178     }
 179   *gidp = cached_gid;
 180   return 1;
 181 }
 182 \f
 183 /* Names from the command call.  */
 184
 185 static struct name *namelist;   /* first name in list, if any */
 186 static struct name **nametail = &namelist;      /* end of name list */
 187 static const char **name_array; /* store an array of names */
 188 static int allocated_names;     /* how big is the array? */
 189 static int names;               /* how many entries does it have? */
 190 static int name_index;          /* how many of the entries have we scanned? */
 191
 192 /* Initialize structures.  */
 193 void
 194 init_names (void)
 195 {
 196   allocated_names = 10;
 197   name_array = xmalloc (sizeof (const char *) * allocated_names);
 198   names = 0;
 199 }
 200
 201 /* Add NAME at end of name_array, reallocating it as necessary.  */
 202 void
 203 name_add (const char *name)
 204 {
 205   if (names == allocated_names)
 206     {
 207       allocated_names *= 2;
 208       name_array =
 209         xrealloc (name_array, sizeof (const char *) * allocated_names);
 210     }
 211   name_array[names++] = name;
 212 }
 213 \f
 214 /* Names from external name file.  */
 215
 216 static FILE *name_file;         /* file to read names from */
 217 static char *name_buffer;       /* buffer to hold the current file name */
 218 static size_t name_buffer_length; /* allocated length of name_buffer */
 219
 220 /* FIXME: I should better check more closely.  It seems at first glance that
 221    is_pattern is only used when reading a file, and ignored for all
 222    command line arguments.  */
 223
 224 static inline int
 225 is_pattern (const char *string)
 226 {
 227   return strchr (string, '*') || strchr (string, '[') || strchr (string, '?');
 228 }
 229
 230 /* Set up to gather file names for tar.  They can either come from a
 231    file or were saved from decoding arguments.  */
 232 void
 233 name_init (int argc, char *const *argv)
 234 {
 235   name_buffer = xmalloc (NAME_FIELD_SIZE + 2);
 236   name_buffer_length = NAME_FIELD_SIZE;
 237
 238   if (files_from_option)
 239     {
 240       if (!strcmp (files_from_option, "-"))
 241         {
 242           request_stdin ("-T");
 243           name_file = stdin;
 244         }
 245       else if (name_file = fopen (files_from_option, "r"), !name_file)
 246         open_fatal (files_from_option);
 247     }
 248 }
 249
 250 void
 251 name_term (void)
 252 {
 253   free (name_buffer);
 254   free (name_array);
 255 }
 256
 257 /* Read the next filename from name_file and null-terminate it.  Put
 258    it into name_buffer, reallocating and adjusting name_buffer_length
 259    if necessary.  Return 0 at end of file, 1 otherwise.  */
 260 static int
 261 read_name_from_file (void)
 262 {
 263   int character;
 264   size_t counter = 0;
 265
 266   /* FIXME: getc may be called even if character was EOF the last time here.  */
 267
 268   /* FIXME: This + 2 allocation might serve no purpose.  */
 269
 270   while (character = getc (name_file),
 271          character != EOF && character != filename_terminator)
 272     {
 273       if (counter == name_buffer_length)
 274         {
 275           if (name_buffer_length * 2 < name_buffer_length)
 276             xalloc_die ();
 277           name_buffer_length *= 2;
 278           name_buffer = xrealloc (name_buffer, name_buffer_length + 2);
 279         }
 280       name_buffer[counter++] = character;
 281     }
 282
 283   if (counter == 0 && character == EOF)
 284     return 0;
 285
 286   if (counter == name_buffer_length)
 287     {
 288       if (name_buffer_length * 2 < name_buffer_length)
 289         xalloc_die ();
 290       name_buffer_length *= 2;
 291       name_buffer = xrealloc (name_buffer, name_buffer_length + 2);
 292     }
 293   name_buffer[counter] = '\0';
 294
 295   return 1;
 296 }
 297
 298 /* Get the next name from ARGV or the file of names.  Result is in
 299    static storage and can't be relied upon across two calls.
 300
 301    If CHANGE_DIRS is true, treat a filename of the form "-C" as
 302    meaning that the next filename is the name of a directory to change
 303    to.  If filename_terminator is NUL, CHANGE_DIRS is effectively
 304    always false.  */
 305 char *
 306 name_next (int change_dirs)
 307 {
 308   const char *source;
 309   char *cursor;
 310   int chdir_flag = 0;
 311
 312   if (filename_terminator == '\0')
 313     change_dirs = 0;
 314
 315   while (1)
 316     {
 317       /* Get a name, either from file or from saved arguments.  */
 318
 319       if (name_index == names)
 320         {
 321           if (! name_file)
 322             break;
 323           if (! read_name_from_file ())
 324             break;
 325         }
 326       else
 327         {
 328           size_t source_len;
 329           source = name_array[name_index++];
 330           source_len = strlen (source);
 331           if (name_buffer_length < source_len)
 332             {
 333               do
 334                 {
 335                   name_buffer_length *= 2;
 336                   if (! name_buffer_length)
 337                     xalloc_die ();
 338                 }
 339               while (name_buffer_length < source_len);
 340
 341               free (name_buffer);
 342               name_buffer = xmalloc (name_buffer_length + 2);
 343             }
 344           strcpy (name_buffer, source);
 345         }
 346
 347       /* Zap trailing slashes.  */
 348
 349       cursor = name_buffer + strlen (name_buffer) - 1;
 350       while (cursor > name_buffer && ISSLASH (*cursor))
 351         *cursor-- = '\0';
 352
 353       if (chdir_flag)
 354         {
 355           if (chdir (name_buffer) < 0)
 356             chdir_fatal (name_buffer);
 357           chdir_flag = 0;
 358         }
 359       else if (change_dirs && strcmp (name_buffer, "-C") == 0)
 360         chdir_flag = 1;
 361       else
 362         {
 363           unquote_string (name_buffer);
 364           return name_buffer;
 365         }
 366     }
 367
 368   /* No more names in file.  */
 369
 370   if (name_file && chdir_flag)
 371     FATAL_ERROR ((0, 0, _("Missing file name after -C")));
 372
 373   return 0;
 374 }
 375
 376 /* Close the name file, if any.  */
 377 void
 378 name_close (void)
 379 {
 380   if (name_file && name_file != stdin)
 381     if (fclose (name_file) != 0)
 382       close_error (name_buffer);
 383 }
 384
 385 /* Gather names in a list for scanning.  Could hash them later if we
 386    really care.
 387
 388    If the names are already sorted to match the archive, we just read
 389    them one by one.  name_gather reads the first one, and it is called
 390    by name_match as appropriate to read the next ones.  At EOF, the
 391    last name read is just left in the buffer.  This option lets users
 392    of small machines extract an arbitrary number of files by doing
 393    "tar t" and editing down the list of files.  */
 394
 395 void
 396 name_gather (void)
 397 {
 398   /* Buffer able to hold a single name.  */
 399   static struct name *buffer;
 400   static size_t allocated_size;
 401
 402   char const *name;
 403
 404   if (same_order_option)
 405     {
 406       static int change_dir;
 407
 408       if (allocated_size == 0)
 409         {
 410           allocated_size = offsetof (struct name, name) + NAME_FIELD_SIZE + 1;
 411           buffer = xmalloc (allocated_size);
 412           /* FIXME: This memset is overkill, and ugly...  */
 413           memset (buffer, 0, allocated_size);
 414         }
 415
 416       while ((name = name_next (0)) && strcmp (name, "-C") == 0)
 417         {
 418           char const *dir = name_next (0);
 419           if (! dir)
 420             FATAL_ERROR ((0, 0, _("Missing file name after -C")));
 421           change_dir = chdir_arg (xstrdup (dir));
 422         }
 423
 424       if (name)
 425         {
 426           size_t needed_size;
 427           buffer->length = strlen (name);
 428           needed_size = offsetof (struct name, name) + buffer->length + 1;
 429           if (allocated_size < needed_size)
 430             {
 431               do
 432                 {
 433                   allocated_size *= 2;
 434                   if (! allocated_size)
 435                     xalloc_die ();
 436                 }
 437               while (allocated_size < needed_size);
 438
 439               buffer = xrealloc (buffer, allocated_size);
 440             }
 441           buffer->change_dir = change_dir;
 442           strcpy (buffer->name, name);
 443           buffer->next = 0;
 444           buffer->found = 0;
 445
 446           namelist = buffer;
 447           nametail = &namelist->next;
 448         }
 449     }
 450   else
 451     {
 452       /* Non sorted names -- read them all in.  */
 453       int change_dir = 0;
 454
 455       for (;;)
 456         {
 457           int change_dir0 = change_dir;
 458           while ((name = name_next (0)) && strcmp (name, "-C") == 0)
 459             {
 460               char const *dir = name_next (0);
 461               if (! dir)
 462                 FATAL_ERROR ((0, 0, _("Missing file name after -C")));
 463               change_dir = chdir_arg (xstrdup (dir));
 464             }
 465           if (name)
 466             addname (name, change_dir);
 467           else
 468             {
 469               if (change_dir != change_dir0)
 470                 addname (0, change_dir);
 471               break;
 472             }
 473         }
 474     }
 475 }
 476
 477 /*  Add a name to the namelist.  */
 478 struct name *
 479 addname (char const *string, int change_dir)
 480 {
 481   size_t length = string ? strlen (string) : 0;
 482   struct name *name = xmalloc (offsetof (struct name, name) + length + 1);
 483
 484   if (string)
 485     {
 486       name->fake = 0;
 487       strcpy (name->name, string);
 488     }
 489   else
 490     {
 491       name->fake = 1;
 492
 493       /* FIXME: This initialization (and the byte of memory that it
 494          initializes) is probably not needed, but we are currently in
 495          bug-fix mode so we'll leave it in for now.  */
 496       name->name[0] = 0;
 497     }
 498
 499   name->next = 0;
 500   name->length = length;
 501   name->found = 0;
 502   name->regexp = 0;             /* assume not a regular expression */
 503   name->firstch = 1;            /* assume first char is literal */
 504   name->change_dir = change_dir;
 505   name->dir_contents = 0;
 506
 507   if (string && is_pattern (string))
 508     {
 509       name->regexp = 1;
 510       if (string[0] == '*' || string[0] == '[' || string[0] == '?')
 511         name->firstch = 0;
 512     }
 513
 514   *nametail = name;
 515   nametail = &name->next;
 516   return name;
 517 }
 518
 519 /* Find a match for PATH (whose string length is LENGTH) in the name
 520    list.  */
 521 static struct name *
 522 namelist_match (char const *path, size_t length)
 523 {
 524   struct name *p;
 525
 526   for (p = namelist; p; p = p->next)
 527     {
 528       /* If first chars don't match, quick skip.  */
 529
 530       if (p->firstch && p->name[0] != path[0])
 531         continue;
 532
 533       if (p->regexp
 534           ? fnmatch (p->name, path, recursion_option) == 0
 535           : (p->length <= length
 536              && (path[p->length] == '\0' || ISSLASH (path[p->length]))
 537              && memcmp (path, p->name, p->length) == 0))
 538         return p;
 539     }
 540
 541   return 0;
 542 }
 543
 544 /* Return true if and only if name PATH (from an archive) matches any
 545    name from the namelist.  */
 546 int
 547 name_match (const char *path)
 548 {
 549   size_t length = strlen (path);
 550
 551   while (1)
 552     {
 553       struct name *cursor = namelist;
 554       struct name *tmpnlp;
 555
 556       if (!cursor)
 557         return ! files_from_option;
 558
 559       if (cursor->fake)
 560         {
 561           chdir_do (cursor->change_dir);
 562           namelist = 0;
 563           nametail = &namelist;
 564           return ! files_from_option;
 565         }
 566
 567       cursor = namelist_match (path, length);
 568       if (cursor)
 569         {
 570           cursor->found = 1; /* remember it matched */
 571           if (starting_file_option)
 572             {
 573               free (namelist);
 574               namelist = 0;
 575               nametail = &namelist;
 576             }
 577           chdir_do (cursor->change_dir);
 578           if (fast_read_option)
 579             {
 580             /* remove the current entry, since we found a match */
 581               if (namelist->next == NULL)
 582                 {
 583                   /* the list contains one element */
 584                   free(namelist);
 585                   namelist = 0;
 586                   nametail = &namelist;
 587                   /* set a boolean to decide wether we started with a */
 588                   /* non-empty  namelist, that was emptied */
 589                   namelist_freed = 1;
 590                 }
 591               else
 592                 {
 593                   if (cursor == namelist)
 594                     {
 595                       /* the first element is the one */
 596                       tmpnlp = namelist->next;
 597                       free(namelist);
 598                       namelist = tmpnlp;
 599                     }
 600                   else
 601                     {
 602                       tmpnlp = namelist;
 603                       while (tmpnlp->next != cursor)
 604                         tmpnlp = tmpnlp->next;
 605                       tmpnlp->next = cursor->next;
 606                       free(cursor);
 607                     }
 608                 }
 609             }
 610
 611           /* We got a match.  */
 612           return 1;
 613         }
 614
 615       /* Filename from archive not found in namelist.  If we have the whole
 616          namelist here, just return 0.  Otherwise, read the next name in and
 617          compare it.  If this was the last name, namelist->found will remain
 618          on.  If not, we loop to compare the newly read name.  */
 619
 620       if (same_order_option && namelist->found)
 621         {
 622           name_gather ();       /* read one more */
 623           if (namelist->found)
 624             return 0;
 625         }
 626       else
 627         return 0;
 628     }
 629 }
 630
 631 /* Print the names of things in the namelist that were not matched.  */
 632 void
 633 names_notfound (void)
 634 {
 635   struct name const *cursor;
 636
 637   for (cursor = namelist; cursor; cursor = cursor->next)
 638     if (!cursor->found && !cursor->fake)
 639       ERROR ((0, 0, _("%s: Not found in archive"),
 640               quotearg_colon (cursor->name)));
 641
 642   /* Don't bother freeing the name list; we're about to exit.  */
 643   namelist = 0;
 644   nametail = &namelist;
 645
 646   if (same_order_option)
 647     {
 648       char *name;
 649
 650       while (name = name_next (1), name)
 651         ERROR ((0, 0, _("%s: Not found in archive"),
 652                 quotearg_colon (name)));
 653     }
 654 }
 655 \f
 656 /* Sorting name lists.  */
 657
 658 /* Sort linked LIST of names, of given LENGTH, using COMPARE to order
 659    names.  Return the sorted list.  Apart from the type `struct name'
 660    and the definition of SUCCESSOR, this is a generic list-sorting
 661    function, but it's too painful to make it both generic and portable
 662    in C.  */
 663
 664 static struct name *
 665 merge_sort (struct name *list, int length,
 666             int (*compare) (struct name const*, struct name const*))
 667 {
 668   struct name *first_list;
 669   struct name *second_list;
 670   int first_length;
 671   int second_length;
 672   struct name *result;
 673   struct name **merge_point;
 674   struct name *cursor;
 675   int counter;
 676
 677 # define SUCCESSOR(name) ((name)->next)
 678
 679   if (length == 1)
 680     return list;
 681
 682   if (length == 2)
 683     {
 684       if ((*compare) (list, SUCCESSOR (list)) > 0)
 685         {
 686           result = SUCCESSOR (list);
 687           SUCCESSOR (result) = list;
 688           SUCCESSOR (list) = 0;
 689           return result;
 690         }
 691       return list;
 692     }
 693
 694   first_list = list;
 695   first_length = (length + 1) / 2;
 696   second_length = length / 2;
 697   for (cursor = list, counter = first_length - 1;
 698        counter;
 699        cursor = SUCCESSOR (cursor), counter--)
 700     continue;
 701   second_list = SUCCESSOR (cursor);
 702   SUCCESSOR (cursor) = 0;
 703
 704   first_list = merge_sort (first_list, first_length, compare);
 705   second_list = merge_sort (second_list, second_length, compare);
 706
 707   merge_point = &result;
 708   while (first_list && second_list)
 709     if ((*compare) (first_list, second_list) < 0)
 710       {
 711         cursor = SUCCESSOR (first_list);
 712         *merge_point = first_list;
 713         merge_point = &SUCCESSOR (first_list);
 714         first_list = cursor;
 715       }
 716     else
 717       {
 718         cursor = SUCCESSOR (second_list);
 719         *merge_point = second_list;
 720         merge_point = &SUCCESSOR (second_list);
 721         second_list = cursor;
 722       }
 723   if (first_list)
 724     *merge_point = first_list;
 725   else
 726     *merge_point = second_list;
 727
 728   return result;
 729
 730 #undef SUCCESSOR
 731 }
 732
 733 /* A comparison function for sorting names.  Put found names last;
 734    break ties by string comparison.  */
 735
 736 static int
 737 compare_names (struct name const *n1, struct name const *n2)
 738 {
 739   int found_diff = n2->found - n1->found;
 740   return found_diff ? found_diff : strcmp (n1->name, n2->name);
 741 }
 742 \f
 743 /* Add all the dirs under NAME, which names a directory, to the namelist.
 744    If any of the files is a directory, recurse on the subdirectory.
 745    DEVICE is the device not to leave, if the -l option is specified.  */
 746
 747 static void
 748 add_hierarchy_to_namelist (struct name *name, dev_t device)
 749 {
 750   char *path = name->name;
 751   char *buffer = get_directory_contents (path, device);
 752
 753   if (! buffer)
 754     name->dir_contents = "\0\0\0\0";
 755   else
 756     {
 757       size_t name_length = name->length;
 758       size_t allocated_length = (name_length >= NAME_FIELD_SIZE
 759                                  ? name_length + NAME_FIELD_SIZE
 760                                  : NAME_FIELD_SIZE);
 761       char *name_buffer = xmalloc (allocated_length + 1);
 762                                 /* FIXME: + 2 above?  */
 763       char *string;
 764       size_t string_length;
 765       int change_dir = name->change_dir;
 766
 767       name->dir_contents = buffer;
 768       strcpy (name_buffer, path);
 769       if (! ISSLASH (name_buffer[name_length - 1]))
 770         {
 771           name_buffer[name_length++] = '/';
 772           name_buffer[name_length] = '\0';
 773         }
 774
 775       for (string = buffer; *string; string += string_length + 1)
 776         {
 777           string_length = strlen (string);
 778           if (*string == 'D')
 779             {
 780               if (allocated_length <= name_length + string_length)
 781                 {
 782                   do
 783                     {
 784                       allocated_length *= 2;
 785                       if (! allocated_length)
 786                         xalloc_die ();
 787                     }
 788                   while (allocated_length <= name_length + string_length);
 789
 790                   name_buffer = xrealloc (name_buffer, allocated_length + 1);
 791                 }
 792               strcpy (name_buffer + name_length, string + 1);
 793               add_hierarchy_to_namelist (addname (name_buffer, change_dir),
 794                                          device);
 795             }
 796         }
 797
 798       free (name_buffer);
 799     }
 800 }
 801 \f
 802 /* Collect all the names from argv[] (or whatever), expand them into a
 803    directory tree, and sort them.  This gets only subdirectories, not
 804    all files.  */
 805
 806 void
 807 collect_and_sort_names (void)
 808 {
 809   struct name *name;
 810   struct name *next_name;
 811   int num_names;
 812   struct stat statbuf;
 813
 814   name_gather ();
 815
 816   if (listed_incremental_option)
 817     read_directory_file ();
 818
 819   if (!namelist)
 820     addname (".", 0);
 821
 822   for (name = namelist; name; name = next_name)
 823     {
 824       next_name = name->next;
 825       if (name->found || name->dir_contents)
 826         continue;
 827       if (name->regexp)         /* FIXME: just skip regexps for now */
 828         continue;
 829       chdir_do (name->change_dir);
 830       if (name->fake)
 831         continue;
 832
 833       if (deref_stat (dereference_option, name->name, &statbuf) != 0)
 834         {
 835           if (ignore_failed_read_option)
 836             stat_warn (name->name);
 837           else
 838             stat_error (name->name);
 839           continue;
 840         }
 841       if (S_ISDIR (statbuf.st_mode))
 842         {
 843           name->found = 1;
 844           add_hierarchy_to_namelist (name, statbuf.st_dev);
 845         }
 846     }
 847
 848   num_names = 0;
 849   for (name = namelist; name; name = name->next)
 850     num_names++;
 851   namelist = merge_sort (namelist, num_names, compare_names);
 852
 853   for (name = namelist; name; name = name->next)
 854     name->found = 0;
 855 }
 856
 857 /* This is like name_match, except that it returns a pointer to the
 858    name it matched, and doesn't set FOUND in structure.  The caller
 859    will have to do that if it wants to.  Oh, and if the namelist is
 860    empty, it returns null, unlike name_match, which returns TRUE.  */
 861 struct name *
 862 name_scan (const char *path)
 863 {
 864   size_t length = strlen (path);
 865
 866   while (1)
 867     {
 868       struct name *cursor = namelist_match (path, length);
 869       if (cursor)
 870         return cursor;
 871
 872       /* Filename from archive not found in namelist.  If we have the whole
 873          namelist here, just return 0.  Otherwise, read the next name in and
 874          compare it.  If this was the last name, namelist->found will remain
 875          on.  If not, we loop to compare the newly read name.  */
 876
 877       if (same_order_option && namelist && namelist->found)
 878         {
 879           name_gather ();       /* read one more */
 880           if (namelist->found)
 881             return 0;
 882         }
 883       else
 884         return 0;
 885     }
 886 }
 887
 888 /* This returns a name from the namelist which doesn't have ->found
 889    set.  It sets ->found before returning, so successive calls will
 890    find and return all the non-found names in the namelist.  */
 891 struct name *gnu_list_name;
 892
 893 char *
 894 name_from_list (void)
 895 {
 896   if (!gnu_list_name)
 897     gnu_list_name = namelist;
 898   while (gnu_list_name && (gnu_list_name->found | gnu_list_name->fake))
 899     gnu_list_name = gnu_list_name->next;
 900   if (gnu_list_name)
 901     {
 902       gnu_list_name->found = 1;
 903       chdir_do (gnu_list_name->change_dir);
 904       return gnu_list_name->name;
 905     }
 906   return 0;
 907 }
 908
 909 void
 910 blank_name_list (void)
 911 {
 912   struct name *name;
 913
 914   gnu_list_name = 0;
 915   for (name = namelist; name; name = name->next)
 916     name->found = 0;
 917 }
 918
 919 /* Yield a newly allocated file name consisting of PATH concatenated to
 920    NAME, with an intervening slash if PATH does not already end in one.  */
 921 char *
 922 new_name (const char *path, const char *name)
 923 {
 924   size_t pathlen = strlen (path);
 925   size_t namesize = strlen (name) + 1;
 926   int slash = pathlen && ! ISSLASH (path[pathlen - 1]);
 927   char *buffer = xmalloc (pathlen + slash + namesize);
 928   memcpy (buffer, path, pathlen);
 929   buffer[pathlen] = '/';
 930   memcpy (buffer + pathlen + slash, name, namesize);
 931   return buffer;
 932 }
 933
 934 /* Return nonzero if file NAME is excluded.  Exclude a name if its
 935    prefix matches a pattern that contains slashes, or if one of its
 936    components matches a pattern that contains no slashes.  */
 937 bool
 938 excluded_name (char const *name)
 939 {
 940   return excluded_filename (excluded, name + FILESYSTEM_PREFIX_LEN (name));
 941 }
 942 \f
 943 /* Names to avoid dumping.  */
 944 static Hash_table *avoided_name_table;
 945
 946 /* Calculate the hash of an avoided name.  */
 947 static unsigned
 948 hash_avoided_name (void const *name, unsigned n_buckets)
 949 {
 950   return hash_string (name, n_buckets);
 951 }
 952
 953 /* Compare two avoided names for equality.  */
 954 static bool
 955 compare_avoided_names (void const *name1, void const *name2)
 956 {
 957   return strcmp (name1, name2) == 0;
 958 }
 959
 960 /* Remember to not archive NAME.  */
 961 void
 962 add_avoided_name (char const *name)
 963 {
 964   if (! ((avoided_name_table
 965           || (avoided_name_table = hash_initialize (0, 0, hash_avoided_name,
 966                                                     compare_avoided_names, 0)))
 967          && hash_insert (avoided_name_table, xstrdup (name))))
 968     xalloc_die ();
 969 }
 970
 971 /* Should NAME be avoided when archiving?  */
 972 int
 973 is_avoided_name (char const *name)
 974 {
 975   return avoided_name_table && hash_lookup (avoided_name_table, name);
 976 }