src/rats.c

   1 /*!
   2  * \file src/rats.c
   3  *
   4  * \brief Rats nest routines.
   5  *
   6  * <hr>
   7  *
   8  * <h1><b>Copyright.</b></h1>\n
   9  *
  10  * PCB, interactive printed circuit board design
  11  *
  12  * Copyright (C) 1994,1995,1996 Thomas Nau
  13  *
  14  * Copyright (C) 1997, harry eaton
  15  *
  16  * This module, rats.c, was written and is Copyright (C) 1997 by
  17  * harry eaton.
  18  *
  19  * This module is also subject to the GNU GPL as described below.
  20  *
  21  * This program is free software; you can redistribute it and/or modify
  22  * it under the terms of the GNU General Public License as published by
  23  * the Free Software Foundation; either version 2 of the License, or
  24  * (at your option) any later version.
  25  *
  26  * This program is distributed in the hope that it will be useful,
  27  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  28  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  29  * GNU General Public License for more details.
  30  *
  31  * You should have received a copy of the GNU General Public License
  32  * along with this program; if not, write to the Free Software
  33  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  34  */
  35
  36 /* Change History:
  37  * Started 6/10/97
  38  * Added support for minimum length rat lines 6/13/97
  39  * rat lines to nearest line/via 8/29/98
  40  * support for netlist window 10/24/98
  41  */
  42
  43 #ifdef HAVE_CONFIG_H
  44 #include "config.h"
  45 #endif
  46
  47 #include <math.h>
  48 #include <stdio.h>
  49
  50 #include "global.h"
  51
  52 #include "create.h"
  53 #include "data.h"
  54 #include "draw.h"
  55 #include "error.h"
  56 #include "file.h"
  57 #include "find.h"
  58 #include "misc.h"
  59 #include "mymem.h"
  60 #include "polygon.h"
  61 #include "rats.h"
  62 #include "search.h"
  63 #include "set.h"
  64 #include "undo.h"
  65
  66 #ifdef HAVE_LIBDMALLOC
  67 #include <dmalloc.h>
  68 #endif
  69
  70 #define TRIEDFIRST 0x1
  71 #define BESTFOUND 0x2
  72
  73 /* ---------------------------------------------------------------------------
  74  * some forward declarations
  75  */
  76 static bool FindPad (char *, char *, ConnectionType *, bool);
  77 static bool ParseConnection (char *, char *, char *);
  78 static bool DrawShortestRats (NetListType *, void (*)(register ConnectionType *, register ConnectionType *, register RouteStyleType *));
  79 static bool GatherSubnets (NetListType *, bool, bool);
  80 static bool CheckShorts (LibraryMenuType *);
  81 static void TransferNet (NetListType *, NetType *, NetType *);
  82
  83 /* ---------------------------------------------------------------------------
  84  * some local identifiers
  85  */
  86 static bool badnet = false;
  87 static Cardinal top_group, bottom_group;        /* layer group holding top/bottom side */
  88
  89 /*!
  90  * \brief Parse a connection description from a string.
  91  *
  92  * Puts the element name in the string and the pin number in
  93  * the number.
  94  *
  95  * \return If a valid connection is found, it returns the number of characters
  96  * processed from the string, otherwise it returns 0.
  97  */
  98 static bool
  99 ParseConnection (char *InString, char *ElementName, char *PinNum)
 100 {
 101   int i, j;
 102
 103   /* copy element name portion */
 104   for (j = 0; InString[j] != '\0' && InString[j] != '-'; j++)
 105     ElementName[j] = InString[j];
 106   if (InString[j] == '-')
 107     {
 108       for (i = j; i > 0 && ElementName[i - 1] >= 'a'; i--);
 109       ElementName[i] = '\0';
 110       for (i = 0, j++; InString[j] != '\0'; i++, j++)
 111         PinNum[i] = InString[j];
 112       PinNum[i] = '\0';
 113       return (false);
 114     }
 115   else
 116     {
 117       ElementName[j] = '\0';
 118       Message (_("Bad net-list format encountered near: \"%s\"\n"),
 119                ElementName);
 120       return (true);
 121     }
 122 }
 123
 124 /*!
 125  * \brief Find a particular pad from an element name and pin number.
 126  */
 127 static bool
 128 FindPad (char *ElementName, char *PinNum, ConnectionType * conn, bool Same)
 129 {
 130   ElementType *element;
 131   GList *i;
 132
 133   if ((element = SearchElementByName (PCB->Data, ElementName)) == NULL)
 134     return false;
 135
 136   for (i = element->Pad; i != NULL; i = g_list_next (i))
 137     {
 138       PadType *pad = i->data;
 139
 140       if (NSTRCMP (PinNum, pad->Number) == 0 &&
 141           (!Same || !TEST_FLAG (DRCFLAG, pad)))
 142         {
 143           conn->type = PAD_TYPE;
 144           conn->ptr1 = element;
 145           conn->ptr2 = pad;
 146           conn->group = TEST_FLAG (ONSOLDERFLAG, pad) ? bottom_group : top_group;
 147
 148           if (TEST_FLAG (EDGE2FLAG, pad))
 149             {
 150               conn->X = pad->Point2.X;
 151               conn->Y = pad->Point2.Y;
 152             }
 153           else
 154             {
 155               conn->X = pad->Point1.X;
 156               conn->Y = pad->Point1.Y;
 157             }
 158           return true;
 159         }
 160     }
 161
 162   for (i = element->Pin; i != NULL; i = g_list_next (i))
 163     {
 164       PinType *pin = i->data;
 165
 166       if (!TEST_FLAG (HOLEFLAG, pin) &&
 167           pin->Number && NSTRCMP (PinNum, pin->Number) == 0 &&
 168           (!Same || !TEST_FLAG (DRCFLAG, pin)))
 169         {
 170           conn->type = PIN_TYPE;
 171           conn->ptr1 = element;
 172           conn->ptr2 = pin;
 173           conn->group = bottom_group;        /* any layer will do */
 174           conn->X = pin->X;
 175           conn->Y = pin->Y;
 176           return true;
 177         }
 178     }
 179
 180   return false;
 181 }
 182
 183 /*!
 184  * \brief Parse a netlist menu entry and locate the corresponding pad.
 185  *
 186  * \return true if found, and fills in Connection information.
 187  */
 188 bool
 189 SeekPad (LibraryEntryType * entry, ConnectionType * conn, bool Same)
 190 {
 191   int j;
 192   char ElementName[256];
 193   char PinNum[256];
 194
 195   if (ParseConnection (entry->ListEntry, ElementName, PinNum))
 196     return (false);
 197   for (j = 0; PinNum[j] != '\0'; j++);
 198   if (j == 0)
 199     {
 200       Message (_("Error! Netlist file is missing pin!\n"
 201                  "white space after \"%s-\"\n"), ElementName);
 202       badnet = true;
 203     }
 204   else
 205     {
 206       if (FindPad (ElementName, PinNum, conn, Same))
 207         return (true);
 208       if (Same)
 209         return (false);
 210       if (PinNum[j - 1] < '0' || PinNum[j - 1] > '9')
 211         {
 212           Message ("WARNING! Pin number ending with '%c'"
 213                    " encountered in netlist file\n"
 214                    "Probably a bad netlist file format\n", PinNum[j - 1]);
 215         }
 216     }
 217   Message (_("Can't find %s pin %s called for in netlist.\n"),
 218            ElementName, PinNum);
 219   return (false);
 220 }
 221
 222 /*!
 223  * \brief Read the library-netlist build a true Netlist structure.
 224  */
 225 NetListType *
 226 ProcNetlist (LibraryType *net_menu)
 227 {
 228   ConnectionType *connection;
 229   ConnectionType LastPoint;
 230   NetType *net;
 231   static NetListType *Wantlist = NULL;
 232
 233   if (!net_menu->MenuN)
 234     return (NULL);
 235   FreeNetListMemory (Wantlist);
 236   free (Wantlist);
 237   badnet = false;
 238
 239   /* find layer groups of the component side and solder side */
 240   bottom_group = GetLayerGroupNumberBySide (BOTTOM_SIDE);
 241   top_group = GetLayerGroupNumberBySide (TOP_SIDE);
 242
 243   Wantlist = (NetListType *)calloc (1, sizeof (NetListType));
 244   if (Wantlist)
 245     {
 246       ALLPIN_LOOP (PCB->Data);
 247       {
 248         pin->Spare = NULL;
 249         CLEAR_FLAG (DRCFLAG, pin);
 250       }
 251       ENDALL_LOOP;
 252       ALLPAD_LOOP (PCB->Data);
 253       {
 254         pad->Spare = NULL;
 255         CLEAR_FLAG (DRCFLAG, pad);
 256       }
 257       ENDALL_LOOP;
 258       MENU_LOOP (net_menu);
 259       {
 260         if (menu->Name[0] == '*' || menu->flag == 0)
 261           {
 262             badnet = true;
 263             continue;
 264           }
 265         net = GetNetMemory (Wantlist);
 266         if (menu->Style)
 267           {
 268             STYLE_LOOP (PCB);
 269             {
 270               if (style->Name && !NSTRCMP (style->Name, menu->Style))
 271                 {
 272                   net->Style = style;
 273                   break;
 274                 }
 275             }
 276             END_LOOP;
 277           }
 278         else                    /* default to NULL if none found */
 279           net->Style = NULL;
 280         ENTRY_LOOP (menu);
 281         {
 282           if (SeekPad (entry, &LastPoint, false))
 283             {
 284               if (TEST_FLAG (DRCFLAG, (PinType *) LastPoint.ptr2))
 285                 Message (_
 286                          ("Error! Element %s pin %s appears multiple times in the netlist file.\n"),
 287                          NAMEONPCB_NAME ((ElementType *) LastPoint.ptr1),
 288                          (LastPoint.type ==
 289                           PIN_TYPE) ? ((PinType *) LastPoint.ptr2)->
 290                          Number : ((PadType *) LastPoint.ptr2)->Number);
 291               else
 292                 {
 293                   connection = GetConnectionMemory (net);
 294                   *connection = LastPoint;
 295                   /* indicate expect net */
 296                   connection->menu = menu;
 297                   /* mark as visited */
 298                   SET_FLAG (DRCFLAG, (PinType *) LastPoint.ptr2);
 299                   if (LastPoint.type == PIN_TYPE)
 300                     ((PinType *) LastPoint.ptr2)->Spare = (void *) menu;
 301                   else
 302                     ((PadType *) LastPoint.ptr2)->Spare = (void *) menu;
 303                 }
 304             }
 305           else
 306             badnet = true;
 307           /* check for more pins with the same number */
 308           for (; SeekPad (entry, &LastPoint, true);)
 309             {
 310               connection = GetConnectionMemory (net);
 311               *connection = LastPoint;
 312               /* indicate expect net */
 313               connection->menu = menu;
 314               /* mark as visited */
 315               SET_FLAG (DRCFLAG, (PinType *) LastPoint.ptr2);
 316               if (LastPoint.type == PIN_TYPE)
 317                 ((PinType *) LastPoint.ptr2)->Spare = (void *) menu;
 318               else
 319                 ((PadType *) LastPoint.ptr2)->Spare = (void *) menu;
 320             }
 321         }
 322         END_LOOP;
 323       }
 324       END_LOOP;
 325     }
 326   /* clear all visit marks */
 327   ALLPIN_LOOP (PCB->Data);
 328   {
 329     CLEAR_FLAG (DRCFLAG, pin);
 330   }
 331   ENDALL_LOOP;
 332   ALLPAD_LOOP (PCB->Data);
 333   {
 334     CLEAR_FLAG (DRCFLAG, pad);
 335   }
 336   ENDALL_LOOP;
 337   return (Wantlist);
 338 }
 339
 340 /*!
 341  * \brief Copy all connections from one net into another and then remove
 342  * the first net from its netlist.
 343  */
 344 static void
 345 TransferNet (NetListType *Netl, NetType *SourceNet, NetType *DestNet)
 346 {
 347   ConnectionType *conn;
 348
 349   /* It would be worth checking if SourceNet is NULL here to avoid a segfault. Seb James. */
 350   CONNECTION_LOOP (SourceNet);
 351   {
 352     conn = GetConnectionMemory (DestNet);
 353     *conn = *connection;
 354   }
 355   END_LOOP;
 356   DestNet->Style = SourceNet->Style;
 357   /* free the connection memory */
 358   FreeNetMemory (SourceNet);
 359   /* remove SourceNet from its netlist */
 360   *SourceNet = Netl->Net[--(Netl->NetN)];
 361   /* zero out old garbage */
 362   memset (&Netl->Net[Netl->NetN], 0, sizeof (NetType));
 363 }
 364
 365 static bool
 366 CheckShorts (LibraryMenuType *theNet)
 367 {
 368   bool newone, warn = false;
 369   PointerListType *generic = (PointerListType *)calloc (1, sizeof (PointerListType));
 370   /* the first connection was starting point so
 371    * the menu is always non-null
 372    */
 373   void **menu = GetPointerMemory (generic);
 374
 375   *menu = theNet;
 376   ALLPIN_LOOP (PCB->Data);
 377   {
 378     if (TEST_FLAG (DRCFLAG, pin))
 379       {
 380         warn = true;
 381         if (!pin->Spare)
 382           {
 383             Message (_("Warning! Net \"%s\" is shorted to %s pin %s\n"),
 384                      &theNet->Name[2],
 385                      UNKNOWN (NAMEONPCB_NAME (element)),
 386                      UNKNOWN (pin->Number));
 387             SET_FLAG (WARNFLAG, pin);
 388             continue;
 389           }
 390         newone = true;
 391         POINTER_LOOP (generic);
 392         {
 393           if (*ptr == pin->Spare)
 394             {
 395               newone = false;
 396               break;
 397             }
 398         }
 399         END_LOOP;
 400         if (newone)
 401           {
 402             menu = GetPointerMemory (generic);
 403             *menu = pin->Spare;
 404             Message (_("Warning! Net \"%s\" is shorted to net \"%s\"\n"),
 405                      &theNet->Name[2],
 406                      &((LibraryMenuType *) (pin->Spare))->Name[2]);
 407             SET_FLAG (WARNFLAG, pin);
 408           }
 409       }
 410   }
 411   ENDALL_LOOP;
 412   ALLPAD_LOOP (PCB->Data);
 413   {
 414     if (TEST_FLAG (DRCFLAG, pad))
 415       {
 416         warn = true;
 417         if (!pad->Spare)
 418           {
 419             Message (_("Warning! Net \"%s\" is shorted  to %s pad %s\n"),
 420                      &theNet->Name[2],
 421                      UNKNOWN (NAMEONPCB_NAME (element)),
 422                      UNKNOWN (pad->Number));
 423             SET_FLAG (WARNFLAG, pad);
 424             continue;
 425           }
 426         newone = true;
 427         POINTER_LOOP (generic);
 428         {
 429           if (*ptr == pad->Spare)
 430             {
 431               newone = false;
 432               break;
 433             }
 434         }
 435         END_LOOP;
 436         if (newone)
 437           {
 438             menu = GetPointerMemory (generic);
 439             *menu = pad->Spare;
 440             Message (_("Warning! Net \"%s\" is shorted to net \"%s\"\n"),
 441                      &theNet->Name[2],
 442                      &((LibraryMenuType *) (pad->Spare))->Name[2]);
 443             SET_FLAG (WARNFLAG, pad);
 444           }
 445       }
 446   }
 447   ENDALL_LOOP;
 448   FreePointerListMemory (generic);
 449   free (generic);
 450   return (warn);
 451 }
 452
 453
 454 /*!
 455  * \brief Determine existing interconnections of the net and gather into
 456  * sub-nets.
 457  *
 458  * Initially the netlist has each connection in its own individual net
 459  * afterwards there can be many fewer nets with multiple connections
 460  * each.
 461  */
 462 static bool
 463 GatherSubnets (NetListType *Netl, bool NoWarn, bool AndRats)
 464 {
 465   NetType *a, *b;
 466   ConnectionType *conn;
 467   Cardinal m, n;
 468   bool Warned = false;
 469
 470   for (m = 0; Netl->NetN > 0 && m < Netl->NetN; m++)
 471     {
 472       a = &Netl->Net[m];
 473       ClearFlagOnAllObjects (false, DRCFLAG, false);
 474       RatFindHook (a->Connection[0].type, a->Connection[0].ptr1,
 475                    a->Connection[0].ptr2, a->Connection[0].ptr2,
 476                    false, DRCFLAG, AndRats);
 477       /* now anybody connected to the first point has DRCFLAG set */
 478       /* so move those to this subnet */
 479       CLEAR_FLAG (DRCFLAG, (PinType *) a->Connection[0].ptr2);
 480       for (n = m + 1; n < Netl->NetN; n++)
 481         {
 482           b = &Netl->Net[n];
 483           /* There can be only one connection in net b */
 484           if (TEST_FLAG (DRCFLAG, (PinType *) b->Connection[0].ptr2))
 485             {
 486               CLEAR_FLAG (DRCFLAG, (PinType *) b->Connection[0].ptr2);
 487               TransferNet (Netl, b, a);
 488               /* back up since new subnet is now at old index */
 489               n--;
 490             }
 491         }
 492       /* now add other possible attachment points to the subnet */
 493       /* e.g. line end-points and vias */
 494       /* don't add non-manhattan lines, the auto-router can't route to them */
 495       ALLLINE_LOOP (PCB->Data);
 496       {
 497         if (TEST_FLAG (DRCFLAG, line))
 498           {
 499             conn = GetConnectionMemory (a);
 500             conn->X = line->Point1.X;
 501             conn->Y = line->Point1.Y;
 502             conn->type = LINE_TYPE;
 503             conn->ptr1 = layer;
 504             conn->ptr2 = line;
 505             conn->group = GetLayerGroupNumberByPointer (layer);
 506             conn->menu = NULL;  /* agnostic view of where it belongs */
 507             conn = GetConnectionMemory (a);
 508             conn->X = line->Point2.X;
 509             conn->Y = line->Point2.Y;
 510             conn->type = LINE_TYPE;
 511             conn->ptr1 = layer;
 512             conn->ptr2 = line;
 513             conn->group = GetLayerGroupNumberByPointer (layer);
 514             conn->menu = NULL;
 515           }
 516       }
 517       ENDALL_LOOP;
 518       /* add polygons so the auto-router can see them as targets */
 519       ALLPOLYGON_LOOP (PCB->Data);
 520       {
 521         if (TEST_FLAG (DRCFLAG, polygon))
 522           {
 523             conn = GetConnectionMemory (a);
 524             /* make point on a vertex */
 525             conn->X = polygon->Clipped->contours->head.point[0];
 526             conn->Y = polygon->Clipped->contours->head.point[1];
 527             conn->type = POLYGON_TYPE;
 528             conn->ptr1 = layer;
 529             conn->ptr2 = polygon;
 530             conn->group = GetLayerGroupNumberByPointer (layer);
 531             conn->menu = NULL;  /* agnostic view of where it belongs */
 532           }
 533       }
 534       ENDALL_LOOP;
 535       VIA_LOOP (PCB->Data);
 536       {
 537         if (TEST_FLAG (DRCFLAG, via))
 538           {
 539             conn = GetConnectionMemory (a);
 540             conn->X = via->X;
 541             conn->Y = via->Y;
 542             conn->type = VIA_TYPE;
 543             conn->ptr1 = via;
 544             conn->ptr2 = via;
 545             conn->group = bottom_group;
 546           }
 547       }
 548       END_LOOP;
 549       if (!NoWarn)
 550         Warned |= CheckShorts (a->Connection[0].menu);
 551     }
 552   ClearFlagOnAllObjects (false, DRCFLAG, false);
 553   return (Warned);
 554 }
 555
 556 /*!
 557  * \brief Draw a rat net (tree) having the shortest lines.
 558  *
 559  * This also frees the subnet memory as they are consumed.
 560  *
 561  * \note The \c Netl we are passed is NOT the main netlist - it's the
 562  * connectivity for ONE net.
 563  * It represents the CURRENT connectivity state for the net, with each
 564  * Netl->Net[N] representing one copper-connected subset of the net.
 565  *
 566  * Everything inside the NetList Netl should be connected together.
 567  *
 568  * Each Net in \c Netl is a group of Connections which are already
 569  * connected together somehow, either by real wires or by rats we've
 570  * already drawn.
 571  *
 572  * Each Connection is a vertex within that blob of connected items.
 573  *
 574  * This loop finds the closest vertex pairs between each blob and draws
 575  * rats that merge the blobs until there's just one big blob.
 576  *
 577  * Just to clarify, with some examples:
 578  *
 579  * Each \c Netl is one full net from a netlist, like from gnetlist.
 580  *
 581  * Each Netl->Net[N] is a subset of that net that's already
 582  * physically connected on the pcb.
 583  *
 584  * So a new design with no traces yet, would have a huge list of Net[N],
 585  * each with one pin in it.
 586  *
 587  * A fully routed design would have one Net[N] with all the pins
 588  * (for that net) in it.
 589  */
 590 static bool
 591 DrawShortestRats (NetListType *Netl, void (*funcp) (register ConnectionType *, register ConnectionType *, register RouteStyleType *))
 592 {
 593   RatType *line;
 594   register float distance, temp;
 595   register ConnectionType *conn1, *conn2, *firstpoint, *secondpoint;
 596   PolygonType *polygon;
 597   bool changed = false;
 598   bool havepoints;
 599   Cardinal n, m, j;
 600   NetType *next, *subnet, *theSubnet = NULL;
 601
 602   /* This is just a sanity check, to make sure we're passed
 603    * *something*.
 604    */
 605   if (!Netl || Netl->NetN < 1)
 606     return false;
 607
 608   /*
 609    * We keep doing this do/while loop until everything's connected.
 610    * I.e. once per rat we add.
 611    */
 612   distance = 0.0;
 613   havepoints = true; /* so we run the loop at least once */
 614   while (Netl->NetN > 1 && havepoints)
 615     {
 616       /* This is the top of the "find one rat" logic.  */
 617       havepoints = false;
 618       firstpoint = secondpoint = NULL;
 619
 620       /* Test Net[0] vs Net[N] for N=1..max.  Find the shortest
 621          distance between any two points in different blobs.  */
 622       subnet = &Netl->Net[0];
 623       for (j = 1; j < Netl->NetN; j++)
 624         {
 625           /*
 626            * Scan between Net[0] blob (subnet) and Net[N] blob (next).
 627            * Note the shortest distance we find.
 628            */
 629           next = &Netl->Net[j];
 630           for (n = subnet->ConnectionN - 1; n != -1; n--)
 631             {
 632               conn1 = &subnet->Connection[n];
 633               for (m = next->ConnectionN - 1; m != -1; m--)
 634                 {
 635                   conn2 = &next->Connection[m];
 636                   /*
 637                    * At this point, conn1 and conn2 are two pins in
 638                    * different blobs of the same net.  See how far
 639                    * apart they are, and if they're "closer" than what
 640                    * we already have.
 641                    */
 642
 643                   /*
 644                    * Prefer to connect Connections over polygons to the
 645                    * polygons (ie assume the user wants a via to a plane,
 646                    * not a daisy chain).  Further prefer to pick an existing
 647                    * via in the Net to make that connection.
 648                    */
 649                   if (conn1->type == POLYGON_TYPE &&
 650                       (polygon = (PolygonType *)conn1->ptr2) &&
 651                       !(distance == 0 &&
 652                         firstpoint && firstpoint->type == VIA_TYPE) &&
 653                       IsPointInPolygonIgnoreHoles (conn2->X, conn2->Y, polygon))
 654                     {
 655                       distance = 0;
 656                       firstpoint = conn2;
 657                       secondpoint = conn1;
 658                       theSubnet = next;
 659                       havepoints = true;
 660                     }
 661                   else if (conn2->type == POLYGON_TYPE &&
 662                       (polygon = (PolygonType *)conn2->ptr2) &&
 663                       !(distance == 0 &&
 664                         firstpoint && firstpoint->type == VIA_TYPE) &&
 665                       IsPointInPolygonIgnoreHoles (conn1->X, conn1->Y, polygon))
 666                     {
 667                       distance = 0;
 668                       firstpoint = conn1;
 669                       secondpoint = conn2;
 670                       theSubnet = next;
 671                       havepoints = true;
 672                     }
 673                   else if ((temp = SQUARE (conn1->X - conn2->X) +
 674                        SQUARE (conn1->Y - conn2->Y)) < distance || !firstpoint)
 675                     {
 676                       distance = temp;
 677                       firstpoint = conn1;
 678                       secondpoint = conn2;
 679                       theSubnet = next;
 680                       havepoints = true;
 681                     }
 682                 }
 683             }
 684         }
 685
 686       /*
 687        * If HAVEPOINTS is true, we've found a pair of points in two
 688        * separate blobs of the net, and need to connect them together.
 689        */
 690       if (havepoints)
 691         {
 692           if (funcp)
 693             {
 694               (*funcp) (firstpoint, secondpoint, subnet->Style);
 695             }
 696           else
 697             {
 698               /* found the shortest distance subnet, draw the rat */
 699               if ((line = CreateNewRat (PCB->Data,
 700                                         firstpoint->X, firstpoint->Y,
 701                                         secondpoint->X, secondpoint->Y,
 702                                         firstpoint->group, secondpoint->group,
 703                                         Settings.RatThickness,
 704                                         NoFlags ())) != NULL)
 705                 {
 706                   if (distance == 0)
 707                     SET_FLAG (VIAFLAG, line);
 708                   AddObjectToCreateUndoList (RATLINE_TYPE, line, line, line);
 709                   DrawRat (line);
 710                   changed = true;
 711                 }
 712             }
 713
 714           /* copy theSubnet into the current subnet */
 715           TransferNet (Netl, theSubnet, subnet);
 716         }
 717     }
 718
 719   /* presently nothing to do with the new subnet */
 720   /* so we throw it away and free the space */
 721   FreeNetMemory (&Netl->Net[--(Netl->NetN)]);
 722   /* Sadly adding a rat line messes up the sorted arrays in connection finder */
 723   /* hace: perhaps not necessarily now that they aren't stored in normal layers */
 724   if (changed)
 725     {
 726       FreeConnectionLookupMemory ();
 727       InitConnectionLookup ();
 728     }
 729   return (changed);
 730 }
 731
 732
 733 /*!
 734  * \brief AddAllRats puts the rats nest into the layout from the loaded
 735  * netlist.
 736  *
 737  * If SelectedOnly is true, it will only draw rats to selected pins and
 738  * pads.
 739  */
 740 bool
 741 AddAllRats (bool SelectedOnly, void (*funcp) (register ConnectionType *, register ConnectionType *, register RouteStyleType *))
 742 {
 743   NetListType *Nets, *Wantlist;
 744   NetType *lonesome;
 745   ConnectionType *onepin;
 746   bool changed, Warned = false;
 747
 748   /* the netlist library has the text form
 749    * ProcNetlist fills in the Netlist
 750    * structure the way the final routing
 751    * is supposed to look
 752    */
 753   Wantlist = ProcNetlist (&PCB->NetlistLib);
 754   if (!Wantlist)
 755     {
 756       Message (_("Can't add rat lines because no netlist is loaded.\n"));
 757       return (false);
 758     }
 759   changed = false;
 760   /* initialize finding engine */
 761   InitConnectionLookup ();
 762   Nets = (NetListType *)calloc (1, sizeof (NetListType));
 763   /* now we build another netlist (Nets) for each
 764    * net in Wantlist that shows how it actually looks now,
 765    * then fill in any missing connections with rat lines.
 766    *
 767    * we first assume each connection is separate
 768    * (no routing), then gather them into groups
 769    * if the net is all routed, the new netlist (Nets)
 770    * will have only one net entry.
 771    * Note that DrawShortestRats consumes all nets
 772    * from Nets, so *Nets is empty after the
 773    * DrawShortestRats call
 774    */
 775   NET_LOOP (Wantlist);
 776   {
 777     CONNECTION_LOOP (net);
 778     {
 779       if (!SelectedOnly
 780           || TEST_FLAG (SELECTEDFLAG, (PinType *) connection->ptr2))
 781         {
 782           lonesome = GetNetMemory (Nets);
 783           onepin = GetConnectionMemory (lonesome);
 784           *onepin = *connection;
 785           lonesome->Style = net->Style;
 786         }
 787     }
 788     END_LOOP;
 789     Warned |= GatherSubnets (Nets, SelectedOnly, true);
 790     if (Nets->NetN > 0)
 791       changed |= DrawShortestRats (Nets, funcp);
 792   }
 793   END_LOOP;
 794   FreeNetListMemory (Nets);
 795   free (Nets);
 796   FreeConnectionLookupMemory ();
 797   if (funcp)
 798     return (true);
 799
 800   if (Warned || changed)
 801     Draw ();
 802
 803   if (Warned)
 804     Settings.RatWarn = true;
 805
 806   if (changed)
 807     {
 808       IncrementUndoSerialNumber ();
 809       if (PCB->Data->RatN > 0)
 810         {
 811           Message ("%d rat line%s remaining\n", PCB->Data->RatN,
 812                    PCB->Data->RatN > 1 ? "s" : "");
 813         }
 814       return (true);
 815     }
 816   if (!SelectedOnly && !Warned)
 817     {
 818       if (!PCB->Data->RatN && !badnet)
 819         Message (_("Congratulations!!\n"
 820                    "The layout is complete and has no shorted nets.\n"));
 821       else
 822         Message (_("Nothing more to add, but there are\n"
 823                    "either rat-lines in the layout, disabled nets\n"
 824                    "in the net-list, or missing components\n"));
 825     }
 826   return (false);
 827 }
 828
 829 /*!
 830  * \todo This is copied in large part from AddAllRats above; for
 831  * maintainability, AddAllRats probably wants to be tweaked to use this
 832  * version of the code so that we don't have duplication.
 833  */
 834 NetListListType
 835 CollectSubnets (bool SelectedOnly)
 836 {
 837   NetListListType result = { 0, 0, NULL };
 838   NetListType *Nets, *Wantlist;
 839   NetType *lonesome;
 840   ConnectionType *onepin;
 841
 842   /* the netlist library has the text form
 843    * ProcNetlist fills in the Netlist
 844    * structure the way the final routing
 845    * is supposed to look
 846    */
 847   Wantlist = ProcNetlist (&PCB->NetlistLib);
 848   if (!Wantlist)
 849     {
 850       Message (_("Can't add rat lines because no netlist is loaded.\n"));
 851       return result;
 852     }
 853   /* initialize finding engine */
 854   InitConnectionLookup ();
 855   /* now we build another netlist (Nets) for each
 856    * net in Wantlist that shows how it actually looks now,
 857    * then fill in any missing connections with rat lines.
 858    *
 859    * we first assume each connection is separate
 860    * (no routing), then gather them into groups
 861    * if the net is all routed, the new netlist (Nets)
 862    * will have only one net entry.
 863    * Note that DrawShortestRats consumes all nets
 864    * from Nets, so *Nets is empty after the
 865    * DrawShortestRats call
 866    */
 867   NET_LOOP (Wantlist);
 868   {
 869     Nets = GetNetListMemory (&result);
 870     CONNECTION_LOOP (net);
 871     {
 872       if (!SelectedOnly
 873           || TEST_FLAG (SELECTEDFLAG, (PinType *) connection->ptr2))
 874         {
 875           lonesome = GetNetMemory (Nets);
 876           onepin = GetConnectionMemory (lonesome);
 877           *onepin = *connection;
 878           lonesome->Style = net->Style;
 879         }
 880     }
 881     END_LOOP;
 882     /* Note that AndRats is *FALSE* here! */
 883     GatherSubnets (Nets, SelectedOnly, false);
 884   }
 885   END_LOOP;
 886   FreeConnectionLookupMemory ();
 887   return result;
 888 }
 889
 890 /*!
 891  * \brief Check to see if a particular name is the name of an already
 892  * existing rats line.
 893  */
 894 static int
 895 rat_used (char *name)
 896 {
 897   if (name == NULL)
 898     return -1;
 899
 900   MENU_LOOP (&PCB->NetlistLib);
 901   {
 902     if (menu->Name && (strcmp (menu->Name, name) == 0))
 903       return 1;
 904   }
 905   END_LOOP;
 906
 907   return 0;
 908 }
 909
 910 /*!
 911  * \brief This function is moved from the original netlist.c as
 912  * part of the gui code separation for the Gtk port.
 913  */
 914 RatType *
 915 AddNet (void)
 916 {
 917   static int ratDrawn = 0;
 918   char name1[256], *name2;
 919   Cardinal group1, group2;
 920   char ratname[20];
 921   int found;
 922   void *ptr1, *ptr2, *ptr3;
 923   LibraryMenuType *menu;
 924   LibraryEntryType *entry;
 925
 926   if (Crosshair.AttachedLine.Point1.X == Crosshair.AttachedLine.Point2.X
 927       && Crosshair.AttachedLine.Point1.Y == Crosshair.AttachedLine.Point2.Y)
 928     return (NULL);
 929
 930   found = SearchObjectByLocation (PAD_TYPE | PIN_TYPE, &ptr1, &ptr2, &ptr3,
 931                                   Crosshair.AttachedLine.Point1.X,
 932                                   Crosshair.AttachedLine.Point1.Y, 5);
 933   if (found == NO_TYPE)
 934     {
 935       Message (_("No pad/pin under rat line\n"));
 936       return (NULL);
 937     }
 938   if (NAMEONPCB_NAME ((ElementType *) ptr1) == NULL
 939       || *NAMEONPCB_NAME ((ElementType *) ptr1) == 0)
 940     {
 941       Message (_("You must name the starting element first\n"));
 942       return (NULL);
 943     }
 944
 945   /* will work for pins to since the FLAG is common */
 946   group1 = GetLayerGroupNumberBySide (
 947             TEST_FLAG (ONSOLDERFLAG, (PadType *) ptr2) ? BOTTOM_SIDE : TOP_SIDE);
 948   strcpy (name1, ConnectionName (found, ptr1, ptr2));
 949   found = SearchObjectByLocation (PAD_TYPE | PIN_TYPE, &ptr1, &ptr2, &ptr3,
 950                                   Crosshair.AttachedLine.Point2.X,
 951                                   Crosshair.AttachedLine.Point2.Y, 5);
 952   if (found == NO_TYPE)
 953     {
 954       Message (_("No pad/pin under rat line\n"));
 955       return (NULL);
 956     }
 957   if (NAMEONPCB_NAME ((ElementType *) ptr1) == NULL
 958       || *NAMEONPCB_NAME ((ElementType *) ptr1) == 0)
 959     {
 960       Message (_("You must name the ending element first\n"));
 961       return (NULL);
 962     }
 963   group2 = GetLayerGroupNumberBySide (
 964             TEST_FLAG (ONSOLDERFLAG, (PadType *) ptr2) ? BOTTOM_SIDE : TOP_SIDE);
 965   name2 = ConnectionName (found, ptr1, ptr2);
 966
 967   menu = netnode_to_netname (name1);
 968   if (menu)
 969     {
 970       if (netnode_to_netname (name2))
 971         {
 972           Message (_
 973                    ("Both connections already in netlist - cannot merge nets\n"));
 974           return (NULL);
 975         }
 976       entry = GetLibraryEntryMemory (menu);
 977       entry->ListEntry = strdup (name2);
 978       netnode_to_netname (name2);
 979       goto ratIt;
 980     }
 981   /* ok, the first name did not belong to a net */
 982   menu = netnode_to_netname (name2);
 983   if (menu)
 984     {
 985       entry = GetLibraryEntryMemory (menu);
 986       entry->ListEntry = strdup (name1);
 987       netnode_to_netname (name1);
 988       goto ratIt;
 989     }
 990
 991   /*
 992    * neither belong to a net, so create a new one.
 993    *
 994    * before creating a new rats here, we need to search
 995    * for a unique name.
 996    */
 997   sprintf (ratname, "  ratDrawn%i", ++ratDrawn);
 998   while (rat_used (ratname))
 999     {
1000       sprintf (ratname, "  ratDrawn%i", ++ratDrawn);
1001     }
1002
1003   menu = GetLibraryMenuMemory (&PCB->NetlistLib);
1004   menu->Name = strdup (ratname);
1005   entry = GetLibraryEntryMemory (menu);
1006   entry->ListEntry = strdup (name1);
1007   entry = GetLibraryEntryMemory (menu);
1008   entry->ListEntry = strdup (name2);
1009   menu->flag = 1;
1010
1011 ratIt:
1012   NetlistChanged (0);
1013   return (CreateNewRat (PCB->Data, Crosshair.AttachedLine.Point1.X,
1014                         Crosshair.AttachedLine.Point1.Y,
1015                         Crosshair.AttachedLine.Point2.X,
1016                         Crosshair.AttachedLine.Point2.Y,
1017                         group1, group2, Settings.RatThickness, NoFlags ()));
1018 }
1019
1020 /*!
1021  * \brief This function is moved from the original netlist.c as
1022  * part of the gui code separation for the Gtk port.
1023  */
1024 char *
1025 ConnectionName (int type, void *ptr1, void *ptr2)
1026 {
1027   static char name[256];
1028   char *num;
1029
1030   switch (type)
1031     {
1032     case PIN_TYPE:
1033       num = ((PinType *) ptr2)->Number;
1034       break;
1035     case PAD_TYPE:
1036       num = ((PadType *) ptr2)->Number;
1037       break;
1038     default:
1039       return (NULL);
1040     }
1041   strcpy (name, UNKNOWN (NAMEONPCB_NAME ((ElementType *) ptr1)));
1042   strcat (name, "-");
1043   strcat (name, UNKNOWN (num));
1044   return (name);
1045 }