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