DIRECTORY Allocator USING [NHeaderP], AllocatorOps USING [FreeObject, NHPToREF, PlausibleRef, 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; PtrToRef: TYPE = LONG POINTER TO REF ANY; RefIndex: TYPE = NAT; 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 PASeq; PASeq: TYPE = RECORD [ SEQUENCE COMPUTED RefIndex OF Basics.LongNumber ]; prev: LONG POINTER TO Basics.LongNumber _ NIL; DO UNTIL ref = NIL DO head: Allocator.NHeaderP = AllocatorOps.REFToNHP[ref]; refType: Type _ head.type; nextx: CARDINAL _ 0; first: REF _ NIL; FreeRef: PROC [r: REF] = {DoFreeRef[r]}; DoFreeRef: PROC [r: REF] = INLINE { IF r # NIL THEN { IF checking AND NOT AllocatorOps.PlausibleRef[LOOPHOLE[r]] THEN ERROR; r _ RCMicrocodeOps.ReclaimedRef[r]; SELECT TRUE FROM r = NIL => {}; first = NIL => first _ r; nextx = 0 => { LOOPHOLE[ref, PAPtr][0] _ MarkBackPointer[LOOPHOLE[prev]]; LOOPHOLE[ref, PAPtr][1] _ LOOPHOLE[r, Basics.LongNumber]; nextx _ 2; }; ENDCASE => { LOOPHOLE[ref, PAPtr][nextx] _ LOOPHOLE[r, Basics.LongNumber]; nextx _ nextx + 1; }; }; }; { rcmx: RCMap.Index; IF refType = CODE[Rope.RopeRep] THEN WITH t: LOOPHOLE[ref, Rope.ROPE] SELECT FROM text => GO TO none; node => refType _ 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; rcmx _ RTTypesBasicPrivate.MapTiTd[refType].rcmx; WITH rcmr: rcmb[rcmx] SELECT FROM null => {}; oneRef => DoFreeRef[(LOOPHOLE[ref, PtrToRef]+rcmr.offset)^]; simple => FOR i: CARDINAL IN [0..rcmr.length) DO IF rcmr.refs[i] THEN DoFreeRef[(LOOPHOLE[ref, PtrToRef]+i)^]; ENDLOOP; ref => DoFreeRef[LOOPHOLE[ref, PtrToRef]^]; ENDCASE => RTTypesBasicPrivate.DoFREEify[LOOPHOLE[ref, PtrToRef], rcmx, FreeRef]; EXITS none => {}; }; IF nextx = 0 THEN AllocatorOps.FreeObject[head] ELSE prev _ LOOPHOLE[@LOOPHOLE[ref, PAPtr][nextx - 1]]; ref _ first; ENDLOOP; DO p: Basics.LongNumber; SELECT TRUE FROM prev = NIL => RETURN; IsBackPointer[p _ prev^] => { AllocatorOps.FreeObject[AllocatorOps.REFToNHP[LOOPHOLE[prev, REF]]]; prev _ LOOPHOLE[UnmarkBackPointer[p]]; }; ENDCASE => { ref _ LOOPHOLE[p, REF]; prev _ prev - SIZE[REF]; EXIT; }; ENDLOOP; ENDLOOP; }; }; IsBackPointer: PROC [ptr: Basics.LongNumber] RETURNS[BOOL] = INLINE { RETURN[Basics.BITAND[ptr.highbits, BackPointerMarkBit] # 0]; }; BackPointerMarkBit: CARDINAL = 100000B; 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. 8ReclaimerImpl.Mesa Copyright c 1985, 1986 by Xerox Corporation. All rights reserved. Richard Koo, July 2, 1984 4:53:39 pm PDT Russ Atkinson (RRA) April 15, 1986 3:34:16 pm PST This type is sufficient to index all references in an object when the object is treated as a PASeq. This should change when we get larger objects possible. The 0th element is a marked (as a "backpointer") pointer. Its pointer part is either NIL or a pointer to the last REF in a previous such array. Other elements are REFs to objects that become reclaimable as other objects are reclaimed. This code avoids both the use of recursion and the use of extra storage by the reclaimer. outer loop inner loop 1: each iteration walks the component refs of the current ref^, applying ReclaimedRef to each and remembering which of the objects so referenced can also be reclaimed. inner loop 1 terminates nextx # 0 => first # NIL nextx = the index relative to LOOPHOLE[ref, PAPtr] of the next place to push a ref to an object discovered while reclaiming ref^ that can also be reclaimed the first object discovered while reclaiming ref^ that can also be reclaimed ***Start this iteration of inner loop 1 Here*** special (faster) case for ROPEs low index to high. DoFreeRef for ea. component ref at most 1 object referenced from within ref^ that can also be reclaimed (no extra objects to remember to reclaim later) more than 1 object referenced from within ref^ that can also be reclaimed (must remember to reclaim it later; use ref^ for storage) NIL unless at least one object referenced from within ref^ can also be reclaimed 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. the given object and all objects referenced only from it (and recursively) have been reclaimed it's a back pointer; the container addressed by prev is empty prev now addresses the last slot in the next container to empty prev addresses the previous slot in this container go around again with the new ref a power of 2, one of the extra bits in a long pointer Κ”˜codešœ™Kšœ Οmœ7™BKšœ(™(J™1—˜šΟk ˜ Kšœ žœ ˜Kšœ žœ0˜BKšœžœžœžœ˜)Kšœ žœΟc˜$Kšœ žœ ˜Kšœžœ˜%Kšœžœ˜$Kšœžœ žœ˜Kšœžœ˜/Kšœ žœ˜——K˜šœž˜Kšžœ žœ5˜KKšžœ ˜Kšžœ˜ Kšœž œ ˜K˜Kš œ žœžœžœžœžœžœ˜)K˜šœ žœžœ˜Kšœœ™œ—K˜Kšœ+˜+Kšœ žœžœ˜K˜—šΟnœžœžœ˜2šžœ=˜?Kšžœ˜!šžœ˜Kšœžœ˜&š œžœžœžœžœ˜$K™Η—šœžœžœ˜Kšžœžœ žœ˜/K˜—Kš œžœžœžœžœ˜.šž˜Kšœ ™ šžœžœž˜KšœΜ™ΜKšœ6˜6Kšœ˜šœžœ˜šœ ™ Kšœ ™ Kšœ›™›——šœžœžœ˜KšœL™L—K˜Kš œžœžœ˜(K˜š  œžœžœžœ˜#šžœžœžœ˜Kš žœ žœžœžœžœžœ˜FKšœ#˜#šžœžœž˜Kšœžœ˜Kšœžœ˜šœ˜Kšžœ"žœ˜:Kšžœžœ˜9Kšœ ˜ K˜—šžœ˜ Kšžœžœ˜=Kšœ˜K˜——K˜—Kšœ˜K˜—Kšœ/™/˜Kšœ˜šžœ žœž˜$Kšœ™š žœžœ žœžœž˜,Kšœžœžœ˜šœ˜šžœžœž˜Kšœ žœ˜)Kšœ žœ˜)Kšœ žœ˜+Kšœ žœ˜(—Kšžœžœ˜—Kšžœžœ˜——Kšœ2™2Kšœ1˜1šžœžœž˜!Kšœ ˜ šœ ˜ Kšœ žœ˜2—šœ ˜ šžœžœžœž˜&Kšžœžœ žœ˜=Kšžœ˜——šœ˜Kšœ žœ˜$—šžœ˜ Kšœžœ ˜F——Kšžœ ˜K˜K˜—šžœ ˜ šžœ˜"šœG™GKšœ/™/——šžœžœžœ˜7šœI™IKšœ9™9———šœ ˜ KšžœM™P—Kšžœ˜—K˜šž˜Kšœ‰™‰Kšœ˜šžœžœž˜šœžœžœ˜Kšœ^™^—šœ˜Kšœ=™=Kšœ.žœžœ˜Dšœžœ˜&Kšœ?™?—Kšœ˜—šžœ˜ Kšœžœžœ˜šœžœžœ˜Kšœ2™2—šžœ˜Kšœ ™ —K˜——Kšžœ˜—Kšžœ˜—Kšœ˜——Kšœ˜K˜—š   œžœžœžœžœ˜EKšžœžœ(˜Kšžœ˜ Kšœ˜—K˜š œžœžœžœ˜UKšœžœ˜9Kšœžœ&˜BKšžœ˜ Kšœ˜—K˜Kšžœ˜K˜—…— œh