libbib/linear.cc

   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 }