Return to subs.c CVS log

Up to [Research Unix] / researchv10dc / cmd / tsort

Annotation of researchv10dc/cmd/tsort/subs.c, revision 1.1

1.1     ! root        1: #include <stdio.h>
        !             2: #include "ts.h"
        !             3: 
        !             4: #define HSIZE 307
        !             5: #define ALSIZE 2040
        !             6: 
        !             7: static struct obj **objhash, *cobj = 0, *lastobj;
        !             8: static struct ref **refhash;
        !             9: static struct group **grouphash, *group0;
        !            10: struct ref *undefrefs = 0, *defedrefs = 0;
        !            11: struct group *cgroup = 0; /* current group */
        !            12: struct obj *obj0 = 0; /* special null object */
        !            13: 
        !            14: unsigned lasthash = 0, ngroup = 0, nrefc = 0;
        !            15: int nextseq;
        !            16: 
        !            17: char *malloc(), *strcpy();
        !            18: extern char *progname;
        !            19: extern int cyclep, verbose, verify;
        !            20: 
        !            21: init(){
        !            22:        int i;
        !            23: 
        !            24:        objhash = (struct obj **) malloc(HSIZE*sizeof(struct obj *));
        !            25:        refhash = (struct ref **) malloc(HSIZE*sizeof(struct ref *));
        !            26:        grouphash = (struct group **) malloc(HSIZE*sizeof(struct group *));
        !            27:        if (!objhash || !refhash || !grouphash)
        !            28:                scream("initial mallocs fail\n","");
        !            29:        for (i = 0; i < HSIZE; i++)
        !            30:                { objhash[i] = 0; refhash[i] = 0; grouphash[i] = 0;}
        !            31:        cgroup = 0;
        !            32:        newgroup("");
        !            33:        group0 = cgroup;
        !            34:        newobj("",1);
        !            35:        obj0 = cobj;
        !            36:        }
        !            37: 
        !            38: unsigned
        !            39: hash(s)
        !            40: unsigned char *s;
        !            41: {
        !            42:        unsigned x = 0;
        !            43:        unsigned char c;
        !            44: 
        !            45:        while(c = *s++) x = (x<<1) + c;
        !            46:        return x % HSIZE;
        !            47:        }
        !            48: 
        !            49: char *
        !            50: newstruct(n)
        !            51: unsigned n;
        !            52: {
        !            53:        static char *next = 0, *last = 0;
        !            54:        char *s;
        !            55: 
        !            56:        if (next + n > last) {
        !            57:                next = malloc(ALSIZE);
        !            58:                if (!next) scream("malloc fails in newstruct\n","");
        !            59:                last = next + ALSIZE;
        !            60:                }
        !            61:        s = next;
        !            62:        next += n;
        !            63:        return s;
        !            64:        }
        !            65: 
        !            66: char *
        !            67: newstring(s)
        !            68: char *s;
        !            69: {
        !            70:        static char *next = 0, *last = 0;
        !            71:        char *s1;
        !            72:        unsigned n, strlen();
        !            73: 
        !            74:        n = strlen(s) + 1;
        !            75:        if (next + n > last) {
        !            76:                next = malloc(ALSIZE);
        !            77:                if (!next) scream("malloc fails in newstring\n","");
        !            78:                last = next + ALSIZE;
        !            79:                }
        !            80:        s1 = next;
        !            81:        next += n;
        !            82:        strcpy(s1,s);
        !            83:        return s1;
        !            84:        }
        !            85: 
        !            86: newgroup(s)
        !            87: char *s;
        !            88: {
        !            89:        struct group *g, *gnext = 0, *gprev;
        !            90: 
        !            91:        cobj = 0;
        !            92:        gprev = (struct group *) &grouphash[hash(s)];
        !            93:        g = gprev->next;
        !            94:        for(;; gprev = g, g = g->next) {
        !            95:                if (!g) {
        !            96:                        g = (struct group *)
        !            97:                                newstruct(sizeof(struct group));
        !            98:                        g->name = newstring(s);
        !            99:                        g->next = 0;
        !           100:                        g->gseq = ngroup++;
        !           101:                        gprev->next = g;
        !           102:                        break;
        !           103:                        }
        !           104:                if (!strcmp(s,g->name)) break;
        !           105:                }
        !           106:        cgroup = g;
        !           107:        }
        !           108: 
        !           109: struct ref *
        !           110: lookup(s,add)
        !           111: char *s;
        !           112: int add;
        !           113: {
        !           114:        struct ref *h, *hprev;
        !           115: 
        !           116:        hprev = (struct ref *) &refhash[lasthash = hash(s)];
        !           117:        h = hprev->next;
        !           118:        while(h) {
        !           119:                if (!strcmp(h->name,s)) return h;
        !           120:                hprev = h;
        !           121:                h = h->next;
        !           122:                }
        !           123:        if (add) {
        !           124:                h = (struct ref *) newstruct(sizeof(struct ref));
        !           125:                hprev->next = h;
        !           126:                h->next = 0;
        !           127:                h->name = cobj && !strcmp(cobj->name,s) ? cobj->name : newstring(s);
        !           128:                h->robj = 0;
        !           129:                }
        !           130:        return h;
        !           131:        }
        !           132: 
        !           133: newobj(s,dup)
        !           134: char *s;
        !           135: int dup;
        !           136: {
        !           137:        struct obj *h, *hnext = 0, *hprev, *o;
        !           138:        struct ref *r1;
        !           139: 
        !           140:        hprev = (struct obj *) &objhash[hash(s)];
        !           141:        h = hprev->next;
        !           142:        while(h) {
        !           143:                if (!strcmp(h->name,s) && h->ogroup == cgroup) {
        !           144:                        if (dup || h == obj0) { cobj = h; return; }
        !           145:                        if (verbose) {
        !           146:                                fprintf(stderr, "duplicate %s", s);
        !           147:                                if (*cgroup->name) fprintf(stderr, " in %s", cgroup->name);
        !           148:                                fputs(" ignored\n", stderr);
        !           149:                                }
        !           150:                        cobj = 0;
        !           151:                        return;
        !           152:                        }
        !           153:                hprev = h;
        !           154:                h = h->next;
        !           155:                }
        !           156:        cobj = o = (struct obj *) newstruct(sizeof(struct obj));
        !           157:        hprev->next = o;
        !           158:        o->next = hnext;
        !           159:        r1 = lookup(s,0);
        !           160:        o->name = r1 ? r1->name : newstring(s);
        !           161:        o->ogroup = cgroup;
        !           162:        o->seq = o->iptr = o->jct = 0;
        !           163:        }
        !           164: 
        !           165: defobjref(s,dup)
        !           166: char *s;
        !           167: int dup;
        !           168: {
        !           169:        rdefobjref(lookup(s,1), s, dup);
        !           170:        }
        !           171: 
        !           172: rdefobjref(r,s,dup)
        !           173: struct ref *r;
        !           174: char *s;
        !           175: int dup;
        !           176: {
        !           177:        struct obj *o;
        !           178: 
        !           179:        if (o = r->robj) {
        !           180:                newobj(s,dup);
        !           181:                if (!dup || o->ogroup != cgroup) dupmsg(0,r,s);
        !           182:                }
        !           183:        else {
        !           184:                r->robj = cobj = o = (struct obj *) newstruct(sizeof(struct obj));
        !           185:                o->next = objhash[lasthash];
        !           186:                objhash[lasthash] = o;
        !           187:                o->name = r->name;
        !           188:                o->ogroup = cgroup;
        !           189:                o->seq = o->iptr = o->jct = 0;
        !           190:                }
        !           191:        }
        !           192: 
        !           193: dupmsg(oprt,r,s)
        !           194: int oprt;
        !           195: struct ref *r;
        !           196: char *s;
        !           197: {
        !           198:        struct obj *o = r->robj;
        !           199:        char *in;
        !           200: 
        !           201:        if (verbose && o != obj0) {
        !           202:                fprintf(stderr, "def of %s", s);
        !           203:                if (oprt && strcmp(s,cobj->name)) {
        !           204:                        fprintf(stderr, " in %s", cobj->name);
        !           205:                        in = "of";
        !           206:                        }
        !           207:                else in = "in";
        !           208:                if (*cgroup->name) fprintf(stderr, " %s lib %s", in, cgroup->name);
        !           209:                else in = "of";
        !           210:                fprintf(stderr, " ignored; first defined in %s", o->name);
        !           211:                if (*(s = o->ogroup->name)) fprintf(stderr, " of lib %s", s);
        !           212:                putc('\n', stderr);
        !           213:                }
        !           214:        }
        !           215: 
        !           216: 
        !           217: newref(s)
        !           218: char *s;
        !           219: { newrefr(lookup(s,1)); }
        !           220: 
        !           221: newrefr(r)
        !           222: struct ref *r;
        !           223: {
        !           224:        struct refc rc;
        !           225:        struct obj *o1;
        !           226:        unsigned i;
        !           227: 
        !           228:        if (!cobj) return;
        !           229:        if (verify && r->robj && cobj != obj0) {
        !           230:                fputs(cobj->name, stderr);
        !           231:                if (cgroup != group0) fprintf(stderr, " of %s", cgroup->name);
        !           232:                fprintf(stderr, " needs %s\n", r->name);
        !           233:                }
        !           234:        rc.rcnext = cobj->iptr;
        !           235:        rc.rcref = r;
        !           236:        o1 = rc.rcref->robj;
        !           237:        if (o1 != cobj && o1 != obj0) { /* discard self references */
        !           238:                                                                        /* and refs to null object */
        !           239:                i = cobj->iptr = ++nrefc;
        !           240:                refstore(i, &rc);
        !           241:                }
        !           242:        }
        !           243: 
        !           244: defref(s)
        !           245: char *s;
        !           246: { defrefr(lookup(s,1), s); }
        !           247: 
        !           248: defrefr(r,s)
        !           249: struct ref *r;
        !           250: char *s;
        !           251: {
        !           252:        if (!cobj) return;
        !           253:        if (r->robj) dupmsg(1,r,s);
        !           254:        else r->robj = cobj;
        !           255:        }
        !           256: 
        !           257: struct obj *
        !           258: ts0()
        !           259: {
        !           260:        int i;
        !           261:        struct obj *firstobj, *o, *onext;
        !           262:        struct ref *r, *rnext;
        !           263: 
        !           264:        /* chain objects together */
        !           265: 
        !           266:        firstobj = 0;
        !           267:        for (i = 0; i < HSIZE; i++) {
        !           268:                for(o = objhash[i]; o; o = onext) {
        !           269:                        onext = o->next;
        !           270:                        o->next = firstobj;
        !           271:                        firstobj = o;
        !           272:                        }
        !           273:                }
        !           274: 
        !           275:        /* chain undefined refs together */
        !           276: 
        !           277:        defedrefs = undefrefs = 0;
        !           278:        for (i = 0; i < HSIZE; i++) {
        !           279:                for (r = refhash[i]; r; r = rnext) {
        !           280:                        rnext = r->next;
        !           281:                        if (!r->robj) { r->next = undefrefs; undefrefs = r; }
        !           282:                        else { r->next = defedrefs; defedrefs = r; }
        !           283:                        }
        !           284:                }
        !           285: 
        !           286:        free((char *) grouphash);
        !           287:        free((char *) refhash);
        !           288:        free((char *) objhash);
        !           289:        return firstobj;
        !           290:        }
        !           291: 
        !           292: struct obj *
        !           293: ts(all)
        !           294: {
        !           295:        int i, i0, k;
        !           296:        unsigned j;
        !           297:        struct obj *firstobj, *o, *o1, *onext, *oprev, **ready, **rs;
        !           298:        struct refc rc;
        !           299: 
        !           300:        firstobj = ts0();
        !           301: 
        !           302:        /* do depth-first search (to break cycles) */
        !           303: 
        !           304:        nextseq = 1;
        !           305:        for (o = firstobj; o; o = o->next)
        !           306:                if (!o->seq && (all || o->ogroup == group0)) dfs(1,o);
        !           307: 
        !           308:        /* discard unreached objects */
        !           309: 
        !           310:        if (!all) {
        !           311:                oprev = (struct obj *) &firstobj;
        !           312:                for (o = firstobj; o; o = o->next)
        !           313:                        if (o->seq) { oprev->next = o; oprev = o; }
        !           314:                oprev->next = 0;
        !           315:                }
        !           316: 
        !           317:        /* set up for funny breadth-first search */
        !           318: 
        !           319:        ready = (struct obj **) malloc(ngroup * sizeof(struct obj *));
        !           320:        if (!ready) scream("malloc of ready list fails\n","");
        !           321:        
        !           322:        obj0->jct = 0; /* force initial inclusion of obj0 */
        !           323:        for (i = 0; i < ngroup; i++) ready[i] = 0;
        !           324:        for (o = firstobj; o; o = onext) {
        !           325:                onext = o->next;
        !           326:                if (!o->jct) {
        !           327:                        rs = ready + o->ogroup->gseq;
        !           328:                        o->next = *rs;
        !           329:                        *rs = o;
        !           330:                        }
        !           331:                }
        !           332:        firstobj = lastobj = 0;
        !           333:        i = i0 = 0;
        !           334:        for(;;) {
        !           335:                if (!(o = ready[i])) {
        !           336:                        i = i0;
        !           337:                        while(!(o = ready[i]))
        !           338:                                if (++i >= ngroup) {
        !           339:                                        if (lastobj) lastobj->next = 0;
        !           340:                                        return firstobj;
        !           341:                                        }
        !           342:                        i0 = i;
        !           343:                        }
        !           344:                ready[i] = o->next;
        !           345:                if (!lastobj) firstobj = o;
        !           346:                else lastobj->next = o;
        !           347:                lastobj = o;
        !           348:                for (j = o->iptr; j; ) {
        !           349:                        reffetch(j, &rc);
        !           350:                        j = rc.rcnext;
        !           351:                        if (j >= nrefc) { j -= nrefc; continue; }
        !           352:                        o1 = rc.rcref->robj;
        !           353:                        if (!o1) continue;
        !           354:                        if (!--o1->jct) {
        !           355:                                k = o1->ogroup->gseq;
        !           356:                                o1->next = ready[k];
        !           357:                                ready[k] = o1;
        !           358:                                if (i0 > k) i0 = k;
        !           359:                                }
        !           360:                        }
        !           361:                }
        !           362:        }
        !           363: 
        !           364: dfs(level, o)
        !           365: int level;
        !           366: struct obj *o;
        !           367: {
        !           368:        struct refc rc;
        !           369:        struct obj *o1;
        !           370:        int level0, s;
        !           371:        static int cycle = 0;
        !           372:        unsigned i, nextrc;
        !           373: 
        !           374:        o->seq = -level;
        !           375:        level0 = -(level + 1);
        !           376:        for (i = o->iptr; i; i = nextrc) {
        !           377:                reffetch(i, &rc);
        !           378:                nextrc = rc.rcnext;
        !           379:                o1 = rc.rcref->robj;
        !           380:                if (!o1 || o == o1 || o1 == obj0) continue;
        !           381:                s = o1->seq;
        !           382:                if (s >= 0) {
        !           383:                        o1->jct++;
        !           384:                        if (s > 0) continue; /* cross link */
        !           385:                        s = dfs(level+1, o1);
        !           386:                        }
        !           387:                else { /* back link */
        !           388:                        if (cyclep && !cycle) {
        !           389:                                fprintf(stderr, "%s: cycle...\n", progname);
        !           390:                                cycle = 1;
        !           391:                                }
        !           392:                        rc.rcnext += nrefc;
        !           393:                        refstore(i, &rc);
        !           394:                        }
        !           395:                if (level0 < s) level0 = s;
        !           396:                }
        !           397:        o->seq = nextseq;
        !           398:        level = -level;
        !           399:        if (level <= level0 && cyclep) {
        !           400:                fprintf(stderr, "%s\n", o->name);
        !           401:                if (level == level0) { cycle = 0; putc('\n',stderr); }
        !           402:                else cycle = 1;
        !           403:                }
        !           404:        if (level > level0 || level == -1) { nextseq++; level0 = level; }
        !           405:        return level0;
        !           406:        }
        !           407: 
        !           408: scream(s, s1)
        !           409: char *s, *s1;
        !           410: {
        !           411:        fprintf(stderr, "%s: ", progname);
        !           412:        fprintf(stderr, s, s1);
        !           413:        exit(1);
        !           414:        }
        !           415: 
        !           416: undef(s,infile)
        !           417: char *s;
        !           418: FILE *infile;
        !           419: {
        !           420:        newgroup("");
        !           421:        newobj("", 1);
        !           422:        newref(s);
        !           423:        }

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