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