+/*
+ * 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.
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 resemblence
+/* 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
String Matching: An Aid to Bibliographic Search," CACM June 1975,
Vol. 18, No. 6, which describes the failure function used below. */
-#ifdef HAVE_CONFIG_H
-# include <config.h>
-#endif
-#include <sys/types.h>
-#include "system.h"
-#include "kwset.h"
-#include "obstack.h"
+#include "cache.h"
-#ifdef GREP
-extern char *xmalloc();
-# undef malloc
-# define malloc xmalloc
-#endif
+#include "kwset.h"
+#include "compat/obstack.h"
#define NCHAR (UCHAR_MAX + 1)
-#define obstack_chunk_alloc malloc
+#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
#define U(c) ((unsigned char) (c))
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 descendents. */
+ int maxshift; /* Max shift of self and descendants. */
};
/* Structure returned opaquely to the caller, containing everything. */
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. */
- char const *trans; /* Character translation table. */
+ 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 (char const *trans)
+kwsalloc (unsigned char const *trans)
{
struct kwset *kwset;
- kwset = (struct kwset *) malloc(sizeof (struct kwset));
- if (!kwset)
- return NULL;
+ kwset = (struct kwset *) xmalloc(sizeof (struct kwset));
obstack_init(&kwset->obstack);
kwset->words = 0;
link = (struct tree *) obstack_alloc(&kwset->obstack,
sizeof (struct tree));
if (!link)
- return _("memory exhausted");
+ return "memory exhausted";
link->llink = NULL;
link->rlink = NULL;
link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
if (!link->trie)
{
obstack_free(&kwset->obstack, link);
- return _("memory exhausted");
+ return "memory exhausted";
}
link->trie->accepting = 0;
link->trie->links = NULL;
treefails(tree->rlink, fail, recourse);
/* Find, in the chain of fails going back to the root, the first
- node that has a descendent on the current label. */
+ node that has a descendant on the current label. */
while (fail)
{
link = fail->links;
register struct kwset *kwset;
register int i;
register struct trie *curr;
- register char const *trans;
+ register unsigned char const *trans;
unsigned char delta[NCHAR];
kwset = (struct kwset *) kws;
/* Looking for just one string. Extract it from the trie. */
kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
if (!kwset->target)
- return _("memory exhausted");
+ return "memory exhausted";
for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
{
kwset->target[i] = curr->links->label;
computing the delta table, failure function, and shift function. */
for (curr = last = kwset->trie; curr; curr = curr->next)
{
- /* Enqueue the immediate descendents in the level order queue. */
+ /* 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 descendents of this node. */
+ /* Update the delta table for the descendants of this node. */
treedelta(curr->links, curr->depth, delta);
- /* Compute the failure function for the decendents of this node. */
+ /* 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
fail->shift = curr->depth - fail->depth;
/* If the current node is accepting then the shift at the
- fail and its descendents should be no larger than 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;
register int d;
register char const *end, *qlim;
register struct tree const *tree;
- register char const *trans;
+ register unsigned char const *trans;
-#ifdef lint
accept = NULL;
-#endif
/* Initialize register copies and look for easy ways out. */
kwset = (struct kwset *) kws;
copy of the preceding main search loops. */
if (lim - mch > kwset->maxd)
lim = mch + kwset->maxd;
- lmch = 0;
+ lmch = NULL;
d = 1;
while (lim - end >= d)
{