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