mutils.container.vecor_queue source code

1 module mutils.container.vecor_queue;
2 
3 import core.bitop;
4 import core.stdc.stdlib : free, malloc;
5 import core.stdc..string : memcpy, memset;
6 import std.stdio;
7 
8 @nogc @safe nothrow pure size_t nextPow2()(size_t num) {
9     return 1 << bsr(num) + 1;
10 }
11 
12 struct VectorQueue(T) {
13     T[] array;
14     size_t begin;
15     size_t end;
16 
17     ~this() {
18         clear();
19     }
20 
21     void clear() {
22         removeAll();
23     }
24 
25     void removeAll() {
26         if (array !is null) {
27             freeData(cast(void[]) array);
28         }
29         array = null;
30         end = 0;
31         begin = 0;
32     }
33 
34     void reserve(size_t numElements) {
35         if (numElements > array.length) {
36             extend(numElements);
37         }
38     }
39 
40     void extend(size_t newNumOfElements) {
41         auto oldArray = manualExtend(array, newNumOfElements);
42         if (oldArray !is null) {
43             freeData(oldArray);
44         }
45     }
46 
47     @nogc void freeData(void[] data) {
48         // 0x0F probably invalid value for pointers and other types
49         memset(data.ptr, 0x0F, data.length); // Makes bugs show up xD 
50         free(data.ptr);
51     }
52 
53     size_t length() {
54         if (end >= begin) {
55             return end - begin;
56         }
57         return array.length + end - begin;
58     }
59 
60     void[] manualExtend(T[] oldArray, size_t newNumOfElements = 0) {
61         if (newNumOfElements == 0)
62             newNumOfElements = 2;
63         size_t oldSize = oldArray.length * T.sizeof;
64         size_t newSize = newNumOfElements * T.sizeof;
65         T* memory = cast(T*) malloc(newSize);
66         array = memory[0 .. newNumOfElements];
67 
68         size_t bbbbb = begin;
69         size_t eeeee = end;
70         size_t lll = length;
71         size_t iterator = begin;
72         size_t i = 0;
73         if (oldArray) {
74             do {
75                 if (iterator == end) {
76                     break;
77                 }
78                 array[i] = oldArray[iterator];
79 
80                 iterator++;
81 
82                 if (iterator == oldArray.length) {
83                     iterator = 0;
84                 }
85                 i++;
86             }
87             while (1);
88         }
89         end = i;
90         begin = 0;
91 
92         return cast(void[]) oldArray;
93     }
94 
95     void add()(auto ref T el) {
96         if (array.length - length <= 1) {
97             extend(nextPow2(array.length + 1));
98         }
99         array[end] = el;
100         end++;
101         if (end == array.length) {
102             end = 0;
103         }
104 
105     }
106 
107     T pop() {
108 
109         assert(begin != end);
110         auto el = array[begin];
111         begin++;
112         if (begin == array.length) {
113             begin = 0;
114         }
115         return el;
116     }
117 }
118 
119 unittest {
120     VectorQueue!int queue;
121 
122     queue.add(1);
123     queue.add(2);
124     queue.add(3);
125 
126     assert(queue.length == 3);
127 
128     assert(queue.pop() == 1);
129     assert(queue.pop() == 2);
130 
131     assert(queue.length == 1);
132     assert(queue.array.length == 4);
133 
134     queue.add(5);
135     queue.add(6);
136     assert(queue.array.length == 4);
137     assert(queue.pop() == 3);
138 
139     assert(queue.length == 2);
140 
141     assert(queue.pop() == 5);
142     assert(queue.pop() == 6);
143     assert(queue.length == 0);
144     assert(queue.array.length == 4);
145 
146     foreach (int i; 0 .. 128) {
147         queue.add(i);
148     }
149 
150     foreach (int i; 0 .. 128) {
151         assert(queue.pop() == i);
152     }
153 
154 }