Listx.c
[目次 | 関数]
1|/*************************************************************************
2|* 1. <<< 単方向リスト構造 (ListX) >>>
3|**************************************************************************/
4|
5|#include "mixer_precomp.h" /* Auto precompiled header, Look at mixer-... folder */
6|// #pragma hdrstop
7|
8|#if defined(USES_MXP_AUTOINC)
9| #include "listx.ah" /* Auto include header, Look at mixer-... folder */
10|#endif
11|
12|/*-----------------------------------------------------------------------*/
13|/* 2. <<< ◆(ListX) 単方向リスト構造・コンテナ >>> */
14|/*-----------------------------------------------------------------------*/
15|
16|#ifdef USES_SYM
17|SYM_STRUCT_START( ListX )
18|SYM_STRUCT_LOOP_FUNC( ListX, ListX_doLoopFunc )
19|SYM_STRUCT_MEMB_FUNC( ListX, ListX_doReadMemb, NULL ) /* first */
20|SYM_STRUCT_END( ListX )
21|#endif
22|
23|
24|
25|/*************************************************************************
26|* 3. <<< [ListX_init_byAble_imp] ListX_init_byAble の関数部 >>>
27|**************************************************************************/
28|#ifdef USES_ARRX
29|void ListX_init_byAble_imp( ListX* m, ArrX_Able* able, Offset list_elem,
30| Offset able_elem, int elem_size )
31|{
32| ListX_Builder b;
33| char* p = (char*)able->arr.first;
34| char* p_over = (char*)able->arr.last;
35|
36| b = ListX_initForBuilder( m );
37| while ( p < p_over ) {
38| if ( Offset_ref( able_elem, p, bool ) ) {
39|
40| /* 以下は、ListX_Builder_add( &b, p ); に相当 */
41| **(&b) = p;
42| *(&b) = &Offset_ref( list_elem, p, ListX_Elem );
43| }
44| p += elem_size;
45| }
46| ListX_Builder_finish( &b );
47|}
48|#endif
49|
50|/*************************************************************************
51|* 4. <<< [ListX_init_byArrXBuf_imp] ListX_init_byArrXBuf の関数部分 >>>
52|**************************************************************************/
53|#ifdef USES_ARRX
54|void ListX_init_byArrXBuf_imp( ListX* m, ArrX_Buf* buf, Offset elem_list,
55| int elem_size )
56|{
57| ListX_Builder b;
58| char* p = (char*)buf->first;
59| char* p_over = (char*)buf->last;
60|
61| b = ListX_initForBuilder( m );
62| while ( p < p_over ) {
63| ListX_Builder_add2( &b, p, elem_list );
64| p += elem_size;
65| }
66| ListX_Builder_finish( &b );
67|}
68|#endif
69|
70|/*************************************************************************
71|* 5. <<< [ListX_toEmptyDelete_imp] ListX_toEmptyDelete の関数部分 >>>
72|**************************************************************************/
73|#ifdef USES_INF
74|#ifdef LISTX_USE_MALLOC
75|void ListX_toEmptyDelete_imp( ListX* m, Offset elem_offset,
76| Inf_FinishFunc Elem_finish )
77|{
78| void* p;
79| void* next;
80|
81| if ( Elem_finish != NULL ) {
82| for ( p = m->first; p != NULL; p = next ) {
83| next = Offset_ref( elem_offset, p, ListX_Elem );
84| Elem_finish( p );
85| free( p );
86| }
87| }
88| else {
89| for ( p = m->first; p != NULL; p = next ) {
90| next = Offset_ref( elem_offset, p, ListX_Elem );
91| free( p );
92| }
93| }
94| ListX_toEmpty( m );
95|}
96|#endif /* USES_INF */
97|#endif
98|
99|
100|
101|/*************************************************************************
102|* 6. <<< [ListX_insert_imp] ListX_insert の関数部 >>>
103|**************************************************************************/
104|void ListX_insert_imp( ListX* m, void* pos, void* ins, Offset elem_next )
105|{
106| void* p;
107| void* p_prev;
108|
109| ASSERT( m != NULL );
110| ASSERT( m->first != NULL || ( m->first == NULL && pos == NULL ) );
111| ASSERT( ins != NULL );
112|
113| /* 要素があって、先頭の場合と */
114| /* 要素が無くて、末尾の場合（先頭の ASSERT で pos == NULL） */
115| if ( m->first == pos || m->first == NULL ) {
116| Offset_ref( elem_next, ins, void* ) = m->first;
117| m->first = ins;
118| }
119|
120| /* 先頭ではない場合 */
121| else {
122| p = Offset_ref( elem_next, m->first, void* );
123| p_prev = m->first;
124| for (;;) {
125| if ( p == pos ) {
126| Offset_ref( elem_next, ins, void* ) = p;
127| Offset_ref( elem_next, p_prev, void* ) = ins;
128| return;
129| }
130| ASSERT( p != NULL ); /* pos が見つからない */
131| p_prev = p;
132| p = Offset_ref( elem_next, p, void* );
133| }
134| }
135|}
136|
137|
138|/*************************************************************************
139|* 7. <<< [ListX_addFirstMalloc_imp] ListX_addFirstMalloc の実装部分 >>>
140|**************************************************************************/
141|#ifdef LISTX_USE_MALLOC
142|void* ListX_addFirstMalloc_imp( ListX* m, Offset elem_offset, int size )
143|{
144| void* p = malloc( size );
145| Offset_ref( elem_offset, p, ListX_Elem ) = m->first;
146| m->first = p;
147| return p;
148|}
149|#endif
150|
151|/*************************************************************************
152|* 8. <<< [ListX_insertMalloc_imp] ListX_insertMalloc の関数部分 >>>
153|**************************************************************************/
154|#ifdef LISTX_USE_MALLOC
155|void* ListX_insertMalloc_imp( ListX* m, void* pos, Offset elem_offset, int size )
156|{
157| void* obj = malloc( size );
158| ListX_insert_imp( m, pos, obj, elem_offset );
159| return obj;
160|}
161|#endif
162|
163|/*************************************************************************
164|* 9. <<< [ListX_remove_imp] ListX_remove の関数部 >>>
165|**************************************************************************/
166|void ListX_remove_imp( ListX* m, void* elem, Offset elem_next )
167|{
168| void* p;
169| void* p_prev;
170|
171| ASSERT( m->first != NULL && elem != NULL );
172|
173| /* 先頭の場合 */
174| if ( m->first == elem ) {
175| m->first = Offset_ref( elem_next, m->first, void* );
176| }
177| /* 先頭ではない場合 */
178| else {
179| p = Offset_ref( elem_next, m->first, void* );
180| p_prev = m->first;
181| for (;;) {
182| ASSERT( p != NULL ); /* 見つからない */
183| if ( p == elem ) {
184| Offset_ref( elem_next, p_prev, void* ) =
185| Offset_ref( elem_next, p, void* );
186| return;
187| }
188| p_prev = p;
189| p = Offset_ref( elem_next, p, void* );
190| }
191| }
192|}
193|
194|
195|/*************************************************************************
196|* 10. <<< [ListX_reverse_imp] ListX_reverse の関数部 >>>
197|**************************************************************************/
198|void ListX_reverse_imp( ListX* m, Offset ofs )
199|{
200| ListX newList;
201| void* ptr;
202|
203| newList.first = NULL;
204| ptr = m->first;
205| while ( ptr != NULL ) {
206| void* next = Offset_ref( ofs, ptr, void* );
207| Offset_ref( ofs, ptr, void* ) = newList.first;
208| newList.first = ptr;
209| ptr = next;
210| }
211| m->first = newList.first;
212|}
213|
214|
215|
216|/*************************************************************************
217|* 11. <<< [ListX_move_imp] ListX_move の関数部 >>>
218|**************************************************************************/
219|void ListX_move_imp( ListX* m, void* pos, void* moving, Offset elem_offset )
220|{
221| if ( pos == moving ) return;
222| ListX_remove_imp( m, moving, elem_offset );
223| ListX_insert_imp( m, pos, moving, elem_offset );
224|}
225|
226|
227|/*************************************************************************
228|* 12. <<< [ListX_moveStep_imp] ListX_moveStep の関数部 >>>
229|**************************************************************************/
230|void ListX_moveStep_imp( ListX* m, void* moving, Offset elem_offset, int plus )
231|{
232| void* pos;
233| int i;
234|
235| i = ListX_getI_imp( m, moving, elem_offset );
236| ASSERT( i != -1 );
237|
238| if ( plus <= 0 ) {
239| i += plus;
240| if ( i <= 0 ) pos = m->first;
241| else pos = ListX_get_imp( m, i, elem_offset );
242| }
243| else {
244| i += plus + 1;
245| if ( i >= ListX_getN_imp( m, elem_offset ) ) pos = NULL;
246| else pos = ListX_get_imp( m, i, elem_offset );
247| }
248|
249| ListX_move_imp( m, pos, moving, elem_offset );
250|}
251|
252|
253|/*************************************************************************
254|* 13. <<< [ListX_moveSet_imp] ListX_moveSet の関数部 >>>
255|**************************************************************************/
256|void ListX_moveSet_imp( ListX* m, void* from_start, void* from_endNext,
257| void* to, Offset elem_offset )
258|{
259| void* start_prev = ListX_getPrev_imp( m, from_start, elem_offset );
260| void* end_prev = ListX_getPrev_imp( m, from_endNext, elem_offset );
261| void* to_prev = ListX_getPrev_imp( m, to, elem_offset );
262|
263| #ifndef NDEBUG
264| {
265| void* p;
266| bool bStart = false;
267| bool bEnd = false;
268| bool bTo = false;
269|
270| for ( p = m->first; p != NULL;
271| p = Offset_ref( elem_offset, p, void* ) ) {
272| if ( p == from_start ) bStart = true;
273| else if ( p == from_endNext && bStart ) bEnd = true;
274| else if ( p == to ) {
275| if ( ! bStart || bEnd ) bTo = true;
276| }
277| }
278| ASSERT( bStart );
279| ASSERT( bEnd );
280| ASSERT( bTo );
281| }
282| #endif
283|
284| ASSERT( end_prev != NULL );
285| Offset_ref( elem_offset, end_prev, void* ) = to;
286|
287| if ( to_prev == NULL )
288| m->first = from_start;
289| else
290| Offset_ref( elem_offset, to_prev, void* ) = from_start;
291|
292| if ( start_prev == NULL )
293| m->first = from_endNext;
294| else
295| Offset_ref( elem_offset, start_prev, void* ) = from_endNext;
296|}
297|
298|
299|/*************************************************************************
300|* 14. <<< [ListX_getLast_imp] ListX_getLast の関数部 >>>
301|**************************************************************************/
302|#ifdef USES_OFFSET
303|void* ListX_getLast_imp( ListX* m, Offset elem_offset )
304|{
305| void* p = m->first;
306| void* p2;
307|
308| if ( p == NULL ) return NULL;
309| for (;;) {
310| p2 = Offset_ref( elem_offset, p, void* );
311| if ( p2 == NULL ) break;
312| p = p2;
313| }
314|
315| return p;
316|}
317|#endif
318|
319|
320|/*************************************************************************
321|* 15. <<< [ListX_get_imp] ListX_get の関数部 >>>
322|**************************************************************************/
323|#ifdef USES_OFFSET
324|void* ListX_get_imp( ListX* m, int i, Offset elem_offset )
325|{
326| void* p = m->first;
327|
328| while ( i > 0 ) {
329| ASSERT( p != NULL );
330| p = Offset_ref( elem_offset, p, void* );
331| i--;
332| }
333|
334| return p;
335|}
336|#endif
337|
338|
339|/*************************************************************************
340|* 16. <<< [ListX_getI_imp] ListX_getI の関数部 >>>
341|**************************************************************************/
342|int ListX_getI_imp( ListX* m, void* elem, Offset elem_offset )
343|{
344| int i = 0;
345| void* p = m->first;
346|
347| while ( p != NULL ) {
348| if ( p == elem ) return i;
349| p = Offset_ref( elem_offset, p, void* );
350| i++;
351| }
352|
353| return -1;
354|}
355|
356|/*************************************************************************
357|* 17. <<< [ListX_getN_imp] ListX_getN の関数部 >>>
358|**************************************************************************/
359|#ifdef USES_OFFSET
360|int ListX_getN_imp( ListX* m, Offset elem_offset )
361|{
362| int i = 0;
363| void* p = m->first;
364|
365| while ( p != NULL ) {
366| p = Offset_ref( elem_offset, p, void* );
367| i++;
368| }
369|
370| return i;
371|}
372|#endif
373|
374|
375|/*************************************************************************
376|* 18. <<< [ListX_getPrev_imp] ListX_getPrev の関数部 >>>
377|**************************************************************************/
378|void* ListX_getPrev_imp( ListX* m, void* elem, Offset elem_offset )
379|{
380| void* p;
381| void* prev = NULL;
382|
383| for ( ListX_forEach_imp( m, &p, elem_offset ) ) {
384| if ( p == elem ) break;
385| prev = p;
386| }
387| return prev;
388|}
389|
390|
391|/***********************************************************************
392|* 19. <<< [ListX_search_s_imp] 検索する >>>
393|*【引数】
394|* ・Offset_Key* key; 辞書要素のキー情報
395|* ・char* kword; 検索するキー文字列
396|* ・Offset elem_offset; 辞書要素の ListX_Elem 型抽象クラスのオフセット
397|* ・void* 返り値; ヒットした辞書要素のアドレス（NULL=ヒットなし）
398|************************************************************************/
399|#ifndef USES_MORI_STDLIB
400|#ifdef __STRING_H
401|#if !defined(FOR_GHS) && !defined(FOR_CA) && !defined(FOR_WINCE)
402|
403|void* ListX_search_s_imp( ListX* m, Offset_Key* key, const char* kword,
404| Offset elem_offset )
405|{
406| void* p;
407|
408| for ( ListX_forEach_imp( m, &p, elem_offset ) ) {
409| if ( Offset_Key_isHit( key, p, kword ) ) return p;
410| }
411| return NULL;
412|}
413|
414|#endif
415|#endif
416|#endif
417|
418|
419|
420|
421|
422|
423|/*************************************************************************
424|* 20. <<< [ListX_printElem_imp] ListX_printElem の関数部 >>>
425|**************************************************************************/
426|#ifndef ERRORS_CUT_DEBUG_TOOL
427|void ListX_printElem_imp( ListX* m, Offset elem_offset, const char* title )
428|{
429| int i = 0;
430| ListX_Elem* p;
431|
432| Errors_printf( "%sListX(%p)...", title, m );
433| Errors_printf( "%s first = %p", title, m->first );
434| for ( ListX_forEach_imp( m, &p, elem_offset ) ) {
435| Errors_printf( "%s elem(%d).adr = %p", title, i, p );
436| i++;
437| }
438|}
439|#endif
440|
441|
442|/**************************************************************************
443|* 21. <<< [ListX_doLoopFunc] SYM_STRUCT_LOOP_FUNC に指定する関数 >>>
444|***************************************************************************/
445|#ifdef USES_SYM
446|bool ListX_doLoopFunc( Sym_Ref* container, Sym_Ref* elem )
447|{
448| ListX* m;
449|
450| if ( container->type == Sym_StructType ) m = (ListX*)container->adr;
451| else m = *(ListX**)container->adr;
452|
453| if ( elem->adr == NULL ) elem->adr = m->first;
454| else elem->adr = Offset_ref( (Offset)container->elem_param, elem->adr, void* );
455|
456| return elem->adr != NULL;
457|}
458|#endif
459|
460|
461|/**************************************************************************
462|* 22. <<< [ListX_doReadMemb] SYM_STRUCT_MEMB_FUNC に指定する関数 >>>
463|***************************************************************************/
464|#ifdef USES_SYM
465|void ListX_doReadMemb( Sym_Ref* obj, char* name, Sym_Ref* ret )
466|{
467| ListX* m = (ListX*)obj->adr;
468|
469| if ( strcmp( name, "first" ) == 0 ) {
470| ret->adr = m->first;
471| ret->type = obj->elem_type;
472| ret->st = obj->elem_st;
473| }
474|}
475|#endif
476|
477|
478|/*-----------------------------------------------------------------------*/
479|/* 23. <<< ◆(ListX_Adder) 単方向リスト構造・末尾追加子 >>> */
480|/*-----------------------------------------------------------------------*/
481|
482|
483|
484|/*************************************************************************
485|* 24. <<< [ListX_Adder_init_imp] ListX_Adder_init の実装部 >>>
486|*【引数】
487|* ・ListX_Adder* m; 単方向リスト構造・末尾追加子
488|* ・ListX* list; 要素を追加されるリスト・コンテナ
489|* ・Offset elemOfs; リスト要素の ListX_Elem_extend へのオフセット
490|**************************************************************************/
491|#ifdef USES_OFFSET
492|void ListX_Adder_init_imp( ListX_Adder* m, ListX* list, Offset elemOfs )
493|{
494| *m = (ListX_Adder)list->first;
495| while ( *m != NULL ) {
496| *m = &Offset_ref( elemOfs, *m, void*);
497| }
498|}
499|#endif
500|
501|
502|/*-----------------------------------------------------------------------*/
503|/* 25. <<< ◆(ListX_Dic) ハッシュテーブルを用いた辞書（ヒープ使用） >>> */
504|/*-----------------------------------------------------------------------*/
505|
506|#ifdef USES_INF
507|#ifdef USES_ARRX
508|#ifdef USES_STRX
509|#ifdef USES_STDPLUS
510|#ifdef LISTX_USE_MALLOC
511|
512|/***********************************************************************
513|* 26. <<< [ListX_Dic_init_imp] ListX_Dic_init の関数部分 >>>
514|************************************************************************/
515|void ListX_Dic_init_imp( ListX_Dic* m, int width, Offset_Key* key,
516| StrX_HashFunc hash, Offset ofsElem )
517|{
518| int size = sizeof( ListX_Plus ) * width;
519| void* p = malloc( size );
520| ListX_Plus* lp;
521|
522| ArrX_init( &m->table, p, size );
523| for ( ArrX_forEach( &m->table, &lp, ListX_Plus ) ) {
524| ListX_Plus_init2( lp, ofsElem );
525| }
526| m->width = ArrX_getN( &m->table, ListX_Plus );
527| m->key = *key;
528| m->hash = hash;
529|}
530|
531|
532|/***********************************************************************
533|* 27. <<< [ListX_Dic_toEmpty_imp] ListX_Dic_toEmpty の関数部分 >>>
534|************************************************************************/
535|void ListX_Dic_toEmpty_imp( ListX_Dic* m, Offset elem_offset,
536| Inf_FinishFunc Elem_finish )
537|{
538| ListX_Plus* lp;
539|
540| for ( ArrX_forEach( &m->table, &lp, ListX_Plus ) ) {
541| ListX_toEmptyDelete_imp( (ListX*)lp, elem_offset, Elem_finish );
542| }
543|}
544|
545|
546|/***********************************************************************
547|* 28. <<< [ListX_Dic_finish_imp] 後始末する >>>
548|************************************************************************/
549|void ListX_Dic_finish_imp( ListX_Dic* m, Offset elem_offset,
550| Inf_FinishFunc Elem_finish )
551|{
552| ListX_Dic_toEmpty_imp( m, elem_offset, Elem_finish );
553| free( m->table.first );
554|}
555|
556|
557|/***********************************************************************
558|* 29. <<< [ListX_Dic_search_imp] ListX_Dic_search の関数部分 >>>
559|************************************************************************/
560|#ifndef USES_MORI_STDLIB
561|#ifdef __STRING_H
562|#if !defined(FOR_GHS) && !defined(FOR_CA) && !defined(FOR_WINCE)
563|
564|void* ListX_Dic_search_imp( ListX_Dic* m, const char* kword, Offset elem_offset )
565|{
566| int hashVar = m->hash( kword, m->width );
567|
568| return ListX_search_s_imp( (ListX*)ArrX_get( &m->table, hashVar, ListX_Plus ),
569| &m->key, kword, elem_offset );
570|}
571|
572|#endif
573|#endif
574|#endif
575|
576|
577|/***********************************************************************
578|* 30. <<< [ListX_Dic_searchNext_imp] ListX_Dic_searchNext の関数部分 >>>
579|************************************************************************/
580|void* ListX_Dic_searchNext_imp( ListX_Dic* m, void* prev, Offset ofsElem )
581|{
582| /* ListX_Elem_forEachFrom */
583| Errors_notSupport();
584| return NULL;
585|}
586|
587|
588|/**************************************************************************
589|* 31. <<< [ListX_Dic_alloc_imp] ListX_Dic_alloc の関数部分 >>>
590|***************************************************************************/
591|#ifndef USES_MORI_STDLIB
592|#ifdef __STRING_H
593|#if !defined(FOR_GHS) && !defined(FOR_CA) && !defined(FOR_WINCE)
594|
595|void* ListX_Dic_alloc_imp( ListX_Dic* m, const char* kword,
596| Offset elem_offset, size_t elem_size )
597|{
598| int hashVar = m->hash( kword, m->width );
599| ListX_Plus* list = ArrX_get( &m->table, hashVar, ListX_Plus );
600|
601| if ( ListX_search_s_imp( (ListX*)list, &m->key, kword, elem_offset ) == NULL ) {
602| void* p = malloc( elem_size );
603| ListX_Plus_addFirst( list, p );
604| return p;
605| }
606| else
607| return NULL;
608|}
609|
610|#endif
611|#endif
612|#endif
613|
614|
615|
616|/**************************************************************************
617|* 32. <<< [ListX_Dic_getN] 辞書要素の数を返す >>>
618|***************************************************************************/
619|int ListX_Dic_getN( ListX_Dic* m )
620|{
621| int n = 0;
622| ListX_Plus* lp;
623|
624| for ( ArrX_forEach( &m->table, &lp, ListX_Plus ) ) {
625| n += ListX_getN_imp( (ListX*)lp, lp->next );
626| }
627| return n;
628|}
629|
630|
631|/**************************************************************************
632|* 33. <<< [ListX_Dic_print] デバッグ表示する >>>
633|***************************************************************************/
634|#ifndef ERRORS_CUT_DEBUG_TOOL
635|void ListX_Dic_print( ListX_Dic* m, const char* title )
636|{
637| Errors_printf( "%snElem = %d", title, ListX_Dic_getN( m ) );
638|}
639|#endif
640|
641|
642|#endif
643|#endif
644|#endif
645|#endif
646|#endif
647|
648|