Linked List project in x86

[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 Select Expand


   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.

[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

[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.

[Etheran]

just eax, ecx and edx.  I understand that the return value is in eax, but why don't they save ecx and edx?

[iago]

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.

[Skywing]

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).

[Etheran]

I just took the final in the class and am satisfied to tell you all that I got an A.  

[Kp]

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.