1 module ikod.containers.compressedlist;
2
3 version(unittest)
4 {}
5 else
6 {
7
8 /* deprecated */
9
10 private import core.memory;
11 private import core.bitop;
12 private import core.exception;
13
14 private import std.experimental.allocator;
15 private import std.experimental.allocator.mallocator : Mallocator;
16 private import std.experimental.allocator.gc_allocator;
17 private import std.experimental.logger;
18 private import std.format;
19 private import std.algorithm;
20 private import std.typecons;
21
22 private import automem: RefCounted, refCounted;
23
24 private import ikod.containers.internal;
25
26 private byte useFreePosition(ubyte[] m) @safe @nogc nothrow
27 {
28 import core.bitop: bsf;
29 //
30 // find free position, mark it as used and return it
31 // least significant bit in freeMap[0] means _nodes[0]
32 // most significant bit in freeMap[$-1] means nodes[$-1]
33 //
34 auto l = m.length;
35 for(uint i=0; i < l;i++)
36 {
37 ubyte v = m[i];
38 if ( v < 255 )
39 {
40 auto p = bsf(v ^ 0xff);
41 m[i] += 1 << p;
42 return cast(byte)((i<<3)+p);
43 }
44 }
45 assert(0);
46 }
47 private void markFreePosition(ubyte[] m, size_t position) @safe @nogc nothrow
48 {
49 auto p = position >> 3;
50 auto b = position & 0x7;
51 m[p] &= (1<<b)^0xff;
52 }
53
54 private bool isFreePosition(ubyte[] m, size_t position) @safe @nogc nothrow
55 {
56 auto p = position >> 3;
57 auto b = position & 0x7;
58 return (m[p] & (1<<b)) == 0;
59 }
60 private ubyte countBusy(ubyte[] m) @safe @nogc nothrow
61 {
62 import core.bitop;
63 ubyte s = 0;
64 foreach(b; m)
65 {
66 s+=popcnt(b);
67 }
68 return s;
69 }
70 @safe version(None) unittest
71 {
72 globalLogLevel = LogLevel.info;
73 import std.algorithm.comparison: equal;
74 ubyte[] map = [0,0];
75 auto p = useFreePosition(map);
76 assert(p == 0, "expected 0, got %s".format(p));
77 assert(map[0] == 1);
78 assert(!isFreePosition(map, 0));
79 assert(isFreePosition(map, 1));
80
81 p = useFreePosition(map);
82 assert(p == 1, "expected 1, got %s".format(p));
83 map = [255,0];
84 p = useFreePosition(map);
85 assert(p == 8, "expected 8, got %s".format(p));
86 assert(map[1] == 1);
87 map = [255,0x01];
88 p = useFreePosition(map);
89 assert(p == 9, "expected 9, got %s".format(p));
90 assert(equal(map, [0xff, 0x03]));
91 markFreePosition(map, 8);
92 assert(equal(map, [0xff, 0x02]), "got %s".format(map));
93 markFreePosition(map, 9);
94 assert(equal(map, [0xff, 0x00]), "got %s".format(map));
95 markFreePosition(map, 0);
96 assert(equal(map, [0xfe, 0x00]), "got %s".format(map));
97 }
98
99 ///
100 /// unrolled list with support only for:
101 /// 1. insert/delete front O(1)
102 /// 2. insert/delete back O(1)
103 /// 3. access/remove by index O(n/m), m - nodes per page
104 ///
105 deprecated("use unrolled list")
106 struct CompressedList(T, Allocator = Mallocator, bool GCRangesAllowed = true)
107 {
108 alias allocator = Allocator.instance;
109 alias StoredT = StoredType!T;
110 //enum MAGIC = 0x00160162;
111 enum PageSize = 512; // in bytes
112 enum NodesPerPage = PageSize/Node.sizeof;
113 static assert(NodesPerPage >= 1, "Node is too large to use this List, use DList instead");
114 static assert(NodesPerPage <= 255, "Strange, but Node size is too small to use this List, use DList instead");
115
116 enum BitMapLength = NodesPerPage % 8 ? NodesPerPage/8+1 : NodesPerPage/8;
117
118
119 struct Page {
120 ///
121 /// Page is fixed-length array of list Nodes
122 /// with batteries
123 ubyte[BitMapLength] _freeMap;
124 Page* _prevPage;
125 Page* _nextPage;
126 byte _firstNode;
127 byte _lastNode;
128 ubyte _count; // nodes counter
129 Node[NodesPerPage] _nodes;
130 }
131
132 struct Node {
133 StoredT v;
134 byte p; // prev index
135 byte n; // next index
136 }
137
138 struct Range {
139 private Page* page;
140 private byte index;
141
142 T front() @safe {
143 if ( page !is null && index == -1)
144 {
145 index = page._firstNode;
146 }
147 return page._nodes[index].v;
148 }
149 void popFront() @safe {
150 if ( page !is null && index == -1)
151 {
152 index = page._firstNode;
153 }
154 index = page._nodes[index].n;
155 if ( index != -1 )
156 {
157 return;
158 }
159 page = page._nextPage;
160 if ( page is null )
161 {
162 return;
163 }
164 index = page._firstNode;
165 }
166 bool empty() const @safe {
167 return page is null;
168 }
169 }
170 /// Iterator over items.
171 Range range() @safe {
172 return Range(_pages_first, -1);
173 }
174 private
175 {
176 Page* _pages_first, _pages_last;
177 ulong _length;
178
179 static Page* _freelist;
180 static int _freelist_len;
181 static enum _freelist_len_max = 100;
182 }
183 this(this) @safe
184 {
185 auto r = range();
186 _pages_first = _pages_last =null;
187 _length = 0;
188 foreach(e; r) {
189 insertBack(e);
190 }
191 }
192 private void move_to_freelist(Page* page) @safe @nogc {
193 if ( _freelist_len >= _freelist_len_max )
194 {
195 debug(cachetools) safe_tracef("dispose page");
196 () @trusted {
197 static if ( UseGCRanges!(Allocator,T, GCRangesAllowed) ) {
198 GC.removeRange(&page._nodes[0]);
199 }
200 dispose(allocator, page);
201 }();
202 return;
203 }
204 debug(cachetools) safe_tracef("put page in freelist");
205 //page._epoque++;
206 page._nextPage = _freelist;
207 _freelist = page;
208 _freelist_len++;
209 }
210
211 private Page* peek_from_freelist() @safe {
212 if ( _freelist is null )
213 {
214 Page* page = make!Page(allocator);
215 static if ( UseGCRanges!(Allocator, T, GCRangesAllowed) ) {
216 () @trusted {
217 GC.addRange(&page._nodes[0], Node.sizeof * NodesPerPage);
218 }();
219 }
220 page._nextPage = page._prevPage = null;
221 page._firstNode = page._lastNode = -1;
222 return page;
223 }
224 Page* p = _freelist;
225 _freelist = p._nextPage;
226 _freelist_len--;
227 assert(_freelist_len>=0 && _freelist_len < _freelist_len_max);
228 p._nextPage = p._prevPage = null;
229 p._firstNode = p._lastNode = -1;
230 return p;
231 }
232
233 ~this() @safe {
234 clear();
235 while(_freelist)
236 {
237 assert(_freelist_len>0);
238 auto next = _freelist._nextPage;
239 () @trusted {
240 static if ( UseGCRanges!(Allocator,T, GCRangesAllowed) ) {
241 GC.removeRange(&_freelist._nodes[0]);
242 }
243 dispose(allocator, _freelist);
244 }();
245 _freelist_len--;
246 _freelist = next;
247 }
248 }
249
250 /// remove anything from list
251 void clear() @safe {
252 _length = 0;
253 Page* page = _pages_first, next;
254 while(page)
255 {
256 next = page._nextPage;
257 *page = Page();
258 move_to_freelist(page);
259 page = next;
260 }
261 _length = 0;
262 _pages_first = _pages_last = null;
263 }
264
265 /// Is list empty?
266 bool empty() @safe const {
267 return _length == 0;
268 }
269
270 /// Items in the list.
271 ulong length() @safe const {
272 return _length;
273 }
274
275 // /// remove node (by 'Pointer')
276 // void remove(ref NodePointer p) @system {
277 // if ( empty )
278 // {
279 // assert(0, "Tried to remove from empty list");
280 // }
281 // _length--;
282 // Page *page = p._page;
283 // byte index = p._index;
284 // assert(!isFreePosition(page._freeMap, index), "you tried to remove already free list element");
285 // with (page)
286 // {
287 // assert(_count>0);
288 // _count--;
289 // // unlink from list
290 // auto next = _nodes[index].n;
291 // auto prev = _nodes[index].p;
292 // if ( prev >= 0)
293 // {
294 // _nodes[prev].n = next;
295 // }
296 // else
297 // {
298 // _firstNode = next;
299 // }
300 // if ( next >= 0)
301 // {
302 // _nodes[next].p = prev;
303 // }
304 // else
305 // {
306 // _lastNode = prev;
307 // }
308 // //_nodes[index].n = _nodes[index].p = -1;
309 // markFreePosition(_freeMap, index);
310 // }
311 // if ( page._count == 0 )
312 // {
313 // // relase this page
314 // if ( _pages_first == page )
315 // {
316 // assert(page._prevPage is null);
317 // _pages_first = page._nextPage;
318 // }
319 // if ( _pages_last == page )
320 // {
321 // assert(page._nextPage is null);
322 // _pages_last = page._prevPage;
323 // }
324 // if ( page._nextPage !is null )
325 // {
326 // page._nextPage._prevPage = page._prevPage;
327 // }
328 // if ( page._prevPage !is null )
329 // {
330 // page._prevPage._nextPage = page._nextPage;
331 // }
332 // move_to_freelist(page);
333 // }
334 // // at this point page can be disposed
335 // }
336
337 /// List front item
338 T front() @safe {
339 if ( empty )
340 {
341 assert(0, "Tried to access front of empty list");
342 }
343 Page* p = _pages_first;
344 assert( p !is null);
345 assert( p._count > 0 );
346 with(p)
347 {
348 return _nodes[_firstNode].v;
349 }
350 }
351
352 /// Pop front item
353 void popFront() @safe {
354 if ( empty )
355 {
356 assert(0, "Tried to popFront from empty list");
357 }
358 _length--;
359 Page* page = _pages_first;
360 //debug(cachetools) safe_tracef("popfront: page before: %s", *page);
361 assert(page !is null);
362 with (page) {
363 assert(_count>0);
364 assert(!isFreePosition(_freeMap, _firstNode));
365 auto first = _firstNode;
366 auto next = _nodes[first].n;
367 markFreePosition(_freeMap, first);
368 if ( next >= 0 )
369 {
370 _nodes[next].p = -1;
371 }
372 //_nodes[first].n = _nodes[first].p = -1;
373 _count--;
374 _firstNode = next;
375 }
376 if ( page._count == 0 )
377 {
378 // relase this page
379 _pages_first = page._nextPage;
380 move_to_freelist(page);
381 if ( _pages_first is null )
382 {
383 _pages_last = null;
384 }
385 else
386 {
387 _pages_first._prevPage = null;
388 }
389 }
390 debug(cachetools) safe_tracef("popfront: page after: %s", *page);
391 }
392
393 /// Insert item at front.
394 void insertFront(T v) {
395 _length++;
396 Page* page = _pages_first;
397 if ( page is null )
398 {
399 page = peek_from_freelist();
400 _pages_first = _pages_last = page;
401 }
402 if (page._count == NodesPerPage)
403 {
404 Page* new_page = peek_from_freelist();
405 new_page._nextPage = page;
406 page._prevPage = new_page;
407 _pages_first = new_page;
408 page = new_page;
409 }
410 // there is free space
411 auto index = useFreePosition(page._freeMap);
412 assert(index < NodesPerPage);
413 Node nn = Node(v, -1, page._firstNode);
414 move(nn, page._nodes[index]);
415 if (page._count == 0)
416 {
417 page._firstNode = page._lastNode = cast(ubyte)index;
418 }
419 else
420 {
421 assert(page._firstNode >= 0);
422 assert(!isFreePosition(page._freeMap, page._firstNode));
423 page._nodes[page._firstNode].p = cast(ubyte)index;
424 page._firstNode = cast(ubyte)index;
425 }
426 page._count++;
427 assert(page._count == countBusy(page._freeMap));
428 debug(cachetools) safe_tracef("page after insert front: %s", *page);
429 return;
430 }
431
432 /// List back item.
433 T back() @safe {
434 if ( empty )
435 {
436 assert(0, "Tried to access back of empty list");
437 }
438 Page* p = _pages_last;
439 assert( p !is null);
440 assert( p._count > 0 );
441 //debug(cachetools) safe_tracef("page: %s", *p);
442 with(p)
443 {
444 return _nodes[_lastNode].v;
445 }
446 }
447
448 /// Pop back item from list.
449 void popBack() @safe {
450 if ( empty )
451 {
452 assert(0, "Tried to popBack from empty list");
453 }
454 _length--;
455 Page* page = _pages_last;
456 assert(page !is null);
457 with (page) {
458 assert(_count>0);
459 assert(!isFreePosition(_freeMap, _lastNode));
460 auto last = _lastNode;
461 auto prev = _nodes[last].p;
462 markFreePosition(_freeMap, last);
463 if ( prev >=0 )
464 {
465 _nodes[prev].n = -1;
466 }
467 //_nodes[last].n = _nodes[last].p = -1;
468 _count--;
469 _lastNode = prev;
470 }
471 if ( page._count == 0 )
472 {
473 debug(cachetools) safe_tracef("release page");
474 // relase this page
475 _pages_last = page._prevPage;
476 move_to_freelist(page);
477 if ( _pages_last is null )
478 {
479 _pages_first = null;
480 }
481 else
482 {
483 _pages_last._nextPage = null;
484 }
485 }
486 }
487
488 /// Insert item back.
489 void insertBack(T v) {
490 _length++;
491 Page* page = _pages_last;
492 if ( page is null )
493 {
494 page = peek_from_freelist();
495 _pages_first = _pages_last = page;
496 }
497 if (page._count == NodesPerPage)
498 {
499 Page* new_page = peek_from_freelist();
500 new_page._prevPage = page;
501 page._nextPage = new_page;
502 _pages_last = new_page;
503 page = new_page;
504 }
505 // there is free space
506 auto index = useFreePosition(page._freeMap);
507 assert(index < NodesPerPage);
508 Node nn = Node(v, page._lastNode, -1);
509 move(nn, page._nodes[index]);
510 if (page._count == 0)
511 {
512 page._firstNode = page._lastNode = cast(ubyte)index;
513 }
514 else
515 {
516 assert(page._lastNode >= 0);
517 assert(!isFreePosition(page._freeMap, page._lastNode));
518 page._nodes[page._lastNode].n = cast(ubyte)index;
519 page._lastNode = cast(ubyte)index;
520 }
521 page._count++;
522 assert(page._count == countBusy(page._freeMap));
523 //debug(cachetools) safe_tracef("page: %s", *page);
524 return;
525 }
526 }
527
528 ///
529 @safe version(None_Deprecated) unittest
530 {
531 import std.experimental.logger;
532 import std.algorithm;
533 import std.range;
534
535 globalLogLevel = LogLevel.info;
536 CompressedList!int list;
537 foreach(i;0..66)
538 {
539 list.insertFront(i);
540 assert(list.front == i);
541 }
542 assert(list.length == 66);
543 assert(list.back == 0);
544 list.popFront();
545 assert(list.length == 65);
546 assert(list.front == 64);
547 list.popFront();
548 assert(list.length == 64);
549 assert(list.front == 63);
550 while( !list.empty )
551 {
552 list.popFront();
553 }
554 foreach(i;1..19)
555 {
556 list.insertFront(i);
557 assert(list.front == i);
558 }
559 foreach(i;1..19)
560 {
561 assert(list.back == i);
562 assert(list.length == 19-i);
563 list.popBack();
564 }
565 assert(list.empty);
566 list.insertBack(99);
567 assert(list.front == 99);
568 assert(list.back == 99);
569 list.insertBack(100);
570 assert(list.front == 99);
571 assert(list.back == 100);
572 list.insertFront(98);
573 list.insertBack(101);
574 () @trusted // * and remove for poiners is unsafe
575 {
576 list.clear();
577 assert(list.empty);
578
579 foreach(i;0..1000)
580 {
581 list.insertBack(i);
582 }
583 assert(equal(list.range(), iota(0,1000)));
584 list.clear();
585
586 assert(list.empty);
587 iota(0, 1000).each!(i => list.insertBack(i));
588 auto r = list.range();
589 while(!r.empty)
590 {
591 int v = r.front;
592 r.popFront();
593 }
594 assert(list.length == 1000, "expected empty list, got length %d".format(list.length));
595 }();
596
597 () @nogc
598 {
599 struct S {}
600 CompressedList!(immutable S) islist;
601 immutable S s = S();
602 islist.insertFront(s);
603 }();
604 class C
605 {
606 int c;
607 this(int v) {
608 c = v;
609 }
610 }
611 CompressedList!C clist;
612 foreach(i;0..5000)
613 {
614 clist.insertBack(new C(i));
615 }
616 foreach(i;0..4500)
617 {
618 clist.popBack();
619 }
620 assert(clist.length == 500);
621 clist.clear();
622 }
623
624 // unittest for unsafe types
625 version(None_Deprecated) unittest {
626 import std.variant;
627 alias T = Algebraic!(int, string);
628 auto v = T(1);
629 CompressedList!T cl;
630 cl.insertFront(v);
631 assert(cl.front == v);
632 cl.insertBack(v);
633 cl.popFront;
634 cl.popBack;
635 }
636
637 @safe @nogc version(None_Deprecated) unittest {
638 import std.range, std.algorithm;
639 CompressedList!int a, b;
640 iota(0,100).each!(e => a.insertBack(e));
641 a.popFront();
642 b = a;
643 assert(equal(a, b));
644 }
645
646 @("range")
647 @safe @nogc version(None_Deprecated) unittest {
648 import std.range, std.algorithm;
649 CompressedList!int a;
650 iota(0,100).each!(e => a.insertBack(e));
651 assert(equal(a.range(), iota(0,100)));
652 }
653 }