Compute the Aho-Corasick failure function for the trie nodes referenced from the given tree, given the failure function for their parent as well as a last resort failure node. */
| 341 | from the given tree, given the failure function for their parent as |
| 342 | well as a last resort failure node. */ |
| 343 | static void |
| 344 | treefails (register struct tree const *tree, struct trie const *fail, |
| 345 | struct trie *recourse) |
| 346 | { |
| 347 | register struct tree *link; |
| 348 | |
| 349 | if (!tree) |
| 350 | return; |
| 351 | |
| 352 | treefails(tree->llink, fail, recourse); |
| 353 | treefails(tree->rlink, fail, recourse); |
| 354 | |
| 355 | /* Find, in the chain of fails going back to the root, the first |
| 356 | node that has a descendant on the current label. */ |
| 357 | while (fail) |
| 358 | { |
| 359 | link = fail->links; |
| 360 | while (link && tree->label != link->label) |
| 361 | if (tree->label < link->label) |
| 362 | link = link->llink; |
| 363 | else |
| 364 | link = link->rlink; |
| 365 | if (link) |
| 366 | { |
| 367 | tree->trie->fail = link->trie; |
| 368 | return; |
| 369 | } |
| 370 | fail = fail->fail; |
| 371 | } |
| 372 | |
| 373 | tree->trie->fail = recourse; |
| 374 | } |
| 375 | |
| 376 | /* Set delta entries for the links of the given tree such that |
| 377 | the preexisting delta value is larger than the current depth. */ |