home *** CD-ROM | disk | FTP | other *** search
/ Aminet 10 / aminetcdnumber101996.iso / Aminet / util / gnu / groff_src.lha / groff-1.10src / libbib / linear.cc < prev    next >
C/C++ Source or Header  |  1995-06-22  |  11KB  |  490 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.  
  22. #include <string.h>
  23. #include <stdlib.h>
  24. #include <assert.h>
  25. #include <errno.h>
  26.  
  27. #include "posix.h"
  28. #include "lib.h"
  29. #include "errarg.h"
  30. #include "error.h"
  31. #include "cset.h"
  32. #include "cmap.h"
  33.  
  34. #include "refid.h"
  35. #include "search.h"
  36.  
  37. class file_buffer {
  38.   char *buffer;
  39.   char *bufend;
  40. public:
  41.   file_buffer();
  42.   ~file_buffer();
  43.   int load(int fd, const char *filename);
  44.   const char *get_start() const;
  45.   const char *get_end() const;
  46. };
  47.  
  48. typedef unsigned char uchar;
  49.  
  50. static uchar map[256];
  51. static uchar inv_map[256][3];
  52.  
  53. struct map_init {
  54.   map_init();
  55. };
  56.  
  57. static map_init the_map_init;
  58.  
  59. map_init::map_init()
  60. {
  61.   int i;
  62.   for (i = 0; i < 256; i++)
  63.     map[i] = csalnum(i) ? cmlower(i) : '\0';
  64.   for (i = 0; i < 256; i++) {
  65.     if (cslower(i)) {
  66.       inv_map[i][0] = i;
  67.       inv_map[i][1] = cmupper(i);
  68.       inv_map[i][2] = '\0';
  69.     }
  70.     else if (csdigit(i)) {
  71.       inv_map[i][0] = i;
  72.       inv_map[i][1] = 0;
  73.     }
  74.     else
  75.       inv_map[i][0] = '\0';
  76.   }
  77. }
  78.  
  79.  
  80. class bmpattern {
  81.   char *pat;
  82.   int len;
  83.   int delta[256];
  84. public:
  85.   bmpattern(const char *pattern, int pattern_length);
  86.   ~bmpattern();
  87.   const char *search(const char *p, const char *end) const;
  88.   int length() const;
  89. };
  90.  
  91. bmpattern::bmpattern(const char *pattern, int pattern_length)
  92. : len(pattern_length)
  93. {
  94.   pat = new char[len];
  95.   int i;
  96.   for (i = 0; i < len; i++)
  97.     pat[i] = map[uchar(pattern[i])];
  98.   for (i = 0; i < 256; i++)
  99.     delta[i] = len;
  100.   for (i = 0; i < len; i++)
  101.     for (const unsigned char *inv = inv_map[uchar(pat[i])]; *inv; inv++)
  102.       delta[*inv] = len - i - 1;
  103. }
  104.  
  105. const char *bmpattern::search(const char *buf, const char *end) const
  106. {
  107.   int buflen = end - buf;
  108.   if (len > buflen)
  109.     return 0;
  110.   const char *strend;
  111.   if (buflen > len*4)
  112.     strend = end - len*4;
  113.   else
  114.     strend = buf;
  115.   const char *k = buf + len - 1;
  116.   const int *del = delta;
  117.   const char *pattern = pat;
  118.   for (;;) {
  119.     while (k < strend) {
  120.       int t = del[uchar(*k)];
  121.       if (!t)
  122.     break;
  123.       k += t;
  124.       k += del[uchar(*k)];
  125.       k += del[uchar(*k)];
  126.     }
  127.     while (k < end && del[uchar(*k)] != 0)
  128.       k++;
  129.     if (k == end)
  130.       break;
  131.     int j = len - 1;
  132.     const char *s = k;
  133.     for (;;) {
  134.       if (j == 0)
  135.     return s;
  136.       if (map[uchar(*--s)] != uchar(pattern[--j]))
  137.     break;
  138.     }
  139.     k++;
  140.   }
  141.   return 0;
  142. }
  143.  
  144. bmpattern::~bmpattern()
  145. {
  146.   a_delete pat;
  147. }
  148.  
  149. inline int bmpattern::length() const
  150. {
  151.   return len;
  152. }
  153.  
  154.  
  155. static const char *find_end(const char *bufend, const char *p);
  156.  
  157. const char *linear_searcher::search_and_check(const bmpattern *key,
  158.   const char *buf, const char *bufend, const char **start) const
  159. {
  160.   assert(buf[-1] == '\n');
  161.   assert(bufend[-1] == '\n');
  162.   const char *ptr = buf;
  163.   for (;;) {
  164.     const char *found = key->search(ptr, bufend);
  165.     if (!found)
  166.       break;
  167.     if (check_match(buf, bufend, found, key->length(), &ptr, start))
  168.       return found;
  169.   }
  170.   return 0;
  171. }
  172.  
  173. static const char *skip_field(const char *end, const char *p)
  174. {
  175.   for (;;)
  176.     if (*p++ == '\n') {
  177.       if (p == end || *p == '%')
  178.     break;
  179.       const char *q;
  180.       for (q = p; *q == ' ' || *q == '\t'; q++)
  181.     ;
  182.       if (*q == '\n')
  183.     break;
  184.       p = q + 1;
  185.     }
  186.   return p;
  187. }
  188.  
  189. static const char *find_end(const char *bufend, const char *p)
  190. {
  191.   for (;;)
  192.     if (*p++ == '\n') {
  193.       if (p == bufend)
  194.     break;
  195.       const char *q;
  196.       for (q = p; *q == ' ' || *q == '\t'; q++)
  197.     ;
  198.       if (*q == '\n')
  199.     break;
  200.       p = q + 1;
  201.     }
  202.   return p;
  203. }
  204.  
  205.  
  206. int linear_searcher::check_match(const char *buf, const char *bufend,
  207.                  const char *match, int matchlen,
  208.                  const char **cont, const char **start) const
  209. {
  210.   *cont = match + 1;
  211.   // The user is required to supply only the first truncate_len characters
  212.   // of the key.  If truncate_len <= 0, he must supply all the key.
  213.   if ((truncate_len <= 0 || matchlen < truncate_len)
  214.       && map[uchar(match[matchlen])] != '\0')
  215.     return 0;
  216.  
  217.   // The character before the match must not be an alphanumeric
  218.   // character (unless the alphanumeric character follows one or two
  219.   // percent characters at the beginning of the line), nor must it be
  220.   // a percent character at the beginning of a line, nor a percent
  221.   // character following a percent character at the beginning of a
  222.   // line.
  223.  
  224.   switch (match - buf) {
  225.   case 0:
  226.     break;
  227.   case 1:
  228.     if (match[-1] == '%' || map[uchar(match[-1])] != '\0')
  229.       return 0;
  230.     break;
  231.   case 2:
  232.     if (map[uchar(match[-1])] != '\0' && match[-2] != '%')
  233.       return 0;
  234.     if (match[-1] == '%'
  235.     && (match[-2] == '\n' || match[-2] == '%'))
  236.       return 0;
  237.     break;
  238.   default:
  239.     if (map[uchar(match[-1])] != '\0'
  240.     && !(match[-2] == '%'
  241.          && (match[-3] == '\n'
  242.          || (match[-3] == '%' && match[-4] == '\n'))))
  243.       return 0;
  244.     if (match[-1] == '%'
  245.     && (match[-2] == '\n'
  246.         || (match[-2] == '%' && match[-3] == '\n')))
  247.       return 0;
  248.   }
  249.     
  250.   const char *p = match;
  251.   int had_percent = 0;
  252.   for (;;) {
  253.     if (*p == '\n') {
  254.       if (!had_percent && p[1] == '%') {
  255.     if (p[2] != '\0' && strchr(ignore_fields, p[2]) != 0) {
  256.       *cont = skip_field(bufend, match + matchlen);
  257.       return 0;
  258.     }
  259.     if (!start)
  260.       break;
  261.     had_percent = 1;
  262.       }
  263.       if (p <= buf) {
  264.     if (start)
  265.       *start = p + 1;
  266.     return 1;
  267.       }
  268.       const char *q;
  269.       for (q = p - 1; *q == ' ' || *q == '\t'; q--)
  270.     ;
  271.       if (*q == '\n') {
  272.     if (start)
  273.       *start = p + 1;
  274.     break;
  275.       }
  276.       p = q;
  277.     }
  278.     p--;
  279.   }
  280.   return 1;
  281. }
  282.  
  283. file_buffer::file_buffer()
  284. : buffer(0), bufend(0)
  285. {
  286. }
  287.  
  288. file_buffer::~file_buffer()
  289. {
  290.   a_delete buffer;
  291. }
  292.  
  293. const char *file_buffer::get_start() const
  294. {
  295.   return buffer ? buffer + 4 : 0;
  296. }
  297.  
  298. const char *file_buffer::get_end() const
  299. {
  300.   return bufend;
  301. }
  302.  
  303. int file_buffer::load(int fd, const char *filename)
  304. {
  305.   struct stat sb;
  306.   if (fstat(fd, &sb) < 0)
  307.     error("can't fstat `%1': %2", filename, strerror(errno));
  308.   else if (!S_ISREG(sb.st_mode))
  309.     error("`%1' is not a regular file", filename);
  310.   else {
  311.     // We need one character extra at the beginning for an additional newline
  312.     // used as a sentinel.  We get 4 instead so that the read buffer will be
  313.     // word-aligned.  This seems to make the read slightly faster.  We also
  314.     // need one character at the end also for an additional newline used as a
  315.     // sentinel.
  316.     int size = int(sb.st_size);
  317.     buffer = new char[size + 4 + 1];
  318.     int nread = read(fd, buffer + 4, size);
  319.     if (nread < 0)
  320.       error("error reading `%1': %2", filename, strerror(errno));
  321.     else if (nread != size)
  322.       error("size of `%1' decreased", filename);
  323.     else {
  324.       char c;
  325.       nread = read(fd, &c, 1);
  326.       if (nread != 0)
  327.     error("size of `%1' increased", filename);
  328.       else if (memchr(buffer + 4, '\0', size < 1024 ? size : 1024) != 0)
  329.     error("database `%1' is a binary file", filename);
  330.       else {
  331.     close(fd);
  332.     buffer[3] = '\n';
  333.     bufend = buffer + 4 + size;
  334.     if (bufend[-1] != '\n')
  335.       *bufend++ = '\n';
  336.     return 1;
  337.       }
  338.     }
  339.     a_delete buffer;
  340.     buffer = 0;
  341.   }
  342.   close(fd);
  343.   return 0;
  344. }
  345.  
  346. linear_searcher::linear_searcher(const char *query, int query_len,
  347.                  const char *ign, int trunc)
  348. : keys(0), nkeys(0), truncate_len(trunc), ignore_fields(ign)
  349. {
  350.   const char *query_end = query + query_len;
  351.   int nk = 0;
  352.   const char *p;
  353.   for (p = query; p < query_end; p++)
  354.     if (map[uchar(*p)] != '\0'
  355.     && (p[1] == '\0' || map[uchar(p[1])] == '\0'))
  356.       nk++;
  357.   if (nk == 0)
  358.     return;
  359.   keys = new bmpattern*[nk];
  360.   p = query;
  361.   for (;;) {
  362.     while (p < query_end && map[uchar(*p)] == '\0')
  363.       p++;
  364.     if (p == query_end)
  365.       break;
  366.     const char *start = p;
  367.     while (p < query_end && map[uchar(*p)] != '\0')
  368.       p++;
  369.     keys[nkeys++] = new bmpattern(start, p - start);
  370.   }
  371.   assert(nkeys <= nk);
  372.   if (nkeys == 0) {
  373.     a_delete keys;
  374.     keys = 0;
  375.   }
  376. }
  377.  
  378. linear_searcher::~linear_searcher()
  379. {
  380.   for (int i = 0; i < nkeys; i++)
  381.     delete keys[i];
  382.   a_delete keys;
  383. }
  384.  
  385. int linear_searcher::search(const char *buffer, const char *bufend,
  386.                 const char **startp, int *lengthp) const
  387. {
  388.   assert(bufend - buffer > 0);
  389.   assert(buffer[-1] == '\n');
  390.   assert(bufend[-1] == '\n');
  391.   if (nkeys == 0)
  392.     return 0;
  393.   for (;;) {
  394.     const char *refstart;
  395.     const char *found = search_and_check(keys[0], buffer, bufend, &refstart);
  396.     if (!found)
  397.       break;
  398.     const char *refend = find_end(bufend, found + keys[0]->length());
  399.     int i;
  400.     for (i = 1; i < nkeys; i++)
  401.       if (!search_and_check(keys[i], refstart, refend))
  402.     break;
  403.     if (i >= nkeys) {
  404.       *startp = refstart;
  405.       *lengthp = refend - refstart;
  406.       return 1;
  407.     }
  408.     buffer = refend;
  409.   }
  410.   return 0;
  411. }
  412.  
  413. class linear_search_item : public search_item {
  414.   file_buffer fbuf;
  415. public:
  416.   linear_search_item(const char *filename, int fid);
  417.   ~linear_search_item();
  418.   int load(int fd);
  419.   search_item_iterator *make_search_item_iterator(const char *);
  420.   friend class linear_search_item_iterator;
  421. };
  422.  
  423. class linear_search_item_iterator : public search_item_iterator {
  424.   linear_search_item *lsi;
  425.   int pos;
  426. public:
  427.   linear_search_item_iterator(linear_search_item *, const char *query);
  428.   ~linear_search_item_iterator();
  429.   int next(const linear_searcher &, const char **ptr, int *lenp,
  430.        reference_id *ridp);
  431. };
  432.  
  433. search_item *make_linear_search_item(int fd, const char *filename, int fid)
  434. {
  435.   linear_search_item *item = new linear_search_item(filename, fid);
  436.   if (!item->load(fd)) {
  437.     delete item;
  438.     return 0;
  439.   }
  440.   else
  441.     return item;
  442. }
  443.  
  444. linear_search_item::linear_search_item(const char *filename, int fid)
  445. : search_item(filename, fid)
  446. {
  447. }
  448.  
  449. linear_search_item::~linear_search_item()
  450. {
  451. }
  452.  
  453. int linear_search_item::load(int fd)
  454. {
  455.   return fbuf.load(fd, name);
  456. }
  457.  
  458. search_item_iterator *linear_search_item::make_search_item_iterator(
  459.   const char *query)
  460. {
  461.   return new linear_search_item_iterator(this, query);
  462. }
  463.  
  464. linear_search_item_iterator::linear_search_item_iterator(
  465.   linear_search_item *p, const char *)
  466. : lsi(p), pos(0)
  467. {
  468. }
  469.  
  470. linear_search_item_iterator::~linear_search_item_iterator()
  471. {
  472. }
  473.  
  474. int linear_search_item_iterator::next(const linear_searcher &searcher,
  475.                       const char **startp, int *lengthp,
  476.                       reference_id *ridp)
  477. {
  478.   const char *bufstart = lsi->fbuf.get_start();
  479.   const char *bufend = lsi->fbuf.get_end();
  480.   const char *ptr = bufstart + pos;
  481.   if (ptr < bufend && searcher.search(ptr, bufend, startp, lengthp)) {
  482.     pos = *startp + *lengthp - bufstart;
  483.     if (ridp)
  484.       *ridp = reference_id(lsi->filename_id, *startp - bufstart);
  485.     return 1;
  486.   }
  487.   else
  488.     return 0;
  489. }
  490.