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; 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. ήPCMapsImpl.mesa Carl Hauser, May 13, 1987 6:01:51 pm PDT Interesting Constants LowOrderTablesPerPage: CARDINAL = DragOpsCross.wordsPerPage/WORDS[LowOrderTable]; -- RDI MapEntriesPerPage: CARDINAL = DragOpsCross.wordsPerPage/WORDS[MapEntry]; -- RDI hi, lo: CARD16 -- RDI 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] The remainder of the sequence can remain uninitialized because it will never be referenced beyond table.nEntries-1. The rest of newTable can remain uninitialized because it will never be referenced beyond newTable.nEntries-1 Κ4˜šœ™Icode™(—šΟk ˜ K˜ K˜Kšœ˜Kšœ˜K˜—KšΠln œœœœ ˜,Kšœ˜Kšœ˜šœœœ˜K˜™Kšœœ˜'KšΟnœœœ˜K˜—KšœœœΟc™XKšœœœ™OKšœœœ ˜TKšœœœ˜KK˜šœ œœ˜*Kšœœ ™Kšœœ ˜K˜—K˜š Ÿœœœœœœ˜UKšœœ˜ Kšœœœ˜6˜Kšœ0˜0Kšœ œœœ˜,Kšœ-˜3K˜—K˜K˜—š Ÿœœ œœœœ˜VKšœœ˜#Kšœ œ@˜Ušœœ œ ˜#Kšœ.˜.Kšœœ$œ$˜YK˜K˜—Kšœ (˜=Kšœœ ˜Kš œœœœœœ˜CK˜K˜—šŸœœ œ!œœœœ˜cK˜ K˜ K˜™KšœQœœœ'™—šœ™KšœΟs™$Kšœ$™$—šœ ˜Kšœœ˜šœœœ˜Kšœ-˜-Kšœ/˜/Kšœ˜—Kšœ˜—Kšœ˜K˜K˜—šŸœœœœœœœ˜LKšœœ˜ K˜Kšœ ˜Kšœœ'˜Hšœ#œœ˜/KšœP˜PK˜Kšœ˜šœœœœ˜:KšœW˜WKšœ˜—šœ˜Kšœ˜K˜—K˜—š˜Kšœ5œ˜LKšœN˜Nšœ6˜6šœ#œ˜*KšœC˜C—Kšœ˜Kšœœ˜&K˜—Kšœ˜—Kšœ'˜'Kšœ˜K˜K˜—šŸœ œœ˜CKšœ œ=˜RKšœ œ'˜;Kšœœ$œ$˜mKš œœœœœ˜KKš œœœœ œ˜KKšœ^˜^K˜Kšœ3˜3K˜K˜—šŸœœœœ˜MKšœœ$œ˜SKšœ.œœ˜=K˜K™sK˜K˜—K˜šŸœ œœ˜_Kšœœ*˜@Kšœ œ˜#Kšœ œ$œ ˜YKšœ4œœ˜CK˜#šœœœœ˜*Kšœ-˜-Kšœ#˜#Kšœ˜—K™lKšœC˜CK˜——Kšœ˜—…—΄Ζ