home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / SourceCode / MiscKit / Projects / MiscFindPanel / SearchCategories / MiscTBMK.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-23  |  8.2 KB  |  270 lines
  1. /*  A variation on Hume & Sunday's Tuned Boyer-Moore algorithm
  2.  *  for searching for a literal string pattern in a text.
  3.  *
  4.  *  References:
  5.  *    Hume, A., D.M. Sunday. "Fast String Searching."
  6.  *       _Software--Practice and Experience_. Vol. 21.
  7.  *       No. 11. p. 1221-48. November 1991.
  8.  *
  9.  *  Copyright (c) 1994 Christopher J. Kane.
  10.  *
  11.  *  Version 1.2 (March 22, 1994)
  12.  */
  13.  
  14. #include <misckit/MiscTBMK.h>
  15. #include <ctype.h>
  16. extern void *calloc(unsigned int, unsigned int);
  17. extern void free(void *);
  18.  
  19. #define TBMKMAGIC 0x54424D4B
  20.  
  21. struct Misc_tbmk_pattern {
  22.   unsigned int magic;
  23.   signed int *pattern;
  24.   signed int skip[256];
  25.   signed int patlen;
  26.   signed int direction;
  27.   signed int jump;
  28. };
  29.  
  30. Misc_TBMKpattern
  31. Misc_TBMKpattern_alloc(const unsigned char *pattern,
  32.                        unsigned int pattern_length,
  33.                        unsigned char reverse,
  34.                        unsigned char nocases)
  35. {
  36.   Misc_TBMKpattern new;
  37.   unsigned char *tmppat;
  38.   int i;
  39.  
  40.   if (pattern_length==0) {
  41.     return 0;
  42.   }
  43.   new = (Misc_TBMKpattern)calloc(1, sizeof(struct Misc_tbmk_pattern));
  44.   if (new==0) {
  45.     return 0;
  46.   }
  47.   new->pattern = (int *)calloc(pattern_length, sizeof(int));
  48.   if (new->pattern==0) {
  49.     free(new);
  50.     return 0;
  51.   }
  52.   tmppat = (unsigned char *)calloc(pattern_length, sizeof(char));
  53.   if (tmppat==0) {
  54.     free(new->pattern);
  55.     free(new);
  56.     return 0;
  57.   }
  58.   new->magic = TBMKMAGIC;
  59.   for (i = pattern_length; i--;) {
  60.     tmppat[i] = nocases?tolower(pattern[i]):pattern[i];
  61.   }
  62.   new->patlen = reverse?-pattern_length:pattern_length;
  63.   new->direction = reverse?-1:1;
  64.   for (i = 256; i--;) {
  65.     new->skip[i] = new->patlen;
  66.   }
  67.   if (reverse) {
  68.     for (i = pattern_length-1; i>=0; i--) {
  69.       if (nocases) {
  70.         new->skip[tolower(tmppat[i])] = -i;
  71.         new->skip[toupper(tmppat[i])] = -i;
  72.       } else {
  73.         new->skip[tmppat[i]] = -i;
  74.       }
  75.     }
  76.     for (i = 1; i<pattern_length && tmppat[i]!=tmppat[0]; i++);
  77.     new->jump = -i;
  78.     for (i = 0; i<pattern_length; i++) {
  79.       new->pattern[pattern_length-1-i] = new->skip[pattern[i]];
  80.     }
  81.   } else {
  82.     for (i = 0; i<pattern_length; i++) {
  83.       if (nocases) {
  84.         new->skip[tolower(tmppat[i])] = pattern_length-1-i;
  85.         new->skip[toupper(tmppat[i])] = pattern_length-1-i;
  86.       } else {
  87.         new->skip[tmppat[i]] = pattern_length-1-i;
  88.       }
  89.     }
  90.     for (i = pattern_length-2; i>=0 && tmppat[i]!=tmppat[pattern_length-1]; i--);
  91.     new->jump = pattern_length-1-i;
  92.     for (i = 0; i<pattern_length; i++) {
  93.       new->pattern[i] = new->skip[pattern[i]];
  94.     }
  95.   }
  96.   free(tmppat);
  97.   return new;
  98. }
  99.  
  100. void
  101. Misc_TBMKpattern_free(Misc_TBMKpattern *pattern)
  102. {
  103.   if (pattern!=0 && *pattern!=0 && (*pattern)->magic==TBMKMAGIC) {
  104.     if ((*pattern)->pattern!=0) {
  105.       free((*pattern)->pattern);
  106.     }
  107.     free(*pattern);
  108.     *pattern = 0;
  109.   }
  110. }
  111.  
  112. #define UNROLL 4
  113.  
  114. int
  115. Misc_TBMKsearch_memory(const Misc_TBMKpattern pattern,
  116.                        const unsigned char *text,
  117.                        int text_extent,
  118.                        unsigned char all_matches,
  119.                        int *match_position)
  120. {
  121.   const unsigned char *cp, *tmpcp, *lb, *flb, *ub, *fub;
  122.   unsigned int nmatch, i;
  123.  
  124.   if (!pattern || pattern->magic!=TBMKMAGIC || !text ||
  125.       (pattern->direction<0 && 0<text_extent) ||
  126.       (0<pattern->direction && text_extent<0)) {
  127.     return -1;                                              /* it's bad, bad */
  128.   }
  129.   cp = text+pattern->patlen-pattern->direction;
  130.   if (0<pattern->direction) { /* calculate upper and lower bounds for search */
  131.     ub = text+text_extent-1;
  132.     fub = ub-UNROLL*pattern->patlen;
  133.     lb = flb = cp;
  134.   } else {
  135.     lb = text+text_extent+1;
  136.     flb = lb+UNROLL*pattern->patlen;
  137.     ub = fub = cp;
  138.   }
  139.   nmatch = 0;
  140.  skip_loop:
  141.   if (ub<cp || cp<lb) {                     /* search is out of bounds; done */
  142.     return nmatch;
  143.   }
  144.   while (pattern->skip[*cp]) {     /* not match of last character in pattern */
  145.     if (flb<cp && cp<fub) {
  146.       cp += pattern->skip[*cp];      /* skip or align to next possible match */
  147.       cp += pattern->skip[*cp];      /* skip or align to next possible match */
  148.       cp += pattern->skip[*cp];      /* skip or align to next possible match */
  149.       cp += pattern->skip[*cp];      /* skip or align to next possible match */
  150.     }
  151.     cp += pattern->skip[*cp];        /* skip or align to next possible match */
  152.     if (ub<cp || cp<lb) {                   /* search is out of bounds; done */
  153.       return nmatch;
  154.     }
  155.   }                                 /* fall out of skip loop, possible match */
  156.   tmpcp = cp-pattern->patlen+pattern->direction;
  157.   for (i = 0; tmpcp!=cp; i++) {                 /* compare pattern with text */
  158.     if (pattern->skip[*tmpcp]!=pattern->pattern[i]) {
  159.       cp += pattern->jump;
  160.       goto skip_loop;                 /* mismatch, go back to fast skip loop */
  161.     }
  162.     tmpcp += pattern->direction;                   /* move to next character */
  163.   }
  164.   *match_position = cp-text;                                  /* match found */
  165.   if (0<pattern->direction) {
  166.     *match_position -= (pattern->patlen-1);
  167.   }
  168.   nmatch++;
  169.   if (all_matches) {
  170.     cp += pattern->patlen;             /* move current position beyond match */
  171.     goto skip_loop;                             /* go back to fast skip loop */
  172.   }
  173.   return nmatch;
  174. }
  175.  
  176. #if defined(NeXT)
  177.  
  178. #define STREAM_MAGIC 0xbead0369
  179. #define Tell(S) ((S)->buf_ptr-(S)->buf_base+(S)->offset)
  180. #define Getc(S) ((S)->buf_left>0?(*(S)->buf_ptr):_NXStreamFillBuffer(S))
  181.  
  182. /* Seek() can handle NX_FROMSTART and NX_FROMCURRENT only. */
  183. #define Seek(S, O, M) ({int _off=(O)+((M)==1?Tell(S):0); \
  184.     if ((S)->eof<Tell(S)) {(S)->eof = Tell(S);} \
  185.     if (_off<0 || (S)->eof<_off) {NX_RAISE(NX_illegalSeek, (S), 0);} \
  186.     (*(S)->functions->seek)((S), _off);})
  187.  
  188. int
  189. Misc_TBMKsearch_stream(const Misc_TBMKpattern pattern,
  190.                        NXStream *stream,
  191.                        int text_extent,
  192.                        unsigned char all_matches,
  193.                        int *match_position)
  194. {
  195.   unsigned int nmatch, i, writable;
  196.   int skip, current, start;
  197.  
  198.   if (!pattern || pattern->magic!=TBMKMAGIC ||
  199.       !stream || stream->magic_number!=STREAM_MAGIC ||
  200.       (pattern->direction<0 && 0<text_extent) ||
  201.       (0<pattern->direction && text_extent<0) ||
  202.       !(stream->flags&NX_READFLAG && stream->flags&NX_CANSEEK)) {
  203.     return -1;
  204.   }
  205.   if ((0<pattern->direction && text_extent<pattern->patlen) ||
  206.       (pattern->direction<0 && text_extent>pattern->patlen)) {
  207.     return 0;
  208.   }
  209.   writable = stream->flags&NX_WRITEFLAG;
  210.   stream->flags &= ~NX_WRITEFLAG;
  211.  NX_DURING
  212.   start = Tell(stream);
  213.   Seek(stream, pattern->patlen-pattern->direction, NX_FROMCURRENT);
  214.   text_extent -= pattern->patlen;
  215.   nmatch = 0;
  216.  skip_loop:
  217.   do {                                                     /* fast skip loop */
  218.     skip = pattern->skip[Getc(stream)];
  219.     Seek(stream, skip, NX_FROMCURRENT);
  220.     text_extent -= skip;
  221.     skip = pattern->skip[Getc(stream)];
  222.     Seek(stream, skip, NX_FROMCURRENT);
  223.     text_extent -= skip;
  224.     if ((0<pattern->direction && text_extent<0) ||
  225.         (pattern->direction<0 && text_extent>0)) {
  226.       if (writable) {
  227.         stream->flags |= NX_WRITEFLAG;
  228.       }
  229.       return nmatch;
  230.     }
  231.   } while (skip);
  232.   current = Tell(stream);
  233.   Seek(stream, -pattern->patlen+pattern->direction, NX_FROMCURRENT);
  234.   for (i = 0; Tell(stream)!=current; i++) {     /* compare pattern with text */
  235.     if (pattern->skip[Getc(stream)]!=pattern->pattern[i]) {
  236.       Seek(stream, current+pattern->jump, NX_FROMSTART);
  237.       text_extent -= pattern->jump;
  238.       goto skip_loop;                 /* mismatch, go back to fast skip loop */
  239.     }
  240.     Seek(stream, pattern->direction, NX_FROMCURRENT);
  241.   }
  242.   *match_position = current-start;                            /* match found */
  243.   if (0<pattern->direction) {
  244.     *match_position -= (pattern->patlen-1);
  245.   }
  246.   nmatch++;
  247.   if (!all_matches) {
  248.     if (writable) {
  249.       stream->flags |= NX_WRITEFLAG;
  250.     }
  251.     return nmatch;
  252.   }
  253.   Seek(stream, pattern->patlen, NX_FROMCURRENT);
  254.   text_extent -= pattern->patlen;
  255.   goto skip_loop;                               /* go back to fast skip loop */
  256.  NX_HANDLER
  257.   if (writable) {
  258.     stream->flags |= NX_WRITEFLAG;
  259.   }
  260.   switch (NXLocalHandler.code) {
  261.     case NX_illegalSeek:
  262.       return nmatch;
  263.     default:
  264.       NX_RERAISE();
  265.   }
  266.  NX_ENDHANDLER
  267. }
  268.  
  269. #endif /* defined(NeXT) */
  270.