~
BEGIN
OPEN PCMaps;
Interesting Constants
defaultLowOrderTableSize: CARDINAL ← 8;
IllegalInsertion: ERROR = CODE;
LowOrderTablesPerPage: CARDINAL = DragOpsCross.wordsPerPage/WORDS[LowOrderTable]; -- RDI
MapEntriesPerPage: CARDINAL = DragOpsCross.wordsPerPage/WORDS[MapEntry]; -- RDI
LowOrderTablesPerPage: CARDINAL = PrincOps.wordsPerPage/WORDS[LowOrderTable]; -- RDI
MapEntriesPerPage: CARDINAL = PrincOps.wordsPerPage/WORDS[MapEntry]; -- RDI
SplitPC:
TYPE =
MACHINE DEPENDENT RECORD [
hi, lo: CARD16 -- RDI
lo, hi: CARD16 -- SIM
];
Lookup:
PUBLIC
ENTRY SAFE PROC [map: Map, pc: BytePC]
RETURNS [val:
WORD] ~
TRUSTED {
splitPC: SplitPC ~ LOOPHOLE[pc];
IF splitPC.hi > map.nEntries THEN RETURN[map.nullVal];
{
lowTable: LowOrderTable ~ map.table[splitPC.hi];
IF lowTable = NIL THEN RETURN[map.nullVal];
RETURN[BinSrch[splitPC.lo, lowTable, map.nullVal]];
};
};
NewMap:
PUBLIC
SAFE PROC [maxPC: BytePC, nullVal:
WORD]
RETURNS [map: Map] ~
TRUSTED {
splitPC: SplitPC ~ LOOPHOLE[maxPC];
pagesNeeded: CARDINAL ~ (splitPC.hi + LowOrderTablesPerPage) / LowOrderTablesPerPage;
mapRef:
REF MapRep ←
NEW[MapRep ← [
nEntries: pagesNeeded * LowOrderTablesPerPage,
table: LOOPHOLE[PrincOpsUtils.AddressForPageNumber[VM.SimpleAllocate[pagesNeeded].page]],
nullVal: nullVal
]];
mapRef.ref ← mapRef; -- make it circular, hence uncollectable
map ← LOOPHOLE[mapRef];
FOR i: CARDINAL IN [0..map.nEntries) DO map.table[i] ← NIL ENDLOOP;
};
BinSrch:
PROC [target:
CARD16, table: LowOrderTable, nullVal:
WORD]
RETURNS [val:
WORD] ~
TRUSTED {
low, hi: INT;
low ← -1;
hi ← table.nEntries;
Assume:
table.s ordered and extended (logically) by -infinity and +infinity at positions -1 and table.nEntries. These positions must not be referenced;
Inv:
-1 <= low < hi <= table.nEntries AND
table.s[low] <= target < table.s[hi]
WHILE low+1 # hi
DO
mid: INT ← (low+hi)/2;
SELECT
TRUE
FROM
target < table.s[mid].lowOrderPC => hi ← mid;
target >= table.s[mid].lowOrderPC => low ← mid;
ENDCASE;
ENDLOOP;
RETURN[table.s[low].value];
};
Insert:
PUBLIC
ENTRY
SAFE
PROC [map: Map, pc: BytePC, val:
WORD] ~
TRUSTED {
splitPC: SplitPC ~ LOOPHOLE[pc];
table: LowOrderTable;
entry: CARDINAL;
IF splitPC.hi > map.nEntries THEN ExtendHighOrderTable[map, splitPC.hi];
IF (table ← map.table[splitPC.hi]) =
NIL
THEN {
table ← (map.table[splitPC.hi] ← CreateLowOrderTable[defaultLowOrderTableSize]);
table.nEntries ← 1;
table.s[0].lowOrderPC ← 0;
IF splitPC.hi > 0
AND map.table[splitPC.hi-1] #
NIL
THEN {
table.s[0].value ← map.table[splitPC.hi-1].s[map.table[splitPC.hi-1].nEntries-1].value;
}
ELSE {
table.s[0].value ← map.nullVal;
};
};
SELECT TRUE FROM
splitPC.lo < table.s[table.nEntries-1].lowOrderPC => ERROR IllegalInsertion;
splitPC.lo = table.s[table.nEntries-1].lowOrderPC => entry ← table.nEntries-1;
splitPC.lo > table.s[table.nEntries-1].lowOrderPC => {
IF table.nEntries = table.maxEntries
THEN
map.table[splitPC.hi] ← ExtendLowOrderTable[map.table[splitPC.hi]];
entry ← table.nEntries;
table.nEntries ← SUCC[table.nEntries];
};
ENDCASE;
table.s[entry].lowOrderPC ← splitPC.lo;
table.s[entry].value ← val;
};
ExtendHighOrderTable:
INTERNAL PROC [map: Map, entries:
CARD16] ~ {
pagesNeeded: CARDINAL ~ (entries + LowOrderTablesPerPage) / LowOrderTablesPerPage;
newEntries: CARDINAL ~ pagesNeeded * LowOrderTablesPerPage;
newTable: HighOrderTable ~ LOOPHOLE[PrincOpsUtils.AddressForPageNumber[VM.SimpleAllocate[pagesNeeded].page]];
FOR i: CARDINAL IN [0..map.nEntries) DO newTable[i] ← map.table[i] ENDLOOP;
FOR i: CARDINAL IN [map.nEntries..newEntries) DO newTable[i] ← NIL ENDLOOP;
VM.Free[[PrincOpsUtils.PageNumberForAddress[map.table], map.nEntries/LowOrderTablesPerPage]];
map.table ← newTable;
map.nEntries ← pagesNeeded * LowOrderTablesPerPage;
};
CreateLowOrderTable:
PROC [size:
CARDINAL]
RETURNS [table: LowOrderTable] ~ {
table ← LOOPHOLE[PrincOpsUtils.AddressForPageNumber[VM.SimpleAllocate[size].page]];
table.maxEntries ← size*MapEntriesPerPage - 2*SIZE[CARDINAL];
table.nEntries ← 0;
The remainder of the sequence can remain uninitialized because it will never be referenced beyond table.nEntries-1.
};
ExtendLowOrderTable:
INTERNAL PROC [table: LowOrderTable]
RETURNS [newTable: LowOrderTable] ~ {
existingSize: CARDINAL ← table.maxEntries/MapEntriesPerPage + 1;
newSize: CARDINAL ← 2*existingSize;
newTable ← LOOPHOLE[PrincOpsUtils.AddressForPageNumber[VM.SimpleAllocate[newSize].page]];
newTable.maxEntries ← newSize*MapEntriesPerPage - 2*SIZE[CARDINAL];
newTable.nEntries ← table.nEntries;
FOR i:
CARDINAL
IN [0..table.nEntries)
DO
newTable[i].lowOrderPC ← table[i].lowOrderPC;
newTable[i].value ← table[i].value;
ENDLOOP;
The rest of newTable can remain uninitialized because it will never be referenced beyond newTable.nEntries-1
VM.Free[[PrincOpsUtils.PageNumberForAddress[table], existingSize]];
};