ikod.containers.ring source code

1 module ikod.containers.ring;
2 
3 private import std.typecons;
4 private import core.bitop;
5 
6 private import std.experimental.allocator;
7 private import std.experimental.allocator.mallocator : Mallocator;
8 private import std.experimental.allocator.gc_allocator;
9 
10 version(TestingContainers) {
11     import ut;
12 }
13 
14 struct Ring(T, alias N, Allocator = Mallocator, bool GCRangesAllowed = true)
15 {
16     static if (popcnt(N) == 1)
17     {
18         enum _useMask = true;
19         enum _mask = N - 1;
20     }
21     else
22     {
23         enum _useMask = false;
24     }
25     public
26     {
27         enum OverflowPolicy
28         {
29             DROP,
30             OVERWRITE,
31             ERROR
32         }
33         enum PutStatus
34         {
35             OK,
36             DROPPPED,
37             OVERWRITTEN,
38             ERROR
39         }
40         enum GetStatus
41         {
42             OK,
43             EMPTY
44         }
45     }
46     private
47     {
48         alias allocator = Allocator.instance;
49         T[]                 _buffer;
50         immutable size_t    _size = N;
51         size_t              _head, _tail, _length; // write to head, read from tail
52         OverflowPolicy      _overflow_policy = OverflowPolicy.ERROR;
53     }
54     void init(OverflowPolicy p = OverflowPolicy.ERROR)
55     {
56         _buffer = makeArray!(T)(allocator, _size);
57         _overflow_policy = p;
58     }
59     ~this() @trusted
60     {
61         if (_buffer)
62         {
63             dispose(allocator, &_buffer[0]);
64         }
65     }
66     auto put(T)(T item)
67     {
68         if (_length == _size)
69         {
70             final switch(_overflow_policy)
71             {
72                 case OverflowPolicy.ERROR:
73                     return PutStatus.ERROR;
74                 case OverflowPolicy.DROP:
75                     return PutStatus.DROPPPED;
76                 case OverflowPolicy.OVERWRITE:
77                     _buffer[_head] = item;
78                     static if(_useMask)
79                     {
80                         _head = (_head + 1) & _mask;
81                         _tail = (_tail + 1) & _mask;
82                     }
83                     else
84                     {
85                         _head = (_head+1) % N;
86                         _tail = (_tail+1) % N;
87                     }
88                     return PutStatus.OVERWRITTEN;
89             }
90         }
91         _buffer[_head] = item;
92         _length++;
93         static if (_useMask)
94         {
95             _head = (_head + 1) & _mask;
96         }
97         else
98         {
99             _head = (_head+1) % N;
100         }
101         return PutStatus.OK;
102     }
103     auto get()
104     {
105         if (_length == 0)
106         {
107             return tuple!("status", "value")(GetStatus.EMPTY, T.init);
108         }
109         auto r = tuple!("status", "value")(GetStatus.OK, _buffer[_tail]);
110         static if(_useMask)
111         {
112             _tail = (_tail + 1) & _mask;
113         }
114         else
115         {
116             _tail = (_tail+1) % N;
117         }
118         _length--;
119         return r;
120     }
121     auto length()
122     {
123         return _length;
124     }
125     auto empty()
126     {
127         return _length == 0;
128     }
129     auto full()
130     {
131         return _length == N;
132     }
133 }
134 
135 @("basic")
136 @safe unittest
137 {
138     import std.algorithm;
139     import std.range;
140 
141     Ring!(int, 10) ring;
142     ring.init();
143     assert(ring.empty);
144     auto p = ring.put(1);
145     assert(p == ring.PutStatus.OK);
146     assert(!ring.empty);
147     assert(!ring.full);
148     auto g = ring.get();
149     assert(g.status == ring.GetStatus.OK);
150     assert(g.value == 1);
151     assert(ring.empty);
152     foreach(i;0..10)
153     {
154         p = ring.put(i);
155         assert(p == ring.PutStatus.OK);
156     }
157     assert(ring.full);
158     assert(ring.length == 10);
159     p = ring.put(10);
160     assert(p == ring.PutStatus.ERROR);
161     int[] a;
162     while(!ring.empty)
163     {
164         a ~= ring.get().value;
165     }
166     assert(equal(a, iota(10)));
167     assert(ring.empty);
168 }
169 @("class")
170 @safe
171 unittest
172 {
173     class C
174     {
175         int _i;
176         this(int i)
177         {
178             _i = i;
179         }
180     }
181     Ring!(C, 32) ring;
182     ring.init();
183     ring.put(new C(1));
184 }
185 @("N=32")
186 unittest
187 {
188     import std.algorithm;
189     import std.range;
190     enum N = 32;
191     Ring!(int, N) ring;
192     ring.init();
193     assert(ring.empty);
194     auto p = ring.put(1);
195     assert(p == ring.PutStatus.OK);
196     assert(!ring.empty);
197     assert(!ring.full);
198     auto g = ring.get();
199     assert(g.status == ring.GetStatus.OK);
200     assert(g.value == 1);
201     assert(ring.empty);
202     foreach(i;0..N)
203     {
204         p = ring.put(i);
205         assert(p == ring.PutStatus.OK);
206     }
207     assert(ring.full);
208     assert(ring.length == N);
209     p = ring.put(N);
210     assert(p == ring.PutStatus.ERROR);
211     int[] a;
212     while(!ring.empty)
213     {
214         a ~= ring.get().value;
215     }
216     assert(equal(a, iota(N)));
217     assert(ring.empty);
218 }