Method and apparatus for generating a linked data structure for integrated circuit layout

Claim 3

The method of claim 1, including, after step 2 and before step 3, the step of merging adjacent cells of the same type, and storing the merged cells as single cells.

Claim 4

The method of claim 1, including, after step 2 and before step 3, the step of fracturing cells along a predetermined dimension to generate convex cell structures, and storing the convex cell structures.

Claim 5

The method of claim 1, wherein step 2 includes the step of storing as an entry in said cell record a related cell pointer pointing to a cell contacting the cell represented by the cell record, but positioned in a different layer of the layout.

Claim 6

The method of claim 1, wherein step 9 further includes the step of generating and storing with each said point record an entry representing a move distance for the referenced point in the execution of a layout modification routine.

Claim 7

The method of claim 1, further including, after step 8 and before step 9, the step of merging adjacent cells of like material where such merging results in convex structures, and storing the merged cells in the memory.

Claim 8

A computer readable memory that can be used to direct a computer to function in a specified manner, comprising: cell data stored in said memory, said cell data including: (1) a list of cells representing a circuit layout, each cell having a specified type, (2) a cell record in a cell table for each cell of said list of cells, each said cell record including a boundary pointer pointing to a boundary record in a boundary table, each boundary record including an adjacent cell pointer, an edge pointer and a next entry pointer for the next record in the boundary table, the adjacent cell pointer pointing to a cell adjacent to the cell for the current boundary record, if any, and the edge pointer pointing to an edge record in an edge table; and executable instructions stored in said memory, said executable instructions including: (3) instructions to select a cell as the current cell, (4) instructions to select an edge of the current cell as the current edge, (5) instructions to produce a division line along the current edge, (6) instructions to subdivide any edges stored in the data structure that are intersected by the generated division line into smaller edges and thereafter store one said edge record for each of the smaller edges, (7) loop control instructions for repeating the execution of instructions (4)-(6) until each edge of the current cell has been processed by instructions (4)-(6), (8) loop control instructions for repeating the execution of instructions (3)-(7) until each cell has been processed by instructions (3)-(7), and (9) instructions to store in each edge record a first endpoint entry and a second endpoint entry, the first endpoint entry including a pointer to a point record in a point table, each point record including entries representing coordinates of the point represented by the point record.

Claim 9

A computer readable memory that can be used to direct a computer to function in a specified manner, comprising: cell data stored in said memory, said cell data including: (1) a list of cells representing a circuit layout, each cell having a specified type, (2) a cell record in a cell table for each cell of said list of cells, each said cell record including a boundary pointer pointing to a boundary record in a boundary table, each boundary record including an adjacent cell pointer, an edge pointer and a next entry pointer for the next record in the boundary table, the adjacent cell pointer pointing to a cell adjacent to the cell for the current boundary record, if any, and the edge pointer pointing to an edge record in an edge table; and executable instructions stored in said memory, said executable instructions including: (3) instructions to select a cell as the current cell, (4) instructions to select an edge of the current cell as the current edge, (5) instructions to produce a division line along the current edge, (6) instructions to subdivide any edges stored in the data structure that are intersected by the generated division line into smaller edges and thereafter store one said edge record for each of the smaller edges, (7) loop control instructions for repeating the execution of instructions (4)-(6) until each edge of the current cell has been processed by instructions (4)-(6), (8) loop control instructions for repeating the execution of instructions (3)-(7) until each cell has been processed by instructions (3)-(7), and (9) instructions to store in each edge record a first endpoint entry and a second endpoint entry, the first endpoint entry including a pointer to a point record in a point table, each point record including entries representing coordinates of the point represented by the point record.

Claim 10

The computer readable memory of claim 7 further comprising instructions, executed between instructions (2) and (3), to merge adjacent cells of the same type and store the merged cells as single cells.

Claim 11

The computer readable memory of claim 7 further comprising instructions, executed between instructions (2) and (3), to fracture cells along a predetermined dimension to generate and store convex cell structures.

Claim 12

The computer readable memory of claim 7 wherein instructions (2) include instructions to store as an entry in said cell record a related cell pointer pointing to a cell contracting the cell represented by the cell record, but positioned in a different layer of the layout.

Claim 13

The computer readable memory of claim 7 wherein instructions (9) include instructions to generate and store with each said point record an entry representing a move distance for the referenced point in the execution of a layout modification routine.

Claim 14

The computer readable memory of claim 7 further comprising instructions, executed between instructions (8) and (9), to merge adjacent cells of like material where such merging results in convex structures, and to store the merged cells in the memory.