Return to machine.h CVS log

Up to [Research Unix] / researchv10no / cmd / twig

Annotation of researchv10no/cmd/twig/machine.h, revision 1.1

1.1     ! root        1: /*
        !             2:  * The machine used here is the same as the one used in fgrep.
        !             3:  * Logically, it is a trie of all the strings to be recognized.
        !             4:  * In this case, the strings are the paths of tree patterns.
        !             5:  * The nodes of the trie are the states of the machine and leaves
        !             6:  * are accepting states.  The trie is augmented by failure transitions.
        !             7:  *
        !             8:  * Each machine state is a linked list of machine_node's and referred to
        !             9:  * by pointing to the head of the list.  The machine_node represents a
        !            10:  * transition.  The nst field points to the next state when the current
        !            11:  * input is MI_EQUAL to the inp field.  If the input is not MI_EQUAL to any
        !            12:  * of the inp fields in the list,  the next state is the one that fail
        !            13:  * points to.  The fail field must be the same for all machine_node's in
        !            14:  * a state.  Accepting states have inp.value equal to -1, and the match
        !            15:  * field points to a list of match structures.  The match structures record
        !            16:  * which trees have been partially matched.
        !            17:  *
        !            18:  * The index is used by the machine generator to convert the machine into
        !            19:  * a list of integers.
        !            20:  *
        !            21:  * Further details about the data structure and algorithms can be
        !            22:  * found in:
        !            23:  *     Knuth, Morris, Pratt in SIAM J Computing 6:3
        !            24:  *     Aho, Corasick in Comm ACM 18:6
        !            25:  *     Hoffman, O'Donnell in JACM 29:1
        !            26:  */
        !            27: struct machine_input {
        !            28:        short value;
        !            29:        struct symbol_entry *sym;
        !            30: };
        !            31: #define MI_EQUAL(x,y)  ((x).value==(y).value)
        !            32: 
        !            33: #include "machcomm.h"
        !            34: 
        !            35: extern int path_getsym();
        !            36: 
        !            37: struct machine_node {
        !            38:        struct machine_input inp;
        !            39:        struct machine_node *nst;
        !            40:        struct machine_node *link;
        !            41:        struct machine_node *fail;
        !            42:        struct match *match;
        !            43:        short int index;
        !            44: };
        !            45: 
        !            46: struct match {
        !            47:        struct match *next;
        !            48:        short int depth;
        !            49:        LabelData *tree;
        !            50: };
        !            51: 
        !            52: extern struct machine_node *machine;
        !            53: 
        !            54: extern void machine_build();

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.