1 | #ifndef ENVIRONMENT_QUEUE_SORT_QUEUE_DYNAMIC_H |
---|
2 | #define ENVIRONMENT_QUEUE_SORT_QUEUE_DYNAMIC_H |
---|
3 | |
---|
4 | #include <stdint.h> |
---|
5 | #include <iostream> |
---|
6 | #include "Parameters.h" |
---|
7 | #include "Queue.h" |
---|
8 | |
---|
9 | namespace environment { |
---|
10 | namespace queue { |
---|
11 | |
---|
12 | #define PERCENT_USE_MAX 90 |
---|
13 | #define PERCENT_USE_MIN 33 |
---|
14 | |
---|
15 | /* |
---|
16 | * Queue, sort by delay with a dynamic size |
---|
17 | */ |
---|
18 | |
---|
19 | template <class T> |
---|
20 | class Sort_Queue_Dynamic : public Queue<T> |
---|
21 | { |
---|
22 | // *****[ variables ]***** |
---|
23 | private : uint32_t _factor ; |
---|
24 | private : uint32_t _size_base; |
---|
25 | |
---|
26 | // *****[ constructor ]***** |
---|
27 | public : Sort_Queue_Dynamic (std::string name, Parameters * param) : Queue <T> (name, param->_size) |
---|
28 | { |
---|
29 | _size_base = param->_size; |
---|
30 | _factor = 1; |
---|
31 | }; |
---|
32 | |
---|
33 | // *****[ destructor ]***** |
---|
34 | public : ~Sort_Queue_Dynamic () |
---|
35 | { |
---|
36 | }; |
---|
37 | |
---|
38 | // *****[ must_decrease ]***** |
---|
39 | // Test if the queue must be decrease |
---|
40 | private : bool must_decrease (void) |
---|
41 | { |
---|
42 | return ( (_factor > 1 ) and |
---|
43 | (((100*Queue <T>::_nb_slot)/Queue <T>::_size) <= PERCENT_USE_MIN)); |
---|
44 | } |
---|
45 | |
---|
46 | // *****[ must_increase ]***** |
---|
47 | // Test if the queue must be increase |
---|
48 | private : bool must_increase (void) |
---|
49 | { |
---|
50 | return (((100*Queue <T>::_nb_slot)/Queue <T>::_size) >= PERCENT_USE_MAX); |
---|
51 | } |
---|
52 | |
---|
53 | // *****[ increase ]***** |
---|
54 | // increase the queue |
---|
55 | private : void increase (void) |
---|
56 | { |
---|
57 | _factor ++; |
---|
58 | change_size (_factor*_size_base); |
---|
59 | } |
---|
60 | |
---|
61 | // *****[ decrease ]***** |
---|
62 | // decrease the queue |
---|
63 | private : void decrease (void) |
---|
64 | { |
---|
65 | _factor --; |
---|
66 | change_size (_factor*_size_base); |
---|
67 | } |
---|
68 | |
---|
69 | // *****[ change_size ]***** |
---|
70 | // decrease the queue |
---|
71 | private : void change_size (uint32_t new_size) |
---|
72 | { |
---|
73 | slot_t<T> * new_slot = new slot_t<T> [new_size]; |
---|
74 | |
---|
75 | // copy data |
---|
76 | for (uint32_t it = 0; it < Queue <T>::_nb_slot; it ++) |
---|
77 | { |
---|
78 | new_slot [it] = Queue <T>::_slot [it]; |
---|
79 | } |
---|
80 | // Change information |
---|
81 | |
---|
82 | delete [] Queue <T>::_slot; |
---|
83 | |
---|
84 | Queue <T>::_slot = new_slot; |
---|
85 | Queue <T>::_size = new_size; |
---|
86 | } |
---|
87 | |
---|
88 | // *****[ reset ]***** |
---|
89 | // Reset the queue in the empty state |
---|
90 | public : void reset (void) |
---|
91 | { |
---|
92 | Queue <T>::_nb_slot = 0; |
---|
93 | }; |
---|
94 | |
---|
95 | // *****[ transition ]***** |
---|
96 | // Decrease the delay at all cycle |
---|
97 | public : void transition () |
---|
98 | { |
---|
99 | for (uint32_t it = 0; it < Queue <T>::_nb_slot; it ++) |
---|
100 | { |
---|
101 | if (Queue <T>::_slot[it]._delay != 0) |
---|
102 | Queue <T>::_slot[it] ._delay --; |
---|
103 | } |
---|
104 | } |
---|
105 | |
---|
106 | // *****[ read ]***** |
---|
107 | // return the n-eme slot. |
---|
108 | // (first = 0) |
---|
109 | public : slot_t<T> read (uint32_t num=0) |
---|
110 | { |
---|
111 | if (num >= Queue <T>::_nb_slot) |
---|
112 | { |
---|
113 | std::cerr << "<Sort_Queue_Dynamic.read> {ERROR} can't read because : num (" << num << ") >= _nb_slot (" << Queue <T>::_nb_slot << ")" << std::endl; |
---|
114 | exit(1); |
---|
115 | } |
---|
116 | |
---|
117 | return Queue <T>::_slot[num]; |
---|
118 | }; |
---|
119 | |
---|
120 | // *****[ pop ]***** |
---|
121 | // read the queue, and update the pointer |
---|
122 | public : T pop (uint32_t num=0) |
---|
123 | { |
---|
124 | if (num >= Queue <T>::_nb_slot) |
---|
125 | { |
---|
126 | std::cerr << "<Sort_Queue_Dynamic.pop> {ERROR} can't read because : num (" << num << ") >= _nb_slot (" << Queue <T>::_nb_slot << ")" << std::endl; |
---|
127 | exit(1); |
---|
128 | } |
---|
129 | |
---|
130 | // If full -> quit |
---|
131 | if (must_decrease() == true) |
---|
132 | decrease(); |
---|
133 | |
---|
134 | T val = Queue <T>::_slot [num]._data; |
---|
135 | |
---|
136 | // Reorganize the queue |
---|
137 | |
---|
138 | for (uint32_t it = num; it+1 < Queue <T>::_nb_slot; it ++) |
---|
139 | { |
---|
140 | uint32_t ptr = (it); |
---|
141 | uint32_t ptr_next = (it+1); |
---|
142 | |
---|
143 | // std::cout << "ptr : " << ptr << std::endl |
---|
144 | // << "ptr_next : " << ptr_next << std::endl |
---|
145 | // << "nb_slot : " << Queue <T>::_nb_slot << std::endl; |
---|
146 | |
---|
147 | Queue <T>::_slot [ptr] = Queue <T>::_slot [ptr_next]; |
---|
148 | } |
---|
149 | |
---|
150 | Queue <T>::_nb_slot --; |
---|
151 | |
---|
152 | return val; |
---|
153 | } |
---|
154 | |
---|
155 | // *****[ push ]***** |
---|
156 | public : bool push (T val) |
---|
157 | { |
---|
158 | return push (0, val); |
---|
159 | } |
---|
160 | |
---|
161 | // Push a new value (they must have a slot free) |
---|
162 | // Is sort by delay |
---|
163 | public : bool push (uint32_t delay, T val) |
---|
164 | { |
---|
165 | // std::cout << val << std::endl; |
---|
166 | |
---|
167 | // Test if must increase the queue (never full) |
---|
168 | if (must_increase() == true) |
---|
169 | increase(); |
---|
170 | |
---|
171 | uint32_t ptr = Queue <T>::_nb_slot; |
---|
172 | |
---|
173 | // Scan the fill to find the good position (keep the sort) |
---|
174 | for (uint32_t it = 0; it < Queue <T>::_nb_slot; it ++) |
---|
175 | { |
---|
176 | uint32_t ptr_scan = ptr-1; // ptr > 0 |
---|
177 | |
---|
178 | if (Queue <T>::_slot[ptr_scan]._delay <= delay) |
---|
179 | break; //find |
---|
180 | |
---|
181 | // reformor the queue |
---|
182 | Queue <T>::_slot [ptr] = Queue <T>::_slot [ptr_scan]; |
---|
183 | ptr = ptr_scan; |
---|
184 | } |
---|
185 | |
---|
186 | Queue <T>::_slot [ptr] = slot_t <T> (delay,val); |
---|
187 | Queue <T>::_nb_slot ++; |
---|
188 | |
---|
189 | return true; |
---|
190 | } |
---|
191 | // *****[ print ]***** |
---|
192 | public : friend std::ostream& operator<< (std::ostream& output, const Sort_Queue_Dynamic & x) |
---|
193 | { |
---|
194 | output << "<" << x._name << ">" << std::endl; |
---|
195 | output << " * nb_slot : " << x._nb_slot << std::endl; |
---|
196 | output << " * size : " << x._size << std::endl; |
---|
197 | output << " * factor : " << x._factor << std::endl; |
---|
198 | |
---|
199 | for (uint32_t it = 0; it < x._nb_slot; it ++) |
---|
200 | { |
---|
201 | output << x._slot [it] << std::endl; |
---|
202 | } |
---|
203 | |
---|
204 | return output; |
---|
205 | }; |
---|
206 | |
---|
207 | |
---|
208 | }; |
---|
209 | |
---|
210 | }; |
---|
211 | }; |
---|
212 | #endif |
---|