/************************************************************************ * * * Copyright (c) 1984, Fred Fish * * All Rights Reserved * * * * This software and/or documentation is protected by U.S. * * Copyright Law (Title 17 United States Code). Unauthorized * * reproduction and/or sales may result in imprisonment of up * * to 1 year and fines of up to $10,000 (17 USC 506). * * Copyright infringers may also be subject to civil liability. * * * ************************************************************************ */ /* * FILE * * trees.c routines for manipulating directory trees * * SCCS * * @(#)trees.c 9.11 5/11/88 * * DESCRIPTION * * Contains various modules for creating, manipulating, and * destroying directory trees. * * Pathnames specified by the user are used to build a * directory tree, one node for each component of the pathname. * * Nodes at the same level (siblings) are kept in a linked * list. Within each node is a pointer to the parent node * and a pointer to the first child (if any). This mechanism * allows arbitrary number of children for any given node. * * BUGS * * This code started out as some of the simplest and most * elegant code in bru. Then, due to pressure from special * cases and other unmentionable reasons, it distorted to * become some of the most obscure and tricky code in bru. * Now even the author now has trouble following some of the * more subtle aspects. This whole module needs to be revised. * */ #include "autoconfig.h" #ifdef amiga #include #include #undef VOID #undef TRUE #undef FALSE #endif #include #if (unix || xenix) # include # include # include #else # include "sys.h" #endif #include "config.h" /* Configuration file */ #include "typedefs.h" /* Locally defined types */ #if (unix || xenix) # if (BSD4_2 || HAVE_SEEKDIR) # if sgi # include # else # include /* BSD flavors only */ # endif # else # include "dir.h" /* NOT ; using new dir routines */ # endif #else # include "dir.h" #endif #include "dbug.h" #include "manifest.h" /* Manifest constants */ #include "errors.h" /* Error codes */ #include "macros.h" /* Useful macros */ #include "trees.h" /* Tree types */ #include "finfo.h" /* File information structure */ #include "flags.h" /* Command line arguments */ /* * External bru functions. */ extern BOOLEAN file_access (); /* Check file for access */ extern BOOLEAN file_stat (); /* Get stat buffer for file */ extern BOOLEAN wild (); /* Expand pattern metacharacters */ extern VOID bru_error (); /* Report an error to user */ extern VOID done (); /* Clean up and exit with status */ extern VOID finfo_init (); /* Initialize a finfo structure */ extern VOID reset_times (); /* Reset atime and mtime of file */ extern char *s_strchr (); /* Find given character in string */ extern char *s_strcpy (); /* Copy string s2 to s1 */ extern char *s_strrchr (); /* Find last given character in string */ extern int s_close (); /* Invoke library file close function */ extern int s_open (); /* Invoke library file open function */ extern int s_read (); /* Invoke library file read function */ extern int s_strlen (); /* Find length of string */ extern VOID *get_memory (); /* Memory allocator */ /* * External bru variables. */ extern struct cmd_flags flags; /* Flags from command line */ /* * Internal structures. */ struct node { char *name; /* String for this component */ struct node *child; /* Pointer to first child node */ struct node *sibling; /* Pointer to next sibling */ short nflags; /* Flags word */ }; static struct node root = { /* Implicit root node */ "", NULL, NULL, 0 }; /* * Flag bits for node flags word and macros for manipulating * them. * * Nodes which terminate an explicit pathname specified by the * user on the command line will be marked for expansion, even * when they are not leaf nodes. Thus including both "/" and * "/usr" as command line arguments will result in both "/" and * "/usr" being expanded. Note however that "/usr" will be * ignored during the expansion of "/". * */ #define NF_MATCHED (000001) /* Node has been matched */ #define NF_EXPAND (000002) /* Always expand if directory */ #define MATCHED(a) (a -> nflags & NF_MATCHED) #define SET_MATCHED(a) (a -> nflags |= NF_MATCHED) #define RSET_MATCHED(a) (a -> nflags &= ~NF_MATCHED) #define EXPAND(a) (a -> nflags & NF_EXPAND) #define SET_EXPAND(a) (a -> nflags |= NF_EXPAND) #define RSET_EXPAND(a) (a -> nflags &= ~NF_EXPAND) /* * Some local buffers and variables. */ static char namebuf[NAMESIZE]; /* Pathname buffer */ static struct stat64 sbuf; /* Stat buffer for pathname */ static dev_t dirdev; /* Device containing explicit dir */ /* * The directory routines are declared in "dir.h". We just use * defines to avoid name conflicts with other s_* routines * under compilers without flexnames. If this still doesn't work, * you can probably just use the plain names, since this should * be the only source file which actually reads directories. */ #define s_closedir closedir #define s_opendir opendir #define s_readdir readdir #define s_rewinddir rewinddir #define s_seekdir seekdir #define s_telldir telldir /* * The following are used to determine when there are nodes in the * tree that have never been matched during an archive scan, or when * an archive scan can be terminated because no more matches will * be found. * * When the tree is built, a count of the number of nodes is kept * in "nnodes". As inquires are made, via the path_type function, * about pathnames encountered while scanning an archive, the * appropriate nodes are marked as "matched" if they represent * a component of any selected pathname. * * A count of the matched nodes is kept so that it can be compared * against the count to total nodes to quickly determine if there * are any nodes that have not yet been matched. * * The conditions for determining when no more matches are possible * are considerably more tricky. The current implementation does * not attempt to deal with all possible conditions but simply * elects to continue scanning an archive for more matches if * any filename patterns are matched. This is done via the boolean * variable "wildcards", which is set TRUE whenever the first pattern * expansion matches a node name. Whenever this variable is TRUE, * path_type will never return FINISHED. If the wildcards is FALSE, * and nnodes equals nmatched, and find_type returns NOMATCH, then * the NOMATCH is changed to FINISHED since all nodes have been * matched and no patterns were encountered. * * In summary, after an archive has been processed, if the count * of nodes in tree (nnodes) and count of nodes matched (nmatched) * does not match then the user specified some files which were * never found in the archive, or some of the files specified were not * processed. In either case, the tree can be walked to find the * pathnames of those files and issue the appropriate warnings. */ static int nnodes = 1; /* Count of nodes in tree */ static int nmatched = 0; /* Count of nodes processed */ static BOOLEAN wildcards = FALSE; /* Filename patterns encountered */ /* * Local functions. */ static BOOLEAN add_leaf (); /* Add pathname component to buffer */ static BOOLEAN do_it (); /* Execute function */ static VOID clear_matches (); /* Clear match bits in tree nodes */ static VOID do_dir (); /* Open directory and walk it */ static VOID not_matched (); /* Process nodes not matched */ static VOID save_it (); /* Save file by name */ static VOID walk_subtree (); /* Internal tree walk */ static struct node *add_path (); /* Add path to tree */ static struct node *find_child (); /* Find child with given name */ static struct node *make_child (); /* Add a node as immediate child */ static struct node *make_node (); /* Create a new node */ /* * FUNCTION * * path_type find type of path * * SYNOPSIS * * int path_type (name) * char *name; * * DESCRIPTION * * Invokes the internal routine find_type to determine * the type of a path in tree. Simply * calls find_type with the name and a pointer to the * root node. Find_type then invokes itself * recursively on subsets of the pathname until a result * is obtained. * * Note the very important result that if there is no * tree (root node has no children) then ALL names * will match. Fortuitously, this is exactly what we want. * * Note the special handling of NOMATCH when there is a * user specified tree, all nodes in the tree have been * matched, and no filename patterns were encountered in the * process of matching the tree. In this case, the * return value is converted to FINISHED to indicate that * no more matches are possible. * */ int path_type (name) char *name; { register int type; DBUG_ENTER ("path_type"); DBUG_PRINT ("tree", ("test path \"%s\"", name)); type = find_type (&root, name); if (nnodes > 1 && nnodes == nmatched && !wildcards && type == NOMATCH) { type = FINISHED; } DBUG_PRINT ("ptype", ("path type is %d", type)); DBUG_RETURN (type); } /* * FUNCTION * * tree_add add a pathname to tree * * SYNOPSIS * * VOID tree_add (name) * char *name; * * DESCRIPTION * * Takes pathname pointed to by "name" and builds appropriate * nodes to add it to the current tree. * * Note that this function simply invokes the internal tree * building routine. It was done this way to hide the * fact that the internal routine returns a pointer to a node * structure. To avoid making the node structure visible * outside this module, tree_add was created instead of * calling add_path directly. * * It also serves a secondary purpose of insuring that no * pathname built directly from the tree will exceed the * maximum name size (since it could not be archived * anyway), and marking the leaf node to always be expanded * if it is a directory. * */ VOID tree_add (name) char *name; { register struct node *leafnode; DBUG_ENTER ("tree_add"); DBUG_PRINT ("tree", ("add pathname \"%s\" to tree", name)); if (s_strlen (name) > (NAMESIZE - 1)) { bru_error (ERR_BIGPATH, name); } else { leafnode = add_path (name); SET_EXPAND (leafnode); } DBUG_VOID_RETURN; } /* * FUNCTION * * add_path add a pathname to the tree * * SYNOPSIS * * static struct node *add_path (name) * char *name; * * DESCRIPTION * * Takes a pointer to a complete pathname, such as "/usr/bin/sh", * and creates nodes as appropriate to add the pathname to the * current tree structure. * * Note that add_path is called recursively until the pathname * is "picked apart into pieces" (starting from right end), then * the recursion "unwinds", making nodes and adding them to the tree * as it goes, while rejoining the pathname components. The end * result is the name string restored to its initial condition, and a * pointer to the current bottom of the tree where nodes are * being added. * */ /* * PSEUDO CODE * * Begin add_path * If path has more than one component then * Split path into stem and leaf parts * Add stem to tree * If leaf is not null string then * Add leaf to tree * End if * Rejoin stem and leaf components * Else * Add leaf to tree * End if * Return pointer to leaf node * End add_path * */ static struct node *add_path (name) char *name; { register char *leaf; register struct node *np; DBUG_ENTER ("add_path"); DBUG_PRINT ("tree", ("add path \"%s\"", name)); if ((leaf = s_strrchr (name, '/')) != NULL) { *leaf++ = EOS; np = add_path (name); if (*leaf != EOS) { np = make_child (np, leaf); } *--leaf = '/'; } else { np = make_child (&root, name); } DBUG_RETURN (np); } /* * FUNCTION * * make_child make a child node with given name * * SYNOPSIS * * static struct node *make_child (np, child) * struct node *np; * char *child; * * DESCRIPTION * * Given pointer to a father node (np) and the name of a potential * child node, makes a child with given name if one does not * already exist. * * Returns pointer to the child node, which can potentially be * used as the father of another node during tree growth. * * Note that it is simplier to add siblings at the head * of the list rather than searching for the tail and adding * a new sibling there. However, this confuses the user * because when the tree is walked, files are archived in * reverse order. Thus we go to a little more trouble and * add siblings at the end of the list. * */ /* * PSEUDO CODE * * Begin make_child * If there are no children for the father node then * Unconditionally make node with given name * Make it the first child of the father node * Else * Look for child in the sibling list * If no child was found during sibling scan then * Make a new node with given name * Scan for end of sibling list * Add the new node at end of sibling list * End if * End if * Return pointer to child node * End make_child * */ static struct node *make_child (np, child) struct node *np; char *child; { register struct node *cnp; /* Child node pointer */ register struct node *sp; /* Sibling list scan pointer */ DBUG_ENTER ("make_child"); DBUG_PRINT ("tree", ("add node \"%s\" under \"%s\"", child, np -> name)); if (np -> child == NULL) { cnp = make_node (child); np -> child = cnp; } else { cnp = find_child (np, child); if (cnp == NULL) { cnp = make_node (child); for (sp = np -> child; sp -> sibling != NULL; sp = sp -> sibling) {;} sp -> sibling = cnp; } } DBUG_RETURN (cnp); } /* * FUNCTION * * make_node make a new node with given name * * SYNOPSIS * * static struct node *make_node (name) * char *name; * * DESCRIPTION * * Allocate and initialize a new node with the given name. * Note that memory for the node and a fresh copy of the name * are obtained from the standard memory allocator. * * Returns pointer to the new node. * */ /* * PSEUDO CODE * * Begin make_node * Increment count of nodes in tree * Allocate memory for the node structure * Allocate memory for copy of name * Copy name to the allocated area * Initialize pointer to child to NULL * Initialize sibling list pointer to NULL * Return pointer to new node * End make_node * */ static struct node *make_node (name) char *name; { register struct node *new; DBUG_ENTER ("make_node"); nnodes++; DBUG_PRINT ("nalloc", ("making node \"%s\", number %d", name, nnodes)); new = (struct node *) get_memory (sizeof (struct node), TRUE); new -> name = (char *) get_memory ((UINT) (s_strlen (name) + 1), TRUE); (VOID) s_strcpy (new -> name, name); new -> child = NULL; new -> sibling = NULL; new -> nflags = 0; DBUG_RETURN (new); } /* * FUNCTION * * find_child find the child node with given name * * SYNOPSIS * * static struct node *find_child (np, name) * struct node *np; * char *name; * * DESCRIPTION * * Given pointer to a father node and pointer to a potential * child name, locates the child node with the given name * and returns it's pointer. * * Returns NULL if no child with the given name. * */ /* * PSEUDO CODE * * Begin find_child * For each child in the child list * If the child node has the desired name then * Break child list scan loop * End if * End for * Return pointer to child found or NULL * End find_child * */ static struct node *find_child (np, name) register struct node *np; register char *name; { DBUG_ENTER ("find_child"); DBUG_PRINT ("tree", ("find child \"%s\"", name)); for (np = np -> child; np != NULL; np = np -> sibling) { if (STRSAME (np -> name, name)) { break; } } DBUG_RETURN (np); } /* * FUNCTION * * tree_walk walk current directory tree executing function * * SYNOPSIS * * VOID tree_walk (funcp) * VOID (*funcp)(); * * DESCRIPTION * * Walks the directory tree in pre-order, executing given function * for each node. Passes an initialized finfo (file info) struct * pointer to the function executed. * */ /* * PSEUDO CODE * * Begin tree_walk * Erase current name in buffer * If there is a tree other than static root node then * Call internal walk function root node's first child * End if * End tree_walk * */ VOID tree_walk (funcp) VOID (*funcp)(); { DBUG_ENTER ("tree_walk"); namebuf[0] = EOS; if (root.child != NULL) { walk_subtree (root.child, funcp, namebuf); } DBUG_VOID_RETURN; } /* * FUNCTION * * walk_subtree call function for single tree node * * SYNOPSIS * * static VOID walk_subtree (np, funcp, cp) * register struct node *np; * VOID (*funcp)(); * char *cp; * * DESCRIPTION * * Given pointer to a tree node (np), a pointer to a * function to execute (funcp), and a pointer to name buffer (cp), * builds a complete pathname from this node's name and * previous stem in pathname buffer, and invokes function * with the complete pathname as the argument. * Then walks any children trees, and finally sibling * trees. * */ /* * PSEUDO CODE * * Begin walk_subtree * If new leaf can be added to end of name then * Find and remember current end of name * If the file is successfully archived then * If there are no children or always expand then * If the file is a directory then * Remember device of explicit directory * Walk subtree rooted in directory * End if * End if * If there is a child node then * Make current name a stem * Walk the child subtree * Rejoin stem with rest of name * End if * End if * Terminate current name * End if * If there are any sibling subtrees then * Walk the next sibling subtree * End if * End walk_subtree * */ static VOID walk_subtree (np, funcp, cp) register struct node *np; VOID (*funcp) (); char *cp; { #ifndef ALMOST_WORKS register char *end; DBUG_ENTER ("walk_subtree"); DBUG_PRINT ("walk", ("stem \"%s\"", namebuf)); DBUG_PRINT ("walk", ("node \"%s\"", np -> name)); if (add_leaf (np -> name, cp)) { STREND (namebuf, end); if (do_it (funcp, FALSE)) { if (np -> child == NULL || EXPAND (np)) { if (IS_DIR (sbuf.st_mode)) { dirdev = sbuf.st_dev; DBUG_PRINT ("dirdev", ("dirdev = %u", dirdev)); do_dir (funcp); } } if (np -> child != NULL) { *end++ = '/'; walk_subtree (np -> child, funcp, end); *--end = '/'; } } *cp = EOS; } if (np -> sibling != NULL) { walk_subtree (np -> sibling, funcp, cp); } DBUG_VOID_RETURN; #else /* * This experimental code is almost sufficient to let us do * our own wild card expansion, as thus also implement leading '!' * for archive creation as well as extraction, as well as not * depending upon the shell for wildcard expansion (for non-unix). * * The problem is the way the tree is stored. When called the * first time with a pathname like "/usr/src/cmd", both namebuf and * np -> are "" (null strings), so no first level match is found. * When the tree manipulation code is cleaned up, or possibly kludged * up a little more, maybe this will work... */ register char *end; register BOOLEAN deof; register DIR *dirp; register long dirpos; auto struct stat64 dsbuf; /* Dummy stat buffer for finfo_init */ auto struct finfo dirf; #ifdef sgi auto struct dirent *dbuf; #else auto struct direct *dbuf; #endif DBUG_ENTER ("walk_subtree"); DBUG_PRINT ("walk", ("stem \"%s\"", namebuf)); DBUG_PRINT ("walk", ("node \"%s\"", np -> name)); finfo_init (&dirf, namebuf, &dsbuf); deof = FALSE; dirpos = 0L; dirp = NULL; if (STRSAME ("", dirf.fname)) { dirf.fname = "."; } DBUG_PRINT ("dirf", ("looking inside directory '%s'", dirf.fname)); while (!deof) { if (dirp == NULL) { if (file_stat (&dirf)) { dirp = s_opendir (dirf.fname); if (dirp == NULL) { bru_error (ERR_OPEN, dirf.fname); } } } if (dirp == NULL) { DBUG_PRINT ("dir", ("dirp == NULL (eof on directory)")); break; } /* * A seek to a saved position immediately after an open should * be ok -- see the man page. If dirp still open (e.g. looping * after a dot file) then for sure the seek will work. * * In any case, seekdir is of type void, so it is impossible to * check its return value like the old code did. */ s_seekdir (dirp, dirpos); if ((dbuf = s_readdir (dirp)) == NULL) { DBUG_PRINT ("dir", ("found eof (readdir returned NULL)")); deof = TRUE; } else if (DOTFILE (dbuf -> d_name)) { DBUG_PRINT ("dir", ("found dotfile \"%s\"", dbuf -> d_name)); } else { if (wild (dbuf -> d_name, np -> name)) { DBUG_PRINT ("dirf", ("process \"%s\"", dbuf -> d_name)); if (add_leaf (dbuf -> d_name, cp)) { STREND (namebuf, end); dirpos = s_telldir (dirp); s_closedir (dirp); dirp = NULL; if (do_it (funcp, FALSE)) { if (np -> child == NULL || EXPAND (np)) { if (IS_DIR (sbuf.st_mode)) { dirdev = sbuf.st_dev; DBUG_PRINT ("dirdev", ("dirdev = %u", dirdev)); do_dir (funcp); } } if (np -> child != NULL) { *end++ = '/'; walk_subtree (np -> child, funcp, end); *--end = '/'; } } *cp = EOS; reset_times (&dirf); } if (np -> sibling != NULL) { walk_subtree (np -> sibling, funcp, cp); } } } if (dirp != NULL) { dirpos = s_telldir (dirp); } } if (dirp != NULL) { s_closedir (dirp); } DBUG_VOID_RETURN; #endif } /* * FUNCTION * * do_it turn control over from tree walk to given function * * SYNOPSIS * * static BOOLEAN do_it (funcp, expanding) * VOID (*funcp) (); * BOOLEAN expanding; * * DESCRIPTION * * Given pointer to a function to execute, and flag indicating * whether we are currently expanding an explicitly named * directory, finishes some bookkeeping and turns control * over to the function to be executed at every node * in the tree. * * Returns TRUE if control was turned over to the function, * FALSE otherwise. * */ /* * PSEUDO CODE * * Begin do_it * Initialize file information structure for node * Default return is FALSE * If the file name is null then * Use root as the name * End if * If the file is accessible for read then * If the file can be stat'd then * If we are not expanding a directory then * Always execute the function when not expanding * Else if excluding remote files and file is remote then * Exclude this file by not calling function * Else if limiting to mounted file system and outside then * Exclude this file by not calling function * Else * No other reason to exclude, so go ahead with function * End if * If found that we were to continue then * Go ahead and execute function * End if * End if * End if * End do_it * */ #include /* for local file check */ static BOOLEAN do_it (funcp, expanding) VOID (*funcp)(); BOOLEAN expanding; { register BOOLEAN rtnval; auto struct finfo file; struct statvfs vfs; DBUG_ENTER ("do_it"); DBUG_PRINT ("tree", ("archive \"%s\"", namebuf)); finfo_init (&file, namebuf, &sbuf); rtnval = FALSE; if (STRSAME ("", file.fname)) { file.fname = "/"; } if (file_access (file.fname, A_READ, TRUE)) { if (file_stat (&file)) { if (!expanding) rtnval = TRUE; else if (flags.mflag && file.statp -> st_dev != dirdev) rtnval = FALSE; else if (flags.Rflag) { if(IS_FLNK(file.statp->st_mode) || (statvfs(file.fname, &vfs) == 0 && (vfs.f_flag&ST_LOCAL))) rtnval = TRUE; else rtnval = FALSE; } else rtnval = TRUE; if (rtnval) (*funcp) (&file); } } DBUG_RETURN (rtnval); } /* * FUNCTION * * do_dir expand a directory * * SYNOPSIS * * static VOID do_dir (funcp) * VOID (*funcp) (); * * DESCRIPTION * * Recursively expands a directory, doing each regular file and * expanding any subdirectories. * * Use the Directory Access routines defined by Berkeley. On non-BSD * systems, the directory stuff will be available from the public * domain version written by Doug Gwyn at BRL. * * The directory access routines do us two favors: * 1) They skip empty directory slots for us (where the inode number is 0) * 2) They automatically EOS terminate the name of the file. * * V.3 NOTE: * System V.3 did away with limits on the name length of a file (at * least as far as you, the poor programmer, is concerned). Thus, * we can't pre-allocate a buffer for the name. I'm not sure why * the original programmer chose to copy the string anyway - if you * look at how it's used, it's never trashed. -- jmb 1/24/88 */ static VOID do_dir (funcp) VOID (*funcp)(); { auto struct stat64 dsbuf; /* Dummy stat buffer for finfo_init */ auto struct finfo file; register char *end; auto struct dirent *dbuf; register DIR *dirp = NULL; DBUG_ENTER ("do_dir"); DBUG_PRINT ("dir", ("archive directory \"%s\"", namebuf)); STREND (namebuf, end); finfo_init (&file, namebuf, &dsbuf); if (STRSAME ("", file.fname)) { file.fname = "/"; } if (file_stat (&file)) { dirp = opendir (file.fname); if (dirp == NULL) bru_error (ERR_OPEN, file.fname); else { while (dbuf = readdir (dirp)) { if(!DOTFILE (dbuf -> d_name)) { DBUG_PRINT ("dir", ("found \"%s\"", dbuf -> d_name)); *end++ = '/'; save_it (dbuf -> d_name, funcp, end); *--end = EOS; reset_times (&file); } } closedir (dirp); } } DBUG_VOID_RETURN; } /* * FUNCTION * * add_leaf add a new pathname component to current pathname * * SYNOPSIS * * static BOOLEAN add_leaf (name, cp) * char *name; * char *cp; * * DESCRIPTION * * If there is room in the name buffer to add the component * pointed to by name then adds the name and returns TRUE. * * If the buffer is too small then notifies user and * returns FALSE. * * Note that the size condition test is such that there * will always be room at the end of the buffer to append * a '/' without another test. * */ static BOOLEAN add_leaf (name, cp) char *name; char *cp; { register BOOLEAN rtnval; DBUG_ENTER ("add_leaf"); if (cp + s_strlen (name) > &namebuf[NAMESIZE - 2]) { rtnval = FALSE; bru_error (ERR_DEPTH, namebuf, name); } else { rtnval = TRUE; (VOID) s_strcpy (cp, name); } DBUG_RETURN (rtnval); } static VOID save_it (name, funcp, cp) char *name; VOID (*funcp) (); char *cp; { DBUG_ENTER ("save_it"); if (add_leaf (name, cp)) { if (do_it (funcp, TRUE)) { if (IS_DIR (sbuf.st_mode)) { do_dir (funcp); } } *cp = EOS; } DBUG_VOID_RETURN; } /* * FUNCTION * * find_type test a path for type * * SYNOPSIS * * static int find_type (np, name) * struct node *np; * char *name; * * DESCRIPTION * * Takes a pointer to a complete pathname, such as "/usr/bin/sh", * and determines its type, NOMATCH, STEM, LEAF, or EXTENSION. * * This is done by splitting the pathname into leading and * trailing components at the first '/' character, looking * for a matching node with the same name as the leading * component, and if found, calling find_type recursively * with the trailing component. The routine "wild" is * called to expand possible pattern matching metacharacters * in the same manner as the shell. * * Returns STEM when the end of the pathname is found * (a null trailing component) without finding a name * mismatch, or reaching a leaf node. * * Returns LEAF when the end of the pathname and a leaf * node are reached simultaneously. * * Returns EXTENSION when a leaf node is reached before the * end of the pathname. * * Returns NOMATCH when any mismatch is found. * * NOTES * * To properly understand the matching algorithm, it is * important to note the following facts: * * (1) Matches are done from the "bottom up". That is * the current path through the tree does not match * the complete pathname given until the bottom of * the tree is reached or the pathname runs out of * components. If a non-match is found at any point, * an alternate path through the tree will be attempted. * Thus a node can only be marked as "matched" if the * result of the current invocation of path_type is * something other than "NOMATCH". * * (2) The current node pointer points to the node which * represents the bottom of the path through the tree * which is a possible match. The following table * represents the current node and unmatched pathname * components when path_type is invoked with the * pathname "a/b/c/d": * * Call number Node Name points to * ----------- ---------- --------------- * * 1 a/b/c/d * 2 a b/c/d * 3 b c/d * 4 c d * 5 d * * Thus the current node pointer always points to the bottom * node of the subtree which represents currently matched * components of the pathname. Subtrees under the current * node represent possible matches for the current name string. * * When picking subtrees to test for matches, the subtree * which has a root node exactly matching the current leading * pathname component is tried first. Then all other subtrees * which have pattern matches are tried. If this fails then * no match is found. * * * (3) Matches cannot be done "top down" because at any node * in the tree, more than one child node may match the * next component, and the "correct" one can only be * found by testing subtrees under each of the possible * child node matches. * */ /* * PSEUDO CODE * * Begin find_type * If current node has no children then * If there is more name left then * Name is extension of tree * Else * Name is leaf of tree * End if * Else * If name has been exhausted then * Name is stem of tree * Else * Locate slash separating components * If there are two components then * Replace slash temporarily with EOS * End if * Default result is no match * Find the child with given name * If child not found then * Result is type of the subtree * End if * If no match yet then * For each child of the node * If not an exact name match then * If child matches pattern then * Type is the type of the subtree * If match found then * Break match loop * End if * End if * End if * End for * End if * If slash was replaced then * Restore it * End if * End if * End if * If result is something other than "no match" then * If this node not yet marked as matched then * Mark it matched * Increment count of nodes matched * End if * End if * Return result * End find_type * */ static int find_type (np, name) struct node *np; char *name; { register int result; register char *sp; register struct node *cp; DBUG_ENTER ("find_type"); DBUG_PRINT ("tree", ("test path \"%s\"", name?name:"")); if (np -> child == NULL) { if (name != NULL) { result = EXTENSION; } else { result = LEAF; } } else { if (name == NULL) { result = STEM; } else { sp = s_strchr (name, '/'); if (sp != NULL) { *sp++ = EOS; } result = NOMATCH; cp = find_child (np, name); if (cp != NULL) { result = find_type (cp, sp); } if (result == NOMATCH) { for (cp = np -> child; cp != NULL; cp = cp -> sibling) { if (!STRSAME (name, cp -> name)) { if (wild (name, cp -> name)) { wildcards = TRUE; result = find_type (cp, sp); if (result != NOMATCH) { break; } } } } } if (sp != NULL) { *--sp = '/'; } } } DBUG_PRINT ("tree", ("result is %d", result)); if (!MATCHED (np)) { DBUG_PRINT ("mnodes", ("node \"%s\" matched", np -> name)); SET_MATCHED (np); nmatched++; } DBUG_RETURN (result); } /* * FUNCTION * * nodes_ignored check tree for any nodes ignored in scan * * SYNOPSIS * * VOID nodes_ignored () * * DESCRIPTION * * Tests to see if there are any tree nodes that have not * been matched. Compares the number of leaf nodes against * the number of matched nodes. If they do not match then * descends the tree in preorder, checking for individual nodes * that have not been matched. * */ VOID nodes_ignored (funcp) VOID (*funcp)(); { DBUG_ENTER ("nodes_ignored"); DBUG_PRINT ("nodes", ("%d nodes, %d matched", nnodes, nmatched)); namebuf[0] = EOS; if (nnodes != nmatched && root.child != NULL) { not_matched (root.child, funcp, namebuf); } DBUG_VOID_RETURN; } /* * FUNCTION * * not_matched (np, funcp, cp) * register struct node *np; * VOID (*funcp) (); * char *cp; * * DESCRIPTION * * Given pointer to a node, pointer to a function to execute if * the node has not been visited, and pointer to a place in the * name buffer where the node's name can be appended to the * current contents, builds the complete pathname in the buffer. * Then tests to see if the node has any children. If so, calls * itself recursively on the child subtree. If not, tests to see * if the node has been matched. If so, calls * the function specified via funcp with the name in the * name buffer. Then recursively checks all sibling subtrees. * * The net effect is that all leaf nodes which have never been * matched result in a call to the specified function with * the full pathname corresponding to the unmatched leaf node. * * Note that the files "." and ".." are treated specially since * they are never archived. Thus if there are leaf nodes * with either name, they are essentially ignored. * */ static VOID not_matched (np, funcp, cp) register struct node *np; VOID (*funcp) (); char *cp; { register char *name; register char *end; DBUG_ENTER ("not_matched"); DBUG_PRINT ("ltest", ("stem \"%s\"", namebuf)); DBUG_PRINT ("ltest", ("node \"%s\"", np -> name)); if (add_leaf (np -> name, cp)) { if (np -> child != NULL) { STREND (namebuf, end); *end++ = '/'; not_matched (np -> child, funcp, end); *--end = '/'; } else { if (!MATCHED (np) && !DOTFILE (namebuf)) { if (STRSAME ("", namebuf)) { name = "/"; } else { name = namebuf; } (*funcp) (name); } } *cp = EOS; } if (np -> sibling != NULL) { not_matched (np -> sibling, funcp, cp); } DBUG_VOID_RETURN; } /* * FUNCTION * * clear_tree reset all match information in tree * * SYNOPSIS * * VOID clear_tree () * * DESCRIPTION * * Is used between archive scans to reset all match information * in the tree so that successive passes can be made over an * archive. It must reset the following items: * * 1. The match bits in the flag word of each node. * 2. The number of nodes matched. * 3. The "wildcard used" flag. * */ VOID clear_tree () { DBUG_ENTER ("clear_tree"); nmatched = 0; wildcards = FALSE; clear_matches (&root); DBUG_VOID_RETURN; } /* * FUNCTION * * clear_matches clear match bits in nodes * * SYNOPSIS * * static VOID clear_matches (np) * struct node *np; * * DESCRIPTION * * Given pointer to a node, clears the match bits in the flag * word of the given node, all child nodes of the given node, * and all sibling nodes of the given node. * */ static VOID clear_matches (np) struct node *np; { DBUG_ENTER ("clear_matches"); RSET_MATCHED (np); if (np -> child != NULL) { clear_matches (np -> child); } if (np -> sibling != NULL) { clear_matches (np -> sibling); } DBUG_VOID_RETURN; }