Hi
How do you create a linked list, add to linked list, traverse a linked list and delete from linked list?
Thanks
http://www.masm32.com/board/index.php?topic=6248.0
Hi
I can not get the code to work yet but I have another implementation of doubly linked list below:
;The MASM32 Runtime Library include file.
;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
include \masm32\include\masm32rt.inc
;<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Listpointer = ^ ListNode
Window Struct
current DD Listpointer
trailing DD Listpointer
Window EndS
ListNode Struct
entry DD listentry
nextNode DD Listpointer
previousNode DD Listpointer
ListNode EndS
ListType Struct
head DD Listpointer
ListType EndS
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
.Code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
Call Main
inkey "Press any key to exit..."
exit
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
CreateList Proc L:ListType
Mov L.head, NULL
Ret
CreateList EndP
;--------------------------------------------------------------
OnList Proc w:Window, L:ListType
.If (w != NULL)
Mov Eax, TRUE
.ElseIf (w == NULL)
Mov Eax, FALSE
.EndIf
Ret
OnList EndP
;---------------------------------------------------------------
InsertNodeAfter Proc current:Listpointer, newNode:ListPointer, L:ListType
.If ((current == NULL) || (newNode == NULL))
print chr$("Error: Attempt to make an incorrect insertion after a node.", 13, 10)
.Else
Mov newNode^.nextNode, current^.nextNode
Mov current^.nextNode, newNode
.EndIf
Ret
InsertNodeAfter EndP
;-------------------------------------------------------------------
InsertAfter Proc w:Window, x:listentry, L:ListType
Local newNode:Listpointer
Local onListResult:BOOLEAN
Invoke OnList, w, L
Mov onListResult, Eax
new (newNode)
Mov newNode^.entry, x
.If (L.head == NULL)
Mov L.head, newNode
Mov w, newNode
Mov newNode^.nextNode, NULL
.ElseIf (onListResult == FALSE)
print chr$("Error: Attempt to insert after a node not in the list.")
.ElseIf
Invoke InsertNodeAfter, w, newNode, L
.EndIf
Ret
InsertAfter EndP
;----------------------------------------------------------------
InsertNodeBefore Proc current:Listpointer, newNode:ListPointer, L:ListType
Local previous:Listpointer
.If (current == NULL) || (newNode == NULL)
print chr$("Error: Attempt to insert a nonexistent node before a node.", 13, 10)
.ElseIf
Mov previous, current^.previousNode
Mov current^.previousNode, newNode
.If previous == NULL
Mov L.head, newNode
.ElseIf
Mov previous^.nextNode, newNode
.EndIf
Mov newNode^.nextNode, current
Mov newNode^.previousNode, previous
.EndIf
Ret
InsertNodeBefore EndP
;---------------------------------------------------------------
TraverseList Proc L:ListType
Local current:Window
Mov current, L.head
.While current != NULL
; visit current^.entry
Mov current, current^.nextNode
.EndW
Ret
TraverseList EndP
;----------------------------------------------------------------
Main Proc
Local Number:DWord
Local WantContinue:DWord
Mov WantContinue, 0 ; initialize WantContinue to zero
.While ((WantContinue >= 0) && (WantContinue < -1))
; while WantContinue is greater than or equal to 0 And
; WantContinue is less than -1 do
Mov WantContinue, sval(input("Enter -1 to quit program : "))
Invoke ClearScreen ; clears the screen
.EndW
print chr$(13, 10)
Ret
Main EndP
End start
Hi code that I posted in previous post is a mixture of some assembly and pascal code.
I am not sure how to translate it completely to assembly yet.
I need help.
Thanks
Hi
Below is the code to delete from a doubly linked list:
DeleteList Proc w:Window, L:ListType
Local onListResult:BOOLEAN
Invoke OnList, w, L
Mov onListResult, Eax
.If (onListResult == FALSE)
print chr$("Error: Attempt to delete a node not on list.", 13, 10)
.ElseIf
.If (w.current == L.head)
Mov w.current, w.current ^.nextNode
Mov L.head, w.current
Mov trailing, NULL
.ElseIf
Mov w.current, w.current ^.nextNode
dispose (w.trailing ^.nextNode)
Mov w.trailing ^.nextNode, w.current
.EndIf
.EndIf
Ret
DeleteList EndP
The code above is a mixture of assembly and pascal code
Hi
I need help to correct my code in the previous posts above to make my code work in MASM32 assembly language.
Thanks
First question: do you understand how to perform those operations on a linked-list by hand? Once you understand it you should find it much easier to do in asm - the only 'complicated' things are the memory allocation and fiddling the pointers.
(Is that your pascal code, or did you find it somewhere? You might find it easier to start over, rather than trying to convert that code.)
Hi Ted,
Yes I know how to do linked list by hand. The code is mostly Pascal that I got from my college text book.
Okay, then I would start from scratch :P You can refer back to that code and add any of its 'features' once you get something working :wink
Start with a simple node of {value:DWORD,pNext:DWORD} and then write a function - "append(Lst,val)" (where 'Lst' is a pointer to the list you're appending to, and 'val' is the value to append.) This will allocate a new node, set its value, and add the pointer to the end of the list. Once you've got that you can do a "remove" function. And then from there extend to allow insertion, etc. Then add 'pPrev' pointers if you want :wink
Just to be a barbarian, would it not be easier with the amount of code in the Pascal example to just build a tree ? It would have to be faster than a linked list.
Hi Tedd,
When I mean I know how to do the linked list by hand, I am referring to tracing the linked list by hand not so much as implementing it. I need some help.
Thanks.
Then you better read up on how a linked list works - once you understand it, you can get coding :P
But, I've started you off (attachment) :wink
I've left the interesting parts for you :bdg When you finish those functions, you can try adding 'pPrev' pointers in, and maintain them.
(If you then keep track of the last item, as well as the first, you can append quickly, and there's a nice shortcut for finding an item at an index past halfway.)
Note: you'll have to use a debugger if you want to see anything happening.
[attachment deleted by admin]
Hi Tedd,
In your code in the zip file,
What does this line do, the compiler complains about this line:
" mov eax,val "
Does the line above need to be corrected before it can run without errors
Is this the correct code below to print each item in the linked list?
LstTraverse Proc Lst:DWord
Push Ebx
Mov Ebx, Lst
Assume Ebx:Ptr NODE
Process:
print ([Ebx].value) ; print print the item of the list
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
Please reply back soon.
Thanks
Something tells me you haven't really read through the code and understood it - do that first!! (Not just what it does, but how and why it does it.)
"mov eax,val" will get the parameter 'val' into eax - if there is a parameter 'val' for the given function, otherwise it's not needed (and doesn't make sense), but that's what you get for blindly copying and pasting code ::)
If you "push ebx" at the start of a function, you should remember to "pop ebx" at the end :P (Also "assume ebx:nothing" to avoid error messages.)
Otherwise, your "traverse" doesn't look too bad :wink
Hi 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?
By the way, how do you set the pointer to always point to the head of the list?
My insert procedure for the linked list is below, can you check if I am on the right track?
Thanks
;insert an item into the given list, at a given 'index'
LstInsert Proc Lst:DWord, valu: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
Local counter:DWord
Local current:DWord
Push Ebx
Mov Ebx, Lst
Assume Ebx:Ptr NODE
Push Edx
Mov Edx, current
Assume Edx:Ptr NODE
Mov counter, 0
Mov Ecx, i
Process:
.If (counter == Ecx)
Jmp done
.ElseIf
Mov Eax, [Ebx].pNext ; get ptr to next
Mov Ebx, Eax
Inc counter
Mov Edi, [Edx].pNext
Test Eax, Eax
Jnz Process
.EndIf
done:
;(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, Edx ;add it to the end
mov ebx,eax
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
Assume Edx:Nothing
Pop Edx
Ret
LstInsert EndP
Hi Tedd,
Even if I had a debugger I would still not know how to set the links to the pointers correctly.
Quote from: etow on March 22, 2008, 11:01:10 PM
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
Quote
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.
Quote
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.
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
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 --
---------------------------------------------------------------------------------------------------------------------------
.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
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.
Why are pointers really hard to understand in assembly language?
It is very messy to understand.
Quote from: etow on June 24, 2008, 10:19:19 PM
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.)
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.
.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.
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