Mercurial > projects > ldc

comparison druntime/src/gc/basic/gcbits.d @ 759:d3eb054172f9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }