Mercurial > projects > ldc

comparison druntime/src/gc/basic/gcbits.d @ 1458:e0b2d67cfe7c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added druntime (this should be removed once it works).
author Robert Clipsham <robert@octarineparrot.com>
date Tue, 02 Jun 2009 17:43:06 +0100
parents
children
comparison
equal deleted inserted replaced
1456:7b218ec1044f 1458:e0b2d67cfe7c
1 /**
2 * Contains a bitfield used by the GC.
3 *
4 * Copyright: Copyright Digital Mars 2005 - 2009.
5 * License: <a href="http://www.boost.org/LICENSE_1_0.txt>Boost License 1.0</a>.
6 * Authors: Walter Bright, David Friedman, Sean Kelly
7 *
8 * Copyright Digital Mars 2005 - 2009.
9 * Distributed under the Boost Software License, Version 1.0.
10 * (See accompanying file LICENSE_1_0.txt or copy at
11 * http://www.boost.org/LICENSE_1_0.txt)
12 */
13 module gc.gcbits;
14
15
16 private
17 {
18 import core.bitop;
19 import core.stdc.string;
20 import core.stdc.stdlib;
21 extern (C) void onOutOfMemoryError();
22 }
23
24
25 version (DigitalMars)
26 {
27 version = bitops;
28 }
29 else version (GNU)
30 {
31 // use the unoptimized version
32 }
33 else version (D_InlineAsm_X86)
34 {
35 version = Asm86;
36 }
37
38 struct GCBits
39 {
40 const int BITS_PER_WORD = 32;
41 const int BITS_SHIFT = 5;
42 const int BITS_MASK = 31;
43
44 uint* data = null;
45 size_t nwords = 0; // allocated words in data[] excluding sentinals
46 size_t nbits = 0; // number of bits in data[] excluding sentinals
47
48 void Dtor()
49 {
50 if (data)
51 {
52 free(data);
53 data = null;
54 }
55 }
56
57 invariant()
58 {
59 if (data)
60 {
61 assert(nwords * data[0].sizeof * 8 >= nbits);
62 }
63 }
64
65 void alloc(size_t nbits)
66 {
67 this.nbits = nbits;
68 nwords = (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT;
69 data = cast(uint*)calloc(nwords + 2, uint.sizeof);
70 if (!data)
71 onOutOfMemoryError();
72 }
73
74 uint test(size_t i)
75 in
76 {
77 assert(i < nbits);
78 }
79 body
80 {
81 //return (cast(bit *)(data + 1))[i];
82 return data[1 + (i >> BITS_SHIFT)] & (1 << (i & BITS_MASK));
83 }
84
85 void set(size_t i)
86 in
87 {
88 assert(i < nbits);
89 }
90 body
91 {
92 //(cast(bit *)(data + 1))[i] = 1;
93 data[1 + (i >> BITS_SHIFT)] |= (1 << (i & BITS_MASK));
94 }
95
96 void clear(size_t i)
97 in
98 {
99 assert(i < nbits);
100 }
101 body
102 {
103 //(cast(bit *)(data + 1))[i] = 0;
104 data[1 + (i >> BITS_SHIFT)] &= ~(1 << (i & BITS_MASK));
105 }
106
107 uint testClear(size_t i)
108 {
109 version (bitops)
110 {
111 return std.intrinsic.btr(data + 1, i);
112 }
113 else version (Asm86)
114 {
115 asm
116 {
117 naked ;
118 mov EAX,data[EAX] ;
119 mov ECX,i-4[ESP] ;
120 btr 4[EAX],ECX ;
121 sbb EAX,EAX ;
122 ret 4 ;
123 }
124 }
125 else
126 { uint result;
127
128 //result = (cast(bit *)(data + 1))[i];
129 //(cast(bit *)(data + 1))[i] = 0;
130
131 uint* p = &data[1 + (i >> BITS_SHIFT)];
132 uint mask = (1 << (i & BITS_MASK));
133 result = *p & mask;
134 *p &= ~mask;
135 return result;
136 }
137 }
138
139 void zero()
140 {
141 memset(data + 1, 0, nwords * uint.sizeof);
142 }
143
144 void copy(GCBits *f)
145 in
146 {
147 assert(nwords == f.nwords);
148 }
149 body
150 {
151 memcpy(data + 1, f.data + 1, nwords * uint.sizeof);
152 }
153
154 uint* base()
155 in
156 {
157 assert(data);
158 }
159 body
160 {
161 return data + 1;
162 }
163 }
164
165 unittest
166 {
167 GCBits b;
168
169 b.alloc(786);
170 assert(b.test(123) == 0);
171 assert(b.testClear(123) == 0);
172 b.set(123);
173 assert(b.test(123) != 0);
174 assert(b.testClear(123) != 0);
175 assert(b.test(123) == 0);
176
177 b.set(785);
178 b.set(0);
179 assert(b.test(785) != 0);
180 assert(b.test(0) != 0);
181 b.zero();
182 assert(b.test(785) == 0);
183 assert(b.test(0) == 0);
184
185 GCBits b2;
186 b2.alloc(786);
187 b2.set(38);
188 b.copy(&b2);
189 assert(b.test(38) != 0);
190 b2.Dtor();
191
192 b.Dtor();
193 }