Index: src/Makefile.am =================================================================== --- src/Makefile.am (revision 65) +++ src/Makefile.am (revision 66) @@ -116,6 +116,7 @@ print.c \ print.h \ rats.c \ + rats_mincut.c \ rats.h \ remove.c \ remove.h \ Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision 65) +++ src/Makefile.in (revision 66) @@ -203,11 +203,11 @@ mtspace.c mtspace.h mymem.c mymem.h netlist.c parse_l.h \ parse_l.l parse_y.h parse_y.y pcb-printf.c pcb-printf.h \ polygon.c polygon.h polygon1.c polyarea.h puller.c print.c \ - print.h rats.c rats.h remove.c remove.h report.c report.h \ - res_parse.y res_lex.l resource.h rotate.c rotate.h rtree.c \ - rtree.h rubberband.c rubberband.h search.c search.h select.c \ - select.h set.c set.h strflags.c strflags.h thermal.c thermal.h \ - undo.c undo.h vector.c vector.h vendor.c vendor.h \ + print.h rats.c rats_mincut.c rats.h remove.c remove.h report.c \ + report.h res_parse.y res_lex.l resource.h rotate.c rotate.h \ + rtree.c rtree.h rubberband.c rubberband.h search.c search.h \ + select.c select.h set.c set.h strflags.c strflags.h thermal.c \ + thermal.h undo.c undo.h vector.c vector.h vendor.c vendor.h \ hid/common/actions.c hid/common/actions.h hid/common/flags.c \ hid/common/hidinit.c hid/common/hidinit.h \ hid/common/hidnogui.c hid/common/hidnogui.h \ @@ -235,15 +235,15 @@ mtspace.$(OBJEXT) mymem.$(OBJEXT) netlist.$(OBJEXT) \ parse_l.$(OBJEXT) parse_y.$(OBJEXT) pcb-printf.$(OBJEXT) \ polygon.$(OBJEXT) polygon1.$(OBJEXT) puller.$(OBJEXT) \ - print.$(OBJEXT) rats.$(OBJEXT) remove.$(OBJEXT) \ - report.$(OBJEXT) res_parse.$(OBJEXT) res_lex.$(OBJEXT) \ - rotate.$(OBJEXT) rtree.$(OBJEXT) rubberband.$(OBJEXT) \ - search.$(OBJEXT) select.$(OBJEXT) set.$(OBJEXT) \ - strflags.$(OBJEXT) thermal.$(OBJEXT) undo.$(OBJEXT) \ - vector.$(OBJEXT) vendor.$(OBJEXT) hid/common/actions.$(OBJEXT) \ - hid/common/flags.$(OBJEXT) hid/common/hidinit.$(OBJEXT) \ - hid/common/hidnogui.$(OBJEXT) hid/common/extents.$(OBJEXT) \ - hid/common/draw_helpers.$(OBJEXT) \ + print.$(OBJEXT) rats.$(OBJEXT) rats_mincut.$(OBJEXT) \ + remove.$(OBJEXT) report.$(OBJEXT) res_parse.$(OBJEXT) \ + res_lex.$(OBJEXT) rotate.$(OBJEXT) rtree.$(OBJEXT) \ + rubberband.$(OBJEXT) search.$(OBJEXT) select.$(OBJEXT) \ + set.$(OBJEXT) strflags.$(OBJEXT) thermal.$(OBJEXT) \ + undo.$(OBJEXT) vector.$(OBJEXT) vendor.$(OBJEXT) \ + hid/common/actions.$(OBJEXT) hid/common/flags.$(OBJEXT) \ + hid/common/hidinit.$(OBJEXT) hid/common/hidnogui.$(OBJEXT) \ + hid/common/extents.$(OBJEXT) hid/common/draw_helpers.$(OBJEXT) \ hid/common/hid_resource.$(OBJEXT) pcb-mincut/graph.$(OBJEXT) \ pcb-mincut/solve.$(OBJEXT) $(am__objects_12) $(am__objects_14) \ $(am__objects_16) @@ -603,20 +603,20 @@ mirror.h misc.c misc.h move.c move.h mtspace.c mtspace.h \ mymem.c mymem.h netlist.c parse_l.h parse_l.l parse_y.h \ parse_y.y pcb-printf.c pcb-printf.h polygon.c polygon.h \ - polygon1.c polyarea.h puller.c print.c print.h rats.c rats.h \ - remove.c remove.h report.c report.h res_parse.y res_lex.l \ - resource.h rotate.c rotate.h rtree.c rtree.h rubberband.c \ - rubberband.h search.c search.h select.c select.h set.c set.h \ - strflags.c strflags.h thermal.c thermal.h undo.c undo.h \ - vector.c vector.h vendor.c vendor.h hid/common/actions.c \ - hid/common/actions.h hid/common/flags.c hid/common/hidinit.c \ - hid/common/hidinit.h hid/common/hidnogui.c \ - hid/common/hidnogui.h hid/common/extents.c \ - hid/common/draw_helpers.c hid/common/draw_helpers.h \ - hid/common/hid_resource.c hid/common/hid_resource.h \ - hid/hidint.h pcb-mincut/graph.c pcb-mincut/graph.h \ - pcb-mincut/solve.c pcb-mincut/solve.h $(am__append_2) \ - $(am__append_5) $(am__append_7) + polygon1.c polyarea.h puller.c print.c print.h rats.c \ + rats_mincut.c rats.h remove.c remove.h report.c report.h \ + res_parse.y res_lex.l resource.h rotate.c rotate.h rtree.c \ + rtree.h rubberband.c rubberband.h search.c search.h select.c \ + select.h set.c set.h strflags.c strflags.h thermal.c thermal.h \ + undo.c undo.h vector.c vector.h vendor.c vendor.h \ + hid/common/actions.c hid/common/actions.h hid/common/flags.c \ + hid/common/hidinit.c hid/common/hidinit.h \ + hid/common/hidnogui.c hid/common/hidnogui.h \ + hid/common/extents.c hid/common/draw_helpers.c \ + hid/common/draw_helpers.h hid/common/hid_resource.c \ + hid/common/hid_resource.h hid/hidint.h pcb-mincut/graph.c \ + pcb-mincut/graph.h pcb-mincut/solve.c pcb-mincut/solve.h \ + $(am__append_2) $(am__append_5) $(am__append_7) EXTRA_pcb_SOURCES = ${DBUS_SRCS} ${GL_SRCS} toporouter.c toporouter.h DBUS_SRCS = \ dbus-pcbmain.c \ @@ -1185,6 +1185,7 @@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/print.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/puller.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/rats.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/rats_mincut.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/remove.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/report.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/res_lex.Po@am__quote@ Index: src/rats.c =================================================================== --- src/rats.c (revision 65) +++ src/rats.c (revision 66) @@ -57,6 +57,7 @@ #include "search.h" #include "set.h" #include "undo.h" +#include "rats_mincut.h" #ifdef HAVE_LIBDMALLOC #include @@ -358,241 +359,6 @@ memset (&Netl->Net[Netl->NetN], 0, sizeof (NetType)); } -#include "pcb-mincut/graph.h" - -typedef struct short_conn_s short_conn_t; -struct short_conn_s { - int gid; /* id in the graph */ -/* int from_type; - AnyObjectType *from;*/ - int from_id; - int to_type; - AnyObjectType *to; - found_conn_type_t type; - short_conn_t *next; -}; - -static short_conn_t *short_conns = NULL; -static int num_short_conns = 0; -static int short_conns_maxid = 0; - -static void proc_short_cb(int current_type, void *current_obj, int from_type, void *from_obj, found_conn_type_t type) -{ - AnyObjectType *curr = current_obj, *from = from_obj; - short_conn_t *s; - - s = malloc(sizeof(short_conn_t)); -/* s->from_type = from_type; - s->from = from;*/ - s->from_id = from == NULL ? -1 : from->ID; - s->to_type = current_type; - s->to = curr; - s->type = type; - s->next = short_conns; - short_conns = s; - if (curr->ID > short_conns_maxid) - short_conns_maxid = curr->ID; - num_short_conns++; - - - - - printf(" found %d %d/%p type %d from %d\n", current_type, curr->ID, current_obj, type, from == NULL ? -1 : from->ID); - - -} - -static void proc_short(PinType *pin, PadType *pad) -{ - find_callback_t old_cb; - Coord x, y; - short_conn_t *n, **lut_by_oid, **lut_by_gid, *next; - int gids; - gr_t *g; - void *S, *T; - int *solution; - int i; - - /* only one should be set, but one must be set */ - assert((pin != NULL) || (pad != NULL)); - assert((pin == NULL) || (pad == NULL)); - - if (pin != NULL) { - printf("short on pin!\n"); - SET_FLAG (WARNFLAG, pin); - x = pin->X; - y = pin->Y; - } - else if (pad != NULL) { - printf("short on pad!\n"); - SET_FLAG (WARNFLAG, pad); - if (TEST_FLAG (EDGE2FLAG, pad)) { - x = pad->Point2.X; - y = pad->Point2.Y; - } - else { - x = pad->Point1.X; - y = pad->Point1.Y; - } - } - -short_conns = NULL; -num_short_conns = 0; -short_conns_maxid = 0; - - /* perform a search using MINCUTFLAG, calling back proc_short_cb() with the connections */ - old_cb = find_callback; - find_callback = proc_short_cb; - SaveFindFlag(MINCUTFLAG); - LookupConnection (x, y, false, 1, MINCUTFLAG); - - printf("- alloced for %d\n", (short_conns_maxid+1)); - lut_by_oid = calloc(sizeof(short_conn_t *), (short_conns_maxid+1)); - lut_by_gid = calloc(sizeof(short_conn_t *), (num_short_conns+3)); - - g = gr_alloc(num_short_conns+2); - - g->node2name = calloc(sizeof(char *), (num_short_conns+2)); - - /* conn 0 is S and conn 1 is T */ - for(n = short_conns, gids=2; n != NULL; n = n->next, gids++) { - char *s, *typ; - n->gid = gids; - printf(" {%d} found %d %d/%p type %d from %d\n", n->gid, n->to_type, n->to->ID, n->to, n->type, n->from_id); - lut_by_oid[n->to->ID] = n; - lut_by_gid[n->gid] = n; - - s = malloc(256); - switch(n->to_type) { - case PIN_TYPE: typ = "pin"; break; - case VIA_TYPE: typ = "via"; break; - case PAD_TYPE: typ = "pad"; break; - case LINE_TYPE: typ = "line"; break; - default: typ="other"; break; - } - sprintf(s, "%s #%d", typ, n->to->ID); - g->node2name[n->gid] = s; - } - g->node2name[0] = strdup("S"); - g->node2name[1] = strdup("T"); - - S = NULL; - T = NULL; - for(n = short_conns; n != NULL; n = n->next) { - short_conn_t *from; - void *spare; - - spare = NULL; - if (n->to_type == PIN_TYPE) - spare = ((PinType *)n->to)->Spare; - if (n->to_type == PAD_TYPE) - spare = ((PadType *)n->to)->Spare; - if (spare != NULL) { - void *net = &(((LibraryMenuTypePtr)spare)->Name[2]); - printf(" net=%s\n", net); - if (S == NULL) { - printf(" -> became S\n"); - S = net; - } - else if ((T == NULL) && (net != S)) { - printf(" -> became T\n"); - T = net; - } - - if (net == S) - gr_add_(g, n->gid, 0, 100000); - else if (net == T) - gr_add_(g, n->gid, 1, 100000); - } - /* if we have a from object, look it up and make a connection between the two gids */ - if (n->from_id >= 0) { - int weight; - from = lut_by_oid[n->from_id]; - /* weight: 1 for connections we can break, large value for connections we shall not break */ - if ((n->type == FCT_COPPER) || (n->type == FCT_START)) - weight = 1; - else - weight = 10000; - if (from != NULL) { - gr_add_(g, n->gid, from->gid, weight); - printf(" CONN %d %d\n", n->gid, from->gid); - } - } - } - - static int drw = 0; - char gfn[256]; - drw++; - sprintf(gfn, "A_%d_a", drw); - printf("gfn=%s\n", gfn); - gr_draw(g, gfn, "png"); - - solution = solve(g); - -/* sprintf(gfn, "A_%d_b", drw); - printf("gfn=%s\n", gfn); - gr_draw(g, gfn, "png");*/ - - printf("Would cut:\n"); - for(i = 0; solution[i] != -1; i++) { - short_conn_t *s; - printf("%d:", i); - s = lut_by_gid[solution[i]]; - printf("%d %p", solution[i], s); - if (s != NULL) { - SET_FLAG (WARNFLAG, s->to); - printf(" -> %d", s->to->ID); - } - printf("\n"); - } - - free(solution); - free(lut_by_oid); - free(lut_by_gid); - - for(n = short_conns; n != NULL; n = next) { - next = n->next; - free(n); - } - - - ResetFoundLinesAndPolygons(false); - ResetFoundPinsViasAndPads(false); - RestoreFindFlag(); - - find_callback = old_cb; -} - -typedef struct pinpad_s pinpad_t; -struct pinpad_s { - PinType *pin; - PadType *pad; - pinpad_t *next; -}; - -static pinpad_t *shorts = NULL; - -static void found_short(PinType *pin, PadType *pad) -{ - pinpad_t *pp; - pp = malloc(sizeof(pinpad_t)); - pp->pin = pin; - pp->pad = pad; - pp->next = shorts; - shorts = pp; -} - -static void proc_shorts(void) -{ - pinpad_t *n, *next; - for(n = shorts; n != NULL; n = next) { - next = n->next; - proc_short(n->pin, n->pad); - free(n); - } - shorts = NULL; -} - static bool CheckShorts (LibraryMenuTypePtr theNet) { @@ -617,7 +383,7 @@ &theNet->Name[2], UNKNOWN (NAMEONPCB_NAME (element)), UNKNOWN (pin->Number)); - found_short(pin, NULL); + rat_found_short(pin, NULL); continue; } newone = true; @@ -637,7 +403,7 @@ Message (_("Warning! Net \"%s\" is shorted to net \"%s\"\n"), &theNet->Name[2], &((LibraryMenuTypePtr) (pin->Spare))->Name[2]); - found_short(pin, NULL); + rat_found_short(pin, NULL); } } } @@ -655,7 +421,7 @@ &theNet->Name[2], UNKNOWN (NAMEONPCB_NAME (element)), UNKNOWN (pad->Number)); - found_short(NULL, pad); + rat_found_short(NULL, pad); continue; } newone = true; @@ -675,7 +441,7 @@ Message (_("Warning! Net \"%s\" is shorted to net \"%s\"\n"), &theNet->Name[2], &((LibraryMenuTypePtr) (pad->Spare))->Name[2]); - found_short(NULL, pad); + rat_found_short(NULL, pad); } } } @@ -1030,7 +796,7 @@ return (true); if (Warned || changed) { - proc_shorts(); + rat_proc_shorts(); Draw (); } Index: src/rats_mincut.c =================================================================== --- src/rats_mincut.c (nonexistent) +++ src/rats_mincut.c (revision 66) @@ -0,0 +1,263 @@ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include +#include +#include + +#include "global.h" + +#include "create.h" +#include "data.h" +#include "draw.h" +#include "error.h" +#include "file.h" +#include "find.h" +#include "misc.h" +#include "mymem.h" +#include "polygon.h" +#include "rats.h" +#include "search.h" +#include "set.h" +#include "undo.h" + +#ifdef HAVE_LIBDMALLOC +#include +#endif + +#include "rats.h" +#include "pcb-mincut/graph.h" + +typedef struct short_conn_s short_conn_t; +struct short_conn_s { + int gid; /* id in the graph */ +/* int from_type; + AnyObjectType *from;*/ + int from_id; + int to_type; + AnyObjectType *to; + found_conn_type_t type; + short_conn_t *next; +}; + +static short_conn_t *short_conns = NULL; +static int num_short_conns = 0; +static int short_conns_maxid = 0; + +static void proc_short_cb(int current_type, void *current_obj, int from_type, void *from_obj, found_conn_type_t type) +{ + AnyObjectType *curr = current_obj, *from = from_obj; + short_conn_t *s; + + s = malloc(sizeof(short_conn_t)); +/* s->from_type = from_type; + s->from = from;*/ + s->from_id = from == NULL ? -1 : from->ID; + s->to_type = current_type; + s->to = curr; + s->type = type; + s->next = short_conns; + short_conns = s; + if (curr->ID > short_conns_maxid) + short_conns_maxid = curr->ID; + num_short_conns++; + + + + + printf(" found %d %d/%p type %d from %d\n", current_type, curr->ID, current_obj, type, from == NULL ? -1 : from->ID); + + +} + +static void proc_short(PinType *pin, PadType *pad) +{ + find_callback_t old_cb; + Coord x, y; + short_conn_t *n, **lut_by_oid, **lut_by_gid, *next; + int gids; + gr_t *g; + void *S, *T; + int *solution; + int i; + + /* only one should be set, but one must be set */ + assert((pin != NULL) || (pad != NULL)); + assert((pin == NULL) || (pad == NULL)); + + if (pin != NULL) { + printf("short on pin!\n"); + SET_FLAG (WARNFLAG, pin); + x = pin->X; + y = pin->Y; + } + else if (pad != NULL) { + printf("short on pad!\n"); + SET_FLAG (WARNFLAG, pad); + if (TEST_FLAG (EDGE2FLAG, pad)) { + x = pad->Point2.X; + y = pad->Point2.Y; + } + else { + x = pad->Point1.X; + y = pad->Point1.Y; + } + } + +short_conns = NULL; +num_short_conns = 0; +short_conns_maxid = 0; + + /* perform a search using MINCUTFLAG, calling back proc_short_cb() with the connections */ + old_cb = find_callback; + find_callback = proc_short_cb; + SaveFindFlag(MINCUTFLAG); + LookupConnection (x, y, false, 1, MINCUTFLAG); + + printf("- alloced for %d\n", (short_conns_maxid+1)); + lut_by_oid = calloc(sizeof(short_conn_t *), (short_conns_maxid+1)); + lut_by_gid = calloc(sizeof(short_conn_t *), (num_short_conns+3)); + + g = gr_alloc(num_short_conns+2); + + g->node2name = calloc(sizeof(char *), (num_short_conns+2)); + + /* conn 0 is S and conn 1 is T */ + for(n = short_conns, gids=2; n != NULL; n = n->next, gids++) { + char *s, *typ; + n->gid = gids; + printf(" {%d} found %d %d/%p type %d from %d\n", n->gid, n->to_type, n->to->ID, n->to, n->type, n->from_id); + lut_by_oid[n->to->ID] = n; + lut_by_gid[n->gid] = n; + + s = malloc(256); + switch(n->to_type) { + case PIN_TYPE: typ = "pin"; break; + case VIA_TYPE: typ = "via"; break; + case PAD_TYPE: typ = "pad"; break; + case LINE_TYPE: typ = "line"; break; + default: typ="other"; break; + } + sprintf(s, "%s #%d", typ, n->to->ID); + g->node2name[n->gid] = s; + } + g->node2name[0] = strdup("S"); + g->node2name[1] = strdup("T"); + + S = NULL; + T = NULL; + for(n = short_conns; n != NULL; n = n->next) { + short_conn_t *from; + void *spare; + + spare = NULL; + if (n->to_type == PIN_TYPE) + spare = ((PinType *)n->to)->Spare; + if (n->to_type == PAD_TYPE) + spare = ((PadType *)n->to)->Spare; + if (spare != NULL) { + void *net = &(((LibraryMenuTypePtr)spare)->Name[2]); + printf(" net=%s\n", net); + if (S == NULL) { + printf(" -> became S\n"); + S = net; + } + else if ((T == NULL) && (net != S)) { + printf(" -> became T\n"); + T = net; + } + + if (net == S) + gr_add_(g, n->gid, 0, 100000); + else if (net == T) + gr_add_(g, n->gid, 1, 100000); + } + /* if we have a from object, look it up and make a connection between the two gids */ + if (n->from_id >= 0) { + int weight; + from = lut_by_oid[n->from_id]; + /* weight: 1 for connections we can break, large value for connections we shall not break */ + if ((n->type == FCT_COPPER) || (n->type == FCT_START)) + weight = 1; + else + weight = 10000; + if (from != NULL) { + gr_add_(g, n->gid, from->gid, weight); + printf(" CONN %d %d\n", n->gid, from->gid); + } + } + } + + static int drw = 0; + char gfn[256]; + drw++; + sprintf(gfn, "A_%d_a", drw); + printf("gfn=%s\n", gfn); + gr_draw(g, gfn, "png"); + + solution = solve(g); + +/* sprintf(gfn, "A_%d_b", drw); + printf("gfn=%s\n", gfn); + gr_draw(g, gfn, "png");*/ + + printf("Would cut:\n"); + for(i = 0; solution[i] != -1; i++) { + short_conn_t *s; + printf("%d:", i); + s = lut_by_gid[solution[i]]; + printf("%d %p", solution[i], s); + if (s != NULL) { + SET_FLAG (WARNFLAG, s->to); + printf(" -> %d", s->to->ID); + } + printf("\n"); + } + + free(solution); + free(lut_by_oid); + free(lut_by_gid); + + for(n = short_conns; n != NULL; n = next) { + next = n->next; + free(n); + } + + + ResetFoundLinesAndPolygons(false); + ResetFoundPinsViasAndPads(false); + RestoreFindFlag(); + + find_callback = old_cb; +} + +typedef struct pinpad_s pinpad_t; +struct pinpad_s { + PinType *pin; + PadType *pad; + pinpad_t *next; +}; + +static pinpad_t *shorts = NULL; + +void rat_found_short(PinType *pin, PadType *pad) +{ + pinpad_t *pp; + pp = malloc(sizeof(pinpad_t)); + pp->pin = pin; + pp->pad = pad; + pp->next = shorts; + shorts = pp; +} + +void rat_proc_shorts(void) +{ + pinpad_t *n, *next; + for(n = shorts; n != NULL; n = next) { + next = n->next; + proc_short(n->pin, n->pad); + free(n); + } + shorts = NULL; +} Index: src/rats_mincut.h =================================================================== --- src/rats_mincut.h (nonexistent) +++ src/rats_mincut.h (revision 66) @@ -0,0 +1,2 @@ +void rat_found_short(PinType *pin, PadType *pad); +void rat_proc_shorts(void);