Linked List Functions

[etow]

Hi Tedd,

Even if I had a debugger I would still not know how to set the links to the pointers correctly.

[Tedd]

Do you know any good debuggers I could use to trace the pointers because I am having trouble setting the links to the previous pointer of the node as well as writing the Insert procedure?

OllyDbg works quite well - http://www.ollydbg.de/odbg110.zip
Of course, you'll need to learn how to use it before it makes sense :P

By the way, how do you set the pointer to always point to the head of the list?

There is already a pointer to the head of the list - "pLst" - which you get when the list is first created (as returned by "LstCreate")
This pointer doesn't change, so it's always the head of the list.

My insert procedure for the linked list is below, can you check if I am on the right track?

Well, I think there may be a number of holes in your understanding of asm :(
For the last time, I strongly suggest you work through the original code and understand what's happening. It's long and boring, but you do NEED to do it. If you don't understand how the code works, there's little point in trying to help you.
You seem to at least half get it, so I'll give you a few pointers (no pun intended.) But seriously, trace through the code by hand, keep track of the registers on paper, and see what happens to them - how items are appended to the list, and how the pointers are set. This is the only way you're really going to get it.

Code Select Expand


LstInsert Proc Lst:DWord, valu:DWord, i:DWord
    Local counter:DWord
    Local current:DWord

    Push Ebx
    Mov Ebx, Lst
    Assume Ebx:Ptr NODE
;;so now we have ebx as a pointer to the head of the list (passed in from 'Lst')

    Push Edx
    Mov Edx, current
    Assume Edx:Ptr NODE
;;what's the value of 'current' at this point???
;;you haven't initialised it yet - it has no value.
;;and the variable isn't even used anywhere else - remove it
;;..if you intend for edx to be a node pointer, which node is it meant to be pointing to?

    Mov counter, 0
    Mov Ecx, i

;* count through the nodes, until you get to node 'i' (first node is node 0)
  Process:
    .If (counter == Ecx)
       Jmp done
    .ElseIf
      Mov Eax, [Ebx].pNext       ; get ptr to next
      Mov Ebx, Eax
      Inc counter
;;this line shouldn't be here - not least because edi isn't used elsewhere.
;;eax (and ebx) already hold pNext, so you don't need to get it yet again
;;      Mov Edi, [Edx].pNext
      Test Eax, Eax
      Jnz Process
    .EndIf

  done:
;;don't copy comments from elsewhere unless you're SURE they mean exactly the same thing here
;;(I actually put those comments in to help you understand what was happening in the code - try reading them in the correct place)
    ;(ebx is now the last item/node)
    ;(so create a new node and append it)
;* create a new node, set its value
;* insert the node -- copy node i's pNext into this new node's, then set i's pNext to this node
    Invoke GlobalAlloc, GMEM_FIXED, SizeOf NODE      ;new node
;;what's the value of edx meant to be here?
;;note: calling api functions has a habit of changing the values of registers eax,ecx,edx
;;      so don't expect them to be correct; save them if you need to (push/pop)
    Mov [Ebx].pNext, Edx                            ;add it to the end
    mov ebx,eax
;;so now you're setting two node-pointers to the same node (edx) - is that wise?
    Mov [Ebx].pNext, Edx                          ;this is the new end of the list

    Mov Eax, valu
    mov [ebx].value,eax                             ;set its value

    assume ebx:nothing
    Pop Ebx
;;you don't have to preserve edx, only ebx,edi,esi are expected to be preserved
    Assume Edx:Nothing
    Pop Edx
    Ret
LstInsert EndP


It's clear you have a little bit more to learn, but you'll get there :wink

P.S. Do yourself a favour and stop blindly copying and pasting code! I know it seems like it makes it easier and at least you get some code out, but it really does just make more of a mess. If you don't understand it, don't copy it - as it may not do exactly what you think/want it to do. If you do understand it, there's no need to copy it because you can write it correctly yourself.
It may be the 'long' way around, but you do need to battle with coding until you understand it - and then you'll be able to write any code you like :wink

[etow]

Hi I am trying to count all the nodes in a linked list but can not get it to count as one number.
For example, I will get a 0 node for the first node in the beginning of the created link list and and other 0 node when I append to the link list.
I am trying to use a global variable but not sure how to use it to count all the nodes in a link list.
Can anyone help me please?

Thanks.

-- Here is my code below --
---------------------------------------------------------------------------------------------------------------------------

Code Select Expand


.686
;The MASM32 Runtime Floating Point Library include file.
;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Include \masm32\include\masm32rt.inc
;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

;***************************************************************************************************

LstCreate Proto IntVal:DWord
LstDestroy proto Lst:DWORD
LstInsert Proto Lst:DWord, IntVal:DWord, i:DWord
LstAppend Proto Lst:DWord, IntVal:DWord
LstRemove proto Lst:DWORD,i:DWORD

;***************************************************************************************************

NODE Struct
numberNode DWord ?
    pNext DWord ?
    value DWord ?
NODE ends

;***************************************************************************************************

.data?
pLst    DWord ?
originalCount  DWord ?
count  DWord ?

.Code
start:
    invoke LstCreate, 123
    mov pLst,eax

    invoke LstAppend, pLst,456
    invoke LstAppend, pLst,789
    invoke LstAppend, pLst,0ffffffffh
    Invoke LstTraverse, pLst
    invoke LstDestroy, pLst
    inkey "Press any key to exit..."
    invoke ExitProcess, NULL

;***************************************************************************************************

;create a new list, with its first item - return ptr to the new list
LstCreate Proc IntVal:DWord
    invoke GlobalAlloc, GMEM_FIXED,SIZEOF NODE      ;allocate a first node
    assume eax:ptr NODE                             ;eax is now a ptr to the new node/item
    mov [eax].pNext,NULL                            ;there is no 'next' item in the list = NULL
    Mov Edx, IntVal
    Mov [Eax].value, Edx                             ;set this item's value = val
    Mov Edx, originalCount
    Mov [Eax].numberNode, Edx
    Assume Eax:Nothing
    ret                                             ;return ptr to the (first item of the) list
LstCreate endp

;destroy given list (deleting all of its nodes)
LstDestroy proc Lst:DWORD
    push ebx
    Mov Ebx, Lst                                     ;get the list ptr
    assume ebx:ptr NODE
  @@:
    test ebx,ebx
    jz @out                                         ;NULL-ptr means no list/end-of-list
    push [ebx].pNext                                ;save ptr to next item
    invoke GlobalFree, ebx                          ;delete this item
    pop ebx                                         ;treat 'next' as new start of list
    jmp @B                                          ;round and round we go..
  @out:
    assume ebx:nothing
    pop ebx
    ret
LstDestroy endp

;insert an item into the given list, at a given 'index'
LstInsert Proc Lst:DWord, IntVal:DWord, i:DWord
    ;* count through the nodes, until you get to node 'i' (first node is node 0)
    ;* create a new node, set its value
    ;* insert the node -- copy node i's pNext into this new node's, then set i's pNext to this node



    ret
LstInsert endp
LstTraverse Proc Lst:DWord
    Push Ebx
    Mov Ebx, Lst
    Assume Ebx:Ptr NODE

Process:
print chr$("numberNode = ")
print str$([Ebx].numberNode)
print chr$(13, 10)
    print chr$("value = ")
    print str$([Ebx].value)    ; print print the item of the list
    print chr$(13, 10)

    Mov Eax, [Ebx].pNext
    Mov Ebx, Eax
    Test Eax, Eax
    Jnz Process            ; if it is not NULL then continue to process the list

Ret
LstTraverse EndP

;add an item to the end of the list
LstAppend Proc Lst:DWord, IntVal:DWord
    push ebx
    mov ebx,Lst
    assume ebx:ptr NODE
    ;(first we need to find the end of the list)
  @@:
    mov eax,[ebx].pNext                             ;get ptr to next
    test eax,eax
    jz @found                                       ;if is NULL then we're at the end of the list
    mov ebx,eax                                     ;else keep looking.. (move onto next item)
    jmp @B
  @found:
    ;(ebx is now the last item/node)
    ;(so create a new node and append it)
    invoke GlobalAlloc, GMEM_FIXED,SIZEOF NODE      ;new node
    mov [ebx].pNext,eax                             ;add it to the end
    mov ebx,eax
    mov [ebx].pNext,NULL                            ;this is the new end of the list
    Mov Eax, IntVal
    Mov [Ebx].value, Eax                             ;set its value
    Mov Eax, count
    Mov [Ebx].numberNode, Eax
    Mov Ecx, 1
    Mov Eax, count
    Add Eax, Ecx
    Mov count, Eax
@out:
    assume ebx:nothing
    Pop Ebx
    ret
LstAppend endp

;remove item at given index from the list
LstRemove proc Lst:DWORD,i:DWORD
    ;* count through the nodes, until you get to node i-1 (but we're deleting the next one)
    ;* using pNext, get node i's pNext
    ;* delete the next node (node i; using this pNext)
    ;* set this node's pNext to the next node (then delete node's pNext)
    ret
LstRemove endp

;***************************************************************************************************

End start


[Tedd]

1. Go back and read all of my comments again - surprisingly they are supposed to help you.
2. For the 50th time, work your way through the code and understand how it works. At least make some effort.
   I wrote a LOT of code for you - not so you could just copy and paste it all, but so you might be able to work through it and understand it.
3. If you're trying to number the nodes, try incrementing (add 1) your "originalCount" each time you add a new one, otherwise they obviously will all have the same number.
4. To simply count how many nodes there are, all you need to do is traverse the list and add 1 each time you follow another node. You don't need to number the nodes to do this, and if you insert another node into the list then the numbering will be wrong anyway.

[etow]

Why are pointers really hard to understand in assembly language?

It is very messy to understand.

[Tedd]

Why are pointers really hard to understand in assembly language?

Are they? I think they're much easier in assembly than in 'higher' languages - you get to see exactly what is happening.

All a pointer is, is the address of something - it 'points' to that thing.
So, if you make EBX the address of a node, it becomes a pointer to that node. Then you can use the register to get the thing it actually points to, e.g. "mov eax,[ebx]" -- that's all there is to it.
I've used 'assume' so that you can easily get the structure members from the node. You could use "mov eax,[ebx+4]" instead, but I think it's easier to read "mov eax,[ebx].pNext", and if you change the NODE struct, you don't need to go through all of your code fixing all of the offsets again. ("assume" doesn't actually make any code, it just means you can use the different notation - you don't have to use it, but I think it makes it easier and more readable.)

[hutch--]

Egan,

The important distinction to remember is between WHERE something is in memory and WHAT is written at that address in memory. If you bother to look at the string conversion of BOTH the content of the variable and the ADDRESS of the variable, you will see what I mean.

Code Select Expand


.data
  variable dd 1234
    ....

.code

    print str$(variable)," The variable content",13,10

    mov eax, OFFSET variable

    print str$(eax)," The variable's ADDRESS",13,10



A LOCAL variable differes only in how you get its address.

Code Select Expand


myproc proc etc ....

    LOCAL lvar  :DWORD

    mov lvar, 9876

    print str$(lvar)," The local variables content"

    lea eax, lvar

    print str$(eax)," The ADDRESS of the local variable",13,10