Return to util.c CVS log

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

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

1.1     ! root        1: #include "draw_dag.h"
        !             2: #include "dag.h"
        !             3: #include "paths.h"
        !             4: #include "parsedag.h"
        !             5: #include "defaults.h"
        !             6: #include "unistd.h"
        !             7: 
        !             8: /*** utility functions ***/
        !             9: 
        !            10: char* Infile::gets(char *buf,int n) {
        !            11:        if (!fp) return 0;
        !            12:        line_number++;
        !            13:        return fgets(buf,n,fp);
        !            14: }
        !            15: 
        !            16: Infile nextfile(char** &argv)
        !            17: {
        !            18:        argv++;
        !            19:        while (**argv == '-') argv++;
        !            20:        Infile rv = Infile(*argv);
        !            21:        if (!rv.fp) fprintf(stderr,"%s: can't open %s\n",Cmd_name,*argv);
        !            22:        return rv;
        !            23: }
        !            24: 
        !            25: /*** shared strings ***/
        !            26: 
        !            27: shared_string_t *shared_string_pool;
        !            28: char *newstring(char *init) {
        !            29:        shared_string_t *it
        !            30:                = (shared_string_t*) malloc(sizeof(shared_string_t) + strlen(init));
        !            31:        it->next = shared_string_pool;
        !            32:        shared_string_pool = it;
        !            33:        strcpy(it->data,init);
        !            34:        return it->data;
        !            35: }
        !            36: 
        !            37: void freestrings() {
        !            38:        shared_string_t *q,*p = shared_string_pool;
        !            39:        while (p) {
        !            40:                q = p->next;
        !            41:                free((char*)p);
        !            42:                p = q;
        !            43:        }
        !            44:        shared_string_pool = 0;
        !            45: }
        !            46: 
        !            47: /*** hash table ***/
        !            48: 
        !            49: int hash(register char* s, int size) {
        !            50:        register unsigned int   h;
        !            51:        register int    c;
        !            52: 
        !            53:        h = 0;
        !            54:        while (c = *s++) {
        !            55:                if ((h <<= 1) < 0) h ^= c ^ ((~(((unsigned int)~0) >> 1)) | 1);
        !            56:                else h ^= c;
        !            57:        }
        !            58:        return(h % size);
        !            59: }
        !            60: 
        !            61: const int Hash_extent = 517;
        !            62: struct hashrec {
        !            63:        int                     node;
        !            64:        hashrec         *next;
        !            65: 
        !            66:        hashrec(int argnode, hashrec *argnext) {
        !            67:                node  = argnode;
        !            68:                next  = argnext;
        !            69:        };
        !            70: } *Hashtab[Hash_extent];
        !            71: 
        !            72: boolean expand_graph(int new_size) {
        !            73:                if (! (Node = (DAG_node_t**)realloc((char*)Node,sizeof(DAG_node_t*)*new_size)))
        !            74:                        return false;
        !            75:                else
        !            76:                        if (! (Edge = (DAG_edge_t**)realloc((char*)Edge,sizeof(DAG_edge_t*)*new_size)))
        !            77:                                return false;
        !            78:                return true;
        !            79: }
        !            80: 
        !            81: /* look name and insert in symbol table if not found. return new node's number. */
        !            82: int node_lookup(char *name) {
        !            83:        int h = hash(name,Hash_extent);
        !            84:        for (hashrec *hp = Hashtab[h]; hp; hp = hp->next)
        !            85:                if (!strcmp(name,Node[hp->node]->name)) break;
        !            86:        if (!hp) {
        !            87:                Hashtab[h] = hp =  new hashrec(N,Hashtab[h]);
        !            88: 
        !            89:                if (N > Extent - 1) {
        !            90:                        Extent += Extent;
        !            91:                        if (!expand_graph(Extent)) {
        !            92:                                yyerror("too many nodes, out of memory");
        !            93:                                exit(1);
        !            94:                        }
        !            95:                }
        !            96:                Node[N] = new DAG_node_t();
        !            97:                *Node[N] = Default_node;
        !            98:                Node[N]->setname(name);
        !            99:                Edge[N] = (DAG_edge_t*)0;
        !           100:                N++;
        !           101:        }
        !           102:        return hp->node;
        !           103: }
        !           104: 
        !           105: /*** utility functions for code gen */
        !           106: 
        !           107: void cat_libfile(char* name) {
        !           108:        char buf[BUFSIZ];
        !           109:        if (!Uselib) return;
        !           110:        if (!Lib_path) {
        !           111: #ifdef EXPTOOLS
        !           112:                char *tools = getenv("TOOLS");
        !           113:                if (tools) {
        !           114:                        Lib_path = new char[strlen(Lib_path)+strlen(EXPTOOLS_SUBDIR)+2];
        !           115:                        sprintf(Lib_path,"%s/%s",tools,EXPTOOLS_SUBDIR);
        !           116:                        sprintf(buf,"%s/%s",Lib_path,name);
        !           117:                        if (access(buf,R_OK))
        !           118:                                Lib_path = LIB_PATH;
        !           119:                }
        !           120:                else
        !           121: #endif EXPTOOLS
        !           122:                        Lib_path = LIB_PATH;
        !           123:        }
        !           124:        fflush(stdout);
        !           125:        sprintf(buf,"cat %s/%s",Lib_path,name);
        !           126:        system(buf);
        !           127: }
        !           128: 
        !           129: Point find_edge_midpoint(DAG_edge_t *e) {
        !           130:        int x,y;
        !           131:        for (int npts = 0; e->splinept[npts].y >= 0; npts++);
        !           132:        if (iabs(e->splinept[0].y - e->splinept[npts-1].y) >
        !           133:            iabs(e->splinept[0].x - e->splinept[npts-1].x)) { // "vertical" edge
        !           134:                int i,y1 = 0;
        !           135:                y1 = (e->splinept[0].y + e->splinept[npts-1].y)/2;
        !           136:                for (i = 0; e->splinept[i].y >= 0; i++)
        !           137:                        if (between(e->splinept[i].y,y1,e->splinept[i+1].y)) break;
        !           138:                y = y1;
        !           139:                x = (int) (e->splinept[i].x +
        !           140:                        (double)(y1 - e->splinept[i].y)/(e->splinept[i+1].y-e->splinept[i].y)
        !           141:                        * (e->splinept[i+1].x - e->splinept[i].x));
        !           142:        }
        !           143:        else {                                                                                          // "horizontal" edge
        !           144:                int i,x1 = 0;
        !           145:                x1 = (e->splinept[0].x + e->splinept[npts-1].x)/2;
        !           146:                for (i = 0; e->splinept[i].y >= 0; i++)
        !           147:                        if (between(e->splinept[i].x,x1,e->splinept[i+1].x)) break;
        !           148:                x = x1;
        !           149:                y = (int) (e->splinept[i].y +
        !           150:                        (double)(x1 - e->splinept[i].x)/(e->splinept[i+1].x-e->splinept[i].x)
        !           151:                        * (e->splinept[i+1].y - e->splinept[i].y));
        !           152:        }
        !           153:        Point rv;
        !           154:        rv .x = x; rv .y = y;
        !           155:        return rv;
        !           156: }
        !           157: 
        !           158: static boolean seginter(int x0,int y0, int x1, int y1, int x2, int y2, int x3, int y3,
        !           159: int& xinter, int& yinter) {
        !           160:        double m0,b0,m1,b1,x;
        !           161: 
        !           162:        if ((x0 == x1) && (x2 == x3)) return false;
        !           163:        if (x2 == x3) {swap(x0,x2); swap(x1,x3); swap(y0,y2); swap(y1,y3);}
        !           164:        if (x0 == x1) {
        !           165:                x = x0;
        !           166:        }       
        !           167:        else {
        !           168:                m0 = (y1 - y0)/(double)(x1 - x0);
        !           169:                b0 = y0 - m0*x0;
        !           170:                m1 = (y3 - y2)/(double)(x3 - x2);
        !           171:                b1 = y2 - m1*x2;
        !           172:                if (m1 == m0) {
        !           173:                        if (b0 != b1) return false;
        !           174:                        int l0lowx = min(x0,x1);
        !           175:                        int l0highx = max(x0,x1);
        !           176:                        int l1lowx = min(x2,x3);
        !           177:                        int l1highx = max(x2,x3);
        !           178:                        if (between(l0lowx,l1lowx,l0highx))
        !           179:                                x = l1lowx;
        !           180:                        else if (between(l0lowx,l1highx,l0highx))
        !           181:                                x = l1highx;
        !           182:                        else if (between(l1lowx,l0lowx,l1highx))
        !           183:                                x = l0lowx;
        !           184:                        else return false;
        !           185:                }
        !           186:                else x = (b1 - b0)/(m0 - m1);
        !           187:        }
        !           188: 
        !           189:        if (between(x2,round(x),x3)) {
        !           190:                if (between(y2,round(m1 * x + b1),y3)) {
        !           191:                        yinter = round(m1 * x + b1);
        !           192:                        xinter = round(x);
        !           193:                        return true;
        !           194:                }
        !           195:        }
        !           196:        return false;
        !           197: }
        !           198: 
        !           199: /*
        !           200:  *  return point of intersection of the node 
        !           201:  *  with the ray from (x0,y0) through (x1,y1).
        !           202:  *  p1 must be on the bounding box of the node.
        !           203:  *  assume User_defined nodes are like Box.
        !           204:  */
        !           205: Point find_nodeport(int node, Point p0, Point p1) {
        !           206:        Point rv;
        !           207:        if ((p0.x == p1.x) && (p0.y == p1.y)) {return p0;}
        !           208:        int x0 = p0.x; int y0 = p0.y; int x1 = p1.x; int y1 = p1.y;
        !           209: 
        !           210:        /* handle degenerate case of vertical line segment */
        !           211:        if (x0 == x1) return p1;
        !           212: 
        !           213:        while (1) {
        !           214:                /* normal case */
        !           215:                double m = (double)(y1 - y0) / (double)(x1 - x0); 
        !           216:                double b = y0 - m * x0;
        !           217:                switch(Node[node]->shape.shape_id) {
        !           218:                        case Circle:
        !           219:                        case Doublecircle:
        !           220:                        case Ellipse:
        !           221:                                double s0,s1;   // two solutions (x values)
        !           222:                                //double b1 = m*Node[node]->pos.x + b - Node[node]->pos.y;
        !           223:                                double b1 = (y0 - Node[node]->pos.y) - m * (x0 - Node[node]->pos.x);
        !           224:                                double rx = Node[node]->xsize/2.;
        !           225:                                double ry = Node[node]->ysize/2.;
        !           226:                                double aa = 1/(rx*rx) + (m*m)/(ry*ry);
        !           227:                                double bb = 2.*m*b1/(ry*ry);
        !           228:                                double cc = (b1*b1)/(ry*ry) - 1;
        !           229:                                if (m == 0.) {
        !           230:                                        s0 = rx;
        !           231:                                        s1 = -rx;
        !           232:                                }
        !           233:                                else {
        !           234:                                        double t = bb*bb - 4.*aa*cc;
        !           235:                                        if (t < 0) {
        !           236:                                                if (x1 == Node[node]->pos.x && y1 == Node[node]->pos.y) 
        !           237:                                                        panic("can't find node intersection");
        !           238:                                                x1 = Node[node]->pos.x;
        !           239:                                                y1 = Node[node]->pos.y;
        !           240:                                                continue;
        !           241:                                        }
        !           242:                                        s0 = (-bb + sqrt(t))/(2.*aa);
        !           243:                                        s1 = (-bb - sqrt(t))/(2.*aa);
        !           244:                                }
        !           245:                                s0 += Node[node]->pos.x;
        !           246:                                s1 += Node[node]->pos.x;
        !           247:                                if (distance(s0,m*s0+b,x0,y0) <= distance(s1,m*s1+b,x0,y0)) {
        !           248:                                        rv.x = round(s0);
        !           249:                                        rv.y = round(s0 * m + b);
        !           250:                                }
        !           251:                                else {
        !           252:                                        rv.x = round(s1);
        !           253:                                        rv.y = round(s1 * m + b);
        !           254:                                }
        !           255:                                return rv;
        !           256:                        case Diamond:
        !           257:                                x1 = Node[node]->pos.x;
        !           258:                                y1 = (int)(m*x1 + b);
        !           259:                                switch((sign(x0 - Node[node]->pos.x)== -1) + 2*(sign(y0 - Node[node]->pos.y)== -1)) {
        !           260:                                        case 0:
        !           261:                                                if (seginter(x0,y0,x1,y1,Node[node]->pos.x+Node[node]->xsize/2,Node[node]->pos.y,Node[node]->pos.x,Node[node]->pos.y+Node[node]->ysize/2,rv.x,rv.y)) return rv;
        !           262:                                                break;
        !           263:                                        case 1:
        !           264:                                                if (seginter(x0,y0,x1,y1,Node[node]->pos.x,Node[node]->pos.y+Node[node]->ysize/2,Node[node]->pos.x-Node[node]->xsize/2,Node[node]->pos.y,rv.x,rv.y)) return rv;
        !           265:                                                break;
        !           266:                                        case 2:
        !           267:                                                if (seginter(x0,y0,x1,y1,Node[node]->pos.x,Node[node]->pos.y-Node[node]->ysize/2,Node[node]->pos.x+Node[node]->xsize/2,Node[node]->pos.y,rv.x,rv.y)) return rv;
        !           268:                                                break;
        !           269:                                        case 3:
        !           270:                                                if (seginter(x0,y0,x1,y1,Node[node]->pos.x-Node[node]->xsize/2,Node[node]->pos.y,Node[node]->pos.x,Node[node]->pos.y-Node[node]->ysize/2,rv.x,rv.y)) return rv;
        !           271:                                                break;
        !           272:                                }
        !           273:                        case Box:
        !           274:                        case Square:
        !           275:                        case Plaintext:
        !           276:                        case User_defined:
        !           277:                        default:
        !           278:                                return p1;
        !           279:                }
        !           280:        }
        !           281: }
        !           282: 
        !           283: void reclaim_hashtable() {
        !           284:        for (int i = 0; i < Hash_extent; i++) {
        !           285:                hashrec *h,*h1;
        !           286:                if (Hashtab[i])
        !           287:                        for (h = Hashtab[i], h1 = h->next; h1; h1=h1->next){
        !           288:                                delete h; h = h1;
        !           289:                        }
        !           290:                Hashtab[i] = 0;
        !           291:        }
        !           292: }
        !           293: 
        !           294: void set_output_type(char *name) {
        !           295:        const int n_output_types = 4;
        !           296:        static struct {
        !           297:                char*                   name;
        !           298:                output_lang_t   lang;
        !           299:        } map[] = {     
        !           300:                "pic",          Pic,
        !           301:                "ps",           Postscript,
        !           302:                "simple",       Graphdraw,
        !           303:                "cip",          Cip
        !           304:        };
        !           305:        for (int i = 0; i < n_output_types; i++)
        !           306:                if (!strcmp(name,map[i].name)) {
        !           307:                        Output_type = map[i].lang;
        !           308:                        return;
        !           309:                }
        !           310:        fprintf(stderr,"%s: warning, no output driver for %s, option ignored.\n",
        !           311:                Cmd_name,name);
        !           312: }
        !           313: 
        !           314: void set_page_size(char *arg) {
        !           315:        double  w,h,mw,mh;      /* width, height, margin width, margin height */
        !           316:        int             nargs;
        !           317:        nargs = sscanf(arg,"%lfx%lf,%lfx%lf",&w,&h,&mw,&mh);
        !           318:        if (nargs > 1) {
        !           319:                Page_size.x = (int)(w*Resolution);
        !           320:                Page_size.y = (int)(h*Resolution);
        !           321:        }
        !           322:        if (nargs > 2) {
        !           323:                Margin.x = (int)(mw * Resolution);
        !           324:                if (nargs > 3) Margin.y = (int)(mh * Resolution);
        !           325:                else Margin.y = Margin.x;
        !           326:        }
        !           327:        Page_size.x -= 2*Margin.x;
        !           328:        Page_size.y -= 2*Margin.y;
        !           329:        if (Page_size.x <= 0 || Page_size.y <= 0) {
        !           330:                fprintf(stderr,"%s: warning, bad page or margin size options (ignored)\n",Cmd_name);
        !           331:                Page_size.x = 0; Page_size.y = 0;
        !           332:        }
        !           333: }
        !           334: 
        !           335: options_t reset_options() {
        !           336:        options_t rv;
        !           337: 
        !           338:        rv.quick                =       Default_options_quick;
        !           339:        rv.verbose              =       Default_options_verbose;
        !           340:        rv.rankadjust   =       Default_options_rankadjust;
        !           341:        rv.ranksep              =       Default_options_ranksep;
        !           342:        rv.nodesep              =       Default_options_nodesep;
        !           343:        rv.xbound               =       0;
        !           344:        rv.ybound               =       0;
        !           345: 
        !           346:        rv.n_same_nodes=        0;
        !           347:        rv.same_nodes   =       0;
        !           348:        rv.source_nodes=        0;
        !           349:        rv.sink_nodes   =       0;
        !           350:        return  rv;
        !           351: }
        !           352: 
        !           353: void set_bounds(double xdimen, double ydimen) {
        !           354:        if ((xdimen <= 0.0) || (ydimen <= 0.0)) return;
        !           355:        /* the following because the picture will be rotated down in draw_dag */
        !           356:        if (User.rotated) {double t = xdimen; xdimen = ydimen; ydimen = t;}
        !           357:        Options.xbound = round(xdimen * Resolution);
        !           358:        Options.ybound = round(ydimen * Resolution);
        !           359: }
        !           360: 
        !           361: shape_t::shape_t(int intype, char* invalue) {
        !           362:        const int n_predefined_shapes = 7;
        !           363:        static struct {
        !           364:                char *          n;
        !           365:                shape_id_t      s;
        !           366:        } map[] = {
        !           367:                "Circle", Circle,
        !           368:                "Doublecircle", Doublecircle,
        !           369:                "Box",  Box,
        !           370:                "Ellipse",      Ellipse,
        !           371:                "Square",       Square,
        !           372:                "Plaintext",    Plaintext,
        !           373:                "Diamond",      Diamond
        !           374:        };
        !           375:        type = intype;
        !           376:        value = invalue;
        !           377:        if (type == STRING) {
        !           378:                for (int i = 0; i < n_predefined_shapes; i++) {
        !           379:                        if (!strcmp(invalue,map[i].n)) {
        !           380:                                type    =       intype;
        !           381:                                predefined = true;
        !           382:                                shape_id = map[i].s;
        !           383:                                return;
        !           384:                        }
        !           385:                }
        !           386:        }
        !           387:        predefined = false;
        !           388:        shape_id = User_defined;
        !           389: }

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