![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to util.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / dag|
Return to util.c CVS log | Up to [Research Unix] / researchv10no / cmd / dag |
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.