libphobos/src/std/internal/scopebuffer.d

   1 /*
   2  * Copyright: 2014 by Digital Mars
   3  * License: $(LINK2 http://boost.org/LICENSE_1_0.txt, Boost License 1.0).
   4  * Authors: Walter Bright
   5  * Source: $(PHOBOSSRC std/internal/_scopebuffer.d)
   6  */
   7
   8 module std.internal.scopebuffer;
   9
  10
  11 //debug=ScopeBuffer;
  12
  13 import core.stdc.stdlib : realloc;
  14 import std.traits;
  15
  16 /**************************************
  17  * ScopeBuffer encapsulates using a local array as a temporary buffer.
  18  * It is initialized with a local array that should be large enough for
  19  * most uses. If the need exceeds that size, ScopeBuffer will reallocate
  20  * the data using its `realloc` function.
  21  *
  22  * ScopeBuffer cannot contain more than `(uint.max-16)/2` elements.
  23  *
  24  * ScopeBuffer is an Output Range.
  25  *
  26  * Since ScopeBuffer may store elements of type `T` in `malloc`'d memory,
  27  * those elements are not scanned when the GC collects. This can cause
  28  * memory corruption. Do not use ScopeBuffer when elements of type `T` point
  29  * to the GC heap, except when a `realloc` function is provided which supports this.
  30  *
  31  * Example:
  32 ---
  33 import core.stdc.stdio;
  34 import std.internal.scopebuffer;
  35 void main()
  36 {
  37     char[2] buf = void;
  38     auto textbuf = ScopeBuffer!char(buf);
  39     scope(exit) textbuf.free(); // necessary for cleanup
  40
  41     // Put characters and strings into textbuf, verify they got there
  42     textbuf.put('a');
  43     textbuf.put('x');
  44     textbuf.put("abc");
  45     assert(textbuf.length == 5);
  46     assert(textbuf[1 .. 3] == "xa");
  47     assert(textbuf[3] == 'b');
  48
  49     // Can shrink it
  50     textbuf.length = 3;
  51     assert(textbuf[0 .. textbuf.length] == "axa");
  52     assert(textbuf[textbuf.length - 1] == 'a');
  53     assert(textbuf[1 .. 3] == "xa");
  54
  55     textbuf.put('z');
  56     assert(textbuf[] == "axaz");
  57
  58     // Can shrink it to 0 size, and reuse same memory
  59     textbuf.length = 0;
  60 }
  61 ---
  62  * It is invalid to access ScopeBuffer's contents when ScopeBuffer goes out of scope.
  63  * Hence, copying the contents are necessary to keep them around:
  64 ---
  65 import std.internal.scopebuffer;
  66 string cat(string s1, string s2)
  67 {
  68     char[10] tmpbuf = void;
  69     auto textbuf = ScopeBuffer!char(tmpbuf);
  70     scope(exit) textbuf.free();
  71     textbuf.put(s1);
  72     textbuf.put(s2);
  73     textbuf.put("even more");
  74     return textbuf[].idup;
  75 }
  76 ---
  77  * ScopeBuffer is intended for high performance usages in $(D @system) and $(D @trusted) code.
  78  * It is designed to fit into two 64 bit registers, again for high performance use.
  79  * If used incorrectly, memory leaks and corruption can result. Be sure to use
  80  * $(D scope(exit) textbuf.free();) for proper cleanup, and do not refer to a ScopeBuffer
  81  * instance's contents after $(D ScopeBuffer.free()) has been called.
  82  *
  83  * The `realloc` parameter defaults to C's `realloc()`. Another can be supplied to override it.
  84  *
  85  * ScopeBuffer instances may be copied, as in:
  86 ---
  87 textbuf = doSomething(textbuf, args);
  88 ---
  89  * which can be very efficent, but these must be regarded as a move rather than a copy.
  90  * Additionally, the code between passing and returning the instance must not throw
  91  * exceptions, otherwise when `ScopeBuffer.free()` is called, memory may get corrupted.
  92  */
  93
  94 @system
  95 struct ScopeBuffer(T, alias realloc = /*core.stdc.stdlib*/.realloc)
  96 if (isAssignable!T &&
  97     !hasElaborateDestructor!T &&
  98     !hasElaborateCopyConstructor!T &&
  99     !hasElaborateAssign!T)
 100 {
 101     import core.exception : onOutOfMemoryError;
 102     import core.stdc.string : memcpy;
 103
 104
 105     /**************************
 106      * Initialize with buf to use as scratch buffer space.
 107      * Params:
 108      *  buf = Scratch buffer space, must have length that is even
 109      * Example:
 110      * ---
 111      * ubyte[10] tmpbuf = void;
 112      * auto sbuf = ScopeBuffer!ubyte(tmpbuf);
 113      * ---
 114      * Note:
 115      * If buf was created by the same `realloc` passed as a parameter
 116      * to `ScopeBuffer`, then the contents of `ScopeBuffer` can be extracted without needing
 117      * to copy them, and `ScopeBuffer.free()` will not need to be called.
 118      */
 119     this(T[] buf)
 120         in
 121         {
 122             assert(!(buf.length & wasResized));    // assure even length of scratch buffer space
 123             assert(buf.length <= uint.max);     // because we cast to uint later
 124         }
 125     body
 126     {
 127         this.buf = buf.ptr;
 128         this.bufLen = cast(uint) buf.length;
 129     }
 130
 131     @system unittest
 132     {
 133         ubyte[10] tmpbuf = void;
 134         auto sbuf = ScopeBuffer!ubyte(tmpbuf);
 135     }
 136
 137     /**************************
 138      * Releases any memory used.
 139      * This will invalidate any references returned by the `[]` operator.
 140      * A destructor is not used, because that would make it not POD
 141      * (Plain Old Data) and it could not be placed in registers.
 142      */
 143     void free()
 144     {
 145         debug(ScopeBuffer) buf[0 .. bufLen] = 0;
 146         if (bufLen & wasResized)
 147             realloc(buf, 0);
 148         buf = null;
 149         bufLen = 0;
 150         used = 0;
 151     }
 152
 153     /************************
 154      * Append element c to the buffer.
 155      * This member function makes `ScopeBuffer` an Output Range.
 156      */
 157     void put(T c)
 158     {
 159         /* j will get enregistered, while used will not because resize() may change used
 160          */
 161         const j = used;
 162         if (j == bufLen)
 163         {
 164             assert(j <= (uint.max - 16) / 2);
 165             resize(j * 2 + 16);
 166         }
 167         buf[j] = c;
 168         used = j + 1;
 169     }
 170
 171     /************************
 172      * Append array s to the buffer.
 173      *
 174      * If $(D const(T)) can be converted to $(D T), then put will accept
 175      * $(D const(T)[]) as input. It will accept a $(D T[]) otherwise.
 176      */
 177     package alias CT = Select!(is(const(T) : T), const(T), T);
 178     /// ditto
 179     void put(CT[] s)
 180     {
 181         const newlen = used + s.length;
 182         assert((cast(ulong) used + s.length) <= uint.max);
 183         const len = bufLen;
 184         if (newlen > len)
 185         {
 186             assert(len <= uint.max / 2);
 187             resize(newlen <= len * 2 ? len * 2 : newlen);
 188         }
 189         buf[used .. newlen] = s[];
 190         used = cast(uint) newlen;
 191     }
 192
 193     /******
 194      * Returns:
 195      *  A slice into the temporary buffer.
 196      * Warning:
 197      *  The result is only valid until the next `put()` or `ScopeBuffer` goes out of scope.
 198      */
 199     @system inout(T)[] opSlice(size_t lower, size_t upper) inout
 200         in
 201         {
 202             assert(lower <= bufLen);
 203             assert(upper <= bufLen);
 204             assert(lower <= upper);
 205         }
 206     body
 207     {
 208         return buf[lower .. upper];
 209     }
 210
 211     /// ditto
 212     @system inout(T)[] opSlice() inout
 213     {
 214         assert(used <= bufLen);
 215         return buf[0 .. used];
 216     }
 217
 218     /*******
 219      * Returns:
 220      *  The element at index i.
 221      */
 222     ref inout(T) opIndex(size_t i) inout
 223     {
 224         assert(i < bufLen);
 225         return buf[i];
 226     }
 227
 228     /***
 229      * Returns:
 230      *  The number of elements in the `ScopeBuffer`.
 231      */
 232     @property size_t length() const
 233     {
 234         return used;
 235     }
 236
 237     /***
 238      * Used to shrink the length of the buffer,
 239      * typically to `0` so the buffer can be reused.
 240      * Cannot be used to extend the length of the buffer.
 241      */
 242     @property void length(size_t i)
 243         in
 244         {
 245             assert(i <= this.used);
 246         }
 247     body
 248     {
 249         this.used = cast(uint) i;
 250     }
 251
 252     alias opDollar = length;
 253
 254   private:
 255     T* buf;
 256     // Using uint instead of size_t so the struct fits in 2 registers in 64 bit code
 257     uint bufLen;
 258     enum wasResized = 1;         // this bit is set in bufLen if we control the memory
 259     uint used;
 260
 261     void resize(size_t newsize)
 262         in
 263         {
 264             assert(newsize <= uint.max);
 265         }
 266     body
 267     {
 268         //writefln("%s: oldsize %s newsize %s", id, buf.length, newsize);
 269         newsize |= wasResized;
 270         void *newBuf = realloc((bufLen & wasResized) ? buf : null, newsize * T.sizeof);
 271         if (!newBuf)
 272             onOutOfMemoryError();
 273         if (!(bufLen & wasResized))
 274         {
 275             memcpy(newBuf, buf, used * T.sizeof);
 276             debug(ScopeBuffer) buf[0 .. bufLen] = 0;
 277         }
 278         buf = cast(T*) newBuf;
 279         bufLen = cast(uint) newsize;
 280
 281         /* This function is called only rarely,
 282          * inlining results in poorer register allocation.
 283          */
 284         version (DigitalMars)
 285             /* With dmd, a fake loop will prevent inlining.
 286              * Using a hack until a language enhancement is implemented.
 287              */
 288             while (1) { break; }
 289     }
 290 }
 291
 292 @system unittest
 293 {
 294     import core.stdc.stdio;
 295     import std.range;
 296
 297     char[2] tmpbuf = void;
 298     {
 299     // Exercise all the lines of code except for assert(0)'s
 300     auto textbuf = ScopeBuffer!char(tmpbuf);
 301     scope(exit) textbuf.free();
 302
 303     static assert(isOutputRange!(ScopeBuffer!char, char));
 304
 305     textbuf.put('a');
 306     textbuf.put('x');
 307     textbuf.put("abc");         // tickle put([])'s resize
 308     assert(textbuf.length == 5);
 309     assert(textbuf[1 .. 3] == "xa");
 310     assert(textbuf[3] == 'b');
 311
 312     textbuf.length = textbuf.length - 1;
 313     assert(textbuf[0 .. textbuf.length] == "axab");
 314
 315     textbuf.length = 3;
 316     assert(textbuf[0 .. textbuf.length] == "axa");
 317     assert(textbuf[textbuf.length - 1] == 'a');
 318     assert(textbuf[1 .. 3] == "xa");
 319
 320     textbuf.put(cast(dchar)'z');
 321     assert(textbuf[] == "axaz");
 322
 323     textbuf.length = 0;                 // reset for reuse
 324     assert(textbuf.length == 0);
 325
 326     foreach (char c; "asdf;lasdlfaklsdjfalksdjfa;lksdjflkajsfdasdfkja;sdlfj")
 327     {
 328         textbuf.put(c); // tickle put(c)'s resize
 329     }
 330     assert(textbuf[] == "asdf;lasdlfaklsdjfalksdjfa;lksdjflkajsfdasdfkja;sdlfj");
 331     } // run destructor on textbuf here
 332
 333 }
 334
 335 @system unittest
 336 {
 337     string cat(string s1, string s2)
 338     {
 339         char[10] tmpbuf = void;
 340         auto textbuf = ScopeBuffer!char(tmpbuf);
 341         scope(exit) textbuf.free();
 342         textbuf.put(s1);
 343         textbuf.put(s2);
 344         textbuf.put("even more");
 345         return textbuf[].idup;
 346     }
 347
 348     auto s = cat("hello", "betty");
 349     assert(s == "hellobettyeven more");
 350 }
 351
 352 // const
 353 @system unittest
 354 {
 355     char[10] tmpbuf = void;
 356     auto textbuf = ScopeBuffer!char(tmpbuf);
 357     scope(exit) textbuf.free();
 358     foreach (i; 0 .. 10) textbuf.put('w');
 359     const csb = textbuf;
 360     const elem = csb[3];
 361     const slice0 = csb[0 .. 5];
 362     const slice1 = csb[];
 363 }
 364
 365 /*********************************
 366  * Creates a `ScopeBuffer` instance using type deduction - see
 367  * $(LREF .ScopeBuffer.this) for details.
 368  * Params:
 369  *      tmpbuf = the initial buffer to use
 370  * Returns:
 371  *      An instance of `ScopeBuffer`.
 372  */
 373
 374 auto scopeBuffer(T)(T[] tmpbuf)
 375 {
 376     return ScopeBuffer!T(tmpbuf);
 377 }
 378
 379 ///
 380 @system unittest
 381 {
 382     ubyte[10] tmpbuf = void;
 383     auto sb = scopeBuffer(tmpbuf);
 384     scope(exit) sb.free();
 385 }
 386
 387 @system unittest
 388 {
 389     ScopeBuffer!(int*) b;
 390     int*[] s;
 391     b.put(s);
 392
 393     ScopeBuffer!char c;
 394     string s1;
 395     char[] s2;
 396     c.put(s1);
 397     c.put(s2);
 398 }