/* 
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991 by Xerox Corporation.  All rights reserved.
 *
 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
 *
 * Permission is hereby granted to copy this garbage collector for any purpose,
 * provided the above notices are retained on all copies.
 */
 
#ifndef GC←H

# define GC←H

# include <stddef.h>

/* Define word and signed←word to be unsigned and signed types of the 	*/
/* size as char * or void *.  There seems to be no way to do this	*/
/* even semi-portably.  The following is probably no better/worse 	*/
/* than almost anything else.						*/
/* The ANSI standard suggests that size←t and ptr←diff←t might be 	*/
/* better choices.  But those appear to have incorrect definitions	*/
/* on may systems.  Notably "typedef int size←t" seems to be both	*/
/* frequent and WRONG.							*/
typedef unsigned long word;
typedef long signed←word;

/* Public read-only variables */

extern word GC←heapsize;       /* Heap size in bytes */

extern word GC←gc←no;	/* Counter incremented per collection.  	*/
			/* Includes empty GCs at startup.		*/

/* Public R/W variables */

extern int GC←dont←gc;	/* Dont collect unless explicitly requested, e.g. */
			/* beacuse it's not safe.			  */

extern int GC←dont←expand;
			/* Dont expand heap unless explicitly requested */
			/* or forced to.				*/
			
extern word GC←non←gc←bytes;
			/* Bytes not considered candidates for collection. */
			/* Used only to control scheduling of collections. */

extern word GC←free←space←divisor;
			/* We try to make sure that we allocate at 	*/
			/* least N/GC←free←space←divisor bytes between	*/
			/* collections, where N is the heap size plus	*/
			/* a rough estimate of the root set size.	*/
			/* Initially, GC←free←space←divisor = 4.	*/
			/* Increasing its value will use less space	*/
			/* but more collection time.  Decreasing it	*/
			/* will appreciably decrease collection time	*/
			/* at the expens of space.			*/
			/* GC←free←space←divisor = 1 will effectively	*/
			/* disable collections.				*/
			
/* Public procedures */
/*
 * general purpose allocation routines, with roughly malloc calling conv.
 * The atomic versions promise that no relevant pointers are contained
 * in the object.  The nonatomic version guarantees that the new object
 * is cleared.
 */
# ifdef ←←STDC←←
  extern void * GC←malloc(size←t size←in←bytes);
  extern void * GC←malloc←atomic(size←t size←in←bytes);
# else
  extern char * GC←malloc(/* size←in←bytes */);
  extern char * GC←malloc←atomic(/* size←in←bytes */);
# endif

/* Explicitly deallocate an object.  Dangerous if used incorrectly.     */
/* Requires a pointer to the base of an object.				*/
# ifdef ←←STDC←←
  extern void GC←free(void * object←addr);
# else
  extern void GC←free(/* object←addr */);
# endif

/* Return a pointer to the base (lowest address) of an object given	*/
/* a pointer to a location within the object.				*/
/* Return 0 if displaced←pointer doesn't point to within a valid	*/
/* object.								*/
# ifdef ←←STDC←←
  void * GC←base(void * displaced←pointer);
# else
  char * GC←base(/* char * displaced←pointer */);
# endif

/* Given a pointer to the base of an object, return its size in bytes.	*/
/* The returned size may be slightly larger than what was originally	*/
/* requested.								*/
# ifdef ←←STDC←←
  size←t GC←size(void * object←addr);
# else
  size←t GC←size(/* char * object←addr */);
# endif

/* For compatibility with C library.  This is occasionally faster than	*/
/* a malloc followed by a bcopy.  But if you rely on that, either here	*/
/* or with the standard C library, your code is broken.  In my		*/
/* opinion, it shouldn't have been invented, but now we're stuck. -HB	*/
# ifdef ←←STDC←←
    extern void * GC←realloc(void * old←object, size←t new←size←in←bytes);
# else
    extern char * GC←realloc(/* old←object, new←size←in←bytes */);
# endif


/* Explicitly increase the heap size.	*/
/* Returns 0 on failure, 1 on success.  */
extern int GC←expand←hp(/* number←of←4K←blocks */);

/* Clear the set of root segments */
extern void GC←clear←roots();

/* Add a root segment */
extern void GC←add←roots(/* low←address, high←address←plus←1 */);

/* Add a displacement to the set of those considered valid by the	*/
/* collector.  GC←register←displacement(n) means that if p was returned */
/* by GC←malloc, then (char *)p + n will be considered to be a valid	*/
/* pointer to n.  N must be small and less than the size of p.		*/
/* (All pointers to the interior of objects from the stack are		*/
/* considered valid in any case.  This applies to heap objects and	*/
/* static data.)							*/
/* Preferably, this should be called before any other GC procedures.	*/
/* Calling it later adds to the probability of excess memory		*/
/* retention.								*/
void GC←register←displacement(/* n */);

/* Explicitly trigger a collection. 	*/
void GC←gcollect();

/* Debugging (annotated) allocation.  GC←gcollect will check 		*/
/* objects allocated in this way for overwrites, etc.			*/
# ifdef ←←STDC←←
  extern void * GC←debug←malloc(size←t size←in←bytes,
  				char * descr←string, int descr←int);
  extern void * GC←debug←malloc←atomic(size←t size←in←bytes,
  				       char * descr←string, int descr←int);
  extern void GC←debug←free(void * object←addr);
  extern void * GC←debug←realloc(void * old←object,
  			 	 size←t new←size←in←bytes,
  			 	 char * descr←string, int descr←int);
# else
  extern char * GC←debug←malloc(/* size←in←bytes, descr←string, descr←int */);
  extern char * GC←debug←malloc←atomic(/* size←in←bytes, descr←string,
  					  descr←int */);
  extern void GC←debug←free(/* object←addr */);
  extern char * GC←debug←realloc(/* old←object, new←size←in←bytes,
  			            descr←string, descr←int */);
# endif
# ifdef GC←DEBUG
#   define GC←MALLOC(sz) GC←debug←malloc(sz, ←←FILE←←, ←←LINE←←)
#   define GC←MALLOC←ATOMIC(sz) GC←debug←malloc←atomic(sz, ←←FILE←←, ←←LINE←←)
#   define GC←REALLOC(old, sz) GC←debug←realloc(old, sz, ←←FILE←←, \
							       ←←LINE←←)
#   define GC←FREE(p) GC←debug←free(p)
#   define GC←REGISTER←FINALIZER(p, f, d, of, od) \
	GC←register←finalizer(GC←base(p), GC←debug←invoke←finalizer, \
			      GC←make←closure(f,d), of, od)
# else
#   define GC←MALLOC(sz) GC←malloc(sz)
#   define GC←MALLOC←ATOMIC(sz) GC←malloc←atomic(sz)
#   define GC←REALLOC(old, sz) GC←realloc(old, sz)
#   define GC←FREE(p) GC←free(p)
#   define GC←REGISTER←FINALIZER(p, f, d, of, od) \
	GC←register←finalizer(p, f, d, of, od)
# endif

/* Finalization.  Some of these primitives are grossly unsafe.		*/
/* The idea is to make them both cheap, and sufficient to build		*/
/* a safer layer, closer to PCedar finalization.			*/
/* The interface represents my conclusions from a long discussion	*/
/* with Alan Demers, Dan Greene, Carl Hauser, Barry Hayes, 		*/
/* Christian Jacobi, and Russ Atkinson.  It's not perfect, and		*/
/* probably nobody else agrees with it.	    Hans-J. Boehm  3/13/92	*/
# ifdef ←←STDC←←
  typedef void (*GC←finalization←proc)(void * obj, void * client←data);
# else
  typedef void (*GC←finalization←proc)(/* void * obj, void * client←data */);
# endif
	
void GC←register←finalizer(/* void * obj,
			      GC←finalization←proc fn, void * cd,
			      GC←finalization←proc *ofn, void ** ocd */);
	/* When obj is no longer accessible, invoke		*/
	/* (*fn)(obj, cd).  If a and b are inaccessible, and	*/
	/* a points to b (after disappearing links have been	*/
	/* made to disappear), then only a will be		*/
	/* finalized.  (If this does not create any new		*/
	/* pointers to b, then b will be finalized after the	*/
	/* next collection.)  Any finalizable object that	*/
	/* is reachable from itself by following one or more	*/
	/* pointers will not be finalized (or collected).	*/
	/* Thus cycles involving finalizable objects should	*/
	/* be avoided, or broken by disappearing links.		*/
	/* fn is invoked with the allocation lock held.  It may */
	/* not allocate.  (Any storage it might need		*/
	/* should be preallocated and passed as part of cd.) 	*/
	/* fn should terminate as quickly as possible, and	*/
	/* defer extended computation.				*/
	/* All but the last finalizer registered for an object  */
	/* is ignored.						*/
	/* Finalization may be removed by passing 0 as fn.	*/
	/* The old finalizer and client data are stored in	*/
	/* *ofn and *ocd.					*/ 
	/* Fn is never invoked on an accessible object,		*/
	/* provided hidden pointers are converted to real 	*/
	/* pointers only if the allocation lock is held, and	*/
	/* such conversions are not performed by finalization	*/
	/* routines.						*/

/* The following routine may be used to break cycles between	*/
/* finalizable objects, thus causing cyclic finalizable		*/
/* objects to be finalized in the cirrect order.  Standard	*/
/* use involves calling GC←register←disappearing←link(&p),	*/
/* where p is a pointer that is not followed by finalization	*/
/* code, and should not be considered in determining 		*/
/* finalization order.						*/ 
int GC←register←disappearing←link(/* void ** link */);
	/* Link should point to a field of a heap allocated 	*/
	/* object obj.  *link will be cleared when obj is	*/
	/* found to be inaccessible.  This happens BEFORE any	*/
	/* finalization code is invoked, and BEFORE any		*/
	/* decisions about finalization order are made.		*/
	/* This is useful in telling the finalizer that 	*/
	/* some pointers are not essential for proper		*/
	/* finalization.  This may avoid finalization cycles.	*/
	/* Note that obj may be resurrected by another		*/
	/* finalizer, and thus the clearing of *link may	*/
	/* be visible to non-finalization code.  		*/
	/* There's an argument that an arbitrary action should  */
	/* be allowed here, instead of just clearing a pointer. */
	/* But this causes problems if that action alters, or 	*/
	/* examines connectivity.				*/
	/* Returns 1 if link was already registered, 0		*/
	/* otherise.						*/
int GC←unregister←disappearing←link(/* void ** link */);
	/* Returns 0 if link was not actually registered.	*/

/* Auxiliary fns to make finalization work correctly with displaced	*/
/* pointers introduced by the debugging allocators.			*/
# ifdef ←←STDC←←
    void * GC←make←closure(GC←finalization←proc fn, void * data);
    void GC←debug←invoke←finalizer(void * obj, void * data);
# else
    char * GC←make←closure(/* GC←finalization←proc fn, char * data */);
    void GC←debug←invoke←finalizer(/* void * obj, void * data */);
# endif

	
/* The following is intended to be used by a higher level	*/
/* (e.g. cedar-like) finalization facility.  It is expected	*/
/* that finalization code will arrange for hidden pointers to	*/
/* disappear.  Otherwise objects can be accessed after they	*/
/* have been collected.						*/
# ifdef I←HIDE←POINTERS
#   ifdef ←←STDC←←
#     define HIDE←POINTER(p) (~(size←t)(p))
#     define REVEAL←POINTER(p) ((void *)(HIDE←POINTER(p)))
#   else
#     define HIDE←POINTER(p) (~(unsigned long)(p))
#     define REVEAL←POINTER(p) ((char *)(HIDE←POINTER(p)))
#   endif
    /* Converting a hidden pointer to a real pointer requires verifying	*/
    /* that the object still exists.  This involves acquiring the  	*/
    /* allocator lock to avoid a race with the collector.		*/
    typedef char * (*GC←fn←type)();
#   ifdef ←←STDC←←
        void * GC←call←with←alloc←lock(GC←fn←type fn, void * client←data);
#   else
        char * GC←call←with←alloc←lock(/* GC←fn←type fn, char * client←data */);
#   endif
# endif

#endif