home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1998 #6 / amigamamagazinepolishissue1998.iso / coders / collector / collector.txt < prev    next >
Text File  |  1995-03-30  |  7KB  |  245 lines
  1. (* (* $VER: Collector 1.0 (10-Feb-94) Copyright © by Lars Düning *) *)
  2.  
  3. DEFINITION Collector;
  4. DEFINITION CollectorS;
  5.  
  6. ---------------------------------------------------------------------------
  7.  Allocation and garbage-collection of elemental objects.
  8.  
  9.  Copyright © 1993-1994 by Lars Düning  -  All rights reserved.
  10.  Permission granted for non-commercial use.
  11. ---------------------------------------------------------------------------
  12.  
  13. TYPE: various pointers
  14.  
  15.   ElementP  *= POINTER TO Element;
  16.   FreeDataP *= POINTER TO FreeData;
  17.  
  18.  
  19. TYPE: Base structure of an collectable element
  20.  
  21.   Element *= RECORD
  22.     next     : ElementP;  next element; NIL for unchained elements
  23.     prev     : ElementP;  previous element; or GC pass# of freelisting
  24.     ecType  -: SHORTINT;  type of this element ('*'-type in CollectorS)
  25.     ecFlags -: SHORTSET;  color and other flags
  26.   END;
  27.  
  28.  
  29. CONST: Element.ecFlags
  30.  
  31.   Black *= 0;  Color 'black', must be 1-White
  32.   White *= 1;  Color 'white', must be 1-Black
  33.   Grey  *= 2;  Color 'grey'
  34.   Dark  *= 5;  set for root elements which are already processed
  35.   Root  *= 6;  set for members of the root set
  36.   Base  *= 7;  Baseelement of a ring
  37.  
  38.  
  39. TYPE: A Freelist entry for one ecType
  40.  
  41.   FreeData *= STRUCT
  42.     list    -: ElementP;                 List of free elements
  43.     new     -: PROCEDURE () : ElementP;  Allocator procedure
  44.     root    -: BOOLEAN;                  Flag if these elements are 'Root'
  45.     max     -: LONGINT;                  Max number of elements to hold
  46.     nrList  -: LONGINT;                  Current number of held elements
  47.     nrReq   -: LONGINT;                  Total count of requests for a new Element
  48.     nrRecyc -: LONGINT;                  Count of Element requests served from the free list
  49.     nrFreed -: LONGINT;                  Total count of Element freed
  50.   END;
  51.  
  52.   FreeListP *= POINTER TO ARRAY OF FreeData;
  53.  
  54.  
  55. VAR
  56.  
  57.   black -: INTEGER;  Actual colors
  58.   white -: INTEGER;
  59.  
  60.   nrTypes -: SHORTINT;  Number of registered ecTypes
  61.  
  62.   freelist -: FreeListP;  All Freelists
  63.  
  64.   sweeping -: BOOLEAN;  GC state: false: marking, true: sweeping
  65.   gcRuns   -: LONGINT;  Count of GC runs
  66.   gcCalls  -: LONGINT;  Calls to GC() during this run
  67.  
  68.  
  69. VAR: And for my curiosity...
  70.  
  71.   gcReqT   -: LONGINT;  Total number of elements requested
  72.   gcFreeT  -: LONGINT;  Total number of elements freed by GC so far
  73.   gcExaT   -: LONGINT;  Total number of elements examinated by GC so far
  74.   gcCallsT -: LONGINT;  Total count of calls to GC()
  75.  
  76.   gcFree -: LONGINT;  Actual number of elements freed this GC-run
  77.   gcExa  -: LONGINT;  Actual number of elements examinated this GC-run
  78.  
  79.  
  80. METHOD (this : ElementP) mark *;
  81.  
  82.   Mark all elements which are referenced by this element as grey.
  83.  
  84.   Argument:
  85.     this: the referencing element.
  86.  
  87.   The element itself is marked by the collector.
  88.  
  89.  
  90. CONST: Returnvalues of this.free()
  91.  
  92.   keep    *= 0;
  93.   enlist  *= 1;
  94.   dispose *= 2;
  95.  
  96. METHOD (this : ElementP) free * () : INTEGER;
  97.  
  98.   Let an unreferenced element clean up itself.
  99.  
  100.   Argument:
  101.     this: the now unreferenced element.
  102.  
  103.   Result:
  104.     keep   : the element is still alive, keep it.
  105.     enlist : put the element into its freelist.
  106.     dispose: deallocate the element.
  107.  
  108.   The result determines the action done by the collector.
  109.  
  110.  
  111. PROCEDURE RegisterType * ( new    : PROCEDURE() : ElementP
  112.                          ; isRoot : BOOLEAN
  113.                          ; max    : LONGINT
  114.                          ) : SHORTINT;
  115.  
  116.   Register a new collectable type.
  117.  
  118.   Arguments:
  119.     new    : the procedure to allocate a record of that type.
  120.     isRoot : TRUE if these elements are to be members of the root set.
  121.     max    : the max number of records to hold in the freelist.
  122.  
  123.   Result:
  124.     The ecType number for the registered type.
  125.  
  126.  
  127. PROCEDURE New * (type : SHORTINT) : ElementP;
  128.  
  129.   Return an element of the given type.
  130.  
  131.   Arguments:
  132.     type   : the type number for the requested element.
  133.  
  134.   Result:
  135.     A pointer to the new element.
  136.  
  137.   The element is allocated either from the freelist, or using the 'new'
  138.   procedure. It is entangled into the collector lists, either in
  139.   the normalset, or if .root is TRUE, in the rootset.
  140.  
  141.  
  142. PROCEDURE Allocate * (type : SHORTINT) : ElementP;
  143.  
  144.   Return an element of the given type.
  145.  
  146.   Arguments:
  147.     type   : the type number for the requested element.
  148.  
  149.   Result:
  150.     A pointer to the new element.
  151.  
  152.   The element is allocated either from the freelist, or using the 'new'
  153.   procedure. It is NOT entangled into the collector lists.
  154.   Use it with care!
  155.  
  156.  
  157. PROCEDURE Free * (elem : ElementP; dealloc : BOOLEAN);
  158.  
  159.   Remove an element from the active ring.
  160.  
  161.   Arguments:
  162.     elem    : the element to remove.
  163.     dealloc : flag if the element should be deallocated.
  164.  
  165.   The element is removed from its ring (if any) and added to the freelist
  166.   of its type, unless 'dealloc' is false, then it is deallocated.
  167.  
  168.   Normally there is no need to call this function by hand!
  169.  
  170.  
  171. PROCEDURE ShortenLists * (age : LONGINT);
  172.  
  173.   Remove old elements from the freelists.
  174.  
  175.   Argument:
  176.     age : the age in GC runs an element needs to stay in the lists.
  177.  
  178.   Elements older than 'age' GC runs are deallocated; with an 'age' of 0
  179.   causing the deallocation of all elements.
  180.  
  181.  
  182. PROCEDURE Mark * (this : ElementP);
  183.  
  184.   Mark an element as grey.
  185.  
  186.   Argument:
  187.     this : the element to shade grey.
  188.  
  189.   The element is colored grey (meaning "referenced but unprocessed")
  190.   and enqueued into the 'grey' ring of its set.
  191.   Non-'white' elements are not recolored or requeued.
  192.   Processed 'dark' white rootset elements are just recolored.
  193.  
  194.   This function is to be called by the .mark()-methods during GC,
  195.   and by Check().
  196.  
  197.   When using CollectorS (and just then), inlining is strongly recommended.
  198.  
  199.  
  200. PROCEDURE Check * (this, elem : ElementP);
  201.  
  202.   Check and possibly recolor an element after referencing.
  203.  
  204.   Argument:
  205.     this : the element referencing 'elem'.
  206.     elem : the element to check.
  207.  
  208.   The element is colored grey (meaning "referenced but unprocessed")
  209.   and enqueued into the 'grey' ring of its set if it is referenced
  210.   by a non-white element 'this'.
  211.   Non-'white' elements are not recolored or requeued.
  212.   Processed 'dark' white rootset elements are just recolored.
  213.  
  214.   This function is to be called if 'elem' was just referenced
  215.   by 'this' element.
  216.  
  217.   When using CollectorS (and just then), inlining is strongly recommended.
  218.  
  219.  
  220. PROCEDURE GC * (steps : LONGINT) : BOOLEAN;
  221.  
  222.   Perform a garbage collection - one step of a full run.
  223.  
  224.   Argument:
  225.     steps : total number of steps (calls) the GC shall need.
  226.             A value < 2 enforces a completing/full run.
  227.  
  228.   Result:
  229.     TRUE if the GC is complete.
  230.  
  231.   Perform one step (or a completing/complete run) of the Mark-and-Sweep-GC
  232.   for the elements.
  233.   The procedure loops either over n elements or until the end of one run.
  234.   'n' is derived from the number of existing elements divided by the
  235.   given number of 'steps' to do.
  236.   If the GC is complete, a call to ShortenLists() should be done.
  237.  
  238.   Note that a 'complete' GC does not necessarily mean that all unreferenced
  239.   memory has been returned already IF it was just completing a previous GC.
  240.  
  241.   It is not guaranteed that a GC really needs just 'steps' calls to complete.
  242.  
  243.  
  244. END Collector.
  245.