Return to dag.c CVS log

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

Annotation of researchv10no/cmd/cflow/dag.c, revision 1.1

1.1     ! root        1: /*     @(#)dag.c       1.4     */
        !             2: #include "stdio.h"
        !             3: #include "ctype.h"
        !             4: 
        !             5: #define        NLINK   8
        !             6: 
        !             7: typedef        struct  node {
        !             8:        struct  node *n_next;
        !             9:        struct  node *n_left;
        !            10:        struct  node *n_right;
        !            11:        char    *n_name;
        !            12:        char    *n_data;
        !            13:        int     n_rcnt;
        !            14:        int     n_visit;
        !            15:        int     n_lcnt;
        !            16:        struct  link *n_link;
        !            17: } node;
        !            18: 
        !            19: node   *first = NULL;
        !            20: node   *last = NULL;
        !            21: node   *root = NULL;
        !            22: 
        !            23: typedef        struct  link {
        !            24:        struct  link *l_next;
        !            25:        struct  node *l_node[NLINK];
        !            26: } link;
        !            27: 
        !            28: #define        isnamec(c)      (isalpha(c)||isdigit(c)||c=='_')
        !            29: #define        NUL     '\0'
        !            30: #define BIGINT 32767
        !            31: 
        !            32: node   *getnode();
        !            33: char   *copy();
        !            34: int    lines, nodes, links, chars;
        !            35: int    lineno = 0;
        !            36: int    lvmax = BIGINT;
        !            37: char   stdbuf[BUFSIZ];
        !            38: 
        !            39: main(argc, argv)
        !            40: char *argv[];
        !            41: {
        !            42:        extern int optind;
        !            43:        extern char *optarg;
        !            44:        register node *np;
        !            45:        node *getnode();
        !            46:        int c;
        !            47:        void reader(), dfs();
        !            48: 
        !            49:        setbuf(stdout, stdbuf);
        !            50:        while ((c = getopt(argc, argv, "d:")) != EOF)
        !            51:                if (c == 'd')
        !            52:                        {
        !            53:                        if ((lvmax = getnum(optarg, 10)) == 0)
        !            54:                                {
        !            55:                                lvmax = BIGINT;
        !            56:                                goto argerr;
        !            57:                                }
        !            58:                        }
        !            59:                else
        !            60:                argerr:
        !            61:                        (void)fprintf(stderr, "dag: bad option %c ignored\n", c);
        !            62:        reader(stdin);
        !            63:        argc -= optind + 1;
        !            64:        if (argc <= 1)
        !            65:                for (np = first; np != NULL; np = np->n_next)
        !            66:                        {
        !            67:                        if (np->n_rcnt == 0)
        !            68:                                dfs(np, 0);
        !            69:                        }
        !            70:        else
        !            71:                while (--argc > 0)
        !            72:                        dfs(getnode(*++argv), 0);
        !            73: }
        !            74: 
        !            75: getnum(p, base)
        !            76:        register int base;
        !            77:        register char *p;
        !            78:        {
        !            79:        register int n;
        !            80: 
        !            81:        n = 0;
        !            82:        while (isdigit(*p))
        !            83:                n = n * base + (*p++ - '0');
        !            84:        return(n);
        !            85:        }
        !            86: 
        !            87: void reader(fp)
        !            88: register FILE *fp;
        !            89: {
        !            90:        register char *p1, *p2;
        !            91:        int     c;
        !            92:        node    *np, *getnode();
        !            93:        char    line[BUFSIZ], *copy();
        !            94: 
        !            95:        while (getst(line, fp)) {
        !            96:                ++lines;
        !            97:                p1 = line;
        !            98:                while (isspace(*p1))
        !            99:                        ++p1;
        !           100:                if (*p1 == NUL)
        !           101:                        continue;
        !           102:                p2 = p1;
        !           103:                while (isnamec(*p2))
        !           104:                        ++p2;
        !           105:                do {
        !           106:                        c = *p2;
        !           107:                        *p2++ = NUL;
        !           108:                } while (isspace(c));
        !           109:                switch (c) {
        !           110: 
        !           111:                case '=':
        !           112:                        np = getnode(p1);
        !           113:                        while (isspace(*p2))
        !           114:                                ++p2;
        !           115:                        if (np->n_data != NULL) {
        !           116:                                (void)fprintf(stderr, "redefinition of %s\n", np->n_name);
        !           117:                                (void)cfree(np->n_data);
        !           118:                        }
        !           119:                        np->n_data = copy(p2);
        !           120:                        continue;
        !           121:                case ':':
        !           122:                        np = getnode(p1);
        !           123:                        while (*(p1 = p2) != NUL) {
        !           124:                                while (isspace(*p1))
        !           125:                                        ++p1;
        !           126:                                p2 = p1;
        !           127:                                while (isnamec(*p2))
        !           128:                                        ++p2;
        !           129:                                (void)addlink(np, getnode(p1));
        !           130:                                if (*p2 != NUL)
        !           131:                                        *p2++ = NUL;
        !           132:                        }
        !           133:                        continue;
        !           134:                }
        !           135:        }
        !           136: }
        !           137: 
        !           138: getst(s, fp)
        !           139: char *s;
        !           140: FILE *fp;
        !           141: {
        !           142:        register i, c;
        !           143: 
        !           144:        i = 0;
        !           145:        while ((c = getc(fp)) != EOF) {
        !           146:                if (c == '\n') {
        !           147:                        *s = NUL;
        !           148:                        return 1;
        !           149:                }
        !           150:                if (i++ < BUFSIZ)
        !           151:                        *s++ = c;
        !           152:        }
        !           153:        return 0;
        !           154: }
        !           155: 
        !           156: char *
        !           157: copy(s)
        !           158: char   *s;
        !           159: {
        !           160:        char    *p, *strcpy(), *calloc();
        !           161:        void    exit();
        !           162: 
        !           163:        p = calloc(sizeof(char), (unsigned)(strlen(s)+2));
        !           164:        if (p == NULL) {
        !           165:                (void)fprintf(stderr, "too many characters\n");
        !           166:                exit(1);
        !           167:        }
        !           168:        (void)strcpy(p, s);
        !           169:        chars += strlen(p);
        !           170:        return p;
        !           171: }
        !           172: 
        !           173: node *
        !           174: getnode(name)
        !           175: char   *name;
        !           176: {
        !           177:        register i;
        !           178:        register node *np, **pp;
        !           179:        void exit();
        !           180:        char *copy(), *calloc();
        !           181: 
        !           182:        pp = &root;
        !           183:        while ((np = *pp) != NULL) {
        !           184:                i = strcmp(name, np->n_name);
        !           185:                if (i > 0)
        !           186:                        pp = &np->n_right;
        !           187:                else if (i < 0)
        !           188:                        pp = &np->n_left;
        !           189:                else
        !           190:                        return np;
        !           191:        }
        !           192:        *pp = (node *)calloc(sizeof(node), 1);
        !           193:        if ((np = *pp) == NULL) {
        !           194:                (void)fprintf(stderr, "too many nodes");
        !           195:                exit(1);
        !           196:        }
        !           197:        ++nodes;
        !           198:        np->n_name = copy(name);
        !           199:        np->n_data = NULL;
        !           200:        if (first == NULL)
        !           201:                first = np;
        !           202:        if (last != NULL)
        !           203:                last->n_next = np;
        !           204:        last = np;
        !           205:        np->n_next = NULL;
        !           206:        np->n_left = np->n_right = NULL;
        !           207:        np->n_rcnt = np->n_lcnt = np->n_visit = 0;
        !           208:        np->n_link = NULL;
        !           209:        return np;
        !           210: }
        !           211: 
        !           212: addlink(np, rp)
        !           213: node   *np, *rp;
        !           214: {
        !           215:        register i, j;
        !           216:        char *calloc();
        !           217:        link    *lp, **pp;
        !           218:        void exit();
        !           219: 
        !           220:        i = j = 0;
        !           221:        pp = &np->n_link;
        !           222:        while ((lp = *pp) != NULL && i < np->n_lcnt) {
        !           223:                if (rp == lp->l_node[j])
        !           224:                        return 0;
        !           225:                if (++j >= NLINK) {
        !           226:                        j = 0;
        !           227:                        pp = &lp->l_next;
        !           228:                }
        !           229:                ++i;
        !           230:        }
        !           231:        if (lp == NULL) {
        !           232:                *pp = (link *)calloc(sizeof(link), 1);
        !           233:                if ((lp = *pp) == NULL) {
        !           234:                        (void)fprintf(stderr, "too many links\n");
        !           235:                        exit(1);
        !           236:                }
        !           237:                ++links;
        !           238:                lp->l_next = NULL;
        !           239:        }
        !           240:        lp->l_node[j] = rp;
        !           241:        if (np != rp)
        !           242:        ++rp->n_rcnt;
        !           243:        ++np->n_lcnt;
        !           244:        return 1;
        !           245: }
        !           246: 
        !           247: void dfs(np, lv)
        !           248: register
        !           249: node *np;
        !           250: {
        !           251:        register i, j;
        !           252:        link *lp;
        !           253: 
        !           254:        if (np == NULL || lv > lvmax)
        !           255:                return;
        !           256:        i = 0;
        !           257:        (void)printf("%d\t",++lineno);
        !           258:        while (i++ < lv)
        !           259:                (void)putchar('\t');
        !           260:        (void)printf("%s: ", np->n_name);
        !           261:        if (np->n_visit > 0) {
        !           262:                (void)printf("%d\n", np->n_visit);
        !           263:                return; 
        !           264:        }
        !           265:        if (np->n_data != NULL)
        !           266:                (void)printf("%s\n", np->n_data);
        !           267:        else
        !           268:                (void)printf("<>\n");
        !           269:        np->n_visit = lineno;
        !           270:        i = j = 0;
        !           271:        lp = np->n_link;
        !           272:        while (i < np->n_lcnt && lp != NULL) {
        !           273:                dfs(lp->l_node[j], lv+1);
        !           274:                if (++j >= NLINK) {
        !           275:                        j = 0;
        !           276:                        lp = lp->l_next;
        !           277:                }
        !           278:                ++i;
        !           279:        }
        !           280: }

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