diff options
Diffstat (limited to 'lib/idwalk.c')
| -rw-r--r-- | lib/idwalk.c | 1189 |
1 files changed, 1189 insertions, 0 deletions
diff --git a/lib/idwalk.c b/lib/idwalk.c new file mode 100644 index 0000000..77aacf2 --- /dev/null +++ b/lib/idwalk.c @@ -0,0 +1,1189 @@ +#include <sys/types.h> +#include <sys/stat.h> +#include <sys/param.h> +#include <stdio.h> +#include <stdlib.h> +#include <stddef.h> +#include <dirent.h> +#include <unistd.h> +#include <string.h> +#include <fcntl.h> +#include <fnmatch.h> +#ifndef FNM_FILE_NAME +#define FNM_FILE_NAME FNM_PATHNAME +#endif + +#define DEBUG(args) /* printf args */ + +#include <config.h> +#include "system.h" +#include "idfile.h" +#include "error.h" +#include "alloc.h" +#include "dynvec.h" +#include "strxtra.h" +#include "scanners.h" +#include "pathmax.h" + +int walk_dir __P((struct file_link *dir_link)); +void walk_flink __P((struct file_link *flink, struct dynvec *sub_dirs_vec)); +struct member_file *get_member_file __P((struct file_link *flink)); +struct lang_args *get_lang_args __P((struct file_link const *flink)); +int walk_sub_dirs __P((struct dynvec *sub_dirs_vec)); +int classify_link __P((struct file_link *flink, struct stat *st)); +struct file_link *get_link_from_dirent __P((struct dirent *dirent, struct file_link *parent)); +struct file_link *make_link_from_dirent __P((struct dirent *dirent, struct file_link *parent)); +struct file_link *get_link_from_string __P((char const *name, struct file_link *parent)); +struct file_link *make_link_from_string __P((char const *name, struct file_link *parent)); +static int same_as_dot __P((char const *cwd)); +int chdir_to_link __P((struct file_link* dir_link)); +struct file_link const **fill_link_vector __P((struct file_link const **vec_buf, struct file_link const *flink)); +struct file_link const **fill_link_vector_1 __P((struct file_link const **vec_buf, struct file_link const *flink)); +char const *maybe_relative_path __P((char *buffer, struct file_link const *to_link, struct file_link const *from_link)); +char *fill_dot_dots __P((char *buf, int levels)); +char *absolute_path __P((char *buffer, struct file_link const *flink)); +static char *absolute_path_1 __P((char *buffer, struct file_link const *flink)); +unsigned long member_file_hash_1 __P((void const *key)); +unsigned long member_file_hash_2 __P((void const *key)); +int member_file_hash_compare __P((void const *x, void const *y)); +unsigned long file_link_hash_1 __P((void const *key)); +unsigned long file_link_hash_2 __P((void const *key)); +int file_link_hash_compare __P((void const *x, void const *y)); +int file_link_qsort_compare __P((void const *x, void const *y)); +int links_depth __P((struct file_link const *flink)); +unsigned long dev_ino_hash_1 __P((void const *key)); +unsigned long dev_ino_hash_2 __P((void const *key)); +int dev_ino_hash_compare __P((void const *x, void const *y)); +int symlink_ancestry __P((struct file_link *flink)); + +/* Interpret `HAVE_LINK' as meaning `UN*X style' directory structure + (e.g., A single root called `/', with `/' separating links), and + !HAVE_LINK as `DOS|OS/2|Windows style' (e.g., Multiple root volues + named `x:', with `\' separating links). */ + +#if HAVE_LINK +struct file_link *find_alias_link __P((struct file_link *flink, struct stat *st)); +struct member_file *maybe_get_member_file __P((struct file_link *flink, struct stat *st)); +struct member_file *find_member_file __P((struct file_link const *flink)); +# define IS_ABSOLUTE(_dir_) ((_dir_)[0] == '/') +# define SLASH_STRING "/" +# define SLASH_CHAR '/' +# define DOT_DOT_SLASH "../" +# define MAYBE_FNM_CASEFOLD 0 +#else +/* NEEDSWORK: prefer forward-slashes as a user-configurable option. */ +# define IS_ABSOLUTE(_dir_) ((_dir_)[1] == ':') +# define SLASH_STRING "\\/" +# define SLASH_CHAR '\\' +# define DOT_DOT_SLASH "..\\" +# define MAYBE_FNM_CASEFOLD FNM_CASEFOLD +#endif + +#define IS_DOT(s) ((s)[0] == '.' && (s)[1] == '\0') +#define IS_DOT_DOT(s) ((s)[0] == '.' && (s)[1] == '.' && (s)[2] == '\0') +#define IS_DOT_or_DOT_DOT(s) \ + (((s)[0] == '.') && (((s)[1] == '\0') || ((s)[1] == '.' && (s)[2] == '\0'))) + +static struct file_link *current_dir_link = 0; + +char* xgetcwd __P((void)); + +/****************************************************************************/ +/* Walk the file-system tree rooted at `dir_link', looking for files + that are eligible for scanning. */ + +int +walk_dir (struct file_link *dir_link) +{ + char buf[PATH_MAX]; + int scannable_files; + struct dynvec *sub_dirs_vec; + DIR *dirp; + + if (!chdir_to_link (dir_link)) + return 0; + dirp = opendir ("."); + if (dirp == 0) + { + error (0, errno, _("can't read directory `%s' (`.' from `%s')"), + absolute_path (buf, dir_link), xgetcwd ()); + return 0; + } + sub_dirs_vec = make_dynvec (32); + scannable_files = 0; + for (;;) + { + struct file_link *flink; + struct dirent *dirent = readdir (dirp); + + if (dirent == 0) + break; + if (IS_DOT_or_DOT_DOT (dirent->d_name)) + continue; + + flink = get_link_from_dirent (dirent, dir_link); + walk_flink (flink, sub_dirs_vec); + } + closedir (dirp); + + scannable_files += walk_sub_dirs (sub_dirs_vec); + dynvec_free (sub_dirs_vec); + return scannable_files; +} + +/* Walk the directories found by walk_dir, calling walk_dir + recursively for each directory. */ + +int +walk_sub_dirs (struct dynvec *sub_dirs_vec) +{ + struct file_link **sub_dirs; + struct file_link **sub_dirs_end; + int total_scannable_files = 0; + + dynvec_freeze (sub_dirs_vec); + sub_dirs_end = (struct file_link **) + &sub_dirs_vec->dv_vec[sub_dirs_vec->dv_fill]; + sub_dirs = (struct file_link **) sub_dirs_vec->dv_vec; + for ( ; sub_dirs < sub_dirs_end; sub_dirs++) + { + struct file_link *sub_dir_link = *sub_dirs; + int scannable_files = walk_dir (sub_dir_link); + if (scannable_files) + total_scannable_files += scannable_files; + } + return total_scannable_files; +} + +void +walk_flink (struct file_link *flink, struct dynvec *sub_dirs_vec) +{ + char buf[PATH_MAX]; + struct stat st; + unsigned int old_flags; + unsigned int new_flags; + + new_flags = classify_link (flink, &st); + if (new_flags == 0) + return; + + old_flags = flink->fl_flags; + if ((old_flags & FL_TYPE_MASK) + && (old_flags & FL_TYPE_MASK) != (new_flags & FL_TYPE_MASK)) + error (0, 0, _("notice: `%s' was a %s, but is now a %s!"), + absolute_path (buf, flink), + (FL_IS_FILE (old_flags) ? _("file") : _("directory")), + (FL_IS_FILE (new_flags) ? _("file") : _("directory"))); + + flink->fl_flags = (old_flags & ~(FL_TYPE_MASK|FL_SYM_LINK)) | new_flags; + if (FL_IS_DIR (new_flags)) + { + if (sub_dirs_vec == 0) + walk_dir (flink); + else if (!(new_flags & FL_SYM_LINK)) /* NEEDSWORK: optinally ignore? */ + dynvec_append (sub_dirs_vec, flink); + } + else + { + struct member_file *member; +#if HAVE_LINK + member = maybe_get_member_file (flink, &st); +#else + member = get_member_file (flink); +#endif + if (member == 0) + return; +#if 0 + member->mf_modify_time = st.st_mtime; + member->mf_access_time = st.st_atime; + if (member->mf_old_index < 0 || st.st_mtime > idh.idh_mod_time) + member->mf_scan_index = 0; +#endif + } +} + +/****************************************************************************/ +/* Serialize and write a file_link hierarchy. */ + +void +serialize_file_links (struct idhead *idhp) +{ + struct file_link **flinks_0; + struct file_link **flinks; + struct file_link **end; + struct file_link **parents_0; + struct file_link **parents; + unsigned long parent_index = 0; + + flinks_0 = (struct file_link **) hash_dump (&idhp->idh_file_link_table, + 0, file_link_qsort_compare); + end = &flinks_0[idhp->idh_file_link_table.ht_fill]; + parents = parents_0 = MALLOC (struct file_link *, idhp->idh_file_link_table.ht_fill); + for (flinks = flinks_0; flinks < end; flinks++) + { + struct file_link *flink = *flinks; + if (!(flink->fl_flags & FL_USED)) + break; + io_write (idhp->idh_FILE, flink->fl_name, 0, IO_TYPE_STR); + io_write (idhp->idh_FILE, &flink->fl_flags, sizeof (flink->fl_flags), IO_TYPE_INT); + io_write (idhp->idh_FILE, (IS_ROOT_FILE_LINK (flink) + ? &parent_index : &flink->fl_parent->fl_index), + FL_PARENT_INDEX_BYTES, IO_TYPE_INT); + *parents++ = flink->fl_parent; /* save parent link before clobbering */ + flink->fl_index = parent_index++; + } + /* restore parent links */ + for ((flinks = flinks_0), (parents = parents_0); flinks < end; flinks++) + { + struct file_link *flink = *flinks; + if (!(flink->fl_flags & FL_USED)) + break; + flink->fl_parent = *parents++; + } + free (parents_0); + free (flinks_0); + idhp->idh_file_links = parent_index; + idhp->idh_files = idhp->idh_member_file_table.ht_fill; +} + +/* Separate the wheat from the chaff. Mark those file_links that are + components in member files. */ + +void +mark_member_file_links (struct idhead *idhp) +{ + struct member_file **members_0 + = (struct member_file **) hash_dump (&idhp->idh_member_file_table, + 0, member_file_qsort_compare); + struct member_file **end = &members_0[idhp->idh_member_file_table.ht_fill]; + struct member_file **members; + int new_index = 0; + + for (members = members_0; members < end; members++) + { + struct member_file *member = *members; + struct file_link *flink; + member->mf_index = new_index++; + for (flink = member->mf_link; + !(flink->fl_flags & FL_USED); flink = flink->fl_parent) + flink->fl_flags |= FL_USED; + } + free (members_0); +} + +/* Read and reconstruct a serialized file_link hierarchy. */ + +struct file_link ** +deserialize_file_links (struct idhead *idhp) +{ + struct file_link **flinks_0 = MALLOC (struct file_link *, idhp->idh_file_links); + struct file_link **flinks = flinks_0; + struct file_link **members_0 = MALLOC (struct file_link *, idhp->idh_files + 1); + struct file_link **members = members_0; + struct file_link *flink; + struct file_link **slot; + int i; + + for (i = 0; i < idhp->idh_file_links; i++) + { + unsigned long parent_index; + int c; + + obstack_blank (&idhp->idh_file_link_obstack, offsetof (struct file_link, fl_name)); + if (obstack_room (&idhp->idh_file_link_obstack) >= idhp->idh_max_link) + do + { + c = getc (idhp->idh_FILE); + obstack_1grow_fast (&idhp->idh_file_link_obstack, c); + } + while (c); + else + do + { + c = getc (idhp->idh_FILE); + obstack_1grow (&idhp->idh_file_link_obstack, c); + } + while (c); + flink = (struct file_link *) obstack_finish (&idhp->idh_file_link_obstack); + *flinks = flink; + io_read (idhp->idh_FILE, &flink->fl_flags, sizeof (flink->fl_flags), IO_TYPE_INT); + io_read (idhp->idh_FILE, &parent_index, FL_PARENT_INDEX_BYTES, IO_TYPE_INT); + flink->fl_parent = flinks_0[parent_index]; + slot = (struct file_link **) hash_find_slot (&idhp->idh_file_link_table, flink); + if (HASH_VACANT (*slot)) + hash_insert_at (&idhp->idh_file_link_table, flink, slot); + else + { + obstack_free (&idhp->idh_file_link_obstack, flink); + (*slot)->fl_flags = flink->fl_flags; + flink = *flinks = *slot; + } + flinks++; + if (flink->fl_flags & FL_MEMBER) + *members++ = flink; + } + free (flinks_0); + *members = 0; + return members_0; +} + + +#if HAVE_LINK + +/****************************************************************************/ +/* Return a `member_file' for this `flink' *if* the filename matches + some scan pattern, and no alias for the file takes precedence ([1] + hard-links dominate symbolic-links; [2] for two hard-links: first + come, first served). */ + +struct member_file * +maybe_get_member_file (struct file_link *flink, struct stat *st) +{ + char buf[PATH_MAX]; + struct file_link *alias_link; + struct member_file *member; + struct member_file *alias_member = 0; + + member = get_member_file (flink); + alias_link = find_alias_link (flink, st); + if (alias_link) + alias_member = find_member_file (alias_link); + + if (member && alias_member) + { + char alias_buf[PATH_MAX]; + int ancestry = symlink_ancestry (flink); + int alias_ancestry = symlink_ancestry (alias_link); + if (member->mf_lang_args != alias_member->mf_lang_args) + error (0, 0, _("warning: `%s' and `%s' are the same file, but yield different scans!"), + absolute_path (buf, flink), absolute_path (alias_buf, alias_link)); + else if (alias_ancestry > ancestry) + { + hash_delete (&idh.idh_member_file_table, member); + member->mf_link->fl_flags &= ~FL_MEMBER; + return 0; + } + else + { + hash_delete (&idh.idh_member_file_table, alias_member); + alias_member->mf_link->fl_flags &= ~FL_MEMBER; + } + } + return member; +} + +/* Return a previously registered alias for `flink', if any. */ + +struct file_link * +find_alias_link (struct file_link *flink, struct stat *st) +{ + struct dev_ino *dev_ino; + struct dev_ino **slot; + + dev_ino = (struct dev_ino *) obstack_alloc (&idh.idh_dev_ino_obstack, sizeof (struct dev_ino)); + dev_ino->di_dev = st->st_dev; + dev_ino->di_ino = st->st_ino; + slot = (struct dev_ino **) hash_find_slot (&idh.idh_dev_ino_table, dev_ino); + if (HASH_VACANT (*slot)) + { + dev_ino->di_link = flink; + hash_insert_at (&idh.idh_dev_ino_table, dev_ino, slot); + return 0; + } + else + { + obstack_free (&idh.idh_dev_ino_obstack, dev_ino); + return (*slot)->di_link; + } +} + +/* Return the distance from `flink' to a symbolic-link ancestor + directory. PATH_MAX is considered an infinite distance (e.g., + there are no symlinks between `flink' and the root). */ + +int +symlink_ancestry (struct file_link *flink) +{ + int ancestry = 0; + while (!IS_ROOT_FILE_LINK (flink)) + { + if (flink->fl_flags & FL_SYM_LINK) + return ancestry; + ancestry++; + flink = flink->fl_parent; + } + return PATH_MAX; +} + +#endif /* HAVE_LINK */ + +struct member_file * +get_member_file (struct file_link *flink) +{ + char buf[PATH_MAX]; + struct member_file *member; + struct member_file **slot; + struct lang_args const *args; + + args = get_lang_args (flink); + if (args == 0) + { + DEBUG (("%s <IGNORE>\n", absolute_path (buf, flink))); + return 0; + } + DEBUG (("%s <%s> <%s>\n", absolute_path (buf, flink), + args->la_language->lg_name, (args->la_args_string + ? args->la_args_string : ""))); + + member = (struct member_file *) obstack_alloc (&idh.idh_member_file_obstack, + sizeof (struct member_file)); + member->mf_link = flink; + slot = (struct member_file **) hash_find_slot (&idh.idh_member_file_table, member); + if (HASH_VACANT (*slot)) + { + member->mf_index = -1; + hash_insert_at (&idh.idh_member_file_table, member, slot); + flink->fl_flags |= FL_MEMBER; + } + else + { + obstack_free (&idh.idh_member_file_obstack, member); +#if 0 + if (member->mf_lang_args != args) + { + error (0, 0, _("notice: scan parameters changed for `%s'"), + absolute_path (buf, flink)); + member->mf_old_index = -1; + } +#endif + member = *slot; + } + member->mf_lang_args = args; + return *slot; +} + +struct member_file * +find_member_file (struct file_link const *flink) +{ + struct member_file key; + struct member_file **slot; + + key.mf_link = (struct file_link *) flink; + slot = (struct member_file **) hash_find_slot (&idh.idh_member_file_table, &key); + if (HASH_VACANT (*slot)) + return 0; + return *slot; +} + +/* March down the list of lang_args, and return the first one whose + pattern matches FLINK. Return the matching lang_args, if a + scanner exists for that language, otherwise return 0. */ + +struct lang_args * +get_lang_args (struct file_link const *flink) +{ + struct lang_args *args = lang_args_list; + + while (args) + { + if (strchr (args->la_pattern, SLASH_CHAR)) + { + char buf[PATH_MAX]; + absolute_path (buf, flink); + if (fnmatch (args->la_pattern, buf, MAYBE_FNM_CASEFOLD | FNM_FILE_NAME) == 0) + return (args->la_language ? args : 0); + } + else + { + if (fnmatch (args->la_pattern, flink->fl_name, MAYBE_FNM_CASEFOLD) == 0) + return (args->la_language ? args : 0); + } + args = args->la_next; + } + return (lang_args_default->la_language ? lang_args_default : 0); +} + +/****************************************************************************/ +/* Convert a file name string to an absolute chain of `file_link's. */ + +struct file_link * +parse_file_name (char *file_name, struct file_link *relative_dir_link) +{ + struct file_link *flink; + + if (IS_ABSOLUTE (file_name)) + { +#if HAVE_LINK + flink = get_link_from_string (SLASH_STRING, 0); +#else + flink = 0; +#endif + } + else if (relative_dir_link) + flink = relative_dir_link; + else if (current_dir_link) + flink = current_dir_link; + else + flink = get_current_dir_link (); + + for (;;) + { + char const* link_name = strtok (file_name, SLASH_STRING); + if (link_name == 0) + break; + file_name = 0; + if (*link_name == '\0' || IS_DOT (link_name)) + ; + else if (IS_DOT_DOT (link_name)) + flink = flink->fl_parent; + else + { + struct stat st; + flink = get_link_from_string (link_name, flink); + if (!flink->fl_flags) + flink->fl_flags = classify_link (flink, &st); + } + } + return flink; +} + +/* Return an absolute chain of `file_link's representing the current + working directory. */ + +struct file_link * +get_current_dir_link (void) +{ + struct file_link *dir_link; + char *cwd_0; + char *cwd; + char *xcwd = 0; + + if (current_dir_link) + return current_dir_link; + + cwd_0 = getenv ("PWD"); + if (cwd_0) + cwd_0 = strdup (cwd_0); + if (!same_as_dot (cwd_0)) + cwd_0 = xcwd = xgetcwd (); + if (cwd_0 == 0) + error (1, errno, _("can't get working directory")); + cwd = cwd_0; +#if HAVE_LINK + dir_link = get_link_from_string (SLASH_STRING, 0); + dir_link->fl_flags = (dir_link->fl_flags & ~FL_TYPE_MASK) | FL_TYPE_DIR; +#else + dir_link = 0; +#endif + for (;;) + { + struct stat st; + char const* link_name = strtok (cwd, SLASH_STRING); + if (link_name == 0) + break; + cwd = 0; + dir_link = get_link_from_string (link_name, dir_link); + if (!dir_link->fl_flags) + dir_link->fl_flags = classify_link (dir_link, &st); + } + chdir_to_link (dir_link); + if (xcwd) + free (xcwd); + current_dir_link = dir_link; + return dir_link; +} + +static int +same_as_dot (char const *cwd) +{ + struct stat cwd_st; + struct stat dot_st; + + if (cwd == 0 || *cwd != '/' + || stat (cwd, &cwd_st) < 0 + || stat (".", &dot_st) < 0) + return 0; + return ((cwd_st.st_ino == dot_st.st_ino) && (cwd_st.st_dev == dot_st.st_dev)); +} + +/* Change the working directory to the directory represented by + `dir_link'. Choose the shortest path to the destination based on + the cached value of the current directory. */ + +int +chdir_to_link (struct file_link *dir_link) +{ + char to_buf[PATH_MAX]; + char from_buf[PATH_MAX]; + + if (current_dir_link == dir_link) + return 1; + + if (current_dir_link) + maybe_relative_path (to_buf, dir_link, current_dir_link); + else + absolute_path (to_buf, dir_link); + if (chdir (to_buf) < 0) + { + if (IS_ABSOLUTE (to_buf)) + error (0, errno, _("can't chdir to `%s'"), to_buf); + else + error (0, errno, _("can't chdir to `%s' from `%s'"), to_buf, + absolute_path (from_buf, current_dir_link)); + return 0; + } + else + { + current_dir_link = dir_link; + return 1; + } +} + +/****************************************************************************/ +/* Gather information about the link at `flink'. If it's a good + file or directory, return its mod-time and type. */ + +int +classify_link (struct file_link *flink, struct stat *st) +{ + char buf[PATH_MAX]; + unsigned int flags = 0; + + if (!chdir_to_link (flink->fl_parent)) + return 0; + +#ifdef S_IFLNK + if (lstat (flink->fl_name, st) < 0) + { + error (0, errno, _("can't lstat `%s' from `%s'"), flink->fl_name, xgetcwd ()); + return 0; + } + if (S_ISLNK (st->st_mode)) + { +#endif + if (stat (flink->fl_name, st) < 0) + { + error (0, errno, _("can't stat `%s' from `%s'"), flink->fl_name, xgetcwd ()); + return 0; + } +#ifdef S_IFLNK + flags |= FL_SYM_LINK; + } +#endif + if (S_ISDIR (st->st_mode)) + flags |= FL_TYPE_DIR; + else if (S_ISREG (st->st_mode)) + flags |= FL_TYPE_FILE; + else + return 0; + return flags; +} + +/****************************************************************************/ +/* Retrieve an existing flink; or if none exists, create one. */ + +struct file_link * +get_link_from_dirent (struct dirent *dirent, struct file_link *parent) +{ + struct file_link **slot; + struct file_link *new_link; + + new_link = make_link_from_dirent (dirent, parent); + slot = (struct file_link **) hash_find_slot (&idh.idh_file_link_table, new_link); + if (HASH_VACANT (*slot)) + hash_insert_at (&idh.idh_file_link_table, new_link, slot); + else + obstack_free (&idh.idh_file_link_obstack, new_link); + return *slot; +} + +struct file_link * +get_link_from_string (char const *name, struct file_link *parent) +{ + struct file_link **slot; + struct file_link *new_link; + + new_link = make_link_from_string (name, parent); + slot = (struct file_link **) hash_find_slot (&idh.idh_file_link_table, new_link); + if (HASH_VACANT (*slot)) + hash_insert_at (&idh.idh_file_link_table, new_link, slot); + else + obstack_free (&idh.idh_file_link_obstack, new_link); + return *slot; +} + +struct file_link * +make_link_from_dirent (struct dirent* dirent, struct file_link *parent) +{ + struct file_link *flink; + + flink = (struct file_link *) obstack_alloc (&idh.idh_file_link_obstack, + sizeof (struct file_link) + strlen (dirent->d_name)); + strcpy (flink->fl_name, dirent->d_name); + flink->fl_parent = parent ? parent : flink; + flink->fl_flags = 0; + + return flink; +} + +struct file_link * +make_link_from_string (char const* name, struct file_link *parent) +{ + struct file_link *flink; + + flink = (struct file_link *) obstack_alloc (&idh.idh_file_link_obstack, + sizeof (struct file_link) + strlen (name)); + strcpy (flink->fl_name, name); + flink->fl_parent = parent ? parent : flink; + flink->fl_flags = 0; + + return flink; +} + +/****************************************************************************/ +/* Convert a `file_link' chain to a vector of component `file_link's, + with the root at [0]. Return a pointer beyond the final component. */ + +struct file_link const ** +fill_link_vector (struct file_link const **vec_buf, struct file_link const *flink) +{ + vec_buf = fill_link_vector_1 (vec_buf, flink); + *vec_buf = 0; + return vec_buf; +} + +struct file_link const ** +fill_link_vector_1 (struct file_link const **vec_buf, struct file_link const *flink) +{ + if (!IS_ROOT_FILE_LINK (flink)) + vec_buf = fill_link_vector_1 (vec_buf, flink->fl_parent); + *vec_buf++ = flink; + return vec_buf; +} + +/****************************************************************************/ +/* Fill BUF_0 with a path to TO_LINK. If a relative path from + FROM_LINK is possible (i.e., no intervening symbolic-links) and + shorter, return the relative path; otherwise, return an absolute + path. */ + +char const * +maybe_relative_path (char *buf_0, struct file_link const *to_link, struct file_link const *from_link) +{ + struct file_link const *to_link_vec_0[PATH_MAX/2]; + struct file_link const *from_link_vec_0[PATH_MAX/2]; + struct file_link const **to_link_vec = to_link_vec_0; + struct file_link const **from_link_vec = from_link_vec_0; + struct file_link const **from_link_end; + struct file_link const **from_links; + char *buf; + int levels; + + if (from_link == 0) + from_link = current_dir_link; + + /* Optimize common cases. */ + if (to_link == from_link) + return strcpy (buf_0, "."); + else if (to_link->fl_parent == from_link) + return strcpy (buf_0, to_link->fl_name); + else if (from_link->fl_flags & FL_SYM_LINK) + return absolute_path (buf_0, to_link); + else if (to_link == from_link->fl_parent) + return strcpy (buf_0, ".."); + else if (to_link->fl_parent == from_link->fl_parent) + { + strcpy (buf_0, DOT_DOT_SLASH); + strcpy (&buf_0[3], to_link->fl_name); + return buf_0; + } + + from_link_end = fill_link_vector (from_link_vec, from_link); + fill_link_vector (to_link_vec, to_link); + while (*to_link_vec == *from_link_vec) + { + if (*to_link_vec == 0) + return "."; + to_link_vec++; + from_link_vec++; + } + levels = from_link_end - from_link_vec; + if (levels >= (from_link_vec - from_link_vec_0)) + return absolute_path (buf_0, to_link); + for (from_links = from_link_vec; *from_links; from_links++) + if ((*from_links)->fl_flags & FL_SYM_LINK) + return absolute_path (buf_0, to_link); + buf = fill_dot_dots (buf_0, levels); + while (*to_link_vec) + { + strcpy (buf, (*to_link_vec)->fl_name); + buf += strlen (buf); + if ((*to_link_vec)->fl_name[0] != SLASH_CHAR && *++to_link_vec) + *buf++ = SLASH_CHAR; + } + return buf_0; +} + +/* Fill `buf' with sequences of "../" in order to ascend so many + `levels' in a directory tree. */ + +char * +fill_dot_dots (char *buf, int levels) +{ + while (levels--) + { + strcpy (buf, DOT_DOT_SLASH); + buf += 3; + } + return buf; +} + +/****************************************************************************/ +/* Fill `buffer' with the absolute path to `flink'. */ + +char * +absolute_path (char *buffer, struct file_link const *flink) +{ + char *end = absolute_path_1 (buffer, flink); + /* Clip the trailing slash. */ +#if HAVE_LINK + if (end > &buffer[1]) + end--; +#else + if (end > &buffer[3]) + end--; +#endif + *end = '\0'; + return buffer; +} + +static char * +absolute_path_1 (char *buffer, struct file_link const *flink) +{ + char *end; + if (IS_ROOT_FILE_LINK (flink)) + end = buffer; + else + end = absolute_path_1 (buffer, flink->fl_parent); + strcpy (end, flink->fl_name); + if (*end == SLASH_CHAR) + end++; + else + { + end += strlen (end); + *end++ = SLASH_CHAR; + } + return end; +} + +/****************************************************************************/ +/* Hash stuff for `struct member_file'. */ + +unsigned long +member_file_hash_1 (void const *key) +{ + return_ADDRESS_HASH_1 (((struct member_file const *) key)->mf_link); +} + +unsigned long +member_file_hash_2 (void const *key) +{ + return_ADDRESS_HASH_2 (((struct member_file const *) key)->mf_link); +} + +int +member_file_hash_compare (void const *x, void const *y) +{ + return_ADDRESS_COMPARE (((struct member_file const *) x)->mf_link, + ((struct member_file const *) y)->mf_link); +} + +/* Collating sequence: + - language.map index + - mf_link: breadth-first, alphabetical */ + +int +member_file_qsort_compare (void const *x, void const *y) +{ + struct member_file const *mfx = *(struct member_file const **) x; + struct member_file const *mfy = *(struct member_file const **) y; + int result; + + INTEGER_COMPARE (mfx->mf_lang_args->la_index, mfy->mf_lang_args->la_index, result); + if (result) + return result; + else + { + struct file_link const *flx = mfx->mf_link; + struct file_link const *fly = mfy->mf_link; + if (flx->fl_parent == fly->fl_parent) + return strcmp (flx->fl_name, fly->fl_name); + result = (links_depth (flx) - links_depth (fly)); + if (result) + return result; + while (flx->fl_parent != fly->fl_parent) + { + flx = flx->fl_parent; + fly = fly->fl_parent; + } + return strcmp (flx->fl_name, fly->fl_name); + } +} + +/****************************************************************************/ +/* Hash stuff for `struct file_link'. */ + +unsigned long +file_link_hash_1 (void const *key) +{ + unsigned long result = 0; + struct file_link const *parent = (IS_ROOT_FILE_LINK (((struct file_link const *) key)) + ? 0 : ((struct file_link const *) key)->fl_parent); + STRING_HASH_1 (((struct file_link const *) key)->fl_name, result); + ADDRESS_HASH_1 (parent, result); + return result; +} + +unsigned long +file_link_hash_2 (void const *key) +{ + unsigned long result = 0; + struct file_link const *parent = (IS_ROOT_FILE_LINK (((struct file_link const *) key)) + ? 0 : ((struct file_link const *) key)->fl_parent); + STRING_HASH_2 (((struct file_link const *) key)->fl_name, result); + ADDRESS_HASH_2 (parent, result); + return result; +} + +int +file_link_hash_compare (void const *x, void const *y) +{ + int result; + struct file_link const *x_parent = (IS_ROOT_FILE_LINK (((struct file_link const *) x)) + ? 0 : ((struct file_link const *) x)->fl_parent); + struct file_link const *y_parent = (IS_ROOT_FILE_LINK (((struct file_link const *) y)) + ? 0 : ((struct file_link const *) y)->fl_parent); + ADDRESS_COMPARE (x_parent, y_parent, result); + if (result) + return result; + STRING_COMPARE (((struct file_link const *) x)->fl_name, + ((struct file_link const *) y)->fl_name, result); + return result; +} + +/* Collation sequence: + - Used before unused. + - Among used: breadth-first (dirs before files, parent dirs before children) + - Among files: collate by mf_index. */ + +int +file_link_qsort_compare (void const *x, void const *y) +{ + struct file_link const *flx = *(struct file_link const **) x; + struct file_link const *fly = *(struct file_link const **) y; + unsigned int x_flags = flx->fl_flags; + unsigned int y_flags = fly->fl_flags; + int result; + + result = (y_flags & FL_USED) - (x_flags & FL_USED); + if (result) + return result; + if (!(x_flags & FL_USED)) /* If neither link is used, we don't care... */ + return 0; + result = (y_flags & FL_TYPE_DIR) - (x_flags & FL_TYPE_DIR); + if (result) + return result; + result = (y_flags & FL_TYPE_MASK) - (x_flags & FL_TYPE_MASK); + if (result) + return result; + if (FL_IS_FILE (x_flags)) + { + struct member_file *x_member = find_member_file (flx); + struct member_file *y_member = find_member_file (fly); + return x_member->mf_index - y_member->mf_index; + } + else + { + int x_depth = links_depth (flx); + int y_depth = links_depth (fly); + return (x_depth - y_depth); + } +} + +/* Count directory components between flink and its root. */ + +int +links_depth (struct file_link const *flink) +{ + int depth = 0; + while (!IS_ROOT_FILE_LINK (flink)) + { + depth++; + flink = flink->fl_parent; + } + return depth; +} + +#if HAVE_LINK + +/****************************************************************************/ +/* Hash stuff for `struct dev_ino'. */ + +unsigned long +dev_ino_hash_1 (void const *key) +{ + unsigned long result = 0; + INTEGER_HASH_1 (((struct dev_ino const *) key)->di_dev, result); + INTEGER_HASH_1 (((struct dev_ino const *) key)->di_ino, result); + return result; +} + +unsigned long +dev_ino_hash_2 (void const *key) +{ + unsigned long result = 0; + INTEGER_HASH_2 (((struct dev_ino const *) key)->di_dev, result); + INTEGER_HASH_2 (((struct dev_ino const *) key)->di_ino, result); + return result; +} + +int +dev_ino_hash_compare (void const *x, void const *y) +{ + int result; + INTEGER_COMPARE (((struct dev_ino const *) x)->di_ino, + ((struct dev_ino const *) y)->di_ino, result); + if (result) + return result; + INTEGER_COMPARE (((struct dev_ino const *) x)->di_dev, + ((struct dev_ino const *) y)->di_dev, result); + return result; +} + +#endif + +/*******************************************************************/ + +void +init_idh_obstacks (struct idhead *idhp) +{ + obstack_init (&idhp->idh_member_file_obstack); + obstack_init (&idhp->idh_file_link_obstack); +#if HAVE_LINK + obstack_init (&idhp->idh_dev_ino_obstack); +#endif +} + +void +init_idh_tables (struct idhead *idhp) +{ + hash_init (&idhp->idh_member_file_table, 16*1024, + member_file_hash_1, member_file_hash_2, member_file_hash_compare); + hash_init (&idhp->idh_file_link_table, 16*1024, + file_link_hash_1, file_link_hash_2, file_link_hash_compare); +#if HAVE_LINK + hash_init (&idhp->idh_dev_ino_table, 16*1024, + dev_ino_hash_1, dev_ino_hash_2, dev_ino_hash_compare); +#endif +} + + +#if TEST_IDWALK +/*******************************************************************/ +/* Test program. */ + +char const *program_name; +struct idhead idh; + +void print_member_file __P((void const *item)); + +void +print_member_file (void const *item) +{ + char buf[PATH_MAX]; +#define member ((struct member_file const *) item) +#if 1 + printf ("%s\n", maybe_relative_path (buf, member->mf_link, 0)); +#else + printf ("%ld %ld %s\n", member->mf_access_time, member->mf_modify_time, + maybe_relative_path (buf, member->mf_link, 0)); +#endif +#undef member +} + +void reset_walker (struct idhead *idhp); +void print_hash_stats (FILE *stream, struct idhead *idhp); + +#define obstack_chunk_alloc xmalloc +#define obstack_chunk_free free + +void +reset_walker (struct idhead *idhp) +{ + hash_delete_items (&idhp->idh_member_file_table); + hash_delete_items (&idhp->idh_file_link_table); +#if HAVE_LINK + hash_delete_items (&idhp->idh_dev_ino_table); +#endif +} + +void +print_hash_stats (FILE *stream, struct idhead *idhp) +{ + fprintf (stream, _("Link Table: ")); hash_print_stats (&idhp->idh_file_link_table, stream); + fprintf (stream, _("\nFile Table: ")); hash_print_stats (&idhp->idh_member_file_table, stream); +#if HAVE_LINK + fprintf (stream, _("\nDupl Table: ")); hash_print_stats (&idhp->idh_dev_ino_table, stream); +#endif + fputc ('\n', stream); +} + +int +main (int argc, char **argv) +{ + struct file_link *cwd_link; + + program_name = ((argc--, *argv++)); + + init_idh_obstacks (&idh); + init_idh_tables (&idh); + + parse_language_map (0); + cwd_link = get_current_dir_link (); + while (argc--) + walk_flink (parse_file_name (*argv++, cwd_link), 0); + + chdir_to_link (cwd_link); + +#if 0 + idh.idh_file_name = "idwalk.serial"; + idh.idh_FILE = fopen (idh.idh_file_name, "w+"); + if (idh.idh_FILE == 0) + error (1, errno, _("can't open `%s' for writing"), idh.idh_file_name); + + printf (">>>>>>>>>>>>>>>> Serialize <<<<<<<<<<<<<<<<\n"); + hash_map (&idh.idh_member_file_table, print_member_file); + printf (">>>>>>>>>>>>>>>> Serialize Stats <<<<<<<<<<<<<<<<\n"); + print_hash_stats (stdout, &idh); + + serialize_file_links (&idh); + reset_walker (&idh); + deserialize_file_links (&idh); + + printf (">>>>>>>>>>>>>>>> Deserialize <<<<<<<<<<<<<<<<\n"); + hash_map (&idh.idh_member_file_table, print_member_file); + printf (">>>>>>>>>>>>>>>> Deserialize Stats <<<<<<<<<<<<<<<<\n"); + print_hash_stats (stdout, &idh); + + printf (">>>>>>>>>>>>>>>> End <<<<<<<<<<<<<<<<\n"); + fclose (idh.idh_FILE); +#endif + return 0; +} + +#endif + +/* + TODO: + - stream I/O + */ |