Mercurial > projects > ldc
comparison druntime/src/gc/basic/gcbits.d @ 759:d3eb054172f9
Added copy of druntime from DMD 2.020 modified for LDC.
author | Tomas Lindquist Olsen <tomas.l.olsen@gmail.com> |
---|---|
date | Tue, 11 Nov 2008 01:52:37 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
758:f04dde6e882c | 759:d3eb054172f9 |
---|---|
1 /** | |
2 * This module contains a specialized bitset implementation. | |
3 * | |
4 * Copyright: Copyright (C) 2005-2006 Digital Mars, www.digitalmars.com. | |
5 * All rights reserved. | |
6 * License: | |
7 * This software is provided 'as-is', without any express or implied | |
8 * warranty. In no event will the authors be held liable for any damages | |
9 * arising from the use of this software. | |
10 * | |
11 * Permission is granted to anyone to use this software for any purpose, | |
12 * including commercial applications, and to alter it and redistribute it | |
13 * freely, in both source and binary form, subject to the following | |
14 * restrictions: | |
15 * | |
16 * o The origin of this software must not be misrepresented; you must not | |
17 * claim that you wrote the original software. If you use this software | |
18 * in a product, an acknowledgment in the product documentation would be | |
19 * appreciated but is not required. | |
20 * o Altered source versions must be plainly marked as such, and must not | |
21 * be misrepresented as being the original software. | |
22 * o This notice may not be removed or altered from any source | |
23 * distribution. | |
24 * Authors: Walter Bright, David Friedman, Sean Kelly | |
25 */ | |
26 | |
27 module gc.gcbits; | |
28 | |
29 | |
30 private | |
31 { | |
32 import core.bitmanip; | |
33 import stdc.string; | |
34 import stdc.stdlib; | |
35 extern (C) void onOutOfMemoryError(); | |
36 } | |
37 | |
38 | |
39 version (DigitalMars) | |
40 { | |
41 version = bitops; | |
42 } | |
43 else version (GNU) | |
44 { | |
45 // use the unoptimized version | |
46 } | |
47 else version (D_InlineAsm_X86) | |
48 { | |
49 version = Asm86; | |
50 } | |
51 | |
52 struct GCBits | |
53 { | |
54 const int BITS_PER_WORD = 32; | |
55 const int BITS_SHIFT = 5; | |
56 const int BITS_MASK = 31; | |
57 | |
58 uint* data = null; | |
59 size_t nwords = 0; // allocated words in data[] excluding sentinals | |
60 size_t nbits = 0; // number of bits in data[] excluding sentinals | |
61 | |
62 void Dtor() | |
63 { | |
64 if (data) | |
65 { | |
66 free(data); | |
67 data = null; | |
68 } | |
69 } | |
70 | |
71 invariant() | |
72 { | |
73 if (data) | |
74 { | |
75 assert(nwords * data[0].sizeof * 8 >= nbits); | |
76 } | |
77 } | |
78 | |
79 void alloc(size_t nbits) | |
80 { | |
81 this.nbits = nbits; | |
82 nwords = (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT; | |
83 data = cast(uint*)calloc(nwords + 2, uint.sizeof); | |
84 if (!data) | |
85 onOutOfMemoryError(); | |
86 } | |
87 | |
88 uint test(size_t i) | |
89 in | |
90 { | |
91 assert(i < nbits); | |
92 } | |
93 body | |
94 { | |
95 //return (cast(bit *)(data + 1))[i]; | |
96 return data[1 + (i >> BITS_SHIFT)] & (1 << (i & BITS_MASK)); | |
97 } | |
98 | |
99 void set(size_t i) | |
100 in | |
101 { | |
102 assert(i < nbits); | |
103 } | |
104 body | |
105 { | |
106 //(cast(bit *)(data + 1))[i] = 1; | |
107 data[1 + (i >> BITS_SHIFT)] |= (1 << (i & BITS_MASK)); | |
108 } | |
109 | |
110 void clear(size_t i) | |
111 in | |
112 { | |
113 assert(i < nbits); | |
114 } | |
115 body | |
116 { | |
117 //(cast(bit *)(data + 1))[i] = 0; | |
118 data[1 + (i >> BITS_SHIFT)] &= ~(1 << (i & BITS_MASK)); | |
119 } | |
120 | |
121 uint testClear(size_t i) | |
122 { | |
123 version (bitops) | |
124 { | |
125 return std.intrinsic.btr(data + 1, i); | |
126 } | |
127 else version (Asm86) | |
128 { | |
129 asm | |
130 { | |
131 naked ; | |
132 mov EAX,data[EAX] ; | |
133 mov ECX,i-4[ESP] ; | |
134 btr 4[EAX],ECX ; | |
135 sbb EAX,EAX ; | |
136 ret 4 ; | |
137 } | |
138 } | |
139 else | |
140 { uint result; | |
141 | |
142 //result = (cast(bit *)(data + 1))[i]; | |
143 //(cast(bit *)(data + 1))[i] = 0; | |
144 | |
145 uint* p = &data[1 + (i >> BITS_SHIFT)]; | |
146 uint mask = (1 << (i & BITS_MASK)); | |
147 result = *p & mask; | |
148 *p &= ~mask; | |
149 return result; | |
150 } | |
151 } | |
152 | |
153 void zero() | |
154 { | |
155 memset(data + 1, 0, nwords * uint.sizeof); | |
156 } | |
157 | |
158 void copy(GCBits *f) | |
159 in | |
160 { | |
161 assert(nwords == f.nwords); | |
162 } | |
163 body | |
164 { | |
165 memcpy(data + 1, f.data + 1, nwords * uint.sizeof); | |
166 } | |
167 | |
168 uint* base() | |
169 in | |
170 { | |
171 assert(data); | |
172 } | |
173 body | |
174 { | |
175 return data + 1; | |
176 } | |
177 } | |
178 | |
179 unittest | |
180 { | |
181 GCBits b; | |
182 | |
183 b.alloc(786); | |
184 assert(b.test(123) == 0); | |
185 assert(b.testClear(123) == 0); | |
186 b.set(123); | |
187 assert(b.test(123) != 0); | |
188 assert(b.testClear(123) != 0); | |
189 assert(b.test(123) == 0); | |
190 | |
191 b.set(785); | |
192 b.set(0); | |
193 assert(b.test(785) != 0); | |
194 assert(b.test(0) != 0); | |
195 b.zero(); | |
196 assert(b.test(785) == 0); | |
197 assert(b.test(0) == 0); | |
198 | |
199 GCBits b2; | |
200 b2.alloc(786); | |
201 b2.set(38); | |
202 b.copy(&b2); | |
203 assert(b.test(38) != 0); | |
204 b2.Dtor(); | |
205 | |
206 b.Dtor(); | |
207 } |