patch.c

/*
 * Copyright (c) 2007 Russ Cox.
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated
 * documentation files (the "Software"), to deal in the
 * Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute,
 * sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so,
 * subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall
 * be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY
 * KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS
 * OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

// A portion of code at https://swtch.com/~rsc/regexp/nfa.c.txt

#include <stdio.h>

typedef struct State State;
struct State {
    int c;
    State *out;
};

typedef union Ptrlist Ptrlist;
union Ptrlist {
    Ptrlist *next;
    State *s;
};

Ptrlist *
list1(State **outp) {
    Ptrlist *l;
    l = (Ptrlist *)outp;
    l->next = NULL;
    return l;
}

void
patch(Ptrlist *l, State *s) {
    Ptrlist *next;
    for (; l; l = next) {
        next = l->next;
        l->s = s;
    }
}

// The following code is not a part of Russ Cox's C code.
// This is a sample code to understand how "concatenation" is implemented using list1 and patch.

int
main() {
    State s1 = {.c = 1};
    State s2 = {.c = 2};
    State s3 = {.c = 3};
    State start = {.out = &s1 };
    Ptrlist *l, *l2;

    l = list1(&s1.out);
    patch(l, &s2); // connect &s2 to s1.out

    l2 = list1(&s2.out);
    patch(l2, &s3); // connect &s3 to s2.out

    for (State *p = start.out; p; p = p->out)
        printf("%d\n", p->c); // 1, 2, 3
    return 0;
}