Mercurial > projects > ldc
diff tango/lib/gc/basic/gcbits.d @ 132:1700239cab2e trunk
[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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tango/lib/gc/basic/gcbits.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,202 @@ +/** + * This module contains a specialized bitset implementation. + * + * Copyright: Copyright (C) 2005-2006 Digital Mars, www.digitalmars.com. + * All rights reserved. + * License: + * This software is provided 'as-is', without any express or implied + * warranty. In no event will the authors be held liable for any damages + * arising from the use of this software. + * + * Permission is granted to anyone to use this software for any purpose, + * including commercial applications, and to alter it and redistribute it + * freely, in both source and binary form, subject to the following + * restrictions: + * + * o The origin of this software must not be misrepresented; you must not + * claim that you wrote the original software. If you use this software + * in a product, an acknowledgment in the product documentation would be + * appreciated but is not required. + * o Altered source versions must be plainly marked as such, and must not + * be misrepresented as being the original software. + * o This notice may not be removed or altered from any source + * distribution. + * Authors: Walter Bright, David Friedman, Sean Kelly + */ + + +private import tango.core.BitManip; +private import tango.stdc.string; +private import tango.stdc.stdlib; +private extern (C) void onOutOfMemoryError(); + + +version (DigitalMars) +{ + version = bitops; +} +else version (GNU) +{ + // use the unoptimized version +} +else version (D_InlineAsm_X86) +{ + version = Asm86; +} + +struct GCBits +{ + const int BITS_PER_WORD = 32; + const int BITS_SHIFT = 5; + const int BITS_MASK = 31; + + uint *data = null; + uint nwords = 0; // allocated words in data[] excluding sentinals + uint nbits = 0; // number of bits in data[] excluding sentinals + + void Dtor() + { + if (data) + { + free(data); + data = null; + } + } + + invariant + { + if (data) + { + assert(nwords * data[0].sizeof * 8 >= nbits); + } + } + + void alloc(uint nbits) + { + this.nbits = nbits; + nwords = (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT; + data = cast(uint *)calloc(nwords + 2, uint.sizeof); + if (!data) + onOutOfMemoryError(); + } + + uint test(uint i) + in + { + assert(i < nbits); + } + body + { + //return (cast(bit *)(data + 1))[i]; + return data[1 + (i >> BITS_SHIFT)] & (1 << (i & BITS_MASK)); + } + + void set(uint i) + in + { + assert(i < nbits); + } + body + { + //(cast(bit *)(data + 1))[i] = 1; + data[1 + (i >> BITS_SHIFT)] |= (1 << (i & BITS_MASK)); + } + + void clear(uint i) + in + { + assert(i < nbits); + } + body + { + //(cast(bit *)(data + 1))[i] = 0; + data[1 + (i >> BITS_SHIFT)] &= ~(1 << (i & BITS_MASK)); + } + + uint testClear(uint i) + { + version (bitops) + { + return std.intrinsic.btr(data + 1, i); + } + else version (Asm86) + { + asm + { + naked ; + mov EAX,data[EAX] ; + mov ECX,i-4[ESP] ; + btr 4[EAX],ECX ; + sbb EAX,EAX ; + ret 4 ; + } + } + else + { uint result; + + //result = (cast(bit *)(data + 1))[i]; + //(cast(bit *)(data + 1))[i] = 0; + + uint *p = &data[1 + (i >> BITS_SHIFT)]; + uint mask = (1 << (i & BITS_MASK)); + result = *p & mask; + *p &= ~mask; + return result; + } + } + + void zero() + { + memset(data + 1, 0, nwords * uint.sizeof); + } + + void copy(GCBits *f) + in + { + assert(nwords == f.nwords); + } + body + { + memcpy(data + 1, f.data + 1, nwords * uint.sizeof); + } + + uint *base() + in + { + assert(data); + } + body + { + return data + 1; + } +} + +unittest +{ + GCBits b; + + b.alloc(786); + assert(b.test(123) == 0); + assert(b.testClear(123) == 0); + b.set(123); + assert(b.test(123) != 0); + assert(b.testClear(123) != 0); + assert(b.test(123) == 0); + + b.set(785); + b.set(0); + assert(b.test(785) != 0); + assert(b.test(0) != 0); + b.zero(); + assert(b.test(785) == 0); + assert(b.test(0) == 0); + + GCBits b2; + b2.alloc(786); + b2.set(38); + b.copy(&b2); + assert(b.test(38) != 0); + b2.Dtor(); + + b.Dtor(); +}