;****************************************************************
;*                                                              *
;*  LLIST.ASM	-- Linked List Example				*
;*                                                              *
;****************************************************************
;*	Author:     Gene Apperson				*
;*	Copyright 2002, Gene Apperson				*
;****************************************************************
;*  Module Description:                                         *
;*                                                              *
;*  This is a design example for use in EE-314. 		*
;*                                                              *
;*                                                              *
;****************************************************************
;*  Revision History:                                           *
;*                                                              *
;*  03/02/2002(GeneA): created					*
;*                                                              *
;****************************************************************
;


; -------------------------------------------------------
;		Include File Definitions
; -------------------------------------------------------

	include segs.inc
	include dosdefs.inc

; -------------------------------------------------------
;		External Symbol Declarations
; -------------------------------------------------------


; -------------------------------------------------------
;		Local Symbol Definitions
; -------------------------------------------------------


; -------------------------------------------------------
;		Structure and Macro Definitions
; -------------------------------------------------------

node	struct

	pnodNext    dw	    ?
	value	    dw	    ?

node	ends

cbNode	equ	sizeof node

; -------------------------------------------------------
;		Code Segment Declarations
; -------------------------------------------------------

_TEXT	segment



_TEXT	ends

; -------------------------------------------------------
;		Data Segment Declarations
; -------------------------------------------------------

_STCK	segment

	dw	128 dup(?)

_STCK	ends



_DATA	segment

	public	    pnodHead
	public	    rgbNodes
	public	    pnodFree


array	    dw	3, 5, 1, -12, 27, 142, -13, 19, 23, 141
count	    dw	10
pintNext    dw	array	    ;pointer to next element of
			    ; array to use

rgbNodes    db	10*cbNode dup(?)    ;block of memory to use for
			    ; the nodes for the list
pnodFree    dw	rgbNodes    ;pointer to next available
			    ; slot in the rgbNodes array

pnodHead    dw	?	    ; head of list


_DATA	ends

;
;****************************************************************
        subttl
        page
;****************************************************************

_TEXT	segment
	assume	cs:_TEXT


;
;   main
;
; This procedure is a test harness to test the operation of
; the linked list subroutines.
;
;   Input:  none
;   Output: none
;   Errors: none
;   Uses:   All registers used

	public	main

main	proc	near

	mov	ax,_DATA
	mov	ds,ax
	mov	es,ax
	assume	ds:_DATA,es:_DATA
;
	mov	pnodHead,0	;init list head to empty
;
; Construct the list in sorted order
; Get the next free node, fill it in with the
; next value from the array, and then insert
; it into the list.
	mov	cx,count

main20: mov	dx,pnodFree	;pointer to next free node
	mov	bx,dx		;keep node pointer in BX
	assume	bx:PTR NODE
	add	dx,cbNode	;set pointer after this one
	mov	pnodFree,dx	;and store as next free one
	mov	[bx].pnodNext,0 ;init this node's next pointer

	mov	si,pintNext	;pointer to next array element
	mov	ax,[si] 	;get the array value
	mov	[bx].value,ax	;store into list node
	add	si,2		;advance array pointer
	mov	pintNext,si	;and store back into variable
;
	mov	ax,bx
	call	ListAddNode	;add this node to the list
;
	loop	main20

	assume	si:NOTHING
;
; Now, search the list for a couple of values
	mov	ax,19
	call	ListFindNode

	mov	ax,-12
	call	ListFindNode

	mov	ax,127
	call	ListFindNode
;
; Delete a couple of nodes from the list
	mov	ax,27
	call	ListFindNode
	call	ListDelNode



;
; All done
	mov	ah,fnExit
	int	21h

main	endp

; -------------------------------------------------------
;   ListAddNode
;
; Description:
;   This routine will add a node to a singly linked list
;   at the correct point to maintain the list in sorted
;   order
;
; Input:
;   AX	    - pointer to the node to add to the list
;
; Output:
;   none
;
; Errors:
;   none
;
; Uses:
;   AX used, all else preserved

	public	ListAddNode
	assume	ds:_DATA, es:_DATA

ListAddNode proc    near

	assume	bx:PTR NODE
	assume	si:PTR NODE
	assume	di:PTR NODE

	push	bx
	push	si
	push	di
;
	mov	bx,ax		;node to add in BX
	mov	si,pnodHead	;head of list to SI
	or	si,si		;check for empty list
	jz	ladd50		;if so, add this one at
				; the head of the list

ladd10: mov	ax,[bx].value	;get node value
	cmp	ax,[si].value	;check against current node
	jl	ladd20
	mov	di,si
	mov	si,[si].pnodNext
	or	si,si
	jnz	ladd10
;
ladd20: cmp	si,pnodHead	;check if we are on the
	jnz	ladd60		; first node, and if not
				; add into middle of list
;
; Add this node at the head of the list.
ladd50: mov	ax,pnodHead
	mov	[bx].pnodNext,ax
	mov	pnodhead,bx
	jmp	ladd90
;
; Add this node before the node pointed to by SI
ladd60: mov	ax,[di].pnodNext    ;pointer to list tail
	mov	[bx].pnodNext,ax    ;point this one at tail
	mov	[di].pnodNext,bx    ;insert this one into list
;
; All done
ladd90: pop	di
	pop	si
	pop	bx
	ret

	assume	bx:NOTHING, si:NOTHING, di:NOTHING

ListAddNode endp

; -------------------------------------------------------
;   ListFindNode
;
; Description:
;   This routine will search the ordered list for the
;   specified value.
;
; Input:
;   AX	    - value to search for
;
; Output:
;   AX	    - pointer to the list element
;
; Errors:
;   AX = 0, and ZR flag set if value not found
;
; Uses:
;   AX used, all else preserved

	assume	ds:_DATA,es:_DATA
	public	ListFindNode

ListFindNode proc   near

	assume	bx:PTR NODE

	push	bx
	mov	bx,pnodHead

lfnd20: or	bx,bx
	jz	lfnd80
	cmp	ax,[bx].value
	jz	lfnd90
	mov	bx,[bx].pnodNext
	jmp	lfnd20
;
; Hit end of list without finding value
lfnd80: xor	ax,ax
;
; All done
lfnd90: mov	ax,bx
	or	ax,ax
	pop	bx
	ret

	assume	bx:NOTHING

ListFindNode endp

; -------------------------------------------------------
;   ListDelNode
;
; Description:
;   This routine will delete the specified node from the
;   linked list.
;
; Input:
;   AX	    - pointer to the node to delete from list
;
; Output:
;   none
;
; Errors:
;   Returns CY set if error (specified node not in list)
;
; Uses:
;   AX used, all else preserve

	public	ListDelNode
	assume	ds:_DATA,es:_DATA

ListDelNode proc near

	assume	si:PTR NODE
	assume	di:PTR NODE

	push	si
	push	di
;
; Start at the head of the list
	mov	si,pnodHead ;pointer to cur node in SI
	xor	di,di	    ;pointer to prev node in DI
;
; Find the node being deleted.
ldel10: or	si,si	    ;at end of list?
	jz	ldel80	    ;if so, it isn't in the list
	cmp	ax,si	    ;is this the one?
	jz	ldel40	    ;if so, delete it
	mov	di,si	    ;cur node becomes prev node
	mov	si,[si].pnodNext    ;get new cur node
	jmp	ldel10	    ;and repeat
;
; Check if the node being deleted is at the head
; of the list. This requires special handling
ldel40: or	di,di
	jnz	ldel50
;
; The node being deleted is the head of the list.
	mov	ax,[si].pnodNext
	mov	pnodHead,ax
	jmp	ldel90
;
; DI contains the pointer to the node prior to the
; one to be deleted. SI contains pointer to the node
; being deleted
ldel50: mov	ax,[si].pnodNext
	mov	[di].pnodNext,ax
	or	ax,ax
	jmp	ldel90
;
; The node to be deleted isn't in the list
ldel80: stc
;
; All done
ldel90: pop	di
	pop	si
	ret

	assume	si:NOTHING, di:NOTHING

ListDelNode endp

; -------------------------------------------------------

_TEXT	ends


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

	end	main