

 This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; at no time do they differ by more than one because rebalancing is done ensure this is the case. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. Note the tree of nodes comprise a set, so duplicate node keys are not allowed.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.



Task

Implement an AVL tree in the language of choice, and provide at least basic operations.




 
/* 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"
 