大学生エンジニアの技術ブログ

Technical blog

Learn More
投稿日:2019年01月27日

【アセンブラ言語】連結リストでinsertを実現してみたよ!

ゴール

連結リストにおいて、insertを実現する。

 

前提知識の整理

 

レコード

ここでは連結リストの1つの要素をレコードとして定義する。

 

レコード = 1語のデータ(data) + 1語のポインタ(next)

 

仮に1000番地という番地があってそのレコードの中身としてはdataとnextが入っている。

ポインタの中身としては、次のレコードの番地が入る。

 

HEAD番地

ここでいうHEAD番地というのは

最初のレコードの番地のことを指す。

 

 

Mallocとヒープ領域

今回の実装ではMallocとヒープ領域という概念を扱うので整理しておこう。

まずヒープだが、「動的に増減可能なメモリ領域」のことを指す。動的にメモリを増減させるというのは、mallocを関数等をもちいて、メモリ領域を確保することです。mallocはメモリ領域を増やし、deleateはメモリ領域を減らす関数です。

 

今回の設定

1.HEAP番地から256語をヒープ領域とする。

2.HEAP-1番地をHPとする。(未使用領域の先頭番地として扱う)

 

 

DCは定数定義命令でHP番地にHEAPを格納。DSは領域確保命令でHEAP番地から256語を確保している。

 

Mallocの実現

 

 

[パラメーターの説明]

 

•GR1(入力パラメーター):確保したい語数

•GR2(返り値):割り当てた領域の先頭番地

•HP:未使用領域の先頭番地

 

 

 

 

MALLOCの動作としては、現在のHPがGR2に確保され、HPがHP+GR1に更新されるという処理がなされている。これは新しく確保した分のメモリを更新することで、残りのヒープ領域(動的に増減可能なメモリ領域)を把握する為に行なっています。すごくわかりづらくて申し訳ないですが、この処理を頭の中で考えたときのメモを一応貼っておきます。

 

insertの考え方

ここでようやくinsertに関する内容に入っていきます。

 

リストに挿入する箱

リストに挿入する箱の中身は、データ(data)が1語、ポインタ(next)が1語である。これらはmallocで返されるGR2番地にdata、GR2+1番地にnextを格納する。(GR2は割り当てた先頭番地)

 

 

 

パラメータ

入力パラメーターGR1:挿入する1つ前の箱の番地

入力パラメーターGR2:挿入する箱のdata値

 

 

insertのフロー

実際に箱を挿入するにあたってフローがあるので、整理する。

 

1:Mallocで新しい箱の作成

2:新しい箱にdataを挿入する

3:1つ前の箱のnextを更新

4:挿入する箱のnextを更新

 

 

 

コードで実装する

 

 

MALLOCを実行すると、GR2に新たな箱の先頭番地が入り、GR1には割り当てる語数が再度ストアされる。

 

 

 

感想・気づき

次回の記事ではdeleteについて書きます。

最後まで読んで頂き
ありがとうございました。
SNS等でのシェアが頂ければ幸いです。

Created by KATUO - Copyright 2019