Mercurial > projects > ldc

comparison lphobos/gc/gcbits.d @ 109:5ab8e92611f9 trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r113] Added initial support for associative arrays (AAs). Fixed some problems with the string runtime support functions. Fixed initialization of array of structs. Fixed slice assignment where LHS is slice but RHS is dynamic array. Fixed problems with result of assignment expressions. Fixed foreach problems with key type mismatches.
author lindquist
date Wed, 21 Nov 2007 04:13:15 +0100
parents
children 373489eeaf90
comparison
equal deleted inserted replaced
108:288fe1029e1f 109:5ab8e92611f9
1
2 // Copyright (C) 2001-2002 by Digital Mars
3 // All Rights Reserved
4 // www.digitalmars.com
5 // Written by Walter Bright
6
7 import std.c.string;
8 import std.c.stdlib;
9 import std.outofmemory;
10 import std.intrinsic;
11
12 //version = Asm86;
13 version = bitops;
14
15 struct GCBits
16 {
17 const int BITS_PER_WORD = 32;
18 const int BITS_SHIFT = 5;
19 const int BITS_MASK = 31;
20
21 uint *data = null;
22 uint nwords = 0; // allocated words in data[] excluding sentinals
23 uint nbits = 0; // number of bits in data[] excluding sentinals
24
25 void Dtor()
26 {
27 if (data)
28 {
29 free(data);
30 data = null;
31 }
32 }
33
34 invariant
35 {
36 if (data)
37 {
38 assert(nwords * data[0].sizeof * 8 >= nbits);
39 }
40 }
41
42 void alloc(uint nbits)
43 {
44 this.nbits = nbits;
45 nwords = (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT;
46 data = cast(uint *)calloc(nwords + 2, uint.sizeof);
47 if (!data)
48 _d_OutOfMemory();
49 }
50
51 uint test(uint i)
52 in
53 {
54 assert(i < nbits);
55 }
56 body
57 {
58 //return (cast(bit *)(data + 1))[i];
59 return data[1 + (i >> BITS_SHIFT)] & (1 << (i & BITS_MASK));
60 }
61
62 void set(uint i)
63 in
64 {
65 assert(i < nbits);
66 }
67 body
68 {
69 //(cast(bit *)(data + 1))[i] = 1;
70 data[1 + (i >> BITS_SHIFT)] |= (1 << (i & BITS_MASK));
71 }
72
73 void clear(uint i)
74 in
75 {
76 assert(i < nbits);
77 }
78 body
79 {
80 //(cast(bit *)(data + 1))[i] = 0;
81 data[1 + (i >> BITS_SHIFT)] &= ~(1 << (i & BITS_MASK));
82 }
83
84 uint testClear(uint i)
85 {
86 version (bitops)
87 {
88 return std.intrinsic.btr(data + 1, i);
89 }
90 else version (Asm86)
91 {
92 asm
93 {
94 naked ;
95 mov EAX,data[EAX] ;
96 mov ECX,i-4[ESP] ;
97 btr 4[EAX],ECX ;
98 sbb EAX,EAX ;
99 ret 4 ;
100 }
101 }
102 else
103 { uint result;
104
105 //result = (cast(bit *)(data + 1))[i];
106 //(cast(bit *)(data + 1))[i] = 0;
107
108 uint *p = &data[1 + (i >> BITS_SHIFT)];
109 uint mask = (1 << (i & BITS_MASK));
110 result = *p & mask;
111 *p &= ~mask;
112 return result;
113 }
114 }
115
116 void zero()
117 {
118 memset(data + 1, 0, nwords * uint.sizeof);
119 }
120
121 void copy(GCBits *f)
122 in
123 {
124 assert(nwords == f.nwords);
125 }
126 body
127 {
128 memcpy(data + 1, f.data + 1, nwords * uint.sizeof);
129 }
130
131 uint *base()
132 in
133 {
134 assert(data);
135 }
136 body
137 {
138 return data + 1;
139 }
140 }
141
142 unittest
143 {
144 GCBits b;
145
146 b.alloc(786);
147 assert(b.test(123) == 0);
148 assert(b.testClear(123) == 0);
149 b.set(123);
150 assert(b.test(123) != 0);
151 assert(b.testClear(123) != 0);
152 assert(b.test(123) == 0);
153
154 b.set(785);
155 b.set(0);
156 assert(b.test(785) != 0);
157 assert(b.test(0) != 0);
158 b.zero();
159 assert(b.test(785) == 0);
160 assert(b.test(0) == 0);
161
162 GCBits b2;
163 b2.alloc(786);
164 b2.set(38);
165 b.copy(&b2);
166 assert(b.test(38) != 0);
167 b2.Dtor();
168
169 b.Dtor();
170 }
171
172 /+
173 void main()
174 {
175 }
176 +/