SinixD2IntervalsImpl.mesa
Copyright Ó 1985, 1987 by Xerox Corporation. All rights reversed.
Created by Bertrand Serlet, March 8, 1986 1:51:29 pm PST
Bertrand Serlet, March 29, 1987 11:25:51 pm PST
DIRECTORY
Basics USING [BITSHIFT],
CDBasics, Core, CoreGeometry,
SinixD2Intervals,
SinixIntervals;
SinixD2IntervalsImpl:
CEDAR
MONITOR
LOCKS table
USING table: Table
IMPORTS Basics, CDBasics, CoreGeometry, SinixIntervals EXPORTS SinixD2Intervals = BEGIN
OPEN SinixD2Intervals;
Normalize:
PROC [table: Table, rect: Rect]
RETURNS [buckets, min, max:
NAT] =
INLINE {
width: INT = table.range.x2 + 1 - table.range.x1;
buckets ← (table.data.hashSize+1)/2;
min ← ((rect.x1 - table.range.x1) * buckets) / width;
max ← ((rect.x2 - table.range.x1) * 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, CoreGeometry.InlineBBox[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: Rect, 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] = {
ReInsert:
PROC [instance: CoreGeometry.Instance, wire: Core.Wire] = {
hash: NAT ← Hash [table, instance];
IF newData[hash]=
NIL
THEN {
newData[hash] ← SinixIntervals.Create[range: [table.range.y1, table.range.y2], logHashSize: 1];
table.leafBuckets ← table.leafBuckets+1;
};
SinixIntervals.Insert[newData[hash], instance, wire];
};
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
IF oldData[i]#NIL THEN SinixIntervals.Enumerate[oldData[i], ReInsert];
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.data[hash] ← SinixIntervals.Create[range: [table.range.y1, table.range.y2], logHashSize: 1];
table.leafBuckets ← table.leafBuckets+1;
};
SinixIntervals.Insert[table.data[hash], instance, wire];
IF table.leafBuckets * 2 > table.data.hashSize THEN ReHash[table];
};
Enumerate:
PUBLIC
PROC [table: Table, action:
PROC [CoreGeometry.Instance, Core.Wire], rect: Rect ← universe] = {
SubEnumerate:
PROC [instance: CoreGeometry.Instance, wire: Core.Wire] = {
IF CDBasics.Intersect[CoreGeometry.InlineBBox[instance], clipped] THEN action[instance, wire];
};
data: REF TableData ← table.data; -- stored in the local frame to avoid concurrent inconsistencies
buckets, min, max: NAT;
hash: NAT ← 0;
clipped: Rect ← CDBasics.Intersection[rect, table.range];
IF NOT CDBasics.NonEmpty[clipped] THEN RETURN; -- empty rect
[buckets, min, max] ← Normalize[table, clipped];
IF min<0 OR max>=buckets THEN ERROR; -- bug in the implementation
WHILE buckets>0
DO
FOR i:
NAT
IN [hash+min .. hash+max]
DO
IF data[i]#NIL THEN SinixIntervals.Enumerate[data[i], SubEnumerate, [clipped.y1, clipped.y2]];
ENDLOOP;
hash ← hash + buckets; buckets ← buckets / 2;
min ← min / 2; max ← max / 2;
ENDLOOP;
};
DeleteOutside:
PUBLIC
ENTRY
PROC [table: Table, rect: Rect] = {
hash: NAT ← 0;
buckets, min, max: NAT;
clipped: Rect ← CDBasics.Intersection[rect, table.range];
nonEmpty: BOOL ← CDBasics.NonEmpty[clipped];
[buckets, min, max] ← Normalize[table, IF nonEmpty THEN clipped ELSE table.range];
WHILE buckets>0
DO
FOR i:
NAT
IN [hash .. hash+buckets)
DO
subTable: SinixIntervals.Table = table.data[i];
IF subTable=NIL THEN LOOP;
SinixIntervals.DeleteOutside[
subTable,
IF nonEmpty AND i>=hash+min AND i<=hash+max THEN [rect.y1, rect.y2] ELSE SinixIntervals.empty
];
ENDLOOP;
hash ← hash + buckets; buckets ← buckets / 2;
min ← min / 2; max ← max / 2;
ENDLOOP;
};
Size:
PROC [table: Table]
RETURNS [size:
INT ← 0] = {
Count: PROC [CoreGeometry.Instance, Core.Wire] = {size ← size + 1};
Enumerate[table, Count];
};