->back to toppage

課題内容-level3-

     リストと配列の実装

リストや配列は複数の要素を格納する変数である。配列は、添字である数値によってランダムにアクセスすることができる。
配列の大きさをどのように決めれば良いか? リスト表現を使用すると、配列の大きさには制限がなくなるが、アクセスは遅くなる。


プログラムの説明

今回はLevel1のプログラムに配列とリストを実装した．
配列及びリストをするためにshell.yを以下のように書き加えた．


shell.yでの変更・追加部分



token()関数
   ・・・
   438	    } else if(('a' <= c && c <= 'z') || ('@' <=c && c <= 'Z') || 
   439		       ('*'<= c && c <= ':') || '~'== c || '$'==c){
   440	        file = ptr - 1;
   441	        while (('a' <= c && c <= 'z') || ('@' <=c && c <= 'Z') ||
   442	               ('*' <= c && c <= ':') || '~' == c || '$'==c )
        ～省略～
   450		switch(getID(value)){
        ～省略～
   457		case 3:
   458		  last_token = DELETE;
   459		  break;
   460		case 4:
   461		  last_token = DELKY;
   462		  break;
        ～省略～
   466		default:
   467		  if(value[0] == '$'){
   468		    last_token = ARR_VAL;
   469		    break;
   470		  }else if(value[0] == '@'){
   471		    last_token = LIS_VAL;
   472		    break;
   473		  }else{
   474		    last_token = 'f';
   475		    break;
   476		  }
   477		}
   478		return last_token;
   ・・・

token()関数では'@'と'$'を変数として扱えるように438～442の部分を書き換えた．通過してきた変数用の文字は466行のdefaultを通り，それぞれARR_VALとLIS_VALといったトークンで返される．また，配列やリストの削除をするためのコマンドを新しいトークンとして追加している，コマンドはあらかじめ予約語として登録しており，今回は450行でハッシュテーブルから探し出しswitchで割り振っている．


構文規則
    ・・・
    66	expr :  expr '|' expr  { $$ = new_node('|',NULL,0,$1,$3);} 
    ～省略～
    74	     |   cmd  val      { $$ = new_node($1->type,$1->value,-1,NULL,$2);
                                  free($1);}
    75	     |   cmd  val '=' file { $$ = new_node($1->type,$1->value,0,$2,$4);
                                  free($1);}  // list
    76	     |   cmd  val '[' file ']' 
    { $$ = new_node($1->type,$1->value,atoi($4->value),NULL,$2); free($1); free($4);}
    77	     |   cmd     {$$ = new_node($1->type,make_args($1,NULL,0),0,NULL,NULL);}
    78	     |   val  '=' file  { $$ = new_node('=',NULL,0,$1,$3); }
    79	     |   val  '[' file ']' '=' file  
    { $$ = new_node('=',NULL,atoi($3->value),$1,$6); free_node($3);}
    ～省略～
    85	     ;
    86	
    87	val  :  ARR_VAL      { $$ = new_node(ARR_VAL,value,0,NULL,NULL); }
    88	     |  LIS_VAL      { $$ = new_node(LIS_VAL,value,0,NULL,NULL);}
    89	     ;
    90	file :  'f'      { $$ = new_node('f',value,0,NULL,NULL);}
    91	cmd  :  WAIT      { $$ = new_node(WAIT,value,0,NULL,NULL);}
    92	     |  REF       { $$ = new_node(REF ,value,0,NULL,NULL);}
    93	     |  DELETE    { $$ = new_node(DELETE,value,0,NULL,NULL);}
    94	     |  DELKY     { $$ =  new_node(DELKY,value,0,NULL,NULL);}
    95	     |  EXIT      { $$ =  new_node(EXIT,value,0,NULL,NULL);}
    96	     ;
    ・・・

構文規則は上記のように変更した．74～76行は値を削除する際のコマンドを扱 うために追加した規則である．78行と79行は変数に値を代入する際に必要とな る規則である．87～96行はそれぞれの終端記号からノードを作成している．

command()関数
　  ・・・
   152	    switch(d->type) {
   153	    case 'c':
   ～省略～
   222	    case DELETE:
   223	      if(d->right&&d->num>=0){
   224	        index_delete(d->right->value, d->num);
   225	      }else if(d->num==-1&&d->right->value[0]=='$'){
   226          array_delete(d->right->value);
   227	      }
   228	      break;
   229	    case REF:
   230	      if(d->right){
   231	        if(d->right->value[0] == '$'){
   232	          if(d->num>=0)
   233	            printArrayValue(d->right->value, d->num);
   234	          else if(d->num==-1)
   235	            printArrayAll(d->right->value);
   236	        }else if(d->right->value[0] == '@')
   237	          printListValue(d->right->value);
   238	        else
   239	          printf("not variable\n");
   240	      }
   241	      break;
   242	    case EXIT:
   243	      exit(0);
   244	      break;
   245	    case DELKY:
   246	      if(d->right){
   247	        if(d->left&&d->left->value[0] == '@'){
   248	          key_delete(d->left->value, d->right->value);
   249	        }else if(d->right->value[0] == '@'){
   250	          list_delete(d->right->value);
   251	        }
   252	        break;
   253	      }else{
   254	        printf("usage : delkey @value [=] [list_name]\n");
   255	        break;
   256	      }
   257	
   258	    case '=':
   259	      if(d->left->value[0] == '$'){   
   260	        insert_data(d->left->value,d->right->value,d->num);
   261	      }else if(d->left->value[0] == '@'){
   262	        insert_list(d->left->value,d->right->value);
   263	      }
   264	      break;
   ～省略～
   270	    }
   ・・・

command関数では与えられたノードのtypeをswitchで判断し，それぞれの処理を行なっ ていく．

222行のDELETEでは配列の削除を行なうコマンドで，配列の添字を指 定したときとしてない時などの条件に合わせて関数を呼び出している． 229行目のREFは変数の値を表示させるコマンドで，自分の右のノードの値をそ れぞれprintArrayValue，printListValueに渡して処理を行なう．245行の DELKYはリストの要素を削除するもので，右のノードのvalueが'@'から始まる ときに処理をする．258行のcaseでは値の代入に関する処理を行なう．このとき， リストと配列では処理を行なう関数が違うのでここで振り分けている．




hash.cでの変更・追加部分


配列の処理

ここで，配列の処理における説明をする．配列の処理はhash.cにおける次の関 数で行なわれる．


リストの処理

次にリストの処理を説明する．リストは新しく追加される度にその領域を確保 し，nextを繋げるという形をとる．また，新しいリストは後ろへと追加されて いく形式とした．これを実現するのに実装したのが以下の関数である．



実行結果

作成したプログラムで配列の処理を行なった場合とリストの処理を行なった場合のそれぞれの 実行結果を以下に示す．

配列の操作

j04013 % ./my-shell                    [~/Documents/classes/junior/unix/level3]
[j04013]% $a=tomoyose
[j04013]% $a[1]=uehara
[j04013]% $a[2]=chinen
[j04013]% ref $a
$a[0]=tomoyose
$a[1]=uehara
$a[2]=chinen
[j04013]% ref $a[1]
$a[1]=uehara
[j04013]% del $a[1]
[j04013]% ref $a
$a[0]=tomoyose
$a[2]=chinen
[j04013]% del $a
[j04013]% ref $a
no such variable $a
[j04013]% $a=tamayose
[j04013]% ref $a
$a[0]=tamayose
上記の実行では変数$a[0]に"tomoyose"，$a[1]に"uehara"，$a[2]に"chinen" といった値を代入し，配列$aに入っている値を表示．次にdelkeyを用いて値 "kazuya"を削除し，削除されたのを確認．次に変数自体を削除し，削除されて いることを確認．最後に一度削除した値がまた使えることを示している．

リストの操作

j04013 % ./my-shell                    [~/Documents/classes/junior/unix/level3]
[j04013]% @a=eisaku;@a=kazuya;@a=naohisa
[j04013]% ref @a
@a=eisaku->kazuya->naohisa
[j04013]% delkey @a=kazuya
[j04013]% ref @a
@a=eisaku->naohisa
[j04013]% delkey @a
[j04013]% ref @a
no such variable @a
[j04013]% @a=yuichiro
[j04013]% ref @a
@a=yuichiro
[j04013]% delkey @a=yuichiro
[j04013]% ref @a
no such variable @a
リストは変数に代入していくことでそれがリストとして保存されるようになっ ている．
上記では"eisaku"，"kazuya"，"naohisa"をリストとして形成し， 間の"kazuya"を削除．次にこのリスト自体を削除し，最後に値を指定して削除 する際にリストが空になった時はハッシュ表から削除されているのを示してい る．



参考文献

<-previous problem　　　 go to top　　　 next problem->