kiss.container.cirularqueue source code

1 /*
2  * Kiss - A refined core library for D programming language.
3  *
4  * Copyright (C) 2015-2018  Shanghai Putao Technology Co., Ltd
5  *
6  * Developer: HuntLabs.cn
7  *
8  * Licensed under the Apache-2.0 License.
9  *
10  */
11 
12 module kiss.container.cirularqueue;
13 
14 import core.memory;
15 import std.experimental.allocator.common;
16 import std.experimental.allocator.gc_allocator;
17 import std.traits;
18 import kiss.container.common;
19 
20 /**
21  * 
22     Queue Struct Template.
23     Params:
24         T         = the element type;
25         autoExten = if the Queue is full, will or not auto expand;
26         addToGC   = if use other Allocator, will or not add to GC scan.
27         Allocator = which type Allocator will used
28 */
29 
30 @trusted struct CirularQueue(T, Allocator = GCAllocator, bool autoExten = false, bool addInGC = true)
31         if (is(T == Unqual!T))
32 {
33     enum TSize = T.sizeof;
34     enum addToGC = addInGC && hasIndirections!T && !is(Unqual!Allocator == GCAllocator);
35     static if (hasIndirections!T)
36         alias InsertT = T;
37     else
38         alias InsertT = const T;
39 
40     /**
41         Params:
42             size        =  the queue init size. 
43     */
44     this(uint size)
45     {
46         assert(size > 3);
47         _size = size;
48         _data = cast(T[]) _alloc.allocate(TSize * size);
49         static if (addToGC)
50             GC.addRange(_data.ptr, len);
51     }
52 
53     static if (!StaticAlloc!Allocator)
54     {
55         this(uint size, Allocator alloc)
56         {
57             this._alloc = alloc;
58             this(size);
59         }
60     }
61     ~this()
62     {
63         if (_data.ptr)
64         {
65             static if (addToGC)
66                 GC.removeRange(_data.ptr);
67             _alloc.deallocate(_data);
68         }
69     }
70 
71     pragma(inline, true) void clear()
72     {
73 
74         _data[] = T.init;
75         _front = _rear = 0;
76     }
77 
78     pragma(inline, true) @property bool empty() const nothrow
79     {
80         return (_rear == _front);
81     }
82 
83     pragma(inline) @property bool full() const
84     {
85         if ((_rear + 1) % _size == _front)
86             return true; //队满
87         else
88             return false;
89     }
90 
91     pragma(inline, true) @property T front()
92     {
93         assert(!empty());
94         return _data[_front];
95     }
96 
97     pragma(inline, true) @property uint length()
98     {
99         return (_rear - _front + _size) % _size;
100     }
101 
102     pragma(inline, true) @property uint maxLength() nothrow
103     {
104         static if (autoExten)
105         {
106             return uint.max;
107         }
108         else
109         {
110             return _size - 1;
111         }
112     }
113 
114     bool enQueue(InsertT x)
115     {
116         if (full())
117         { //队满
118             static if (autoExten)
119                 exten();
120             else
121                 return false;
122         }
123         _data[_rear] = x;
124         _rear = (_rear + 1) % _size; //队尾指针加 1 取模
125         return true;
126     }
127 
128     pragma(inline, true) T deQueue(T v = T.init) nothrow
129     {
130         assert(!empty());
131         auto x = _data[_front];
132         _data[_front] = v;
133         _front = (_front + 1) % _size; //队头指针加 1 取模
134         return x;
135     }
136 
137     static if (autoExten)
138     {
139     protected:
140         void exten()
141         {
142             auto size = _size > 128 ? _size + ((_size / 3) * 2) : _size * 2;
143             auto len = TSize * size;
144             auto data = cast(T[]) _alloc.allocate(TSize * size);
145             static if (addToGC)
146                 GC.addRange(data.ptr, len);
147             uint i = 0;
148             while (!empty)
149             {
150                 data[i] = deQueue();
151                 ++i;
152             }
153             _size = size;
154             _front = 0;
155             _rear = i;
156             static if (addToGC)
157                 GC.removeRange(_data.ptr);
158             _alloc.deallocate(_data);
159             _data = data;
160         }
161 
162     }
163     mixin AllocDefine!Allocator;
164 private:
165     @disable this();
166     @disable this(this);
167     uint _front = 0;
168     uint _rear = 0;
169     T[] _data = null;
170     uint _size;
171 }
172 
173 unittest
174 {
175     import std.stdio;
176 
177     auto myq = CirularQueue!(int)(5);
178     writeln("init is empty = ", myq.empty);
179     foreach (i; 0 .. 13)
180     {
181         writeln("enQueue i =  ", i, "  en value = ", myq.enQueue(i));
182     }
183     writeln("end is empty = ", myq.empty);
184     writeln("end is full = ", myq.full);
185     writeln("size  = ", myq.length);
186     int i = 0;
187     while (!myq.empty)
188     {
189         writeln("\n");
190         writeln("\tstart while! i = ", i);
191         writeln("\tfront is = ", myq.front());
192         writeln("\tdeQueue is = ", myq.deQueue());
193 
194         ++i;
195     }
196     writeln("size  = ", myq.length);
197     int x = 2;
198     myq.enQueue(x);
199     writeln("front is = ", myq.front());
200     writeln("size  = ", myq.length);
201     x = 3;
202     myq.enQueue(x);
203     writeln("size  = ", myq.length);
204     writeln("front is = ", myq.front());
205     writeln("deQueue is = ", myq.deQueue());
206     writeln("size  = ", myq.length);
207     writeln("front is = ", myq.front());
208 }