]>
Commit | Line | Data |
---|---|---|
73ffefd0 TT |
1 | /* |
2 | * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers | |
3 | * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved. | |
4 | * | |
5 | * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED | |
6 | * OR IMPLIED. ANY USE IS AT YOUR OWN RISK. | |
7 | * | |
8 | * Permission is hereby granted to use or copy this program | |
9 | * for any purpose, provided the above notices are retained on all copies. | |
10 | * Permission to modify the code and to distribute modified code is granted, | |
11 | * provided the above notices are retained, and a notice that the code was | |
12 | * modified is included with the above copyright notice. | |
13 | */ | |
14 | /* Boehm, July 11, 1995 11:54 am PDT */ | |
15 | # ifndef GC_HEADERS_H | |
16 | # define GC_HEADERS_H | |
17 | typedef struct hblkhdr hdr; | |
18 | ||
19 | # if CPP_WORDSZ != 32 && CPP_WORDSZ < 36 | |
20 | --> Get a real machine. | |
21 | # endif | |
22 | ||
23 | /* | |
24 | * The 2 level tree data structure that is used to find block headers. | |
25 | * If there are more than 32 bits in a pointer, the top level is a hash | |
26 | * table. | |
27 | */ | |
28 | ||
29 | # if CPP_WORDSZ > 32 | |
30 | # define HASH_TL | |
31 | # endif | |
32 | ||
33 | /* Define appropriate out-degrees for each of the two tree levels */ | |
34 | # ifdef SMALL_CONFIG | |
35 | # define LOG_BOTTOM_SZ 11 | |
36 | /* Keep top index size reasonable with smaller blocks. */ | |
37 | # else | |
38 | # define LOG_BOTTOM_SZ 10 | |
39 | # endif | |
40 | # ifndef HASH_TL | |
41 | # define LOG_TOP_SZ (WORDSZ - LOG_BOTTOM_SZ - LOG_HBLKSIZE) | |
42 | # else | |
43 | # define LOG_TOP_SZ 11 | |
44 | # endif | |
45 | # define TOP_SZ (1 << LOG_TOP_SZ) | |
46 | # define BOTTOM_SZ (1 << LOG_BOTTOM_SZ) | |
47 | ||
48 | typedef struct bi { | |
49 | hdr * index[BOTTOM_SZ]; | |
50 | /* | |
51 | * The bottom level index contains one of three kinds of values: | |
20bbd3cd TT |
52 | * 0 means we're not responsible for this block, |
53 | * or this is a block other than the first one in a free block. | |
73ffefd0 TT |
54 | * 1 < (long)X <= MAX_JUMP means the block starts at least |
55 | * X * HBLKSIZE bytes before the current address. | |
56 | * A valid pointer points to a hdr structure. (The above can't be | |
57 | * valid pointers due to the GET_MEM return convention.) | |
58 | */ | |
59 | struct bi * asc_link; /* All indices are linked in */ | |
20bbd3cd TT |
60 | /* ascending order... */ |
61 | struct bi * desc_link; /* ... and in descending order. */ | |
73ffefd0 TT |
62 | word key; /* high order address bits. */ |
63 | # ifdef HASH_TL | |
64 | struct bi * hash_link; /* Hash chain link. */ | |
65 | # endif | |
66 | } bottom_index; | |
67 | ||
68 | /* extern bottom_index GC_all_nils; - really part of GC_arrays */ | |
69 | ||
70 | /* extern bottom_index * GC_top_index []; - really part of GC_arrays */ | |
71 | /* Each entry points to a bottom_index. */ | |
72 | /* On a 32 bit machine, it points to */ | |
73 | /* the index for a set of high order */ | |
74 | /* bits equal to the index. For longer */ | |
75 | /* addresses, we hash the high order */ | |
76 | /* bits to compute the index in */ | |
77 | /* GC_top_index, and each entry points */ | |
78 | /* to a hash chain. */ | |
79 | /* The last entry in each chain is */ | |
80 | /* GC_all_nils. */ | |
81 | ||
82 | ||
83 | # define MAX_JUMP (HBLKSIZE - 1) | |
84 | ||
85 | # define HDR_FROM_BI(bi, p) \ | |
86 | ((bi)->index[((word)(p) >> LOG_HBLKSIZE) & (BOTTOM_SZ - 1)]) | |
87 | # ifndef HASH_TL | |
88 | # define BI(p) (GC_top_index \ | |
89 | [(word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE)]) | |
90 | # define HDR_INNER(p) HDR_FROM_BI(BI(p),p) | |
91 | # ifdef SMALL_CONFIG | |
92 | # define HDR(p) GC_find_header((ptr_t)(p)) | |
93 | # else | |
94 | # define HDR(p) HDR_INNER(p) | |
95 | # endif | |
96 | # define GET_BI(p, bottom_indx) (bottom_indx) = BI(p) | |
97 | # define GET_HDR(p, hhdr) (hhdr) = HDR(p) | |
98 | # define SET_HDR(p, hhdr) HDR_INNER(p) = (hhdr) | |
99 | # define GET_HDR_ADDR(p, ha) (ha) = &(HDR_INNER(p)) | |
100 | # else /* hash */ | |
101 | /* Hash function for tree top level */ | |
102 | # define TL_HASH(hi) ((hi) & (TOP_SZ - 1)) | |
103 | /* Set bottom_indx to point to the bottom index for address p */ | |
104 | # define GET_BI(p, bottom_indx) \ | |
105 | { \ | |
106 | register word hi = \ | |
107 | (word)(p) >> (LOG_BOTTOM_SZ + LOG_HBLKSIZE); \ | |
108 | register bottom_index * _bi = GC_top_index[TL_HASH(hi)]; \ | |
109 | \ | |
110 | while (_bi -> key != hi && _bi != GC_all_nils) \ | |
111 | _bi = _bi -> hash_link; \ | |
112 | (bottom_indx) = _bi; \ | |
113 | } | |
114 | # define GET_HDR_ADDR(p, ha) \ | |
115 | { \ | |
116 | register bottom_index * bi; \ | |
117 | \ | |
118 | GET_BI(p, bi); \ | |
119 | (ha) = &(HDR_FROM_BI(bi, p)); \ | |
120 | } | |
121 | # define GET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \ | |
122 | (hhdr) = *_ha; } | |
123 | # define SET_HDR(p, hhdr) { register hdr ** _ha; GET_HDR_ADDR(p, _ha); \ | |
124 | *_ha = (hhdr); } | |
125 | # define HDR(p) GC_find_header((ptr_t)(p)) | |
126 | # endif | |
127 | ||
128 | /* Is the result a forwarding address to someplace closer to the */ | |
129 | /* beginning of the block or NIL? */ | |
130 | # define IS_FORWARDING_ADDR_OR_NIL(hhdr) ((unsigned long) (hhdr) <= MAX_JUMP) | |
131 | ||
132 | /* Get an HBLKSIZE aligned address closer to the beginning of the block */ | |
133 | /* h. Assumes hhdr == HDR(h) and IS_FORWARDING_ADDR(hhdr). */ | |
134 | # define FORWARDED_ADDR(h, hhdr) ((struct hblk *)(h) - (unsigned long)(hhdr)) | |
135 | # endif /* GC_HEADERS_H */ |