(* (* $VER: Collector 1.0 (10-Feb-94) Copyright © by Lars Düning *) *) DEFINITION Collector; DEFINITION CollectorS; --------------------------------------------------------------------------- Allocation and garbage-collection of elemental objects. Copyright © 1993-1994 by Lars Düning - All rights reserved. Permission granted for non-commercial use. --------------------------------------------------------------------------- TYPE: various pointers ElementP *= POINTER TO Element; FreeDataP *= POINTER TO FreeData; TYPE: Base structure of an collectable element Element *= RECORD next : ElementP; next element; NIL for unchained elements prev : ElementP; previous element; or GC pass# of freelisting ecType -: SHORTINT; type of this element ('*'-type in CollectorS) ecFlags -: SHORTSET; color and other flags END; CONST: Element.ecFlags Black *= 0; Color 'black', must be 1-White White *= 1; Color 'white', must be 1-Black Grey *= 2; Color 'grey' Dark *= 5; set for root elements which are already processed Root *= 6; set for members of the root set Base *= 7; Baseelement of a ring TYPE: A Freelist entry for one ecType FreeData *= STRUCT list -: ElementP; List of free elements new -: PROCEDURE () : ElementP; Allocator procedure root -: BOOLEAN; Flag if these elements are 'Root' max -: LONGINT; Max number of elements to hold nrList -: LONGINT; Current number of held elements nrReq -: LONGINT; Total count of requests for a new Element nrRecyc -: LONGINT; Count of Element requests served from the free list nrFreed -: LONGINT; Total count of Element freed END; FreeListP *= POINTER TO ARRAY OF FreeData; VAR black -: INTEGER; Actual colors white -: INTEGER; nrTypes -: SHORTINT; Number of registered ecTypes freelist -: FreeListP; All Freelists sweeping -: BOOLEAN; GC state: false: marking, true: sweeping gcRuns -: LONGINT; Count of GC runs gcCalls -: LONGINT; Calls to GC() during this run VAR: And for my curiosity... gcReqT -: LONGINT; Total number of elements requested gcFreeT -: LONGINT; Total number of elements freed by GC so far gcExaT -: LONGINT; Total number of elements examinated by GC so far gcCallsT -: LONGINT; Total count of calls to GC() gcFree -: LONGINT; Actual number of elements freed this GC-run gcExa -: LONGINT; Actual number of elements examinated this GC-run METHOD (this : ElementP) mark *; Mark all elements which are referenced by this element as grey. Argument: this: the referencing element. The element itself is marked by the collector. CONST: Returnvalues of this.free() keep *= 0; enlist *= 1; dispose *= 2; METHOD (this : ElementP) free * () : INTEGER; Let an unreferenced element clean up itself. Argument: this: the now unreferenced element. Result: keep : the element is still alive, keep it. enlist : put the element into its freelist. dispose: deallocate the element. The result determines the action done by the collector. PROCEDURE RegisterType * ( new : PROCEDURE() : ElementP ; isRoot : BOOLEAN ; max : LONGINT ) : SHORTINT; Register a new collectable type. Arguments: new : the procedure to allocate a record of that type. isRoot : TRUE if these elements are to be members of the root set. max : the max number of records to hold in the freelist. Result: The ecType number for the registered type. PROCEDURE New * (type : SHORTINT) : ElementP; Return an element of the given type. Arguments: type : the type number for the requested element. Result: A pointer to the new element. The element is allocated either from the freelist, or using the 'new' procedure. It is entangled into the collector lists, either in the normalset, or if .root is TRUE, in the rootset. PROCEDURE Allocate * (type : SHORTINT) : ElementP; Return an element of the given type. Arguments: type : the type number for the requested element. Result: A pointer to the new element. The element is allocated either from the freelist, or using the 'new' procedure. It is NOT entangled into the collector lists. Use it with care! PROCEDURE Free * (elem : ElementP; dealloc : BOOLEAN); Remove an element from the active ring. Arguments: elem : the element to remove. dealloc : flag if the element should be deallocated. The element is removed from its ring (if any) and added to the freelist of its type, unless 'dealloc' is false, then it is deallocated. Normally there is no need to call this function by hand! PROCEDURE ShortenLists * (age : LONGINT); Remove old elements from the freelists. Argument: age : the age in GC runs an element needs to stay in the lists. Elements older than 'age' GC runs are deallocated; with an 'age' of 0 causing the deallocation of all elements. PROCEDURE Mark * (this : ElementP); Mark an element as grey. Argument: this : the element to shade grey. The element is colored grey (meaning "referenced but unprocessed") and enqueued into the 'grey' ring of its set. Non-'white' elements are not recolored or requeued. Processed 'dark' white rootset elements are just recolored. This function is to be called by the .mark()-methods during GC, and by Check(). When using CollectorS (and just then), inlining is strongly recommended. PROCEDURE Check * (this, elem : ElementP); Check and possibly recolor an element after referencing. Argument: this : the element referencing 'elem'. elem : the element to check. The element is colored grey (meaning "referenced but unprocessed") and enqueued into the 'grey' ring of its set if it is referenced by a non-white element 'this'. Non-'white' elements are not recolored or requeued. Processed 'dark' white rootset elements are just recolored. This function is to be called if 'elem' was just referenced by 'this' element. When using CollectorS (and just then), inlining is strongly recommended. PROCEDURE GC * (steps : LONGINT) : BOOLEAN; Perform a garbage collection - one step of a full run. Argument: steps : total number of steps (calls) the GC shall need. A value < 2 enforces a completing/full run. Result: TRUE if the GC is complete. Perform one step (or a completing/complete run) of the Mark-and-Sweep-GC for the elements. The procedure loops either over n elements or until the end of one run. 'n' is derived from the number of existing elements divided by the given number of 'steps' to do. If the GC is complete, a call to ShortenLists() should be done. Note that a 'complete' GC does not necessarily mean that all unreferenced memory has been returned already IF it was just completing a previous GC. It is not guaranteed that a GC really needs just 'steps' calls to complete. END Collector.