home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / bsd / src / make / make-amiga / dir.c < prev    next >
C/C++ Source or Header  |  1993-09-23  |  38KB  |  1,238 lines
  1. /*
  2.  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
  3.  * Copyright (c) 1988, 1989 by Adam de Boor
  4.  * Copyright (c) 1989 by Berkeley Softworks
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Adam de Boor.
  9.  *
  10.  * Redistribution and use in source and binary forms, with or without
  11.  * modification, are permitted provided that the following conditions
  12.  * are met:
  13.  * 1. Redistributions of source code must retain the above copyright
  14.  *    notice, this list of conditions and the following disclaimer.
  15.  * 2. Redistributions in binary form must reproduce the above copyright
  16.  *    notice, this list of conditions and the following disclaimer in the
  17.  *    documentation and/or other materials provided with the distribution.
  18.  * 3. All advertising materials mentioning features or use of this software
  19.  *    must display the following acknowledgement:
  20.  *    This product includes software developed by the University of
  21.  *    California, Berkeley and its contributors.
  22.  * 4. Neither the name of the University nor the names of its contributors
  23.  *    may be used to endorse or promote products derived from this software
  24.  *    without specific prior written permission.
  25.  *
  26.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36.  * SUCH DAMAGE.
  37.  */
  38.  
  39. #ifndef lint
  40. static char sccsid[] = "@(#)dir.c    5.6 (Berkeley) 12/28/90";
  41. #endif /* not lint */
  42.  
  43. /*-
  44.  * dir.c --
  45.  *    Directory searching using wildcards and/or normal names...
  46.  *    Used both for source wildcarding in the Makefile and for finding
  47.  *    implicit sources.
  48.  *
  49.  * The interface for this module is:
  50.  *    Dir_Init          Initialize the module.
  51.  *
  52.  *    Dir_HasWildcards    Returns TRUE if the name given it needs to
  53.  *                      be wildcard-expanded.
  54.  *
  55.  *    Dir_Expand        Given a pattern and a path, return a Lst of names
  56.  *                      which match the pattern on the search path.
  57.  *
  58.  *    Dir_FindFile        Searches for a file on a given search path.
  59.  *                      If it exists, the entire path is returned.
  60.  *                      Otherwise NULL is returned.
  61.  *
  62.  *    Dir_MTime         Return the modification time of a node. The file
  63.  *                      is searched for along the default search path.
  64.  *                      The path and mtime fields of the node are filled
  65.  *                      in.
  66.  *
  67.  *    Dir_AddDir        Add a directory to a search path.
  68.  *
  69.  *    Dir_MakeFlags        Given a search path and a command flag, create
  70.  *                      a string with each of the directories in the path
  71.  *                      preceded by the command flag and all of them
  72.  *                      separated by a space.
  73.  *
  74.  *    Dir_Destroy        Destroy an element of a search path. Frees up all
  75.  *                      things that can be freed for the element as long
  76.  *                      as the element is no longer referenced by any other
  77.  *                      search path.
  78.  *    Dir_ClearPath        Resets a search path to the empty list.
  79.  *
  80.  * For debugging:
  81.  *    Dir_PrintDirectories    Print stats about the directory cache.
  82.  */
  83.  
  84. #include <stdio.h>
  85. #include <sys/types.h>
  86. #include <sys/dir.h>
  87. #include <sys/stat.h>
  88. #include "make.h"
  89. #include "hash.h"
  90.  
  91. /*
  92.  *    A search path consists of a Lst of Path structures. A Path structure
  93.  *    has in it the name of the directory and a hash table of all the files
  94.  *    in the directory. This is used to cut down on the number of system
  95.  *    calls necessary to find implicit dependents and their like. Since
  96.  *    these searches are made before any actions are taken, we need not
  97.  *    worry about the directory changing due to creation commands. If this
  98.  *    hampers the style of some makefiles, they must be changed.
  99.  *
  100.  *    A list of all previously-read directories is kept in the
  101.  *    openDirectories Lst. This list is checked first before a directory
  102.  *    is opened.
  103.  *
  104.  *    The need for the caching of whole directories is brought about by
  105.  *    the multi-level transformation code in suff.c, which tends to search
  106.  *    for far more files than regular make does. In the initial
  107.  *    implementation, the amount of time spent performing "stat" calls was
  108.  *    truly astronomical. The problem with hashing at the start is,
  109.  *    of course, that pmake doesn't then detect changes to these directories
  110.  *    during the course of the make. Three possibilities suggest themselves:
  111.  *
  112.  *        1) just use stat to test for a file's existence. As mentioned
  113.  *           above, this is very inefficient due to the number of checks
  114.  *           engendered by the multi-level transformation code.
  115.  *        2) use readdir() and company to search the directories, keeping
  116.  *           them open between checks. I have tried this and while it
  117.  *           didn't slow down the process too much, it could severely
  118.  *           affect the amount of parallelism available as each directory
  119.  *           open would take another file descriptor out of play for
  120.  *           handling I/O for another job. Given that it is only recently
  121.  *           that UNIX OS's have taken to allowing more than 20 or 32
  122.  *           file descriptors for a process, this doesn't seem acceptable
  123.  *           to me.
  124.  *        3) record the mtime of the directory in the Path structure and
  125.  *           verify the directory hasn't changed since the contents were
  126.  *           hashed. This will catch the creation or deletion of files,
  127.  *           but not the updating of files. However, since it is the
  128.  *           creation and deletion that is the problem, this could be
  129.  *           a good thing to do. Unfortunately, if the directory (say ".")
  130.  *           were fairly large and changed fairly frequently, the constant
  131.  *           rehashing could seriously degrade performance. It might be
  132.  *           good in such cases to keep track of the number of rehashes
  133.  *           and if the number goes over a (small) limit, resort to using
  134.  *           stat in its place.
  135.  *
  136.  *    An additional thing to consider is that pmake is used primarily
  137.  *    to create C programs and until recently pcc-based compilers refused
  138.  *    to allow you to specify where the resulting object file should be
  139.  *    placed. This forced all objects to be created in the current
  140.  *    directory. This isn't meant as a full excuse, just an explanation of
  141.  *    some of the reasons for the caching used here.
  142.  *
  143.  *    One more note: the location of a target's file is only performed
  144.  *    on the downward traversal of the graph and then only for terminal
  145.  *    nodes in the graph. This could be construed as wrong in some cases,
  146.  *    but prevents inadvertent modification of files when the "installed"
  147.  *    directory for a file is provided in the search path.
  148.  *
  149.  *    Another data structure maintained by this module is an mtime
  150.  *    cache used when the searching of cached directories fails to find
  151.  *    a file. In the past, Dir_FindFile would simply perform an access()
  152.  *    call in such a case to determine if the file could be found using
  153.  *    just the name given. When this hit, however, all that was gained
  154.  *    was the knowledge that the file existed. Given that an access() is
  155.  *    essentially a stat() without the copyout() call, and that the same
  156.  *    filesystem overhead would have to be incurred in Dir_MTime, it made
  157.  *    sense to replace the access() with a stat() and record the mtime
  158.  *    in a cache for when Dir_MTime was actually called.
  159.  */
  160.  
  161. Lst          dirSearchPath;    /* main search path */
  162.  
  163. static Lst   openDirectories;    /* the list of all open directories */
  164.  
  165. /*
  166.  * Variables for gathering statistics on the efficiency of the hashing
  167.  * mechanism.
  168.  */
  169. static int    hits,          /* Found in directory cache */
  170.           misses,          /* Sad, but not evil misses */
  171.           nearmisses,     /* Found under search path */
  172.           bigmisse