<> <> <> DIRECTORY Allocator USING[NHeaderP], AllocatorOps USING[FreeObject, NHPToREF, PlausibleRef, ReferentType, REFToNHP], Basics USING[LongNumber, BITAND, BITOR], Collector USING[], -- EXPORTS only RCMapOps USING[GetBase], RCMap USING[Index, Base, nullIndex], RCMicrocodeOps USING[ReclaimedRef], Rope USING[RopeRep, ROPE], RTTypesBasicPrivate USING[DoFREEify, MapTiTd], SafeStorage USING[Type]; ReclaimerImpl: PROGRAM IMPORTS AllocatorOps, Basics, RCMapOps, RCMicrocodeOps, RTTypesBasicPrivate EXPORTS Collector SHARES Rope = BEGIN OPEN SafeStorage; rcmb: RCMap.Base = RCMapOps.GetBase[].base; checking: BOOL = FALSE; Reclaim: PUBLIC PROC[nhp: Allocator.NHeaderP] = { IF RTTypesBasicPrivate.MapTiTd[nhp.type].rcmx = RCMap.nullIndex THEN AllocatorOps.FreeObject[nhp] ELSE { ref: REF _ AllocatorOps.NHPToREF[nhp]; PAPtr: TYPE = LONG POINTER TO ARRAY OF Basics.LongNumber; <> prev: LONG POINTER TO Basics.LongNumber _ NIL; DO -- outer loop UNTIL ref = NIL DO <> refType: Type _ LOOPHOLE[AllocatorOps.ReferentType[ref], Type]; -- NOTE XXX nextx: CARDINAL _ 0; < >> <> <> first: REF ANY _ NIL; <> FreeRef: PROC[r: REF] = {DoFreeRef[r]}; DoFreeRef: PROC[r: REF] = INLINE { IF r = NIL THEN RETURN; IF checking AND NOT AllocatorOps.PlausibleRef[LOOPHOLE[r, LONG CARDINAL]] THEN ERROR; r _ RCMicrocodeOps.ReclaimedRef[r]; IF r # NIL THEN { -- r^ can also be reclaimed. IF first = NIL THEN first _ r ELSE Push[r]; }; }; Push: PROC[r: REF] = --INLINE-- { IF nextx = 0 THEN { LOOPHOLE[ref, PAPtr][0] _ MarkBackPointer[LOOPHOLE[prev]]; LOOPHOLE[ref, PAPtr][1] _ LOOPHOLE[r, Basics.LongNumber]; nextx _ 2; } ELSE { LOOPHOLE[ref, PAPtr][nextx] _ LOOPHOLE[r, Basics.LongNumber]; nextx _ nextx + 1; }; }; FREEify: PROC[ptr: LONG POINTER, rcmx: RCMap.Index] = INLINE { <> WITH rcmr: rcmb[rcmx] SELECT FROM null => NULL; oneRef => DoFreeRef[LOOPHOLE[ptr+rcmr.offset, LONG POINTER TO REF ANY]^]; simple => FOR i: CARDINAL IN [0..rcmr.length) DO IF rcmr.refs[i] THEN {DoFreeRef[LOOPHOLE[ptr+i, LONG POINTER TO REF ANY]^]}; ENDLOOP; ref => DoFreeRef[LOOPHOLE[ptr, LONG POINTER TO REF ANY]^]; ENDCASE => RTTypesBasicPrivate.DoFREEify[ptr, rcmx, FreeRef]; }; <<>> <<***Start this iteration of inner loop 1 Here***>> IF refType = CODE[Rope.RopeRep] -- special (faster) case for ROPEs THEN refType _ WITH t: LOOPHOLE[ref, Rope.ROPE] SELECT FROM text => CODE[Rope.RopeRep.text], node => WITH v: t SELECT FROM substr => CODE[Rope.RopeRep.node.substr], concat => CODE[Rope.RopeRep.node.concat], replace => CODE[Rope.RopeRep.node.replace], object => CODE[Rope.RopeRep.node.object] ENDCASE => ERROR ENDCASE => ERROR; FREEify[ LOOPHOLE[ref, LONG POINTER], RTTypesBasicPrivate.MapTiTd[refType].rcmx]; IF nextx = 0 THEN AllocatorOps.FreeObject[AllocatorOps.REFToNHP[ref]] <> <<(no extra objects to remember to reclaim later)>> ELSE prev _ LOOPHOLE[@LOOPHOLE[ref, PAPtr][nextx - 1]]; <> <<(must remember to reclaim it later; use ref^ for storage)>> ref _ first; <> ENDLOOP; -- inner loop 1 DO -- inner loop 2: pop the next pushed ref, reclaiming its container if it becomes empty. If there's no pushed ref to pop, terminate Reclaim. p: Basics.LongNumber; IF prev = NIL THEN RETURN <> ELSE IF IsBackPointer[p _ prev^] THEN { -- it's a back pointer; the container addressed by prev is empty AllocatorOps.FreeObject[AllocatorOps.REFToNHP[LOOPHOLE[prev, REF]]]; prev _ LOOPHOLE[UnmarkBackPointer[p]]; <> } ELSE { ref _ LOOPHOLE[p, REF]; prev _ prev - SIZE[REF]; -- prev addresses the previous slot in this container EXIT; -- go around again with the new ref }; ENDLOOP; -- inner loop 2 ENDLOOP; -- outer loop }; -- end ELSE }; -- end Reclaim BackPointerMarkBit: CARDINAL = 100000B; <> IsBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[BOOL] = INLINE { RETURN[Basics.BITAND[ptr.highbits, BackPointerMarkBit] # 0]; }; MarkBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[Basics.LongNumber] = INLINE { ptr.highbits _ Basics.BITOR[ptr.highbits, BackPointerMarkBit]; RETURN[ptr]; }; UnmarkBackPointer: PROC[ptr: Basics.LongNumber] RETURNS[Basics.LongNumber] = INLINE { BackPointerUnmarkMask: CARDINAL = BackPointerMarkBit - 1; ptr.highbits _ Basics.BITAND[ptr.highbits, BackPointerUnmarkMask]; RETURN[ptr]; }; END.