CASTACK2.C
[目次 | 関数]
1|/**************************************************************************
2|* 1. <<< リード・キャッシュ機能付き固定長スタック (CaStack2) >>>
3|*
4|*・スタック領域を確保する際にキーナンバーを指定して、キャッシュ内に一致する
5|* ものがあれば、その領域を返します。その領域には以前読み込んだデータが入っ
6|* ているので、ファイルからデータを再び読み込むなどの重い処理をする必要はあ
7|* りません。
8|*・書き込みのキャッシュでは、ありません。
9|*・RLU（古いものを優先的にキャッシュから外す）アルゴリズムを使っています。
10|*・RLU でない単純なアルゴリズムを用いたタイプの [CaStack] もあります。
11|*・サンプルは test フォルダを参照してください。
12|*
13|* 【内部補足】
14|*・スタック・ブロックを抜けると、通常のスタック変数（自動変数）と 同じように、
15|* スタック要素にアクセスすることは出来ません。
16|*・スタック・ブロックから一度抜けても、キャッシュ情報は残っているので、
17|* ヒットする可能性があります。
18|*・キャッシュがヒットしても、ファイルなどのキャッシュ元のデータが
19|* 変更された場合、再び読み込む必要があります。
20|*・内部では、スタック・メモリの構造は、実際スタック構造ではなく、
21|* 配列で管理しています。
22|* 
23|*
24|* 2. <<<【属性】>>>
25|*・メモリ領域に必要なサイズ [CaStack2_getMemSize()]
26|*・管理オブジェクト [CaStack2_getMan()]
27|*・スタック要素
28|*・要素番号 [CaStack2_Field_getI()]
29|*・ロック状態 [CaStack2_Field_isLock()]
30|*
31|* 3. <<<【メモ】>>>
32|*・複数スタックのテストはしていません。
33|*・caAllocRead のサンプル
34|*・CaStack_alloc が多すぎたらどうなる？
35|*・CaStack_alloc を同じスタック・ブロックで何度もするとどうなる？
36|*・CaStack_free、上位レベルで alloc され、多重ロックされているかも
37|*
38|* 4. <<< 用語 [スタック・メモリ] >>>
39|* キャッシュ・スタックが使用するメモリ領域
40|* その中に、スタック管理データや、ユーザに確保されるデータ領域が
41|* 格納されます。
42|*
43|* 5. <<< 用語 [スタック要素] >>>
44|* キャッシュ・スタックから確保するメモリ領域
45|* CaStack_alloc 関数を用いて確保されるメモリ領域です。１つのキャッシュ・
46|* スタックからは、 1種類の型のスタック要素しか確保できません。
47|*
48|* 6. <<< 用語 [キャッシュ・スタック管理] >>>
49|* すべての「キャッシュ・スタック」を管理するもの
50|* CaStack_start 関数などが、すべての「キャッシュ・スタック」を参照するために
51|* 管理するオブジェクトです。「キャッシュ・スタック」が１つしかない場合でも、
52|* 暗黙的に存在します。
53|*
54|* 7. <<< 用語 [キー] >>>
55|* キャッシュがヒットしたかどうかを判断するキー・データ
56|* 通常は int 型の数値を用いますが、どんな型でも構いません。ただし、１つの
57|* キャッシュ・スタックからは、1種類の型のキーしか使えません。
58|*
59|* 8. <<< 用語 [スタック・ブロック] >>>
60|* 関数のブロックや if 文などのブロック
61|* 中括弧 { } で囲まれた部分ですが、キャッシュ・スタックにおいては、
62|* CaStack_start 関数から CaStack_end 関数で囲まれた部分です。
63|* （サンプルを参照）
64|*
65|* 9. <<< 用語 [番号スタック] >>>
66|* 「配列要素」番号のスタック
67|* スタック要素を確保した順番に「配列要素」番号が入っていきます。また、
68|* スタック・ブロックのネストを示す区切りコード(-1)も入ります。
69|*
70|* 10. <<< 用語 [配列要素] >>>
71|* 内部で使用している配列の要素
72|* 「キー」と「スタック要素」から構成されます。
73|***************************************************************************/
74|
75|#include "mixer_precomp.h"
76|// #pragma hdrstop ("mixer_precomp")
77|
78|#ifdef USES_MXP_AUTOINC
79| #include <castack2.ah> /* Auto include header, Look at mixer-... folder */
80|#endif
81|
82|/**************************************************************************
83|* 11. <<< 暗黙的な「キャッシュ・スタック」[pCaStack2] >>>
84|*【役割】
85|*・「キャッシュ・スタック」が全部で１つしか無い場合に用いられる暗黙的な
86|* 「キャッシュ・スタック」のアドレス変数です。
87|***************************************************************************/
88|CaStack2* pCaStack2;
89|CaStack2_Man CaStack2_man = { &pCaStack2, 0, 0 };
90|
91|
92|/**************************************************************************
93|* 12. <<<「キャッシュ・スタック」の初期化 [CaStack2_init()] >>>
94|*【引数】
95|* ・CaStack2* m; 「キャッシュ・スタック」のアドレス
96|* ・CaStack2_Man* man; 「キャッシュ・スタック管理」のアドレス
97|* ・char* mem; 「スタック・メモリ」のアドレス
98|* ・int elem_size; 「スタック要素」のサイズ(byte)
99|* ・int key_size; 「キー」のサイズ(byte)
100|* ・int mElem; 「スタック要素」の最大数
101|*【補足】
102|*・「キャッシュ・スタック」は、１種類の型しか使えません。２つ以上の種類の
103|* 型の場合、複数の「キャッシュ・スタック」を使います。
104|*・「キャッシュ・スタック」が複数存在しない場合は、man に NULL を指定でき
105|* ます。
106|*・「キー」が、int 型なら key_size == sizeof(int) です。
107|*・「キー」が 2つの int 型なら、struct ii { int n1; int n2; } として
108|* key_size == sizeof( struct ii ) と指定します。
109|*・必要な mem のサイズは、CaStack2_getMemSize() 関数から求まります。
110|***************************************************************************/
111|void CaStack2_init( CaStack2* m, CaStack2_Man* man, char* mem,
112| int elem_size, int key_size, int mElem )
113|{
114| /* 「キャッシュ・スタック管理」man の配列へ m を登録する */
115| if ( man == NULL ) {
116| /* 「キャッシュスタック管理」の配列を pCaStack2 にし、*/
117| /* そこへ m を登録する */
118| #ifdef _CHECKER
119| if ( CaStack2_man.caStack_n != 0 ) error();
120| #endif
121| CaStack2_man.caStack = &pCaStack2;
122| CaStack2_man.caStack[0] = m;
123| CaStack2_man.caStack_n = 1;
124| CaStack2_man.caStack_m = 1;
125| }
126| else {
127| #ifdef _CHECKER
128| if ( CaStack2_man.caStack == &pCaStack2 ) error();
129| if ( CaStack2_man.caStack_n == CaStack2_man.caStack_m ) error();
130| if ( &CaStack2_man != man ) error();
131| #endif
132| CaStack2_man.caStack[ CaStack2_man.caStack_n ++ ] = m;
133| }
134|
135| /* 各種属性の設定 */
136| ArrayU3_init( &m->arr, (char*)((int*)mem + mElem * 2),
137| key_size + elem_size, mElem );
138| m->pStack = (int*)mem;
139| m->nStack = 0;
140| m->mStack = mElem * 2;
141| m->key_size = key_size;
142|}
143|
144|
145|/**************************************************************************
146|* 13. <<<「キャッシュ・スタック管理」を返す [CaStack2_getMan()] >>>
147|*【引数】
148|* ・CaStack2** caStack;「キャッシュ・スタック」のアドレス配列の先頭アドレス
149|* ・int caStack_n; caStackの要素数
150|* ・CaStack2_Man* 返り値; 「キャッシュ・スタック管理」のアドレス
151|***************************************************************************/
152|CaStack2_Man* CaStack2_getMan( CaStack2** caStack, int caStack_n )
153|{
154| CaStack2_man.caStack = caStack;
155| CaStack2_man.caStack_n = 0;
156| CaStack2_man.caStack_m = caStack_n;
157| return &CaStack2_man;
158|}
159|
160|
161|/**************************************************************************
162|* 14. <<<「スタック・ブロック」開始の宣言 [CaStack2_getMan()] >>>
163|*【補足】
164|* 全ての種類の「キャッシュ・スタック」に、「スタック・ブロック」の境界を
165|* 示す区切りコード(-1)を付けます。（参照：CaStack2_end()）
166|***************************************************************************/
167|void CaStack2_start()
168|{
169| int i;
170|
171| for ( i = 0; i < CaStack2_man.caStack_n; i++ ) {
172| ArraySI_add( CaStack2_man.caStack[i]->pStack,
173| &CaStack2_man.caStack[i]->nStack, -1 );
174| }
175|}
176|
177|
178|/**************************************************************************
179|* 15. <<<「スタック・ブロック」終了の宣言 [CaStack2_end()] >>>
180|*【機能】
181|* CaStack2_start 関数が呼ばれた後の CaStack2_alloc によって確保された
182|* 全ての種類の「スタック要素」を解放します。
183|*【補足】
184|*・解放されても、次の CaStack2_alloc 関数、または CaStack2_get マクロが
185|* 実行されるまで、値は保持されています。詳細は CaStack2_alloc_func
186|* 関数の isLock = 0 の場合のドキュメントを参照してください。
187|***************************************************************************/
188|void CaStack2_end()
189|{
190| int i;
191|
192| for ( i = 0; i < CaStack2_man.caStack_n; i++ ) {
193|
194| /* 「スタック要素」を解放する「キャッシュ・スタック」s を */
195| /* 取得する */
196| CaStack2* s = CaStack2_man.caStack[i];
197|
198| #ifdef _CHECKER
199| if ( s->nStack <= 0 ) error();
200| #endif
201|
202| /* CaStack2_start 関数で付けた目印(-1)まで、*/
203| /*「スタック要素」を解放する */
204| s->nStack --;
205| while ( s->pStack[s->nStack] != -1 && s->nStack >= 0 ) {
206| ArrayU3_disuse( &s->arr, s->pStack[s->nStack] );
207| s->nStack --;
208| }
209|
210| /* 「スタック要素」が全て解放されたら、スタックの要素数を０にする */
211| if ( s->nStack < 0 ) s->nStack = 0;
212| }
213|}
214|
215|
216|/**************************************************************************
217|* 16. <<<「スタック要素」を確保する（キャッシュ付き）[CaStack2_alloc2p()] >>>
218|*【引数】
219|* ・CaStack2* m; 「キャッシュ・スタック」のアドレス
220|* ・void* pKey; 「キー」のアドレス, NULL も可能
221|* ・bool isLock; 確保したあとロックするかどうか(yes=1, no=0)
222|* ・void* 返り値; 確保した「スタック要素」のアドレス
223|*【補足】
224|*・pKey を調べてキャッシュにヒットしたら、その以前
225|* 読み込んだデータが入っている「スタック要素」を返します。
226|*・pKey が NULL の場合は、必ずヒットしません。
227|*・ヒットしたかどうかは、CaStack2_isHit 関数で確認します。
228|*・「キー」はアドレスで指定するので、たとえば int 型の key なら、
229|* CaStack2_alloc2(m,&key,true,type); とします。
230|*・isLock が 1 なら、CaStack2_end 関数までロックが掛かります。
231|*・isLock が 0 なら、ロックされませんが、最低でも次の
232|* CaStack_alloc_func 関数が
233|* 呼ばれるまで「スタック要素」の値とそのアドレスは保証されます。
234|* CaStack2_init 関数の mElem 引数で指定した値の回数を超える
235|* CaStack_alloc_func 関数の呼び出しがあると、確保した「スタック要素」の
236|* 値は保証されません。ただし、他の関数で、呼び出しが無いか注意してください。
237|***************************************************************************/
238|void* CaStack2_alloc2p( CaStack2* m, void* pKey, bool isLock )
239|{
240| int i,j;
241| CaStack2_Elem* pElem;
242|
243| /* 「配列要素」中の「キー」が pKey と一致したら、*/
244| /* その「配列要素」中の「スタック要素」を確保して返す */
245| /* 確保されていない「スタック要素」と確保されているそれから探します */
246| if ( pKey != NULL ) {
247| i = ArrayU3_getNoUseLast( &m->arr );
248| for ( j = 0; j < m->arr.nNoUseButValid && i != -1; j++ ) {
249| pElem = &ArrayU3_getElem( &m->arr, i, CaStack2_Elem );
250| if ( memcmp( CaStack2_Elem_getPKey( pElem, m ),
251| pKey, m->key_size ) == 0 ) {
252| CaStack2_man.isLastHit = true;
253| ArrayU3_use( &m->arr, i );
254| ArraySI_add( m->pStack, &m->nStack, i );
255| if ( ! isLock ) {
256| ArrayU3_disuse( &m->arr, m->pStack[m->nStack-1] );
257| ArraySI_delLast( &m->nStack );
258| }
259|
260| return (void*)CaStack2_Elem_getPField( pElem, m );
261| }
262| i = ArrayU3_getPrev( &m->arr, i );
263| }
264| i = ArrayU3_getUseTop( &m->arr );
265| while ( i != -1 ) {
266| pElem = &ArrayU3_getElem( &m->arr, i, CaStack2_Elem );
267| if ( memcmp( CaStack2_Elem_getPKey( pElem, m ),
268| pKey, m->key_size ) == 0 ) {
269| CaStack2_man.isLastHit = true;
270| ArrayU3_use( &m->arr, i );
271| /* 「番号スタック」には入れない */
272| if ( ! isLock ) {
273| ArrayU3_disuse( &m->arr, m->pStack[m->nStack-1] );
274| }
275| return (void*)CaStack2_Elem_getPField( pElem, m );
276| }
277| i = ArrayU3_getNext( &m->arr, i );
278| }
279| }
280|
281| /* 任意の「配列要素」を取得し、その「キー」を登録し、*/
282| /* その「スタック要素」を確保して返す */
283| CaStack2_man.isLastHit = false;
284| i = ArrayU3_getNoUseTop( &m->arr );
285| ASSERT( i != -1 );
286| pElem = &ArrayU3_getElem( &m->arr, i, CaStack2_Elem );
287| memcpy( CaStack2_Elem_getPKey( pElem, m ), pKey, m->key_size );
288| ArrayU3_useTop( &m->arr );
289| ArraySI_add( m->pStack, &m->nStack, i );
290| if ( ! isLock ) {
291| ArrayU3_disuse( &m->arr, m->pStack[m->nStack-1] );
292| ArraySI_delLast( &m->nStack );
293| }
294|
295| return (void*)CaStack2_Elem_getPField( pElem, m );
296|}
297|
298|
299|/**************************************************************************
300|* 17. <<<「スタック要素」を解放する [CaStack2_free()] >>>
301|*【引数】
302|* ・CaStack2* m; 「キャッシュ・スタック」のアドレス
303|* ・void* field; 解放する「スタック要素」のアドレス
304|*【補足】
305|*・二重解放すると、error() で止まります。
306|***************************************************************************/
307|void CaStack2_free( CaStack2* m, void* field )
308|{
309| int iElem = CaStack2_Field_getI( field, m ); /* 「配列要素」番号 */
310| int iStack; /* 「番号スタック」の要素番号 */
311|
312| /* 配列使用管理の未使用状態にする */
313| ArrayU3_disuse( &m->arr, iElem );
314|
315| /* iElem の値を持つ「番号スタック」の要素番号 iSatck を取得する */
316| for ( iStack = 0; iStack < m->nStack; iStack++ )
317| if ( m->pStack[iStack] == iElem )
318| break;
319|
320| #ifdef _CHECKER
321| if ( iStack >= m->nStack ) error(); /* field の値がおかしい */
322| #endif
323|
324| /* 「番号スタック」から「配列要素」番号 iStack を除く */
325| ArraySI_del( m->pStack, &m->nStack, iStack );
326|}
327|
328|
329|/**************************************************************************
330|* 18. <<< キャッシュにヒットしたかどうかを返す [CaStack2_isHit()] >>>
331|*【引数】
332|* ・int 返り値; ヒットした=1, していない=0
333|*【補足】
334|* 直前の CaStack2_alloc 関数が返した「スタック要素」が、
335|* キャッシュにヒットしているかどうかを返します。
336|***************************************************************************/
337|bool CaStack2_isHit()
338|{
339| return CaStack2_man.isLastHit;
340|}
341|
342|
343|/**************************************************************************
344|* 19. <<<「キャッシュ・スタック」のチェック [CaStack2_check()] >>>
345|*【補足】
346|* main 関数の終わりにチェックして、CaStack2_start 関数と CaStack2_end 関数が
347|* １つずつ正しく対応していなければ、エラーでプログラムを中止します。
348|***************************************************************************/
349|void CaStack2_check()
350|{
351| int i;
352|
353| for ( i = 0; i < CaStack2_man.caStack_n; i++ )
354| if ( CaStack2_man.caStack[i]->nStack != 0 )
355| error();
356|}
357|
358|
359|/**************************************************************************
360|* 20. <<<「スタック要素」のロック状態を返す [CaStack2_Field_isLock()] >>>
361|*【引数】
362|* ・void* field; 「スタック要素」のアドレス
363|* ・CaStack2* cas; field が所属しているキャッシュ・スタック
364|* ・bool 返り値; ロックしているか(true=1, false=0)
365|***************************************************************************/
366|bool CaStack2_Field_isLock( void* field, CaStack2* cas )
367|{
368| return ArrayU3_isUse( &cas->arr, CaStack2_Field_getI( field, cas ) );
369|}
370|
371|