【タイマー管理】
タイマー粒度問題を解決するために待ち時間をマイクロ秒で指定する方法を考えてみた。
問題は複数の待ち時間をどう管理するかだ。それと使うタイマーは１個で済ませたい。となると方法は一つしかない。タイマーにはカウント値と比較し割り込みを発生させる比較割り込みがある。それを利用すれば実現可能だ。
要求された複数の待ち時間は通常同じはならない(同じであってもかまわない)ので待ち時間の長さで要求を並び替えることは可能である。と考えると複数の要求があったとしてもタイマーは最短の待ち時間にのみ専念するだけで良いことになる。最初の要求を処理したら次の要求のためにタイマーを再セットアップする。それを要求が無くなるまで繰り返すだけだ。
但し、待ち時間で管理すると割り込みの遅延やオーバーヘッドにより誤差が拡大しつづけるので注意してほしい。誤差が拡大しないようにするには待ち時間を時刻※に変換し管理する必要がある。時刻※はいつかオーバーフローしてしまい過去なのか未来なのかわからなくなってしまうときがくるが現在時刻※を起点（ゼロ）とするだけで解決できる。要求時刻※から現在時刻※を減算した結果を符号付きと見なし、マイナスなら過去、プラスなら未来と判断する。この方法による制約は待ち時間が時刻※の最大値の半分に制限されるということだけだ。
※時刻は３２ビットのマイクロ秒値を想定。
実装上の問題としては割り込み処理のオーバーヘッド等によりタイマーセットアップ中に要求時刻を過ぎてしまう場合があることだ。過ぎ去ったものは仕方ない。後ろを振り返えらず前に進もう。ということでそういう場合は最短のタイミングで次の割り込みが発生するようほんの少し未来のカウンター値（カウンター値＋２※）を比較値として設定すれば良いだろう。
※タイマーはいつカウントアップするかわからないため＋１では失敗する可能性がある。
一番の問題だと言っていたタイマーだけでもうちょっと書けるかなと思っていたが、なんか無理っぽいので、違う話題に．．．
【汎用リスト管理】
ＲＴＯＳの自作ではタスク管理のためのリスト構造があちこちで必要になる。都度コーディングするのもいいが面倒なので汎用的に使えるライブラリを作成してみた。stdテンプレート・ライブラリにリスト管理のためのクラスはあるがデータ構造自体を内部割り当てしてしまうため多重リンクには適さない。でも、複数のリンク・ポインターをどう管理するのか？という素朴な問題があったので暫し悩んでみて解決策をひらめいた。offsetof()を使う方法だ。リンク・ポインターの位置さえ分かればあとはキャストでどうにでもなる。試してみたところ構造体メンバは問題なかったがクラス・フィールドを指定すると警告が出るので構造体に限定すべき？なのだろう。
ライブラリは、headポインターのみの”single ended queue”と、head及びtailポインターを持つ”double ended queue”の２種類のテンプレート・クラス。最後に追加する頻度が高いのであれば”double ended queue”、そうでなければ”single ended queue”と目的に合わせて使い分けすれば良い。また、同一仕様なので同じ使い方ができる。
多重リンクに対応するために構造体名とそのリンク・ポインターとなるメンバー名を指定する仕様となっている。定義されたマクロを使うと少しだけシンプルに短く書ける。なお、リンクする構造体自体の領域は利用者側で割り当てすること。
【サンプル・コード】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// queue.h macro's //#define SEQUE(T, N) single_ended_queue<T, offsetof(T, N)> //#define DEQUE(T, N) double_ended_queue<T, offsetof(T, N)> #include "queue.h" struct NODE { struct NODE *next1; struct NODE *next2; ... }; SEQUE(struct NODE, next1) queue1; DEQUE(struct NODE, next2) queue2; |
【リスト管理ライブラリの概要】
|
1 |
void clear(void) |
リストを初期化する。
|
1 |
T *head(void) |
先頭ノードを取得する。リストが空の場合は、nullptrが返される。
|
1 |
T *tail(void) |
最終ノードを取得する。リストが空の場合は、nullptrが返される。
|
1 |
bool empty(void) |
リストが空ならtrueを返す。
|
1 |
size_t count(void) |
リストの登録ノード数を返す。
|
1 |
void enqueue(T *node) |
リストの最後にノードを追加する。
|
1 |
T *dequeue(void) |
リストの先頭ノードを削除し返す。リストが空の場合はnullptrを返す。
|
1 |
QUEUE_STATUS remove(T *node) |
指定ノードを削除する。先頭ノードが削除されるとQUEUE_STATUS_FIRST、それ以降はQUEUE_STATUS_SECOND、削除されなかった場合はQUEUE_STATUS_NONEを返す。
|
1 2 |
template<typename U> bool removeMatch(bool (*match)(T *, U), U arg) |
指定されたmatch関数がtrueを返したノードだけを削除する。リストが空になるとtrueを返す。
|
1 2 |
template<typename U> bool removeUntil(bool (*match)(T *, U), U arg) |
指定されたmatch関数がtrueを返している間ノードを削除し続ける。リストが空になるとtrueを返す。
|
1 2 |
template<typename U> QUEUE_STATUS insert(T *node, bool (*match)(T *, U), U arg) |
指定されたmatch関数がtrueを返したノードの直前に指定されたノードを挿入する。match関数がtrueを返さなかった場合は、最後に追加される。先頭に挿入されるとQUEUE_STATUS_FIRST、それ以降はQUEUE_STATUS_SECONDを返す。
|
1 2 |
template<typename U> T *scan(bool (*match)(T *, U), U arg) |
指定されたmatch関数がtrueを返したノードを返す。
【リスト管理ライブラリ】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 |
/* queue.h - Queue Algorithm Template Class Copyright (c) 2021 Sasapea's Lab. All right reserved. This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifndef __QUEUE_H #define __QUEUE_H #include <stdint.h> #include <stdbool.h> #include <stddef.h> #define SEQUE(T, N) single_ended_queue<T, offsetof(T, N)> #define DEQUE(T, N) double_ended_queue<T, offsetof(T, N)> #define QUEUE_NEXT_PTR(p) (T **)((char *)(p) + N) #define QUEUE_NODE_PTR(p) (T *)((char *)(p) - N) typedef enum { QUEUE_STATUS_NONE, QUEUE_STATUS_FIRST, QUEUE_STATUS_SECOND, } QUEUE_STATUS; template<typename T, size_t N> class single_ended_queue { private: T *_head; public: single_ended_queue(void) { clear(); } void clear(void) { _head = nullptr; } T *head(void) { return _head; } T *tail(void) { T *p = _head; if (p) { T *q = p; do q = *QUEUE_NEXT_PTR(p = q); while (q); } return p; } bool empty(void) { return _head == nullptr; } size_t count(void) { size_t cnt = 0; for (T *p = _head; p; p = *QUEUE_NEXT_PTR(p)) ++cnt; return cnt; } void enqueue(T *node) { *QUEUE_NEXT_PTR(node) = nullptr; for (T **p = &_head;; p = QUEUE_NEXT_PTR(*p)) { if (*p == nullptr) { *p = node; break; } } } T *dequeue(void) { T *node = _head; if (node) _head = *QUEUE_NEXT_PTR(node); return node; } QUEUE_STATUS remove(T *node) { for (T **p = &_head; *p; p = QUEUE_NEXT_PTR(*p)) { if (*p == node) { *p = *QUEUE_NEXT_PTR(*p); return (p == &_head ? QUEUE_STATUS_FIRST : QUEUE_STATUS_SECOND); } } return QUEUE_STATUS_NONE; } template<typename U> bool removeMatch(bool (*match)(T *, U), U arg) { T **p; for (p = &_head; *p; ) { if (match(*p, arg)) *p = *QUEUE_NEXT_PTR(*p); else p = QUEUE_NEXT_PTR(*p); } return p == &_head; } template<typename U> bool removeUntil(bool (*match)(T *, U), U arg) { for (T **p = &_head; *p; *p = *QUEUE_NEXT_PTR(*p)) { if (!match(*p, arg)) return false; } return true; } template<typename U> QUEUE_STATUS insert(T *node, bool (*match)(T *, U), U arg) { T **p; for (p = &_head;; p = QUEUE_NEXT_PTR(*p)) { if (*p == nullptr) break; if (match(*p, arg)) break; } *QUEUE_NEXT_PTR(node) = *p; *p = node; return (p == &_head ? QUEUE_STATUS_FIRST : QUEUE_STATUS_SECOND); } template<typename U> T *scan(bool (*match)(T *, U), U arg) { for (T *p = _head; p; p = *QUEUE_NEXT_PTR(p)) { if (match(p, arg)) return p; } return nullptr; } }; template<typename T, size_t N> class double_ended_queue { private: T *_head; T *_tail; public: double_ended_queue(void) { clear(); } void clear(void) { _head = _tail = nullptr; } T *head(void) { return _head; } T *tail(void) { return _tail; } bool empty(void) { return _head == nullptr; } size_t count(void) { size_t cnt = 0; for (T *p = _head; p; p = *QUEUE_NEXT_PTR(p)) ++cnt; return cnt; } void enqueue(T *node) { *QUEUE_NEXT_PTR(node) = nullptr; if (_head) _tail = (*QUEUE_NEXT_PTR(_tail) = node); else _head = _tail = node; } T *dequeue(void) { T *node = _head; if (node) { _head = *QUEUE_NEXT_PTR(node); if (_head == nullptr) _tail = nullptr; } return node; } QUEUE_STATUS remove(T *node) { for (T **p = &_head; *p; p = QUEUE_NEXT_PTR(*p)) { if (*p == node) { *p = *QUEUE_NEXT_PTR(*p); if (*p == nullptr) _tail = (p == &_head ? nullptr : QUEUE_NODE_PTR(p)); return (p == &_head ? QUEUE_STATUS_FIRST : QUEUE_STATUS_SECOND); } } return QUEUE_STATUS_NONE; } template<typename U> bool removeMatch(bool (*match)(T *, U), U arg) { T **p; for (p = &_head; *p; ) { if (match(*p, arg)) *p = *QUEUE_NEXT_PTR(*p); else p = QUEUE_NEXT_PTR(*p); } _tail = (p == &_head ? nullptr : QUEUE_NODE_PTR(p)); return p == &_head; } template<typename U> bool removeUntil(bool (*match)(T *, U), U arg) { for (T **p = &_head; *p; *p = *QUEUE_NEXT_PTR(*p)) { if (!match(*p, arg)) return false; } _tail = nullptr; return true; } template<typename U> QUEUE_STATUS insert(T *node, bool (*match)(T *, U), U arg) { T **p; for (p = &_head;; p = QUEUE_NEXT_PTR(*p)) { if (*p == nullptr) { _tail = node; break; } if (match(*p, arg)) break; } *QUEUE_NEXT_PTR(node) = *p; *p = node; return (p == &_head ? QUEUE_STATUS_FIRST : QUEUE_STATUS_SECOND); } template<typename U> T *scan(bool (*match)(T *, U), U arg) { for (T *p = _head; p; p = *QUEUE_NEXT_PTR(p)) { if (match(p, arg)) return p; } return nullptr; } }; #endif |
次回は、ＧＰＩＯ管理にしようかな。
【関連する投稿】
理想のＲＴＯＳを自作する (1)
理想のＲＴＯＳを自作する (2)
理想のＲＴＯＳを自作する (3)
理想のＲＴＯＳを自作する (4)
理想のＲＴＯＳを自作する (5)
理想のＲＴＯＳを自作する (6)
理想のＲＴＯＳを自作する (7)
理想のＲＴＯＳを自作する (8)
理想のＲＴＯＳを自作する (9)
理想のＲＴＯＳを自作する (10)
理想のＲＴＯＳを自作する (11)