/* 
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991, 1992 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←HEADERS←H
# define GC←HEADERS←H
typedef struct hblkhdr hdr;

# if CPP←WORDSZ != 32 && CPP←WORDSZ < 36
	--> Get a real machine.
# endif

/*
 * The 2 level tree data structure that is used to find block headers.
 * If there are more than 32 bits in a pointer, the top level is a hash
 * table.
 */

# if CPP←WORDSZ > 32
#   define HASH←TL
# endif

/* Define appropriate out-degrees for each of the two tree levels	*/
# define LOG←BOTTOM←SZ 10
# ifndef HASH←TL
#   define LOG←TOP←SZ (WORDSZ - LOG←BOTTOM←SZ - LOG←HBLKSIZE)
# else
#   define LOG←TOP←SZ 11
# endif
# define TOP←SZ (1 << LOG←TOP←SZ)
# define BOTTOM←SZ (1 << LOG←BOTTOM←SZ)

typedef struct bi {
    hdr * index[BOTTOM←SZ];
	/*
 	 * The bottom level index contains one of three kinds of values:
	 * 0 means we're not responsible for this block.
	 * 1 < (long)X <= MAX←JUMP means the block starts at least
	 *        X * HBLKSIZE bytes before the current address.
	 * A valid pointer points to a hdr structure. (The above can't be
	 * valid pointers due to the GET←MEM return convention.)
	 */
    struct bi * asc←link;	/* All indices are linked in	*/
    				/* ascending order.		*/
    word key;			/* high order address bits.	*/
# ifdef HASH←TL
    struct bi * hash←link;	/* Hash chain link.		*/
# endif
} bottom←index;

/* extern bottom←index GC←all←nils; - really part of GC←arrays */

/* extern bottom←index * GC←top←index []; - really part of GC←arrays */
				/* Each entry points to a bottom←index.	*/
				/* On a 32 bit machine, it points to 	*/
				/* the index for a set of high order	*/
				/* bits equal to the index.  For longer	*/
				/* addresses, we hash the high order	*/
				/* bits to compute the index in 	*/
				/* GC←top←index, and each entry points	*/
				/* to a hash chain.			*/
				/* The last entry in each chain is	*/
				/* GC←all←nils.				*/


# define MAX←JUMP (HBLKSIZE - 1)

# ifndef HASH←TL
#   define BI(p) (GC←top←index \
		[(word)(p) >> (LOG←BOTTOM←SZ + LOG←HBLKSIZE)])
#   define HDR(p) (BI(p)->index \
		[((word)(p) >> LOG←HBLKSIZE) & (BOTTOM←SZ - 1)])
#   define GET←BI(p, bottom←indx) (bottom←indx) = BI(p)
#   define GET←HDR(p, hhdr) (hhdr) = HDR(p)
#   define SET←HDR(p, hhdr) HDR(p) = (hhdr)
#   define GET←HDR←ADDR(p, ha) (ha) = &(HDR(p))
# else /* hash */
/*  Hash function for tree top level */
#   define TL←HASH(hi) ((hi) & (TOP←SZ - 1))
/*  Set bottom←indx to point to the bottom index for address p */
#   define GET←BI(p, bottom←indx) \
	{ \
	    register word hi = \
	        (word)(p) >> (LOG←BOTTOM←SZ + LOG←HBLKSIZE); \
	    register bottom←index * ←bi = GC←top←index[TL←HASH(hi)]; \
	    \
	    while (←bi -> key != hi && ←bi != &GC←all←nils) \
	    	←bi = ←bi -> hash←link; \
	    (bottom←indx) = ←bi; \
	}
#   define GET←HDR←ADDR(p, ha) \
	{ \
	    register bottom←index * bi; \
	    \
	    GET←BI(p, bi);	\
	    (ha) = &(bi->index[((unsigned long)(p)>>LOG←HBLKSIZE) \
	        	  	& (BOTTOM←SZ - 1)]); \
	}
#   define GET←HDR(p, hhdr) { register hdr ** ←ha; GET←HDR←ADDR(p, ←ha); \
			      (hhdr) = *←ha; }
#   define SET←HDR(p, hhdr) { register hdr ** ←ha; GET←HDR←ADDR(p, ←ha); \
			      *←ha = (hhdr); }
#   define HDR(p) GC←find←header(p)
# endif
			    
/* Is the result a forwarding address to someplace closer to the	*/
/* beginning of the block or NIL?					*/
# define IS←FORWARDING←ADDR←OR←NIL(hhdr) ((unsigned long) (hhdr) <= MAX←JUMP)

/* Get an HBLKSIZE aligned address closer to the beginning of the block */
/* h.  Assumes hhdr == HDR(h) and IS←FORWARDING←ADDR(hhdr).		*/
# define FORWARDED←ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr))
# endif /*  GC←HEADERS←H */