/*

 * This file has been copied from commit e7ac713d^ in the GNU grep git

 * repository. A few small changes have been made to adapt the code to

 * Git.

 */

/* kwset.c - search for any of a set of keywords.

   Copyright 1989, 1998, 2000, 2005 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 2, or (at your option)

   any later version.

   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License

   along with this program; if not, see <https://www.gnu.org/licenses/>. */

/* Written August 1989 by Mike Haertel.

   The author may be reached (Email) at the address mike@ai.mit.edu,

   or (US mail) as Mike Haertel c/o Free Software Foundation. */

/* The algorithm implemented by these routines bears a startling resemblance

   to one discovered by Beate Commentz-Walter, although it is not identical.

   See "A String Matching Algorithm Fast on the Average," Technical Report,

   IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900

   Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient

   String Matching:  An Aid to Bibliographic Search," CACM June 1975,

   Vol. 18, No. 6, which describes the failure function used below. */

#include "git-compat-util.h"

#include "kwset.h"

#include "compat/obstack.h"

#define NCHAR (UCHAR_MAX + 1)

/* adapter for `xmalloc()`, which takes `size_t`, not `long` */

static void *obstack_chunk_alloc(long size)

{

  if (size < 0)

    BUG("Cannot allocate a negative amount: %ld", size);

  return xmalloc(size);

}

#define obstack_chunk_free free

#define U(c) ((unsigned char) (c))

/* For case-insensitive kwset */

const unsigned char tolower_trans_tbl[256] = {

  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,

  0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,

  0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,

  0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,

   ' ',  '!',  '"',  '#',  '$',  '%',  '&', 0x27,

   '(',  ')',  '*',  '+',  ',',  '-',  '.',  '/',

   '0',  '1',  '2',  '3',  '4',  '5',  '6',  '7',

   '8',  '9',  ':',  ';',  '<',  '=',  '>',  '?',

   '@',  'a',  'b',  'c',  'd',  'e',  'f',  'g',

   'h',  'i',  'j',  'k',  'l',  'm',  'n',  'o',

   'p',  'q',  'r',  's',  't',  'u',  'v',  'w',

   'x',  'y',  'z',  '[', 0x5c,  ']',  '^',  '_',

   '`',  'a',  'b',  'c',  'd',  'e',  'f',  'g',

   'h',  'i',  'j',  'k',  'l',  'm',  'n',  'o',

   'p',  'q',  'r',  's',  't',  'u',  'v',  'w',

   'x',  'y',  'z',  '{',  '|',  '}',  '~', 0x7f,

  0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,

  0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,

  0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,

  0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,

  0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,

  0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,

  0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,

  0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,

  0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,

  0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,

  0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,

  0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,

  0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,

  0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,

  0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,

  0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff,

};

/* Balanced tree of edges and labels leaving a given trie node. */

struct tree

{

  struct tree *llink;   /* Left link; MUST be first field. */

  struct tree *rlink;   /* Right link (to larger labels). */

  struct trie *trie;    /* Trie node pointed to by this edge. */

  unsigned char label;    /* Label on this edge. */

  char balance;     /* Difference in depths of subtrees. */

};

/* Node of a trie representing a set of reversed keywords. */

struct trie

{

  unsigned int accepting; /* Word index of accepted word, or zero. */

  struct tree *links;   /* Tree of edges leaving this node. */

  struct trie *parent;    /* Parent of this node. */

  struct trie *next;    /* List of all trie nodes in level order. */

  struct trie *fail;    /* Aho-Corasick failure function. */

  int depth;      /* Depth of this node from the root. */

  int shift;      /* Shift function for search failures. */

  int maxshift;     /* Max shift of self and descendants. */

};

/* Structure returned opaquely to the caller, containing everything. */

struct kwset

{

  struct obstack obstack; /* Obstack for node allocation. */

  int words;      /* Number of words in the trie. */

  struct trie *trie;    /* The trie itself. */

  int mind;     /* Minimum depth of an accepting node. */

  int maxd;     /* Maximum depth of any node. */

  unsigned char delta[NCHAR]; /* Delta table for rapid search. */

  struct trie *next[NCHAR]; /* Table of children of the root. */

  char *target;     /* Target string if there's only one. */

  int mind2;      /* Used in Boyer-Moore search for one string. */

  unsigned char const *trans;  /* Character translation table. */

};

/* Allocate and initialize a keyword set object, returning an opaque

   pointer to it.  Return NULL if memory is not available. */

kwset_t

kwsalloc (unsigned char const *trans)

{

  struct kwset *kwset;

  kwset = (struct kwset *) xmalloc(sizeof (struct kwset));

  obstack_init(&kwset->obstack);

  kwset->words = 0;

  kwset->trie

    = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));

  if (!kwset->trie)

    {

      kwsfree((kwset_t) kwset);

      return NULL;

    }

  kwset->trie->accepting = 0;

  kwset->trie->links = NULL;

  kwset->trie->parent = NULL;

  kwset->trie->next = NULL;

  kwset->trie->fail = NULL;

  kwset->trie->depth = 0;

  kwset->trie->shift = 0;

  kwset->mind = INT_MAX;

  kwset->maxd = -1;

  kwset->target = NULL;

  kwset->trans = trans;

  return (kwset_t) kwset;

}

/* This upper bound is valid for CHAR_BIT >= 4 and

   exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */

#define DEPTH_SIZE (CHAR_BIT + CHAR_BIT/2)

/* Add the given string to the contents of the keyword set.  Return NULL

   for success, an error message otherwise. */

const char *

kwsincr (kwset_t kws, char const *text, size_t len)

{

  struct kwset *kwset;

  register struct trie *trie;

  register unsigned char label;

  register struct tree *link;

  register int depth;

  struct tree *links[DEPTH_SIZE];

  enum { L, R } dirs[DEPTH_SIZE];

  struct tree *t, *r, *l, *rl, *lr;

  kwset = (struct kwset *) kws;

  trie = kwset->trie;

  text += len;

  /* Descend the trie (built of reversed keywords) character-by-character,

     installing new nodes when necessary. */

  while (len--)

    {

      label = kwset->trans ? kwset->trans[U(*--text)] : *--text;

      /* Descend the tree of outgoing links for this trie node,

   looking for the current character and keeping track

   of the path followed. */

      link = trie->links;

      links[0] = (struct tree *) &trie->links;

      dirs[0] = L;

      depth = 1;

      while (link && label != link->label)

  {

    links[depth] = link;

    if (label < link->label)

      dirs[depth++] = L, link = link->llink;

    else

      dirs[depth++] = R, link = link->rlink;

  }

      /* The current character doesn't have an outgoing link at

   this trie node, so build a new trie node and install

   a link in the current trie node's tree. */

      if (!link)

  {

    link = (struct tree *) obstack_alloc(&kwset->obstack,

                 sizeof (struct tree));

    if (!link)

      return "memory exhausted";

    link->llink = NULL;

    link->rlink = NULL;

    link->trie = (struct trie *) obstack_alloc(&kwset->obstack,

                 sizeof (struct trie));

    if (!link->trie)

      {

        obstack_free(&kwset->obstack, link);

        return "memory exhausted";

      }

    link->trie->accepting = 0;

    link->trie->links = NULL;

    link->trie->parent = trie;

    link->trie->next = NULL;

    link->trie->fail = NULL;

    link->trie->depth = trie->depth + 1;

    link->trie->shift = 0;

    link->label = label;

    link->balance = 0;

    /* Install the new tree node in its parent. */

    if (dirs[--depth] == L)

      links[depth]->llink = link;

    else

      links[depth]->rlink = link;

    /* Back up the tree fixing the balance flags. */

    while (depth && !links[depth]->balance)

      {

        if (dirs[depth] == L)

    --links[depth]->balance;

        else

    ++links[depth]->balance;

        --depth;

      }

    /* Rebalance the tree by pointer rotations if necessary. */

    if (depth && ((dirs[depth] == L && --links[depth]->balance)

      || (dirs[depth] == R && ++links[depth]->balance)))

      {

        switch (links[depth]->balance)

    {

    case (char) -2:

      switch (dirs[depth + 1])

        {

        case L:

          r = links[depth], t = r->llink, rl = t->rlink;

          t->rlink = r, r->llink = rl;

          t->balance = r->balance = 0;

          break;

        case R:

          r = links[depth], l = r->llink, t = l->rlink;

          rl = t->rlink, lr = t->llink;

          t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;

          l->balance = t->balance != 1 ? 0 : -1;

          r->balance = t->balance != (char) -1 ? 0 : 1;

          t->balance = 0;

          break;

        default:

          abort ();

        }

      break;

    case 2:

      switch (dirs[depth + 1])

        {

        case R:

          l = links[depth], t = l->rlink, lr = t->llink;

          t->llink = l, l->rlink = lr;

          t->balance = l->balance = 0;

          break;

        case L:

          l = links[depth], r = l->rlink, t = r->llink;

          lr = t->llink, rl = t->rlink;

          t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;

          l->balance = t->balance != 1 ? 0 : -1;

          r->balance = t->balance != (char) -1 ? 0 : 1;

          t->balance = 0;

          break;

        default:

          abort ();

        }

      break;

    default:

      abort ();

    }

        if (dirs[depth - 1] == L)

    links[depth - 1]->llink = t;

        else

    links[depth - 1]->rlink = t;

      }

  }

      trie = link->trie;

    }

  /* Mark the node we finally reached as accepting, encoding the

     index number of this word in the keyword set so far. */

  if (!trie->accepting)

    trie->accepting = 1 + 2 * kwset->words;

  ++kwset->words;

  /* Keep track of the longest and shortest string of the keyword set. */

  if (trie->depth < kwset->mind)

    kwset->mind = trie->depth;

  if (trie->depth > kwset->maxd)

    kwset->maxd = trie->depth;

  return NULL;

}

/* Enqueue the trie nodes referenced from the given tree in the

   given queue. */

static void

enqueue (struct tree *tree, struct trie **last)

{

  if (!tree)

    return;

  enqueue(tree->llink, last);

  enqueue(tree->rlink, last);

  (*last) = (*last)->next = tree->trie;

}

/* Compute the Aho-Corasick failure function for the trie nodes referenced

   from the given tree, given the failure function for their parent as

   well as a last resort failure node. */

static void

treefails (register struct tree const *tree, struct trie const *fail,

     struct trie *recourse)

{

  register struct tree *link;

  if (!tree)

    return;

  treefails(tree->llink, fail, recourse);

  treefails(tree->rlink, fail, recourse);

  /* Find, in the chain of fails going back to the root, the first

     node that has a descendant on the current label. */

  while (fail)

    {

      link = fail->links;

      while (link && tree->label != link->label)

  if (tree->label < link->label)

    link = link->llink;

  else

    link = link->rlink;

      if (link)

  {

    tree->trie->fail = link->trie;

    return;

  }

      fail = fail->fail;

    }

  tree->trie->fail = recourse;

}

/* Set delta entries for the links of the given tree such that

   the preexisting delta value is larger than the current depth. */

static void

treedelta (register struct tree const *tree,

     register unsigned int depth,

     unsigned char delta[])

{

  if (!tree)

    return;

  treedelta(tree->llink, depth, delta);

  treedelta(tree->rlink, depth, delta);

  if (depth < delta[tree->label])

    delta[tree->label] = depth;

}

/* Return true if A has every label in B. */

static int

hasevery (register struct tree const *a, register struct tree const *b)

{

  if (!b)

    return 1;

  if (!hasevery(a, b->llink))

    return 0;

  if (!hasevery(a, b->rlink))

    return 0;

  while (a && b->label != a->label)

    if (b->label < a->label)

      a = a->llink;

    else

      a = a->rlink;

  return !!a;

}

/* Compute a vector, indexed by character code, of the trie nodes

   referenced from the given tree. */

static void

treenext (struct tree const *tree, struct trie *next[])

{

  if (!tree)

    return;

  treenext(tree->llink, next);

  treenext(tree->rlink, next);

  next[tree->label] = tree->trie;

}

/* Compute the shift for each trie node, as well as the delta

   table and next cache for the given keyword set. */

const char *

kwsprep (kwset_t kws)

{

  register struct kwset *kwset;

  register int i;

  register struct trie *curr;

  register unsigned char const *trans;

  unsigned char delta[NCHAR];

  kwset = (struct kwset *) kws;

  /* Initial values for the delta table; will be changed later.  The

     delta entry for a given character is the smallest depth of any

     node at which an outgoing edge is labeled by that character. */

  memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);

  /* Check if we can use the simple boyer-moore algorithm, instead

     of the hairy commentz-walter algorithm. */

  if (kwset->words == 1 && kwset->trans == NULL)

    {

      char c;

      /* Looking for just one string.  Extract it from the trie. */

      kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);

      if (!kwset->target)

  return "memory exhausted";

      for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)

  {

    kwset->target[i] = curr->links->label;

    curr = curr->links->trie;

  }

      /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */

      for (i = 0; i < kwset->mind; ++i)

  delta[U(kwset->target[i])] = kwset->mind - (i + 1);

      /* Find the minimal delta2 shift that we might make after

   a backwards match has failed. */

      c = kwset->target[kwset->mind - 1];

      for (i = kwset->mind - 2; i >= 0; --i)

  if (kwset->target[i] == c)

    break;

      kwset->mind2 = kwset->mind - (i + 1);

    }

  else

    {

      register struct trie *fail;

      struct trie *last, *next[NCHAR];

      /* Traverse the nodes of the trie in level order, simultaneously

   computing the delta table, failure function, and shift function. */

      for (curr = last = kwset->trie; curr; curr = curr->next)

  {

    /* Enqueue the immediate descendants in the level order queue. */

    enqueue(curr->links, &last);

    curr->shift = kwset->mind;

    curr->maxshift = kwset->mind;

    /* Update the delta table for the descendants of this node. */

    treedelta(curr->links, curr->depth, delta);

    /* Compute the failure function for the descendants of this node. */

    treefails(curr->links, curr->fail, kwset->trie);

    /* Update the shifts at each node in the current node's chain

       of fails back to the root. */

    for (fail = curr->fail; fail; fail = fail->fail)

      {

        /* If the current node has some outgoing edge that the fail

     doesn't, then the shift at the fail should be no larger

     than the difference of their depths. */

        if (!hasevery(fail->links, curr->links))

    if (curr->depth - fail->depth < fail->shift)

      fail->shift = curr->depth - fail->depth;

        /* If the current node is accepting then the shift at the

     fail and its descendants should be no larger than the

     difference of their depths. */

        if (curr->accepting && fail->maxshift > curr->depth - fail->depth)

    fail->maxshift = curr->depth - fail->depth;

      }

  }

      /* Traverse the trie in level order again, fixing up all nodes whose

   shift exceeds their inherited maxshift. */

      for (curr = kwset->trie->next; curr; curr = curr->next)

  {

    if (curr->maxshift > curr->parent->maxshift)

      curr->maxshift = curr->parent->maxshift;

    if (curr->shift > curr->maxshift)

      curr->shift = curr->maxshift;

  }

      /* Create a vector, indexed by character code, of the outgoing links

   from the root node. */

      for (i = 0; i < NCHAR; ++i)

  next[i] = NULL;

      treenext(kwset->trie->links, next);

      if ((trans = kwset->trans))

  for (i = 0; i < NCHAR; ++i)

    kwset->next[i] = next[U(trans[i])];

      else

  COPY_ARRAY(kwset->next, next, NCHAR);

    }

  /* Fix things up for any translation table. */

  if ((trans = kwset->trans))

    for (i = 0; i < NCHAR; ++i)

      kwset->delta[i] = delta[U(trans[i])];

  else

    memcpy(kwset->delta, delta, NCHAR);

  return NULL;

}

/* Fast boyer-moore search. */

static size_t

bmexec (kwset_t kws, char const *text, size_t size)

{

  struct kwset const *kwset;

  register unsigned char const *d1;

  register char const *ep, *sp, *tp;

  register int d, gc, i, len, md2;

  kwset = (struct kwset const *) kws;

  len = kwset->mind;

  if (len == 0)

    return 0;

  if (len > size)

    return -1;

  if (len == 1)

    {

      tp = memchr (text, kwset->target[0], size);

      return tp ? tp - text : -1;

    }

  d1 = kwset->delta;

  sp = kwset->target + len;

  gc = U(sp[-2]);

  md2 = kwset->mind2;

  tp = text + len;

  /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */

  if (size > 12 * len)

    /* 11 is not a bug, the initial offset happens only once. */

    for (ep = text + size - 11 * len;;)

      {

  while (tp <= ep)

    {

      d = d1[U(tp[-1])], tp += d;

      d = d1[U(tp[-1])], tp += d;

      if (d == 0)

        goto found;

      d = d1[U(tp[-1])], tp += d;

      d = d1[U(tp[-1])], tp += d;

      d = d1[U(tp[-1])], tp += d;

      if (d == 0)

        goto found;

      d = d1[U(tp[-1])], tp += d;

      d = d1[U(tp[-1])], tp += d;

      d = d1[U(tp[-1])], tp += d;

      if (d == 0)

        goto found;

      d = d1[U(tp[-1])], tp += d;

      d = d1[U(tp[-1])], tp += d;

    }

  break;

      found:

  if (U(tp[-2]) == gc)

    {

      for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)

        ;

      if (i > len)

        return tp - len - text;

    }

  tp += md2;

      }

  /* Now we have only a few characters left to search.  We

     carefully avoid ever producing an out-of-bounds pointer. */

  ep = text + size;

  d = d1[U(tp[-1])];

  while (d <= ep - tp)

    {

      d = d1[U((tp += d)[-1])];

      if (d != 0)

  continue;

      if (U(tp[-2]) == gc)

  {

    for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)

      ;

    if (i > len)

      return tp - len - text;

  }

      d = md2;

    }

  return -1;

}

/* Hairy multiple string search. */

static size_t

cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)

{

  struct kwset const *kwset;

  struct trie * const *next;

  struct trie const *trie;

  struct trie const *accept;

  char const *beg, *lim, *mch, *lmch;

  register unsigned char c;

  register unsigned char const *delta;

  register int d;

  register char const *end, *qlim;

  register struct tree const *tree;

  register unsigned char const *trans;

  accept = NULL;

  /* Initialize register copies and look for easy ways out. */

  kwset = (struct kwset *) kws;

  if (len < kwset->mind)

    return -1;

  next = kwset->next;

  delta = kwset->delta;

  trans = kwset->trans;

  lim = text + len;

  end = text;

  if ((d = kwset->mind) != 0)

    mch = NULL;

  else

    {

      mch = text, accept = kwset->trie;

      goto match;

    }

  if (len >= 4 * kwset->mind)

    qlim = lim - 4 * kwset->mind;

  else

    qlim = NULL;

  while (lim - end >= d)

    {

      if (qlim && end <= qlim)

  {

    end += d - 1;

    while ((d = delta[c = *end]) && end < qlim)

      {

        end += d;

        end += delta[U(*end)];

        end += delta[U(*end)];

      }

    ++end;

  }

      else

  d = delta[c = (end += d)[-1]];

      if (d)

  continue;

      beg = end - 1;

      trie = next[c];

      if (trie->accepting)

  {

    mch = beg;

    accept = trie;

  }

      d = trie->shift;

      while (beg > text)

  {

    c = trans ? trans[U(*--beg)] : *--beg;

    tree = trie->links;

    while (tree && c != tree->label)

      if (c < tree->label)

        tree = tree->llink;

      else

        tree = tree->rlink;

    if (tree)

      {

        trie = tree->trie;

        if (trie->accepting)

    {

      mch = beg;

      accept = trie;

    }

      }

    else

      break;

    d = trie->shift;

  }

      if (mch)

  goto match;

    }

  return -1;

 match:

  /* Given a known match, find the longest possible match anchored

     at or before its starting point.  This is nearly a verbatim

     copy of the preceding main search loops. */

  if (lim - mch > kwset->maxd)

    lim = mch + kwset->maxd;

  lmch = NULL;

  d = 1;

  while (lim - end >= d)

    {

      if ((d = delta[c = (end += d)[-1]]) != 0)

  continue;

      beg = end - 1;

      if (!(trie = next[c]))

  {

    d = 1;

    continue;

  }

      if (trie->accepting && beg <= mch)

  {

    lmch = beg;

    accept = trie;

  }

      d = trie->shift;

      while (beg > text)

  {

    c = trans ? trans[U(*--beg)] : *--beg;

    tree = trie->links;

    while (tree && c != tree->label)

      if (c < tree->label)

        tree = tree->llink;

      else

        tree = tree->rlink;

    if (tree)

      {

        trie = tree->trie;

        if (trie->accepting && beg <= mch)

    {

      lmch = beg;

      accept = trie;

    }

      }

    else

      break;

    d = trie->shift;

  }

      if (lmch)

  {

    mch = lmch;

    goto match;

  }

      if (!d)

  d = 1;

    }

  if (kwsmatch)

    {

      kwsmatch->index = accept->accepting / 2;

      kwsmatch->offset[0] = mch - text;

      kwsmatch->size[0] = accept->depth;

    }

  return mch - text;

}

/* Search through the given text for a match of any member of the

   given keyword set.  Return a pointer to the first character of

   the matching substring, or NULL if no match is found.  If FOUNDLEN

   is non-NULL store in the referenced location the length of the

   matching substring.  Similarly, if FOUNDIDX is non-NULL, store

   in the referenced location the index number of the particular

   keyword matched. */

size_t

kwsexec (kwset_t kws, char const *text, size_t size,

   struct kwsmatch *kwsmatch)

{

  struct kwset const *kwset = (struct kwset *) kws;

  if (kwset->words == 1 && kwset->trans == NULL)

    {

      size_t ret = bmexec (kws, text, size);

      if (kwsmatch != NULL && ret != (size_t) -1)

  {

    kwsmatch->index = 0;

    kwsmatch->offset[0] = ret;

    kwsmatch->size[0] = kwset->mind;

  }

      return ret;

    }

  else

    return cwexec(kws, text, size, kwsmatch);

}

/* Free the components of the given keyword set. */

void

kwsfree (kwset_t kws)

{

  struct kwset *kwset;

  kwset = (struct kwset *) kws;

  obstack_free(&kwset->obstack, NULL);

  free(kws);

}