rt/gc/cdgc/bits.d

   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 rt.gc.cdgc.bits;
  28
  29 import cstdlib = tango.stdc.stdlib;
  30 import cstring = tango.stdc.string;
  31
  32 private extern (C) void onOutOfMemoryError();
  33
  34
  35 version (DigitalMars)
  36 {
  37     version = bitops;
  38     import std.intrinsic;
  39 }
  40 else version (GNU)
  41 {
  42     // use the unoptimized version
  43 }
  44 else version(LDC)
  45 {
  46     // ditto
  47 }
  48 else version (D_InlineAsm_X86)
  49 {
  50     version = Asm86;
  51 }
  52
  53 struct GCBits
  54 {
  55     const int BITS_PER_WORD = 32;
  56     const int BITS_SHIFT = 5;
  57     const int BITS_MASK = 31;
  58
  59     uint*  data = null;
  60     size_t nwords = 0;    // allocated words in data[] excluding sentinals
  61     size_t nbits = 0;     // number of bits in data[] excluding sentinals
  62
  63     void Dtor()
  64     {
  65         // Even when free() can be called with a null pointer, the extra call
  66         // might be significant. On hard GC benchmarks making the test for null
  67         // here (i.e. not making the call) can reduce the GC time by almost
  68         // ~5%.
  69         if (data)
  70         {
  71             cstdlib.free(data);
  72             data = null;
  73         }
  74     }
  75
  76     invariant
  77     {
  78         if (data)
  79         {
  80             assert(nwords * data[0].sizeof * 8 >= nbits);
  81         }
  82     }
  83
  84     void alloc(size_t nbits)
  85     {
  86         this.nbits = nbits;
  87         nwords = (nbits + (BITS_PER_WORD - 1)) >> BITS_SHIFT;
  88         data = cast(uint*)cstdlib.calloc(nwords + 2, uint.sizeof);
  89         if (!data)
  90             onOutOfMemoryError();
  91     }
  92
  93     uint test(size_t i)
  94     in
  95     {
  96         assert(i < nbits);
  97     }
  98     body
  99     {
 100         //return (cast(bit *)(data + 1))[i];
 101         return data[1 + (i >> BITS_SHIFT)] & (1 << (i & BITS_MASK));
 102     }
 103
 104     void set(size_t i)
 105     in
 106     {
 107         assert(i < nbits);
 108     }
 109     body
 110     {
 111         //(cast(bit *)(data + 1))[i] = 1;
 112         data[1 + (i >> BITS_SHIFT)] |= (1 << (i & BITS_MASK));
 113     }
 114
 115     void clear(size_t i)
 116     in
 117     {
 118         assert(i < nbits);
 119     }
 120     body
 121     {
 122         //(cast(bit *)(data + 1))[i] = 0;
 123         data[1 + (i >> BITS_SHIFT)] &= ~(1 << (i & BITS_MASK));
 124     }
 125
 126     uint testClear(size_t i)
 127     {
 128         version (bitops)
 129         {
 130             return std.intrinsic.btr(data + 1, i);
 131         }
 132         else version (Asm86)
 133         {
 134             asm
 135             {
 136                 naked                   ;
 137                 mov     EAX,data[EAX]   ;
 138                 mov     ECX,i-4[ESP]    ;
 139                 btr     4[EAX],ECX      ;
 140                 sbb     EAX,EAX         ;
 141                 ret     4               ;
 142             }
 143         }
 144         else
 145         {
 146             //result = (cast(bit *)(data + 1))[i];
 147             //(cast(bit *)(data + 1))[i] = 0;
 148
 149             uint* p = &data[1 + (i >> BITS_SHIFT)];
 150             uint  mask = (1 << (i & BITS_MASK));
 151             uint result = *p & mask;
 152             *p &= ~mask;
 153             return result;
 154         }
 155     }
 156
 157     void zero()
 158     {
 159         version(MEMCPY_NON_SIG_SAFE) {
 160             uint * d1=data+1,dEnd=d1+nwords;
 161             for (;d1!=dEnd;++d1)
 162                 *d1=0u;
 163         } else {
 164             cstring.memset(data + 1, 0, nwords * uint.sizeof);
 165         }
 166     }
 167
 168     void copy(GCBits *f)
 169     in
 170     {
 171         assert(nwords == f.nwords);
 172     }
 173     body
 174     {
 175         version(MEMCPY_NON_SIG_SAFE) {
 176             uint * d1=data+1,d2=f.data+1,dEnd=d1+nwords;
 177             for (;d1!=dEnd;++d1,++d2)
 178                 *d1=*d2;
 179         } else {
 180             cstring.memcpy(data + 1, f.data + 1, nwords * uint.sizeof);
 181         }
 182     }
 183
 184     uint* base()
 185     in
 186     {
 187         assert(data);
 188     }
 189     body
 190     {
 191         return data + 1;
 192     }
 193 }
 194
 195 unittest
 196 {
 197     GCBits b;
 198
 199     b.alloc(786);
 200     assert(b.test(123) == 0);
 201     assert(b.testClear(123) == 0);
 202     b.set(123);
 203     assert(b.test(123) != 0);
 204     assert(b.testClear(123) != 0);
 205     assert(b.test(123) == 0);
 206
 207     b.set(785);
 208     b.set(0);
 209     assert(b.test(785) != 0);
 210     assert(b.test(0) != 0);
 211     b.zero();
 212     assert(b.test(785) == 0);
 213     assert(b.test(0) == 0);
 214
 215     GCBits b2;
 216     b2.alloc(786);
 217     b2.set(38);
 218     b.copy(&b2);
 219     assert(b.test(38) != 0);
 220     b2.Dtor();
 221
 222     b.Dtor();
 223 }
 224
 225
 226 // vim: set et sw=4 sts=4 :