Mercurial > projects > ldc

comparison tango/lib/gc/basic/gcbits.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children a168a2c3ea48
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
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
28 private import tango.core.BitManip;
29 private import tango.stdc.string;
30 private import tango.stdc.stdlib;
31 private extern (C) void onOutOfMemoryError();
32
33
34 version (DigitalMars)
35 {
36 version = bitops;
37 }
38 else version (GNU)
39 {
40 // use the unoptimized version
41 }
42 else version (D_InlineAsm_X86)
43 {
44 version = Asm86;
45 }
46
47 struct GCBits
48 {
49 const int BITS_PER_WORD = 32;
50 const int BITS_SHIFT = 5;
51 const int BITS_MASK = 31;
52
53 uint *data = null;
54 uint nwords = 0; // allocated words in data[] excluding sentinals
55 uint nbits = 0; // number of bits in data[] excluding sentinals
56
57 void Dtor()
58 {
59 if (data)
60 {
61 free(data);
62 data = null;
63 }
64 }
65
66 invariant
67 {
68 if (data)
69 {
70 assert(nwords * data[0].sizeof * 8 >= nbits);
71 }
72 }
73
74 void alloc(uint nbits)
75 {
76 this.nbits = nbits;
77 nwords = (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT;
78 data = cast(uint *)calloc(nwords + 2, uint.sizeof);
79 if (!data)
80 onOutOfMemoryError();
81 }
82
83 uint test(uint i)
84 in
85 {
86 assert(i < nbits);
87 }
88 body
89 {
90 //return (cast(bit *)(data + 1))[i];
91 return data[1 + (i >> BITS_SHIFT)] & (1 << (i & BITS_MASK));
92 }
93
94 void set(uint i)
95 in
96 {
97 assert(i < nbits);
98 }
99 body
100 {
101 //(cast(bit *)(data + 1))[i] = 1;
102 data[1 + (i >> BITS_SHIFT)] |= (1 << (i & BITS_MASK));
103 }
104
105 void clear(uint i)
106 in
107 {
108 assert(i < nbits);
109 }
110 body
111 {
112 //(cast(bit *)(data + 1))[i] = 0;
113 data[1 + (i >> BITS_SHIFT)] &= ~(1 << (i & BITS_MASK));
114 }
115
116 uint testClear(uint i)
117 {
118 version (bitops)
119 {
120 return std.intrinsic.btr(data + 1, i);
121 }
122 else version (Asm86)
123 {
124 asm
125 {
126 naked ;
127 mov EAX,data[EAX] ;
128 mov ECX,i-4[ESP] ;
129 btr 4[EAX],ECX ;
130 sbb EAX,EAX ;
131 ret 4 ;
132 }
133 }
134 else
135 { uint result;
136
137 //result = (cast(bit *)(data + 1))[i];
138 //(cast(bit *)(data + 1))[i] = 0;
139
140 uint *p = &data[1 + (i >> BITS_SHIFT)];
141 uint mask = (1 << (i & BITS_MASK));
142 result = *p & mask;
143 *p &= ~mask;
144 return result;
145 }
146 }
147
148 void zero()
149 {
150 memset(data + 1, 0, nwords * uint.sizeof);
151 }
152
153 void copy(GCBits *f)
154 in
155 {
156 assert(nwords == f.nwords);
157 }
158 body
159 {
160 memcpy(data + 1, f.data + 1, nwords * uint.sizeof);
161 }
162
163 uint *base()
164 in
165 {
166 assert(data);
167 }
168 body
169 {
170 return data + 1;
171 }
172 }
173
174 unittest
175 {
176 GCBits b;
177
178 b.alloc(786);
179 assert(b.test(123) == 0);
180 assert(b.testClear(123) == 0);
181 b.set(123);
182 assert(b.test(123) != 0);
183 assert(b.testClear(123) != 0);
184 assert(b.test(123) == 0);
185
186 b.set(785);
187 b.set(0);
188 assert(b.test(785) != 0);
189 assert(b.test(0) != 0);
190 b.zero();
191 assert(b.test(785) == 0);
192 assert(b.test(0) == 0);
193
194 GCBits b2;
195 b2.alloc(786);
196 b2.set(38);
197 b.copy(&b2);
198 assert(b.test(38) != 0);
199 b2.Dtor();
200
201 b.Dtor();
202 }