c言語でのスタック(単純配列実装)

はじめに

c言語でのスタックをステップバイステップで書いてみて,構造を学ぶ.
本記事では,単純な配列を用いて実装していく♪

目標

5段の空スタックを作成(各段には数値が一つ入る)
スタックが満タンか調べる機能,PUSH機能,スタックの中身を表示する機能を追加 を追加
スタックが空か調べる機能,POP機能を追加
スタック全体を削除する機能を追加

Step1: 空のスタックを作成

以下のようにmain.cを作成。

コンパイルして、実行してみる.

 $ gcc main.c
 $ ./a.out 

出力はないので合っているかわからんけど,エラーがでないから多分OK.

Step2: PUSH機能の追加

以下のようにmain.cを修正.

コンパイルからの実行.

 $ gcc main.c func.c
 $ ./a.out 
 Stack Overflow
 1
 2
 3
 4
 5

1回目から5回目のPUSHは成功して,6回目はオーバーフローになっているのでOK.

Step3: POP機能の追加

main.cを修正.

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
data 5 is removed
1
2
3
4

一番最後にPUSHした5が取り除かれているのでOK.

Step4: スタック全体を削除する機能を追加

main.cを修正.

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
data 5 is removed
1
2
3
4
There is no stack

スタックがなくなっているのでOK.目標達成!!

c言語での単一連結リスト ③削除編

はじめに

c言語での単一連結リストをステップバイステップで書いてみて,構造を学ぶ.
以下の手順で作っていく♪
①「表示編」リストの情報を表示する機能を実装
②「挿入編」リストに情報を追加する機能を実装
③「削除編」リストの情報を削除する機能を実装

目標

[2| 次のノードのアドレス]→[4| 次のノードのアドレス]→[5| 次のノードのアドレス]→[7| 次のノードのアドレス]→ [10|NULL]
まず,上のリストの先頭のノードを削除して以下のリストを作る.
[4| 次のノードのアドレス]→[5| 次のノードのアドレス]→[7| 次のノードのアドレス]→ [10|NULL]
次に,上のリストの最後尾のノードを削除して以下のリストを作る.
[4| 次のノードのアドレス]→[5| 次のノードのアドレス]→[7| NULL]
最後に,上のリストのノード間にノードを挿入して以下のリストを作る.
[4| 次のノードのアドレス]→[7| NULL]

Step3.1: リスト先頭の削除

以下のようにmain.cを作成。

コンパイルして、実行してみる.

 $ gcc main.c func.c
 $ ./a.out 
 before
  2
  4
  5
  7
 10
 after
  4
  5
  7
 10

先頭の2のデータを持つノードが削除されているので完了!

Step3.2: リスト最後尾の削除

まず最後尾のノードを探す.
次に最後尾の直前のノードの指すアドレスをNULLにする.
そして最後尾のノードを解放する.
この手順でmain.cを修正.

コンパイルからの実行.

 $ gcc main.c func.c
 $ ./a.out 
 before
  2
  4
  5
  7
 10
 after
  4
  5
  7

10のデータを持つ末尾のノードが削除されているからOK.

Step3.3: 中間のノードを削除

n番目のノードを削除するとき,n番目のノードを探す.
n-1番目のノードの指すアドレスをn+1番目のノードのアドレスにする.
n番目のノードを解放する.
この手順でmain.cを修正.

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
 before
  2
  4
  5
  7
 10
 after
  4
  7

5のデータを持つノードが削除されたからOK.

Step3.4: 一つの関数にまとめる

関数を一つにする.ついでに存在しないノードを削除の対象にしてしまったときのエラー処理も追加する. main.cを修正.

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
 before
  2
  4
  5
  7
 10
 after
  4
  7

さっきと同じ結果なのでOK.

Step3.5: ファイルを分割

いつも通り,ファイルを整理!

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
 before
  2
  4
  5
  7
 10
 after
  4
  7

さっきと同じ結果なのでOK.目標達成!!

c言語での単一連結リスト ②挿入編

はじめに

c言語での単一連結リストをステップバイステップで書いてみて,構造を学ぶ.
以下の手順で作っていく♪
①「表示編」リストの情報を表示する機能を実装
②「挿入編」リストに情報を追加する機能を実装
③「削除編」リストの情報を削除する機能を実装

目標

[5| NULL] まず,上のリストの先頭にノードを挿入して以下のリストを作る.
[2| 次のノードのアドレス]→[5| NULL]
次に,上のリストの最後尾にノードを挿入して以下のリストを作る.
[2| 次のノードのアドレス]→[5| 次のノードのアドレス]→ [10|NULL]
最後に,上のリストのノード間にノードを挿入して以下のリストを作る.
[2| 次のノードのアドレス]→[5| 次のノードのアドレス]→[7| 次のノードのアドレス]→ [10|NULL]

Step2.1: リスト先頭への挿入

以下のようにmain.cを作成。

コンパイルして、実行してみる.

$ gcc main.c func.c
$ ./a.out 
before
5
after
5

2のデータを持つノードが挿入されていない.main関数の中のhead変数は書き換わっていないからだと思われる. ってことで二重ポインタを使って書き直す.

コンパイルして、実行してみる.

$ gcc main.c func.c
$ ./a.out 
before
5
after
2
5

2のデータを持つノードが先頭に追加されているようなので完了!

Step2.2: リスト最後尾への挿入

以下のようにmain.cを修正.

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
before
 5
after
 2
 5
10

10のデータを持つノードが末尾に追加されているからOK.

Step2.3: ノード中間への挿入

以下のようにmain.cを修正.

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out 
before
 5
after
 2
 5
 7
10

7のデータを持つノードが3番目のノードとして挿入されたからOK.

Step2.4: 関数を一つにまとめる

挿入に関する3つの関数を作ったが,共通する内容が多いので一つにまとめてみる. 以下のようにmain.cを修正.

さっきと同じようにコンパイルして,同じ結果が得られたのでOK.

Step2.5: ファイル分割する

main.cが長いくなるのは嫌なので,関数は違うファイルにまとめる.すべてのプログラムはこんな感じ.(define.hは変更していない)

コンパイルからの実行.

$ gcc main.c func.c
$ ./a.out
before
 5
after
 2
 5
 7
10

2,5,7,10が順番に出力されてので,目標達成!!

c言語での単一連結リスト ①表示編

はじめに

c言語での単一連結リストをステップバイステップで書いてみて,構造を学ぶ.
以下の手順で作っていく♪
①「表示編」リストの情報を表示する機能を実装
②「挿入編」リストに情報を追加する機能を実装
③「削除編」リストの情報を削除する機能を実装

目標

[5| 次のノードのアドレス]→ [7|次のノードのアドレス]→ [10|NULL] 上のリストを手動で書き,リストの内容(今回は数字)を表示する関数を作成する。

Step1.1: 手動でのリストの作成と表示

以下のようにmain.cを作成。

コンパイルして、実行してみる.

5 0x7ffee390c4f0
7 0x7ffee390c4e0
10 (nil)

1列目には,あらかじめ決めておいた数字が書かれていて2列目にはアドレスっぽいのが書かれてるから大丈夫なはず.(nil)はよくわからん.

Step1.2: ノードの内容を順々に表示する

最初のノード(headと呼ぶ)から第2のノードへ,第2のノードから第3のノード,といったように順々に辿って内容を表示してみる.
以下のようにmain.cを修正.

実行した結果、5,7,10が出力されたからOK.

Step1.3: ループを使って簡単に書く

ノードの数だけprintf関数を書くのは大変なので,ループを使う.
以下のようにmain.cを修正.

実行した結果、5,7,10が出力されたからOK.

Step4:関数として書き直す

流用できるように関数にまとめる.ついでにノードの個数を数える機能を付け加える.
以下のようにmain.cを修正。

実行した結果、5,7,10が出力されたからOK.

Step5:ファイル分割する

構造体の宣言や関数を別ファイルにまとめちゃう.
以下の4つのファイルを作成。

これでコンパイルし,実行すると5,7,10が表示されたので目標達成!!

ラズベリーパイ3のメモ(ARMv8の実行状態,例外レベルとか)

実行状態 Execution state

・2種類の実行状態がある.

AArch32 state 32ビット汎用レジスタにアクセスできる
A32およびT32命令セットのみを使用できる
AArch64 state 64ビット汎用レジスタにアクセスできる
A64命令セットのみを使用できる

・(AArch32 stateにはさらに,A32 stateとT32 stateがあるが省略)

例外レベル Exception Level

・以下の表のように,4種類の例外レベルがある

例外レベル 一般的な使用用途
EL0 アプリケーション
EL1 OSカーネル
EL2 ハイパーバイザ
EL3 セキュアモニタ

・例外レベルが上がるに従い,アクセスできるシステムレジスタが増える

実行状態の変更方法

・AArch32およびAArch64状態の切り替えは、例外の境界でのみ発生する
・より高い例外レベルへリターンしたときに,AArch32⇒AArch64に変更できる
(例)
EL0レベルで例外が発生しEL1レベルにリターンしたときに,AArch32⇒AArch64に変更できる
・より低い例外レベルへリターンしたときに,AArch64⇒AArch32に変更できる
(例)
EL3レベルで例外が発生しEL2レベルにリターンしたときに,AArch64⇒AArch32に変更できる

スタックポインタレジスタ Stack Pointer register

・以下の表のように,各例外レベルに個別のスタックポインタがある

例外レベル SPレジスタの名前(64bit)
EL0 SP_EL0
EL1 SP_EL1
EL2 SP_EL2
EL3 SP_EL3

・2通りのSPレジスタの選択方法(なぜ2通りあるのか?)

EL0t EL0レベルでSP_EL0を使用
EL1t EL1レベルでSP_EL0を使用
EL2t EL2レベルでSP_EL0を使用
EL3t EL3レベルでSP_EL0を使用
EL0h なし
EL1h SP_EL1を使用
EL2h SP_EL2を使用
EL3h SP_EL3を使用

例外ベクタテーブル

例外が発生した例外レベル Synchronous IRQ or vIRQ FIQ or vFIQ SError or vSError
現在の例外レベル(SP_EL0を使用したい) 0x000 0x080 0x100 0x180
現在の例外レベル(SP_ELxを使用したい) 0x200 0x280 0x300 0x380
? 0x400 0x480 0x500 0x580

?|0x600|0x680|0x700|0x780|

アセンブラ(ARM)

レジスタ

VBAR_EL1, Vector Base Address Register (p.2745)

EL1で発生する任意の例外のための,ベクタテーブルのベースアドレスを格納



sctlr_el1

命令

add

足し算

add  x0, x1, x2           @ x0=x1+x2

sub

Subtractの略.引き算

sub  x0, x1, x2           @ x0=x1-x2
sub  x0, x1, #3           @ x0=x1-3

subs

引き算とNZCVレジスタの更新

subs  x0, x1, #3           @ x0=x1-3, x0が0ならNZCVレジスタのフラグが立つ

and

論理和

and  x0, x1, x2           @ x0=x1&x2

mov

Moveの略.値のコピー

mov  x0, #1               @ x0=1

ldr

Load registerの略

ldr  x0, [x1]             @ x1番地の値を,x0レジスタにロード
ldr  x0, =0x1000          @ 0x1000を,x0レジスタにロード
ldr  x0, [x1], #8         @ x1番地の値を,x0レジスタにロードした後,x1=x1+8に更新される

str

Store registerの略

str  x0, [x1]             @ x0レジスタの値を,x1番地にストア
str  x0, [x1, #8]             @ x0レジスタの値を,x1+8番地にストア
str  x0, [x1], #8         @ x0レジスタの値を,x1番地にストアした後,x1=x1+8に更新される

adr

ラベルの相対アドレスを,ターゲットレジスタにロード

adr  x0, label            @ labelの示すアドレスを,x0レジスタにロード

mrs

の略.システムレジスタのデータを,汎用レジスタにロードする.

mrs  x0, mpidr_el1        @ mpidr_el1レジスタのデータを,x0レジスタにロード 

msr

の略.汎用レジスタのデータを,システムレジスタにロードする.

msr  sctlr_el1, x0        @ x0レジスタのデータを,sctlr_el1レジスタにロード 

bl

Branch and linkの略

b.gt

Branch if greater thanの略

subs  x1, x1, #8
b.gt  label               @ x1が0より大きければ,ラベルlabelへジャンプ

lsr

Logical shift rightの略

lsr  x0, x0, #2               @ x0を右に2ビット分シフト

stp

Store pair of registersの略

stp  x0, x1, [sp, #48]               @ x0, x1をsp+48番地に格納(spの値は変わらない)

ldp

Load pair of registersの略

ldp  x0, x1, [sp, #48]               @ sp+48番地からの128ビットをx0, x1に格納

unionとかenum

共用体

  • 基本的には,データAとデータBは違うアドレスに置く
  • しかし,同じアドレスに置くこともできる
  • その操作を行うのが共用体で,unionというキーワードを用いる
例(共用体を使ってみる)

とりあえず,どんな感じで使うのか見てみる

#include <stdio.h>

int main(void){
	union sample{
		char 	ch;
		short 	sh;
		int	it;
	};

	union sample u1;
	
	u1.it = 0x12345678;
	printf("%x\n", u1.ch);
	printf("%x\n", u1.sh);
	printf("%x\n", u1.it);

	return 0;
}

上のファイルをコンパイルして実行すると以下の結果が得られる.

78
5678
12345678

確かに,1つの変数を触っただけなのに,他の変数の値も更新されている.

例(typedefと併用してみる)

unionはtypedefと一緒に使うことが多いそうなので,試してみる.

#include <stdio.h>

int main(void){
	typedef union sample{
		char 	ch;
		short 	sh;
		int	it;
	}smpl;

	smpl u1;
	
	u1.it = 0x12345678;
	printf("%x\n", u1.ch);
	printf("%x\n", u1.sh);
	printf("%x\n", u1.it);

	return 0;
}

変数を宣言するときに,いちいちunionと言わなくてよくなった.もちろん,結果はさっきと同じ.

どう使うのか?何がうれしいのか?

メモリの節約に関係しているそうだが,詳細は不明.いい例があったら今後追加する

列挙型データ

  • define ~をまとめて,見栄えをよくするための機能
  • つまり,定数をメンバにもつデータ型(構造体?)
  • 各定数の値はint型
  • enumというキーワードを用いる
例(enumを使ってみる)

とりあえず,どんな感じで使うのか見てみる

#include <stdio.h>

enum coltyp{  //値を指定しなければ上から0, 1, ... が割り振られる
	RED,
	BLUE,
	BLACK,
	WHITE
}color;

int main(void){
	color = BLUE;
	printf("%d\n", color);
	color = WHITE;
	printf("%d\n", color);

	return 0;
}

上のファイルをコンパイルして実行すると以下の結果が得られる.

0
1
3