home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / octa21fs.zip / octave / kpathsea / db.c < prev    next >
C/C++ Source or Header  |  2000-01-15  |  18KB  |  530 lines
  1. /* db.c: an external database to avoid filesystem lookups.
  2.  
  3. Copyright (C) 1994, 95, 96, 97 Karl Berry.
  4.  
  5. This library is free software; you can redistribute it and/or
  6. modify it under the terms of the GNU Library General Public
  7. License as published by the Free Software Foundation; either
  8. version 2 of the License, or (at your option) any later version.
  9.  
  10. This library 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 GNU
  13. Library General Public License for more details.
  14.  
  15. You should have received a copy of the GNU Library General Public
  16. License along with this library; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  18.  
  19. /* Modified by Klaus Gebhardt, 1999 */
  20.  
  21. #include <kpathsea/config.h>
  22. #include <kpathsea/absolute.h>
  23. #include <kpathsea/c-fopen.h>
  24. #include <kpathsea/c-pathch.h>
  25. #include <kpathsea/db.h>
  26. #include <kpathsea/hash.h>
  27. #include <kpathsea/line.h>
  28. #include <kpathsea/pathsearch.h>
  29. #include <kpathsea/readable.h>
  30. #include <kpathsea/str-list.h>
  31. #include <kpathsea/tex-file.h>
  32. #include <kpathsea/variable.h>
  33.  
  34. static hash_table_type db; /* The hash table for all the ls-R's.  */
  35. /* SMALL: The old size of the hash table was 7603, with the assumption
  36.    that a minimal ls-R bas about 3500 entries.  But a typical ls-R will
  37.    be more like double that size.  */
  38. #ifndef DB_HASH_SIZE
  39. #define DB_HASH_SIZE 15991
  40. #endif
  41. #ifndef DB_NAME
  42. #define DB_NAME "ls-R"
  43. #endif
  44.  
  45. static hash_table_type alias_db;
  46. #ifndef ALIAS_NAME
  47. #define ALIAS_NAME "aliases"
  48. #endif
  49. #ifndef ALIAS_HASH_SIZE
  50. #define ALIAS_HASH_SIZE 1009
  51. #endif
  52.  
  53. static str_list_type db_dir_list;
  54.  
  55. /* If DIRNAME contains any element beginning with a `.' (that is more
  56.    than just `./'), return true.  This is to allow ``hidden''
  57.    directories -- ones that don't get searched.  */
  58.  
  59. static boolean
  60. ignore_dir_p P1C(const_string, dirname)
  61. {
  62.   const_string dot_pos = dirname;
  63.   
  64.   while ((dot_pos = strchr (dot_pos + 1, '.'))) {
  65.     /* If / before and no / after, skip it. */
  66.     if (IS_DIR_SEP (dot_pos[-1]) && dot_pos[1] && !IS_DIR_SEP (dot_pos[1]))
  67.       return true;
  68.   }
  69.   
  70.   return false;
  71. }
  72.  
  73. /* If no DB_FILENAME, return false (maybe they aren't using this feature).
  74.    Otherwise, add entries from DB_FILENAME to TABLE, and return true.  */
  75.  
  76. static boolean
  77. db_build P2C(hash_table_type *, table,  const_string, db_filename)
  78. {
  79.   string line;
  80.   unsigned dir_count = 0, file_count = 0, ignore_dir_count = 0;
  81.   unsigned len = strlen (db_filename) - sizeof (DB_NAME) + 1; /* Keep the /. */
  82.   string top_dir = xmalloc (len + 1);
  83.   string cur_dir = NULL; /* First thing in ls-R might be a filename.  */
  84.   FILE *db_file = fopen (db_filename, FOPEN_R_MODE);
  85.   
  86.   strncpy (top_dir, db_filename, len);
  87.   top_dir[len] = 0;
  88.   
  89.   if (db_file) {
  90.     while ((line = read_line (db_file)) != NULL) {
  91.       len = strlen (line);
  92.  
  93.       /* A line like `/foo:' = new dir foo.  Allow both absolute (/...)
  94.          and explicitly relative (./...) names here.  It's a kludge to
  95.          pass in the directory name with the trailing : still attached,
  96.          but it doesn't actually hurt.  */
  97.       if (len > 0 && line[len - 1] == ':' && kpse_absolute_p (line, true)) {
  98.         /* New directory line.  */
  99.         if (!ignore_dir_p (line)) {
  100.           /* If they gave a relative name, prepend full directory name now.  */
  101.           line[len - 1] = DIR_SEP;
  102.           /* Skip over leading `./', it confuses `match' and is just a
  103.              waste of space, anyway.  This will lose on `../', but `match'
  104.              won't work there, either, so it doesn't matter.  */
  105.           cur_dir = *line == '.' ? concat (top_dir, line + 2) : xstrdup (line);
  106.           dir_count++;
  107.         } else {
  108.           cur_dir = NULL;
  109.           ignore_dir_count++;
  110.         }
  111.  
  112.       /* Ignore blank, `.' and `..' lines.  */
  113.       } else if (*line != 0 && cur_dir   /* a file line? */
  114.                  && !(*line == '.'
  115.                       && (line[1] == '0' || (line[1] == '.' && line[2] == 0))))
  116.        {/* Make a new hash table entry with a key of `line' and a data
  117.            of `cur_dir'.  An already-existing identical key is ok, since
  118.            a file named `foo' can be in more than one directory.  Share
  119.            `cur_dir' among all its files (and hence never free it). */
  120.         hash_insert (table, xstrdup (line), cur_dir);
  121.         file_count++;
  122.  
  123.       } /* else ignore blank lines or top-level files
  124.            or files in ignored directories*/
  125.  
  126.       free (line);
  127.     }
  128.  
  129.     xfclose (db_file, db_filename);
  130.  
  131.     if (file_count == 0) {
  132.       WARNING1 ("kpathsea: No usable entries in %s", db_filename);
  133.       WARNING ("kpathsea: See the manual for how to generate ls-R");
  134.       db_file = NULL;
  135.     } else {
  136.       str_list_add (&db_dir_list, xstrdup (top_dir));
  137.     }
  138.  
  139. #ifdef KPSE_DEBUG
  140.     if (KPSE_DEBUG_P (KPSE_DEBUG_HASH)) {
  141.       /* Don't make this a debugging bit, since the output is so
  142.          voluminous, and being able to specify -1 is too useful.
  143.          Instead, let people who want it run the program under
  144.          a debugger and change the variable that way.  */
  145.       boolean hash_summary_only = true;
  146.  
  147.       DEBUGF4 ("%s: %u entries in %d directories (%d hidden).\n",
  148.                db_filename, file_count, dir_count, ignore_dir_count);
  149.       DEBUGF ("ls-R hash table:");
  150.       hash_print (*table, hash_summary_only);
  151.       fflush (stderr);
  152.     }
  153. #endif /* KPSE_DEBUG */
  154.   }
  155.  
  156.   free (top_dir);
  157.  
  158.   return db_file != NULL;
  159. }
  160.  
  161.  
  162. /* Insert FNAME into the hash table.  This is for files that get built
  163.    during a run.  We wouldn't want to reread all of ls-R, even if it got
  164.    rebuilt.  */
  165.  
  166. void
  167. kpse_db_insert P1C(const_string, passed_fname)
  168. {
  169.   /* We might not have found ls-R, or even had occasion to look for it
  170.      yet, so do nothing if we have no hash table.  */
  171.   if (db.buckets) {
  172.     const_string dir_part;
  173.     string fname = xstrdup (passed_fname);
  174.     string baseptr = (string)basename (fname);
  175.     const_string file_part = xstrdup (baseptr);
  176.  
  177.     *baseptr = '\0';  /* Chop off the filename.  */
  178.     dir_part = fname; /* That leaves the dir, with the trailing /.  */
  179.  
  180.     hash_insert (&db, file_part, dir_part);
  181.   }
  182. }
  183.  
  184. /* Return true if FILENAME could be in PATH_ELT, i.e., if the directory
  185.    part of FILENAME matches PATH_ELT.  Have to consider // wildcards, but
  186.    $ and ~ expansion have already been done.  */
  187.      
  188. static boolean
  189. match P2C(const_string, filename,  const_string, path_elt)
  190. {
  191.   const_string original_filename = filename;
  192.   boolean matched = false;
  193.   
  194.   for (; *filename && *path_elt; filename++, path_elt++) {
  195.     if (FILECHARCASEEQ (*filename, *path_elt)) /* normal character match */
  196.       ;
  197.  
  198.     else if (IS_DIR_SEP (*path_elt)  /* at // */
  199.              && original_filename < filename && IS_DIR_SEP (path_elt[-1])) {
  200.       while (IS_DIR_SEP (*path_elt))
  201.         path_elt++; /* get past second and any subsequent /'s */
  202.       if (*path_elt == 0) {
  203.         /* Trailing //, matches anything. We could make this part of the
  204.            other case, but it seems pointless to do the extra work.  */
  205.         matched = true;
  206.         break;
  207.       } else {
  208.         /* Intermediate //, have to match rest of PATH_ELT.  */
  209.         for (; !matched && *filename; filename++) {
  210.           /* Try matching at each possible character.  */
  211.           if (IS_DIR_SEP (filename[-1])
  212.               && FILECHARCASEEQ (*filename, *path_elt))
  213.             matched = match (filename, path_elt);
  214.         }
  215.         /* Prevent filename++ when *filename='\0'. */
  216.         break;
  217.       }
  218.     }
  219.  
  220.     else /* normal character nonmatch, quit */
  221.       break;
  222.   }
  223.   
  224.   /* If we've reached the end of PATH_ELT, check that we're at the last
  225.      component of FILENAME, we've matched.  */
  226.   if (!matched && *path_elt == 0) {
  227.     /* Probably PATH_ELT ended with `vf' or some such, and FILENAME ends
  228.        with `vf/ptmr.vf'.  In that case, we'll be at a directory
  229.        separator.  On the other hand, if PATH_ELT ended with a / (as in
  230.        `vf/'), FILENAME being the same `vf/ptmr.vf', we'll be at the
  231.        `p'.  Upshot: if we're at a dir separator in FILENAME, skip it.
  232.        But if not, that's ok, as long as there are no more dir separators.  */
  233.     if (IS_DIR_SEP (*filename))
  234.       filename++;
  235.       
  236.     while (*filename && !IS_DIR_SEP (*filename))
  237.       filename++;
  238.     matched = *filename == 0;
  239.   }
  240.   
  241.   return matched;
  242. }
  243.  
  244.  
  245. /* If DB_DIR is a prefix of PATH_ELT, return true; otherwise false.
  246.    That is, the question is whether to try the db for a file looked up
  247.    in PATH_ELT.  If PATH_ELT == ".", for example, the answer is no. If
  248.    PATH_ELT == "/usr/local/lib/texmf/fonts//tfm", the answer is yes.
  249.    
  250.    In practice, ls-R is only needed for lengthy subdirectory
  251.    comparisons, but there's no gain to checking PATH_ELT to see if it is
  252.    a subdir match, since the only way to do that is to do a string
  253.    search in it, which is all we do anyway.  */
  254.    
  255. static boolean
  256. elt_in_db P2C(const_string, db_dir,  const_string, path_elt)
  257. {
  258.   boolean found = false;
  259.  
  260.   while (!found && FILECHARCASEEQ (*db_dir++, *path_elt++)) {
  261.     /* If we've matched the entire db directory, it's good.  */
  262.     if (*db_dir == 0)
  263.       found = true;
  264.  
  265.     /* If we've reached the end of PATH_ELT, but not the end of the db
  266.        directory, it's no good.  */
  267.     else if (*path_elt == 0)
  268.       break;
  269.   }
  270.  
  271.   return found;
  272. }
  273.  
  274. /* If ALIAS_FILENAME exists, read it into TABLE.  */
  275.  
  276. static boolean
  277. alias_build P2C(hash_table_type *, table,  const_string, alias_filename)
  278. {
  279.   string line, real, alias;
  280.   unsigned count = 0;
  281.   FILE *alias_file = fopen (alias_filename, FOPEN_R_MODE);
  282.  
  283.   if (alias_file) {
  284.     while ((line = read_line (alias_file)) != NULL) {
  285.       /* comments or empty */
  286.       if (*line == 0 || *line == '%' || *line == '#') {
  287.         ;
  288.       } else {
  289.         /* Each line should have two fields: realname aliasname.  */
  290.         real = line;
  291.         while (*real && ISSPACE (*real))
  292.           real++;
  293.         alias = real;
  294.         while (*alias && !ISSPACE (*alias))
  295.           alias++;
  296.         *alias++ = 0;
  297.         while (*alias && ISSPACE (*alias)) 
  298.           alias++;
  299.         /* Is the check for errors strong enough?  Should we warn the user
  300.            for potential errors?  */
  301.         if (strlen (real) != 0 && strlen (alias) != 0) {
  302.           hash_insert (table, xstrdup (alias), xstrdup (real));
  303.           count++;
  304.         }
  305.       }
  306.       free (line);
  307.     }
  308.  
  309. #ifdef KPSE_DEBUG
  310.     if (KPSE_DEBUG_P (KPSE_DEBUG_HASH)) {
  311.       /* As with ls-R above ... */
  312.       boolean hash_summary_only = true;
  313.       DEBUGF2 ("%s: %u aliases.\n", alias_filename, count);
  314.       DEBUGF ("alias hash table:");
  315.       hash_print (*table, hash_summary_only);
  316.       fflush (stderr);
  317.     }
  318. #endif /* KPSE_DEBUG */
  319.  
  320.     xfclose (alias_file, alias_filename);
  321.   }
  322.  
  323.   return alias_file != NULL;
  324. }
  325.  
  326. /* Initialize the path for ls-R files, and read them all into the hash
  327.    table `db'.  If no usable ls-R's are found, set db.buckets to NULL.  */
  328.  
  329. void
  330. kpse_init_db P1H(void)
  331. {
  332.   boolean ok = false;
  333.   const_string db_path = kpse_init_format (kpse_db_format);
  334.   string *db_files = kpse_all_path_search (db_path, DB_NAME);
  335.   string *orig_db_files = db_files;
  336.  
  337.   /* Must do this after the path searching (which ends up calling
  338.     kpse_db_search recursively), so db.buckets stays NULL.  */
  339.   db = hash_create (DB_HASH_SIZE);
  340.  
  341.   while (db_files && *db_files) {
  342.     if (db_build (&db, *db_files))
  343.       ok = true;
  344.     free (*db_files);
  345.     db_files++;
  346.   }
  347.   
  348.   if (!ok) {
  349.     /* If db can't be built, leave `size' nonzero (so we don't
  350.        rebuild it), but clear `buckets' (so we don't look in it).  */
  351.     free (db.buckets);
  352.     db.buckets = NULL;
  353.   }
  354.  
  355.   free (orig_db_files);
  356.  
  357.   /* Add the content of any alias databases.  There may exist more than
  358.      one alias file along DB_NAME files.  This duplicates the above code
  359.      -- should be a function.  */
  360.   ok = false;
  361.   db_files = kpse_all_path_search (db_path, ALIAS_NAME);
  362.   orig_db_files = db_files;
  363.  
  364.   alias_db = hash_create (ALIAS_HASH_SIZE);
  365.  
  366.   while (db_files && *db_files) {
  367.     if (alias_build (&alias_db, *db_files))
  368.       ok = true;
  369.     free (*db_files);
  370.     db_files++;
  371.   }
  372.  
  373.   if (!ok) {
  374.     free (alias_db.buckets);
  375.     alias_db.buckets = NULL;
  376.   }
  377.  
  378.   free (orig_db_files);
  379. }
  380.  
  381. /* Avoid doing anything if this PATH_ELT is irrelevant to the databases. */
  382.  
  383. str_list_type *
  384. kpse_db_search P3C(const_string, name,  const_string, orig_path_elt,
  385.                    boolean, all)
  386. {
  387.   string *db_dirs, *orig_dirs, *r;
  388.   const_string last_slash;
  389.   string path_elt;
  390.   boolean done;
  391. #ifdef __EMX__
  392.   str_list_type *ret = NULL;
  393. #else
  394.   str_list_type *ret;
  395. #endif
  396.   unsigned e;
  397.   string *aliases = NULL;
  398.   boolean relevant = false;
  399.   
  400.   /* If we failed to build the database (or if this is the recursive
  401.      call to build the db path), quit.  */
  402.   if (db.buckets == NULL)
  403.     return NULL;
  404.   
  405.   /* When tex-glyph.c calls us looking for, e.g., dpi600/cmr10.pk, we
  406.      won't find it unless we change NAME to just `cmr10.pk' and append
  407.      `/dpi600' to PATH_ELT.  We are justified in using a literal `/'
  408.      here, since that's what tex-glyph.c unconditionally uses in
  409.      DPI_BITMAP_SPEC.  But don't do anything if the / begins NAME; that
  410.      should never happen.  */
  411.   last_slash = strrchr (name, '/');
  412.   if (last_slash && last_slash != name) {
  413.     unsigned len = last_slash - name + 1;
  414.     string dir_part = xmalloc (len);
  415.     strncpy (dir_part, name, len - 1);
  416.     dir_part[len - 1] = 0;
  417.     path_elt = concat3 (orig_path_elt, "/", dir_part);
  418.     name = last_slash + 1;
  419.   } else
  420.     path_elt = (string) orig_path_elt;
  421.  
  422.   /* Don't bother doing any lookups if this `path_elt' isn't covered by
  423.      any of database directories.  We do this not so much because the
  424.      extra couple of hash lookups matter -- they don't -- but rather
  425.      because we want to return NULL in this case, so path_search can
  426.      know to do a disk search.  */
  427.   for (e = 0; !relevant && e < STR_LIST_LENGTH (db_dir_list); e++) {
  428.     relevant = elt_in_db (STR_LIST_ELT (db_dir_list, e), path_elt);
  429.   }
  430.   if (!relevant)
  431.     return NULL;
  432.  
  433.   /* If we have aliases for this name, use them.  */
  434.   if (alias_db.buckets)
  435.     aliases = hash_lookup (alias_db, name);
  436.  
  437.   if (!aliases) {
  438.     aliases = XTALLOC1 (string);
  439.     aliases[0] = NULL;
  440.   }
  441.   {  /* Push aliases up by one and insert the original name at the front.  */
  442.     unsigned i;
  443.     unsigned len = 1; /* Have NULL element already allocated.  */
  444.     for (r = aliases; *r; r++)
  445.       len++;
  446.     XRETALLOC (aliases, len + 1, string);
  447.     for (i = len; i > 0; i--) {
  448.       aliases[i] = aliases[i - 1];
  449.     }
  450.     aliases[0] = (string) name;
  451.   }
  452.  
  453.   done = false;
  454.   for (r = aliases; !done && *r; r++) {
  455.     string try = *r;
  456.  
  457.     /* We have an ls-R db.  Look up `try'.  */
  458.     orig_dirs = db_dirs = hash_lookup (db, try);
  459.  
  460.     ret = XTALLOC1 (str_list_type);
  461.     *ret = str_list_init ();
  462.  
  463.     /* For each filename found, see if it matches the path element.  For
  464.        example, if we have .../cx/cmr10.300pk and .../ricoh/cmr10.300pk,
  465.        and the path looks like .../cx, we don't want the ricoh file.  */
  466.     while (!done && db_dirs && *db_dirs) {
  467.       string db_file = concat (*db_dirs, try);
  468.       boolean matched = match (db_file, path_elt);
  469.  
  470. #ifdef KPSE_DEBUG
  471.       if (KPSE_DEBUG_P (KPSE_DEBUG_SEARCH))
  472.         DEBUGF3 ("db:match(%s,%s) = %d\n", db_file, path_elt, matched);
  473. #endif
  474.  
  475.       /* We got a hit in the database.  Now see if the file actually
  476.          exists, possibly under an alias.  */
  477.       if (matched) {
  478.         string found = NULL;
  479.         if (kpse_readable_file (db_file)) {
  480.           found = db_file;
  481.           
  482.         } else {
  483.           string *a;
  484.           
  485.           free (db_file); /* `db_file' wasn't on disk.  */
  486.           
  487.           /* The hit in the DB doesn't exist in disk.  Now try all its
  488.              aliases.  For example, suppose we have a hierarchy on CD,
  489.              thus `mf.bas', but ls-R contains `mf.base'.  Find it anyway.
  490.              Could probably work around this with aliases, but
  491.              this is pretty easy and shouldn't hurt.  The upshot is that
  492.              if one of the aliases actually exists, we use that.  */
  493.           for (a = aliases + 1; *a && !found; a++) {
  494.             string atry = concat (*db_dirs, *a);
  495.             if (kpse_readable_file (atry))
  496.               found = atry;
  497.             else
  498.               free (atry);
  499.           }
  500.         }
  501.           
  502.         /* If we have a real file, add it to the list, maybe done.  */
  503.         if (found) {
  504.           str_list_add (ret, found);
  505.           if (!all && found)
  506.             done = true;
  507.         }
  508.       } else { /* no match in the db */
  509.         free (db_file);
  510.       }
  511.       
  512.  
  513.       /* On to the next directory, if any.  */
  514.       db_dirs++;
  515.     }
  516.  
  517.     /* This is just the space for the pointers, not the strings.  */
  518.     if (orig_dirs && *orig_dirs)
  519.       free (orig_dirs);
  520.   }
  521.   
  522.   free (aliases);
  523.   
  524.   /* If we had to break up NAME, free the temporary PATH_ELT.  */
  525.   if (path_elt != orig_path_elt)
  526.     free (path_elt);
  527.  
  528.   return ret;
  529. }
  530.