|
0
|
1 #ifndef INCLUDED_QUEUE_INFO
|
|
|
2 #define INCLUDED_QUEUE_INFO
|
|
|
3
|
|
|
4 #include "base.h"
|
|
|
5 #include "types.h"
|
|
|
6
|
|
|
7 #if 0
|
|
|
8 template <typename T> class Queue : T {
|
|
|
9 public:
|
|
|
10
|
|
|
11 T();
|
|
|
12
|
|
|
13 T *waiter;
|
|
|
14 T *next;
|
|
|
15 T *prev;
|
|
|
16
|
|
|
17 void initOnce(); // to initialize object in pool
|
|
|
18 void freeOnce(); // to destroy object in pool
|
|
|
19
|
|
|
20 // virual void init();
|
|
|
21 };
|
|
|
22 #endif
|
|
|
23
|
|
|
24 template <typename T> class QueueInfo : public T {
|
|
|
25
|
|
|
26 public:
|
|
|
27 /* constructor */
|
|
|
28
|
|
|
29 /**
|
|
|
30 singleton queuePool constructor
|
|
|
31 Do not use this as a Queue
|
|
|
32 */
|
|
|
33 QueueInfo<T>(){
|
|
|
34 queueInfoInit();
|
|
|
35 }
|
|
|
36 /**
|
|
|
37 normal constructor requires
|
|
|
38 */
|
|
|
39 QueueInfo<T>(QueueInfo<T> *p) {
|
|
|
40 queueInfoInit();
|
|
|
41 queuePool = p;
|
|
|
42 }
|
|
|
43
|
|
|
44 BASE_NEW_DELETE(QueueInfo);
|
|
|
45
|
|
|
46 /* functions */
|
|
|
47 T *create();
|
|
|
48
|
|
|
49 void free_(T *queue);
|
|
|
50
|
|
|
51 void addFirst(T* e);
|
|
|
52 void addLast(T* e);
|
|
|
53 T* getFirst();
|
|
|
54 T* getLast();
|
|
|
55 int remove(T* e);
|
|
|
56 T* poll();
|
|
|
57 void moveToFirst(T* e); // or use();
|
|
|
58 T* get(int index);
|
|
|
59 T* find(T *task);
|
|
|
60 int empty();
|
|
|
61 void freePool() ;
|
|
|
62 void freeAll();
|
|
|
63
|
|
|
64 // Iterator
|
|
|
65 T* getNext(T* q) ;
|
|
|
66 int length();
|
|
|
67
|
|
|
68 private:
|
|
|
69 /* variables */
|
|
|
70
|
|
|
71 /* we cannot use static in template */
|
|
|
72 /* static */ QueueInfo<T> *queuePool;
|
|
|
73 T* first;
|
|
|
74 T* last;
|
|
|
75
|
|
|
76 /* functions */
|
|
|
77 int extend_pool(int num);
|
|
|
78 void destroy();
|
|
|
79 void queueInfoInit();
|
|
|
80 } ;
|
|
|
81
|
|
|
82
|
|
|
83
|
|
|
84 #ifdef CHECK
|
|
|
85 #include <stdio.h>
|
|
|
86 #endif
|
|
|
87 #include <stdlib.h>
|
|
|
88
|
|
|
89
|
|
|
90 /**
|
|
|
91 Use singleton queuePool constructor
|
|
|
92 all queueInfo should share this as a pool.
|
|
|
93
|
|
|
94 exteren QueueInfo<H> pool;
|
|
|
95 QueueInfo<H> pool = new QueueInfo<H>();
|
|
|
96
|
|
|
97 use this in non initialize envrionment is wrong.
|
|
|
98 */
|
|
|
99
|
|
|
100 template<typename T>void QueueInfo<T>::queueInfoInit() {
|
|
|
101 // 最初の一つは自分
|
|
|
102 first = last = this;
|
|
|
103 this->next = this->prev = this;
|
|
|
104 this->waiter = NULL;
|
|
|
105 }
|
|
|
106
|
|
|
107 template<typename T>void
|
|
|
108 QueueInfo<T>::freePool() {
|
|
|
109 for(T * p = queuePool->waiter; p; ) {
|
|
|
110 T * next = p->waiter;
|
|
|
111 p->waiter = NULL;
|
|
|
112 p->freeOnce();
|
|
|
113 free(p);
|
|
|
114 p = next;
|
|
|
115 }
|
|
|
116 }
|
|
|
117
|
|
|
118 /**
|
|
|
119 all pools are shared among QueueInfo (separated by size and type).
|
|
|
120 it automatically extended by 64.
|
|
|
121 */
|
|
|
122 template<typename T>int
|
|
|
123 QueueInfo<T>::extend_pool(int num)
|
|
|
124 {
|
|
|
125 #ifdef CHECK
|
|
|
126 if (queuePool) fprintf(stderr, "don't use queuePool directly");
|
|
|
127 #endif
|
|
|
128
|
|
|
129 T* q = (T*)malloc(sizeof(T)*(num+1)+DEFAULT_ALIGNMENT);
|
|
|
130
|
|
|
131 // First Queue is previous pool
|
|
|
132 q->waiter = this->waiter; this->waiter = q;
|
|
|
133 q = (T*)ROUND_UP_ALIGN((long)q, DEFAULT_ALIGNMENT);
|
|
|
134 q++;
|
|
|
135
|
|
|
136 /* Connect all free queue in the pool */
|
|
|
137 T* p = q;
|
|
|
138 for (; num-- > 0;) {
|
|
|
139 p->waiter = NULL;
|
|
|
140 p->initOnce();
|
|
|
141 addLast(p);
|
|
|
142 p = (T*)ROUND_UP_ALIGN((long)(p+1),DEFAULT_ALIGNMENT);
|
|
|
143 }
|
|
|
144
|
|
|
145 return 0;
|
|
|
146
|
|
|
147 }
|
|
|
148
|
|
|
149 /**
|
|
|
150 * Task をプールから取って来て返す
|
|
|
151 *
|
|
|
152 * @param [cmd] タスクコマンド
|
|
|
153 */
|
|
|
154 template<typename T>T *
|
|
|
155 QueueInfo<T>::create()
|
|
|
156 {
|
|
|
157 T * q = queuePool->poll();
|
|
|
158 if (! q) {
|
|
|
159 queuePool->extend_pool(64);
|
|
|
160 q = queuePool->poll();
|
|
|
161 }
|
|
|
162 q->init();
|
|
|
163 return q;
|
|
|
164 }
|
|
|
165
|
|
|
166
|
|
|
167 template<typename T>void
|
|
|
168 QueueInfo<T>::free_(T * q)
|
|
|
169 {
|
|
|
170 q->waiter = NULL;
|
|
|
171 queuePool->addLast(q);
|
|
|
172 }
|
|
|
173
|
|
|
174
|
|
|
175 /*!
|
|
|
176 QueueInfo<T> は空にならない。最低1個は要素が入っていて
|
|
|
177 1個目は特別扱いする。getFirst すると first->next を返す
|
|
|
178 */
|
|
|
179
|
|
|
180 /*!
|
|
|
181 最初の1個は特別扱いなので、それの後に追加していく
|
|
|
182 */
|
|
|
183 template<typename T>void
|
|
|
184 QueueInfo<T>::addFirst(T* e)
|
|
|
185 {
|
|
|
186 e->prev = first;
|
|
|
187 e->next = first->next;
|
|
|
188 first->next->prev = e;
|
|
|
189 first->next = e;
|
|
|
190 }
|
|
|
191
|
|
|
192 template<typename T>void
|
|
|
193 QueueInfo<T>::addLast(T* e)
|
|
|
194 {
|
|
|
195 #ifdef CHECK
|
|
|
196 if (find(e)) {
|
|
|
197 fprintf(stderr,"Add duplicate task %0x\n",(int)e);
|
|
|
198 return;
|
|
|
199 // ...
|
|
|
200 }
|
|
|
201 #endif
|
|
|
202 e->next = first;
|
|
|
203 e->prev = last;
|
|
|
204 last->next = e;
|
|
|
205 last = e;
|
|
|
206 }
|
|
|
207
|
|
|
208 template<typename T>T*
|
|
|
209 QueueInfo<T>::getFirst()
|
|
|
210 {
|
|
|
211 if (empty()) return NULL;
|
|
|
212 return first->next;
|
|
|
213 }
|
|
|
214
|
|
|
215 template<typename T>T*
|
|
|
216 QueueInfo<T>::getLast()
|
|
|
217 {
|
|
|
218 if (empty()) return NULL;
|
|
|
219 return last;
|
|
|
220 }
|
|
|
221
|
|
|
222 template<typename T>int
|
|
|
223 QueueInfo<T>::remove(T* e)
|
|
|
224 {
|
|
|
225 #ifdef CHECK
|
|
|
226 if (!find(e)) {
|
|
|
227 fprintf(stderr,"Remove non existing task %0x\n",(int)e);
|
|
|
228 return 0;
|
|
|
229 // ...
|
|
|
230 }
|
|
|
231 #endif
|
|
|
232 e->prev->next = e->next;
|
|
|
233 e->next->prev = e->prev;
|
|
|
234
|
|
|
235 if (first->next == e) {
|
|
|
236 first->next = e->next;
|
|
|
237 }
|
|
|
238 if (last == e) {
|
|
|
239 last = e->prev;
|
|
|
240 }
|
|
|
241
|
|
|
242 e->prev = NULL;
|
|
|
243 e->next = NULL;
|
|
|
244
|
|
|
245 return 1;
|
|
|
246 }
|
|
|
247
|
|
|
248 /*!
|
|
|
249 リストの先頭を取得および削除する。リストが空の場合は NULL を返す。
|
|
|
250 */
|
|
|
251
|
|
|
252 template<typename T>T*
|
|
|
253 QueueInfo<T>::poll()
|
|
|
254 {
|
|
|
255 T* e = first->next;
|
|
|
256 if (e == this) {
|
|
|
257 return NULL;
|
|
|
258 }
|
|
|
259 remove(e);
|
|
|
260 return e;
|
|
|
261 }
|
|
|
262
|
|
|
263 template<typename T>void
|
|
|
264 QueueInfo<T>::moveToFirst(T* e)
|
|
|
265 {
|
|
|
266 remove(e);
|
|
|
267 addFirst(e);
|
|
|
268 }
|
|
|
269
|
|
|
270 /*!
|
|
|
271 リスト内の指定された位置にある要素を返す。
|
|
|
272 要素数を超えた位置を指定した場合 NULL を返す。
|
|
|
273 */
|
|
|
274
|
|
|
275 template<typename T>T*
|
|
|
276 QueueInfo<T>::get(int index)
|
|
|
277 {
|
|
|
278 T* e = first->next;
|
|
|
279 for (int i = 0; i < index; i++) {
|
|
|
280 if (e->next == this) return NULL;
|
|
|
281 e = e->next;
|
|
|
282 }
|
|
|
283 return e;
|
|
|
284 }
|
|
|
285
|
|
|
286 template<typename T>T*
|
|
|
287 QueueInfo<T>::find(T* task)
|
|
|
288 {
|
|
|
289 T* e = first->next;
|
|
|
290 for(;;) {
|
|
|
291 if (e == this) return NULL;
|
|
|
292 if (e == task) break;
|
|
|
293 e = e->next;
|
|
|
294 }
|
|
|
295 return e;
|
|
|
296 }
|
|
|
297
|
|
|
298 template<typename T>int
|
|
|
299 QueueInfo<T>::empty()
|
|
|
300 {
|
|
|
301 return this->next == this;
|
|
|
302 }
|
|
|
303
|
|
|
304 template<typename T>T*
|
|
|
305 QueueInfo<T>::getNext(T* q)
|
|
|
306 {
|
|
|
307 if (q->next==this) return NULL;
|
|
|
308 return q->next;
|
|
|
309 }
|
|
|
310
|
|
|
311 template<typename T>int
|
|
|
312 QueueInfo<T>::length()
|
|
|
313 {
|
|
|
314 int i = 0;
|
|
|
315 if (empty()) return 0;
|
|
|
316 T* e = first;
|
|
|
317 while((e = e->next) != this ) i++;
|
|
|
318 return i;
|
|
|
319 }
|
|
|
320
|
|
|
321 template<typename T>void
|
|
|
322 QueueInfo<T>::freeAll()
|
|
|
323 {
|
|
|
324 T* t;
|
|
|
325 while((t=poll())) free_(t);
|
|
|
326 }
|
|
|
327
|
|
|
328
|
|
|
329
|
|
|
330 /* end */
|
|
|
331
|
|
|
332
|
|
|
333
|
|
|
334 #endif
|
