kwset.c revision 53451
1/* kwset.c - search for any of a set of keywords. 2 Copyright 1989 Free Software Foundation 3 Written August 1989 by Mike Haertel. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 1, or (at your option) 8 any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; if not, write to the Free Software 17 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 18 19 The author may be reached (Email) at the address mike@ai.mit.edu, 20 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 21 22/* The algorithm implemented by these routines bears a startling resemblence 23 to one discovered by Beate Commentz-Walter, although it is not identical. 24 See "A String Matching Algorithm Fast on the Average," Technical Report, 25 IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900 26 Heidelberg, Germany. See also Aho, A.V., and M. Corasick, "Efficient 27 String Matching: An Aid to Bibliographic Search," CACM June 1975, 28 Vol. 18, No. 6, which describes the failure function used below. */ 29 30/* $FreeBSD: head/gnu/usr.bin/grep/kwset.c 53451 1999-11-20 09:40:28Z peter $ */ 31 32 33#ifdef STDC_HEADERS 34#include <limits.h> 35#include <stdlib.h> 36#else 37#define INT_MAX 2147483647 38#define UCHAR_MAX 255 39#ifdef __STDC__ 40#include <stddef.h> 41#else 42#include <sys/types.h> 43#endif 44extern char *malloc(); 45extern void free(); 46#endif 47 48#ifdef HAVE_MEMCHR 49#include <string.h> 50#ifdef NEED_MEMORY_H 51#include <memory.h> 52#endif 53#else 54#ifdef __STDC__ 55extern void *memchr(); 56#else 57extern char *memchr(); 58#endif 59#endif 60 61#ifdef GREP 62extern char *xmalloc(); 63#define malloc xmalloc 64#endif 65 66#include "kwset.h" 67#include "obstack.h" 68 69#define NCHAR (UCHAR_MAX + 1) 70#define obstack_chunk_alloc malloc 71#define obstack_chunk_free free 72 73/* Balanced tree of edges and labels leaving a given trie node. */ 74struct tree 75{ 76 struct tree *llink; /* Left link; MUST be first field. */ 77 struct tree *rlink; /* Right link (to larger labels). */ 78 struct trie *trie; /* Trie node pointed to by this edge. */ 79 unsigned char label; /* Label on this edge. */ 80 char balance; /* Difference in depths of subtrees. */ 81}; 82 83/* Node of a trie representing a set of reversed keywords. */ 84struct trie 85{ 86 unsigned int accepting; /* Word index of accepted word, or zero. */ 87 struct tree *links; /* Tree of edges leaving this node. */ 88 struct trie *parent; /* Parent of this node. */ 89 struct trie *next; /* List of all trie nodes in level order. */ 90 struct trie *fail; /* Aho-Corasick failure function. */ 91 int depth; /* Depth of this node from the root. */ 92 int shift; /* Shift function for search failures. */ 93 int maxshift; /* Max shift of self and descendents. */ 94}; 95 96/* Structure returned opaquely to the caller, containing everything. */ 97struct kwset 98{ 99 struct obstack obstack; /* Obstack for node allocation. */ 100 int words; /* Number of words in the trie. */ 101 struct trie *trie; /* The trie itself. */ 102 int mind; /* Minimum depth of an accepting node. */ 103 int maxd; /* Maximum depth of any node. */ 104 unsigned char delta[NCHAR]; /* Delta table for rapid search. */ 105 struct trie *next[NCHAR]; /* Table of children of the root. */ 106 char *target; /* Target string if there's only one. */ 107 int mind2; /* Used in Boyer-Moore search for one string. */ 108 char *trans; /* Character translation table. */ 109}; 110 111/* Allocate and initialize a keyword set object, returning an opaque 112 pointer to it. Return NULL if memory is not available. */ 113kwset_t 114kwsalloc(trans) 115 char *trans; 116{ 117 struct kwset *kwset; 118 119 kwset = (struct kwset *) malloc(sizeof (struct kwset)); 120 if (!kwset) 121 return 0; 122 123 obstack_init(&kwset->obstack); 124 kwset->words = 0; 125 kwset->trie 126 = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie)); 127 if (!kwset->trie) 128 { 129 kwsfree((kwset_t) kwset); 130 return 0; 131 } 132 kwset->trie->accepting = 0; 133 kwset->trie->links = 0; 134 kwset->trie->parent = 0; 135 kwset->trie->next = 0; 136 kwset->trie->fail = 0; 137 kwset->trie->depth = 0; 138 kwset->trie->shift = 0; 139 kwset->mind = INT_MAX; 140 kwset->maxd = -1; 141 kwset->target = 0; 142 kwset->trans = trans; 143 144 return (kwset_t) kwset; 145} 146 147/* Add the given string to the contents of the keyword set. Return NULL 148 for success, an error message otherwise. */ 149char * 150kwsincr(kws, text, len) 151 kwset_t kws; 152 char *text; 153 size_t len; 154{ 155 struct kwset *kwset; 156 register struct trie *trie; 157 register unsigned char label; 158 register struct tree *link; 159 register int depth; 160 struct tree *links[12]; 161 enum { L, R } dirs[12]; 162 struct tree *t, *r, *l, *rl, *lr; 163 164 kwset = (struct kwset *) kws; 165 trie = kwset->trie; 166 text += len; 167 168 /* Descend the trie (built of reversed keywords) character-by-character, 169 installing new nodes when necessary. */ 170 while (len--) 171 { 172 label = kwset->trans ? kwset->trans[(unsigned char) *--text] : *--text; 173 174 /* Descend the tree of outgoing links for this trie node, 175 looking for the current character and keeping track 176 of the path followed. */ 177 link = trie->links; 178 links[0] = (struct tree *) &trie->links; 179 dirs[0] = L; 180 depth = 1; 181 182 while (link && label != link->label) 183 { 184 links[depth] = link; 185 if (label < link->label) 186 dirs[depth++] = L, link = link->llink; 187 else 188 dirs[depth++] = R, link = link->rlink; 189 } 190 191 /* The current character doesn't have an outgoing link at 192 this trie node, so build a new trie node and install 193 a link in the current trie node's tree. */ 194 if (!link) 195 { 196 link = (struct tree *) obstack_alloc(&kwset->obstack, 197 sizeof (struct tree)); 198 if (!link) 199 return "memory exhausted"; 200 link->llink = 0; 201 link->rlink = 0; 202 link->trie = (struct trie *) obstack_alloc(&kwset->obstack, 203 sizeof (struct trie)); 204 if (!link->trie) 205 return "memory exhausted"; 206 link->trie->accepting = 0; 207 link->trie->links = 0; 208 link->trie->parent = trie; 209 link->trie->next = 0; 210 link->trie->fail = 0; 211 link->trie->depth = trie->depth + 1; 212 link->trie->shift = 0; 213 link->label = label; 214 link->balance = 0; 215 216 /* Install the new tree node in its parent. */ 217 if (dirs[--depth] == L) 218 links[depth]->llink = link; 219 else 220 links[depth]->rlink = link; 221 222 /* Back up the tree fixing the balance flags. */ 223 while (depth && !links[depth]->balance) 224 { 225 if (dirs[depth] == L) 226 --links[depth]->balance; 227 else 228 ++links[depth]->balance; 229 --depth; 230 } 231 232 /* Rebalance the tree by pointer rotations if necessary. */ 233 if (depth && ((dirs[depth] == L && --links[depth]->balance) 234 || (dirs[depth] == R && ++links[depth]->balance))) 235 { 236 switch (links[depth]->balance) 237 { 238 case (char) -2: 239 switch (dirs[depth + 1]) 240 { 241 case L: 242 r = links[depth], t = r->llink, rl = t->rlink; 243 t->rlink = r, r->llink = rl; 244 t->balance = r->balance = 0; 245 break; 246 case R: 247 r = links[depth], l = r->llink, t = l->rlink; 248 rl = t->rlink, lr = t->llink; 249 t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl; 250 l->balance = t->balance != 1 ? 0 : -1; 251 r->balance = t->balance != (char) -1 ? 0 : 1; 252 t->balance = 0; 253 break; 254 } 255 break; 256 case 2: 257 switch (dirs[depth + 1]) 258 { 259 case R: 260 l = links[depth], t = l->rlink, lr = t->llink; 261 t->llink = l, l->rlink = lr; 262 t->balance = l->balance = 0; 263 break; 264 case L: 265 l = links[depth], r = l->rlink, t = r->llink; 266 lr = t->llink, rl = t->rlink; 267 t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl; 268 l->balance = t->balance != 1 ? 0 : -1; 269 r->balance = t->balance != (char) -1 ? 0 : 1; 270 t->balance = 0; 271 break; 272 } 273 break; 274 } 275 276 if (dirs[depth - 1] == L) 277 links[depth - 1]->llink = t; 278 else 279 links[depth - 1]->rlink = t; 280 } 281 } 282 283 trie = link->trie; 284 } 285 286 /* Mark the node we finally reached as accepting, encoding the 287 index number of this word in the keyword set so far. */ 288 if (!trie->accepting) 289 trie->accepting = 1 + 2 * kwset->words; 290 ++kwset->words; 291 292 /* Keep track of the longest and shortest string of the keyword set. */ 293 if (trie->depth < kwset->mind) 294 kwset->mind = trie->depth; 295 if (trie->depth > kwset->maxd) 296 kwset->maxd = trie->depth; 297 298 return 0; 299} 300 301/* Enqueue the trie nodes referenced from the given tree in the 302 given queue. */ 303static void 304enqueue(tree, last) 305 struct tree *tree; 306 struct trie **last; 307{ 308 if (!tree) 309 return; 310 enqueue(tree->llink, last); 311 enqueue(tree->rlink, last); 312 (*last) = (*last)->next = tree->trie; 313} 314 315/* Compute the Aho-Corasick failure function for the trie nodes referenced 316 from the given tree, given the failure function for their parent as 317 well as a last resort failure node. */ 318static void 319treefails(tree, fail, recourse) 320 register struct tree *tree; 321 struct trie *fail; 322 struct trie *recourse; 323{ 324 register struct tree *link; 325 326 if (!tree) 327 return; 328 329 treefails(tree->llink, fail, recourse); 330 treefails(tree->rlink, fail, recourse); 331 332 /* Find, in the chain of fails going back to the root, the first 333 node that has a descendent on the current label. */ 334 while (fail) 335 { 336 link = fail->links; 337 while (link && tree->label != link->label) 338 if (tree->label < link->label) 339 link = link->llink; 340 else 341 link = link->rlink; 342 if (link) 343 { 344 tree->trie->fail = link->trie; 345 return; 346 } 347 fail = fail->fail; 348 } 349 350 tree->trie->fail = recourse; 351} 352 353/* Set delta entries for the links of the given tree such that 354 the preexisting delta value is larger than the current depth. */ 355static void 356treedelta(tree, depth, delta) 357 register struct tree *tree; 358 register unsigned int depth; 359 unsigned char delta[]; 360{ 361 if (!tree) 362 return; 363 treedelta(tree->llink, depth, delta); 364 treedelta(tree->rlink, depth, delta); 365 if (depth < delta[tree->label]) 366 delta[tree->label] = depth; 367} 368 369/* Return true if A has every label in B. */ 370static int 371hasevery(a, b) 372 register struct tree *a; 373 register struct tree *b; 374{ 375 if (!b) 376 return 1; 377 if (!hasevery(a, b->llink)) 378 return 0; 379 if (!hasevery(a, b->rlink)) 380 return 0; 381 while (a && b->label != a->label) 382 if (b->label < a->label) 383 a = a->llink; 384 else 385 a = a->rlink; 386 return !!a; 387} 388 389/* Compute a vector, indexed by character code, of the trie nodes 390 referenced from the given tree. */ 391static void 392treenext(tree, next) 393 struct tree *tree; 394 struct trie *next[]; 395{ 396 if (!tree) 397 return; 398 treenext(tree->llink, next); 399 treenext(tree->rlink, next); 400 next[tree->label] = tree->trie; 401} 402 403/* Compute the shift for each trie node, as well as the delta 404 table and next cache for the given keyword set. */ 405char * 406kwsprep(kws) 407 kwset_t kws; 408{ 409 register struct kwset *kwset; 410 register int i; 411 register struct trie *curr, *fail; 412 register char *trans; 413 unsigned char delta[NCHAR]; 414 struct trie *last, *next[NCHAR]; 415 416 kwset = (struct kwset *) kws; 417 418 /* Initial values for the delta table; will be changed later. The 419 delta entry for a given character is the smallest depth of any 420 node at which an outgoing edge is labeled by that character. */ 421 if (kwset->mind < 256) 422 for (i = 0; i < NCHAR; ++i) 423 delta[i] = kwset->mind; 424 else 425 for (i = 0; i < NCHAR; ++i) 426 delta[i] = 255; 427 428 /* Check if we can use the simple boyer-moore algorithm, instead 429 of the hairy commentz-walter algorithm. */ 430 if (kwset->words == 1 && kwset->trans == 0) 431 { 432 /* Looking for just one string. Extract it from the trie. */ 433 kwset->target = obstack_alloc(&kwset->obstack, kwset->mind); 434 for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i) 435 { 436 kwset->target[i] = curr->links->label; 437 curr = curr->links->trie; 438 } 439 /* Build the Boyer Moore delta. Boy that's easy compared to CW. */ 440 for (i = 0; i < kwset->mind; ++i) 441 delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1); 442 kwset->mind2 = kwset->mind; 443 /* Find the minimal delta2 shift that we might make after 444 a backwards match has failed. */ 445 for (i = 0; i < kwset->mind - 1; ++i) 446 if (kwset->target[i] == kwset->target[kwset->mind - 1]) 447 kwset->mind2 = kwset->mind - (i + 1); 448 } 449 else 450 { 451 /* Traverse the nodes of the trie in level order, simultaneously 452 computing the delta table, failure function, and shift function. */ 453 for (curr = last = kwset->trie; curr; curr = curr->next) 454 { 455 /* Enqueue the immediate descendents in the level order queue. */ 456 enqueue(curr->links, &last); 457 458 curr->shift = kwset->mind; 459 curr->maxshift = kwset->mind; 460 461 /* Update the delta table for the descendents of this node. */ 462 treedelta(curr->links, curr->depth, delta); 463 464 /* Compute the failure function for the decendents of this node. */ 465 treefails(curr->links, curr->fail, kwset->trie); 466 467 /* Update the shifts at each node in the current node's chain 468 of fails back to the root. */ 469 for (fail = curr->fail; fail; fail = fail->fail) 470 { 471 /* If the current node has some outgoing edge that the fail 472 doesn't, then the shift at the fail should be no larger 473 than the difference of their depths. */ 474 if (!hasevery(fail->links, curr->links)) 475 if (curr->depth - fail->depth < fail->shift) 476 fail->shift = curr->depth - fail->depth; 477 478 /* If the current node is accepting then the shift at the 479 fail and its descendents should be no larger than the 480 difference of their depths. */ 481 if (curr->accepting && fail->maxshift > curr->depth - fail->depth) 482 fail->maxshift = curr->depth - fail->depth; 483 } 484 } 485 486 /* Traverse the trie in level order again, fixing up all nodes whose 487 shift exceeds their inherited maxshift. */ 488 for (curr = kwset->trie->next; curr; curr = curr->next) 489 { 490 if (curr->maxshift > curr->parent->maxshift) 491 curr->maxshift = curr->parent->maxshift; 492 if (curr->shift > curr->maxshift) 493 curr->shift = curr->maxshift; 494 } 495 496 /* Create a vector, indexed by character code, of the outgoing links 497 from the root node. */ 498 for (i = 0; i < NCHAR; ++i) 499 next[i] = 0; 500 treenext(kwset->trie->links, next); 501 502 if ((trans = kwset->trans) != 0) 503 for (i = 0; i < NCHAR; ++i) 504 kwset->next[i] = next[(unsigned char) trans[i]]; 505 else 506 for (i = 0; i < NCHAR; ++i) 507 kwset->next[i] = next[i]; 508 } 509 510 /* Fix things up for any translation table. */ 511 if ((trans = kwset->trans) != 0) 512 for (i = 0; i < NCHAR; ++i) 513 kwset->delta[i] = delta[(unsigned char) trans[i]]; 514 else 515 for (i = 0; i < NCHAR; ++i) 516 kwset->delta[i] = delta[i]; 517 518 return 0; 519} 520 521#define U(C) ((unsigned char) (C)) 522 523/* Fast boyer-moore search. */ 524static char * 525bmexec(kws, text, size) 526 kwset_t kws; 527 char *text; 528 size_t size; 529{ 530 struct kwset *kwset; 531 register unsigned char *d1; 532 register char *ep, *sp, *tp; 533 register int d, gc, i, len, md2; 534 535 kwset = (struct kwset *) kws; 536 len = kwset->mind; 537 538 if (len == 0) 539 return text; 540 if (len > size) 541 return 0; 542 if (len == 1) 543 return memchr(text, kwset->target[0], size); 544 545 d1 = kwset->delta; 546 sp = kwset->target + len; 547 gc = U(sp[-2]); 548 md2 = kwset->mind2; 549 tp = text + len; 550 551 /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */ 552 if (size > 12 * len) 553 /* 11 is not a bug, the initial offset happens only once. */ 554 for (ep = text + size - 11 * len;;) 555 { 556 while (tp <= ep) 557 { 558 d = d1[U(tp[-1])], tp += d; 559 d = d1[U(tp[-1])], tp += d; 560 if (d == 0) 561 goto found; 562 d = d1[U(tp[-1])], tp += d; 563 d = d1[U(tp[-1])], tp += d; 564 d = d1[U(tp[-1])], tp += d; 565 if (d == 0) 566 goto found; 567 d = d1[U(tp[-1])], tp += d; 568 d = d1[U(tp[-1])], tp += d; 569 d = d1[U(tp[-1])], tp += d; 570 if (d == 0) 571 goto found; 572 d = d1[U(tp[-1])], tp += d; 573 d = d1[U(tp[-1])], tp += d; 574 } 575 break; 576 found: 577 if (U(tp[-2]) == gc) 578 { 579 for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i) 580 ; 581 if (i > len) 582 return tp - len; 583 } 584 tp += md2; 585 } 586 587 /* Now we have only a few characters left to search. We 588 carefully avoid ever producing an out-of-bounds pointer. */ 589 ep = text + size; 590 d = d1[U(tp[-1])]; 591 while (d <= ep - tp) 592 { 593 d = d1[U((tp += d)[-1])]; 594 if (d != 0) 595 continue; 596 if (U(tp[-2]) == gc) 597 { 598 for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i) 599 ; 600 if (i > len) 601 return tp - len; 602 } 603 d = md2; 604 } 605 606 return 0; 607} 608 609/* Hairy multiple string search. */ 610static char * 611cwexec(kws, text, len, kwsmatch) 612 kwset_t kws; 613 char *text; 614 size_t len; 615 struct kwsmatch *kwsmatch; 616{ 617 struct kwset *kwset; 618 struct trie **next, *trie, *accept; 619 char *beg, *lim, *mch, *lmch; 620 register unsigned char c, *delta; 621 register int d; 622 register char *end, *qlim; 623 register struct tree *tree; 624 register char *trans; 625 626 /* Initialize register copies and look for easy ways out. */ 627 kwset = (struct kwset *) kws; 628 if (len < kwset->mind) 629 return 0; 630 next = kwset->next; 631 delta = kwset->delta; 632 trans = kwset->trans; 633 lim = text + len; 634 end = text; 635 if ((d = kwset->mind) != 0) 636 mch = 0; 637 else 638 { 639 mch = text, accept = kwset->trie; 640 goto match; 641 } 642 643 if (len >= 4 * kwset->mind) 644 qlim = lim - 4 * kwset->mind; 645 else 646 qlim = 0; 647 648 while (lim - end >= d) 649 { 650 if (qlim && end <= qlim) 651 { 652 end += d - 1; 653 while ((d = delta[c = *end]) && end < qlim) 654 { 655 end += d; 656 end += delta[(unsigned char) *end]; 657 end += delta[(unsigned char) *end]; 658 } 659 ++end; 660 } 661 else 662 d = delta[c = (end += d)[-1]]; 663 if (d) 664 continue; 665 beg = end - 1; 666 trie = next[c]; 667 if (trie->accepting) 668 { 669 mch = beg; 670 accept = trie; 671 } 672 d = trie->shift; 673 while (beg > text) 674 { 675 c = trans ? trans[(unsigned char) *--beg] : *--beg; 676 tree = trie->links; 677 while (tree && c != tree->label) 678 if (c < tree->label) 679 tree = tree->llink; 680 else 681 tree = tree->rlink; 682 if (tree) 683 { 684 trie = tree->trie; 685 if (trie->accepting) 686 { 687 mch = beg; 688 accept = trie; 689 } 690 } 691 else 692 break; 693 d = trie->shift; 694 } 695 if (mch) 696 goto match; 697 } 698 return 0; 699 700 match: 701 /* Given a known match, find the longest possible match anchored 702 at or before its starting point. This is nearly a verbatim 703 copy of the preceding main search loops. */ 704 if (lim - mch > kwset->maxd) 705 lim = mch + kwset->maxd; 706 lmch = 0; 707 d = 1; 708 while (lim - end >= d) 709 { 710 if ((d = delta[c = (end += d)[-1]]) != 0) 711 continue; 712 beg = end - 1; 713 if (!(trie = next[c])) 714 { 715 d = 1; 716 continue; 717 } 718 if (trie->accepting && beg <= mch) 719 { 720 lmch = beg; 721 accept = trie; 722 } 723 d = trie->shift; 724 while (beg > text) 725 { 726 c = trans ? trans[(unsigned char) *--beg] : *--beg; 727 tree = trie->links; 728 while (tree && c != tree->label) 729 if (c < tree->label) 730 tree = tree->llink; 731 else 732 tree = tree->rlink; 733 if (tree) 734 { 735 trie = tree->trie; 736 if (trie->accepting && beg <= mch) 737 { 738 lmch = beg; 739 accept = trie; 740 } 741 } 742 else 743 break; 744 d = trie->shift; 745 } 746 if (lmch) 747 { 748 mch = lmch; 749 goto match; 750 } 751 if (!d) 752 d = 1; 753 } 754 755 if (kwsmatch) 756 { 757 kwsmatch->index = accept->accepting / 2; 758 kwsmatch->beg[0] = mch; 759 kwsmatch->size[0] = accept->depth; 760 } 761 return mch; 762} 763 764/* Search through the given text for a match of any member of the 765 given keyword set. Return a pointer to the first character of 766 the matching substring, or NULL if no match is found. If FOUNDLEN 767 is non-NULL store in the referenced location the length of the 768 matching substring. Similarly, if FOUNDIDX is non-NULL, store 769 in the referenced location the index number of the particular 770 keyword matched. */ 771char * 772kwsexec(kws, text, size, kwsmatch) 773 kwset_t kws; 774 char *text; 775 size_t size; 776 struct kwsmatch *kwsmatch; 777{ 778 struct kwset *kwset; 779 char *ret; 780 781 kwset = (struct kwset *) kws; 782 if (kwset->words == 1 && kwset->trans == 0) 783 { 784 ret = bmexec(kws, text, size); 785 if (kwsmatch != 0 && ret != 0) 786 { 787 kwsmatch->index = 0; 788 kwsmatch->beg[0] = ret; 789 kwsmatch->size[0] = kwset->mind; 790 } 791 return ret; 792 } 793 else 794 return cwexec(kws, text, size, kwsmatch); 795} 796 797/* Free the components of the given keyword set. */ 798void 799kwsfree(kws) 800 kwset_t kws; 801{ 802 struct kwset *kwset; 803 804 kwset = (struct kwset *) kws; 805 obstack_free(&kwset->obstack, 0); 806 free(kws); 807} 808