<> <> DIRECTORY PrincOps, PrincOpsUtils, PCMaps, VM; PCMapsImpl: MONITOR LOCKS map USING map: Map IMPORTS PrincOpsUtils, VM EXPORTS PCMaps ~ BEGIN OPEN PCMaps; <> defaultLowOrderTableSize: CARDINAL _ 8; IllegalInsertion: ERROR = CODE; <> <> LowOrderTablesPerPage: CARDINAL = PrincOps.wordsPerPage/WORDS[LowOrderTable]; -- RDI MapEntriesPerPage: CARDINAL = PrincOps.wordsPerPage/WORDS[MapEntry]; -- RDI SplitPC: TYPE = MACHINE DEPENDENT RECORD [ <> 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; <> <> <> <<-1 <= low < hi <= table.nEntries AND>> <> 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; <> }; 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; <> VM.Free[[PrincOpsUtils.PageNumberForAddress[table], existingSize]]; }; END.