ssarray.d

   1 /*
   2  * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
   3  * Understanding is not required. Only obedience.
   4  *
   5  * This program is free software: you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation, either version 3 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program. If not, see <http://www.gnu.org/licenses/>.
  17  */
  18 module iv.ssarray /*is aliced*/;
  19
  20 version(aliced) {} else private alias usize = size_t;
  21
  22 //debug = debug_ssarray;
  23
  24
  25 /** Array implementation that doesn't fragment memory, and does no `realloc()`s.
  26  *
  27  * I.e. `SSArray` will never move its items on resizing.
  28  * Also, there is no need to "reserve" space in `SSArray`, it won't make your
  29  * code faster, 'cause total number of `malloc()`s will be the same.
  30  *
  31  * $(WARNING This completely ignores any postblits, dtors and GC anchoring!)
  32  */
  33 static struct SSArray(T, bool initNewElements=true, uint MemPageSize=4096)
  34 if (MemPageSize > 0 && MemPageSize < uint.max/65536 && T.sizeof <= MemPageSize)
  35 {
  36 public nothrow @trusted @nogc:
  37   enum PageSize = MemPageSize;
  38   enum ItemsPerPage = cast(uint)(PageSize/T.sizeof); // items per one page
  39   alias Me = SSArray!T;
  40   alias ValueT = T;
  41
  42 private:
  43   static struct PageStore {
  44     enum RefsPerPage = cast(uint)(PageSize/(void*).sizeof); // page pointers per one page
  45   nothrow @trusted @nogc:
  46     uint rc; // refcounter
  47     void** mHugeDir; // 2nd level directory page (allocated if mHugeRefs > 0; points to 1st level directories), or 1st level directory page (if mHugeRefs == 0)
  48     uint mHugeRefs; // number of refs in hugedir page
  49     uint mAllocPages; // number of allocated data pages
  50     uint xcount; // we'll keep it here too, so range iterators can use it
  51
  52     @disable this (this);
  53     void opAssign() (in auto ref typeof(this)) { static assert(0, `assigning disabled`); }
  54
  55     @property uint allocedPages () const pure { pragma(inline, true); return mAllocPages; }
  56
  57     // so i can easily override it
  58     void freePage(void* ptr) {
  59       pragma(inline, true);
  60       if (ptr !is null) {
  61         import core.stdc.stdlib : free;
  62         free(ptr);
  63       }
  64     }
  65
  66     // so i can easily override it
  67     void* mallocPage(bool doClear) () {
  68       import core.stdc.stdlib : malloc;
  69       static if (doClear) {
  70         if (auto res = malloc(PageSize)) {
  71           import core.stdc.string : memset;
  72           memset(res, 0, PageSize);
  73           return res;
  74         } else {
  75           return null;
  76         }
  77       } else {
  78         pragma(inline, true);
  79         return malloc(PageSize);
  80       }
  81     }
  82
  83     // allocate one new page
  84     // allocate new data page is `newData` is `null`
  85     bool allocNewPage(bool requireMem) (void* newData=null) {
  86       if (mHugeRefs == 0 && mAllocPages == RefsPerPage) {
  87         // we need to create hugedir
  88         debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: creating hugedir (%p)\n", &this, mHugeDir); }}
  89         auto vv = cast(void**)mallocPage!true;
  90         static if (!requireMem) { if (vv is null) return false; } else
  91         if (vv is null) assert(0, "PageStore: out of memory");
  92         assert(mHugeDir !is null);
  93         vv[0] = mHugeDir; // first 1st level page
  94         mHugeDir = vv;
  95         mHugeRefs = 1;
  96       }
  97       // allocate new data page (we'll need it anyway)
  98       auto dp = (newData is null ? mallocPage!false : newData); // don't clear
  99       static if (!requireMem) { if (dp is null) return false; } else
 100       if (dp is null) assert(0, "PageStore: out of memory");
 101       // simple case?
 102       if (mHugeRefs == 0) {
 103         if (mAllocPages == 0 && mHugeDir is null) {
 104           // no dir page, allocate one
 105           debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: creating smalldir\n", &this); }}
 106           void** hd = cast(void**)mallocPage!true;
 107           static if (!requireMem) { if (hd is null) { if (dp !is newData) freePage(dp); return false; } } else
 108           if (hd is null) assert(0, "PageStore: out of memory");
 109           mHugeDir = hd;
 110         }
 111         assert(mAllocPages+1 <= RefsPerPage);
 112         mHugeDir[mAllocPages++] = dp;
 113       } else {
 114         // allocate new 1st level directory page if necessary
 115         uint dirpgeidx = 0;
 116         void** dirpg = void;
 117         if (mAllocPages%RefsPerPage == 0) {
 118           debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: creating new 1st-level dir page (ap=%u; hr=%u)\n", &this, mAllocPages, mHugeRefs); }}
 119           // yep, last 1st level page is full, allocate new one
 120           if (mHugeRefs == RefsPerPage) assert(0, "PageStore: out of directory space");
 121           dirpg = cast(void**)mallocPage!true;
 122           static if (!requireMem) { if (dirpg is null) { if (dp !is newData) freePage(dp); return false; } } else
 123           if (dirpg is null) assert(0, "PageStore: out of memory");
 124           mHugeDir[mHugeRefs++] = dirpg;
 125           debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: new huge item! pa=%u; hr=%u; ptr=%p\n", &this, mAllocPages, mHugeRefs, dirpg); }}
 126         } else {
 127           // there should be some room in last 1st level page
 128           assert(mHugeRefs > 0);
 129           dirpg = cast(void**)mHugeDir[mHugeRefs-1];
 130           dirpgeidx = mAllocPages%RefsPerPage;
 131           assert(dirpg[dirpgeidx] is null);
 132         }
 133         dirpg[dirpgeidx] = dp;
 134         ++mAllocPages;
 135       }
 136       return true;
 137     }
 138
 139     void freeLastPage () {
 140       if (mAllocPages == 0) return;
 141       --mAllocPages; // little optimization: avoid `-1` everywhere
 142       if (mHugeRefs == 0) {
 143         // easy case
 144         // free last data page
 145         freePage(mHugeDir[mAllocPages]);
 146         mHugeDir[mAllocPages] = null; // why not?
 147         if (mAllocPages == 0) {
 148           // free catalog page too
 149           debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: freeing smalldir\n", &this); }}
 150           freePage(mHugeDir);
 151           mHugeDir = null;
 152         }
 153       } else {
 154         // hard case
 155         assert(mAllocPages != 0);
 156         immutable uint lv1pgidx = mAllocPages/RefsPerPage;
 157         immutable uint dtpgidx = mAllocPages%RefsPerPage;
 158         // free last data page
 159         void** pp = cast(void**)mHugeDir[lv1pgidx];
 160         freePage(pp[dtpgidx]);
 161         pp[dtpgidx] = null; // required
 162         if (dtpgidx == 0) {
 163           debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: freeing last 1st-level dir page (ap=%u)\n", &this, mAllocPages); }}
 164           // we should free this catalog page too
 165           freePage(pp);
 166           --mHugeRefs;
 167           // convert to one-level?
 168           if (mAllocPages == RefsPerPage) {
 169             assert(mHugeRefs == 1);
 170             debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: converting to smalldir\n", &this); }}
 171             pp = cast(void**)mHugeDir[0];
 172             // drop huge catalog page
 173             freePage(mHugeDir);
 174             mHugeDir = pp;
 175             mHugeRefs = 0;
 176           }
 177         }
 178       }
 179     }
 180
 181     // ensure that we have at least this number of bytes
 182     void ensureSize(bool requireMem) (uint size) {
 183       if (size >= uint.max/2) assert(0, "PageStore: out of memory"); // 2GB is enough for everyone!
 184       while (size > mAllocPages*PageSize) {
 185         if (!allocNewPage!requireMem()) {
 186           static if (!requireMem) break; else assert(0, "PageStore: out of memory");
 187         }
 188       }
 189     }
 190
 191     // ensure that we have at least this number of pages
 192     void ensurePages(bool requireMem) (uint pgcount) {
 193       if (pgcount >= uint.max/2/PageSize) assert(0, "PageStore: out of memory"); // 2GB is enough for everyone!
 194       while (pgcount > mAllocPages) {
 195         if (!allocNewPage!requireMem()) {
 196           static if (!requireMem) break; else assert(0, "PageStore: out of memory");
 197         }
 198       }
 199     }
 200
 201     // free everything
 202     void clear () {
 203       import core.stdc.string : memset;
 204       if (mHugeRefs == 0) {
 205         foreach (void* pg1; mHugeDir[0..mAllocPages]) freePage(pg1);
 206       } else {
 207         // for each 1st level dir page
 208         foreach (void* pg1; mHugeDir[0..mHugeRefs]) {
 209           // for each page in 1st level dir page
 210           foreach (void* dpg; (cast(void**)pg1)[0..RefsPerPage]) freePage(dpg);
 211           freePage(pg1);
 212         }
 213       }
 214       freePage(mHugeDir);
 215       memset(&this, 0, this.sizeof);
 216     }
 217
 218     uint lengthInFullPages () const pure { pragma(inline, true); return (xcount+ItemsPerPage-1)/ItemsPerPage; }
 219
 220     // get pointer to the first byte of the page with the given index
 221     inout(ubyte)* pagePtr (uint pgidx) inout pure {
 222       pragma(inline, true);
 223       return
 224         pgidx < mAllocPages ?
 225         (mHugeRefs == 0 ?
 226           cast(inout(ubyte)*)mHugeDir[pgidx] :
 227           cast(inout(ubyte)*)(cast(void**)mHugeDir[pgidx/RefsPerPage])[pgidx%RefsPerPage]) :
 228         null;
 229     }
 230
 231     // get pointer to the directory entry for the given page
 232     // used to move pages around
 233     inout(void)** pageDirPtr (uint pgidx) inout pure {
 234       pragma(inline, true);
 235       return
 236         pgidx < mAllocPages ?
 237         (mHugeRefs == 0 ?
 238           cast(inout(void)**)&mHugeDir[pgidx] :
 239           cast(inout(void)**)&(cast(void**)mHugeDir[pgidx/RefsPerPage])[pgidx%RefsPerPage]) :
 240         null;
 241     }
 242   }
 243
 244 private:
 245   usize psptr;
 246
 247   @property inout(PageStore)* psp () inout pure { pragma(inline, true); return cast(inout(PageStore*))psptr; }
 248
 249   // ugly hack, but it never returns anyway
 250   static void boundsError (uint idx, uint len) pure {
 251     import std.traits : functionAttributes, FunctionAttribute, functionLinkage, SetFunctionAttributes, isFunctionPointer, isDelegate;
 252     static auto assumePure(T) (scope T t) if (isFunctionPointer!T || isDelegate!T) {
 253       enum attrs = functionAttributes!T|FunctionAttribute.pure_;
 254       return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs))t;
 255     }
 256     assumePure((){
 257       import core.stdc.stdlib : malloc;
 258       import core.stdc.stdio : snprintf;
 259       char* msg = cast(char*)malloc(1024);
 260       auto len = snprintf(msg, 1024, "SSArray: out of bounds access; index=%u; length=%u", idx, len);
 261       assert(0, msg[0..len]);
 262     })();
 263   }
 264
 265   uint lengthInFullPages () const pure {
 266     pragma(inline, true);
 267     return (psptr ? ((cast(PageStore*)psptr).xcount+ItemsPerPage-1)/ItemsPerPage : 0);
 268   }
 269
 270   static uint lengthInFullPages (uint count) pure {
 271     pragma(inline, true);
 272     return (count+ItemsPerPage-1)/ItemsPerPage;
 273   }
 274
 275 public:
 276   this (this) pure { pragma(inline, true); if (psptr) ++(cast(PageStore*)psptr).rc; }
 277
 278   ~this () {
 279     pragma(inline, true);
 280     if (psptr) {
 281       if (--(cast(PageStore*)psptr).rc == 0) (cast(PageStore*)psptr).clear();
 282     }
 283   }
 284
 285   void opAssign() (in auto ref Me src) pure {
 286     pragma(inline, true);
 287     if (src.psptr) ++(cast(PageStore*)src.psptr).rc;
 288     if (psptr) {
 289       if (--(cast(PageStore*)psptr).rc == 0) (cast(PageStore*)psptr).clear();
 290     }
 291     psptr = src.psptr;
 292   }
 293
 294   /// remove all elements, free all memory
 295   void clear () {
 296     pragma(inline, true);
 297     if (psptr) {
 298       if (--(cast(PageStore*)psptr).rc == 0) (cast(PageStore*)psptr).clear();
 299     }
 300   }
 301
 302   ref inout(T) currWrap (uint idx) inout pure { pragma(inline, true); if (length == 0) assert(0, "SSArray: bounds error"); return this[idx%length]; } /// does wraparound
 303   ref inout(T) prevWrap (uint idx) inout pure { pragma(inline, true); if (length == 0) assert(0, "SSArray: bounds error"); return this[(idx+length-1)%length]; } /// does wraparound
 304   ref inout(T) nextWrap (uint idx) inout pure { pragma(inline, true); if (length == 0) assert(0, "SSArray: bounds error"); return this[(idx+1)%length]; } /// does wraparound
 305
 306   /// returns number of elements in the array
 307   @property uint length () const pure { pragma(inline, true); return (psptr ? (cast(PageStore*)psptr).xcount : 0); }
 308   /// sets new number of elements in the array (will free memory on shrinking)
 309   @property void length (usize count) {
 310     pragma(inline, true);
 311     static if (usize.sizeof == 4) {
 312       setLength(count);
 313     } else {
 314       if (count > uint.max/2) assert(0, "SSArray: out of memory");
 315       setLength(cast(uint)count);
 316     }
 317   }
 318   alias opDollar = length;
 319
 320   ///
 321   ref inout(T) opIndex (uint idx) inout pure {
 322     pragma(inline, true);
 323     if (idx >= length) boundsError(idx, length);
 324     return *((cast(inout(T)*)((cast(PageStore*)psptr).pagePtr(idx/ItemsPerPage)))+idx%ItemsPerPage);
 325   }
 326
 327   private bool ensurePS(bool requireMem) () {
 328     if (psptr == 0) {
 329       // allocate new
 330       import core.stdc.stdlib : malloc;
 331       import core.stdc.string : memset;
 332       auto psx = cast(PageStore*)malloc(PageStore.sizeof);
 333       static if (!requireMem) { if (psx is null) return false; } else
 334       if (psx is null) assert(0, "SSArray: out of memory");
 335       memset(psx, 0, PageStore.sizeof);
 336       psx.rc = 1;
 337       psptr = cast(usize)psx;
 338     }
 339     return true;
 340   }
 341
 342   /// reserve memory for the given number of elements (fail hard if `requireMem` is `true`)
 343   void reserve(bool requireMem=false) (uint count) {
 344     if (count == 0) return;
 345     if (uint.max/2/T.sizeof < count) {
 346       static if (requireMem) assert(0, "SSArray: out of memory");
 347       else count = uint.max/2/T.sizeof;
 348     }
 349     if (!ensurePS!requireMem()) return; // this will fail if necessary
 350     psp.ensureSize!requireMem(lengthInFullPages(cast(uint)(T.sizeof*count))*PageSize);
 351   }
 352
 353   /// set new array length.
 354   /// if `doShrinkFree` is `true`, free memory on shrinking.
 355   /// if `doClear` is `true`, fill new elements with `.init` on grow.
 356   /// reserve memory for the given number of elements (fail hard if `requireMem` is `true`)
 357   void setLength(bool doShrinkFree=false, bool doClear=initNewElements) (uint count) {
 358     if (uint.max/2/T.sizeof < count) assert(0, "SSArray: out of memory");
 359     if (count == length) return;
 360     if (count == 0) { if (psptr) (cast(PageStore*)psptr).clear(); return; }
 361     uint newPageCount = lengthInFullPages(count);
 362     assert(newPageCount > 0);
 363     ensurePS!true();
 364     if (count < (cast(PageStore*)psptr).xcount) {
 365       // shrink
 366       static if (doShrinkFree) {
 367         while ((cast(PageStore*)psptr).allocedPages > newPageCount) (cast(PageStore*)psptr).freeLastPage();
 368       }
 369       (cast(PageStore*)psptr).xcount = count;
 370     } else {
 371       // grow
 372       debug(debug_ssarray) if (psptr) { import core.stdc.stdio; printf("%p: grow000: ap=%u; sz=%u; qsz=%u; itperpage=%u; count=%u; length=%u\n", &this, (cast(PageStore*)psptr).allocedPages, (cast(PageStore*)psptr).allocedPages*PageSize, count*T.sizeof, ItemsPerPage, count, length); }
 373       (cast(PageStore*)psptr).ensurePages!true(newPageCount);
 374       static if (doClear) {
 375         static if (__traits(isIntegral, T) && T.init == 0) {
 376         } else {
 377           static immutable it = T.init;
 378           static bool checked = false;
 379           static bool isZero = false;
 380           if (!checked) {
 381             ubyte b = 0;
 382             foreach (immutable ubyte v; (cast(immutable(ubyte)*)(&it))[0..it.sizeof]) b |= v;
 383             isZero = (b == 0);
 384             checked = true;
 385           }
 386         }
 387         // fill up previous last page
 388         if ((cast(PageStore*)psptr).xcount%ItemsPerPage != 0) {
 389           uint itemsLeft = ItemsPerPage-(cast(PageStore*)psptr).xcount%ItemsPerPage;
 390           if (itemsLeft > count-(cast(PageStore*)psptr).xcount) itemsLeft = count-(cast(PageStore*)psptr).xcount;
 391           auto cp = (cast(T*)((cast(PageStore*)psptr).pagePtr((cast(PageStore*)psptr).xcount/ItemsPerPage)))+(cast(PageStore*)psptr).xcount%ItemsPerPage;
 392           (cast(PageStore*)psptr).xcount += itemsLeft;
 393           static if (__traits(isIntegral, T) && T.init == 0) {
 394             import core.stdc.string : memset;
 395             //pragma(msg, "ZEROING! (000)");
 396             memset(cp, 0, itemsLeft*T.sizeof);
 397           } else {
 398             if (isZero) {
 399               import core.stdc.string : memset;
 400               debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: ZERO FILL(000)\n", psp); }}
 401               memset(cp, 0, itemsLeft*T.sizeof);
 402             } else {
 403               import core.stdc.string : memcpy;
 404               while (itemsLeft--) {
 405                 memcpy(cp, &it, it.sizeof);
 406                 ++cp;
 407               }
 408             }
 409           }
 410           if (count == (cast(PageStore*)psptr).xcount) return;
 411         }
 412         // fill full pages
 413         assert((cast(PageStore*)psptr).xcount%ItemsPerPage == 0);
 414         while ((cast(PageStore*)psptr).xcount < count) {
 415           uint ileft = count-(cast(PageStore*)psptr).xcount;
 416           if (ileft > ItemsPerPage) ileft = ItemsPerPage;
 417           auto cp = cast(T*)((cast(PageStore*)psptr).pagePtr((cast(PageStore*)psptr).xcount/ItemsPerPage));
 418           //debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: xcount=%u; cp=%p; ileft=%u\n", psp, xcount, cp, ileft); }}
 419           (cast(PageStore*)psptr).xcount += ileft;
 420           static if (__traits(isIntegral, T) && T.init == 0) {
 421             import core.stdc.string : memset;
 422             //pragma(msg, "ZEROING! (001)");
 423             memset(cp, 0, ileft*T.sizeof);
 424           } else {
 425             if (isZero) {
 426               import core.stdc.string : memset;
 427               debug(debug_ssarray) {{ import core.stdc.stdio; printf("%p: ZERO FILL(001)\n", psp); }}
 428               memset(cp, 0, ileft*T.sizeof);
 429             } else {
 430               import core.stdc.string : memcpy;
 431               while (ileft--) {
 432                 memcpy(cp, &it, it.sizeof);
 433                 ++cp;
 434               }
 435             }
 436           }
 437         }
 438       } else {
 439         (cast(PageStore*)psptr).xcount = count;
 440       }
 441     }
 442   }
 443
 444   /// remove `size` last elements, but don't free memory.
 445   /// won't fail if `size` > `length`.
 446   void chop (uint size) {
 447     pragma(inline, true);
 448     if (psptr) {
 449       if (size > length) {
 450         (cast(PageStore*)psptr).xcount = 0;
 451       } else {
 452         (cast(PageStore*)psptr).xcount -= size;
 453       }
 454     }
 455   }
 456
 457   /// remove all array elements, but don't free any memory.
 458   void chopAll () { pragma(inline, true); if (psptr) (cast(PageStore*)psptr).xcount = 0; }
 459
 460   /// append new element to the array. uses `memcpy()` to copy data.
 461   void append() (in auto ref T t) {
 462     import core.stdc.string : memcpy;
 463     setLength!(false, false)(length+1); // don't clear, don't shrink
 464     memcpy(&this[$-1], &t, T.sizeof);
 465   }
 466
 467   /// append new element to the array. uses `memcpy()` to copy data.
 468   void opOpAssign(string op:"~") (in auto ref T t) { pragma(inline, true); append(t); }
 469
 470   // i HAET it!
 471   private import std.traits : ParameterTypeTuple;
 472
 473   int opApply(DG) (scope DG dg) if (ParameterTypeTuple!DG.length == 1 || ParameterTypeTuple!DG.length == 2) {
 474     // don't use `foreach` here, we *really* want to re-check length on each iteration
 475     for (uint idx = 0; idx < (cast(PageStore*)psptr).xcount; ++idx) {
 476       static if (ParameterTypeTuple!DG.length == 1) {
 477         // one arg
 478         if (auto res = dg(this[idx])) return res;
 479       } else {
 480         // two args
 481         uint xidx = idx;
 482         if (auto res = dg(xidx, this[idx])) return res;
 483       }
 484     }
 485     return 0;
 486   }
 487
 488   int opApplyReverse(DG) (scope DG dg) if (ParameterTypeTuple!DG.length == 1 || ParameterTypeTuple!DG.length == 2) {
 489     foreach_reverse (immutable uint idx; 0..length) {
 490       if (idx >= length) return 0; // yeah, recheck it
 491       static if (ParameterTypeTuple!DG.length == 1) {
 492         // one arg
 493         if (auto res = dg(this[idx])) return res;
 494       } else {
 495         // two args
 496         uint xidx = idx;
 497         if (auto res = dg(xidx, this[idx])) return res;
 498       }
 499     }
 500     return 0;
 501   }
 502
 503   /// range iterator
 504   static struct Range {
 505   public nothrow @trusted @nogc:
 506     alias ItemT = T;
 507   private:
 508     uint psptr;
 509     uint pos;
 510     uint xend;
 511
 512   private:
 513     this (uint a, uint b, uint c) pure { pragma(inline, true); psptr = a; pos = b; xend = c; if (psptr) ++(cast(PageStore*)psptr).rc; }
 514
 515   public:
 516     this() (in auto ref Me arr) pure { pragma(inline, true); psptr = arr.psptr; xend = arr.length; if (psptr) ++(cast(PageStore*)psptr).rc; }
 517     this (this) pure { if (psptr) ++(cast(PageStore*)psptr).rc; }
 518     ~this () {
 519       pragma(inline, true);
 520       if (psptr) {
 521         if (--(cast(PageStore*)psptr).rc == 0) (cast(PageStore*)psptr).clear();
 522       }
 523     }
 524     void opAssign() (in auto ref Range src) pure {
 525       pragma(inline, true);
 526       if (src.psptr) ++(cast(PageStore*)src.psptr).rc;
 527       if (psptr) {
 528         if (--(cast(PageStore*)psptr).rc == 0) (cast(PageStore*)psptr).clear();
 529       }
 530       psptr = src.psptr;
 531       pos = src.pos;
 532       xend = src.xend;
 533     }
 534     Range save () const { pragma(inline, true); return (empty ? Range.init : Range(psptr, pos, xend)); }
 535     @property bool empty () const pure { pragma(inline, true); return (psptr == 0 || pos >= xend || pos >= (cast(PageStore*)psptr).xcount); }
 536     @property ref inout(T) front () inout pure {
 537       version(aliced) pragma(inline, true);
 538       if (psptr && pos < xend && pos < (cast(PageStore*)psptr).xcount) {
 539         return *((cast(inout(T)*)((cast(PageStore*)psptr).pagePtr(pos/ItemsPerPage)))+pos%ItemsPerPage);
 540       } else {
 541         boundsError(pos, length);
 542         assert(0); // make compiler happy
 543       }
 544     }
 545     void popFront () pure { pragma(inline, true); if (!empty) ++pos; }
 546     uint length () const pure { pragma(inline, true); return (empty ? 0 : (xend < (cast(PageStore*)psptr).xcount ? xend : (cast(PageStore*)psptr).xcount)-pos); }
 547     alias opDollar = length;
 548
 549     Range opSlice () const { version(aliced) pragma(inline, true); return (empty ? Range.init : Range(psptr, pos, xend)); }
 550     Range opSlice (uint lo, uint hi) const {
 551       version(aliced) pragma(inline, true);
 552       if (lo > length) boundsError(lo, length);
 553       if (hi > length) boundsError(hi, length);
 554       if (lo >= hi) return Range.init;
 555       return Range(psptr, pos+lo, pos+hi);
 556     }
 557
 558     ref inout(T) opIndex (uint idx) inout pure {
 559       version(aliced) pragma(inline, true);
 560       if (psptr && idx >= 0 && idx < length) {
 561         return *((cast(inout(T)*)((cast(PageStore*)psptr).pagePtr((pos+idx)/ItemsPerPage)))+(pos+idx)%ItemsPerPage);
 562       } else {
 563         boundsError(idx, length);
 564         assert(0); // make compiler happy
 565       }
 566     }
 567   }
 568
 569   ///
 570   Range opSlice () const { version(aliced) pragma(inline, true); return Range(this); }
 571
 572   ///
 573   Range opSlice (uint lo, uint hi) const {
 574     version(aliced) pragma(inline, true);
 575     if (lo > length) boundsError(lo, length);
 576     if (hi > length) boundsError(hi, length);
 577     if (lo >= hi) return Range.init;
 578     return Range(psptr, lo, hi);
 579   }
 580
 581   // ////////////////////////////////////////////////////////////////////// //
 582   // low-level thingy, which may be handy sometimes
 583
 584   /// get direct pointer to the page data. pointer should not outlive the array.
 585   /// $(WARNING shrinking array can invalidate pointer (but not enlarging).)
 586   T* pageDataPtr (uint pgidx) const pure { pragma(inline, true); return (psptr ? cast(T*)((cast(PageStore*)psptr).pagePtr(pgidx)) : null); }
 587
 588   /// get total number of allocated pages
 589   uint allocatedPages () const pure { pragma(inline, true); return (psptr ? (cast(PageStore*)psptr).mAllocPages : 0); }
 590
 591   /// get number of used pages (there can be more allocated pages in the array)
 592   uint usedPages () const pure { pragma(inline, true); return (psptr ? (cast(PageStore*)psptr).lengthInFullPages : 0); }
 593
 594   /// insert new page before the given page; returns success flag
 595   /// `beforePageIdx` can be one past the last page, but not more
 596   /// this won't clear inserted elements with any value
 597   /// if `requireMem` is `false`, rollback on OOM
 598   /// if `data` is not null, don't allocate new data page, but use the given one
 599   bool insertPageBefore(bool requireMem=true) (uint beforePageIdx, void* data=null) {
 600     PageStore* ps = cast(PageStore*)psptr;
 601     if (ps !is null) {
 602       if (beforePageIdx > ps.lengthInFullPages) return false; // oops
 603       // memory check
 604       if (ps.lengthInFullPages >= uint.max/2/PageSize) {
 605         // just can't
 606         static if (requireMem) assert(0, "SSArray: out of memory");
 607         else return false;
 608       }
 609     } else {
 610       if (beforePageIdx > 0) return false; // oops
 611       if (!ensurePS!requireMem()) return false; // this will fail if necessary
 612       ps = cast(PageStore*)psptr;
 613     }
 614     // allocate new page
 615     if (ps.mAllocPages < ps.lengthInFullPages+1) {
 616       if (!ps.allocNewPage!requireMem(data)) return false; // this will fail if necessary
 617     }
 618     // easy case?
 619     if (beforePageIdx != ps.lengthInFullPages) {
 620       // no, move page pointers
 621       auto lpp = *ps.pageDirPtr(ps.mAllocPages-1);
 622       foreach_reverse (immutable uint pidx; beforePageIdx+1..ps.mAllocPages) {
 623         *ps.pageDirPtr(pidx) = *ps.pageDirPtr(pidx-1);
 624       }
 625       *ps.pageDirPtr(beforePageIdx) = lpp;
 626     }
 627     // fix length
 628     ps.xcount = (ps.lengthInFullPages+1)*ItemsPerPage;
 629     return true;
 630   }
 631
 632   /// remove the given page; returns success flag
 633   /// if `doFreeMem` is `false`, don't free removed page, just move it into unused set
 634   bool removePageAt(bool doFreeMem=true) (uint pgidx) {
 635     PageStore* ps = cast(PageStore*)psptr;
 636     if (ps is null) return false; // can't
 637     if (pgidx >= ps.lengthInFullPages) return false; // can't
 638     // easy case?
 639     if (pgidx != ps.lengthInFullPages-1) {
 640       // no, move page pointers
 641       auto lpp = *ps.pageDirPtr(pgidx);
 642       foreach (immutable uint pidx; pgidx+1..ps.mAllocPages) {
 643         *ps.pageDirPtr(pidx-1) = *ps.pageDirPtr(pidx);
 644       }
 645       *ps.pageDirPtr(ps.mAllocPages-1) = lpp;
 646     }
 647     static if (doFreeMem) ps.freeLastPage();
 648     if (ps.lengthInFullPages == 1) {
 649       ps.xcount = 0;
 650     } else {
 651       uint newlen = (ps.lengthInFullPages-1)*ItemsPerPage;
 652       if (ps.xcount > newlen) ps.xcount = newlen;
 653     }
 654     return true;
 655   }
 656
 657   /// extract the given page; returns page data pointer of `null` on failure
 658   void* extractPageAt (uint pgidx) {
 659     PageStore* ps = cast(PageStore*)psptr;
 660     if (ps is null) return null; // can't
 661     if (pgidx >= ps.lengthInFullPages) return null; // can't
 662     void* res = ps.pagePtr(pgidx);
 663     // easy case?
 664     if (pgidx != ps.lengthInFullPages-1) {
 665       // no, move page pointers
 666       auto lpp = *ps.pageDirPtr(pgidx);
 667       foreach (immutable uint pidx; pgidx+1..ps.mAllocPages) {
 668         *ps.pageDirPtr(pidx-1) = *ps.pageDirPtr(pidx);
 669       }
 670       *ps.pageDirPtr(ps.mAllocPages-1) = lpp;
 671     }
 672     *ps.pageDirPtr(ps.mAllocPages-1) = null; // page manager can live with this
 673     ps.freeLastPage();
 674     if (ps.lengthInFullPages == 1) {
 675       ps.xcount = 0;
 676     } else {
 677       uint newlen = (ps.lengthInFullPages-1)*ItemsPerPage;
 678       if (ps.xcount > newlen) ps.xcount = newlen;
 679     }
 680     return res;
 681   }
 682 }
 683
 684
 685 version(test_ssarray) unittest {
 686   import iv.vfs.io;
 687
 688   void testPostBlit (SSArray!int ssa) {
 689     writefln("T000: ssa ptr/rc: %x/%u/%u", ssa.psp, ssa.psp.rc, ssa.length);
 690     foreach (uint idx, int v; ssa) {
 691       assert(v == idx);
 692     }
 693   }
 694
 695   {
 696     SSArray!int ssa;
 697     ssa.length = 8;
 698     writefln("001: ssa ptr/rc: %x/%u/%u", ssa.psp, ssa.psp.rc, ssa.length);
 699     foreach (uint idx, ref int v; ssa) {
 700       assert(v == 0);
 701       v = idx;
 702     }
 703     testPostBlit(ssa);
 704
 705     ssa.length = ssa.PageSize/int.sizeof+128;
 706     writefln("002: ssa ptr/rc: %x/%u/%u; pages=%u", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.allocedPages);
 707
 708     ssa.length = (ssa.PageSize/int.sizeof)*(ssa.PageSize/(void*).sizeof)+4096;
 709     writefln("003: ssa ptr/rc: %x/%u/%u; pages=%u", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.allocedPages);
 710
 711     ssa.length = ssa.length/2;
 712     writefln("004: ssa ptr/rc: %x/%u/%u; pages=%u", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.allocedPages);
 713
 714     uint n = 0;
 715     foreach (immutable uint v; ssa[2..6]) n += v;
 716     assert(n == 2+3+4+5);
 717   }
 718
 719   {
 720     SSArray!int ssa;
 721     if (!ssa.insertPageBefore(0)) assert(0, "wtf?!");
 722     writefln("100: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 723     if (!ssa.insertPageBefore(0)) assert(0, "wtf?!");
 724     writefln("101: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 725     if (!ssa.insertPageBefore(0)) assert(0, "wtf?!");
 726     writefln("102: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 727     if (!ssa.removePageAt(1)) assert(0, "wtf?!");
 728     writefln("103: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 729     if (!ssa.removePageAt(0)) assert(0, "wtf?!");
 730     writefln("103: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 731     if (!ssa.removePageAt(0)) assert(0, "wtf?!");
 732     if (ssa.psp !is null) {
 733       writefln("103: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 734     }
 735   }
 736
 737   {
 738     SSArray!int ssa;
 739     if (!ssa.insertPageBefore(0)) assert(0, "wtf?!");
 740     writefln("200: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 741     if (!ssa.insertPageBefore(0)) assert(0, "wtf?!");
 742     writefln("201: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 743     if (!ssa.insertPageBefore(0)) assert(0, "wtf?!");
 744     writefln("202: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 745     auto pg = ssa.extractPageAt(1);
 746     if (pg is null) assert(0, "wtf?!");
 747     writefln("203: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 748     if (!ssa.insertPageBefore(0, pg)) assert(0, "wtf?!");
 749     writefln("204: ssa ptr/rc/len/allocpg: %x/%u/%u/%u  %x : %x : %x", ssa.psp, ssa.psp.rc, ssa.length, ssa.psp.mAllocPages, ssa.pageDataPtr(0), ssa.pageDataPtr(1), ssa.pageDataPtr(2));
 750   }
 751 }