Author | Message | Time |
---|---|---|
Etheran | 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 :) [code] 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 [/code] comments/questions and critique is welcome. | December 15, 2003, 11:11 PM |
iago | 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 :) | December 15, 2003, 11:24 PM |
Kp | 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. | December 15, 2003, 11:35 PM |
Etheran | just eax, ecx and edx. I understand that the return value is in eax, but why don't they save ecx and edx? | December 15, 2003, 11:43 PM |
iago | [quote author=Kp link=board=7;threadid=4267;start=0#msg35594 date=1071531312] 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. [/quote] That's more convention than anything. But you're right, the rest of the program would have to make special arrangements. | December 15, 2003, 11:43 PM |
Skywing | [quote author=Etheran link=board=7;threadid=4267;start=0#msg35595 date=1071531808] just eax, ecx and edx. I understand that the return value is in eax, but why don't they save ecx and edx? [/quote] edx is used to return 64-bit values (along with eax). | December 16, 2003, 12:04 AM |
Etheran | I just took the final in the class and am satisfied to tell you all that I got an A. ;D | December 16, 2003, 3:25 AM |
Kp | [quote author=Etheran link=board=7;threadid=4267;start=0#msg35595 date=1071531808] just eax, ecx and edx. I understand that the return value is in eax, but why don't they save ecx and edx?[/quote] 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. | December 16, 2003, 4:13 AM |