Linked list example ?

[RuiLoureiro]

I wrote this example using index values
Try this and say something. Does this work correctly ?

Code Select Expand


include \masm32\include\masm32rt.inc
.686p

; »»»»»»»»»»»»»»»» CONSOLE ASSEMLBLE & LINK »»»»»»»»»»»»»

InsertLkdList       proto   :DWORD,:DWORD,:DWORD
CreateLkdList       proto   :DWORD,:DWORD,:DWORD,:DWORD
DestroyLkdList      proto   :DWORD


NODE struct
   pNext   dd ?
   pPrev   dd ?
   LkdData db 256 dup (?)
NODE ends

IDXFSTLIST      equ 12
IDXLSTLIST      equ 8
IDXALCLIST      equ 4

LENNODE         equ sizeof NODE
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
.data
    Str1        db "zzzzzz", 0
    Str2        db "ccccccccc", 0
    Str3        db "bbbbbbbbb", 0
    Str4        db "aaaaaaaaa", 0
    Str5        db "aaaaaxxxx", 0


.data?
   pBuffer      dd ?
   pList        dd ?
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
.code

start:
   
        invoke   CreateLkdList, 20000, sizeof NODE, addr pBuffer, addr pList
        jc       _exit

        ;call     SeeLkdList
       
        invoke   InsertLkdList, pList, sizeof NODE, addr Str1
        invoke   InsertLkdList, pList, sizeof NODE, addr Str2
        invoke   InsertLkdList, pList, sizeof NODE, addr Str3
        invoke   InsertLkdList, pList, sizeof NODE, addr Str4
        invoke   InsertLkdList, pList, sizeof NODE, addr Str5

        call     ShowLkdListDn
        call     ShowLkdListUp
   ;---------------------
_exit:
        inkey
        invoke   DestroyLkdList, pBuffer
        exit
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
InsertLkdList       proc    pLst:DWORD, lReg:DWORD, pStr:DWORD
                    push    ebx
                    push    esi
                    push    edi
                    ;
                    mov     esi, pStr
                    mov     edi, pLst
                    mov     eax, dword ptr [edi - IDXALCLIST]            ; Alloc

                    cmp     eax, 0
                    jne     short @F
                    ;
                    ; Is full
                    ; -------
                    stc
                    jmp     _end
                   

    @@:             mov     ebx, eax
   
                    sub     eax, 1
                    mov     ecx, lReg
                    mul     ecx
                    add     eax, edi
                   
                    mov     edx, dword ptr [eax].NODE.pNext
                    mov     dword ptr [edi - IDXALCLIST], edx         ; Alloc

                    mov     dword ptr [eax].NODE.pNext, 0
                    mov     dword ptr [eax].NODE.pPrev, 0

                    call    SetLkdList
                   
                    cmp     dword ptr [edi - IDXFSTLIST], 0           ; Idx First
                    jne     short _next
                    ;
                    ; Is first
                    ; --------
                    mov     dword ptr [edi - IDXFSTLIST], ebx         ; Idx First
                    mov     dword ptr [edi - IDXLSTLIST], ebx         ; Idx Last                   
                    jmp     _end
                   
    _next:          call    CmpLkdList
   
                    clc
    _end:           pop     edi
                    pop     esi
                    pop     ebx
                    ret
InsertLkdList       endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
;       ESI     - pStr   
;       EDI     - pList
;       ECX     - lReg
;
CmpLkdList          proc
                    LOCAL   LenReg, IdxNew, PtrNew, IdxCur, IdxNxt, IdxPre:DWORD
                    push    esi
                    push    edi

                    mov     PtrNew, eax                             ; Ptr new
                    mov     IdxNew, ebx                             ; Idx new
                    mov     LenReg, ecx                             ; Len Reg

                    call    LenStringN

                    mov     eax, dword ptr [edi - IDXFSTLIST]       ; Idx First
                    jmp     short _start
                   
        _next:      mov     eax, IdxNxt
                    cmp     eax, 0
                    je      _last
                   
        _start:     mov     IdxCur, eax
       
                    mov     edx, LenReg
                    sub     eax, 1
                    mul     edx
                    add     eax, edi
                    mov     ebx, eax
                    ;
                    mov     eax, dword ptr [ebx].NODE.pNext         ; Idx Next
                    mov     IdxNxt, eax
                    mov     edx, dword ptr [ebx].NODE.pPrev         ; Idx Prev
                    mov     IdxPre, edx

                    call    CmpStrings
                    jae     short _next
;--------------------
                    mov     eax, IdxPre
                    cmp     eax, 0
                    je      _first

                    mov     edx, IdxNew                             ; Idx new
                    mov     dword ptr [ebx].NODE.pPrev, edx         ; Idx Prev

                    mov     edx, IdxCur
                    ;mov     eax, IdxPre
                   
                    mov     ebx, PtrNew                             ; Ptr new
                    mov     dword ptr [ebx].NODE.pNext, edx         ; Idx Next
                    mov     dword ptr [ebx].NODE.pPrev, eax         ; Idx Prev

                    mov     edx, LenReg
                    sub     eax, 1
                    mul     edx
                    add     eax, edi

                    mov     edx, IdxNew                             ; Idx new
                    mov     dword ptr [eax].NODE.pNext, edx         ; Idx Next
                    jmp     _end
;--------------------
        _last:      mov     eax, IdxNew                             ; Idx new
                    mov     dword ptr [edi - IDXLSTLIST], eax       ; Idx Last
                    mov     dword ptr [ebx].NODE.pNext, eax         ; Idx Next

                    mov     eax, IdxCur
                    mov     ebx, PtrNew                             ; Ptr new
                    mov     dword ptr [ebx].NODE.pPrev, eax         ; Idx Prev
                    jmp     _end
;--------------------
        _first:     mov     eax, IdxNew                             ; Idx new
                    mov     dword ptr [edi - IDXFSTLIST], eax       ; Idx First
                    mov     dword ptr [ebx].NODE.pPrev, eax         ; Idx Prev

                    mov     eax, IdxCur
                    mov     ebx, PtrNew                             ; Ptr new
                    mov     dword ptr [ebx].NODE.pNext, eax         ; Idx Next
                   
        _end:       pop     edi
                    pop     esi
                    ret
CmpLkdList          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
LenStringN          proc

                    xor     ecx, ecx
                    jz      short _start
                   
        @@:         add     ecx, 1
        _start:     cmp     byte ptr [esi + ecx], 0
                    jne     short @B

                    ret
LenStringN          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
LenStringX          proc
                    xor     edx, edx
                    jz      short _start
                   
        @@:         add     edx, 1
        _start:     cmp     byte ptr [edi + edx], 0
                    jne     short @B

                    ret
LenStringX          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
;       ESI     - pStr   
;       EDI     - pList
;       ECX     - lReg
;       EBX     - pReg Cur
;
CmpStrings          proc
                    push    ecx
                    push    esi
                    push    edi

                    lea     edi, dword ptr [ebx].NODE.LkdData
                    call    LenStringX
                    ;
                    cmp     ecx, edx
                    jb      short _below
                    ja      short _above     

    ;***---***
    _equal:         movzx   eax, byte ptr [esi]
                    cmp     al, byte ptr [edi]
                    jne     _fim
                    ;
                    add     esi, 1
                    add     edi, 1
                    ;
                    sub     ecx, 1
                    jnz     short _equal
                    jz      _fim

    ;***---***
    _above:         movzx   eax, byte ptr [esi]
                    cmp     al, byte ptr [edi]
                    jne     _fim
                    ;
                    add     esi, 1
                    add     edi, 1
                    ;
                    sub     edx, 1
                    jnz     short _above
                    jz      short _cmp
    ;***---***
    _below:         movzx   eax, byte ptr [esi]
                    cmp     al, byte ptr [edi]
                    jne     _fim
                    ;
                    add     esi, 1
                    add     edi, 1
                    ;
                    sub     ecx, 1
                    jnz     short _below
       
    _cmp:           cmp     ecx, edx

    _fim:           pop     edi
                    pop     esi
                    pop     ecx
                    ret
CmpStrings          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
SetLkdList          proc
                    push    eax
                    push    ebx
                    push    esi
                   
                    mov     ebx, eax
                   
        @@:         movzx   eax, byte ptr [esi]                   
                    mov     byte ptr [ebx].NODE.LkdData, al
                    add     esi, 1
                    add     ebx, 1
                    cmp     al, 0
                    jne     short @B

                    pop     esi                   
                    pop     ebx
                    pop     eax
                    ret
SetLkdList          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
PutLkdList          proc
                    push    eax
                    push    esi
                    push    edi
                   
                    lea     edi, dword ptr [eax].NODE.LkdData
                   
        @@:         movzx   eax, byte ptr [esi]                   
                    mov     byte ptr [edi], al
                    add     esi, 1
                    add     edi, 1
                    cmp     al, 0
                    jne     short @B
                   
                    pop     edi
                    pop     esi
                    pop     eax                   
                    ret
PutLkdList          endp     
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
CreateLkdList       proc    nReg:DWORD, lReg:DWORD, pBuf:DWORD, pLst:DWORD

                    mov     eax, nReg
                    mov     edx, lReg
                    mul     edx
                    add     eax, 16
                    ;
                    invoke  GlobalAlloc, GMEM_FIXED, eax
                    cmp     eax, NULL
                    jne     @F
                    stc
                    ret
                   
        @@:         push    ebx
                    push    edi
                   
                    mov     edx, pBuf
                    mov     dword ptr [edx], eax
                    add     eax, 12
                    mov     edi, eax
                    ;
                    mov     edx, pLst
                    mov     dword ptr [edx], eax
                    ;
                    mov     dword ptr [edi - IDXALCLIST], 1         ; Alloc
                    mov     dword ptr [edi - IDXFSTLIST], 0         ; Idx First
                    mov     dword ptr [edi - IDXLSTLIST], 0         ; Idx Last
                    ;
                    mov     ecx, nReg
                    sub     ecx, 1
                    ;
                    mov     eax, lReg
                    mul     ecx
                    add     eax, edi
                    mov     dword ptr [eax].NODE.pNext, 0
                    ;
        @@:         mov     ebx, ecx
                    add     ebx, 1
                    ;
                    sub     ecx, 1
                    ;
                    mov     eax, lReg
                    mul     ecx
                    add     eax, edi
                    mov     dword ptr [eax].NODE.pNext, ebx
                    ;
                    cmp     ecx, 0
                    jne     short @B

                    clc       
                    pop     edi
                    pop     ebx
                    ret
CreateLkdList       endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
DestroyLkdList      proc    pBuf:DWORD
                    invoke  GlobalFree, pBuf
                    ret
DestroyLkdList      endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
SeeLkdList          proc
                    pushad
                    ;
                    mov     edi, pList
                    ;print   str$(edi), 13, 10
                    ;inkey
                    ;
                    mov     ebx, 1
                   
        @@:         push    ebx
                    sub     ebx, 1                   
                    mov     eax, LENNODE
                    mul     ebx
                    add     eax, edi
                    mov     eax, dword ptr [eax].NODE.pNext

                    print   str$(eax), 13, 10
                    inkey
                    ;
                    pop     ebx
                   
                    add     ebx, 1
                    cmp     ebx, 5
                    jbe     @B
                   
                    popad
                    ret
SeeLkdList          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
ShowLkdListUp       proc
                    pushad

                    print   "From BOTTOM to TOP ", 13, 10

                    mov     edi, pList
                    call    ShowHeader
                   
                    mov     ebx, dword ptr [edi - IDXLSTLIST]            ; Idx Last

        _next:      cmp     ebx, 0
                    je      _fim
                   
                    mov     ecx, LENNODE
                    mov     eax, ebx
                    sub     eax, 1
                    mul     ecx
                    add     eax, edi
                    mov     esi, eax
                    ;
                    print   "Cur= "
                    print   str$(ebx)
                    ;
                    print   "   Next= "
                    mov     eax, dword ptr [esi].NODE.pNext
                    print   str$(eax)
                    ;
                    print   "   Prev= "
                    mov     eax, dword ptr [esi].NODE.pPrev
                    print   str$(eax)
                    ;
                    print   "   String= "
                    lea     ebx, dword ptr [esi].NODE.LkdData
                    print   ebx, 13, 10
                    ;
                    mov     ebx, dword ptr [esi].NODE.pPrev                   
                    jmp     _next
                   

        _fim:       ;inkey

                    popad
                    ret
ShowLkdListUp       endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
ShowLkdListDn       proc
                    pushad

                    print   "From TOP to BOTTOM ", 13, 10

                    mov     edi, pList
                    call    ShowHeader

                    mov     ebx, dword ptr [edi - IDXFSTLIST]            ; Idx First
                   
        _next:      cmp     ebx, 0
                    je      _fim
                   
                    mov     ecx, LENNODE
                    mov     eax, ebx
                    sub     eax, 1
                    mul     ecx
                    add     eax, edi
                    mov     esi, eax
                    ;
                    print   "Cur= "
                    print   str$(ebx)
                    ;
                    print   "   Next= "
                    mov     eax, dword ptr [esi].NODE.pNext
                    print   str$(eax)
                    ;
                    print   "   Prev= "
                    mov     eax, dword ptr [esi].NODE.pPrev
                    print   str$(eax)
                    ;
                    print   "   String= "
                    lea     ebx, dword ptr [esi].NODE.LkdData
                    print   ebx, 13, 10
                    ;
                    mov     ebx, dword ptr [esi].NODE.pNext                   
                    jmp     _next
                   
        _fim:       ;inkey
                    print   " ", 13, 10

                    popad
                    ret
ShowLkdListDn       endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
ShowHeader          proc

                    print   "Alloc= "
                    mov     eax, dword ptr [edi - IDXALCLIST]            ; Alloc
                    print   str$(eax), 13, 10

                    print   "First= "
                    mov     eax, dword ptr [edi - IDXFSTLIST]            ; Idx First
                    print   str$(eax), 13, 10
                    ;
                    print   "Last= "
                    mov     eax, dword ptr [edi - IDXLSTLIST]            ; Idx Last
                    print   str$(eax), 13, 10
                    ;
                    ret
ShowHeader          endp
;»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»»
end start


[qWord]

hi,
After a quick look:
- why not using a struct instead of this?:

Code Select Expand

IDXFSTLIST      equ 12
IDXLSTLIST      equ 8
IDXALCLIST      equ 4

- AFAIKS DestroyLkdList does not destroy the list - it only deletes the 'header' (or however you call it)

[RuiLoureiro]

hi qWord,

1. »» why not using a struct instead of this?

      because i dont like to use strutures, one is enough
      I like to use the top of the buffer for that type of variables
      I alloc buffer for 20000 structures + 16 bytes for that (header)

2. »» AFAIKS DestroyLkdList does not destroy the list ...

      After we call DestroyLkdList, the memory doesnt exist
      so the list is destroyed. To allocate memory i use GlobalAlloc
      and to destroy it i use GlobalFree

   »»» ... it only deletes the header

       wrong, not the header but all memory     

    The structure of the memory i alloc is this:


                dd ?                       ; IDXFSTLIST
                dd ?                       ; IDXLSTLIST
                dd ?                       ; IDXALCLIST
       LkdList  db 20000 * sizeof NODE dup (?)
                dd

[qWord]

ok - I didn't see (and expect :-) ) that you allocating all nodes at creation of list.

[RuiLoureiro]

Now we have

        CreateLkdList:  to create the linked list
        DestroyLkdList: do destroy the list
        InsertLkdList:  to insert a string into the linked list
        DeleteLkdList:  to delete a string from the linked list

The strings are ordered and we can call from top to bottom
or from bottom to top
We can see the example in LkdList1.zip (.asm & .exe)       

[RuiLoureiro]

We can see the example in LkdList2.zip (.asm & .exe)       

It contains:

        CreateLkdList:  to create the linked list
        FormatLkdList:  used to delete all strings from the list
        DestroyLkdList: to destroy the list ( used before end )
        InsertLkdList:  to insert a string into the linked list
        DeleteLkdList:  to delete a string from the linked list

        VerifyLkdList:  to verify the structure of the linked list

To create a list with 20000 nodes, use this:

        invoke   CreateLkdList, 20000, sizeof NODE, addr pBuffer, addr pList

----------------------------------------------
When we run it, we see this (and more...):

From TOP to BOTTOM
Alloc= 0
First= 11
Last= 17
Cur= 11   Next= 8    Prev= 0    String= almond
Cur= 8    Next= 4    Prev= 11   String= apple
Cur= 4    Next= 15   Prev= 8    String= apricot
Cur= 15   Next= 10   Prev= 4    String= banana
Cur= 10   Next= 19   Prev= 15   String= cherry
Cur= 19   Next= 7    Prev= 10   String= fig
Cur= 7    Next= 12   Prev= 19   String= grape
Cur= 12   Next= 16   Prev= 7    String= lemon
Cur= 16   Next= 18   Prev= 12   String= loquat
Cur= 18   Next= 2    Prev= 16   String= mango
Cur= 2    Next= 9    Prev= 18   String= melon
Cur= 9    Next= 14   Prev= 2    String= melon
Cur= 14   Next= 1    Prev= 9    String= mulberry
Cur= 1    Next= 20   Prev= 14   String= orange
Cur= 20   Next= 6    Prev= 1    String= passion-fruit
Cur= 6    Next= 13   Prev= 20   String= peach
Cur= 13   Next= 3    Prev= 6    String= pear
Cur= 3    Next= 5    Prev= 13   String= quince
Cur= 5    Next= 17   Prev= 3    String= strawberry
Cur= 17   Next= 0    Prev= 5    String= walnut

From BOTTOM to TOP
Alloc= 0
First= 11
Last= 17
Cur= 17   Next= 0    Prev= 5    String= walnut
Cur= 5    Next= 17   Prev= 3    String= strawberry
Cur= 3    Next= 5    Prev= 13   String= quince
Cur= 13   Next= 3    Prev= 6    String= pear
Cur= 6    Next= 13   Prev= 20   String= peach
Cur= 20   Next= 6    Prev= 1    String= passion-fruit
Cur= 1    Next= 20   Prev= 14   String= orange
Cur= 14   Next= 1    Prev= 9    String= mulberry
Cur= 9    Next= 14   Prev= 2    String= melon
Cur= 2    Next= 9    Prev= 18   String= melon
Cur= 18   Next= 2    Prev= 16   String= mango
Cur= 16   Next= 18   Prev= 12   String= loquat
Cur= 12   Next= 16   Prev= 7    String= lemon
Cur= 7    Next= 12   Prev= 19   String= grape
Cur= 19   Next= 7    Prev= 10   String= fig
Cur= 10   Next= 19   Prev= 15   String= cherry
Cur= 15   Next= 10   Prev= 4    String= banana
Cur= 4    Next= 15   Prev= 8    String= apricot
Cur= 8    Next= 4    Prev= 11   String= apple
Cur= 11   Next= 8    Prev= 0    String= almond
----------------------------------------------
DELETE melon, strawberry, apricot
----------------------------------------------
...

[RuiLoureiro]

Now, we can see the example in LkdList3.zip (.asm & .exe)       

It contains:

        CreateLkdList:  to create the linked list
        FormatLkdList:  used to delete all strings from the list
        DestroyLkdList: to destroy the list ( used before end )
        InsertLkdList:  to insert a string into the linked list
        DeleteLkdList:  to delete a string from the linked list

        VerifyLkdList:  to verify the structure of the linked list
     
        AddStrLkdList:  to add any string
        AddIntLkdList:  to add any integer

This is the structure of each node:

NODE       struct
   iNext   dd ?
   iPrev   dd ?
   LkdData db 80 dup (?)    ; linked string
   StrData db 40 dup (?)    ; another string
   IntData dd ?             ; another integer
NODE       ends

[RuiLoureiro]

I made a mistake in LkdList3
A better example is LkdList4.zip (.asm & .exe)
We dont need to use «sizeof NODE» except in CreateLkdList