gEDA Project Wiki

The connection lookup algorithm starts at an object and looks for any objects that touch the starting object or any object touching the starting object. This code is implemented in find.c and used throughout the code base for a variety of purposes.

The connection lookup process starts at an object (pins/pads only?) and searches for intersecting objects. For each object it finds, it sets a specified flag. (todo: eventually this should build a list of objects instead). These flags are used in a convoluted way to identify things that have already been found, and if the algorithm should continue looking for more objects.

One of the tricks that the algorithm uses to restore the state of the flags in some cases is to use ClearFlagOnAllObjects to wipe out a flag (an undoable operation), then do everything without adding operations to the Undo stack, run ClearFlagsOnAllObjects a second time (without undo), and then Undo the first one. I guess the point of this is to prevent the undo system from sucking up resources during these operations? This has led to a global variable “User” which has the effect of causing flag change operations to be added to the undo list. I think this is absolutely horrid. This variable needs to die. I think a better way of accomplishing this goal is by locking the undo system.

In a number of places, the “andRats” parameter is used. This indicates that rat lines should be considered when looking for overlaps. This way, you can highlight an entire net, even if all the pieces aren't connected with copper. It's important to preserve this functionality.

1. InitConnectionLookup()

A. InitComponentLookup()
  a. Compute the number of pads on each side of the pcb
  b. Allocate enough memory for the PadLists to hold pointers to all of them, and initialize the list structures.
B. InitLayoutLookup()
  a. For each copper layer, allocate enough memory for each list (lines, arcs, polygons) to hold pointers to all of the objects on the layer, and initialize the list structures.
  b. Allocate enough memory for the pin and via combined list, and initialize it.
  c. Allocate enough memory for the rats list to hold all of the rats.

2. ListStart(type, ptr1, ptr2, ptr3)

A. Add the seed object to the lists.

3. DoIt(flag, bloat, AndRats, AndDraw, is_drc)

A. Set the global drc flag and bloat value
B. Update layer "no_drc" flags
C. Lookup connection loop:
  a. LookupPVConnectionsToPVList(flag)
    i. Save our current position in the PV list
    ii. If our current position is not the last item in the list:
      1. Get the current list item
      2. Expand the bounding box by the global bloat for the search
      3. to be continued...
    iii. Restore the list position

The DRC uses the connection lookup code in combination with the “Bloat” and “Shrink” settings to detect places with insufficient spacing and overlap.

action.c

action.c

action.c

action.c

action.c

netlist window

Saves list of unused pins and pads: ActionSaveTo:action.c:5752 LookupUnusedPins:find.c:2464 PrintAndSelectUnusedPinsAndPadsOfElement:find.c:1982 DoIt:find.c:2000, 2044

Saves list of element connections ActionSaveTo:action.c:5752 LookupElementConnections:find.c:2255 PrintElementConnections:find.c:2120 DoIt:find.c:2136, 2161

There are quite a few of these. (action.c: 905, 906, 1366, 2314, 2315, 2789, 2792) LookupConnection:find.c:2376 (netlist.c: 171, 180) LookupConnection:find.c:2376 (report.c: 598) LookupConnection:find.c:2376 DoIt:find.c:2417

(ipcd356.c: 493, 514, 538) LookupConnectionByPin:find.c:2431 DoIt:find.c:2439

(gsvit.c:433) RatFindHook:find.c:2450 (lesstif/netlist.c:140) RatFindHook:find.c:2450 (gtk/gui-netlist-window.c:543) RatFindHook:find.c:2450 (rats.c:474) RatFindHook:find.c:2450 (select.c:996) RatFindHook:find.c:2450 DoIt:find.c:2456

start_do_it_and_dump:find.c:2681 DoIt:find.c:2689