egra: agg mini clipping bugfix; some fixes in widget rendering (buttons, etc.)
[iv.d.git] / ssarray.d
blob4b26f25bd8a17e6afd544e98f865f62eb201ab33
1 /*
2 * coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
3 * Understanding is not required. Only obedience.
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.
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.
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/>.
17 module iv.ssarray /*is aliced*/;
19 version(aliced) {} else private alias usize = size_t;
21 //debug = debug_ssarray;
24 /** Array implementation that doesn't fragment memory, and does no `realloc()`s.
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.
30 * $(WARNING This completely ignores any postblits, dtors and GC anchoring!)
32 static struct SSArray(T, bool initNewElements=true, uint MemPageSize=4096)
33 if (MemPageSize > 0 && MemPageSize < uint.max/65536 && T.sizeof <= MemPageSize)
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;
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
51 @disable this (this);
52 void opAssign() (in auto ref typeof(this)) { static assert(0, `assigning disabled`); }
54 @property uint allocedPages () const pure { pragma(inline, true); return mAllocPages; }
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);
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;
76 } else {
77 pragma(inline, true);
78 return malloc(PageSize);
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;
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;
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);
132 dirpg[dirpgeidx] = dp;
133 ++mAllocPages;
135 return true;
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;
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;
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");
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");
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);
213 freePage(mHugeDir);
214 memset(&this, 0, this.sizeof);
217 uint lengthInFullPages () const pure { pragma(inline, true); return (xcount+ItemsPerPage-1)/ItemsPerPage; }
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;
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;
243 private:
244 usize psptr;
246 @property inout(PageStore)* psp () inout pure { pragma(inline, true); return cast(inout(PageStore*))psptr; }
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;
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 })();
264 uint lengthInFullPages () const pure {
265 pragma(inline, true);
266 return (psptr ? ((cast(PageStore*)psptr).xcount+ItemsPerPage-1)/ItemsPerPage : 0);
269 static uint lengthInFullPages (uint count) pure {
270 pragma(inline, true);
271 return (count+ItemsPerPage-1)/ItemsPerPage;
274 public:
275 this (this) pure { pragma(inline, true); if (psptr) ++(cast(PageStore*)psptr).rc; }
277 ~this () {
278 pragma(inline, true);
279 if (psptr) {
280 if (--(cast(PageStore*)psptr).rc == 0) (cast(PageStore*)psptr).clear();
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();
290 psptr = src.psptr;
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();
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
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);
317 alias opDollar = length;
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);
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;
338 return true;
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;
348 if (!ensurePS!requireMem()) return; // this will fail if necessary
349 psp.ensureSize!requireMem(lengthInFullPages(cast(uint)(T.sizeof*count))*PageSize);
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();
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;
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;
409 if (count == (cast(PageStore*)psptr).xcount) return;
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;
437 } else {
438 (cast(PageStore*)psptr).xcount = count;
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;
456 /// remove all array elements, but don't free any memory.
457 void chopAll () { pragma(inline, true); if (psptr) (cast(PageStore*)psptr).xcount = 0; }
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);
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); }
469 // i HAET it!
470 private import std.traits : ParameterTypeTuple;
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;
484 return 0;
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;
499 return 0;
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;
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; }
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();
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();
529 psptr = src.psptr;
530 pos = src.pos;
531 xend = src.xend;
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
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;
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);
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
569 Range opSlice () const { version(aliced) pragma(inline, true); return Range(this); }
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);
580 // ////////////////////////////////////////////////////////////////////// //
581 // low-level thingy, which may be handy sometimes
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); }
587 /// get total number of allocated pages
588 uint allocatedPages () const pure { pragma(inline, true); return (psptr ? (cast(PageStore*)psptr).mAllocPages : 0); }
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); }
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;
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;
613 // allocate new page
614 if (ps.mAllocPages < ps.lengthInFullPages+1) {
615 if (!ps.allocNewPage!requireMem(data)) return false; // this will fail if necessary
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);
624 *ps.pageDirPtr(beforePageIdx) = lpp;
626 // fix length
627 ps.xcount = (ps.lengthInFullPages+1)*ItemsPerPage;
628 return true;
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);
644 *ps.pageDirPtr(ps.mAllocPages-1) = lpp;
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;
653 return true;
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);
669 *ps.pageDirPtr(ps.mAllocPages-1) = lpp;
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;
679 return res;
684 version(test_ssarray) unittest {
685 import iv.vfs.io;
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);
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;
702 testPostBlit(ssa);
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);
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);
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);
713 uint n = 0;
714 foreach (immutable uint v; ssa[2..6]) n += v;
715 assert(n == 2+3+4+5);
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));
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));