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