home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1994 June / NEBULA_SE.ISO / SourceCode / MiscKit / Projects / MiscFindPanel / SearchCategories / MiscTBMK.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-23  |  4.8 KB  |  109 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. #ifndef _MISC_TBMK_H
  15. #define _MISC_TBMK_H
  16.  
  17. /* The type Misc_TBMKpattern is a pointer to a structure used to hold
  18.  * a compiled pattern. Create a compiled pattern by using the function
  19.  * Misc_TBMKpattern_alloc(), destroy it with Misc_TBMKpattern_free().
  20.  * The members of the structure should never be accessed directly. */
  21.  
  22. typedef struct Misc_tbmk_pattern * Misc_TBMKpattern;
  23.  
  24.  
  25. /* Creates and compiles a pattern structure from the parameters, and
  26.  * returns a pointer to it. The search is for a fixed-length sequence of
  27.  * characters; the pattern can contain embedded \0 characters. To change
  28.  * the case sensitivity of a search or the direction, the pattern must
  29.  * be recompiled. Returns NULL if 'pattern_length' is zero, or memory
  30.  * couldn't be allocated. Note that if the parameter 'nocases' is true,
  31.  * searches with the returned pattern will be case insensitive. */
  32.  
  33. Misc_TBMKpattern
  34. Misc_TBMKpattern_alloc(const unsigned char *pattern,
  35.                        unsigned int pattern_length,
  36.                        unsigned char reverse,
  37.                        unsigned char nocases);
  38.  
  39.  
  40. /* Destroys a pattern structure created with Misc_TBMKpattern_alloc().
  41.  * Note that a *pointer* to the value returned by that function is
  42.  * passed as the paramter. On return, the value pointed to by 'pattern'
  43.  * has been set to NULL. This function does nothing if 'pattern' or the
  44.  * address 'pattern' points to is NULL, or does not point to a valid
  45.  * Misc_TBMKpattern. */
  46.  
  47. void
  48. Misc_TBMKpattern_free(Misc_TBMKpattern *pattern);
  49.  
  50.  
  51. /* Both of these search function search a source of characters for a
  52.  * literal text as compiled into a Misc_TBMKpattern structure. The first,
  53.  * Misc_TBMKsearch_memory(), uses a contiguous block of memory as the
  54.  * source of characters; the parameter 'text' points to the first
  55.  * character that might possibly be examined by the search. The second
  56.  * function, Misc_TBMKsearch_stream() gets its characters from the
  57.  * NXStream 'stream'; searching begins at the current position of the
  58.  * stream. The search encompasses at most 'text_extent' characters from
  59.  * (and including) the character pointed to by 'text'. 'text_extent' is
  60.  * positive for forward searches, negative for reverse searches (as
  61.  * specified when the pattern was compiled). If 'all_matches' is true,
  62.  * the entire extent is searched and the total number of matches is
  63.  * returned; otherwise, the search stops at the first match. The number
  64.  * of non-overlapping matches is returned (zero if no matches found), and
  65.  * the offset from 'text' of the last match is returned by reference in
  66.  * 'match_position' (for reverse searches, the 'match_position' will be
  67.  * negative). Both functions return -1 if 'pattern' is clearly not a
  68.  * valid pattern, or the sign of 'text_extent' is not valid for the
  69.  * direction of the search specified when the pattern was compiled.
  70.  *
  71.  * Additionally, for Misc_TBMKsearch_stream(): When searching a stream,
  72.  * if the end of stream arrives before 'text_extent' is reached, the
  73.  * function returns as it does when 'text_extent' is reached. Note that
  74.  * since seeks on a stream that is writable extend the size of the
  75.  * stream, the write flag of the stream is turned off while this function
  76.  * is executing; this may impact, for instance, signal handlers which are
  77.  * called during the search. The flag is restored before the function
  78.  * returns or upon the generation of an exception (before an non-handled
  79.  * exeption is propogated outside the function). In addition to the
  80.  * errors named above, -1 is returned if the stream is not readable or
  81.  * not seekable. Exceptions other than NX_illegalSeek are propogated up
  82.  * the function call stack as usual; NX_illegalSeek exceptions cause a
  83.  * normal return. Finally, the function guarentees nothing about the
  84.  * current position of the stream when the function returns. */
  85.  
  86. int
  87. Misc_TBMKsearch_memory(const Misc_TBMKpattern pattern,
  88.                        const unsigned char *text,
  89.                        int text_extent,
  90.                        unsigned char all_matches,
  91.                        int *match_position);
  92.  
  93. #if defined(NeXT)
  94. #include <streams/streams.h>
  95.  
  96. int
  97. Misc_TBMKsearch_stream(const Misc_TBMKpattern pattern,
  98.                        NXStream *stream,
  99.                        int text_extent,
  100.                        unsigned char all_matches,
  101.                        int *match_position);
  102.  
  103. #endif /* defined(NeXT) */
  104.  
  105. /* For compatibility with version 1.0 of this module. */
  106. #define Misc_TBMKsearch Misc_TBMKsearch_memory
  107.  
  108. #endif /* _MISC_TBMK_H */
  109.