From 1a7de6e286287f992919e9f774b2b2d6f0269a1a Mon Sep 17 00:00:00 2001 From: ian Date: Sat, 19 Mar 2005 18:56:02 +0000 Subject: [PATCH] generates ours.redactgraph, which needs some work --- layout/.cvsignore | 2 + layout/Makefile | 9 +- layout/extractgraph | 12 ++- layout/graph-data.h | 13 ++- layout/redactgraph.c | 228 +++++++++++++++++++++++++++++++++++++++---- 5 files changed, 235 insertions(+), 29 deletions(-) diff --git a/layout/.cvsignore b/layout/.cvsignore index b1842cc..4877cda 100644 --- a/layout/.cvsignore +++ b/layout/.cvsignore @@ -15,3 +15,5 @@ ui-plan-*.ppm parts.ps *-a.ps ours.graph.c +t.* +ours.redactgraph diff --git a/layout/Makefile b/layout/Makefile index e2e70bb..b4d232f 100644 --- a/layout/Makefile +++ b/layout/Makefile @@ -23,7 +23,7 @@ CPROGS= subseg2display compose-segenco default: $(CPROGS) for-test-ui all: default lpages layers extras for-test-ui: ours.dgram-bot.segcmap subseg2display \ - ui-plan-bot.ppm ours.graph.c + ui-plan-bot.ppm ours.graph.c ours.redactgraph layers: $(LAYERS) lpages: $(LPAGES) @@ -34,6 +34,10 @@ include segencolayers.m o=>$@.new && mv -f $@.new $@ +CFLAGS= -Wall -Wwrite-strings -Wpointer-arith \ + -Wstrict-prototypes -Wmissing-prototypes \ + -Wmissing-declarations -Werror +CPPFLAGS= -D_GNU_SOURCE LINK= $(CC) $(CFLAGS) $(LDFLAGS) -o $@ $+ $(LIBS) NETPBM= -lnetpbm # -lppm @@ -44,6 +48,9 @@ subseg2display: subseg2display.o compose-segenco: compose-segenco.o $(LINK) $(NETPBM) +%.redactgraph: %.graph.o redactgraph.o + $(LINK) + %.d4: %.m4 $(M4INCS) Makefile m4 -s <$< $o diff --git a/layout/extractgraph b/layout/extractgraph index d34be3e..b7b18ed 100755 --- a/layout/extractgraph +++ b/layout/extractgraph @@ -221,12 +221,12 @@ sub writeout () { for $segname (keys %segments) { $segment= $segments{$segname}; $movfeats= $segment->{MovFeats}; - o("static MovFeat movfeats_${segname}[];\n"); + o("static MovFeat movfeats_$segname","[];\n"); o("static Segment segment_$segname= {"); o(" \"$segname\","); o(" ",scalar(@$movfeats),", movfeats_$segname"); o(" };\n"); - o("static MovFeat movfeats_${segname}[]= {"); + o("static MovFeat movfeats_$segname","[]= {"); $delim= ""; for $movfeat (@$movfeats) { o("$delim\n"); @@ -271,7 +271,7 @@ sub writeout () { if ($reverse) { o("/*reverse*/ "); } $sss =~ m,^(\w*)/(([A-Za-z]*)(\d*))$, or die; ($segname, $movfeatpos, $movfeat, $movpos) = ($1,$2,$3,$4); - o("&movfeats_${segname}[", + o("&movfeats_${segname}","[", $segments{$segname}{MovFeatMap}{$movfeat}, "], ", (length $movfeat ? $movpos : 0), @@ -305,8 +305,10 @@ sub writeout () { o("\n }\n};\n"); } o("\n"); - o("Node *nodes_head= ",(@nodes ? '&'.pr(Node,$nodes[0]) : 0),";\n"); - o("Node *nodes_tail= ",(@nodes ? '&'.pr(Node,$nodes[$#nodes]) : 0),";\n"); + o("NodeList all_nodes= { ", + (@nodes ? '&'.pr(Node,$nodes[0]) : 0), ", ", + (@nodes ? '&'.pr(Node,$nodes[$#nodes]) : 0), + " };\n"); } o("/*autogenerated - do not edit*/\n\n"); diff --git a/layout/graph-data.h b/layout/graph-data.h index 977d9d2..9b7f770 100644 --- a/layout/graph-data.h +++ b/layout/graph-data.h @@ -10,17 +10,18 @@ typedef struct Segment Segment; typedef struct MovFeat MovFeat; typedef struct EdgeEnd EdgeEnd; typedef struct Node Node; +typedef struct NodeList NodeList; typedef struct NodeSide NodeSide; struct Segment { - const char *name; /* 0 if unknown (usually elided by extractgraph) */ + const char *segname; /* 0 if unknown (usually elided by extractgraph) */ int n_movfeats; MovFeat *movfeats; /* [0] is fixed */ }; struct MovFeat { Segment *segment; - const char *name; /* 0 if fixed */ + const char *movfeat; /* 0 if fixed */ int n_positions; }; @@ -33,7 +34,7 @@ struct EdgeEnd { struct Edge { double distance; - MovFeat *segment; + MovFeat *subseg; int movpos; /* 0 if fixed */ EdgeEnd ends[2]; }; @@ -49,7 +50,11 @@ struct Node { NodeSide sides[2]; }; -extern Node *nodes_head, *nodes_tail; +struct NodeList { + Node *head, *tail; +}; + +extern NodeList all_nodes; #endif /*GRAPH_DATA_H*/ diff --git a/layout/redactgraph.c b/layout/redactgraph.c index 5729853..129310e 100644 --- a/layout/redactgraph.c +++ b/layout/redactgraph.c @@ -1,6 +1,122 @@ /**/ +#include +#include +#include +#include +#include + +#include "dlist.h" +#include "graph-data.h" + +/*---------- output processing ----------*/ + +static void voutputstuff(int trace, const char *fmt, va_list al) { + static struct OutputBuf { + int used, allocd; + char *buf; + } bufs[2]; + + struct OutputBuf *b; + char *s, *p, *newline; + int r, l; + + b= &bufs[trace]; + r= vasprintf(&s,fmt,al); if (r<0) { perror("vasprintf"); exit(16); } + p= s; + + for (;;) { + newline= strchr(p,'\n'); + if (newline) { *newline= 0; } + l= strlen(p); + if (l+b->used > b->allocd) { + b->allocd= l+b->used; + b->buf= realloc(b->buf, b->allocd); + if (!b->buf) { perror("realloc voutputstuff"); exit(16); } + } + memcpy(b->buf+b->used, p, l); + b->used += l; + + if (!newline) break; + + if (trace) { fputs("# ",stdout); } + fwrite(b->buf, 1,b->used, stdout); + putc('\n',stdout); + if (ferror(stdout) || fflush(stdout)) { + perror("stdout voutputstuff"); exit(12); + } + b->used= 0; + p= newline+1; + } + + free(s); +} + +#define OF(fn,tr) \ + static void v##fn(const char *fmt, va_list al) { \ + voutputstuff(tr,fmt,al); \ + } \ + static void fn(const char *fmt, ...) { \ + va_list al; \ + va_start(al,fmt); \ + v##fn(fmt,al); \ + va_end(al); \ + } +OF(output,0) +OF(trace,1) + +/*---------- general graph-manipulation and printing stuff ----------*/ + +static void trace_node(Node *node) { + trace("n%p",node); +} + +static void trace_edgeend(EdgeEnd *edge) { + trace("n%p%c",edge->node->node,"OI"[edge->node->side]); +} + +static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) { + return &thisend->edge->ends[!thisend->end]; +} + +static int count_edges(const NodeSide *node) { + int count; + const EdgeEnd *edge; + + for (count=0, edge=node->head; + edge; + count++, edge=edge->next); + return count; +} + +static void edgeend_disconnect(EdgeEnd *toremove) { + LIST_UNLINK(*toremove->node, toremove); +} + +static void edgeend_replumb(EdgeEnd *tomove, NodeSide *newtarget) { + edgeend_disconnect(tomove); + LIST_LINK_TAIL(*newtarget, tomove); + tomove->node= newtarget; +} + +static void edge_delete(Edge *edge) { + edgeend_disconnect(&edge->ends[0]); + edgeend_disconnect(&edge->ends[1]); +} + +static void node_surely_orphaned(Node *node) { + assert(!node->sides[0].head); + assert(!node->sides[1].head); + LIST_UNLINK(all_nodes, node); +} + +/*---------- operations ----------*/ + static void extendsplits(void) { + int pass, rightside, n; + Node *node; + EdgeEnd *leftedge, *rightedge; + /* * Whenever we have a node which has one or more moveable feature * subsegments, part of the same moveable feature, on one side, and @@ -18,7 +134,7 @@ static void extendsplits(void) { for (;;) { pass++; - for (node=nodes_head; node; node=node->next) { + for (node=all_nodes.head; node; node=node->next) { for (rightside=0; rightside<2; rightside++) { trace("extendsplit pass %d node ",pass); trace_node(node); trace("/%d ",rightside); @@ -27,7 +143,7 @@ static void extendsplits(void) { goto no_extend_this; } leftedge= node->sides[!rightside].head; - if (leftedge->edge->movfeatpos) { + if (leftedge->edge->subseg->movfeat) { trace("no: lhs moveable\n"); goto no_extend_this; } @@ -38,14 +154,15 @@ static void extendsplits(void) { for (rightedge= node->sides[rightside].head; rightedge; rightedge= rightedge->next) { - if (!rightedge->edge->movfeatpos) { + if (!rightedge->edge->subseg->movfeat) { trace("no: rhs fixed ("); trace_edgeend(rightedge); trace(")\n"); goto no_extend_this; } - if (strcmp(leftedge->edge->segment, rightedge->edge->segment)) { + if (leftedge->edge->subseg->segment != + rightedge->edge->subseg->segment) { trace("no: lhs seg %s, rhs seg %s (", - leftedge->edge->segment - rightedge->edge->segment); + leftedge->edge->subseg->segment->segname, + rightedge->edge->subseg->segment->segname); trace_edgeend(rightedge); trace(")\n"); goto no_extend_this; } @@ -63,7 +180,7 @@ static void extendsplits(void) { rightedge; rightedge= rightedge->next) { rightedge->edge->distance += leftedge->edge->distance; - edge_replumb(rightedge, edgeend_otherend(leftedge)->node); + edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node); } edge_delete(leftedge->edge); node_surely_orphaned(node); @@ -71,16 +188,15 @@ static void extendsplits(void) { } } -static EdgeEnd *edgeend_otherend(EdgeEnd *thisend) { - return &thisend->edge->ends[!thisend->end]; -} - static void elimtrivial(void) { /* Eliminate trivial nodes: ones which have only two edges, which * come in on opposite sides, have the same subsegspec, and with the * two ends identically aligned. */ - for (node=nodes_head; node; node=next_node) { + EdgeEnd *leftedge, *rightedge; + Node *node, *next_node; + + for (node=all_nodes.head; node; node=next_node) { next_node=node->next; trace("elimtrivial node "); trace_node(node); trace(" "); if (!(count_edges(&node->sides[0])==1 && @@ -90,13 +206,12 @@ static void elimtrivial(void) { } leftedge= node->sides[0].head; rightedge= node->sides[0].head; - if (strcmp(leftedge->edge.segment,rightedge->edge.segment)) { - trace("no, segments differ\n"); + if (leftedge->edge->subseg != rightedge->edge->subseg) { + trace("no, (sub)segments differ\n"); continue; } - if (!!leftedge->edge.movfeatpos != !!rightedge->edge.movfeatpos || - strcmp(leftedge->edge.movfeatpos, rightedge->edge.movfeatpos)) { - trace("no, movfeatpos's differ\n"); + if (leftedge->edge->movpos != rightedge->edge->movpos) { + trace("no, movpos's differ\n"); continue; } if (leftedge->end == rightedge->end) { @@ -105,7 +220,7 @@ static void elimtrivial(void) { } trace(" yes:\n"); rightedge->edge->distance += leftedge->edge->distance; - edge_replumb(rightedge, edgeend_otherend(leftedge)->node); + edgeend_replumb(rightedge, edgeend_otherend(leftedge)->node); edge_delete(leftedge->edge); node_surely_orphaned(node); trace(" elimtrivial operation complete\n"); @@ -115,4 +230,79 @@ static void elimtrivial(void) { static void consistency(void) { } -static void print +static void printforneato(void) { + Node *node; + EdgeEnd *edgeend; + Edge *edge; + int side; + + output("digraph L {\n"); + + for (node=all_nodes.head; node; node=node->next) { + output(" n%pO -> n%pI [len=0];\n", + node, node); + for (side=0; side<2; side++) { + for (edgeend=node->sides[side].head; edgeend; edgeend=edgeend->next) { + if (edgeend->end) continue; /* do each edge once, from end 0, only */ + edge= edgeend->edge; + output(" n%p%c -> n%p%c [label=\"", + edge->ends[0].node->node, "OI"[edge->ends[0].node->side], + edge->ends[1].node->node, "OI"[edge->ends[1].node->side]); + if (!edge->subseg->segment->segname) { + output("?"); + } else { + output(edge->subseg->segment->segname); + if (edge->subseg->movfeat) { + output("/%s%d",edge->subseg->movfeat,edge->movpos); + } + } + output("\"];\n"); + } + } + } + output("}\n"); +} + +typedef struct { + const char *name; + void (*fn)(void); +} OpInfo; + +static const OpInfo opinfos[]= { +#define OI(x) { #x, x }, + OI(printforneato) + OI(consistency) + OI(extendsplits) + OI(elimtrivial) + { 0,0 } +}; + +static void usage(void) { + const OpInfo *oi; + + fprintf(stderr, + "usage: .../redactgraph [...]\n" + "operations:\n"); + for (oi=opinfos; oi->name; oi++) { + fprintf(stderr," %s\n",oi->name); + } + fflush(stderr); + exit(8); +} + +int main(int argc, const char *const *argv) { + const OpInfo *oi; + const char *arg; + + if (!argv[0] || !argv[1]) usage(); + + while ((arg= *++argv)) { + for (oi=opinfos; oi->name && strcmp(arg,oi->name); oi++); + if (!oi->name) usage(); + oi->fn(); + } + trace("\n"); + output("\n"); + if (ferror(stdout) || fflush(stdout)) { perror("stdout"); exit(12); } + exit(0); +} -- 2.30.2