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