[bug #14060] Max one keyword is used for multiple string patterns - results in poor performance

[Johannes T. Prinz]

URL:
  <http://savannah.gnu.org/bugs/?func=detailitem&item_id=14060>

                 Summary: Max one keyword is used for multiple string patterns
- results in poor performance
                 Project: grep
            Submitted by: purple
            Submitted on: Sun 08/07/2005 at 19:39
                Category: None
                Severity: 3 - Normal
              Item Group: None
                  Status: None
                 Privacy: Public
             Assigned to: None
             Open/Closed: Open

    _______________________________________________________

Details:

When searching patterns like e.g. "Bloom|Dedalus" or in general "s1|s2|.." the
fast commentz-walter algorithm is not used at all.

Analyzing the source code shows that in function dfamust() in dfa.c one string
at maximum (!) is computed as keyword for dfa->must (s. attached code
excerpt). So all string pattern matching in kwset.c uses at maximum one
string.


excerpt from dfamust():

..
done:
  if (strlen(result))
    {
      MALLOC(dm, struct dfamust, 1);
      dm->exact = exact;
      MALLOC(dm->must, char, strlen(result) + 1);
      strcpy(dm->must, result);
      dm->next = dfa->musts;
      dfa->musts = dm;
    }
  mp = musts;
  for (i = 0; i <= dfa->tindex; ++i)
    {
      freelist(mp[i].in);
      ifree((char *) mp[i].in);
      ifree(mp[i].left);
      ifree(mp[i].right);
      ifree(mp[i].is);
    }
  free((char *) mp);
}

..



    _______________________________________________________

Carbon-Copy List:

CC Address                          | Comment
------------------------------------+-----------------------------
address@hidden          | 




    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?func=detailitem&item_id=14060>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/