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