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