765 lines
25 KiB
Plaintext
765 lines
25 KiB
Plaintext
/* ARM assembly Raspberry PI */
|
|
/* program avltree2.s */
|
|
|
|
/* REMARK 1 : this program use routines in a include file
|
|
see task Include a file language arm assembly
|
|
for the routine affichageMess conversion10
|
|
see at end of this program the instruction include */
|
|
|
|
/*******************************************/
|
|
/* Constantes */
|
|
/*******************************************/
|
|
.equ STDOUT, 1 @ Linux output console
|
|
.equ EXIT, 1 @ Linux syscall
|
|
.equ WRITE, 4 @ Linux syscall
|
|
.equ BRK, 0x2d @ Linux syscall
|
|
.equ CHARPOS, '@'
|
|
|
|
.equ NBVAL, 12
|
|
|
|
/*******************************************/
|
|
/* Structures */
|
|
/********************************************/
|
|
/* structure tree */
|
|
.struct 0
|
|
tree_root: @ root pointer (or node right)
|
|
.struct tree_root + 4
|
|
tree_size: @ number of element of tree
|
|
.struct tree_size + 4
|
|
tree_suite:
|
|
.struct tree_suite + 12 @ for alignement to node
|
|
tree_fin:
|
|
/* structure node tree */
|
|
.struct 0
|
|
node_right: @ right pointer
|
|
.struct node_right + 4
|
|
node_left: @ left pointer
|
|
.struct node_left + 4
|
|
node_value: @ element value
|
|
.struct node_value + 4
|
|
node_height: @ element value
|
|
.struct node_height + 4
|
|
node_parent: @ element value
|
|
.struct node_parent + 4
|
|
node_fin:
|
|
/* structure queue*/
|
|
.struct 0
|
|
queue_begin: @ next pointer
|
|
.struct queue_begin + 4
|
|
queue_end: @ element value
|
|
.struct queue_end + 4
|
|
queue_fin:
|
|
/* structure node queue */
|
|
.struct 0
|
|
queue_node_next: @ next pointer
|
|
.struct queue_node_next + 4
|
|
queue_node_value: @ element value
|
|
.struct queue_node_value + 4
|
|
queue_node_fin:
|
|
/*******************************************/
|
|
/* Initialized data */
|
|
/*******************************************/
|
|
.data
|
|
szMessPreOrder: .asciz "PreOrder :\n"
|
|
szCarriageReturn: .asciz "\n"
|
|
/* datas error display */
|
|
szMessErreur: .asciz "Error detected.\n"
|
|
szMessKeyDbl: .asciz "Key exists in tree.\n"
|
|
szMessInsInv: .asciz "Insertion in inverse order.\n"
|
|
/* datas message display */
|
|
szMessResult: .asciz "Ele: @ G: @ D: @ val @ h @ pere @\n"
|
|
sValue: .space 12,' '
|
|
.asciz "\n"
|
|
/*******************************************/
|
|
/* UnInitialized data */
|
|
/*******************************************/
|
|
.bss
|
|
sZoneConv: .skip 24
|
|
stTree: .skip tree_fin @ place to structure tree
|
|
stTree1: .skip tree_fin @ place to structure tree
|
|
stQueue: .skip queue_fin @ place to structure queue
|
|
/*******************************************/
|
|
/* code section */
|
|
/*******************************************/
|
|
.text
|
|
.global main
|
|
main:
|
|
mov r8,#1 @ node tree value
|
|
1: @ loop insertion in order
|
|
ldr r0,iAdrstTree @ structure tree address
|
|
mov r1,r8
|
|
bl insertElement @ add element value r1
|
|
cmp r0,#-1
|
|
beq 99f
|
|
//ldr r3,iAdrstTree @ tree root address (begin structure)
|
|
//ldr r0,[r3,#tree_root]
|
|
//ldr r1,iAdrdisplayElement @ function to execute
|
|
//bl preOrder
|
|
add r8,#1 @ increment value
|
|
cmp r8,#NBVAL @ end ?
|
|
ble 1b @ no -> loop
|
|
|
|
ldr r0,iAdrstTree @ structure tree address
|
|
mov r1,#11 @ verif key dobble
|
|
bl insertElement @ add element value r1
|
|
cmp r0,#-1
|
|
bne 2f
|
|
ldr r0,iAdrszMessErreur
|
|
bl affichageMess
|
|
2:
|
|
ldr r0,iAdrszMessPreOrder @ load verification
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree @ tree root address (begin structure)
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl preOrder
|
|
|
|
|
|
ldr r0,iAdrszMessInsInv
|
|
bl affichageMess
|
|
mov r8,#NBVAL @ node tree value
|
|
3: @ loop insertion inverse order
|
|
ldr r0,iAdrstTree1 @ structure tree address
|
|
mov r1,r8
|
|
bl insertElement @ add element value r1
|
|
cmp r0,#-1
|
|
beq 99f
|
|
sub r8,#1 @ increment value
|
|
cmp r8,#0 @ end ?
|
|
bgt 3b @ no -> loop
|
|
|
|
ldr r0,iAdrszMessPreOrder @ load verification
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree1 @ tree root address (begin structure)
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl preOrder
|
|
|
|
@ search value
|
|
ldr r0,iAdrstTree1 @ tree root address (begin structure)
|
|
mov r1,#11 @ value to search
|
|
bl searchTree
|
|
cmp r0,#-1
|
|
beq 100f
|
|
mov r2,r0
|
|
ldr r0,iAdrszMessKeyDbl @ key exists
|
|
bl affichageMess
|
|
@ suppresssion previous value
|
|
mov r0,r2
|
|
ldr r1,iAdrstTree1
|
|
bl supprimer
|
|
|
|
ldr r0,iAdrszMessPreOrder @ verification
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree1 @ tree root address (begin structure)
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl preOrder
|
|
|
|
b 100f
|
|
99: @ display error
|
|
ldr r0,iAdrszMessErreur
|
|
bl affichageMess
|
|
100: @ standard end of the program
|
|
mov r7, #EXIT @ request to exit program
|
|
svc 0 @ perform system call
|
|
iAdrszMessPreOrder: .int szMessPreOrder
|
|
iAdrszMessErreur: .int szMessErreur
|
|
iAdrszCarriageReturn: .int szCarriageReturn
|
|
iAdrstTree: .int stTree
|
|
iAdrstTree1: .int stTree1
|
|
iAdrstQueue: .int stQueue
|
|
iAdrdisplayElement: .int displayElement
|
|
iAdrszMessInsInv: .int szMessInsInv
|
|
/******************************************************************/
|
|
/* insert element in the tree */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the tree structure */
|
|
/* r1 contains the value of element */
|
|
/* r0 returns address of element or - 1 if error */
|
|
insertElement: @ INFO: insertElement
|
|
push {r1-r8,lr} @ save registers
|
|
mov r7,r0 @ save head
|
|
mov r0,#node_fin @ reservation place one element
|
|
bl allocHeap
|
|
cmp r0,#-1 @ allocation error
|
|
beq 100f
|
|
mov r5,r0
|
|
str r1,[r5,#node_value] @ store value in address heap
|
|
mov r3,#0
|
|
str r3,[r5,#node_left] @ init left pointer with zero
|
|
str r3,[r5,#node_right] @ init right pointer with zero
|
|
str r3,[r5,#node_height] @ init balance with zero
|
|
ldr r2,[r7,#tree_size] @ load tree size
|
|
cmp r2,#0 @ 0 element ?
|
|
bne 1f
|
|
str r5,[r7,#tree_root] @ yes -> store in root
|
|
b 4f
|
|
1: @ else search free address in tree
|
|
ldr r3,[r7,#tree_root] @ start with address root
|
|
2: @ begin loop to insertion
|
|
ldr r4,[r3,#node_value] @ load key
|
|
cmp r1,r4
|
|
beq 6f @ key equal
|
|
blt 3f @ key <
|
|
@ key > insertion right
|
|
ldr r8,[r3,#node_right] @ node empty ?
|
|
cmp r8,#0
|
|
movne r3,r8 @ no -> next node
|
|
bne 2b @ and loop
|
|
str r5,[r3,#node_right] @ store node address in right pointer
|
|
b 4f
|
|
3: @ left
|
|
ldr r8,[r3,#node_left] @ left pointer empty ?
|
|
cmp r8,#0
|
|
movne r3,r8 @
|
|
bne 2b @ no -> loop
|
|
str r5,[r3,#node_left] @ store node address in left pointer
|
|
4:
|
|
str r3,[r5,#node_parent] @ store parent
|
|
mov r4,#1
|
|
str r4,[r5,#node_height] @ store height = 1
|
|
mov r0,r5 @ begin node to requilbrate
|
|
mov r1,r7 @ head address
|
|
bl equilibrer
|
|
|
|
5:
|
|
add r2,#1 @ increment tree size
|
|
str r2,[r7,#tree_size]
|
|
mov r0,#0
|
|
b 100f
|
|
6: @ key equal ?
|
|
ldr r0,iAdrszMessKeyDbl
|
|
bl affichageMess
|
|
mov r0,#-1
|
|
b 100f
|
|
100:
|
|
pop {r1-r8,lr} @ restaur registers
|
|
bx lr @ return
|
|
iAdrszMessKeyDbl: .int szMessKeyDbl
|
|
/******************************************************************/
|
|
/* equilibrer after insertion */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 contains the address of head */
|
|
equilibrer: @ INFO: equilibrer
|
|
push {r1-r8,lr} @ save registers
|
|
mov r3,#0 @ balance factor
|
|
1: @ begin loop
|
|
ldr r5,[r0,#node_parent] @ load father
|
|
cmp r5,#0 @ end ?
|
|
beq 5f
|
|
cmp r3,#2 @ right tree too long
|
|
beq 5f
|
|
cmp r3,#-2 @ left tree too long
|
|
beq 5f
|
|
mov r6,r0 @ s = current
|
|
ldr r0,[r6,#node_parent] @ current = father
|
|
ldr r7,[r0,#node_left]
|
|
cmp r7,#0
|
|
ldrne r8,[r7,#node_height] @ height left tree
|
|
moveq r8,#0
|
|
ldr r7,[r0,#node_right]
|
|
cmp r7,#0
|
|
ldrne r9,[r7,#node_height] @ height right tree
|
|
moveq r9,#0
|
|
cmp r8,r9
|
|
addgt r8,#1
|
|
strgt r8,[r0,#node_height]
|
|
addle r9,#1
|
|
strle r9,[r0,#node_height]
|
|
//
|
|
ldr r7,[r0,#node_right]
|
|
cmp r7,#0
|
|
ldrne r8,[r7,#node_height]
|
|
moveq r8,#0
|
|
ldr r7,[r0,#node_left]
|
|
cmp r7,#0
|
|
ldrne r9,[r7,#node_height]
|
|
moveq r9,#0
|
|
sub r3,r8,r9 @ compute balance factor
|
|
b 1b
|
|
5:
|
|
cmp r3,#2
|
|
beq 6f
|
|
cmp r3,#-2
|
|
beq 6f
|
|
b 100f
|
|
6:
|
|
mov r3,r1
|
|
mov r4,r0
|
|
mov r1,r6
|
|
bl equiUnSommet
|
|
@ change head address ?
|
|
ldr r2,[r3,#tree_root]
|
|
cmp r2,r4
|
|
streq r6,[r3,#tree_root]
|
|
100:
|
|
pop {r1-r8,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* equilibre 1 sommet */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 contains the address of the node */
|
|
equiUnSommet: @ INFO: equiUnSommet
|
|
push {r1-r9,lr} @ save registers
|
|
mov r5,r0 @ save p
|
|
mov r6,r1 // s
|
|
ldr r2,[r5,#node_left]
|
|
cmp r2,r6
|
|
bne 5f
|
|
ldr r7,[r5,#node_right]
|
|
cmp r7,#0
|
|
moveq r8,#0
|
|
ldrne r8,[r7,#node_height]
|
|
ldr r7,[r5,#node_left]
|
|
cmp r7,#0
|
|
moveq r9,#0
|
|
ldrne r9,[r7,#node_height]
|
|
sub r3,r8,r9
|
|
cmp r3,#-2
|
|
bne 100f
|
|
ldr r7,[r6,#node_right]
|
|
cmp r7,#0
|
|
moveq r8,#0
|
|
ldrne r8,[r7,#node_height]
|
|
ldr r7,[r6,#node_left]
|
|
cmp r7,#0
|
|
moveq r9,#0
|
|
ldrne r9,[r7,#node_height]
|
|
sub r3,r8,r9
|
|
cmp r3,#1
|
|
bge 2f
|
|
mov r0,r5
|
|
bl rotRight
|
|
b 100f
|
|
2:
|
|
mov r0,r6
|
|
bl rotLeft
|
|
mov r0,r5
|
|
bl rotRight
|
|
b 100f
|
|
|
|
5:
|
|
ldr r7,[r5,#node_right]
|
|
cmp r7,#0
|
|
moveq r8,#0
|
|
ldrne r8,[r7,#node_height]
|
|
ldr r7,[r5,#node_left]
|
|
cmp r7,#0
|
|
moveq r9,#0
|
|
ldrne r9,[r7,#node_height]
|
|
sub r3,r8,r9
|
|
cmp r3,#2
|
|
bne 100f
|
|
ldr r7,[r6,#node_right]
|
|
cmp r7,#0
|
|
moveq r8,#0
|
|
ldrne r8,[r7,#node_height]
|
|
ldr r7,[r6,#node_left]
|
|
cmp r7,#0
|
|
moveq r9,#0
|
|
ldrne r9,[r7,#node_height]
|
|
sub r3,r8,r9
|
|
cmp r3,#-1
|
|
ble 2f
|
|
mov r0,r5
|
|
bl rotLeft
|
|
b 100f
|
|
2:
|
|
mov r0,r6
|
|
bl rotRight
|
|
mov r0,r5
|
|
bl rotLeft
|
|
b 100f
|
|
|
|
100:
|
|
pop {r1-r9,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* right rotation */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
rotRight: @ INFO: rotRight
|
|
push {r1-r5,lr} @ save registers
|
|
// r2 r2
|
|
// r0 r1
|
|
// r1 r0
|
|
// r3 r3
|
|
ldr r1,[r0,#node_left] @ load left children
|
|
ldr r2,[r0,#node_parent] @ load father
|
|
cmp r2,#0 @ no father ???
|
|
beq 2f
|
|
ldr r3,[r2,#node_left] @ load left node father
|
|
cmp r3,r0 @ equal current node ?
|
|
streq r1,[r2,#node_left] @ yes store left children
|
|
strne r1,[r2,#node_right] @ no store right
|
|
2:
|
|
str r2,[r1,#node_parent] @ change parent
|
|
str r1,[r0,#node_parent]
|
|
ldr r3,[r1,#node_right]
|
|
str r3,[r0,#node_left]
|
|
cmp r3,#0
|
|
strne r0,[r3,#node_parent] @ change parent node left
|
|
str r0,[r1,#node_right]
|
|
|
|
ldr r3,[r0,#node_left] @ compute newbalance factor
|
|
cmp r3,#0
|
|
moveq r4,#0
|
|
ldrne r4,[r3,#node_height]
|
|
ldr r3,[r0,#node_right]
|
|
cmp r3,#0
|
|
moveq r5,#0
|
|
ldrne r5,[r3,#node_height]
|
|
cmp r4,r5
|
|
addgt r4,#1
|
|
strgt r4,[r0,#node_height]
|
|
addle r5,#1
|
|
strle r5,[r0,#node_height]
|
|
//
|
|
ldr r3,[r1,#node_left] @ compute new balance factor
|
|
cmp r3,#0
|
|
moveq r4,#0
|
|
ldrne r4,[r3,#node_height]
|
|
ldr r3,[r1,#node_right]
|
|
cmp r3,#0
|
|
moveq r5,#0
|
|
ldrne r5,[r3,#node_height]
|
|
cmp r4,r5
|
|
addgt r4,#1
|
|
strgt r4,[r1,#node_height]
|
|
addle r5,#1
|
|
strle r5,[r1,#node_height]
|
|
100:
|
|
pop {r1-r5,lr} @ restaur registers
|
|
bx lr
|
|
/******************************************************************/
|
|
/* left rotation */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node sommet */
|
|
rotLeft: @ INFO: rotLeft
|
|
push {r1-r5,lr} @ save registers
|
|
// r2 r2
|
|
// r0 r1
|
|
// r1 r0
|
|
// r3 r3
|
|
ldr r1,[r0,#node_right] @ load right children
|
|
ldr r2,[r0,#node_parent] @ load father (racine)
|
|
cmp r2,#0 @ no father ???
|
|
beq 2f
|
|
ldr r3,[r2,#node_left] @ load left node father
|
|
cmp r3,r0 @ equal current node ?
|
|
streq r1,[r2,#node_left] @ yes store left children
|
|
strne r1,[r2,#node_right] @ no store to right
|
|
2:
|
|
str r2,[r1,#node_parent] @ change parent of right children
|
|
str r1,[r0,#node_parent] @ change parent of sommet
|
|
ldr r3,[r1,#node_left] @ left children
|
|
str r3,[r0,#node_right] @ left children pivot exists ?
|
|
cmp r3,#0
|
|
strne r0,[r3,#node_parent] @ yes store in
|
|
str r0,[r1,#node_left]
|
|
//
|
|
ldr r3,[r0,#node_left] @ compute new height for old summit
|
|
cmp r3,#0
|
|
moveq r4,#0
|
|
ldrne r4,[r3,#node_height] @ left height
|
|
ldr r3,[r0,#node_right]
|
|
cmp r3,#0
|
|
moveq r5,#0
|
|
ldrne r5,[r3,#node_height] @ right height
|
|
cmp r4,r5
|
|
addgt r4,#1
|
|
strgt r4,[r0,#node_height] @ if right > left
|
|
addle r5,#1
|
|
strle r5,[r0,#node_height] @ if left > right
|
|
//
|
|
ldr r3,[r1,#node_left] @ compute new height for new
|
|
cmp r3,#0
|
|
moveq r4,#0
|
|
ldrne r4,[r3,#node_height]
|
|
ldr r3,[r1,#node_right]
|
|
cmp r3,#0
|
|
moveq r5,#0
|
|
ldrne r5,[r3,#node_height]
|
|
cmp r4,r5
|
|
addgt r4,#1
|
|
strgt r4,[r1,#node_height]
|
|
addle r5,#1
|
|
strle r5,[r1,#node_height]
|
|
100:
|
|
pop {r1-r5,lr} @ restaur registers
|
|
bx lr
|
|
/******************************************************************/
|
|
/* search value in tree */
|
|
/******************************************************************/
|
|
/* r0 contains the address of structure of tree */
|
|
/* r1 contains the value to search */
|
|
searchTree: @ INFO: searchTree
|
|
push {r1-r4,lr} @ save registers
|
|
ldr r2,[r0,#tree_root]
|
|
|
|
1: @ begin loop
|
|
ldr r4,[r2,#node_value] @ load key
|
|
cmp r1,r4
|
|
beq 3f @ key equal
|
|
blt 2f @ key <
|
|
@ key > insertion right
|
|
ldr r3,[r2,#node_right] @ node empty ?
|
|
cmp r3,#0
|
|
movne r2,r3 @ no -> next node
|
|
bne 1b @ and loop
|
|
mov r0,#-1 @ not find
|
|
b 100f
|
|
2: @ left
|
|
ldr r3,[r2,#node_left] @ left pointer empty ?
|
|
cmp r3,#0
|
|
movne r2,r3 @
|
|
bne 1b @ no -> loop
|
|
mov r0,#-1 @ not find
|
|
b 100f
|
|
3:
|
|
mov r0,r2 @ return node address
|
|
100:
|
|
pop {r1-r4,lr} @ restaur registers
|
|
bx lr
|
|
/******************************************************************/
|
|
/* suppression node */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 contains structure tree address */
|
|
supprimer: @ INFO: supprimer
|
|
push {r1-r8,lr} @ save registers
|
|
ldr r1,[r0,#node_left]
|
|
cmp r1,#0
|
|
bne 5f
|
|
ldr r1,[r0,#node_right]
|
|
cmp r1,#0
|
|
bne 5f
|
|
@ is a leaf
|
|
mov r4,#0
|
|
ldr r3,[r0,#node_parent] @ father
|
|
cmp r3,#0
|
|
streq r4,[r1,#tree_root]
|
|
beq 100f
|
|
ldr r1,[r3,#node_left]
|
|
cmp r1,r0
|
|
bne 2f
|
|
str r4,[r3,#node_left] @ suppression left children
|
|
ldr r5,[r3,#node_right]
|
|
cmp r5,#0
|
|
moveq r6,#0
|
|
ldrne r6,[r5,#node_height]
|
|
add r6,#1
|
|
str r6,[r3,#node_height]
|
|
b 3f
|
|
2: @ suppression right children
|
|
str r4,[r3,#node_right]
|
|
ldr r5,[r3,#node_left]
|
|
cmp r5,#0
|
|
moveq r6,#0
|
|
ldrne r6,[r5,#node_height]
|
|
add r6,#1
|
|
str r6,[r3,#node_height]
|
|
3: @ new balance
|
|
mov r0,r3
|
|
bl equilibrerSupp
|
|
b 100f
|
|
5: @ is not à leaf
|
|
ldr r7,[r0,#node_right]
|
|
cmp r7,#0
|
|
beq 7f
|
|
mov r8,r0
|
|
mov r0,r7
|
|
6:
|
|
ldr r6,[r0,#node_left]
|
|
cmp r6,#0
|
|
movne r0,r6
|
|
bne 6b
|
|
b 9f
|
|
7:
|
|
ldr r7,[r0,#node_left] @ search the litle element
|
|
cmp r7,#0
|
|
beq 9f
|
|
mov r8,r0
|
|
mov r0,r7
|
|
8:
|
|
ldr r6,[r0,#node_right] @ search the great element
|
|
cmp r6,#0
|
|
movne r0,r6
|
|
bne 8b
|
|
9:
|
|
ldr r5,[r0,#node_value] @ copy value
|
|
str r5,[r8,#node_value]
|
|
bl supprimer @ suppression node r0
|
|
100:
|
|
pop {r1-r8,lr} @ restaur registers
|
|
bx lr
|
|
|
|
/******************************************************************/
|
|
/* equilibrer after suppression */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 contains the address of head */
|
|
equilibrerSupp: @ INFO: equilibrerSupp
|
|
push {r1-r8,lr} @ save registers
|
|
mov r3,#1 @ balance factor
|
|
ldr r2,[r1,#tree_root]
|
|
1:
|
|
ldr r5,[r0,#node_parent] @ load father
|
|
cmp r5,#0 @ no father
|
|
beq 100f
|
|
cmp r3,#0 @ balance equilibred
|
|
beq 100f
|
|
mov r6,r0 @ save entry node
|
|
ldr r0,[r6,#node_parent] @ current = father
|
|
ldr r7,[r0,#node_left]
|
|
cmp r7,#0
|
|
ldrne r8,[r7,#node_height] @ height left tree
|
|
moveq r8,#0
|
|
ldr r7,[r0,#node_right]
|
|
cmp r7,#0
|
|
ldrne r9,[r7,#node_height] @ height right tree
|
|
moveq r9,#0
|
|
cmp r8,r9
|
|
addgt r8,#1
|
|
strgt r8,[r0,#node_height]
|
|
addle r9,#1
|
|
strle r9,[r0,#node_height]
|
|
//
|
|
ldr r7,[r0,#node_right]
|
|
cmp r7,#0
|
|
ldrne r8,[r7,#node_height]
|
|
moveq r8,#0
|
|
ldr r7,[r0,#node_left]
|
|
cmp r7,#0
|
|
ldrne r9,[r7,#node_height]
|
|
moveq r9,#0
|
|
sub r3,r8,r9 @ compute balance factor
|
|
mov r2,r1
|
|
mov r4,r0 @ save current
|
|
mov r1,r6
|
|
bl equiUnSommet
|
|
@ change head address ?
|
|
cmp r2,r4
|
|
streq r6,[r3,#tree_root]
|
|
mov r0,r4 @ restaur current
|
|
b 1b
|
|
|
|
100:
|
|
pop {r1-r8,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* preOrder */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 function address */
|
|
preOrder: @ INFO: preOrder
|
|
push {r1-r2,lr} @ save registers
|
|
cmp r0,#0
|
|
beq 100f
|
|
mov r2,r0
|
|
blx r1 @ call function
|
|
|
|
ldr r0,[r2,#node_left]
|
|
bl preOrder
|
|
ldr r0,[r2,#node_right]
|
|
bl preOrder
|
|
100:
|
|
pop {r1-r2,lr} @ restaur registers
|
|
bx lr
|
|
|
|
/******************************************************************/
|
|
/* display node */
|
|
/******************************************************************/
|
|
/* r0 contains node address */
|
|
displayElement: @ INFO: displayElement
|
|
push {r1,r2,r3,lr} @ save registers
|
|
mov r2,r0
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion16
|
|
mov r4,#0
|
|
strb r4,[r1,r0]
|
|
ldr r0,iAdrszMessResult
|
|
ldr r1,iAdrsZoneConv
|
|
bl strInsertAtCharInc
|
|
mov r3,r0
|
|
ldr r0,[r2,#node_left]
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion16
|
|
mov r4,#0
|
|
strb r4,[r1,r0]
|
|
mov r0,r3
|
|
ldr r1,iAdrsZoneConv
|
|
bl strInsertAtCharInc
|
|
mov r3,r0
|
|
ldr r0,[r2,#node_right]
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion16
|
|
mov r4,#0
|
|
strb r4,[r1,r0]
|
|
mov r0,r3
|
|
ldr r1,iAdrsZoneConv
|
|
bl strInsertAtCharInc
|
|
mov r3,r0
|
|
ldr r0,[r2,#node_value]
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion10
|
|
mov r4,#0
|
|
strb r4,[r1,r0]
|
|
mov r0,r3
|
|
ldr r1,iAdrsZoneConv
|
|
bl strInsertAtCharInc
|
|
mov r3,r0
|
|
ldr r0,[r2,#node_height]
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion10
|
|
mov r4,#0
|
|
strb r4,[r1,r0]
|
|
mov r0,r3
|
|
ldr r1,iAdrsZoneConv
|
|
bl strInsertAtCharInc
|
|
mov r3,r0
|
|
ldr r0,[r2,#node_parent]
|
|
ldr r1,iAdrsZoneConv
|
|
bl conversion16
|
|
mov r4,#0
|
|
strb r4,[r1,r0]
|
|
mov r0,r3
|
|
ldr r1,iAdrsZoneConv
|
|
bl strInsertAtCharInc
|
|
bl affichageMess
|
|
100:
|
|
pop {r1,r2,r3,lr} @ restaur registers
|
|
bx lr @ return
|
|
iAdrszMessResult: .int szMessResult
|
|
iAdrsZoneConv: .int sZoneConv
|
|
iAdrsValue: .int sValue
|
|
|
|
/******************************************************************/
|
|
/* memory allocation on the heap */
|
|
/******************************************************************/
|
|
/* r0 contains the size to allocate */
|
|
/* r0 returns address of memory heap or - 1 if error */
|
|
/* CAUTION : The size of the allowance must be a multiple of 4 */
|
|
allocHeap:
|
|
push {r5-r7,lr} @ save registers
|
|
@ allocation
|
|
mov r6,r0 @ save size
|
|
mov r0,#0 @ read address start heap
|
|
mov r7,#0x2D @ call system 'brk'
|
|
svc #0
|
|
mov r5,r0 @ save address heap for return
|
|
add r0,r6 @ reservation place for size
|
|
mov r7,#0x2D @ call system 'brk'
|
|
svc #0
|
|
cmp r0,#-1 @ allocation error
|
|
movne r0,r5 @ return address memory heap
|
|
pop {r5-r7,lr} @ restaur registers
|
|
bx lr @ return
|
|
/***************************************************/
|
|
/* ROUTINES INCLUDE */
|
|
/***************************************************/
|
|
.include "../affichage.inc"
|