{"thread":{"id":"28179","subject":"[PATCH v2 1/5] Add obstack.[ch] from EGLIBC 2.10","startedAt":"2011-08-20T22:40:40Z","lastAt":"2011-08-28T11:31:49Z","messageCount":7,"participants":["Fredrik Kuivinen","Paolo Bonzini"],"isPatch":true,"patchVersion":2,"patchTotal":5},"messages":[{"id":"173943","messageId":"20110820224040.GB2199@fredrik-Q430-Q530","threadId":"28179","inReplyTo":"20110820223032.12380.72469.stgit@localhost6.localdomain6","subject":"[PATCH v2 1/5] Add obstack.[ch] from EGLIBC 2.10","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2011-08-20T22:40:40Z","receivedAt":"2011-08-20T22:40:40Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"\n\nSigned-off-by: Fredrik Kuivinen \n---\n Makefile | 2 \n compat/obstack.c | 441 +++++++++++++++++++++++++++++++++++++++++++++++\n compat/obstack.h | 509 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 3 files changed, 952 insertions(+), 0 deletions(-)\n create mode 100644 compat/obstack.c\n create mode 100644 compat/obstack.h\n\ndiff --git a/Makefile b/Makefile\nindex 89cc624..4cd061f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -514,6 +514,7 @@ LIB_H += commit.h\n LIB_H += compat/bswap.h\n LIB_H += compat/cygwin.h\n LIB_H += compat/mingw.h\n+LIB_H += compat/obstack.h\n LIB_H += compat/win32/pthread.h\n LIB_H += compat/win32/syslog.h\n LIB_H += compat/win32/sys/poll.h\n@@ -593,6 +594,7 @@ LIB_OBJS += cache-tree.o\n LIB_OBJS += color.o\n LIB_OBJS += combine-diff.o\n LIB_OBJS += commit.o\n+LIB_OBJS += compat/obstack.o\n LIB_OBJS += config.o\n LIB_OBJS += connect.o\n LIB_OBJS += convert.o\ndiff --git a/compat/obstack.c b/compat/obstack.c\nnew file mode 100644\nindex 0000000..75440d9\n--- /dev/null\n+++ b/compat/obstack.c\n@@ -0,0 +1,441 @@\n+/* obstack.c - subroutines used implicitly by object stack macros\n+ Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998,\n+ 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.\n+ This file is part of the GNU C Library.\n+\n+ The GNU C Library is free software; you can redistribute it and/or\n+ modify it under the terms of the GNU Lesser General Public\n+ License as published by the Free Software Foundation; either\n+ version 2.1 of the License, or (at your option) any later version.\n+\n+ The GNU C Library is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public\n+ License along with the GNU C Library; if not, write to the Free\n+ Software Foundation, Inc., 51 Franklin Street, Fifth Floor,\n+ Boston, MA 02110-1301, USA. */\n+\n+\n+#ifdef HAVE_CONFIG_H\n+# include \n+#endif\n+\n+#ifdef _LIBC\n+# include \n+# include \n+#else\n+# include \"obstack.h\"\n+#endif\n+\n+/* NOTE BEFORE MODIFYING THIS FILE: This version number must be\n+ incremented whenever callers compiled using an old obstack.h can no\n+ longer properly call the functions in this obstack.c. */\n+#define OBSTACK_INTERFACE_VERSION 1\n+\n+/* Comment out all this code if we are using the GNU C Library, and are not\n+ actually compiling the library itself, and the installed library\n+ supports the same library interface we do. This code is part of the GNU\n+ C Library, but also included in many other GNU distributions. Compiling\n+ and linking in this code is a waste when using the GNU C library\n+ (especially if it is a shared library). Rather than having every GNU\n+ program understand `configure --with-gnu-libc' and omit the object\n+ files, it is simpler to just do this in the source for each such file. */\n+\n+#include \t\t/* Random thing to get __GNU_LIBRARY__. */\n+#if !defined _LIBC && defined __GNU_LIBRARY__ && __GNU_LIBRARY__ > 1\n+# include \n+# if _GNU_OBSTACK_INTERFACE_VERSION == OBSTACK_INTERFACE_VERSION\n+# define ELIDE_CODE\n+# endif\n+#endif\n+\n+#include \n+\n+#ifndef ELIDE_CODE\n+\n+\n+# if HAVE_INTTYPES_H\n+# include \n+# endif\n+# if HAVE_STDINT_H || defined _LIBC\n+# include \n+# endif\n+\n+/* Determine default alignment. */\n+union fooround\n+{\n+ uintmax_t i;\n+ long double d;\n+ void *p;\n+};\n+struct fooalign\n+{\n+ char c;\n+ union fooround u;\n+};\n+/* If malloc were really smart, it would round addresses to DEFAULT_ALIGNMENT.\n+ But in fact it might be less smart and round addresses to as much as\n+ DEFAULT_ROUNDING. So we prepare for it to do that. */\n+enum\n+ {\n+ DEFAULT_ALIGNMENT = offsetof (struct fooalign, u),\n+ DEFAULT_ROUNDING = sizeof (union fooround)\n+ };\n+\n+/* When we copy a long block of data, this is the unit to do it with.\n+ On some machines, copying successive ints does not work;\n+ in such a case, redefine COPYING_UNIT to `long' (if that works)\n+ or `char' as a last resort. */\n+# ifndef COPYING_UNIT\n+# define COPYING_UNIT int\n+# endif\n+\n+\n+/* The functions allocating more room by calling `obstack_chunk_alloc'\n+ jump to the handler pointed to by `obstack_alloc_failed_handler'.\n+ This can be set to a user defined function which should either\n+ abort gracefully or use longjump - but shouldn't return. This\n+ variable by default points to the internal function\n+ `print_and_abort'. */\n+static void print_and_abort (void);\n+void (*obstack_alloc_failed_handler) (void) = print_and_abort;\n+\n+/* Exit value used when `print_and_abort' is used. */\n+# include \n+# ifdef _LIBC\n+int obstack_exit_failure = EXIT_FAILURE;\n+# else\n+# include \"exitfail.h\"\n+# define obstack_exit_failure exit_failure\n+# endif\n+\n+# ifdef _LIBC\n+# if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)\n+/* A looong time ago (before 1994, anyway; we're not sure) this global variable\n+ was used by non-GNU-C macros to avoid multiple evaluation. The GNU C\n+ library still exports it because somebody might use it. */\n+struct obstack *_obstack_compat;\n+compat_symbol (libc, _obstack_compat, _obstack, GLIBC_2_0);\n+# endif\n+# endif\n+\n+/* Define a macro that either calls functions with the traditional malloc/free\n+ calling interface, or calls functions with the mmalloc/mfree interface\n+ (that adds an extra first argument), based on the state of use_extra_arg.\n+ For free, do not use ?:, since some compilers, like the MIPS compilers,\n+ do not allow (expr) ? void : void. */\n+\n+# define CALL_CHUNKFUN(h, size) \\\n+ (((h) -> use_extra_arg) \\\n+ ? (*(h)->chunkfun) ((h)->extra_arg, (size)) \\\n+ : (*(struct _obstack_chunk *(*) (long)) (h)->chunkfun) ((size)))\n+\n+# define CALL_FREEFUN(h, old_chunk) \\\n+ do { \\\n+ if ((h) -> use_extra_arg) \\\n+ (*(h)->freefun) ((h)->extra_arg, (old_chunk)); \\\n+ else \\\n+ (*(void (*) (void *)) (h)->freefun) ((old_chunk)); \\\n+ } while (0)\n+\n+\f\n+/* Initialize an obstack H for use. Specify chunk size SIZE (0 means default).\n+ Objects start on multiples of ALIGNMENT (0 means use default).\n+ CHUNKFUN is the function to use to allocate chunks,\n+ and FREEFUN the function to free them.\n+\n+ Return nonzero if successful, calls obstack_alloc_failed_handler if\n+ allocation fails. */\n+\n+int\n+_obstack_begin (struct obstack *h,\n+\t\tint size, int alignment,\n+\t\tvoid *(*chunkfun) (long),\n+\t\tvoid (*freefun) (void *))\n+{\n+ register struct _obstack_chunk *chunk; /* points to new chunk */\n+\n+ if (alignment == 0)\n+ alignment = DEFAULT_ALIGNMENT;\n+ if (size == 0)\n+ /* Default size is what GNU malloc can fit in a 4096-byte block. */\n+ {\n+ /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.\n+\t Use the values for range checking, because if range checking is off,\n+\t the extra bytes won't be missed terribly, but if range checking is on\n+\t and we used a larger request, a whole extra 4096 bytes would be\n+\t allocated.\n+\n+\t These number are irrelevant to the new GNU malloc. I suspect it is\n+\t less sensitive to the size of the request. */\n+ int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))\n+\t\t + 4 + DEFAULT_ROUNDING - 1)\n+\t\t & ~(DEFAULT_ROUNDING - 1));\n+ size = 4096 - extra;\n+ }\n+\n+ h->chunkfun = (struct _obstack_chunk * (*)(void *, long)) chunkfun;\n+ h->freefun = (void (*) (void *, struct _obstack_chunk *)) freefun;\n+ h->chunk_size = size;\n+ h->alignment_mask = alignment - 1;\n+ h->use_extra_arg = 0;\n+\n+ chunk = h->chunk = CALL_CHUNKFUN (h, h -> chunk_size);\n+ if (!chunk)\n+ (*obstack_alloc_failed_handler) ();\n+ h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,\n+\t\t\t\t\t alignment - 1);\n+ h->chunk_limit = chunk->limit\n+ = (char *) chunk + h->chunk_size;\n+ chunk->prev = 0;\n+ /* The initial chunk now contains no empty object. */\n+ h->maybe_empty_object = 0;\n+ h->alloc_failed = 0;\n+ return 1;\n+}\n+\n+int\n+_obstack_begin_1 (struct obstack *h, int size, int alignment,\n+\t\t void *(*chunkfun) (void *, long),\n+\t\t void (*freefun) (void *, void *),\n+\t\t void *arg)\n+{\n+ register struct _obstack_chunk *chunk; /* points to new chunk */\n+\n+ if (alignment == 0)\n+ alignment = DEFAULT_ALIGNMENT;\n+ if (size == 0)\n+ /* Default size is what GNU malloc can fit in a 4096-byte block. */\n+ {\n+ /* 12 is sizeof (mhead) and 4 is EXTRA from GNU malloc.\n+\t Use the values for range checking, because if range checking is off,\n+\t the extra bytes won't be missed terribly, but if range checking is on\n+\t and we used a larger request, a whole extra 4096 bytes would be\n+\t allocated.\n+\n+\t These number are irrelevant to the new GNU malloc. I suspect it is\n+\t less sensitive to the size of the request. */\n+ int extra = ((((12 + DEFAULT_ROUNDING - 1) & ~(DEFAULT_ROUNDING - 1))\n+\t\t + 4 + DEFAULT_ROUNDING - 1)\n+\t\t & ~(DEFAULT_ROUNDING - 1));\n+ size = 4096 - extra;\n+ }\n+\n+ h->chunkfun = (struct _obstack_chunk * (*)(void *,long)) chunkfun;\n+ h->freefun = (void (*) (void *, struct _obstack_chunk *)) freefun;\n+ h->chunk_size = size;\n+ h->alignment_mask = alignment - 1;\n+ h->extra_arg = arg;\n+ h->use_extra_arg = 1;\n+\n+ chunk = h->chunk = CALL_CHUNKFUN (h, h -> chunk_size);\n+ if (!chunk)\n+ (*obstack_alloc_failed_handler) ();\n+ h->next_free = h->object_base = __PTR_ALIGN ((char *) chunk, chunk->contents,\n+\t\t\t\t\t alignment - 1);\n+ h->chunk_limit = chunk->limit\n+ = (char *) chunk + h->chunk_size;\n+ chunk->prev = 0;\n+ /* The initial chunk now contains no empty object. */\n+ h->maybe_empty_object = 0;\n+ h->alloc_failed = 0;\n+ return 1;\n+}\n+\n+/* Allocate a new current chunk for the obstack *H\n+ on the assumption that LENGTH bytes need to be added\n+ to the current object, or a new object of length LENGTH allocated.\n+ Copies any partial object from the end of the old chunk\n+ to the beginning of the new one. */\n+\n+void\n+_obstack_newchunk (struct obstack *h, int length)\n+{\n+ register struct _obstack_chunk *old_chunk = h->chunk;\n+ register struct _obstack_chunk *new_chunk;\n+ register long\tnew_size;\n+ register long obj_size = h->next_free - h->object_base;\n+ register long i;\n+ long already;\n+ char *object_base;\n+\n+ /* Compute size for new chunk. */\n+ new_size = (obj_size + length) + (obj_size >> 3) + h->alignment_mask + 100;\n+ if (new_size < h->chunk_size)\n+ new_size = h->chunk_size;\n+\n+ /* Allocate and initialize the new chunk. */\n+ new_chunk = CALL_CHUNKFUN (h, new_size);\n+ if (!new_chunk)\n+ (*obstack_alloc_failed_handler) ();\n+ h->chunk = new_chunk;\n+ new_chunk->prev = old_chunk;\n+ new_chunk->limit = h->chunk_limit = (char *) new_chunk + new_size;\n+\n+ /* Compute an aligned object_base in the new chunk */\n+ object_base =\n+ __PTR_ALIGN ((char *) new_chunk, new_chunk->contents, h->alignment_mask);\n+\n+ /* Move the existing object to the new chunk.\n+ Word at a time is fast and is safe if the object\n+ is sufficiently aligned. */\n+ if (h->alignment_mask + 1 >= DEFAULT_ALIGNMENT)\n+ {\n+ for (i = obj_size / sizeof (COPYING_UNIT) - 1;\n+\t i >= 0; i--)\n+\t((COPYING_UNIT *)object_base)[i]\n+\t = ((COPYING_UNIT *)h->object_base)[i];\n+ /* We used to copy the odd few remaining bytes as one extra COPYING_UNIT,\n+\t but that can cross a page boundary on a machine\n+\t which does not do strict alignment for COPYING_UNITS. */\n+ already = obj_size / sizeof (COPYING_UNIT) * sizeof (COPYING_UNIT);\n+ }\n+ else\n+ already = 0;\n+ /* Copy remaining bytes one by one. */\n+ for (i = already; i < obj_size; i++)\n+ object_base[i] = h->object_base[i];\n+\n+ /* If the object just copied was the only data in OLD_CHUNK,\n+ free that chunk and remove it from the chain.\n+ But not if that chunk might contain an empty object. */\n+ if (! h->maybe_empty_object\n+ && (h->object_base\n+\t == __PTR_ALIGN ((char *) old_chunk, old_chunk->contents,\n+\t\t\t h->alignment_mask)))\n+ {\n+ new_chunk->prev = old_chunk->prev;\n+ CALL_FREEFUN (h, old_chunk);\n+ }\n+\n+ h->object_base = object_base;\n+ h->next_free = h->object_base + obj_size;\n+ /* The new chunk certainly contains no empty object yet. */\n+ h->maybe_empty_object = 0;\n+}\n+# ifdef _LIBC\n+libc_hidden_def (_obstack_newchunk)\n+# endif\n+\n+/* Return nonzero if object OBJ has been allocated from obstack H.\n+ This is here for debugging.\n+ If you use it in a program, you are probably losing. */\n+\n+/* Suppress -Wmissing-prototypes warning. We don't want to declare this in\n+ obstack.h because it is just for debugging. */\n+int _obstack_allocated_p (struct obstack *h, void *obj);\n+\n+int\n+_obstack_allocated_p (struct obstack *h, void *obj)\n+{\n+ register struct _obstack_chunk *lp;\t/* below addr of any objects in this chunk */\n+ register struct _obstack_chunk *plp;\t/* point to previous chunk if any */\n+\n+ lp = (h)->chunk;\n+ /* We use >= rather than > since the object cannot be exactly at\n+ the beginning of the chunk but might be an empty object exactly\n+ at the end of an adjacent chunk. */\n+ while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))\n+ {\n+ plp = lp->prev;\n+ lp = plp;\n+ }\n+ return lp != 0;\n+}\n+\f\n+/* Free objects in obstack H, including OBJ and everything allocate\n+ more recently than OBJ. If OBJ is zero, free everything in H. */\n+\n+# undef obstack_free\n+\n+void\n+obstack_free (struct obstack *h, void *obj)\n+{\n+ register struct _obstack_chunk *lp;\t/* below addr of any objects in this chunk */\n+ register struct _obstack_chunk *plp;\t/* point to previous chunk if any */\n+\n+ lp = h->chunk;\n+ /* We use >= because there cannot be an object at the beginning of a chunk.\n+ But there can be an empty object at that address\n+ at the end of another chunk. */\n+ while (lp != 0 && ((void *) lp >= obj || (void *) (lp)->limit < obj))\n+ {\n+ plp = lp->prev;\n+ CALL_FREEFUN (h, lp);\n+ lp = plp;\n+ /* If we switch chunks, we can't tell whether the new current\n+\t chunk contains an empty object, so assume that it may. */\n+ h->maybe_empty_object = 1;\n+ }\n+ if (lp)\n+ {\n+ h->object_base = h->next_free = (char *) (obj);\n+ h->chunk_limit = lp->limit;\n+ h->chunk = lp;\n+ }\n+ else if (obj != 0)\n+ /* obj is not in any of the chunks! */\n+ abort ();\n+}\n+\n+# ifdef _LIBC\n+/* Older versions of libc used a function _obstack_free intended to be\n+ called by non-GCC compilers. */\n+strong_alias (obstack_free, _obstack_free)\n+# endif\n+\f\n+int\n+_obstack_memory_used (struct obstack *h)\n+{\n+ register struct _obstack_chunk* lp;\n+ register int nbytes = 0;\n+\n+ for (lp = h->chunk; lp != 0; lp = lp->prev)\n+ {\n+ nbytes += lp->limit - (char *) lp;\n+ }\n+ return nbytes;\n+}\n+\f\n+/* Define the error handler. */\n+# ifdef _LIBC\n+# include \n+# else\n+# include \"gettext.h\"\n+# endif\n+# ifndef _\n+# define _(msgid) gettext (msgid)\n+# endif\n+\n+# ifdef _LIBC\n+# include \n+# endif\n+\n+# ifndef __attribute__\n+/* This feature is available in gcc versions 2.5 and later. */\n+# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 5)\n+# define __attribute__(Spec) /* empty */\n+# endif\n+# endif\n+\n+static void\n+__attribute__ ((noreturn))\n+print_and_abort (void)\n+{\n+ /* Don't change any of these strings. Yes, it would be possible to add\n+ the newline to the string and use fputs or so. But this must not\n+ happen because the \"memory exhausted\" message appears in other places\n+ like this and the translation should be reused instead of creating\n+ a very similar string which requires a separate translation. */\n+# ifdef _LIBC\n+ (void) __fxprintf (NULL, \"%s\\n\", _(\"memory exhausted\"));\n+# else\n+ fprintf (stderr, \"%s\\n\", _(\"memory exhausted\"));\n+# endif\n+ exit (obstack_exit_failure);\n+}\n+\n+#endif\t/* !ELIDE_CODE */\ndiff --git a/compat/obstack.h b/compat/obstack.h\nnew file mode 100644\nindex 0000000..449070e\n--- /dev/null\n+++ b/compat/obstack.h\n@@ -0,0 +1,509 @@\n+/* obstack.h - object stack macros\n+ Copyright (C) 1988-1994,1996-1999,2003,2004,2005,2009\n+\tFree Software Foundation, Inc.\n+ This file is part of the GNU C Library.\n+\n+ The GNU C Library is free software; you can redistribute it and/or\n+ modify it under the terms of the GNU Lesser General Public\n+ License as published by the Free Software Foundation; either\n+ version 2.1 of the License, or (at your option) any later version.\n+\n+ The GNU C Library is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU\n+ Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public\n+ License along with the GNU C Library; if not, write to the Free\n+ Software Foundation, Inc., 51 Franklin Street, Fifth Floor,\n+ Boston, MA 02110-1301, USA. */\n+\n+/* Summary:\n+\n+All the apparent functions defined here are macros. The idea\n+is that you would use these pre-tested macros to solve a\n+very specific set of problems, and they would run fast.\n+Caution: no side-effects in arguments please!! They may be\n+evaluated MANY times!!\n+\n+These macros operate a stack of objects. Each object starts life\n+small, and may grow to maturity. (Consider building a word syllable\n+by syllable.) An object can move while it is growing. Once it has\n+been \"finished\" it never changes address again. So the \"top of the\n+stack\" is typically an immature growing object, while the rest of the\n+stack is of mature, fixed size and fixed address objects.\n+\n+These routines grab large chunks of memory, using a function you\n+supply, called `obstack_chunk_alloc'. On occasion, they free chunks,\n+by calling `obstack_chunk_free'. You must define them and declare\n+them before using any obstack macros.\n+\n+Each independent stack is represented by a `struct obstack'.\n+Each of the obstack macros expects a pointer to such a structure\n+as the first argument.\n+\n+One motivation for this package is the problem of growing char strings\n+in symbol tables. Unless you are \"fascist pig with a read-only mind\"\n+--Gosper's immortal quote from HAKMEM item 154, out of context--you\n+would not like to put any arbitrary upper limit on the length of your\n+symbols.\n+\n+In practice this often means you will build many short symbols and a\n+few long symbols. At the time you are reading a symbol you don't know\n+how long it is. One traditional method is to read a symbol into a\n+buffer, realloc()ating the buffer every time you try to read a symbol\n+that is longer than the buffer. This is beaut, but you still will\n+want to copy the symbol from the buffer to a more permanent\n+symbol-table entry say about half the time.\n+\n+With obstacks, you can work differently. Use one obstack for all symbol\n+names. As you read a symbol, grow the name in the obstack gradually.\n+When the name is complete, finalize it. Then, if the symbol exists already,\n+free the newly read name.\n+\n+The way we do this is to take a large chunk, allocating memory from\n+low addresses. When you want to build a symbol in the chunk you just\n+add chars above the current \"high water mark\" in the chunk. When you\n+have finished adding chars, because you got to the end of the symbol,\n+you know how long the chars are, and you can create a new object.\n+Mostly the chars will not burst over the highest address of the chunk,\n+because you would typically expect a chunk to be (say) 100 times as\n+long as an average object.\n+\n+In case that isn't clear, when we have enough chars to make up\n+the object, THEY ARE ALREADY CONTIGUOUS IN THE CHUNK (guaranteed)\n+so we just point to it where it lies. No moving of chars is\n+needed and this is the second win: potentially long strings need\n+never be explicitly shuffled. Once an object is formed, it does not\n+change its address during its lifetime.\n+\n+When the chars burst over a chunk boundary, we allocate a larger\n+chunk, and then copy the partly formed object from the end of the old\n+chunk to the beginning of the new larger chunk. We then carry on\n+accreting characters to the end of the object as we normally would.\n+\n+A special macro is provided to add a single char at a time to a\n+growing object. This allows the use of register variables, which\n+break the ordinary 'growth' macro.\n+\n+Summary:\n+\tWe allocate large chunks.\n+\tWe carve out one object at a time from the current chunk.\n+\tOnce carved, an object never moves.\n+\tWe are free to append data of any size to the currently\n+\t growing object.\n+\tExactly one object is growing in an obstack at any one time.\n+\tYou can run one obstack per control block.\n+\tYou may have as many control blocks as you dare.\n+\tBecause of the way we do it, you can `unwind' an obstack\n+\t back to a previous state. (You may remove objects much\n+\t as you would with a stack.)\n+*/\n+\n+\n+/* Don't do the contents of this file more than once. */\n+\n+#ifndef _OBSTACK_H\n+#define _OBSTACK_H 1\n+\n+#ifdef __cplusplus\n+extern \"C\" {\n+#endif\n+\f\n+/* We need the type of a pointer subtraction. If __PTRDIFF_TYPE__ is\n+ defined, as with GNU C, use that; that way we don't pollute the\n+ namespace with 's symbols. Otherwise, include \n+ and use ptrdiff_t. */\n+\n+#ifdef __PTRDIFF_TYPE__\n+# define PTR_INT_TYPE __PTRDIFF_TYPE__\n+#else\n+# include \n+# define PTR_INT_TYPE ptrdiff_t\n+#endif\n+\n+/* If B is the base of an object addressed by P, return the result of\n+ aligning P to the next multiple of A + 1. B and P must be of type\n+ char *. A + 1 must be a power of 2. */\n+\n+#define __BPTR_ALIGN(B, P, A) ((B) + (((P) - (B) + (A)) & ~(A)))\n+\n+/* Similiar to _BPTR_ALIGN (B, P, A), except optimize the common case\n+ where pointers can be converted to integers, aligned as integers,\n+ and converted back again. If PTR_INT_TYPE is narrower than a\n+ pointer (e.g., the AS/400), play it safe and compute the alignment\n+ relative to B. Otherwise, use the faster strategy of computing the\n+ alignment relative to 0. */\n+\n+#define __PTR_ALIGN(B, P, A)\t\t\t\t\t\t \\\n+ __BPTR_ALIGN (sizeof (PTR_INT_TYPE) < sizeof (void *) ? (B) : (char *) 0, \\\n+\t\tP, A)\n+\n+#include \n+\n+struct _obstack_chunk\t\t/* Lives at front of each chunk. */\n+{\n+ char *limit;\t\t\t/* 1 past end of this chunk */\n+ struct _obstack_chunk *prev;\t/* address of prior chunk or NULL */\n+ char\tcontents[4];\t\t/* objects begin here */\n+};\n+\n+struct obstack\t\t/* control current object in current chunk */\n+{\n+ long\tchunk_size;\t\t/* preferred size to allocate chunks in */\n+ struct _obstack_chunk *chunk;\t/* address of current struct obstack_chunk */\n+ char\t*object_base;\t\t/* address of object we are building */\n+ char\t*next_free;\t\t/* where to add next char to current object */\n+ char\t*chunk_limit;\t\t/* address of char after current chunk */\n+ union\n+ {\n+ PTR_INT_TYPE tempint;\n+ void *tempptr;\n+ } temp;\t\t\t/* Temporary for some macros. */\n+ int alignment_mask;\t\t/* Mask of alignment for each object. */\n+ /* These prototypes vary based on `use_extra_arg', and we use\n+ casts to the prototypeless function type in all assignments,\n+ but having prototypes here quiets -Wstrict-prototypes. */\n+ struct _obstack_chunk *(*chunkfun) (void *, long);\n+ void (*freefun) (void *, struct _obstack_chunk *);\n+ void *extra_arg;\t\t/* first arg for chunk alloc/dealloc funcs */\n+ unsigned use_extra_arg:1;\t/* chunk alloc/dealloc funcs take extra arg */\n+ unsigned maybe_empty_object:1;/* There is a possibility that the current\n+\t\t\t\t chunk contains a zero-length object. This\n+\t\t\t\t prevents freeing the chunk if we allocate\n+\t\t\t\t a bigger chunk to replace it. */\n+ unsigned alloc_failed:1;\t/* No longer used, as we now call the failed\n+\t\t\t\t handler on error, but retained for binary\n+\t\t\t\t compatibility. */\n+};\n+\n+/* Declare the external functions we use; they are in obstack.c. */\n+\n+extern void _obstack_newchunk (struct obstack *, int);\n+extern int _obstack_begin (struct obstack *, int, int,\n+\t\t\t void *(*) (long), void (*) (void *));\n+extern int _obstack_begin_1 (struct obstack *, int, int,\n+\t\t\t void *(*) (void *, long),\n+\t\t\t void (*) (void *, void *), void *);\n+extern int _obstack_memory_used (struct obstack *);\n+\n+void obstack_free (struct obstack *__obstack, void *__block);\n+\n+\f\n+/* Error handler called when `obstack_chunk_alloc' failed to allocate\n+ more memory. This can be set to a user defined function which\n+ should either abort gracefully or use longjump - but shouldn't\n+ return. The default action is to print a message and abort. */\n+extern void (*obstack_alloc_failed_handler) (void);\n+\n+/* Exit value used when `print_and_abort' is used. */\n+extern int obstack_exit_failure;\n+\f\n+/* Pointer to beginning of object being allocated or to be allocated next.\n+ Note that this might not be the final address of the object\n+ because a new chunk might be needed to hold the final size. */\n+\n+#define obstack_base(h) ((void *) (h)->object_base)\n+\n+/* Size for allocating ordinary chunks. */\n+\n+#define obstack_chunk_size(h) ((h)->chunk_size)\n+\n+/* Pointer to next byte not yet allocated in current chunk. */\n+\n+#define obstack_next_free(h)\t((h)->next_free)\n+\n+/* Mask specifying low bits that should be clear in address of an object. */\n+\n+#define obstack_alignment_mask(h) ((h)->alignment_mask)\n+\n+/* To prevent prototype warnings provide complete argument list. */\n+#define obstack_init(h)\t\t\t\t\t\t\\\n+ _obstack_begin ((h), 0, 0,\t\t\t\t\t\\\n+\t\t (void *(*) (long)) obstack_chunk_alloc,\t\\\n+\t\t (void (*) (void *)) obstack_chunk_free)\n+\n+#define obstack_begin(h, size)\t\t\t\t\t\\\n+ _obstack_begin ((h), (size), 0,\t\t\t\t\\\n+\t\t (void *(*) (long)) obstack_chunk_alloc,\t\\\n+\t\t (void (*) (void *)) obstack_chunk_free)\n+\n+#define obstack_specify_allocation(h, size, alignment, chunkfun, freefun) \\\n+ _obstack_begin ((h), (size), (alignment),\t\t\t\t \\\n+\t\t (void *(*) (long)) (chunkfun),\t\t\t \\\n+\t\t (void (*) (void *)) (freefun))\n+\n+#define obstack_specify_allocation_with_arg(h, size, alignment, chunkfun, freefun, arg) \\\n+ _obstack_begin_1 ((h), (size), (alignment),\t\t\t\t\\\n+\t\t (void *(*) (void *, long)) (chunkfun),\t\t\\\n+\t\t (void (*) (void *, void *)) (freefun), (arg))\n+\n+#define obstack_chunkfun(h, newchunkfun) \\\n+ ((h) -> chunkfun = (struct _obstack_chunk *(*)(void *, long)) (newchunkfun))\n+\n+#define obstack_freefun(h, newfreefun) \\\n+ ((h) -> freefun = (void (*)(void *, struct _obstack_chunk *)) (newfreefun))\n+\n+#define obstack_1grow_fast(h,achar) (*((h)->next_free)++ = (achar))\n+\n+#define obstack_blank_fast(h,n) ((h)->next_free += (n))\n+\n+#define obstack_memory_used(h) _obstack_memory_used (h)\n+\f\n+#if defined __GNUC__ && defined __STDC__ && __STDC__\n+/* NextStep 2.0 cc is really gcc 1.93 but it defines __GNUC__ = 2 and\n+ does not implement __extension__. But that compiler doesn't define\n+ __GNUC_MINOR__. */\n+# if __GNUC__ < 2 || (__NeXT__ && !__GNUC_MINOR__)\n+# define __extension__\n+# endif\n+\n+/* For GNU C, if not -traditional,\n+ we can define these macros to compute all args only once\n+ without using a global variable.\n+ Also, we can avoid using the `temp' slot, to make faster code. */\n+\n+# define obstack_object_size(OBSTACK)\t\t\t\t\t\\\n+ __extension__\t\t\t\t\t\t\t\t\\\n+ ({ struct obstack const *__o = (OBSTACK);\t\t\t\t\\\n+ (unsigned) (__o->next_free - __o->object_base); })\n+\n+# define obstack_room(OBSTACK)\t\t\t\t\t\t\\\n+ __extension__\t\t\t\t\t\t\t\t\\\n+ ({ struct obstack const *__o = (OBSTACK);\t\t\t\t\\\n+ (unsigned) (__o->chunk_limit - __o->next_free); })\n+\n+# define obstack_make_room(OBSTACK,length)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ int __len = (length);\t\t\t\t\t\t\\\n+ if (__o->chunk_limit - __o->next_free < __len)\t\t\t\\\n+ _obstack_newchunk (__o, __len);\t\t\t\t\t\\\n+ (void) 0; })\n+\n+# define obstack_empty_p(OBSTACK)\t\t\t\t\t\\\n+ __extension__\t\t\t\t\t\t\t\t\\\n+ ({ struct obstack const *__o = (OBSTACK);\t\t\t\t\\\n+ (__o->chunk->prev == 0\t\t\t\t\t\t\\\n+ && __o->next_free == __PTR_ALIGN ((char *) __o->chunk,\t\t\\\n+\t\t\t\t\t__o->chunk->contents,\t\t\\\n+\t\t\t\t\t__o->alignment_mask)); })\n+\n+# define obstack_grow(OBSTACK,where,length)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ int __len = (length);\t\t\t\t\t\t\\\n+ if (__o->next_free + __len > __o->chunk_limit)\t\t\t\\\n+ _obstack_newchunk (__o, __len);\t\t\t\t\t\\\n+ memcpy (__o->next_free, where, __len);\t\t\t\t\\\n+ __o->next_free += __len;\t\t\t\t\t\t\\\n+ (void) 0; })\n+\n+# define obstack_grow0(OBSTACK,where,length)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ int __len = (length);\t\t\t\t\t\t\\\n+ if (__o->next_free + __len + 1 > __o->chunk_limit)\t\t\t\\\n+ _obstack_newchunk (__o, __len + 1);\t\t\t\t\\\n+ memcpy (__o->next_free, where, __len);\t\t\t\t\\\n+ __o->next_free += __len;\t\t\t\t\t\t\\\n+ *(__o->next_free)++ = 0;\t\t\t\t\t\t\\\n+ (void) 0; })\n+\n+# define obstack_1grow(OBSTACK,datum)\t\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ if (__o->next_free + 1 > __o->chunk_limit)\t\t\t\t\\\n+ _obstack_newchunk (__o, 1);\t\t\t\t\t\\\n+ obstack_1grow_fast (__o, datum);\t\t\t\t\t\\\n+ (void) 0; })\n+\n+/* These assume that the obstack alignment is good enough for pointers\n+ or ints, and that the data added so far to the current object\n+ shares that much alignment. */\n+\n+# define obstack_ptr_grow(OBSTACK,datum)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ if (__o->next_free + sizeof (void *) > __o->chunk_limit)\t\t\\\n+ _obstack_newchunk (__o, sizeof (void *));\t\t\t\t\\\n+ obstack_ptr_grow_fast (__o, datum); })\t\t\t\t\\\n+\n+# define obstack_int_grow(OBSTACK,datum)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ if (__o->next_free + sizeof (int) > __o->chunk_limit)\t\t\\\n+ _obstack_newchunk (__o, sizeof (int));\t\t\t\t\\\n+ obstack_int_grow_fast (__o, datum); })\n+\n+# define obstack_ptr_grow_fast(OBSTACK,aptr)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o1 = (OBSTACK);\t\t\t\t\t\\\n+ *(const void **) __o1->next_free = (aptr);\t\t\t\t\\\n+ __o1->next_free += sizeof (const void *);\t\t\t\t\\\n+ (void) 0; })\n+\n+# define obstack_int_grow_fast(OBSTACK,aint)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o1 = (OBSTACK);\t\t\t\t\t\\\n+ *(int *) __o1->next_free = (aint);\t\t\t\t\t\\\n+ __o1->next_free += sizeof (int);\t\t\t\t\t\\\n+ (void) 0; })\n+\n+# define obstack_blank(OBSTACK,length)\t\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ int __len = (length);\t\t\t\t\t\t\\\n+ if (__o->chunk_limit - __o->next_free < __len)\t\t\t\\\n+ _obstack_newchunk (__o, __len);\t\t\t\t\t\\\n+ obstack_blank_fast (__o, __len);\t\t\t\t\t\\\n+ (void) 0; })\n+\n+# define obstack_alloc(OBSTACK,length)\t\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__h = (OBSTACK);\t\t\t\t\t\\\n+ obstack_blank (__h, (length));\t\t\t\t\t\\\n+ obstack_finish (__h); })\n+\n+# define obstack_copy(OBSTACK,where,length)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__h = (OBSTACK);\t\t\t\t\t\\\n+ obstack_grow (__h, (where), (length));\t\t\t\t\\\n+ obstack_finish (__h); })\n+\n+# define obstack_copy0(OBSTACK,where,length)\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__h = (OBSTACK);\t\t\t\t\t\\\n+ obstack_grow0 (__h, (where), (length));\t\t\t\t\\\n+ obstack_finish (__h); })\n+\n+/* The local variable is named __o1 to avoid a name conflict\n+ when obstack_blank is called. */\n+# define obstack_finish(OBSTACK)\t\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o1 = (OBSTACK);\t\t\t\t\t\\\n+ void *__value = (void *) __o1->object_base;\t\t\t\t\\\n+ if (__o1->next_free == __value)\t\t\t\t\t\\\n+ __o1->maybe_empty_object = 1;\t\t\t\t\t\\\n+ __o1->next_free\t\t\t\t\t\t\t\\\n+ = __PTR_ALIGN (__o1->object_base, __o1->next_free,\t\t\t\\\n+\t\t __o1->alignment_mask);\t\t\t\t\\\n+ if (__o1->next_free - (char *)__o1->chunk\t\t\t\t\\\n+ > __o1->chunk_limit - (char *)__o1->chunk)\t\t\t\\\n+ __o1->next_free = __o1->chunk_limit;\t\t\t\t\\\n+ __o1->object_base = __o1->next_free;\t\t\t\t\t\\\n+ __value; })\n+\n+# define obstack_free(OBSTACK, OBJ)\t\t\t\t\t\\\n+__extension__\t\t\t\t\t\t\t\t\\\n+({ struct obstack *__o = (OBSTACK);\t\t\t\t\t\\\n+ void *__obj = (OBJ);\t\t\t\t\t\t\t\\\n+ if (__obj > (void *)__o->chunk && __obj < (void *)__o->chunk_limit) \\\n+ __o->next_free = __o->object_base = (char *)__obj;\t\t\t\\\n+ else (obstack_free) (__o, __obj); })\n+\f\n+#else /* not __GNUC__ or not __STDC__ */\n+\n+# define obstack_object_size(h) \\\n+ (unsigned) ((h)->next_free - (h)->object_base)\n+\n+# define obstack_room(h)\t\t\\\n+ (unsigned) ((h)->chunk_limit - (h)->next_free)\n+\n+# define obstack_empty_p(h) \\\n+ ((h)->chunk->prev == 0\t\t\t\t\t\t\t\\\n+ && (h)->next_free == __PTR_ALIGN ((char *) (h)->chunk,\t\t\\\n+\t\t\t\t (h)->chunk->contents,\t\t\\\n+\t\t\t\t (h)->alignment_mask))\n+\n+/* Note that the call to _obstack_newchunk is enclosed in (..., 0)\n+ so that we can avoid having void expressions\n+ in the arms of the conditional expression.\n+ Casting the third operand to void was tried before,\n+ but some compilers won't accept it. */\n+\n+# define obstack_make_room(h,length)\t\t\t\t\t\\\n+( (h)->temp.tempint = (length),\t\t\t\t\t\t\\\n+ (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit)\t\t\\\n+ ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0))\n+\n+# define obstack_grow(h,where,length)\t\t\t\t\t\\\n+( (h)->temp.tempint = (length),\t\t\t\t\t\t\\\n+ (((h)->next_free + (h)->temp.tempint > (h)->chunk_limit)\t\t\\\n+ ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0),\t\t\\\n+ memcpy ((h)->next_free, where, (h)->temp.tempint),\t\t\t\\\n+ (h)->next_free += (h)->temp.tempint)\n+\n+# define obstack_grow0(h,where,length)\t\t\t\t\t\\\n+( (h)->temp.tempint = (length),\t\t\t\t\t\t\\\n+ (((h)->next_free + (h)->temp.tempint + 1 > (h)->chunk_limit)\t\t\\\n+ ? (_obstack_newchunk ((h), (h)->temp.tempint + 1), 0) : 0),\t\t\\\n+ memcpy ((h)->next_free, where, (h)->temp.tempint),\t\t\t\\\n+ (h)->next_free += (h)->temp.tempint,\t\t\t\t\t\\\n+ *((h)->next_free)++ = 0)\n+\n+# define obstack_1grow(h,datum)\t\t\t\t\t\t\\\n+( (((h)->next_free + 1 > (h)->chunk_limit)\t\t\t\t\\\n+ ? (_obstack_newchunk ((h), 1), 0) : 0),\t\t\t\t\\\n+ obstack_1grow_fast (h, datum))\n+\n+# define obstack_ptr_grow(h,datum)\t\t\t\t\t\\\n+( (((h)->next_free + sizeof (char *) > (h)->chunk_limit)\t\t\\\n+ ? (_obstack_newchunk ((h), sizeof (char *)), 0) : 0),\t\t\\\n+ obstack_ptr_grow_fast (h, datum))\n+\n+# define obstack_int_grow(h,datum)\t\t\t\t\t\\\n+( (((h)->next_free + sizeof (int) > (h)->chunk_limit)\t\t\t\\\n+ ? (_obstack_newchunk ((h), sizeof (int)), 0) : 0),\t\t\t\\\n+ obstack_int_grow_fast (h, datum))\n+\n+# define obstack_ptr_grow_fast(h,aptr)\t\t\t\t\t\\\n+ (((const void **) ((h)->next_free += sizeof (void *)))[-1] = (aptr))\n+\n+# define obstack_int_grow_fast(h,aint)\t\t\t\t\t\\\n+ (((int *) ((h)->next_free += sizeof (int)))[-1] = (aint))\n+\n+# define obstack_blank(h,length)\t\t\t\t\t\\\n+( (h)->temp.tempint = (length),\t\t\t\t\t\t\\\n+ (((h)->chunk_limit - (h)->next_free < (h)->temp.tempint)\t\t\\\n+ ? (_obstack_newchunk ((h), (h)->temp.tempint), 0) : 0),\t\t\\\n+ obstack_blank_fast (h, (h)->temp.tempint))\n+\n+# define obstack_alloc(h,length)\t\t\t\t\t\\\n+ (obstack_blank ((h), (length)), obstack_finish ((h)))\n+\n+# define obstack_copy(h,where,length)\t\t\t\t\t\\\n+ (obstack_grow ((h), (where), (length)), obstack_finish ((h)))\n+\n+# define obstack_copy0(h,where,length)\t\t\t\t\t\\\n+ (obstack_grow0 ((h), (where), (length)), obstack_finish ((h)))\n+\n+# define obstack_finish(h)\t\t\t\t\t\t\\\n+( ((h)->next_free == (h)->object_base\t\t\t\t\t\\\n+ ? (((h)->maybe_empty_object = 1), 0)\t\t\t\t\t\\\n+ : 0),\t\t\t\t\t\t\t\t\\\n+ (h)->temp.tempptr = (h)->object_base,\t\t\t\t\t\\\n+ (h)->next_free\t\t\t\t\t\t\t\\\n+ = __PTR_ALIGN ((h)->object_base, (h)->next_free,\t\t\t\\\n+\t\t (h)->alignment_mask),\t\t\t\t\\\n+ (((h)->next_free - (char *) (h)->chunk\t\t\t\t\\\n+ > (h)->chunk_limit - (char *) (h)->chunk)\t\t\t\t\\\n+ ? ((h)->next_free = (h)->chunk_limit) : 0),\t\t\t\t\\\n+ (h)->object_base = (h)->next_free,\t\t\t\t\t\\\n+ (h)->temp.tempptr)\n+\n+# define obstack_free(h,obj)\t\t\t\t\t\t\\\n+( (h)->temp.tempint = (char *) (obj) - (char *) (h)->chunk,\t\t\\\n+ ((((h)->temp.tempint > 0\t\t\t\t\t\t\\\n+ && (h)->temp.tempint < (h)->chunk_limit - (char *) (h)->chunk))\t\\\n+ ? (int) ((h)->next_free = (h)->object_base\t\t\t\t\\\n+\t = (h)->temp.tempint + (char *) (h)->chunk)\t\t\t\\\n+ : (((obstack_free) ((h), (h)->temp.tempint + (char *) (h)->chunk), 0), 0)))\n+\n+#endif /* not __GNUC__ or not __STDC__ */\n+\n+#ifdef __cplusplus\n+}\t/* C++ */\n+#endif\n+\n+#endif /* obstack.h */\n"},{"id":"173944","messageId":"20110820224111.GC2199@fredrik-Q430-Q530","threadId":"28179","inReplyTo":"20110820223032.12380.72469.stgit@localhost6.localdomain6","subject":"[PATCH v2 2/5] Add string search routines from GNU grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2011-08-20T22:41:11Z","receivedAt":"2011-08-20T22:41:11Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"kwset.c and kwset.h have been copied unmodified from commit e7ac713d^\nin the GNU grep git repository (this is the last commit in the\nrepository licensed under GPLv2).\n\nSigned-off-by: Fredrik Kuivinen \n---\n kwset.c | 778 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n kwset.h | 57 +++++\n 2 files changed, 835 insertions(+), 0 deletions(-)\n create mode 100644 kwset.c\n create mode 100644 kwset.h\n\ndiff --git a/kwset.c b/kwset.c\nnew file mode 100644\nindex 0000000..e66193b\n--- /dev/null\n+++ b/kwset.c\n@@ -0,0 +1,778 @@\n+/* kwset.c - search for any of a set of keywords.\n+ Copyright 1989, 1998, 2000, 2005 Free Software Foundation, Inc.\n+\n+ This program is free software; you can redistribute it and/or modify\n+ it under the terms of the GNU General Public License as published by\n+ the Free Software Foundation; either version 2, or (at your option)\n+ any later version.\n+\n+ This program is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU General Public License for more details.\n+\n+ You should have received a copy of the GNU General Public License\n+ along with this program; if not, write to the Free Software\n+ Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA\n+ 02110-1301, USA. */\n+\n+/* Written August 1989 by Mike Haertel.\n+ The author may be reached (Email) at the address mike@ai.mit.edu,\n+ or (US mail) as Mike Haertel c/o Free Software Foundation. */\n+\n+/* The algorithm implemented by these routines bears a startling resemblence\n+ to one discovered by Beate Commentz-Walter, although it is not identical.\n+ See \"A String Matching Algorithm Fast on the Average,\" Technical Report,\n+ IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900\n+ Heidelberg, Germany. See also Aho, A.V., and M. Corasick, \"Efficient\n+ String Matching: An Aid to Bibliographic Search,\" CACM June 1975,\n+ Vol. 18, No. 6, which describes the failure function used below. */\n+\n+#ifdef HAVE_CONFIG_H\n+# include \n+#endif\n+#include \n+#include \"system.h\"\n+#include \"kwset.h\"\n+#include \"obstack.h\"\n+\n+#ifdef GREP\n+extern char *xmalloc();\n+# undef malloc\n+# define malloc xmalloc\n+#endif\n+\n+#define NCHAR (UCHAR_MAX + 1)\n+#define obstack_chunk_alloc malloc\n+#define obstack_chunk_free free\n+\n+#define U(c) ((unsigned char) (c))\n+\n+/* Balanced tree of edges and labels leaving a given trie node. */\n+struct tree\n+{\n+ struct tree *llink;\t\t/* Left link; MUST be first field. */\n+ struct tree *rlink;\t\t/* Right link (to larger labels). */\n+ struct trie *trie;\t\t/* Trie node pointed to by this edge. */\n+ unsigned char label;\t\t/* Label on this edge. */\n+ char balance;\t\t\t/* Difference in depths of subtrees. */\n+};\n+\n+/* Node of a trie representing a set of reversed keywords. */\n+struct trie\n+{\n+ unsigned int accepting;\t/* Word index of accepted word, or zero. */\n+ struct tree *links;\t\t/* Tree of edges leaving this node. */\n+ struct trie *parent;\t\t/* Parent of this node. */\n+ struct trie *next;\t\t/* List of all trie nodes in level order. */\n+ struct trie *fail;\t\t/* Aho-Corasick failure function. */\n+ int depth;\t\t\t/* Depth of this node from the root. */\n+ int shift;\t\t\t/* Shift function for search failures. */\n+ int maxshift;\t\t\t/* Max shift of self and descendents. */\n+};\n+\n+/* Structure returned opaquely to the caller, containing everything. */\n+struct kwset\n+{\n+ struct obstack obstack;\t/* Obstack for node allocation. */\n+ int words;\t\t\t/* Number of words in the trie. */\n+ struct trie *trie;\t\t/* The trie itself. */\n+ int mind;\t\t\t/* Minimum depth of an accepting node. */\n+ int maxd;\t\t\t/* Maximum depth of any node. */\n+ unsigned char delta[NCHAR];\t/* Delta table for rapid search. */\n+ struct trie *next[NCHAR];\t/* Table of children of the root. */\n+ char *target;\t\t\t/* Target string if there's only one. */\n+ int mind2;\t\t\t/* Used in Boyer-Moore search for one string. */\n+ char const *trans;\t\t/* Character translation table. */\n+};\n+\n+/* Allocate and initialize a keyword set object, returning an opaque\n+ pointer to it. Return NULL if memory is not available. */\n+kwset_t\n+kwsalloc (char const *trans)\n+{\n+ struct kwset *kwset;\n+\n+ kwset = (struct kwset *) malloc(sizeof (struct kwset));\n+ if (!kwset)\n+ return NULL;\n+\n+ obstack_init(&kwset->obstack);\n+ kwset->words = 0;\n+ kwset->trie\n+ = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));\n+ if (!kwset->trie)\n+ {\n+ kwsfree((kwset_t) kwset);\n+ return NULL;\n+ }\n+ kwset->trie->accepting = 0;\n+ kwset->trie->links = NULL;\n+ kwset->trie->parent = NULL;\n+ kwset->trie->next = NULL;\n+ kwset->trie->fail = NULL;\n+ kwset->trie->depth = 0;\n+ kwset->trie->shift = 0;\n+ kwset->mind = INT_MAX;\n+ kwset->maxd = -1;\n+ kwset->target = NULL;\n+ kwset->trans = trans;\n+\n+ return (kwset_t) kwset;\n+}\n+\n+/* This upper bound is valid for CHAR_BIT >= 4 and\n+ exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */\n+#define DEPTH_SIZE (CHAR_BIT + CHAR_BIT/2)\n+\n+/* Add the given string to the contents of the keyword set. Return NULL\n+ for success, an error message otherwise. */\n+const char *\n+kwsincr (kwset_t kws, char const *text, size_t len)\n+{\n+ struct kwset *kwset;\n+ register struct trie *trie;\n+ register unsigned char label;\n+ register struct tree *link;\n+ register int depth;\n+ struct tree *links[DEPTH_SIZE];\n+ enum { L, R } dirs[DEPTH_SIZE];\n+ struct tree *t, *r, *l, *rl, *lr;\n+\n+ kwset = (struct kwset *) kws;\n+ trie = kwset->trie;\n+ text += len;\n+\n+ /* Descend the trie (built of reversed keywords) character-by-character,\n+ installing new nodes when necessary. */\n+ while (len--)\n+ {\n+ label = kwset->trans ? kwset->trans[U(*--text)] : *--text;\n+\n+ /* Descend the tree of outgoing links for this trie node,\n+\t looking for the current character and keeping track\n+\t of the path followed. */\n+ link = trie->links;\n+ links[0] = (struct tree *) &trie->links;\n+ dirs[0] = L;\n+ depth = 1;\n+\n+ while (link && label != link->label)\n+\t{\n+\t links[depth] = link;\n+\t if (label < link->label)\n+\t dirs[depth++] = L, link = link->llink;\n+\t else\n+\t dirs[depth++] = R, link = link->rlink;\n+\t}\n+\n+ /* The current character doesn't have an outgoing link at\n+\t this trie node, so build a new trie node and install\n+\t a link in the current trie node's tree. */\n+ if (!link)\n+\t{\n+\t link = (struct tree *) obstack_alloc(&kwset->obstack,\n+\t\t\t\t\t sizeof (struct tree));\n+\t if (!link)\n+\t return _(\"memory exhausted\");\n+\t link->llink = NULL;\n+\t link->rlink = NULL;\n+\t link->trie = (struct trie *) obstack_alloc(&kwset->obstack,\n+\t\t\t\t\t\t sizeof (struct trie));\n+\t if (!link->trie)\n+\t {\n+\t obstack_free(&kwset->obstack, link);\n+\t return _(\"memory exhausted\");\n+\t }\n+\t link->trie->accepting = 0;\n+\t link->trie->links = NULL;\n+\t link->trie->parent = trie;\n+\t link->trie->next = NULL;\n+\t link->trie->fail = NULL;\n+\t link->trie->depth = trie->depth + 1;\n+\t link->trie->shift = 0;\n+\t link->label = label;\n+\t link->balance = 0;\n+\n+\t /* Install the new tree node in its parent. */\n+\t if (dirs[--depth] == L)\n+\t links[depth]->llink = link;\n+\t else\n+\t links[depth]->rlink = link;\n+\n+\t /* Back up the tree fixing the balance flags. */\n+\t while (depth && !links[depth]->balance)\n+\t {\n+\t if (dirs[depth] == L)\n+\t\t--links[depth]->balance;\n+\t else\n+\t\t++links[depth]->balance;\n+\t --depth;\n+\t }\n+\n+\t /* Rebalance the tree by pointer rotations if necessary. */\n+\t if (depth && ((dirs[depth] == L && --links[depth]->balance)\n+\t\t\t|| (dirs[depth] == R && ++links[depth]->balance)))\n+\t {\n+\t switch (links[depth]->balance)\n+\t\t{\n+\t\tcase (char) -2:\n+\t\t switch (dirs[depth + 1])\n+\t\t {\n+\t\t case L:\n+\t\t r = links[depth], t = r->llink, rl = t->rlink;\n+\t\t t->rlink = r, r->llink = rl;\n+\t\t t->balance = r->balance = 0;\n+\t\t break;\n+\t\t case R:\n+\t\t r = links[depth], l = r->llink, t = l->rlink;\n+\t\t rl = t->rlink, lr = t->llink;\n+\t\t t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;\n+\t\t l->balance = t->balance != 1 ? 0 : -1;\n+\t\t r->balance = t->balance != (char) -1 ? 0 : 1;\n+\t\t t->balance = 0;\n+\t\t break;\n+\t\t default:\n+\t\t abort ();\n+\t\t }\n+\t\t break;\n+\t\tcase 2:\n+\t\t switch (dirs[depth + 1])\n+\t\t {\n+\t\t case R:\n+\t\t l = links[depth], t = l->rlink, lr = t->llink;\n+\t\t t->llink = l, l->rlink = lr;\n+\t\t t->balance = l->balance = 0;\n+\t\t break;\n+\t\t case L:\n+\t\t l = links[depth], r = l->rlink, t = r->llink;\n+\t\t lr = t->llink, rl = t->rlink;\n+\t\t t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;\n+\t\t l->balance = t->balance != 1 ? 0 : -1;\n+\t\t r->balance = t->balance != (char) -1 ? 0 : 1;\n+\t\t t->balance = 0;\n+\t\t break;\n+\t\t default:\n+\t\t abort ();\n+\t\t }\n+\t\t break;\n+\t\tdefault:\n+\t\t abort ();\n+\t\t}\n+\n+\t if (dirs[depth - 1] == L)\n+\t\tlinks[depth - 1]->llink = t;\n+\t else\n+\t\tlinks[depth - 1]->rlink = t;\n+\t }\n+\t}\n+\n+ trie = link->trie;\n+ }\n+\n+ /* Mark the node we finally reached as accepting, encoding the\n+ index number of this word in the keyword set so far. */\n+ if (!trie->accepting)\n+ trie->accepting = 1 + 2 * kwset->words;\n+ ++kwset->words;\n+\n+ /* Keep track of the longest and shortest string of the keyword set. */\n+ if (trie->depth < kwset->mind)\n+ kwset->mind = trie->depth;\n+ if (trie->depth > kwset->maxd)\n+ kwset->maxd = trie->depth;\n+\n+ return NULL;\n+}\n+\n+/* Enqueue the trie nodes referenced from the given tree in the\n+ given queue. */\n+static void\n+enqueue (struct tree *tree, struct trie **last)\n+{\n+ if (!tree)\n+ return;\n+ enqueue(tree->llink, last);\n+ enqueue(tree->rlink, last);\n+ (*last) = (*last)->next = tree->trie;\n+}\n+\n+/* Compute the Aho-Corasick failure function for the trie nodes referenced\n+ from the given tree, given the failure function for their parent as\n+ well as a last resort failure node. */\n+static void\n+treefails (register struct tree const *tree, struct trie const *fail,\n+\t struct trie *recourse)\n+{\n+ register struct tree *link;\n+\n+ if (!tree)\n+ return;\n+\n+ treefails(tree->llink, fail, recourse);\n+ treefails(tree->rlink, fail, recourse);\n+\n+ /* Find, in the chain of fails going back to the root, the first\n+ node that has a descendent on the current label. */\n+ while (fail)\n+ {\n+ link = fail->links;\n+ while (link && tree->label != link->label)\n+\tif (tree->label < link->label)\n+\t link = link->llink;\n+\telse\n+\t link = link->rlink;\n+ if (link)\n+\t{\n+\t tree->trie->fail = link->trie;\n+\t return;\n+\t}\n+ fail = fail->fail;\n+ }\n+\n+ tree->trie->fail = recourse;\n+}\n+\n+/* Set delta entries for the links of the given tree such that\n+ the preexisting delta value is larger than the current depth. */\n+static void\n+treedelta (register struct tree const *tree,\n+\t register unsigned int depth,\n+\t unsigned char delta[])\n+{\n+ if (!tree)\n+ return;\n+ treedelta(tree->llink, depth, delta);\n+ treedelta(tree->rlink, depth, delta);\n+ if (depth < delta[tree->label])\n+ delta[tree->label] = depth;\n+}\n+\n+/* Return true if A has every label in B. */\n+static int\n+hasevery (register struct tree const *a, register struct tree const *b)\n+{\n+ if (!b)\n+ return 1;\n+ if (!hasevery(a, b->llink))\n+ return 0;\n+ if (!hasevery(a, b->rlink))\n+ return 0;\n+ while (a && b->label != a->label)\n+ if (b->label < a->label)\n+ a = a->llink;\n+ else\n+ a = a->rlink;\n+ return !!a;\n+}\n+\n+/* Compute a vector, indexed by character code, of the trie nodes\n+ referenced from the given tree. */\n+static void\n+treenext (struct tree const *tree, struct trie *next[])\n+{\n+ if (!tree)\n+ return;\n+ treenext(tree->llink, next);\n+ treenext(tree->rlink, next);\n+ next[tree->label] = tree->trie;\n+}\n+\n+/* Compute the shift for each trie node, as well as the delta\n+ table and next cache for the given keyword set. */\n+const char *\n+kwsprep (kwset_t kws)\n+{\n+ register struct kwset *kwset;\n+ register int i;\n+ register struct trie *curr;\n+ register char const *trans;\n+ unsigned char delta[NCHAR];\n+\n+ kwset = (struct kwset *) kws;\n+\n+ /* Initial values for the delta table; will be changed later. The\n+ delta entry for a given character is the smallest depth of any\n+ node at which an outgoing edge is labeled by that character. */\n+ memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR);\n+\n+ /* Check if we can use the simple boyer-moore algorithm, instead\n+ of the hairy commentz-walter algorithm. */\n+ if (kwset->words == 1 && kwset->trans == NULL)\n+ {\n+ char c;\n+\n+ /* Looking for just one string. Extract it from the trie. */\n+ kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);\n+ if (!kwset->target)\n+\treturn _(\"memory exhausted\");\n+ for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)\n+\t{\n+\t kwset->target[i] = curr->links->label;\n+\t curr = curr->links->trie;\n+\t}\n+ /* Build the Boyer Moore delta. Boy that's easy compared to CW. */\n+ for (i = 0; i < kwset->mind; ++i)\n+\tdelta[U(kwset->target[i])] = kwset->mind - (i + 1);\n+ /* Find the minimal delta2 shift that we might make after\n+\t a backwards match has failed. */\n+ c = kwset->target[kwset->mind - 1];\n+ for (i = kwset->mind - 2; i >= 0; --i)\n+\tif (kwset->target[i] == c)\n+\t break;\n+ kwset->mind2 = kwset->mind - (i + 1);\n+ }\n+ else\n+ {\n+ register struct trie *fail;\n+ struct trie *last, *next[NCHAR];\n+\n+ /* Traverse the nodes of the trie in level order, simultaneously\n+\t computing the delta table, failure function, and shift function. */\n+ for (curr = last = kwset->trie; curr; curr = curr->next)\n+\t{\n+\t /* Enqueue the immediate descendents in the level order queue. */\n+\t enqueue(curr->links, &last);\n+\n+\t curr->shift = kwset->mind;\n+\t curr->maxshift = kwset->mind;\n+\n+\t /* Update the delta table for the descendents of this node. */\n+\t treedelta(curr->links, curr->depth, delta);\n+\n+\t /* Compute the failure function for the decendents of this node. */\n+\t treefails(curr->links, curr->fail, kwset->trie);\n+\n+\t /* Update the shifts at each node in the current node's chain\n+\t of fails back to the root. */\n+\t for (fail = curr->fail; fail; fail = fail->fail)\n+\t {\n+\t /* If the current node has some outgoing edge that the fail\n+\t\t doesn't, then the shift at the fail should be no larger\n+\t\t than the difference of their depths. */\n+\t if (!hasevery(fail->links, curr->links))\n+\t\tif (curr->depth - fail->depth < fail->shift)\n+\t\t fail->shift = curr->depth - fail->depth;\n+\n+\t /* If the current node is accepting then the shift at the\n+\t\t fail and its descendents should be no larger than the\n+\t\t difference of their depths. */\n+\t if (curr->accepting && fail->maxshift > curr->depth - fail->depth)\n+\t\tfail->maxshift = curr->depth - fail->depth;\n+\t }\n+\t}\n+\n+ /* Traverse the trie in level order again, fixing up all nodes whose\n+\t shift exceeds their inherited maxshift. */\n+ for (curr = kwset->trie->next; curr; curr = curr->next)\n+\t{\n+\t if (curr->maxshift > curr->parent->maxshift)\n+\t curr->maxshift = curr->parent->maxshift;\n+\t if (curr->shift > curr->maxshift)\n+\t curr->shift = curr->maxshift;\n+\t}\n+\n+ /* Create a vector, indexed by character code, of the outgoing links\n+\t from the root node. */\n+ for (i = 0; i < NCHAR; ++i)\n+\tnext[i] = NULL;\n+ treenext(kwset->trie->links, next);\n+\n+ if ((trans = kwset->trans) != NULL)\n+\tfor (i = 0; i < NCHAR; ++i)\n+\t kwset->next[i] = next[U(trans[i])];\n+ else\n+\tmemcpy(kwset->next, next, NCHAR * sizeof(struct trie *));\n+ }\n+\n+ /* Fix things up for any translation table. */\n+ if ((trans = kwset->trans) != NULL)\n+ for (i = 0; i < NCHAR; ++i)\n+ kwset->delta[i] = delta[U(trans[i])];\n+ else\n+ memcpy(kwset->delta, delta, NCHAR);\n+\n+ return NULL;\n+}\n+\n+/* Fast boyer-moore search. */\n+static size_t\n+bmexec (kwset_t kws, char const *text, size_t size)\n+{\n+ struct kwset const *kwset;\n+ register unsigned char const *d1;\n+ register char const *ep, *sp, *tp;\n+ register int d, gc, i, len, md2;\n+\n+ kwset = (struct kwset const *) kws;\n+ len = kwset->mind;\n+\n+ if (len == 0)\n+ return 0;\n+ if (len > size)\n+ return -1;\n+ if (len == 1)\n+ {\n+ tp = memchr (text, kwset->target[0], size);\n+ return tp ? tp - text : -1;\n+ }\n+\n+ d1 = kwset->delta;\n+ sp = kwset->target + len;\n+ gc = U(sp[-2]);\n+ md2 = kwset->mind2;\n+ tp = text + len;\n+\n+ /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */\n+ if (size > 12 * len)\n+ /* 11 is not a bug, the initial offset happens only once. */\n+ for (ep = text + size - 11 * len;;)\n+ {\n+\twhile (tp <= ep)\n+\t {\n+\t d = d1[U(tp[-1])], tp += d;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t if (d == 0)\n+\t goto found;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t if (d == 0)\n+\t goto found;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t if (d == 0)\n+\t goto found;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t d = d1[U(tp[-1])], tp += d;\n+\t }\n+\tbreak;\n+ found:\n+\tif (U(tp[-2]) == gc)\n+\t {\n+\t for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)\n+\t ;\n+\t if (i > len)\n+\t return tp - len - text;\n+\t }\n+\ttp += md2;\n+ }\n+\n+ /* Now we have only a few characters left to search. We\n+ carefully avoid ever producing an out-of-bounds pointer. */\n+ ep = text + size;\n+ d = d1[U(tp[-1])];\n+ while (d <= ep - tp)\n+ {\n+ d = d1[U((tp += d)[-1])];\n+ if (d != 0)\n+\tcontinue;\n+ if (U(tp[-2]) == gc)\n+\t{\n+\t for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)\n+\t ;\n+\t if (i > len)\n+\t return tp - len - text;\n+\t}\n+ d = md2;\n+ }\n+\n+ return -1;\n+}\n+\n+/* Hairy multiple string search. */\n+static size_t\n+cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)\n+{\n+ struct kwset const *kwset;\n+ struct trie * const *next;\n+ struct trie const *trie;\n+ struct trie const *accept;\n+ char const *beg, *lim, *mch, *lmch;\n+ register unsigned char c;\n+ register unsigned char const *delta;\n+ register int d;\n+ register char const *end, *qlim;\n+ register struct tree const *tree;\n+ register char const *trans;\n+\n+#ifdef lint\n+ accept = NULL;\n+#endif\n+\n+ /* Initialize register copies and look for easy ways out. */\n+ kwset = (struct kwset *) kws;\n+ if (len < kwset->mind)\n+ return -1;\n+ next = kwset->next;\n+ delta = kwset->delta;\n+ trans = kwset->trans;\n+ lim = text + len;\n+ end = text;\n+ if ((d = kwset->mind) != 0)\n+ mch = NULL;\n+ else\n+ {\n+ mch = text, accept = kwset->trie;\n+ goto match;\n+ }\n+\n+ if (len >= 4 * kwset->mind)\n+ qlim = lim - 4 * kwset->mind;\n+ else\n+ qlim = NULL;\n+\n+ while (lim - end >= d)\n+ {\n+ if (qlim && end <= qlim)\n+\t{\n+\t end += d - 1;\n+\t while ((d = delta[c = *end]) && end < qlim)\n+\t {\n+\t end += d;\n+\t end += delta[U(*end)];\n+\t end += delta[U(*end)];\n+\t }\n+\t ++end;\n+\t}\n+ else\n+\td = delta[c = (end += d)[-1]];\n+ if (d)\n+\tcontinue;\n+ beg = end - 1;\n+ trie = next[c];\n+ if (trie->accepting)\n+\t{\n+\t mch = beg;\n+\t accept = trie;\n+\t}\n+ d = trie->shift;\n+ while (beg > text)\n+\t{\n+\t c = trans ? trans[U(*--beg)] : *--beg;\n+\t tree = trie->links;\n+\t while (tree && c != tree->label)\n+\t if (c < tree->label)\n+\t tree = tree->llink;\n+\t else\n+\t tree = tree->rlink;\n+\t if (tree)\n+\t {\n+\t trie = tree->trie;\n+\t if (trie->accepting)\n+\t\t{\n+\t\t mch = beg;\n+\t\t accept = trie;\n+\t\t}\n+\t }\n+\t else\n+\t break;\n+\t d = trie->shift;\n+\t}\n+ if (mch)\n+\tgoto match;\n+ }\n+ return -1;\n+\n+ match:\n+ /* Given a known match, find the longest possible match anchored\n+ at or before its starting point. This is nearly a verbatim\n+ copy of the preceding main search loops. */\n+ if (lim - mch > kwset->maxd)\n+ lim = mch + kwset->maxd;\n+ lmch = 0;\n+ d = 1;\n+ while (lim - end >= d)\n+ {\n+ if ((d = delta[c = (end += d)[-1]]) != 0)\n+\tcontinue;\n+ beg = end - 1;\n+ if (!(trie = next[c]))\n+\t{\n+\t d = 1;\n+\t continue;\n+\t}\n+ if (trie->accepting && beg <= mch)\n+\t{\n+\t lmch = beg;\n+\t accept = trie;\n+\t}\n+ d = trie->shift;\n+ while (beg > text)\n+\t{\n+\t c = trans ? trans[U(*--beg)] : *--beg;\n+\t tree = trie->links;\n+\t while (tree && c != tree->label)\n+\t if (c < tree->label)\n+\t tree = tree->llink;\n+\t else\n+\t tree = tree->rlink;\n+\t if (tree)\n+\t {\n+\t trie = tree->trie;\n+\t if (trie->accepting && beg <= mch)\n+\t\t{\n+\t\t lmch = beg;\n+\t\t accept = trie;\n+\t\t}\n+\t }\n+\t else\n+\t break;\n+\t d = trie->shift;\n+\t}\n+ if (lmch)\n+\t{\n+\t mch = lmch;\n+\t goto match;\n+\t}\n+ if (!d)\n+\td = 1;\n+ }\n+\n+ if (kwsmatch)\n+ {\n+ kwsmatch->index = accept->accepting / 2;\n+ kwsmatch->offset[0] = mch - text;\n+ kwsmatch->size[0] = accept->depth;\n+ }\n+ return mch - text;\n+}\n+\n+/* Search through the given text for a match of any member of the\n+ given keyword set. Return a pointer to the first character of\n+ the matching substring, or NULL if no match is found. If FOUNDLEN\n+ is non-NULL store in the referenced location the length of the\n+ matching substring. Similarly, if FOUNDIDX is non-NULL, store\n+ in the referenced location the index number of the particular\n+ keyword matched. */\n+size_t\n+kwsexec (kwset_t kws, char const *text, size_t size,\n+\t struct kwsmatch *kwsmatch)\n+{\n+ struct kwset const *kwset = (struct kwset *) kws;\n+ if (kwset->words == 1 && kwset->trans == NULL)\n+ {\n+ size_t ret = bmexec (kws, text, size);\n+ if (kwsmatch != NULL && ret != (size_t) -1)\n+\t{\n+\t kwsmatch->index = 0;\n+\t kwsmatch->offset[0] = ret;\n+\t kwsmatch->size[0] = kwset->mind;\n+\t}\n+ return ret;\n+ }\n+ else\n+ return cwexec(kws, text, size, kwsmatch);\n+}\n+\n+/* Free the components of the given keyword set. */\n+void\n+kwsfree (kwset_t kws)\n+{\n+ struct kwset *kwset;\n+\n+ kwset = (struct kwset *) kws;\n+ obstack_free(&kwset->obstack, NULL);\n+ free(kws);\n+}\ndiff --git a/kwset.h b/kwset.h\nnew file mode 100644\nindex 0000000..10836be\n--- /dev/null\n+++ b/kwset.h\n@@ -0,0 +1,57 @@\n+/* kwset.h - header declaring the keyword set library.\n+ Copyright (C) 1989, 1998, 2005 Free Software Foundation, Inc.\n+\n+ This program is free software; you can redistribute it and/or modify\n+ it under the terms of the GNU General Public License as published by\n+ the Free Software Foundation; either version 2, or (at your option)\n+ any later version.\n+\n+ This program is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU General Public License for more details.\n+\n+ You should have received a copy of the GNU General Public License\n+ along with this program; if not, write to the Free Software\n+ Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA\n+ 02110-1301, USA. */\n+\n+/* Written August 1989 by Mike Haertel.\n+ The author may be reached (Email) at the address mike@ai.mit.edu,\n+ or (US mail) as Mike Haertel c/o Free Software Foundation. */\n+\n+struct kwsmatch\n+{\n+ int index;\t\t\t/* Index number of matching keyword. */\n+ size_t offset[1];\t\t/* Offset of each submatch. */\n+ size_t size[1];\t\t/* Length of each submatch. */\n+};\n+\n+typedef ptr_t kwset_t;\n+\n+/* Return an opaque pointer to a newly allocated keyword set, or NULL\n+ if enough memory cannot be obtained. The argument if non-NULL\n+ specifies a table of character translations to be applied to all\n+ pattern and search text. */\n+extern kwset_t kwsalloc PARAMS((char const *));\n+\n+/* Incrementally extend the keyword set to include the given string.\n+ Return NULL for success, or an error message. Remember an index\n+ number for each keyword included in the set. */\n+extern const char *kwsincr PARAMS((kwset_t, char const *, size_t));\n+\n+/* When the keyword set has been completely built, prepare it for\n+ use. Return NULL for success, or an error message. */\n+extern const char *kwsprep PARAMS((kwset_t));\n+\n+/* Search through the given buffer for a member of the keyword set.\n+ Return a pointer to the leftmost longest match found, or NULL if\n+ no match is found. If foundlen is non-NULL, store the length of\n+ the matching substring in the integer it points to. Similarly,\n+ if foundindex is non-NULL, store the index of the particular\n+ keyword found therein. */\n+extern size_t kwsexec PARAMS((kwset_t, char const *, size_t, struct kwsmatch *));\n+\n+/* Deallocate the given keyword set and all its associated storage. */\n+extern void kwsfree PARAMS((kwset_t));\n+\n"},{"id":"173945","messageId":"20110820224141.GD2199@fredrik-Q430-Q530","threadId":"28179","inReplyTo":"20110820223032.12380.72469.stgit@localhost6.localdomain6","subject":"[PATCH v2 3/5] Adapt the kwset code to Git","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2011-08-20T22:41:41Z","receivedAt":"2011-08-20T22:41:41Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"\n\nSigned-off-by: Fredrik Kuivinen \n---\n kwset.c | 31 ++++++++++++-------------------\n kwset.h | 18 ++++++++++++------\n 2 files changed, 24 insertions(+), 25 deletions(-)\n\ndiff --git a/kwset.c b/kwset.c\nindex e66193b..06a66e7 100644\n--- a/kwset.c\n+++ b/kwset.c\n@@ -1,3 +1,8 @@\n+/* This file has been copied from commit e7ac713d^ in the GNU grep git\n+ * repository. A few small changes have been made to adapt the code to\n+ * Git.\n+ */\n+\n /* kwset.c - search for any of a set of keywords.\n Copyright 1989, 1998, 2000, 2005 Free Software Foundation, Inc.\n \n@@ -28,22 +33,14 @@\n String Matching: An Aid to Bibliographic Search,\" CACM June 1975,\n Vol. 18, No. 6, which describes the failure function used below. */\n \n-#ifdef HAVE_CONFIG_H\n-# include \n-#endif\n+#include \"cache.h\"\n+\n #include \n-#include \"system.h\"\n #include \"kwset.h\"\n #include \"obstack.h\"\n \n-#ifdef GREP\n-extern char *xmalloc();\n-# undef malloc\n-# define malloc xmalloc\n-#endif\n-\n #define NCHAR (UCHAR_MAX + 1)\n-#define obstack_chunk_alloc malloc\n+#define obstack_chunk_alloc xmalloc\n #define obstack_chunk_free free\n \n #define U(c) ((unsigned char) (c))\n@@ -93,9 +90,7 @@ kwsalloc (char const *trans)\n {\n struct kwset *kwset;\n \n- kwset = (struct kwset *) malloc(sizeof (struct kwset));\n- if (!kwset)\n- return NULL;\n+ kwset = (struct kwset *) xmalloc(sizeof (struct kwset));\n \n obstack_init(&kwset->obstack);\n kwset->words = 0;\n@@ -174,7 +169,7 @@ kwsincr (kwset_t kws, char const *text, size_t len)\n \t link = (struct tree *) obstack_alloc(&kwset->obstack,\n \t\t\t\t\t sizeof (struct tree));\n \t if (!link)\n-\t return _(\"memory exhausted\");\n+\t return \"memory exhausted\";\n \t link->llink = NULL;\n \t link->rlink = NULL;\n \t link->trie = (struct trie *) obstack_alloc(&kwset->obstack,\n@@ -182,7 +177,7 @@ kwsincr (kwset_t kws, char const *text, size_t len)\n \t if (!link->trie)\n \t {\n \t obstack_free(&kwset->obstack, link);\n-\t return _(\"memory exhausted\");\n+\t return \"memory exhausted\";\n \t }\n \t link->trie->accepting = 0;\n \t link->trie->links = NULL;\n@@ -405,7 +400,7 @@ kwsprep (kwset_t kws)\n /* Looking for just one string. Extract it from the trie. */\n kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);\n if (!kwset->target)\n-\treturn _(\"memory exhausted\");\n+\treturn \"memory exhausted\";\n for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)\n \t{\n \t kwset->target[i] = curr->links->label;\n@@ -597,9 +592,7 @@ cwexec (kwset_t kws, char const *text, size_t len, struct kwsmatch *kwsmatch)\n register struct tree const *tree;\n register char const *trans;\n \n-#ifdef lint\n accept = NULL;\n-#endif\n \n /* Initialize register copies and look for easy ways out. */\n kwset = (struct kwset *) kws;\ndiff --git a/kwset.h b/kwset.h\nindex 10836be..a21b2ea 100644\n--- a/kwset.h\n+++ b/kwset.h\n@@ -1,3 +1,8 @@\n+/* This file has been copied from commit e7ac713d^ in the GNU grep git\n+ * repository. A few small changes have been made to adapt the code to\n+ * Git.\n+ */\n+\n /* kwset.h - header declaring the keyword set library.\n Copyright (C) 1989, 1998, 2005 Free Software Foundation, Inc.\n \n@@ -27,22 +32,23 @@ struct kwsmatch\n size_t size[1];\t\t/* Length of each submatch. */\n };\n \n-typedef ptr_t kwset_t;\n+struct kwset_t;\n+typedef struct kwset_t* kwset_t;\n \n /* Return an opaque pointer to a newly allocated keyword set, or NULL\n if enough memory cannot be obtained. The argument if non-NULL\n specifies a table of character translations to be applied to all\n pattern and search text. */\n-extern kwset_t kwsalloc PARAMS((char const *));\n+extern kwset_t kwsalloc(char const *);\n \n /* Incrementally extend the keyword set to include the given string.\n Return NULL for success, or an error message. Remember an index\n number for each keyword included in the set. */\n-extern const char *kwsincr PARAMS((kwset_t, char const *, size_t));\n+extern const char *kwsincr(kwset_t, char const *, size_t);\n \n /* When the keyword set has been completely built, prepare it for\n use. Return NULL for success, or an error message. */\n-extern const char *kwsprep PARAMS((kwset_t));\n+extern const char *kwsprep(kwset_t);\n \n /* Search through the given buffer for a member of the keyword set.\n Return a pointer to the leftmost longest match found, or NULL if\n@@ -50,8 +56,8 @@ extern const char *kwsprep PARAMS((kwset_t));\n the matching substring in the integer it points to. Similarly,\n if foundindex is non-NULL, store the index of the particular\n keyword found therein. */\n-extern size_t kwsexec PARAMS((kwset_t, char const *, size_t, struct kwsmatch *));\n+extern size_t kwsexec(kwset_t, char const *, size_t, struct kwsmatch *);\n \n /* Deallocate the given keyword set and all its associated storage. */\n-extern void kwsfree PARAMS((kwset_t));\n+extern void kwsfree(kwset_t);\n \n"},{"id":"173946","messageId":"20110820224157.GE2199@fredrik-Q430-Q530","threadId":"28179","inReplyTo":"20110820223032.12380.72469.stgit@localhost6.localdomain6","subject":"[PATCH v2 4/5] Use kwset in pickaxe","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2011-08-20T22:41:57Z","receivedAt":"2011-08-20T22:41:57Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Benchmarks in the hot cache case:\n\nbefore:\n$ perf stat --repeat=5 git log -Sqwerty\n\nPerformance counter stats for 'git log -Sqwerty' (5 runs):\n\n 47,092,744 cache-misses # 2.825 M/sec ( +- 1.607% )\n 123,368,389 cache-references # 7.400 M/sec ( +- 0.812% )\n 330,040,998 branch-misses # 3.134 % ( +- 0.257% )\n 10,530,896,750 branches # 631.663 M/sec ( +- 0.121% )\n 62,037,201,030 instructions # 1.399 IPC ( +- 0.142% )\n 44,331,294,321 cycles # 2659.073 M/sec ( +- 0.326% )\n 96,794 page-faults # 0.006 M/sec ( +- 11.952% )\n 25 CPU-migrations # 0.000 M/sec ( +- 25.266% )\n 1,424 context-switches # 0.000 M/sec ( +- 0.540% )\n 16671.708650 task-clock-msecs # 0.997 CPUs ( +- 0.343% )\n\n 16.728692052 seconds time elapsed ( +- 0.344% )\n\nafter:\n$ perf stat --repeat=5 git log -Sqwerty\n\nPerformance counter stats for 'git log -Sqwerty' (5 runs):\n\n 51,385,522 cache-misses # 4.619 M/sec ( +- 0.565% )\n 129,177,880 cache-references # 11.611 M/sec ( +- 0.219% )\n 319,222,775 branch-misses # 6.946 % ( +- 0.134% )\n 4,595,913,233 branches # 413.086 M/sec ( +- 0.112% )\n 31,395,042,533 instructions # 1.062 IPC ( +- 0.129% )\n 29,558,348,598 cycles # 2656.740 M/sec ( +- 0.204% )\n 93,224 page-faults # 0.008 M/sec ( +- 4.487% )\n 19 CPU-migrations # 0.000 M/sec ( +- 10.425% )\n 950 context-switches # 0.000 M/sec ( +- 0.360% )\n 11125.796039 task-clock-msecs # 0.997 CPUs ( +- 0.239% )\n\n 11.164216599 seconds time elapsed ( +- 0.240% )\n\nSo the kwset code is about 33% faster.\n\nSigned-off-by: Fredrik Kuivinen \n---\n Makefile | 2 ++\n diffcore-pickaxe.c | 34 +++++++++++++++++++++++-----------\n 2 files changed, 25 insertions(+), 11 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 4cd061f..45ef51f 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -533,6 +533,7 @@ LIB_H += graph.h\n LIB_H += grep.h\n LIB_H += hash.h\n LIB_H += help.h\n+LIB_H += kwset.h\n LIB_H += levenshtein.h\n LIB_H += list-objects.h\n LIB_H += ll-merge.h\n@@ -624,6 +625,7 @@ LIB_OBJS += hash.o\n LIB_OBJS += help.o\n LIB_OBJS += hex.o\n LIB_OBJS += ident.o\n+LIB_OBJS += kwset.o\n LIB_OBJS += levenshtein.o\n LIB_OBJS += list-objects.o\n LIB_OBJS += ll-merge.o\ndiff --git a/diffcore-pickaxe.c b/diffcore-pickaxe.c\nindex ea03b91..c3760cf 100644\n--- a/diffcore-pickaxe.c\n+++ b/diffcore-pickaxe.c\n@@ -6,6 +6,7 @@\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"xdiff-interface.h\"\n+#include \"kwset.h\"\n \n struct diffgrep_cb {\n \tregex_t *regexp;\n@@ -146,7 +147,7 @@ static void diffcore_pickaxe_grep(struct diff_options *o)\n \n static unsigned int contains(struct diff_filespec *one,\n \t\t\t const char *needle, unsigned long len,\n-\t\t\t regex_t *regexp)\n+\t\t\t regex_t *regexp, kwset_t kws)\n {\n \tunsigned int cnt;\n \tunsigned long sz;\n@@ -175,9 +176,12 @@ static unsigned int contains(struct diff_filespec *one,\n \n \t} else { /* Classic exact string match */\n \t\twhile (sz) {\n-\t\t\tconst char *found = memmem(data, sz, needle, len);\n-\t\t\tif (!found)\n+\t\t\tsize_t offset = kwsexec(kws, data, sz, NULL);\n+\t\t\tconst char *found;\n+\t\t\tif (offset == -1)\n \t\t\t\tbreak;\n+\t\t\telse\n+\t\t\t\tfound = data + offset;\n \t\t\tsz -= found - data + len;\n \t\t\tdata = found + len;\n \t\t\tcnt++;\n@@ -195,6 +199,7 @@ static void diffcore_pickaxe_count(struct diff_options *o)\n \tunsigned long len = strlen(needle);\n \tint i, has_changes;\n \tregex_t regex, *regexp = NULL;\n+\tkwset_t kws = NULL;\n \tstruct diff_queue_struct outq;\n \tDIFF_QUEUE_CLEAR(&outq);\n \n@@ -209,6 +214,10 @@ static void diffcore_pickaxe_count(struct diff_options *o)\n \t\t\tdie(\"invalid pickaxe regex: %s\", errbuf);\n \t\t}\n \t\tregexp = ®ex;\n+\t} else {\n+\t\tkws = kwsalloc(NULL);\n+\t\tkwsincr(kws, needle, len);\n+\t\tkwsprep(kws);\n \t}\n \n \tif (opts & DIFF_PICKAXE_ALL) {\n@@ -219,16 +228,16 @@ static void diffcore_pickaxe_count(struct diff_options *o)\n \t\t\t\tif (!DIFF_FILE_VALID(p->two))\n \t\t\t\t\tcontinue; /* ignore unmerged */\n \t\t\t\t/* created */\n-\t\t\t\tif (contains(p->two, needle, len, regexp))\n+\t\t\t\tif (contains(p->two, needle, len, regexp, kws))\n \t\t\t\t\thas_changes++;\n \t\t\t}\n \t\t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t\tif (contains(p->one, needle, len, regexp))\n+\t\t\t\tif (contains(p->one, needle, len, regexp, kws))\n \t\t\t\t\thas_changes++;\n \t\t\t}\n \t\t\telse if (!diff_unmodified_pair(p) &&\n-\t\t\t\t contains(p->one, needle, len, regexp) !=\n-\t\t\t\t contains(p->two, needle, len, regexp))\n+\t\t\t\t contains(p->one, needle, len, regexp, kws) !=\n+\t\t\t\t contains(p->two, needle, len, regexp, kws))\n \t\t\t\thas_changes++;\n \t\t}\n \t\tif (has_changes)\n@@ -251,16 +260,17 @@ static void diffcore_pickaxe_count(struct diff_options *o)\n \t\t\t\tif (!DIFF_FILE_VALID(p->two))\n \t\t\t\t\t; /* ignore unmerged */\n \t\t\t\t/* created */\n-\t\t\t\telse if (contains(p->two, needle, len, regexp))\n+\t\t\t\telse if (contains(p->two, needle, len, regexp,\n+\t\t\t\t\t\t kws))\n \t\t\t\t\thas_changes = 1;\n \t\t\t}\n \t\t\telse if (!DIFF_FILE_VALID(p->two)) {\n-\t\t\t\tif (contains(p->one, needle, len, regexp))\n+\t\t\t\tif (contains(p->one, needle, len, regexp, kws))\n \t\t\t\t\thas_changes = 1;\n \t\t\t}\n \t\t\telse if (!diff_unmodified_pair(p) &&\n-\t\t\t\t contains(p->one, needle, len, regexp) !=\n-\t\t\t\t contains(p->two, needle, len, regexp))\n+\t\t\t\t contains(p->one, needle, len, regexp, kws) !=\n+\t\t\t\t contains(p->two, needle, len, regexp, kws))\n \t\t\t\thas_changes = 1;\n \n \t\t\tif (has_changes)\n@@ -271,6 +281,8 @@ static void diffcore_pickaxe_count(struct diff_options *o)\n \n \tif (opts & DIFF_PICKAXE_REGEX)\n \t\tregfree(®ex);\n+\telse\n+\t\tkwsfree(kws);\n \n \tfree(q->queue);\n \t*q = outq;\n"},{"id":"173947","messageId":"20110820224218.GF2199@fredrik-Q430-Q530","threadId":"28179","inReplyTo":"20110820223032.12380.72469.stgit@localhost6.localdomain6","subject":"[PATCH v2 5/5] Use kwset in grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2011-08-20T22:42:18Z","receivedAt":"2011-08-20T22:42:18Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Benchmarks for the hot cache case:\n\nbefore:\n$ perf stat --repeat=5 git grep qwerty > /dev/null\n\nPerformance counter stats for 'git grep qwerty' (5 runs):\n\n 3,478,085 cache-misses # 2.322 M/sec ( +- 2.690% )\n 11,356,177 cache-references # 7.582 M/sec ( +- 2.598% )\n 3,872,184 branch-misses # 0.363 % ( +- 0.258% )\n 1,067,367,848 branches # 712.673 M/sec ( +- 2.622% )\n 3,828,370,782 instructions # 0.947 IPC ( +- 0.033% )\n 4,043,832,831 cycles # 2700.037 M/sec ( +- 0.167% )\n 8,518 page-faults # 0.006 M/sec ( +- 3.648% )\n 847 CPU-migrations # 0.001 M/sec ( +- 3.262% )\n 6,546 context-switches # 0.004 M/sec ( +- 2.292% )\n 1497.695495 task-clock-msecs # 3.303 CPUs ( +- 2.550% )\n\n 0.453394396 seconds time elapsed ( +- 0.912% )\n\nafter:\n$ perf stat --repeat=5 git grep qwerty > /dev/null\n\nPerformance counter stats for 'git grep qwerty' (5 runs):\n\n 2,989,918 cache-misses # 3.166 M/sec ( +- 5.013% )\n 10,986,041 cache-references # 11.633 M/sec ( +- 4.899% ) (scaled from 95.06%)\n 3,511,993 branch-misses # 1.422 % ( +- 0.785% )\n 246,893,561 branches # 261.433 M/sec ( +- 3.967% )\n 1,392,727,757 instructions # 0.564 IPC ( +- 0.040% )\n 2,468,142,397 cycles # 2613.494 M/sec ( +- 0.110% )\n 7,747 page-faults # 0.008 M/sec ( +- 3.995% )\n 897 CPU-migrations # 0.001 M/sec ( +- 2.383% )\n 6,535 context-switches # 0.007 M/sec ( +- 1.993% )\n 944.384228 task-clock-msecs # 3.177 CPUs ( +- 0.268% )\n\n 0.297257643 seconds time elapsed ( +- 0.450% )\n\n\nSo we gain about 35% by using the kwset code.\n\nAs a side effect of using kwset two grep tests are fixed by this\npatch. The first is fixed because kwset can deal with case-insensitive\nsearch containing NULs, something strcasestr cannot do. The second one\nis fixed because we consider patterns containing NULs as fixed strings\n(regcomp cannot accept patterns with NULs).\n\nSigned-off-by: Fredrik Kuivinen \n---\n grep.c | 66 +++++++++++++++++++++++++++++++++---------------\n grep.h | 2 +\n t/t7008-grep-binary.sh | 4 +--\n 3 files changed, 49 insertions(+), 23 deletions(-)\n\ndiff --git a/grep.c b/grep.c\nindex 26e8d8e..6618cd8 100644\n--- a/grep.c\n+++ b/grep.c\n@@ -137,16 +137,50 @@ static void free_pcre_regexp(struct grep_pat *p)\n }\n #endif /* !USE_LIBPCRE */\n \n+static int is_fixed(const char *s, size_t len)\n+{\n+\tsize_t i;\n+\n+\t/* regcomp cannot accept patterns with NULs so we\n+\t * consider any pattern containing a NUL fixed.\n+\t */\n+\tif (memchr(s, 0, len))\n+\t\treturn 1;\n+\n+\tfor (i = 0; i < len; i++) {\n+\t\tif (is_regex_special(s[i]))\n+\t\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+\n static void compile_regexp(struct grep_pat *p, struct grep_opt *opt)\n {\n \tint err;\n \n \tp->word_regexp = opt->word_regexp;\n \tp->ignore_case = opt->ignore_case;\n-\tp->fixed = opt->fixed;\n \n-\tif (p->fixed)\n+\tif (opt->fixed || is_fixed(p->pattern, p->patternlen))\n+\t\tp->fixed = 1;\n+\telse\n+\t\tp->fixed = 0;\n+\n+\tif (p->fixed) {\n+\t\tif (opt->regflags & REG_ICASE || p->ignore_case) {\n+\t\t\tstatic char trans[256];\n+\t\t\tint i;\n+\t\t\tfor (i = 0; i < 256; i++)\n+\t\t\t\ttrans[i] = tolower(i);\n+\t\t\tp->kws = kwsalloc(trans);\n+\t\t} else {\n+\t\t\tp->kws = kwsalloc(NULL);\n+\t\t}\n+\t\tkwsincr(p->kws, p->pattern, p->patternlen);\n+\t\tkwsprep(p->kws);\n \t\treturn;\n+\t}\n \n \tif (opt->pcre) {\n \t\tcompile_pcre_regexp(p, opt);\n@@ -395,7 +429,9 @@ void free_grep_patterns(struct grep_opt *opt)\n \t\tcase GREP_PATTERN: /* atom */\n \t\tcase GREP_PATTERN_HEAD:\n \t\tcase GREP_PATTERN_BODY:\n-\t\t\tif (p->pcre_regexp)\n+\t\t\tif (p->kws)\n+\t\t\t\tkwsfree(p->kws);\n+\t\t\telse if (p->pcre_regexp)\n \t\t\t\tfree_pcre_regexp(p);\n \t\t\telse\n \t\t\t\tregfree(&p->regexp);\n@@ -455,26 +491,14 @@ static void show_name(struct grep_opt *opt, const char *name)\n static int fixmatch(struct grep_pat *p, char *line, char *eol,\n \t\t regmatch_t *match)\n {\n-\tchar *hit;\n-\n-\tif (p->ignore_case) {\n-\t\tchar *s = line;\n-\t\tdo {\n-\t\t\thit = strcasestr(s, p->pattern);\n-\t\t\tif (hit)\n-\t\t\t\tbreak;\n-\t\t\ts += strlen(s) + 1;\n-\t\t} while (s < eol);\n-\t} else\n-\t\thit = memmem(line, eol - line, p->pattern, p->patternlen);\n-\n-\tif (!hit) {\n+\tstruct kwsmatch kwsm;\n+\tsize_t offset = kwsexec(p->kws, line, eol - line, &kwsm);\n+\tif (offset == -1) {\n \t\tmatch->rm_so = match->rm_eo = -1;\n \t\treturn REG_NOMATCH;\n-\t}\n-\telse {\n-\t\tmatch->rm_so = hit - line;\n-\t\tmatch->rm_eo = match->rm_so + p->patternlen;\n+\t} else {\n+\t\tmatch->rm_so = offset;\n+\t\tmatch->rm_eo = match->rm_so + kwsm.size[0];\n \t\treturn 0;\n \t}\n }\ndiff --git a/grep.h b/grep.h\nindex ae50c45..a652800 100644\n--- a/grep.h\n+++ b/grep.h\n@@ -7,6 +7,7 @@\n typedef int pcre;\n typedef int pcre_extra;\n #endif\n+#include \"kwset.h\"\n \n enum grep_pat_token {\n \tGREP_PATTERN,\n@@ -41,6 +42,7 @@ struct grep_pat {\n \tregex_t regexp;\n \tpcre *pcre_regexp;\n \tpcre_extra *pcre_extra_info;\n+\tkwset_t kws;\n \tunsigned fixed:1;\n \tunsigned ignore_case:1;\n \tunsigned word_regexp:1;\ndiff --git a/t/t7008-grep-binary.sh b/t/t7008-grep-binary.sh\nindex e058d18..917a264 100755\n--- a/t/t7008-grep-binary.sh\n+++ b/t/t7008-grep-binary.sh\n@@ -84,7 +84,7 @@ test_expect_success 'git grep -Fi Yf a' \"\n \tgit grep -f f -Fi a\n \"\n \n-test_expect_failure 'git grep -Fi Yx a' \"\n+test_expect_success 'git grep -Fi Yx a' \"\n \tprintf 'YQx' | q_to_nul >f &&\n \ttest_must_fail git grep -f f -Fi a\n \"\n@@ -94,7 +94,7 @@ test_expect_success 'git grep yf a' \"\n \tgit grep -f f a\n \"\n \n-test_expect_failure 'git grep yx a' \"\n+test_expect_success 'git grep yx a' \"\n \tprintf 'yQx' | q_to_nul >f &&\n \ttest_must_fail git grep -f f a\n \"\n"},{"id":"173997","messageId":"4E51F998.50801@gnu.org","threadId":"28179","inReplyTo":"20110820224218.GF2199@fredrik-Q430-Q530","subject":"Re: [PATCH v2 5/5] Use kwset in grep","fromName":"Paolo Bonzini","fromEmail":"bonzini@gnu.org","sentAt":"2011-08-22T06:39:20Z","receivedAt":"2011-08-22T06:39:20Z","isPatch":true,"sender":{"key":"bonzini@gnu.org","avatar":"https://avatars.githubusercontent.com/u/42082?v=4"},"body":"On 08/21/2011 12:42 AM, Fredrik Kuivinen wrote:\n> +\t\tif (opt->regflags& REG_ICASE || p->ignore_case) {\n> +\t\t\tstatic char trans[256];\n> +\t\t\tint i;\n> +\t\t\tfor (i = 0; i< 256; i++)\n> +\t\t\t\ttrans[i] = tolower(i);\n> +\t\t\tp->kws = kwsalloc(trans);\n> +\t\t} else {\n> +\t\t\tp->kws = kwsalloc(NULL);\n> +\t\t}\n\nOf course, this makes absolutely no sense for MB_CUR_MAX > 1. It's \nworth mentioning that grep instead uses a loop with \nmbrtowc/towlower/wcrtomb. This in turn will remove the need for the \ncomplex kwset code. :)\n\nThe \"mbtolower\" code\" dates to after the license change, but I wrote it \nand I give permission to use it under GPLv2. See commits 70e23616 and \n30af8050 in the GNU grep repository.\n\nShould still be good enough for most uses, so I'll give my\n\nAcked-by: Paolo Bonzini \n\nPaolo\n"},{"id":"174411","messageId":"CALx8hKTuZ5hG6fGUnTbRPLifF=N-SJcfmgYAKUVDO-jgzrKRaA@mail.gmail.com","threadId":"28179","inReplyTo":"4E51F998.50801@gnu.org","subject":"Re: [PATCH v2 5/5] Use kwset in grep","fromName":"Fredrik Kuivinen","fromEmail":"frekui@gmail.com","sentAt":"2011-08-28T11:31:49Z","receivedAt":"2011-08-28T11:31:49Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Mon, Aug 22, 2011 at 08:39, Paolo Bonzini wrote:\n> On 08/21/2011 12:42 AM, Fredrik Kuivinen wrote:\n>>\n>> +               if (opt->regflags&  REG_ICASE || p->ignore_case) {\n>> +                       static char trans[256];\n>> +                       int i;\n>> +                       for (i = 0; i<  256; i++)\n>> +                               trans[i] = tolower(i);\n>> +                       p->kws = kwsalloc(trans);\n>> +               } else {\n>> +                       p->kws = kwsalloc(NULL);\n>> +               }\n>\n> Of course, this makes absolutely no sense for MB_CUR_MAX > 1.  It's worth\n> mentioning that grep instead uses a loop with mbrtowc/towlower/wcrtomb.\n>  This in turn will remove the need for the complex kwset code. :)\n\nGood catch. At least it is not a regression from the current behavior,\nneither our own strcasestr in compat/ nor strcasestr in glibc can\nhandle MB_CUR_MAX > 1. My original idea was to make use of kwset also\nfor the case when more than one fixed string is given to git-grep, but\nI didn't find a nice way to refactor the code to make that possible.\n\n> The \"mbtolower\" code\" dates to after the license change, but I wrote it and\n> I give permission to use it under GPLv2.  See commits 70e23616 and 30af8050\n> in the GNU grep repository.\n>\n> Should still be good enough for most uses, so I'll give my\n>\n> Acked-by: Paolo Bonzini \n\nThanks.\n\n- Fredrik\n"}]}