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