어셈블리 Linked List Operation (insert/remove/sort/search/empty)

0. 개 관

 하나의 노드는 데이터 값과 다음 노드의 주소 값을 엔트리로 갖는다. 다음 노드의 주소 값이 -1일 경우에는 NULL을 가리키는 것으로 생각하고, 주소 값이 0일 경우에는 노드할당이 해제 혹은 초기화 된 것으로 코딩하였다.

-데이터 영역 레이블

start : 노드의 개수

start_point : 첫 노드의 주소

dArea : linked list가 저장될 영역

1. 소스 및 주석

-insert

insert

ADRr1, start;r1=address_of_start

LDRr2, [r1, #0];r2=number_of_items

CMP r2, #25;is_full?

BLEQinsert_full

CMPr2, #0;is_empty?

BEQinsert_empty

ADRr3, start_point;r3=address_of_start_point

LDRr4, [r3, #0];r4=pointer

findLastSUBSr2, r2, #1

MOVr3, r4

LDRr4, [r3, #4]!

BNEfindLast;r3=address_of_recor_last

;r4=data_of_record_last

ADDr3, r3, #8

SUBr6, r3, #4;next_address

LDRr5, [r3, #0]

SUBr3, r3, #8

CMPr5, #0;if_(next_pointer==0)_free_space

BEQcreateNode

ADRr3, dArea

ADDr3, r3, #4

findEmptyLDRr5, [r3, #0]

CMPr5, #0

ADDr3, r3, #8

BNEfindEmpty

SUBr6, r3, #4

SUBr3, r3, #8

createNodeSTRr6, [r3, #0]

STRr0, [r6, #0];store data r0

MOVr0, #-1

STRr0, [r6, #4];store next pointer

LDRr2, [r1, #0]

ADDr2, r2, #1

STRr2, [r1, #0];number increase

MOVr0, #1

Breturn0

insert_emptyADR r7, dArea;r7 =data area address

STRr0, [r7, #0]

ADRr8, start_point

STRr7, [r8, #0];start_point_address setting

ADDr5, r7, #8

MOVr8, #-1

STRr8, [r7, #4];insert_null

LDRr2, [r1, #0]

ADDr2, r2, #1

STRr2, [r1, #0];number_increase

MOVr0, #1;return_ok

Breturn0

insert_fullMOVr0, #0

Breturn0

-remove

removeADRr1, start

LDRr2, [r1, #0];r2=number_of_items

ADRr3, start_point

LDRr4, [r3, #0];r4=address_of_first_record

findItemSUBSr2, r2, #1

CMPr2, #-1

BEQnotfind_for_remove

MOVr3, r4;r3=address_of_record_first

LDRr4, [r3, #0];r4=data_of_record

CMP r0, r4

LDRr4, [r3, #4]!;r4=next_address_of_record

BEQremoving

MOVr7, r3;r7=before_address_of_record_last

BNEfindItem

removingADRr5, start_point

LDRr6, [r5, #0];r6=address_of_first_record

ADDr6, r6, #4

CMPr6, r3;r3=address_of_record

BEQremove_first

BNEremove_othrer

remove_firstSTRr4, [r5, #0]

MOVr0, #1;remove_ok

MOVr1, #0

STRr1, [r3, #0];space_free

ADRr1, start

LDRr2, [r1, #0];r2=number_of_items

SUBr2, r2, #1

STRr2, [r1, #0];decrease_number_of_item

Breturn0

remove_othrerSTRr4, [r7, #0]

MOVr0, #1;remove_ok

MOVr1, #0

STRr1, [r3, #0];space_free

ADRr1, start

LDRr2, [r1, #0];r2=number_of_items

SUBr2, r2, #1

STRr2, [r1, #0];decrease_number_of_item

Breturn0

notfind_for_remove

MOVr0, #0;remove_no

Breturn0

-sort

sortADR r1, start

LDRr2, [r1, #0];r2=number_of_items

compareADRr3, start_point

LDRr4, [r3, #0];r4=address_of_first_record

SUBSr2, r2, #1

ADDr9, r2, #1

compare0SUBSr9, r9, #1

MOVr3, r4;r3=address_of_record_first

LDRr4, [r3, #0];r4=data_of_record

CMPr9, r2

CMPNEr8, r4

LDRr5, [r3, #4]!;r5=next_address_of_record

STMFDsp!, {r0-r12, lr}

BLGTswap

LDMFDsp!, {r0-r12, lr}

SUBr7, r3, #4;r7=before_address_of_record_first

MOVr8, r4;r8=before_address_of_data

MOVr4, r5

CMPr9, #0

BNEcompare0

CMPr2, #1

BNEcompare

Breturn0

swapMOVr0, r4;r0=temp_data

SUBr1, r3, #4

STRr8, [r1, #0]

STRr0, [r7, #0]

Breturn0

-search

searchADRr1, start;r1=address_of_start

LDRr2, [r1, #0];r2=number_of_items

ADRr3, start_point;r3=address_of_start_point

LDRr4, [r3, #0];r4=pointer

findDataSUBr2, r2, #1

MOVr3, r4

LDRr4, [r3, #0];r4=data_of_record

CMPr0, r4

BEQfindIt

LDRr4, [r3, #4]!

CMPr2, #0

BNEfindData

MOVr0, #0;return_value 0

MOVpc, lr

findItMOVr0, #1;return_value 1

MOVr0, lr

STRr0, [r4, #0];store data r0

ADDr0, r4, #8

-empty

emptyADRr1, start;r1=address_of_start

LDRr2, [r1, #0];r2=number_of_items

CMPr2, #0

BEQempty_state

MOVr0, #0;return_value

MOVpc, lr

empty_stateMOVr0, #1;return_value

MOVpc, lr

2. 소스 분석

-insert

삽입부는 위의 소스에 대해 간략히 설명하면, start label에서 노드의 개수를 읽어 와서 empty상태인지 full상태인지를 확인한다.

만약 empty라면(즉, 노드의 개수가 0이라면 insert_empty라는 label로 branch한다. 여기서 dArea영역의 첫 주소 값을 읽어 와서 이 주소 값을 start_point라는 레이블이 가리키는 영역에 linked list의 첫 노드 값을 저장하고, 노드 첫 부분에서는 r0에 있는 insert하려는 값을 저장하고, 뒷부분에는 NULL값 (여기서는 -1)을 집어넣고, 1을 return한다.

만약 full인 상태인 경우는 0을 return한다.

empty도 아니고 full도 아니면 그대로 내려가 findLast 레이블에 들어가 루프를 돈다. start_point label에서 처음 주소를 읽어 와서 linked list의 루프를 돌면 r3에는 가장 마지막 노드의 뒷부분 주소, r4에는 가장 마지막 노드의 값(즉, 다음 링크의 주소인데 마지막 노드이므로 이 경우에는 NULL값인 -1)이 저장되는데, r3에서 8을 더한 값 즉, 다음 메모리 노드 영역을 탐지하여 0이면 free space이므로 그 자리에 삽입하기 위해 crateNode label 로 branch한다.

만약 다음 노드 위치가 free space가 아니라 사용 중이라면, findEmpty label로 가게 되고, 비어 있는 공간을 dArea 처음 영역부터 찾는다. 비어 있다는 것은 노드의 뒷부분이 0이면 free space 로 간주한다. (이미 앞서 full, 즉, 25개의 노드가 할당되어 있지는 않으므로 dArea영역이 끝나기 전까지 비어있는 노드를 최소한 한 개 이상은 찾을 것이다.)

삽입할 위치를 찾았으면 createNode에서 다음 주소 값(r6)을 r3에 저장된 주소 저장한다. 그리고 r6에 저장된 주소에 데이터 r0와 r6+#4의 주소에 NULL값 -1을 각각 집어넣는다. 그리고 노드의 개수 start에 1을 증가시키고 r0에 1을 저장하여 1을 return 한다.

-remove

삭제부에 대해 간략히 설명하면, start label에서 노드의 개수를 읽고, start_point label에서 첫 번째 노드 주소를 읽어온다.

그리고 루프를 돌면서 remove하려는 data가 어디에 있는지 search를 한다. 만약 돌면서 노드의 개수보다 작아질 때까지 찾지 못하면 notfind_for_remove label로 가서 0을 return 한다. search할 때에는 이전 노드와 삭제하려는 노드의 정보를 가지고 있어야 한다. 왜냐하면 삭제하려는 노드의 포인터(다음 링크 주소 값)를 이전 노드의 포인터(다음 링크 주소 값)로 옮기고, 삭제 노드의 포인터는 0으로 바꾸어줘야 한다. (이후 만약에 있을 insert시 이 위치에 새로운 노드를 생성 할 수 있게 하기 위해서)

만약 search하면 removing label로 가게 되고, 거기에서 삭제하려는 노드가 linked list의 시작 노드인지 아닌지를 compare한다.

그 결과 삭제하려는 노드가 가장 linked list의 시작노드라면 remove_first label로 간다. 그리고

start_point label의 값을 2번째 노드의 주소 값으로 바꾸고 처음 노드의 포인터(다음 링크 주소 값)를 0으로 바꾼다. start(노드의 개수) label의 값을 하나 감소하여 저장한다. 그리고 r0에 1을 저장하여 return 한다.

만약 삭제하려는 노드가 linked list의 시작 노드가 아니라면, remove_other label로 간다. 이 전 노드의 포인터(다음 링크 주소값)에 삭제하려는 노드의 포인터(다음 링크 주소값)을 저장하고, 삭제 노드의 포인터(다음 링크 주소 값)을 0으로 저장한다. start(노드의 개수) label의 값을 하나 감소하여 저장한다. 그리고 r0에 1을 저장하여 return 한다.

-sort

정렬부는 삽입 정렬을 사용하였다. 이중 루프를 돌게 하여 compare label과 그 안의 루프인 compare0을 두었다. compare0의 경우 루프 도는 회수는 compare 루프 한번 돌면 compare0가 돌아야할 루프는 하나씩 더 줄어들게 하였다. compare0는 linked list를 한번씩 compare에 정해지는 만큼 (처음 루프 수행보다 하나씩 줄어든다)까지 비교작업을 한다. 여기서 이전노드가 그 다음 노드보다 클 경우에는 swap label로 가서 두 개의 data값을 바꾼다. 그렇지 않으면 그냥 그대로 루프를 돌아 비교작업을 한다.

-search

탐색부는 시작주소부터 linked list를 읽는데 데이터 영역을 r4에 읽고 탐색하려는 값과 동일하면(r0와 비교하여) findIt label로 가서 r0를 1로 바꿔 return 시킨다.

만약 노드의 개수만큼 탐색하였는데도(즉, NULL값까지) 탐색 되지 않았다면 r0를 0으로 바꿔 return 시킨다.

-empty

empty는 start( 노드의 개수)가 0이면 1을 return 시키고, 0이 아니면 0을 return 시킨다.

1)메모리 영역

2. 첫번째 Data 삽입

3. Test1 수행 : insert(1, 3, 5, 7, 2, 4, 6)

4. Test2 수행 : remove(1, 2, 3, 4)

5. Test3 수행 : sorting 후 메모리 영역 변화(data value 변함)

6. Test4 수행 : data3 search 후 register return value

7. Test5 수행 : data 5, 6, 7 remove 후 시작주소와 노드 갯수 메모리값

8. Test6 : empty 수행 후 register return value