Compute the shift for each trie node, as well as the delta table and next cache for the given keyword set. */
| 421 | /* Compute the shift for each trie node, as well as the delta |
| 422 | table and next cache for the given keyword set. */ |
| 423 | const char * |
| 424 | kwsprep (kwset_t kws) |
| 425 | { |
| 426 | register struct kwset *kwset; |
| 427 | register int i; |
| 428 | register struct trie *curr; |
| 429 | register unsigned char const *trans; |
| 430 | unsigned char delta[NCHAR]; |
| 431 | |
| 432 | kwset = (struct kwset *) kws; |
| 433 | |
| 434 | /* Initial values for the delta table; will be changed later. The |
| 435 | delta entry for a given character is the smallest depth of any |
| 436 | node at which an outgoing edge is labeled by that character. */ |
| 437 | memset(delta, kwset->mind < UCHAR_MAX ? kwset->mind : UCHAR_MAX, NCHAR); |
| 438 | |
| 439 | /* Check if we can use the simple boyer-moore algorithm, instead |
| 440 | of the hairy commentz-walter algorithm. */ |
| 441 | if (kwset->words == 1 && kwset->trans == NULL) |
| 442 | { |
| 443 | char c; |
| 444 | |
| 445 | /* Looking for just one string. Extract it from the trie. */ |
| 446 | kwset->target = obstack_alloc(&kwset->obstack, kwset->mind); |
| 447 | if (!kwset->target) |
| 448 | return "memory exhausted"; |
| 449 | for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i) |
| 450 | { |
| 451 | kwset->target[i] = curr->links->label; |
| 452 | curr = curr->links->trie; |
| 453 | } |
| 454 | /* Build the Boyer Moore delta. Boy that's easy compared to CW. */ |
| 455 | for (i = 0; i < kwset->mind; ++i) |
| 456 | delta[U(kwset->target[i])] = kwset->mind - (i + 1); |
| 457 | /* Find the minimal delta2 shift that we might make after |
| 458 | a backwards match has failed. */ |
| 459 | c = kwset->target[kwset->mind - 1]; |
| 460 | for (i = kwset->mind - 2; i >= 0; --i) |
| 461 | if (kwset->target[i] == c) |
| 462 | break; |
| 463 | kwset->mind2 = kwset->mind - (i + 1); |
| 464 | } |
| 465 | else |
| 466 | { |
| 467 | register struct trie *fail; |
| 468 | struct trie *last, *next[NCHAR]; |
| 469 | |
| 470 | /* Traverse the nodes of the trie in level order, simultaneously |
| 471 | computing the delta table, failure function, and shift function. */ |
| 472 | for (curr = last = kwset->trie; curr; curr = curr->next) |
| 473 | { |
| 474 | /* Enqueue the immediate descendants in the level order queue. */ |
| 475 | enqueue(curr->links, &last); |
| 476 | |
| 477 | curr->shift = kwset->mind; |
| 478 | curr->maxshift = kwset->mind; |
| 479 | |
| 480 | /* Update the delta table for the descendants of this node. */ |