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, March 18, 1987 3:48:55 am PST
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;
Hand allocation is needed in this interface
Cons:
PRIVATE
PROC [iw:
IW, list:
LIST
OF
IW]
RETURNS [new:
LIST
OF
IW] = {
new ← CONS [iw, list];
IF freeIWs=NIL THEN freeIWs ← LIST [[[], NIL]]; -- too bad!
IF freeIWs.first#[[], NIL] THEN ERROR; -- something real bad going on!
new ← freeIWs; new.first ← iw; new.rest ← list; freeIWs ← freeIWs.rest;
};
only disposes of the first element!
Dispose:
PRIVATE
PROC [list:
LIST
OF
IW]
RETURNS [rest:
LIST
OF
IW] = {
rest ← list.rest;
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
FOR values:
LIST
OF
IW ← oldData[i], values.rest
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]];
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] = {
clipped: Interval ← [MAX [interval.min, table.range.min], MIN [interval.max, table.range.max]];
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;
};
Overlapping of two intervals (trivial function).
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];
};