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