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