home *** CD-ROM | disk | FTP | other *** search
/ Mega Top 1 / os2_top1.zip / os2_top1 / APPS / TEKST / GROFFSRC / SRC / LIBBIB / INDEX.CC < prev    next >
Encoding:
C/C++ Source or Header  |  1994-01-03  |  16.3 KB  |  616 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21. #include <stdio.h>
  22. #include <io.h>
  23. #include <string.h>
  24. #include <stdlib.h>
  25. #include <errno.h>
  26.  
  27. #include "posix.h"
  28. #include "lib.h"
  29. #include "cset.h"
  30. #include "cmap.h"
  31. #include "errarg.h"
  32. #include "error.h"
  33.  
  34. #include "refid.h"
  35. #include "search.h"
  36. #include "index.h"
  37. #include "defs.h"
  38.  
  39. // Interface to mmap.
  40. extern "C" {
  41.   void *mapread(int fd, int len);
  42.   int unmap(void *, int len);
  43. }
  44.  
  45. const int minus_one = -1;
  46.  
  47. int verify_flag = 0;
  48.  
  49. struct word_list;
  50.  
  51. class index_search_item : public search_item {
  52.   search_item *out_of_date_files;
  53.   index_header header;
  54.   char *buffer;
  55.   void *map_addr;
  56.   int map_len;
  57.   tag *tags;
  58.   int *table;
  59.   int *lists;
  60.   char *pool;
  61.   char *key_buffer;
  62.   char *filename_buffer;
  63.   int filename_buflen;
  64.   char **common_words_table;
  65.   int common_words_table_size;
  66.   const char *ignore_fields;
  67.   time_t mtime;
  68.  
  69.   const char *do_verify();
  70.   const int *search1(const char **pp, const char *end);
  71.   const int *search(const char *ptr, int length, int **temp_listp);
  72.   const char *munge_filename(const char *);
  73.   void read_common_words_file();
  74.   void add_out_of_date_file(int fd, const char *filename, int fid);
  75. public:
  76.   index_search_item(const char *, int);
  77.   ~index_search_item();
  78.   int load(int fd);
  79.   search_item_iterator *make_search_item_iterator(const char *);
  80.   int verify();
  81.   void check_files();
  82.   int next_filename_id() const;
  83.   friend class index_search_item_iterator;
  84. };
  85.  
  86. class index_search_item_iterator : public search_item_iterator {
  87.   index_search_item *indx;
  88.   search_item_iterator *out_of_date_files_iter;
  89.   search_item *next_out_of_date_file;
  90.   const int *found_list;
  91.   int *temp_list;
  92.   char *buf;
  93.   int buflen;
  94.   linear_searcher searcher;
  95.   char *query;
  96.   int get_tag(int tagno, const linear_searcher &, const char **, int *,
  97.           reference_id *);
  98. public:
  99.   index_search_item_iterator(index_search_item *, const char *);
  100.   ~index_search_item_iterator();
  101.   int next(const linear_searcher &, const char **, int *, reference_id *);
  102. };
  103.  
  104.  
  105. index_search_item::index_search_item(const char *filename, int fid)
  106. : search_item(filename, fid), out_of_date_files(0), key_buffer(0),
  107.   filename_buffer(0), filename_buflen(0), common_words_table(0),
  108.   map_addr(0), map_len(0), buffer(0)
  109. {
  110. }
  111.  
  112. index_search_item::~index_search_item()
  113. {
  114.   if (buffer)
  115.     free(buffer);
  116.   if (map_addr) {
  117.     if (unmap(map_addr, map_len) < 0)
  118.       error("unmap: %1", strerror(errno));
  119.   }
  120.   while (out_of_date_files) {
  121.     search_item *tem = out_of_date_files;
  122.     out_of_date_files = out_of_date_files->next;
  123.     delete tem;
  124.   }
  125.   a_delete filename_buffer;
  126.   a_delete key_buffer;
  127.   if (common_words_table) {
  128.     for (int i = 0; i < common_words_table_size; i++)
  129.       a_delete common_words_table[i];
  130.     a_delete common_words_table;
  131.   }
  132. }
  133.  
  134. class file_closer {
  135.   int *fdp;
  136. public:
  137.   file_closer(int &fd) : fdp(&fd) { }
  138.   ~file_closer() { close(*fdp); }
  139. };
  140.   
  141. int index_search_item::load(int fd)
  142. {
  143.   file_closer fd_closer(fd);    // close fd on return
  144.   struct stat sb;
  145.   if (fstat(fd, &sb) < 0) {
  146.     error("can't fstat `%1': %2", name, strerror(errno));
  147.     return 0;
  148.   }
  149.   if (!S_ISREG(sb.st_mode)) {
  150.     error("`%1' is not a regular file", name);
  151.     return 0;
  152.   }
  153.   mtime = sb.st_mtime;
  154.   int size = int(sb.st_size);
  155.   char *addr;
  156.   map_addr = mapread(fd, size);
  157.   if (map_addr) {
  158.     addr = (char *)map_addr;
  159.     map_len = size;
  160.   }
  161.   else {
  162.     addr = buffer = (char *)malloc(size);
  163.     if (buffer == 0) {
  164.       error("can't allocate buffer for `%1'", name);
  165.       return 0;
  166.     }
  167.     char *ptr = buffer;
  168.     int bytes_to_read = size;
  169.     while (bytes_to_read > 0) {
  170.       int nread = read(fd, ptr, bytes_to_read);
  171.       if (nread == 0) {
  172.     error("unexpected EOF on `%1'", name);
  173.     return 0;
  174.       }
  175.       if (nread < 0) {
  176.     error("read error on `%1': %2", name, strerror(errno));
  177.     return 0;
  178.       }
  179.       bytes_to_read -= nread;
  180.       ptr += nread;
  181.     }
  182.   }
  183.   header = *(index_header *)addr;
  184.   if (header.magic != INDEX_MAGIC) {
  185.     error("`%1' is not an index file: wrong magic number", name);
  186.     return 0;
  187.   }
  188.   if (header.version != INDEX_VERSION) {
  189.     error("version number in `%1' is wrong: was %2, should be %3",
  190.       name, header.version, INDEX_VERSION);
  191.     return 0;
  192.   }
  193.   int sz = (header.tags_size * sizeof(tag)
  194.         + header.lists_size * sizeof(int)
  195.         + header.table_size * sizeof(int)
  196.         + header.strings_size
  197.         + sizeof(header));
  198.   if (sz != size) {
  199.     error("size of `%1' is wrong: was %2, should be %3",
  200.       name, size, sz);
  201.     return 0;
  202.   }
  203.   tags = (tag *)(addr + sizeof(header));
  204.   lists = (int *)(tags + header.tags_size);
  205.   table = (int *)(lists + header.lists_size);
  206.   pool = (char *)(table + header.table_size);
  207.   ignore_fields = strchr(strchr(pool, '\0') + 1, '\0') + 1;
  208.   key_buffer = new char[header.truncate];
  209.   read_common_words_file();
  210.   return 1;
  211. }
  212.  
  213. const char *index_search_item::do_verify()
  214. {
  215.   if (tags == 0)
  216.     return "not loaded";
  217.   if (lists[header.lists_size - 1] >= 0)
  218.     return "last list element not negative";
  219.   int i;
  220.   for (i = 0; i < header.table_size; i++) {
  221.     int li = table[i];
  222.     if (li >= header.lists_size)
  223.       return "bad list index";
  224.     if (li >= 0) {
  225.       for (int *ptr = lists + li; *ptr >= 0; ptr++) {
  226.     if (*ptr >= header.tags_size)
  227.       return "bad tag index";
  228.     if (*ptr >= ptr[1] && ptr[1] >= 0)
  229.       return "list not ordered";
  230.       }
  231.     }
  232.   }
  233.   for (i = 0; i < header.tags_size; i++) {
  234.     if (tags[i].filename_index >= header.strings_size)
  235.       return "bad index in tags";
  236.     if (tags[i].length < 0)
  237.       return "bad length in tags";
  238.     if (tags[i].start < 0)
  239.       return "bad start in tags";
  240.   }
  241.   if (pool[header.strings_size - 1] != '\0')
  242.     return "last character in pool not nul";
  243.   return 0;
  244. }
  245.  
  246. int index_search_item::verify()
  247. {
  248.   const char *reason = do_verify();
  249.   if (!reason)
  250.     return 1;
  251.   error("`%1' is bad: %2", name, reason);
  252.   return 0;
  253. }
  254.  
  255. int index_search_item::next_filename_id() const
  256. {
  257.   return filename_id + header.strings_size + 1;
  258. }
  259.  
  260. search_item_iterator *index_search_item::make_search_item_iterator(
  261.   const char *query)
  262. {
  263.   return new index_search_item_iterator(this, query);
  264. }
  265.  
  266. search_item *make_index_search_item(const char *filename, int fid)
  267. {
  268.   char *index_filename = new char[strlen(filename) + sizeof(INDEX_SUFFIX)];
  269.   strcpy(index_filename, filename);
  270.   strcat(index_filename, INDEX_SUFFIX);
  271.   int fd = open(index_filename, O_RDONLY);
  272.   if (fd < 0)
  273.     return 0;
  274.   index_search_item *item = new index_search_item(index_filename, fid);
  275.   a_delete index_filename;
  276.   if (!item->load(fd)) {
  277.     close(fd);
  278.     delete item;
  279.     return 0;
  280.   }
  281.   else if (verify_flag && !item->verify()) {
  282.     delete item;
  283.     return 0;
  284.   }
  285.   else {
  286.     item->check_files();
  287.     return item;
  288.   }
  289. }
  290.  
  291.  
  292. index_search_item_iterator::index_search_item_iterator(index_search_item *ind,
  293.                                const char *q)
  294. : indx(ind), buf(0), buflen(0), temp_list(0), query(strsave(q)),
  295.   searcher(q, strlen(q), ind->ignore_fields, ind->header.truncate),
  296.   out_of_date_files_iter(0), next_out_of_date_file(0)
  297. {
  298.   found_list = indx->search(q, strlen(q), &temp_list);
  299.   if (!found_list) {
  300.     found_list = &minus_one;
  301.     warning("all keys would have been discarded in constructing index `%1'",
  302.         indx->name);
  303.   }
  304. }
  305.  
  306. index_search_item_iterator::~index_search_item_iterator()
  307. {
  308.   a_delete temp_list;
  309.   a_delete buf;
  310.   a_delete query;
  311.   delete out_of_date_files_iter;
  312. }
  313.  
  314. int index_search_item_iterator::next(const linear_searcher &,
  315.                      const char **pp, int *lenp,
  316.                      reference_id *ridp)
  317. {
  318.   if (found_list) {
  319.     for (;;) {
  320.       int tagno = *found_list;
  321.       if (tagno == -1)
  322.     break;
  323.       found_list++;
  324.       if (get_tag(tagno, searcher, pp, lenp, ridp))
  325.     return 1;
  326.     }
  327.     found_list = 0;
  328.     next_out_of_date_file = indx->out_of_date_files;
  329.   }
  330.   while (next_out_of_date_file) {
  331.     if (out_of_date_files_iter == 0)
  332.       out_of_date_files_iter
  333.     = next_out_of_date_file->make_search_item_iterator(query);
  334.     if (out_of_date_files_iter->next(searcher, pp, lenp, ridp))
  335.       return 1;
  336.     delete out_of_date_files_iter;
  337.     out_of_date_files_iter = 0;
  338.     next_out_of_date_file = next_out_of_date_file->next;
  339.   }
  340.   return 0;
  341. }
  342.  
  343. int index_search_item_iterator::get_tag(int tagno,
  344.                     const linear_searcher &searcher,
  345.                     const char **pp, int *lenp,
  346.                     reference_id *ridp)
  347. {
  348.   if (tagno < 0 || tagno >= indx->header.tags_size) {
  349.     error("bad tag number");
  350.     return 0;
  351.   }
  352.   tag *tp = indx->tags + tagno;
  353.   const char *filename = indx->munge_filename(indx->pool + tp->filename_index);
  354.   int fd = open(filename, O_RDONLY);
  355.   if (fd < 0) {
  356.     error("can't open `%1': %2", filename, strerror(errno));
  357.     return 0;
  358.   }
  359.   struct stat sb;
  360.   if (fstat(fd, &sb) < 0) {
  361.     error("can't fstat: %1", strerror(errno));
  362.     close(fd);
  363.     return 0;
  364.   }
  365.   time_t mtime = sb.st_mtime;
  366.   if (mtime > indx->mtime) {
  367.     indx->add_out_of_date_file(fd, filename,
  368.                    indx->filename_id + tp->filename_index);
  369.     return 0;
  370.   }
  371.   int res = 0;
  372.   FILE *fp = fdopen(fd, "r");
  373.   if (!fp) {
  374.     error("fdopen failed");
  375.     close(fd);
  376.     return 0;
  377.   }
  378.   if (tp->start != 0 && fseek(fp, long(tp->start), 0) < 0)
  379.     error("can't seek on `%1': %2", filename, strerror(errno));
  380.   else {
  381.     int length = tp->length;
  382.     int err = 0;
  383.     if (length == 0) {
  384.       struct stat sb;
  385.       if (fstat(fileno(fp), &sb) < 0) {
  386.     error("can't stat `%1': %2", filename, strerror(errno));
  387.     err = 1;
  388.       }
  389.       else if ((sb.st_mode & S_IFMT) != S_IFREG) {
  390.     error("`%1' is not a regular file", filename);
  391.     err = 1;
  392.       }
  393.       else
  394.     length = int(sb.st_size);
  395.     }
  396.     if (!err) {
  397.       if (length + 2 > buflen) {
  398.     a_delete buf;
  399.     buflen = length + 2;
  400.     buf = new char[buflen];
  401.       }
  402.       if (fread(buf + 1, 1, length, fp) != length)
  403.     error("fread on `%1' failed: %2", filename, strerror(errno));
  404.       else {
  405.     buf[0] = '\n';
  406.     buf[length + 1] = '\n';
  407.     res = searcher.search(buf + 1, buf + 2 + length, pp, lenp);
  408.     if (res && ridp)
  409.       *ridp = reference_id(indx->filename_id + tp->filename_index,
  410.                    tp->start);
  411.       }
  412.     }
  413.   }
  414.   fclose(fp);
  415.   return res;
  416. }
  417.  
  418. const char *index_search_item::munge_filename(const char *filename)
  419. {
  420.   if (filename[0] == '/')
  421.     return filename;
  422.   const char *cwd = pool;
  423.   int need_slash = (cwd[0] != 0 && strchr(cwd, '\0')[-1] != '/');
  424.   int len = strlen(cwd) + strlen(filename) + need_slash + 1;
  425.   if (len > filename_buflen) {
  426.     a_delete filename_buffer;
  427.     filename_buflen = len;
  428.     filename_buffer = new char[len];
  429.   }
  430.   strcpy(filename_buffer, cwd);
  431.   if (need_slash)
  432.     strcat(filename_buffer, "/");
  433.   strcat(filename_buffer, filename);
  434.   return filename_buffer;
  435. }
  436.  
  437. const int *index_search_item::search1(const char **pp, const char *end)
  438. {
  439.   while (*pp < end && !csalnum(**pp))
  440.     *pp += 1;
  441.   if (*pp >= end)
  442.     return 0;
  443.   const char *start = *pp;
  444.   while (*pp < end && csalnum(**pp))
  445.     *pp += 1;
  446.   int len = *pp - start;
  447.   if (len < header.shortest)
  448.     return 0;
  449.   if (len > header.truncate)
  450.     len = header.truncate;
  451.   int is_number = 1;
  452.   for (int i = 0; i < len; i++)
  453.     if (csdigit(start[i]))
  454.       key_buffer[i] = start[i];
  455.     else {
  456.       key_buffer[i] = cmlower(start[i]);
  457.       is_number = 0;
  458.     }
  459.   if (is_number && !(len == 4 && start[0] == '1' && start[1] == '9'))
  460.     return 0;
  461.   unsigned hc = hash(key_buffer, len);
  462.   if (common_words_table) {
  463.     for (int h = hc % common_words_table_size;
  464.      common_words_table[h];
  465.      --h) {
  466.       if (strlen(common_words_table[h]) == len
  467.       && memcmp(common_words_table[h], key_buffer, len) == 0)
  468.     return 0;
  469.       if (h == 0)
  470.     h = common_words_table_size;
  471.     }
  472.   }
  473.   int li = table[int(hc % header.table_size)];
  474.   return li < 0 ? &minus_one : lists + li;
  475. }
  476.  
  477. static void merge(int *result, const int *s1, const int *s2)
  478. {
  479.   for (; *s1 >= 0; s1++) {
  480.     while (*s2 >= 0 && *s2 < *s1)
  481.       s2++;
  482.     if (*s2 == *s1)
  483.       *result++ = *s2;
  484.   }
  485.   *result++ = -1;
  486. }
  487.  
  488. const int *index_search_item::search(const char *ptr, int length,
  489.                      int **temp_listp)
  490. {
  491.   const char *end = ptr + length;
  492.   if (*temp_listp) {
  493.     a_delete *temp_listp;
  494.     *temp_listp = 0;
  495.   }
  496.   const int *first_list = 0;
  497.   while (ptr < end && (first_list = search1(&ptr, end)) == 0)
  498.     ;
  499.   if (!first_list)
  500.     return 0;
  501.   if (*first_list < 0)
  502.     return first_list;
  503.   const int *second_list = 0;
  504.   while (ptr < end && (second_list = search1(&ptr, end)) == 0)
  505.     ;
  506.   if (!second_list)
  507.     return first_list;
  508.   if (*second_list < 0)
  509.     return second_list;
  510.   for (const int *p = first_list; *p >= 0; p++)
  511.     ;
  512.   int len = p - first_list;
  513.   for (p = second_list; *p >= 0; p++)
  514.     ;
  515.   if (p - second_list < len)
  516.     len = p - second_list;
  517.   int *matches = new int[len + 1];
  518.   merge(matches, first_list, second_list);
  519.   while (ptr < end) {
  520.     const int *list = search1(&ptr, end);
  521.     if (list != 0) {
  522.       if (*list < 0) {
  523.     a_delete matches;
  524.     return list;
  525.       }
  526.       merge(matches, matches, list);
  527.       if (*matches < 0) {
  528.     a_delete matches;
  529.     return &minus_one;
  530.       }
  531.     }
  532.   }
  533.   *temp_listp = matches;
  534.   return matches;
  535. }
  536.  
  537. void index_search_item::read_common_words_file()
  538. {
  539.   if (header.common <= 0)
  540.     return;
  541.   const char *common_words_file = munge_filename(strchr(pool, '\0') + 1);
  542.   errno = 0;
  543.   FILE *fp = fopen(common_words_file, "r");
  544.   if (!fp) {
  545.     error("can't open `%1': %2", common_words_file, strerror(errno));
  546.     return;
  547.   }
  548.   common_words_table_size = 2*header.common + 1;
  549.   while (!is_prime(common_words_table_size))
  550.     common_words_table_size++;
  551.   common_words_table = new char *[common_words_table_size];
  552.   for (int i = 0; i < common_words_table_size; i++)
  553.     common_words_table[i] = 0;
  554.   int count = 0;
  555.   int key_len = 0;
  556.   for (;;) {
  557.     int c = getc(fp);
  558.     while (c != EOF && !csalnum(c))
  559.       c = getc(fp);
  560.     if (c == EOF)
  561.       break;
  562.     do {
  563.       if (key_len < header.truncate)
  564.     key_buffer[key_len++] = cmlower(c);
  565.       c = getc(fp);
  566.     } while (c != EOF && csalnum(c));
  567.     if (key_len >= header.shortest) {
  568.       int h = hash(key_buffer, key_len) % common_words_table_size;
  569.       while (common_words_table[h]) {
  570.     if (h == 0)
  571.       h = common_words_table_size;
  572.     --h;
  573.       }
  574.       common_words_table[h] = new char[key_len + 1];
  575.       memcpy(common_words_table[h], key_buffer, key_len);
  576.       common_words_table[h][key_len] = '\0';
  577.     }
  578.     if (++count >= header.common)
  579.       break;
  580.     key_len = 0;
  581.     if (c == EOF)
  582.       break;
  583.   }
  584.   fclose(fp);
  585. }
  586.  
  587. void index_search_item::add_out_of_date_file(int fd, const char *filename,
  588.                          int fid)
  589. {
  590.   for (search_item **pp = &out_of_date_files; *pp; pp = &(*pp)->next)
  591.     if ((*pp)->is_named(filename))
  592.       return;
  593.   *pp = make_linear_search_item(fd, filename, fid);
  594.   warning("`%1' modified since `%2' created", filename, name);
  595. }
  596.  
  597. void index_search_item::check_files()
  598. {
  599.   const char *pool_end = pool + header.strings_size;
  600.   for (const char *ptr = strchr(ignore_fields, '\0') + 1;
  601.        ptr < pool_end;
  602.        ptr = strchr(ptr, '\0') + 1) {
  603.     const char *path = munge_filename(ptr);
  604.     struct stat sb;
  605.     if (stat(path, &sb) < 0)
  606.       error("can't stat `%1': %2", path, strerror(errno));
  607.     else if (sb.st_mtime > mtime) {
  608.       int fd = open(path, O_RDONLY);
  609.       if (fd < 0)
  610.     error("can't open `%1': %2", path, strerror(errno));
  611.       else
  612.     add_out_of_date_file(fd, path, filename_id + (ptr - pool));
  613.     }
  614.   }
  615. }
  616.