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)
命令
add
足し算
add x0, x1, x2 @ x0=x1+x2
sub
Subtractの略.引き算
sub x0, x1, x2 @ x0=x1-x2 sub x0, x1, #3 @ x0=x1-3
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に更新される
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というキーワードを用いる