home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / id-utils-3.2-src.tgz / tar.out / fsf / id-utils / libidu / walker.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  31KB  |  1,131 lines
  1. /* walker.c -- nifty file-tree walker
  2.    Copyright (C) 1986, 1995, 1996 Free Software Foundation, Inc.
  3.    Written by Greg McGary <gkm@gnu.ai.mit.edu>
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 2, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18. */
  19.  
  20. #include <config.h>
  21. #include "xsysstat.h"
  22. #include <stdio.h>
  23. #include "xstdlib.h"
  24. #include "xstddef.h"
  25. #include "xunistd.h"
  26. #include "xstring.h"
  27. #include "xfnmatch.h"
  28. #include "xdirent.h"
  29. #include "xnls.h"
  30. #include "idfile.h"
  31. #include "error.h"
  32. #include "xmalloc.h"
  33. #include "dynvec.h"
  34. #include "scanners.h"
  35. #include "pathmax.h"
  36. #include "xalloca.h"
  37.  
  38. int walk_dir __P((struct file_link *dir_link));
  39. struct member_file *get_member_file __P((struct file_link *flink));
  40. struct lang_args *get_lang_args __P((struct file_link const *flink));
  41. int walk_sub_dirs __P((struct dynvec *sub_dirs_vec));
  42. void reparent_children __P((struct file_link *dlink, struct file_link *slink));
  43. int classify_link __P((struct file_link *flink, struct stat *stp));
  44. struct file_link *get_link_from_dirent __P((struct dirent *dirent, struct file_link *parent));
  45. struct file_link *make_link_from_dirent __P((struct dirent *dirent, struct file_link *parent));
  46. struct file_link *get_link_from_string __P((char const *name, struct file_link *parent));
  47. struct file_link *make_link_from_string __P((char const *name, struct file_link *parent));
  48. int lang_wanted __P((char const *lang_name));
  49. char **append_strings_to_vector __P((char **vector_0, char *string, char *delimiter_class));
  50. int vector_length __P((char **vector));
  51. int string_in_vector __P((char const *string, char **vector));
  52. static int same_as_dot __P((char const *cwd));
  53. struct file_link const **fill_link_vector __P((struct file_link const **vec_buf, struct file_link const *flink));
  54. struct file_link const **fill_link_vector_1 __P((struct file_link const **vec_buf, struct file_link const *flink));
  55. char *fill_dot_dots __P((char *buf, int levels));
  56. static char *absolute_file_name_1 __P((char *buffer, struct file_link const *flink));
  57. unsigned long member_file_hash_1 __P((void const *key));
  58. unsigned long member_file_hash_2 __P((void const *key));
  59. int member_file_hash_compare __P((void const *x, void const *y));
  60. unsigned long file_link_hash_1 __P((void const *key));
  61. unsigned long file_link_hash_2 __P((void const *key));
  62. int file_link_hash_compare __P((void const *x, void const *y));
  63. unsigned long dev_ino_hash_1 __P((void const *key));
  64. unsigned long dev_ino_hash_2 __P((void const *key));
  65. int dev_ino_hash_compare __P((void const *x, void const *y));
  66. int symlink_ancestry __P((struct file_link *flink));
  67.  
  68. #if HAVE_LINK
  69. struct file_link *find_alias_link __P((struct file_link *flink, struct stat *stp));
  70. struct member_file *maybe_get_member_file __P((struct file_link *flink, struct stat *stp));
  71. #endif
  72.  
  73. #define IS_DOT(s) ((s)[0] == '.' && (s)[1] == '\0')
  74. #define IS_DOT_DOT(s) ((s)[0] == '.' && (s)[1] == '.' && (s)[2] == '\0')
  75. #define IS_DOT_or_DOT_DOT(s) \
  76.     (((s)[0] == '.') && (((s)[1] == '\0') || ((s)[1] == '.' && (s)[2] == '\0')))
  77.  
  78. static struct file_link *current_dir_link = 0;
  79.  
  80. static char white_space[] = " \t\r\n\v\f";
  81.  
  82. char* xgetcwd __P((void));
  83.  
  84.  
  85. /****************************************************************************/
  86. /* Walk the file-system tree rooted at `dir_link', looking for files
  87.    that are eligible for scanning.  */
  88.  
  89. int
  90. walk_dir (struct file_link *dir_link)
  91. {
  92.   int scannable_files;
  93.   struct dynvec *sub_dirs_vec;
  94.   DIR *dirp;
  95.  
  96.   if (!chdir_to_link (dir_link))
  97.     return 0;
  98.   dirp = opendir (".");
  99.   if (dirp == 0)
  100.     {
  101.       char *file_name = ALLOCA (char, PATH_MAX);
  102.       absolute_file_name (file_name, dir_link);
  103.       error (0, errno, _("can't read directory `%s' (`.' from `%s')"), file_name, xgetcwd ());
  104.       return 0;
  105.     }
  106.   sub_dirs_vec = make_dynvec (32);
  107.   scannable_files = 0;
  108.   for (;;)
  109.     {
  110.       struct file_link *flink;
  111.       struct dirent *dirent = readdir (dirp);
  112.  
  113.       if (dirent == 0)
  114.     break;
  115.       if (IS_DOT_or_DOT_DOT (dirent->d_name))
  116.     continue;
  117.  
  118.       flink = get_link_from_dirent (dirent, dir_link);
  119.       if (!(flink->fl_flags & FL_PRUNE))
  120.     walk_flink (flink, sub_dirs_vec);
  121.     }
  122.   closedir (dirp);
  123.  
  124.   scannable_files += walk_sub_dirs (sub_dirs_vec);
  125.   dynvec_free (sub_dirs_vec);
  126.   return scannable_files;
  127. }
  128.  
  129. /* Walk the directories found by walk_dir, calling walk_dir
  130.    recursively for each directory. */
  131.  
  132. int
  133. walk_sub_dirs (struct dynvec *sub_dirs_vec)
  134. {
  135.   struct file_link **sub_dirs;
  136.   struct file_link **sub_dirs_end;
  137.   int total_scannable_files = 0;
  138.  
  139.   dynvec_freeze (sub_dirs_vec);
  140.   sub_dirs_end = (struct file_link **)
  141.     &sub_dirs_vec->dv_vec[sub_dirs_vec->dv_fill];
  142.   sub_dirs = (struct file_link **) sub_dirs_vec->dv_vec;
  143.   for ( ; sub_dirs < sub_dirs_end; sub_dirs++)
  144.     {
  145.       struct file_link *sub_dir_link = *sub_dirs;
  146.       int scannable_files = walk_dir (sub_dir_link);
  147.       if (scannable_files)
  148.     total_scannable_files += scannable_files;
  149.     }
  150.   return total_scannable_files;
  151. }
  152.  
  153. void
  154. walk_flink (struct file_link *flink, struct dynvec *sub_dirs_vec)
  155. {
  156.   struct stat st;
  157.   unsigned int old_flags;
  158.   unsigned int new_flags;
  159.  
  160.   new_flags = classify_link (flink, &st);
  161.   if (new_flags == 0)
  162.     return;
  163.  
  164.   old_flags = flink->fl_flags;
  165.   if ((old_flags & FL_TYPE_MASK)
  166.       && (old_flags & FL_TYPE_MASK) != (new_flags & FL_TYPE_MASK))
  167.     {
  168.       char *file_name = ALLOCA (char, PATH_MAX);
  169.       absolute_file_name (file_name, flink);
  170.       error (0, 0, _("notice: `%s' was a %s, but is now a %s!"), file_name,
  171.          (FL_IS_FILE (old_flags) ? _("file") : _("directory")),
  172.          (FL_IS_FILE (new_flags) ? _("file") : _("directory")));
  173.     }
  174.   
  175.  
  176.   flink->fl_flags = (old_flags & ~(FL_TYPE_MASK|FL_SYM_LINK)) | new_flags;
  177.   if (FL_IS_DIR (new_flags))
  178.     {
  179.       struct file_link *alias_link = find_alias_link (flink, &st);
  180.  
  181.       if (alias_link)
  182.     {
  183.       if (!(new_flags & FL_SYM_LINK))
  184.         reparent_children (flink, alias_link);
  185.     }
  186.       else if (sub_dirs_vec == 0)
  187.     walk_dir (flink);
  188.       else
  189.     dynvec_append (sub_dirs_vec, flink);
  190.     }
  191.   else
  192.     {
  193.       struct member_file *member;
  194. #if HAVE_LINK
  195.       member = maybe_get_member_file (flink, &st);
  196. #else
  197.       member = get_member_file (flink);
  198. #endif
  199.       if (member == 0)
  200.     return;
  201.     }
  202. }
  203.  
  204. /* Take child file_link nodes from a symlinked directory and give them
  205.    to a hard linked directory.  This is something of a pain since a
  206.    file_link's parent node is part of its hash-table key.  We must
  207.    search the entire hash-table for the children.  With each child, we
  208.    must delete it, reset its parent link, then reinsert.  */
  209.  
  210. void
  211. reparent_children (struct file_link *dlink, struct file_link *slink)
  212. {
  213.   void **slot = idh.idh_file_link_table.ht_vec;
  214.   void **end = &idh.idh_file_link_table.ht_vec[idh.idh_file_link_table.ht_size];
  215.  
  216.   for ( ; slot < end; slot++)
  217.     {
  218.       if (!HASH_VACANT (*slot))
  219.     {
  220.       struct file_link *child = (struct file_link *) *slot;
  221.       if (child->fl_parent == slink)
  222.         {
  223.           void **new_slot;
  224.           *slot = hash_deleted_item;
  225.           child->fl_parent = dlink;
  226.           new_slot = hash_find_slot (&idh.idh_file_link_table, child);
  227.           *new_slot = child;
  228.         }
  229.     }
  230.     }
  231. }
  232.  
  233.  
  234. /****************************************************************************/
  235. /* Separate the wheat from the chaff.  Mark those file_links that are
  236.    components in member files.  */
  237.  
  238. void
  239. mark_member_file_links (struct idhead *idhp)
  240. {
  241.   struct member_file **members_0
  242.     = (struct member_file **) hash_dump (&idhp->idh_member_file_table,
  243.                      0, member_file_qsort_compare);
  244.   struct member_file **end = &members_0[idhp->idh_member_file_table.ht_fill];
  245.   struct member_file **members;
  246.   int new_index = 0;
  247.  
  248.   for (members = members_0; members < end; members++)
  249.     {
  250.       struct member_file *member = *members;
  251.       struct file_link *flink;
  252.       member->mf_index = new_index++;
  253.       for (flink = member->mf_link;
  254.        !(flink->fl_flags & FL_USED); flink = flink->fl_parent)
  255.     flink->fl_flags |= FL_USED;
  256.     }
  257.   free (members_0);
  258. }
  259.  
  260.  
  261. #if HAVE_LINK
  262.  
  263. /****************************************************************************/
  264. /* Return a `member_file' for this `flink' *if* the filename matches
  265.    some scan pattern, and no alias for the file takes precedence ([1]
  266.    hard-links dominate symbolic-links; [2] for two hard-links: first
  267.    come, first served).  */
  268.  
  269. struct member_file *
  270. maybe_get_member_file (struct file_link *flink, struct stat *stp)
  271. {
  272.   struct file_link *alias_link;
  273.   struct member_file *member;
  274.   struct member_file *alias_member = 0;
  275.  
  276.   member = get_member_file (flink);
  277.   alias_link = find_alias_link (flink, stp);
  278.   if (alias_link)
  279.     alias_member = find_member_file (alias_link);
  280.  
  281.   if (member && alias_member)
  282.     {
  283.       int ancestry = symlink_ancestry (flink);
  284.       int alias_ancestry = symlink_ancestry (alias_link);
  285.       if (member->mf_lang_args != alias_member->mf_lang_args)
  286.     {
  287.       char *file_name = ALLOCA (char, PATH_MAX);
  288.       char *alias_file_name = ALLOCA (char, PATH_MAX);
  289.       absolute_file_name (file_name, flink);
  290.       absolute_file_name (alias_file_name, alias_link);
  291.       error (0, 0, _("warning: `%s' and `%s' are the same file, but yield different scans!"),
  292.          file_name, alias_file_name);
  293.     }
  294.       else if (alias_ancestry > ancestry)
  295.     {
  296.       hash_delete (&idh.idh_member_file_table, member);
  297.       member->mf_link->fl_flags &= ~FL_MEMBER;
  298.       return 0;
  299.     }
  300.       else
  301.     {
  302.       hash_delete (&idh.idh_member_file_table, alias_member);
  303.       alias_member->mf_link->fl_flags &= ~FL_MEMBER;
  304.     }
  305.     }
  306.   return member;
  307. }
  308.  
  309. /* Return a previously registered alias for `flink', if any.  */
  310.  
  311. struct file_link *
  312. find_alias_link (struct file_link *flink, struct stat *stp)
  313. {
  314.   struct dev_ino *dev_ino;
  315.   struct dev_ino **slot;
  316.  
  317.   dev_ino = (struct dev_ino *) obstack_alloc (&idh.idh_dev_ino_obstack, sizeof (struct dev_ino));
  318.   dev_ino->di_dev = stp->st_dev;
  319.   dev_ino->di_ino = stp->st_ino;
  320.   slot = (struct dev_ino **) hash_find_slot (&idh.idh_dev_ino_table, dev_ino);
  321.   if (HASH_VACANT (*slot))
  322.     {
  323.       dev_ino->di_link = flink;
  324.       hash_insert_at (&idh.idh_dev_ino_table, dev_ino, slot);
  325.       return 0;
  326.     }
  327.   else
  328.     {
  329.       obstack_free (&idh.idh_dev_ino_obstack, dev_ino);
  330.       return (*slot)->di_link;
  331.     }
  332. }
  333.  
  334. /* Return the distance from `flink' to a symbolic-link ancestor
  335.    directory.  PATH_MAX is considered an infinite distance (e.g.,
  336.    there are no symlinks between `flink' and the root).  */
  337.  
  338. int
  339. symlink_ancestry (struct file_link *flink)
  340. {
  341.   int ancestry = 0;
  342.   while (!IS_ROOT_FILE_LINK (flink))
  343.     {
  344.       if (flink->fl_flags & FL_SYM_LINK)
  345.     return ancestry;
  346.       ancestry++;
  347.       flink = flink->fl_parent;
  348.     }
  349.   return PATH_MAX;
  350. }
  351.  
  352. #endif /* HAVE_LINK */
  353.  
  354. struct member_file *
  355. get_member_file (struct file_link *flink)
  356. {
  357.   struct member_file *member;
  358.   struct member_file **slot;
  359.   struct lang_args const *args;
  360.  
  361.   args = get_lang_args (flink);
  362.   if (args == 0)
  363.     return 0;
  364.   if (!lang_wanted (args->la_language->lg_name))
  365.     return 0;
  366.  
  367.   member = (struct member_file *) obstack_alloc (&idh.idh_member_file_obstack,
  368.                          sizeof (struct member_file));
  369.   member->mf_link = flink;
  370.   slot = (struct member_file **) hash_find_slot (&idh.idh_member_file_table, member);
  371.   if (HASH_VACANT (*slot))
  372.     {
  373.       member->mf_index = -1;
  374.       hash_insert_at (&idh.idh_member_file_table, member, slot);
  375.       flink->fl_flags |= FL_MEMBER;
  376.     }
  377.   else
  378.     {
  379.       obstack_free (&idh.idh_member_file_obstack, member);
  380. #if 0
  381.       if (member->mf_lang_args != args)
  382.     {
  383.       char *file_name = ALLOCA (char, PATH_MAX);
  384.       absolute_file_name (file_name, flink);
  385.       error (0, 0, _("notice: scan parameters changed for `%s'"), file_name);
  386.       member->mf_old_index = -1;
  387.     }
  388. #endif
  389.       member = *slot;
  390.     }
  391.   member->mf_lang_args = args;
  392.   return *slot;
  393. }
  394.  
  395. struct member_file *
  396. find_member_file (struct file_link const *flink)
  397. {
  398.   struct member_file key;
  399.   struct member_file **slot;
  400.  
  401.   key.mf_link = (struct file_link *) flink;
  402.   slot = (struct member_file **) hash_find_slot (&idh.idh_member_file_table, &key);
  403.   if (HASH_VACANT (*slot))
  404.     return 0;
  405.   return *slot;
  406. }
  407.  
  408. /* March down the list of lang_args, and return the first one whose
  409.    pattern matches FLINK.  Return the matching lang_args, if a
  410.    scanner exists for that language, otherwise return 0.  */
  411.  
  412. struct lang_args *
  413. get_lang_args (struct file_link const *flink)
  414. {
  415.   struct lang_args *args = lang_args_list;
  416.  
  417.   while (args)
  418.     {
  419.       if (strchr (args->la_pattern, SLASH_CHAR))
  420.     {
  421.       char *file_name = ALLOCA (char, PATH_MAX);
  422.       absolute_file_name (file_name, flink);
  423.       if (fnmatch (args->la_pattern, file_name, MAYBE_FNM_CASEFOLD | FNM_FILE_NAME) == 0)
  424.         return (args->la_language ? args : 0);
  425.     }
  426.       else
  427.     {
  428.       if (fnmatch (args->la_pattern, flink->fl_name, MAYBE_FNM_CASEFOLD) == 0)
  429.         return (args->la_language ? args : 0);
  430.     }
  431.       args = args->la_next;
  432.     }
  433.   return ((lang_args_default && lang_args_default->la_language)
  434.       ? lang_args_default : 0);
  435. }
  436.  
  437.  
  438. /****************************************************************************/
  439.  
  440. static char **langs_included;
  441. static char **langs_excluded;
  442.  
  443. int
  444. lang_wanted (char const *lang_name)
  445. {
  446.   if (langs_excluded)
  447.     return !string_in_vector (lang_name, langs_excluded);
  448.   else if (langs_included)
  449.     return string_in_vector (lang_name, langs_included);
  450.   else
  451.     return 1;
  452. }
  453.  
  454. void
  455. include_languages (char *lang_names)
  456. {
  457.   if (langs_excluded)
  458.     error (1, 0, "can't mix --include and --exclude options");
  459.   langs_included = append_strings_to_vector (langs_included, lang_names, white_space);
  460. }
  461.  
  462. void
  463. exclude_languages (char *lang_names)
  464. {
  465.   if (langs_excluded)
  466.     error (1, 0, "can't mix --include and --exclude options");
  467.   langs_excluded = append_strings_to_vector (langs_excluded, lang_names, white_space);
  468. }
  469.  
  470. char **
  471. append_strings_to_vector (char **vector_0, char *string, char *delimiter_class)
  472. {
  473.   char **vector;
  474.   if (vector_0)
  475.     {
  476.       int length = vector_length (vector_0);
  477.       vector_0 = REALLOC (vector_0, char *,
  478.               length + 2 + strlen (string) / 2);
  479.       vector = &vector_0[length];
  480.     }
  481.   else
  482.     vector = vector_0 = MALLOC (char *, 2 + strlen (string) / 2);
  483.   
  484.   *vector = strtok (string, delimiter_class);
  485.   while (*vector)
  486.     *++vector = strtok (0, delimiter_class);
  487.   return REALLOC (vector_0, char *, ++vector - vector_0);
  488. }
  489.  
  490. int
  491. vector_length (char **vector)
  492. {
  493.   int length = 0;
  494.   while (*vector++)
  495.     length++;
  496.   return length;
  497. }
  498.  
  499. int
  500. string_in_vector (char const *string, char **vector)
  501. {
  502.   while (*vector)
  503.     if (strequ (string, *vector++))
  504.       return 1;
  505.   return 0;
  506. }
  507.  
  508.  
  509. /****************************************************************************/
  510. /* Convert a file name string to an absolute chain of `file_link's.  */
  511.  
  512. struct file_link *
  513. parse_file_name (char *file_name, struct file_link *relative_dir_link)
  514. {
  515.   struct file_link *flink;
  516.   char **links_0;
  517.   char **links;
  518.  
  519.   if (IS_ABSOLUTE (file_name))
  520.     {
  521. #if HAVE_LINK
  522.       flink = get_link_from_string (SLASH_STRING, 0);
  523. #else
  524.       flink = 0;
  525. #endif
  526.     }
  527.   else if (relative_dir_link)
  528.     flink = relative_dir_link;
  529.   else if (current_dir_link)
  530.     flink = current_dir_link;
  531.   else
  532.     flink = get_current_dir_link ();
  533.  
  534.   links = links_0 = vectorize_string (file_name, SLASH_STRING);
  535.   while (*links)
  536.     {
  537.       char const* link_name = *links++;
  538.       if (*link_name == '\0' || IS_DOT (link_name))
  539.     ;
  540.       else if (IS_DOT_DOT (link_name))
  541.     flink = flink->fl_parent;
  542.       else
  543.     {
  544.       struct stat st;
  545.       flink = get_link_from_string (link_name, flink);
  546.       if (!flink->fl_flags)
  547.         {
  548.           flink->fl_flags = classify_link (flink, &st);
  549.           if (!flink->fl_flags)
  550.         return 0;
  551.         }
  552.     }
  553.     }
  554.   free (links_0);
  555.   return flink;
  556. }
  557.  
  558. /* Return an absolute chain of `file_link's representing the current
  559.    working directory.  */
  560.  
  561. struct file_link *
  562. get_current_dir_link (void)
  563. {
  564.   struct file_link *dir_link;
  565.   char *cwd_0;
  566.   char *cwd;
  567.   char *xcwd = 0;
  568.   char **links_0;
  569.   char **links;
  570.  
  571.   if (current_dir_link)
  572.     return current_dir_link;
  573.  
  574.   cwd_0 = getenv ("PWD");
  575.   if (cwd_0)
  576.     cwd_0 = strdup (cwd_0);
  577.   if (!same_as_dot (cwd_0))
  578.     cwd_0 = xcwd = xgetcwd ();
  579.   if (cwd_0 == 0)
  580.     error (1, errno, _("can't get working directory"));
  581.   cwd = cwd_0;
  582. #if HAVE_LINK
  583.   dir_link = get_link_from_string (SLASH_STRING, 0);
  584.   dir_link->fl_flags = (dir_link->fl_flags & ~FL_TYPE_MASK) | FL_TYPE_DIR;
  585. #else
  586.   dir_link = 0;
  587. #endif
  588.   links = links_0 = vectorize_string (cwd, SLASH_STRING);
  589.   while (*links)
  590.     {
  591.       struct stat st;
  592.       char const* link_name = *links++;
  593.       dir_link = get_link_from_string (link_name, dir_link);
  594.       if (!dir_link->fl_flags)
  595.     dir_link->fl_flags = classify_link (dir_link, &st);
  596.     }
  597.   chdir_to_link (dir_link);
  598.   free (links_0);
  599.   if (xcwd)
  600.     free (xcwd);
  601.   current_dir_link = dir_link;
  602.   return dir_link;
  603. }
  604.  
  605. static int
  606. same_as_dot (char const *cwd)
  607. {
  608.   struct stat cwd_st;
  609.   struct stat dot_st;
  610.  
  611.   if (cwd == 0 || *cwd != '/'
  612.       || stat (cwd, &cwd_st) < 0
  613.       || stat (".", &dot_st) < 0)
  614.     return 0;
  615.   return ((cwd_st.st_ino == dot_st.st_ino) && (cwd_st.st_dev == dot_st.st_dev));
  616. }
  617.  
  618. /* Change the working directory to the directory represented by
  619.    `dir_link'.  Choose the shortest path to the destination based on
  620.    the cached value of the current directory.  */
  621.  
  622. int
  623. chdir_to_link (struct file_link *dir_link)
  624. {
  625.   char *to_dir_name = ALLOCA (char, PATH_MAX);
  626.  
  627.   if (current_dir_link == dir_link)
  628.     return 1;
  629.  
  630.   if (current_dir_link)
  631.     maybe_relative_file_name (to_dir_name, dir_link, current_dir_link);
  632.   else
  633.     absolute_file_name (to_dir_name, dir_link);
  634.   if (chdir (to_dir_name) < 0)
  635.     {
  636.       if (IS_ABSOLUTE (to_dir_name))
  637.     error (0, errno, _("can't chdir to `%s'"), to_dir_name);
  638.       else
  639.     {
  640.       char *from_dir_name = ALLOCA (char, PATH_MAX);
  641.       absolute_file_name (from_dir_name, current_dir_link);
  642.       error (0, errno, _("can't chdir to `%s' from `%s'"), to_dir_name, from_dir_name);
  643.     }
  644.       return 0;
  645.     }
  646.   else
  647.     {
  648.       current_dir_link = dir_link;
  649.       return 1;
  650.     }
  651. }
  652.  
  653. char **
  654. vectorize_string (char *string, char *delimiter_class)
  655. {
  656.   char **vector_0 = MALLOC (char *, 2 + strlen (string) / 2);
  657.   char **vector = vector_0;
  658.   
  659.   *vector = strtok (string, delimiter_class);
  660.   while (*vector)
  661.     *++vector = strtok (0, delimiter_class);
  662.   return REALLOC (vector_0, char *, ++vector - vector_0);
  663. }
  664.  
  665. void
  666. prune_file_names (char *str, struct file_link *from_link)
  667. {
  668.   char **file_names_0 = vectorize_string (str, white_space);
  669.   char **file_names = file_names_0;
  670.  
  671.   while (*file_names)
  672.     {
  673.       struct file_link *flink = parse_file_name (*file_names++, from_link);
  674.       if (flink)
  675.     flink->fl_flags |= FL_PRUNE;
  676.     }
  677.   free (file_names_0);
  678. }
  679.  
  680.  
  681. /****************************************************************************/
  682. /* Gather information about the link at `flink'.  If it's a good
  683.    file or directory, return its mod-time and type.  */
  684.  
  685. int
  686. classify_link (struct file_link *flink, struct stat *stp)
  687. {
  688.   unsigned int flags = 0;
  689.  
  690.   if (!chdir_to_link (flink->fl_parent))
  691.     return 0;
  692.  
  693. #ifdef S_IFLNK
  694.   if (lstat (flink->fl_name, stp) < 0)
  695.     {
  696.       error (0, errno, _("can't lstat `%s' from `%s'"), flink->fl_name, xgetcwd ());
  697.       return 0;
  698.     }
  699.   if (S_ISLNK (stp->st_mode))
  700.     {
  701. #endif
  702.       if (stat (flink->fl_name, stp) < 0)
  703.     {
  704.       error (0, errno, _("can't stat `%s' from `%s'"), flink->fl_name, xgetcwd ());
  705.       return 0;
  706.     }
  707. #ifdef S_IFLNK
  708.       flags |= FL_SYM_LINK;
  709.     }
  710. #endif
  711.   if (S_ISDIR (stp->st_mode))
  712.     flags |= FL_TYPE_DIR;
  713.   else if (S_ISREG (stp->st_mode))
  714.     flags |= FL_TYPE_FILE;
  715.   else
  716.     return 0;
  717.   return flags;
  718. }
  719.  
  720.  
  721. /****************************************************************************/
  722. /* Retrieve an existing flink; or if none exists, create one. */
  723.  
  724. struct file_link *
  725. get_link_from_dirent (struct dirent *dirent, struct file_link *parent)
  726. {
  727.   struct file_link **slot;
  728.   struct file_link *new_link;
  729.  
  730.   new_link = make_link_from_dirent (dirent, parent);
  731.   slot = (struct file_link **) hash_find_slot (&idh.idh_file_link_table, new_link);
  732.   if (HASH_VACANT (*slot))
  733.     hash_insert_at (&idh.idh_file_link_table, new_link, slot);
  734.   else
  735.     obstack_free (&idh.idh_file_link_obstack, new_link);
  736.   return *slot;
  737. }
  738.  
  739. struct file_link *
  740. get_link_from_string (char const *name, struct file_link *parent)
  741. {
  742.   struct file_link **slot;
  743.   struct file_link *new_link;
  744.  
  745.   new_link = make_link_from_string (name, parent);
  746.   slot = (struct file_link **) hash_find_slot (&idh.idh_file_link_table, new_link);
  747.   if (HASH_VACANT (*slot))
  748.     hash_insert_at (&idh.idh_file_link_table, new_link, slot);
  749.   else
  750.     obstack_free (&idh.idh_file_link_obstack, new_link);
  751.   return *slot;
  752. }
  753.  
  754. struct file_link *
  755. make_link_from_dirent (struct dirent* dirent, struct file_link *parent)
  756. {
  757.   struct file_link *flink;
  758.  
  759.   flink = (struct file_link *) obstack_alloc (&idh.idh_file_link_obstack,
  760.                           sizeof (struct file_link) + strlen (dirent->d_name));
  761.   strcpy (flink->fl_name, dirent->d_name);
  762.   flink->fl_parent = parent ? parent : flink;
  763.   flink->fl_flags = 0;
  764.  
  765.   return flink;
  766. }
  767.  
  768. struct file_link *
  769. make_link_from_string (char const* name, struct file_link *parent)
  770. {
  771.   struct file_link *flink;
  772.  
  773.   flink = (struct file_link *) obstack_alloc (&idh.idh_file_link_obstack,
  774.                           sizeof (struct file_link) + strlen (name));
  775.   strcpy (flink->fl_name, name);
  776.   flink->fl_parent = parent ? parent : flink;
  777.   flink->fl_flags = 0;
  778.  
  779.   return flink;
  780. }
  781.  
  782.  
  783. /****************************************************************************/
  784. /* Convert a `file_link' chain to a vector of component `file_link's,
  785.    with the root at [0].  Return a pointer beyond the final component.  */
  786.  
  787. struct file_link const **
  788. fill_link_vector (struct file_link const **vec_buf, struct file_link const *flink)
  789. {
  790.   vec_buf = fill_link_vector_1 (vec_buf, flink);
  791.   *vec_buf = 0;
  792.   return vec_buf;
  793. }
  794.  
  795. struct file_link const **
  796. fill_link_vector_1 (struct file_link const **vec_buf, struct file_link const *flink)
  797. {
  798.   if (!IS_ROOT_FILE_LINK (flink))
  799.     vec_buf = fill_link_vector_1 (vec_buf, flink->fl_parent);
  800.   *vec_buf++ = flink;
  801.   return vec_buf;
  802. }
  803.  
  804.  
  805. /****************************************************************************/
  806. /* Fill BUF_0 with a path to TO_LINK.  If a relative path from
  807.    FROM_LINK is possible (i.e., no intervening symbolic-links) and
  808.    shorter, return the relative path; otherwise, return an absolute
  809.    path.  */
  810.  
  811. char *
  812. maybe_relative_file_name (char *buf_0, struct file_link const *to_link, struct file_link const *from_link)
  813. {
  814.   struct file_link const **to_link_vec_0 = ALLOCA (struct file_link const *, PATH_MAX/2);
  815.   struct file_link const **from_link_vec_0 = ALLOCA (struct file_link const *, PATH_MAX/2);
  816.   struct file_link const **to_link_vec = to_link_vec_0;
  817.   struct file_link const **from_link_vec = from_link_vec_0;
  818.   struct file_link const **from_link_end;
  819.   struct file_link const **from_links;
  820.   int alloc_me = (buf_0 == 0);
  821.   char *buf;
  822.   int levels;
  823.  
  824.   if (from_link == 0)
  825.     from_link = current_dir_link;
  826.  
  827.   if (alloc_me)
  828.     buf_0 = MALLOC (char, PATH_MAX);
  829.  
  830.   /* Optimize common cases.  */
  831.   if (to_link == from_link)
  832.     strcpy (buf_0, ".");
  833.   else if (to_link->fl_parent == from_link)
  834.     strcpy (buf_0, to_link->fl_name);
  835.   else if (from_link->fl_flags & FL_SYM_LINK)
  836.     absolute_file_name (buf_0, to_link);
  837.   else if (to_link == from_link->fl_parent)
  838.     strcpy (buf_0, "..");
  839.   else if (to_link->fl_parent == from_link->fl_parent)
  840.     {
  841.       strcpy (buf_0, DOT_DOT_SLASH);
  842.       strcpy (&buf_0[3], to_link->fl_name);
  843.     }
  844.   else
  845.     {
  846.       from_link_end = fill_link_vector (from_link_vec, from_link);
  847.       fill_link_vector (to_link_vec, to_link);
  848.       while (*to_link_vec == *from_link_vec)
  849.     {
  850.       if (*to_link_vec == 0)
  851.         {
  852.           strcpy (buf_0, ".");
  853.           goto out;
  854.         }
  855.       to_link_vec++;
  856.       from_link_vec++;
  857.     }
  858.       levels = from_link_end - from_link_vec;
  859.       if (levels >= (from_link_vec - from_link_vec_0))
  860.     {
  861.       absolute_file_name (buf_0, to_link);
  862.       goto out;
  863.     }
  864.       for (from_links = from_link_vec; *from_links; from_links++)
  865.     if ((*from_links)->fl_flags & FL_SYM_LINK)
  866.       {
  867.         absolute_file_name (buf_0, to_link);
  868.         goto out;
  869.       }
  870.       buf = fill_dot_dots (buf_0, levels);
  871.       if (*to_link_vec == 0)
  872.     *--buf = '\0';
  873.       else
  874.     {
  875.       do
  876.         {
  877.           strcpy (buf, (*to_link_vec)->fl_name);
  878.           buf += strlen (buf);
  879.           if ((*to_link_vec)->fl_name[0] != SLASH_CHAR && *++to_link_vec)
  880.         *buf++ = SLASH_CHAR;
  881.         }
  882.       while (*to_link_vec);
  883.     }
  884.     }
  885. out:
  886.   if (alloc_me)
  887.     buf_0 = REALLOC (buf_0, char, 1 + strlen (buf_0));
  888.   return buf_0;
  889. }
  890.  
  891. /* Fill `buf' with sequences of "../" in order to ascend so many
  892.    `levels' in a directory tree.  */
  893.  
  894. char *
  895. fill_dot_dots (char *buf, int levels)
  896. {
  897.   while (levels--)
  898.     {
  899.       strcpy (buf, DOT_DOT_SLASH);
  900.       buf += 3;
  901.     }
  902.   return buf;
  903. }
  904.  
  905.  
  906. /****************************************************************************/
  907. /* Fill `buffer' with the absolute path to `flink'.  */
  908.  
  909. char *
  910. absolute_file_name (char *buf_0, struct file_link const *flink)
  911. {
  912.   char *end;
  913.   int alloc_me = (buf_0 == 0);
  914.  
  915.   if (alloc_me)
  916.     buf_0 = MALLOC (char, PATH_MAX);
  917.   end = absolute_file_name_1 (buf_0, flink);
  918.   /* Clip the trailing slash.  */
  919. #if HAVE_LINK
  920.   if (end > &buf_0[1])
  921.     end--;
  922. #else
  923.   if (end > &buf_0[3])
  924.     end--;
  925. #endif
  926.   *end++ = '\0';
  927.   if (alloc_me)
  928.     buf_0 = REALLOC (buf_0, char, end - buf_0);
  929.   return buf_0;
  930. }
  931.  
  932. static char *
  933. absolute_file_name_1 (char *buf, struct file_link const *flink)
  934. {
  935.   char *end;
  936.   if (IS_ROOT_FILE_LINK (flink))
  937.     end = buf;
  938.   else
  939.     end = absolute_file_name_1 (buf, flink->fl_parent);
  940.   strcpy (end, flink->fl_name);
  941.   if (*end == SLASH_CHAR)
  942.     end++;
  943.   else
  944.     {
  945.       end += strlen (end);
  946.       *end++ = SLASH_CHAR;
  947.     }
  948.   return end;
  949. }
  950.  
  951.  
  952. /****************************************************************************/
  953. /* Hash stuff for `struct member_file'.  */
  954.  
  955. unsigned long
  956. member_file_hash_1 (void const *key)
  957. {
  958.   return_ADDRESS_HASH_1 (((struct member_file const *) key)->mf_link);
  959. }
  960.  
  961. unsigned long
  962. member_file_hash_2 (void const *key)
  963. {
  964.   return_ADDRESS_HASH_2 (((struct member_file const *) key)->mf_link);
  965. }
  966.  
  967. int
  968. member_file_hash_compare (void const *x, void const *y)
  969. {
  970.   return_ADDRESS_COMPARE (((struct member_file const *) x)->mf_link,
  971.               ((struct member_file const *) y)->mf_link);
  972. }
  973.  
  974. /* Collating sequence:
  975.    - language.map index
  976.    - mf_link: breadth-first, alphabetical */
  977.  
  978. int
  979. member_file_qsort_compare (void const *x, void const *y)
  980. {
  981.   struct member_file const *mfx = *(struct member_file const *const *) x;
  982.   struct member_file const *mfy = *(struct member_file const *const *) y;
  983.   int result;
  984.  
  985.   INTEGER_COMPARE (mfx->mf_lang_args->la_index, mfy->mf_lang_args->la_index, result);
  986.   if (result)
  987.     return result;
  988.   else
  989.     {
  990.       struct file_link const *flx = mfx->mf_link;
  991.       struct file_link const *fly = mfy->mf_link;
  992.       if (flx->fl_parent == fly->fl_parent)
  993.     return strcmp (flx->fl_name, fly->fl_name);
  994.       result = (links_depth (flx) - links_depth (fly));
  995.       if (result)
  996.     return result;
  997.       while (flx->fl_parent != fly->fl_parent)
  998.     {
  999.       flx = flx->fl_parent;
  1000.       fly = fly->fl_parent;
  1001.     }
  1002.       return strcmp (flx->fl_name, fly->fl_name);
  1003.     }
  1004. }
  1005.  
  1006. /****************************************************************************/
  1007. /* Hash stuff for `struct file_link'.  */
  1008.  
  1009. unsigned long
  1010. file_link_hash_1 (void const *key)
  1011. {
  1012.   unsigned long result = 0;
  1013.   struct file_link const *parent = (IS_ROOT_FILE_LINK (((struct file_link const *) key))
  1014.                     ? 0 : ((struct file_link const *) key)->fl_parent);
  1015.   STRING_HASH_1 (((struct file_link const *) key)->fl_name, result);
  1016.   ADDRESS_HASH_1 (parent, result);
  1017.   return result;
  1018. }
  1019.  
  1020. unsigned long
  1021. file_link_hash_2 (void const *key)
  1022. {
  1023.   unsigned long result = 0;
  1024.   struct file_link const *parent = (IS_ROOT_FILE_LINK (((struct file_link const *) key))
  1025.                     ? 0 : ((struct file_link const *) key)->fl_parent);
  1026.   STRING_HASH_2 (((struct file_link const *) key)->fl_name, result);
  1027.   ADDRESS_HASH_2 (parent, result);
  1028.   return result;
  1029. }
  1030.  
  1031. int
  1032. file_link_hash_compare (void const *x, void const *y)
  1033. {
  1034.   int result;
  1035.   struct file_link const *x_parent = (IS_ROOT_FILE_LINK (((struct file_link const *) x))
  1036.                       ? 0 : ((struct file_link const *) x)->fl_parent);
  1037.   struct file_link const *y_parent = (IS_ROOT_FILE_LINK (((struct file_link const *) y))
  1038.                       ? 0 : ((struct file_link const *) y)->fl_parent);
  1039.   ADDRESS_COMPARE (x_parent, y_parent, result);
  1040.   if (result)
  1041.     return result;
  1042.   STRING_COMPARE (((struct file_link const *) x)->fl_name,
  1043.           ((struct file_link const *) y)->fl_name, result);
  1044.   return result;
  1045. }
  1046.  
  1047. /* Count directory components between flink and its root.  */
  1048.  
  1049. int
  1050. links_depth (struct file_link const *flink)
  1051. {
  1052.   int depth = 0;
  1053.   while (!IS_ROOT_FILE_LINK (flink))
  1054.     {
  1055.       depth++;
  1056.       flink = flink->fl_parent;
  1057.     }
  1058.   return depth;
  1059. }
  1060.  
  1061. #if HAVE_LINK
  1062.  
  1063. /****************************************************************************/
  1064. /* Hash stuff for `struct dev_ino'.  */
  1065.  
  1066. unsigned long
  1067. dev_ino_hash_1 (void const *key)
  1068. {
  1069.   unsigned long result = 0;
  1070.   INTEGER_HASH_1 (((struct dev_ino const *) key)->di_dev, result);
  1071.   INTEGER_HASH_1 (((struct dev_ino const *) key)->di_ino, result);
  1072.   return result;
  1073. }
  1074.  
  1075. unsigned long
  1076. dev_ino_hash_2 (void const *key)
  1077. {
  1078.   unsigned long result = 0;
  1079.   INTEGER_HASH_2 (((struct dev_ino const *) key)->di_dev, result);
  1080.   INTEGER_HASH_2 (((struct dev_ino const *) key)->di_ino, result);
  1081.   return result;
  1082. }
  1083.  
  1084. int
  1085. dev_ino_hash_compare (void const *x, void const *y)
  1086. {
  1087.   int result;
  1088.   INTEGER_COMPARE (((struct dev_ino const *) x)->di_ino,
  1089.            ((struct dev_ino const *) y)->di_ino, result);
  1090.   if (result)
  1091.     return result;
  1092.   INTEGER_COMPARE (((struct dev_ino const *) x)->di_dev,
  1093.            ((struct dev_ino const *) y)->di_dev, result);
  1094.   return result;
  1095. }
  1096.  
  1097. #endif
  1098.  
  1099. /*******************************************************************/
  1100.  
  1101. struct file_link *
  1102. init_walker (struct idhead *idhp)
  1103. {
  1104.   init_idh_obstacks (idhp);
  1105.   init_idh_tables (idhp);
  1106.   return get_current_dir_link ();
  1107. }
  1108.  
  1109. void
  1110. init_idh_obstacks (struct idhead *idhp)
  1111. {
  1112.   obstack_init (&idhp->idh_member_file_obstack);
  1113.   obstack_init (&idhp->idh_file_link_obstack);
  1114. #if HAVE_LINK
  1115.   obstack_init (&idhp->idh_dev_ino_obstack);
  1116. #endif
  1117. }
  1118.  
  1119. void
  1120. init_idh_tables (struct idhead *idhp)
  1121. {
  1122.   hash_init (&idhp->idh_member_file_table, 16*1024,
  1123.          member_file_hash_1, member_file_hash_2, member_file_hash_compare);
  1124.   hash_init (&idhp->idh_file_link_table, 16*1024,
  1125.          file_link_hash_1, file_link_hash_2, file_link_hash_compare);
  1126. #if HAVE_LINK
  1127.   hash_init (&idhp->idh_dev_ino_table, 16*1024,
  1128.          dev_ino_hash_1, dev_ino_hash_2, dev_ino_hash_compare);
  1129. #endif
  1130. }
  1131.