Doubly-linked list/Definition: Difference between revisions
Content added Content deleted
(→{{header|C sharp|C#}}: Added usage notes about framework class; adjusted style) |
(Add task to ARM assembly Raspberry pi) |
||
Line 132: | Line 132: | ||
Empty from tail: saw I cat a it Was |
Empty from tail: saw I cat a it Was |
||
</pre> |
</pre> |
||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi}} |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
|||
/* program defDblList.s */ |
|||
/* Constantes */ |
|||
.equ STDOUT, 1 @ Linux output console |
|||
.equ EXIT, 1 @ Linux syscall |
|||
.equ READ, 3 |
|||
.equ WRITE, 4 |
|||
/*******************************************/ |
|||
/* Structures */ |
|||
/********************************************/ |
|||
/* structure Doublylinkedlist*/ |
|||
.struct 0 |
|||
dllist_head: @ head node |
|||
.struct dllist_head + 4 |
|||
dllist_tail: @ tail node |
|||
.struct dllist_tail + 4 |
|||
dllist_fin: |
|||
/* structure Node Doublylinked List*/ |
|||
.struct 0 |
|||
NDlist_next: @ next element |
|||
.struct NDlist_next + 4 |
|||
NDlist_prev: @ previous element |
|||
.struct NDlist_prev + 4 |
|||
NDlist_value: @ element value or key |
|||
.struct NDlist_value + 4 |
|||
NDlist_fin: |
|||
/* Initialized data */ |
|||
.data |
|||
szMessInitListe: .asciz "List initialized.\n" |
|||
szCarriageReturn: .asciz "\n" |
|||
szMessErreur: .asciz "Error detected.\n" |
|||
/* UnInitialized data */ |
|||
.bss |
|||
dllist1: .skip dllist_fin @ list memory place |
|||
/* code section */ |
|||
.text |
|||
.global main |
|||
main: |
|||
ldr r0,iAdrdllist1 |
|||
bl newDList @ create new list |
|||
ldr r0,iAdrszMessInitListe |
|||
bl affichageMess |
|||
ldr r0,iAdrdllist1 @ list address |
|||
mov r1,#10 @ value |
|||
bl insertHead @ insertion at head |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
ldr r0,iAdrdllist1 |
|||
mov r1,#20 |
|||
bl insertTail @ insertion at tail |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
ldr r0,iAdrdllist1 @ list address |
|||
mov r1,#10 @ value to after insered |
|||
mov r2,#15 @ new value |
|||
bl insertAfter |
|||
cmp r0,#-1 |
|||
beq 99f |
|||
b 100f |
|||
99: |
|||
ldr r0,iAdrszMessErreur |
|||
bl affichageMess |
|||
100: @ standard end of the program |
|||
mov r7, #EXIT @ request to exit program |
|||
svc 0 @ perform system call |
|||
iAdrszMessInitListe: .int szMessInitListe |
|||
iAdrszMessErreur: .int szMessErreur |
|||
iAdrszCarriageReturn: .int szCarriageReturn |
|||
iAdrdllist1: .int dllist1 |
|||
/******************************************************************/ |
|||
/* create new list */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
newDList: |
|||
push {r1,lr} @ save registers |
|||
mov r1,#0 |
|||
str r1,[r0,#dllist_tail] |
|||
str r1,[r0,#dllist_head] |
|||
pop {r1,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* list is empty ? */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r0 return 0 if empty else return 1 */ |
|||
isEmpty: |
|||
//push {r1,lr} @ save registers |
|||
ldr r0,[r0,#dllist_head] |
|||
cmp r0,#0 |
|||
movne r0,#1 |
|||
//pop {r1,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* insert value at list head */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains value */ |
|||
insertHead: |
|||
push {r1-r4,lr} @ save registers |
|||
mov r4,r0 @ save address |
|||
mov r0,r1 @ value |
|||
bl createNode |
|||
cmp r0,#-1 @ allocation error ? |
|||
beq 100f |
|||
ldr r2,[r4,#dllist_head] @ load address first node |
|||
str r2,[r0,#NDlist_next] @ store in next pointer on new node |
|||
mov r1,#0 |
|||
str r1,[r0,#NDlist_prev] @ store zero in previous pointer on new node |
|||
str r0,[r4,#dllist_head] @ store address new node in address head list |
|||
cmp r2,#0 @ address first node is null ? |
|||
strne r0,[r2,#NDlist_prev] @ no store adresse new node in previous pointer |
|||
streq r0,[r4,#dllist_tail] @ else store new node in tail address |
|||
100: |
|||
pop {r1-r4,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* insert value at list tail */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains value */ |
|||
insertTail: |
|||
push {r1-r4,lr} @ save registers |
|||
mov r4,r0 @ save list address |
|||
mov r0,r1 @ value |
|||
bl createNode @ create new node |
|||
cmp r0,#-1 |
|||
beq 100f @ allocation error |
|||
ldr r2,[r4,#dllist_tail] @ load address last node |
|||
str r2,[r0,#NDlist_prev] @ store in previous pointer on new node |
|||
mov r1,#0 @ store null un next pointer |
|||
str r1,[r0,#NDlist_next] |
|||
str r0,[r4,#dllist_tail] @ store address new node on list tail |
|||
cmp r2,#0 @ address last node is null ? |
|||
strne r0,[r2,#NDlist_next] @ no store address new node in next pointer |
|||
streq r0,[r4,#dllist_head] @ else store in head list |
|||
100: |
|||
pop {r1-r4,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* insert value after other element */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains value to search*/ |
|||
/* r2 contains value to insert */ |
|||
insertAfter: |
|||
push {r1-r5,lr} @ save registers |
|||
mov r4,r0 @ save list address |
|||
bl searchValue @ search this value in r1 |
|||
cmp r0,#-1 |
|||
beq 100f @ not found -> error |
|||
mov r5,r0 @ save address of node find |
|||
mov r0,r2 @ new value |
|||
bl createNode @ create new node |
|||
cmp r0,#-1 |
|||
beq 100f @ allocation error |
|||
ldr r2,[r5,#NDlist_next] @ load pointer next of find node |
|||
str r0,[r5,#NDlist_next] @ store new node in pointer next |
|||
str r5,[r0,#NDlist_prev] @ store address find node in previous pointer on new node |
|||
str r2,[r0,#NDlist_next] @ store pointer next of find node on pointer next on new node |
|||
cmp r2,#0 @ next pointer is null ? |
|||
strne r0,[r2,#NDlist_prev] @ no store address new node in previous pointer |
|||
streq r0,[r4,#dllist_tail] @ else store in list tail |
|||
100: |
|||
pop {r1-r5,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* search value */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the list structure */ |
|||
/* r1 contains the value to search */ |
|||
/* r0 return address of node or -1 if not found */ |
|||
searchValue: |
|||
push {r2,lr} @ save registers |
|||
ldr r0,[r0,#dllist_head] @ load first node |
|||
1: |
|||
cmp r0,#0 @ null -> end search not found |
|||
moveq r0,#-1 |
|||
beq 100f |
|||
ldr r2,[r0,#NDlist_value] @ load node value |
|||
cmp r2,r1 @ equal ? |
|||
beq 100f |
|||
ldr r0,[r0,#NDlist_next] @ load addresse next node |
|||
b 1b @ and loop |
|||
100: |
|||
pop {r2,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* Create new node */ |
|||
/******************************************************************/ |
|||
/* r0 contains the value */ |
|||
/* r0 return node address or -1 if allocation error*/ |
|||
createNode: |
|||
push {r1-r7,lr} @ save registers |
|||
mov r4,r0 @ save value |
|||
@ allocation place on the heap |
|||
mov r0,#0 @ allocation place heap |
|||
mov r7,#0x2D @ call system 'brk' |
|||
svc #0 |
|||
mov r5,r0 @ save address heap for output string |
|||
add r0,#NDlist_fin @ reservation place one element |
|||
mov r7,#0x2D @ call system 'brk' |
|||
svc #0 |
|||
cmp r0,#-1 @ allocation error |
|||
beq 100f |
|||
mov r0,r5 |
|||
str r4,[r0,#NDlist_value] @ store value |
|||
mov r2,#0 |
|||
str r2,[r0,#NDlist_next] @ store zero to pointer next |
|||
str r2,[r0,#NDlist_prev] @ store zero to pointer previous |
|||
100: |
|||
pop {r1-r7,lr} @ restaur registers |
|||
bx lr @ return |
|||
/******************************************************************/ |
|||
/* display text with size calculation */ |
|||
/******************************************************************/ |
|||
/* r0 contains the address of the message */ |
|||
affichageMess: |
|||
push {r0,r1,r2,r7,lr} @ save registers |
|||
mov r2,#0 @ counter length */ |
|||
1: @ loop length calculation |
|||
ldrb r1,[r0,r2] @ read octet start position + index |
|||
cmp r1,#0 @ if 0 its over |
|||
addne r2,r2,#1 @ else add 1 in the length |
|||
bne 1b @ and loop |
|||
@ so here r2 contains the length of the message |
|||
mov r1,r0 @ address message in r1 |
|||
mov r0,#STDOUT @ code to write to the standard output Linux |
|||
mov r7, #WRITE @ code call system "write" |
|||
svc #0 @ call system |
|||
pop {r0,r1,r2,r7,lr} @ restaur registers |
|||
bx lr @ return |
|||
</lang> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
see [[Doubly-linked list/AutoHotkey]] |
see [[Doubly-linked list/AutoHotkey]] |