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