gEDA Project Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
=====Connection Lookup=====

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.

Objects are broken into two categories, "layer objects" (LO) and pins and vias (PV). The tests then get split into four categories, PV to PV, LO to PV, LO to LO, and PV to LO.

=====Detailed Algorithm=====

  - Initialize the lists
  - Add seed object
  - Initialize global variables
  - Search lists for new connections
    - Check the PV list for new PV connections (LookupPVConnectionsToPVList)
      - rsearch the pin tree calling pv_pv_callback
      - rsearch the via tree calling pv_pv_callback
        - check that the pvs are on intersecting layers
        - check that it's not already in the list
        - check that they touch
        - check that neither is just a hole
        - add the new pv to the list
    - Check the PV list for new LO connections
      - rsearch the pad tree calling LOCtoPVpad_callback
      - For each copper layer
        - rsearch the line tree calling LOCtoPVline_callback
        - rsearch the arc tree calling LOCtoPVarc_callback
        - rsearch the polygon tree calling LOCtoPVpoly_callback


  - InitConnectionLookup()
    - InitComponentLookup()
      - Compute the number of pads on each side of the pcb
      - Allocate enough memory for the PadLists to hold pointers to all of them, and initialize the list structures.
    - InitLayoutLookup()
      - 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.
      - Allocate enough memory for the pin and via combined list, and initialize it.
      - Allocate enough memory for the rats list to hold all of the rats.
  - ListStart(type, ptr1, ptr2, ptr3)
    - Add the seed object to the lists.
  - DoIt(flag, bloat, AndRats, AndDraw, is_drc)
    - Set the global drc flag and bloat value
    - Update layer "no_drc" flags
    - Lookup connection loop:
      - Note that if any of the four lookup functions returns true, it will likely short-circuit the rest of the tests.
      - LookupPVConnectionsToPVList(flag)
        - Save our current position in the PV list
        - If our current position is not the last item in the list:
          - Get the current list item
          - Expand the bounding box by the global bloat for the search
          - Set a jump point, and do an r_search on the via tree around the current PV (pv_pv_callback)
            - If the vias are buried and the layers don't intersect, return and continue the search.
            - If the new PV hasn't been marked yet, and the new one overlaps with the current one,
              - If it's just a hole (no copper annulus), throw a warning and continue the search
              - Otherwise, add the new PV to the list (add_object_to_list)
                - If this is a DRC and the selected flag wasn't set, long jump back to LookupPVConnectionsToPVList
                - Otherwise, continue the search
          - If we returned via a long jump, return true (found something/want to stop lookup up objects)
          - Otherwise check the pin tree (repeat via tree steps)
          - If we returned via a long jump, return true (found something/want to stop lookup up objects)
          - Otherwise, keep looking through the PV list until we get to the end.
        - Restore the list position (why? Probably so that LookupLOConnectionsToPVList can iterate over the same group of objects)
        - Return false (no new objects/we want to keep looking up objects)
      - LookupLOConnectionsToPVList(flag, AndRats)
        - If our current position is not the last item in the list:
          - Get the current list item
          - Expand the bounding box by the global bloat for the search
          - Set a jump point, and do an r_search on the pad tree around the current PV (LOCtoPVpad_callback)
            - If the PV doesn't intersect the pad layer (top or bottom), return false (keep looking for objects)
            - If we haven't already flagged the pad, the PV and pad intersect, and the PV isn't just a hole, add the pad to the list, and longjmp back to LookupLOConnectionToPVList
            - Otherwise, return 0 (keep looking for objects)
          - For each layer:
            - if the no_drc flag is set, skip this layer
            - Set a jump point, and do an r_search on the layer's line tree around the via (LOCtoPVline_callback)
              - Repeat the pad procedure here
            - If we returned via long jump, return true (abort search)
            - Otherwise, set a jump point and do an r_search on the layer's arc tree around the via (LOCtoPVarc_callback)
              - Repeat the pad procedure here
            - If we returned via long jump, return true (abort search)
            - Otherwise, set a jump point and do an r_search on the layer's polygon tree around the via (LOCtoPVpoly_callback)
              - If the PV doesn't intersect the polygon layer, return 0 (continue search)
              - If we haven't yet flagged the polygon and the PV isn't just a hole...
                - If there's no thermal and the polygon is clearing, return 0 (continue search)
                - Otherwise...
                  - compute the width of the search box
                  - if the pv has the square flag set,
                    - compute the corner points
                    - if the rectangle is in the polygon (IsRectangleInPolygon) add it to the list (... ends up in add_object_to_list)
                    - if we're doing the drc and the object didn't have the selected flag set, long jump back to to LookupLOConnectionToPVList
                    - otherwise return 0 (continue search)
                  - otherwise, if the pv has the octagon flag set...
                    - create a dummy octagon polygon
                    - if the dummy octagon and the polygon intersect (isects), add it to the list
                    - if we're doing the drc and the object didn't have the selected flag set, long jump back to to LookupLOConnectionToPVList
                  - otherwise, pv is round, and if intersects the polygon (IsPointInPolygon)
                    - add it to the list
                    - if we're doing the drc and the object didn't have the selected flag set, long jump back to LookupLOConnectionToPVList
              - return 0 (continue search)
            - Move on to the next layer
          - If we're following rats, set a jump point and do an r_search on the rat tree (LOCtoPVrat_callback)
            - If we haven't already found the rat, add it to the list, and long jump back to LookupLOConnectionToPVList
          - Increment the position in the list and check the next PV
        - Return false (continue search)
      - LookupLOConnectionsToLOList(flag, AndRats)
  
  
====Uses of the Connection Lookup Algorithm====

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

=== NotifyLine ===
action.c

=== NotifyMode ===
action.c

=== ActionConnection ===
action.c

=== ActionDisplay ===
action.c

=== ActionSaveTo ===
action.c

=== IPCD HID ===

=== GTK HID ===
netlist window

=== netlist.c ===

=== report.c ===

=== Places that call DoIt ===
==Notes from 20180810==
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
gEDA Project Wiki

User Tools

Site Tools

Page Tools
