I've finished my linked list project in assembly and it can be downloaded here: http://aodw.hypermart.net/linkedList.zip
here is the program listing for your enjoyment :)
TITLE LinkedList (ll.asm)
;---------------------------------------------------------------------------------
;
; STUDENT ID: 1814539
;
; Purpose: To dynamically create a linked list and sort the nodes
; as they are inserted.
;
; Dependancies: kernal32.lib, user32.lib, irvine32.lib
;
; Input: The user enters integer values until his heart is content
; or the computer runs out of memory.
;
; Output: A sorted version of the numbers the user entered.
;
; Version History
; 1.10.0001 DS 2003/12/2 Writing the first build of the program
; 1.10.0002 DS 2003/12/2 Fixed 5 syntax errors
; 1.10.0003 DS 2003/12/2 Fixed logic error
; 1.10.0004 DS 2003/12/2 Fixed logic error
; 1.10.0005 DS 2003/12/2 Created a better driver program
; 1.10.0006 DS 2003/12/5 fixed a fatal error that caused the program to
; crash if the user didn't input anything into
; the list.
; 1.10.0006 DS 2003/12/5 Fixed a logic error that the earlier fix created
; 1.10.0007 DS 2003/12/5 Rebuilt the InsertSorted method
; 1.10.0008 DS 2003/12/6 Made a quick optimization to MakeNode
; 1.10.0009 DS 2003/12/7 "optimization" caused a major logic error, fixed
; 1.10.0010 DS 2003/12/7 Fixed up the less than functional Remove procedure
;
;----------------------------------------------------------------------------------
; #########################################################################
.386
.model flat, stdcall
; #########################################################################
.NOLIST
;include \masm32\include\windows.inc ; I'm getting errors from this...
include \masm32\include\user32.inc
include \masm32\include\kernel32.inc
includelib \masm32\lib\user32.lib
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\irvine32.lib
.LIST
; #########################################################################
;----------------------------------------
; Procedure Prototypes from irvine32.lib
;----------------------------------------
Crlf PROTO ; output carriage-return / linefeed
WriteString PROTO ; write null-terminated string to output
ReadInt PROTO
WriteDec PROTO
WriteChar PROTO
;----------------------------------------
; Symbols
;----------------------------------------
LMEM_ZEROINIT equ 0040h
;----------------------------------------
; List Structures
;----------------------------------------
ListNode STRUCT
Value DWORD 0
NextNode DWORD 0
ListNode ENDS
List STRUCT
HeadNode DWORD 0
TailNode DWORD 0
List ENDS
;----------------------------------------
; Prototypes
;----------------------------------------
MakeNode PROTO, value:DWORD ; Dynamically Allocates a new node and returns a pointer to it
Insert PROTO, theList:PTR List, ; Inserts a node into a list
value:DWORD
InsertSorted PROTO, theList:PTR List, ; Inserts a node into a list in ascending order
value:DWORD
Remove PROTO, theList:PTR List ; Removes a node from the back of a list
;-----------------------------------
; data segment
;-----------------------------------
.data
myList List<0,0>
PromptForNumber BYTE "Insert a number(-1 to quit): ",0
PromptLinkedList BYTE "The contents of the linked list is:",0
;-----------------------------------
; code segment
;-----------------------------------
.code
main PROC
next:
mov edx, OFFSET PromptForNumber
call WriteString
call ReadInt ; value returned in eax
cmp eax, -1
je cont
INVOKE InsertSorted, ADDR myList, eax
jmp next
cont:
mov esi, myList.HeadNode
test esi, esi ; is there a list?
jz done ; if not don't print the list
mov edx, OFFSET PromptLinkedList
call WriteString
call Crlf
printList:
mov eax, (ListNode PTR [esi]).Value
call WriteDec
mov al, ' '
call WriteChar
mov esi, (ListNode PTR [esi]).NextNode
cmp esi, 0
je done
jmp printList
done:
INVOKE ExitProcess, 0
main ENDP
;*****************************************************
; MakeNode
; Arguments: value:DWORD
;
; Returns: a pointer to a newly allocated ListNode
;
; Remarks: use this function to create a new node
; for a linked list.
;
;*****************************************************
MakeNode PROC, value:DWORD
push edx
push ecx
INVOKE LocalAlloc, LMEM_ZEROINIT, SIZEOF ListNode
mov edx, value
mov (ListNode PTR [eax]).Value, edx
mov (ListNode PTR [eax]).NextNode, 0
pop ecx
pop edx
ret
MakeNode ENDP
;*******************************************************
; Insert
; Arguments: theList:PTR List
; value :DWORD
;
; Returns: void
;
; Remarks: Use this function to insert a node into
; a linked list
; note: this function inserts at the front
;
;*******************************************************
Insert PROC, theList:PTR List,
value:DWORD
pushad
INVOKE MakeNode, value ; returns new node in eax
mov ebx, theList
mov edx, (List PTR [ebx]).TailNode
cmp (List PTR [ebx]).HeadNode, 0 ; if the pointer to head node is zero then the list is empty
je empty
mov (ListNode PTR [edx]).NextNode, eax
mov (List PTR [ebx]).TailNode, eax
jmp done
empty:
mov (List PTR [ebx]).HeadNode, eax
mov (List PTR [ebx]).TailNode, eax
done:
popad
ret
Insert ENDP
;*******************************************************
; InsertSorted
; Arguments: theList:PTR List
; value:DWORD
;
; Returns: void
;
;
; Remarks: Use this function to insert a node into
; a linked list sorted ascending
;
;
;*******************************************************
InsertSorted PROC, theList:PTR List,
value:DWORD
pushad
mov eax, theList
mov ebx, (List PTR [eax]).HeadNode
mov ecx, 0 ; ecx will be a pointer to the last node, if it is zero then we
; know that we're on our first node
; if(ebx == NULL) insert and set head and tail
test ebx, ebx ; is our list empty?
jz emptyList ; yes
; while(ebx.NextNode != NULL)
; if(value <= ebx.Value) insert value into the list in back of
next:
mov edx, value
cmp edx, (ListNode PTR [ebx]).Value
jle insertInBackOf ; ecx is not set if this is the first node
mov edx, (ListNode PTR [ebx]).NextNode
test edx, edx ; is the next node null?
jz InsertAtTail ; yes, this is our tail
mov ecx, ebx ; save current node
mov ebx, edx ; save our next node
jmp next
insertAtTail:
;insert in the back and set the tail
invoke MakeNode, value
mov ecx, eax ; store the new node in ecx for later use
mov eax, theList
mov eax, (List PTR [eax]).TailNode
mov (ListNode PTR [eax]).NextNode, ecx
mov eax, theList
mov (List PTR [eax]).TailNode, ecx
jmp done
insertInBackOf:
; note: ebx = current node
; ecx = previous node
test ecx, ecx ; if ecx is null then this is our first node
jz firstNode ; it is so insert it as our first node
invoke MakeNode, value
mov (ListNode PTR [eax]).NextNode, ebx ; ebx is our current node
mov (ListNode PTR [ecx]).NextNode, eax
jmp done
firstNode:
; insert node at head
mov ebx, theList
mov ecx, (List PTR [ebx]).HeadNode ; save our current head pointer
invoke MakeNode, value
mov (List PTR [ebx]).HeadNode, eax ; set the head pointer to our new pointer
mov (ListNode PTR [eax]).NextNode, ecx ; put our saved pointer in the next node of our new pointer
jmp done
emptyList:
; list is empty
invoke MakeNode, value
mov ecx, eax ; save our new node
mov eax, theList
mov (List PTR [eax]).HeadNode, ecx
mov (List PTR [eax]).TailNode, ecx
done:
popad
ret
InsertSorted ENDP
;*******************************************************
; Remove
; Arguments: theList:PTR List
;
; Returns: 1 success
; 0 fail
;
;*******************************************************
Remove PROC, theList:PTR List
pushad
mov ebx, (List PTR [theList]).HeadNode
mov edx, theList
mov eax, 0
test ebx, ebx ; is the list empty?
jz done ; yes then quit
next:
mov eax, (ListNode PTR [ebx]).NextNode ; NextNode
cmp eax, (List PTR [edx]).TailNode ; is NextNode Tail Node ?
je continue ; yes, we've found it
mov ebx, (ListNode PTR [ebx]).NextNode ; save NextNode
jmp next
continue:
mov eax, (List PTR [edx]).TailNode
pushad
INVOKE LocalFree, eax ; these functions don't save my registers!!!
popad
mov (ListNode PTR [ebx]).NextNode, 0
mov (List PTR [edx]).TailNode, ebx
mov eax,1
done:
popad
ret
Remove ENDP
End main
comments/questions and critique is welcome.
I'll be honest: I didn't read that.
But I did a linked list and binary tree in SPARC once, and it was actually really nice. I like "mov ecx,[ecx]" in a loop, it's just so pretty! :)
Good job, though, this forum needs activity :)
Were all your registers being clobbered or only eax, ecx, and edx? It's perfectly acceptable in all x86 OSes that I've seen to clobber those three, but it's generally quite rude to go ruining other registers from your caller without prior arrangement.
just eax, ecx and edx. I understand that the return value is in eax, but why don't they save ecx and edx?
Quote from: Kp on December 15, 2003, 05:35 PM
Were all your registers being clobbered or only eax, ecx, and edx? It's perfectly acceptable in all x86 OSes that I've seen to clobber those three, but it's generally quite rude to go ruining other registers from your caller without prior arrangement.
That's more convention than anything. But you're right, the rest of the program would have to make special arrangements.
Quote from: Etheran on December 15, 2003, 05:43 PM
just eax, ecx and edx. I understand that the return value is in eax, but why don't they save ecx and edx?
edx is used to return 64-bit values (along with eax).
I just took the final in the class and am satisfied to tell you all that I got an A. ;D
Quote from: Etheran on December 15, 2003, 05:43 PM
just eax, ecx and edx. I understand that the return value is in eax, but why don't they save ecx and edx?
Well, ecx is the counter register, so it's nice to be able to clobber it if you wanted to do a loop using rep. As Skywing pointed out, edx is used for part of a 64 bit return. IMO, it's mostly a convenience issue that it got set up this way - for simple functions that only need a few registers in use, being able to clobber eax/ecx/edx and not be required to restore them can simplify code flow and simplify the function assembly.