DIRECTORY Basics USING [BITSHIFT], CD, Core, CoreGeometry, SinixIntervals; SinixIntervalsImpl: CEDAR MONITOR LOCKS table USING table: Table IMPORTS Basics, CoreGeometry EXPORTS SinixIntervals = BEGIN OPEN SinixIntervals; freeIWs: LIST OF IW _ NIL; Cons: PRIVATE PROC [iw: IW, list: LIST OF IW] RETURNS [new: LIST OF IW] = { IF freeIWs=NIL THEN freeIWs _ LIST [[[], NIL]]; -- too bad! IF freeIWs.first#[[], NIL] THEN ERROR; -- something real bad going on! new _ freeIWs; freeIWs _ freeIWs.rest; new.first _ iw; new.rest _ list; }; Dispose: PRIVATE PROC [list: LIST OF IW] RETURNS [rest: LIST OF IW] = { rest _ list.rest; list.first _ [[], NIL]; list.rest _ freeIWs; freeIWs _ list; IF freeIWs.first#[[], NIL] THEN ERROR; -- something real bad going on! }; InstanceInterval: PROC [instance: CoreGeometry.Instance] RETURNS [interval: Interval] = INLINE { rect: CD.Rect _ CoreGeometry.InlineBBox[instance]; RETURN [[rect.y1, rect.y2]]; }; Normalize: PROC [table: Table, interval: Interval] RETURNS [buckets, min, max: NAT] = INLINE { width: INT = table.range.max + 1 - table.range.min; buckets _ (table.data.hashSize+1)/2; min _ ((interval.min - table.range.min) * buckets) / width; max _ ((interval.max - table.range.min) * buckets) / width; IF min<0 OR max>=buckets THEN ERROR; -- ERROR probably due to an interval outside the table range }; Hash: PROC [table: Table, instance: CoreGeometry.Instance] RETURNS [hash: NAT _ 0]= { buckets, min, max: NAT; [buckets, min, max] _ Normalize[table, InstanceInterval[instance]]; UNTIL min=max DO hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; hash _ hash + min; }; Create: PUBLIC PROC [range: Interval, logHashSize: NAT _ 2] RETURNS [Table] = { data: REF TableData _ NEW [TableData[Basics.BITSHIFT[value: 1, count: logHashSize]-1]]; RETURN [NEW [TableRec _ [range: range, leafBuckets: 0, data: data]]]; }; ReHash: PROC [table: Table] = { oldData: REF TableData _ table.data; newData: REF TableData _ NEW [TableData[oldData.hashSize*2+1]]; table.data _ newData; table.leafBuckets _ 0; FOR i: NAT IN [0 .. oldData.hashSize) DO values: LIST OF IW _ oldData[i]; WHILE values#NIL DO hash: NAT _ Hash[table, values.first.instance]; IF newData[hash]=NIL THEN table.leafBuckets _ table.leafBuckets+1; newData[hash] _ Cons[values.first, newData[hash]]; values _ Dispose[values]; ENDLOOP; ENDLOOP; }; Insert: PUBLIC ENTRY PROC [table: Table, instance: CoreGeometry.Instance, wire: Core.Wire] = { ENABLE UNWIND => NULL; hash: NAT _ Hash[table, instance]; IF table.data[hash]=NIL THEN table.leafBuckets _ table.leafBuckets+1; table.data[hash] _ Cons[[instance, wire], table.data[hash]]; IF table.leafBuckets * 2 > table.data.hashSize THEN ReHash[table]; }; Enumerate: PUBLIC PROC [table: Table, action: PROC [CoreGeometry.Instance, Core.Wire], interval: Interval _ universe] = { data: REF TableData _ table.data; -- stored in the local frame to avoid concurrent inconsistencies buckets, min, max: NAT; hash: NAT _ 0; clipped: Interval _ [MAX [interval.min, table.range.min], MIN [interval.max, table.range.max]]; IF clipped.min>clipped.max THEN RETURN; -- empty interval [buckets, min, max] _ Normalize[table, clipped]; WHILE buckets>0 DO FOR i: NAT IN [hash+min .. hash+max] DO FOR values: LIST OF IW _ data[i], values.rest WHILE values#NIL DO IF Overlap[InstanceInterval[values.first.instance], clipped] THEN action[values.first.instance, values.first.wire]; ENDLOOP; ENDLOOP; hash _ hash + buckets; buckets _ buckets / 2; min _ min / 2; max _ max / 2; ENDLOOP; }; DeleteOutside: PUBLIC ENTRY PROC [table: Table, interval: Interval] = { FOR i: NAT IN [0 .. table.data.hashSize) DO IF table.data[i]#NIL THEN { current: LIST OF IW _ table.data[i]; previous: LIST OF IW _ NIL; -- either NIL or the node before current allDeleted: BOOL _ TRUE; UNTIL current = NIL DO SELECT TRUE FROM Overlap[interval, InstanceInterval[current.first.instance]] => { allDeleted _ FALSE; previous _ current; current _ current.rest; }; previous = NIL => current _ table.data[i] _ Dispose[current]; ENDCASE => current _ previous.rest _ Dispose[current]; ENDLOOP; IF allDeleted THEN table.leafBuckets _ table.leafBuckets-1; }; ENDLOOP; }; Overlap: PROC [interval1, interval2: Interval] RETURNS [BOOL] = INLINE { RETURN [(interval1.min<=interval2.max) AND (interval2.min<=interval1.max)]; }; Size: PROC [table: Table] RETURNS [size: INT _ 0] = { Count: PROC [CoreGeometry.Instance, Core.Wire] = {size _ size + 1}; Enumerate[table, Count]; }; END. вSinixIntervalsImpl.mesa Copyright ╙ 1985, 1987 by Xerox Corporation. All rights reversed. Created by Bertrand Serlet, November 16, 1985 7:22:05 pm PST Bertrand Serlet, April 28, 1987 10:52:48 pm PDT Hand allocation for efficiency reasons equivalent to: new _ CONS [iw, list]; equivalent to: rest _ list.rest; only disposes of the first element! Overlapping of two intervals (trivial function). For debugging! Э╩&Ц "cedar" styleШcodeЪЬЩKЪЬBЩBKЪЬ9╧kЩ