DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Untracked file

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
/* 
 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
 * Copyright (c) 1991-1994 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 use or copy this program
 * for any purpose,  provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 */
/* Boehm, July 11, 1995 11:54 am PDT */
# 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	*/
# ifdef SMALL_CONFIG
#   define LOG_BOTTOM_SZ 11
	/* Keep top index size reasonable with smaller blocks. */
# else
#   define LOG_BOTTOM_SZ 10
# endif
# 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)

# define HDR_FROM_BI(bi, p) \
		((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)])
# ifndef HASH_TL
#   define BI(p) (GC_top_index \
		[(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)])
#   define HDR_INNER(p) HDR_FROM_BI(BI(p),p)
#   ifdef SMALL_CONFIG
#	define HDR(p) GC_find_header((ptr_t)(p))
#   else
#	define HDR(p) HDR_INNER(p)
#   endif
#   define GET_BI(p, bottom_indx) (bottom_indx) = BI(p)
#   define GET_HDR(p, hhdr) (hhdr) = HDR(p)
#   define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr)
#   define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(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) = &(HDR_FROM_BI(bi, p)); \
	}
#   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((ptr_t)(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 */