mirror of https://github.com/lianthony/NT4.0
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
190 lines
2.7 KiB
190 lines
2.7 KiB
; Native Code Version of the function InsertNode to the main
|
|
; program compress. This function handles insertion of strings
|
|
; into a binary tree.
|
|
;
|
|
; (C) Microsoft Corperation
|
|
; Written by Steven Zeck July 1989
|
|
|
|
.model small,c
|
|
.286
|
|
|
|
ND struc
|
|
pNDright dw ?
|
|
pNDleft dw ?
|
|
pNDpar dw ?
|
|
pRingBuf dw ?
|
|
ND ends
|
|
|
|
cStrMax equ 18
|
|
.data
|
|
|
|
extrn cbMatchCur:word
|
|
extrn rgND:word
|
|
extrn nilND:word
|
|
extrn ringBuf:byte
|
|
extrn iMatchCur:word
|
|
extrn rgRoot:byte
|
|
|
|
retAddr dw 0 ;; Return address
|
|
|
|
doRet macro
|
|
pop si
|
|
pop di
|
|
jmp retAddr
|
|
endm
|
|
|
|
.code
|
|
extrn printL:proc, printR:proc, printI:proc
|
|
|
|
|
|
;; align 4
|
|
;;INSERTNODE PROC pascal uses si di, istring:word
|
|
|
|
INSERTNODE:
|
|
public pascal INSERTNODE
|
|
|
|
pKey equ ax
|
|
pNDNew equ dx
|
|
pND equ bx
|
|
|
|
; pKey = &ringBuf[iString];
|
|
|
|
pop retAddr ; custom entry sequence
|
|
pop ax
|
|
push di
|
|
push si
|
|
|
|
push ss
|
|
pop es
|
|
|
|
mov si,ax
|
|
mov di,si ; save for later use
|
|
|
|
; pND = &rgRoot[*pKey]; // start with tree index by first char in string
|
|
|
|
add si,offset ringBuf
|
|
lodsb
|
|
mov bl,al
|
|
mov pKey,si
|
|
|
|
mov bh,0
|
|
mov byte ptr cbMatchCur,bh ;cbMatchCur = 0
|
|
shl bx,3
|
|
add bx,offset rgRoot ; BX == pND
|
|
|
|
;* pNDNew = &rgND[iString];
|
|
|
|
shl di,3 ; later use
|
|
add di,OFFSET rgND
|
|
mov pNDNew,di
|
|
|
|
;* pNDNew->pNDleft = pNDNew->pNDright = &nilND;
|
|
|
|
mov [di].pNDleft,offset nilND
|
|
mov [di].pNDright,offset nilND
|
|
jmp short firstTime
|
|
|
|
retLeft:
|
|
mov si,pNDNew
|
|
mov [pND].pNDleft,si
|
|
mov [si].pNDpar,pND
|
|
|
|
ifdef debug
|
|
push bx
|
|
call printL
|
|
add sp,2
|
|
endif
|
|
doRet
|
|
stringLess:
|
|
cmp [pND].pNDleft,offset nilND ; else if if pND->pNDright == nil
|
|
je retLeft
|
|
|
|
mov pND,[pND].pNDleft
|
|
jmp short CompareStrings
|
|
|
|
retRight:
|
|
mov si,pNDNew
|
|
mov [pND].pNDRight,si
|
|
mov [si].pNDpar,pND
|
|
|
|
ifdef debug
|
|
push bx
|
|
call printR
|
|
add sp,2
|
|
endif
|
|
doRet
|
|
|
|
searchLoop:
|
|
popf ; if last string was >=
|
|
jb stringLess
|
|
firstTime:
|
|
cmp [pND].pNDright,offset nilND ; if pND->pNDright == nil
|
|
je retRight
|
|
|
|
mov pND,[pND].pNDright
|
|
|
|
CompareStrings:
|
|
mov di,[pND].pRingBuf
|
|
mov cx,cStrMax-1
|
|
|
|
rep cmpsb
|
|
|
|
je exactMatch
|
|
pushf
|
|
mov si,pKey
|
|
inc cx
|
|
neg cx
|
|
add cl,cStrMax
|
|
|
|
cmp cl,byte ptr cbMatchCur
|
|
jbe searchLoop
|
|
|
|
mov di,pNd
|
|
sub di,offset rgND ; pND - rgND
|
|
shr di,3
|
|
mov iMatchCur,di
|
|
mov byte ptr cbMatchCur,cl
|
|
jmp searchLoop
|
|
|
|
exactMatch:
|
|
mov ax,pNd
|
|
sub ax,offset rgND ; pND - rgND
|
|
shr ax,3
|
|
mov iMatchCur,ax
|
|
mov byte ptr cbMatchCur,18
|
|
|
|
mov di,pNDNew
|
|
mov si,pND
|
|
|
|
movsw ;*pNDNew = *pND
|
|
movsw
|
|
movsw
|
|
|
|
mov si,[pND].pNDleft
|
|
mov [si].pNDpar,pNDNew
|
|
|
|
mov si,[pND].pNDright
|
|
mov [si].pNDpar,pNDNew
|
|
|
|
mov si,[pND].pNDpar
|
|
cmp [si].pNDright,pND
|
|
jne L20
|
|
|
|
mov [si].pNDright,pNDNew
|
|
jmp short L21
|
|
|
|
L20:
|
|
mov [si].pNDleft,pNDNew
|
|
L21:
|
|
mov [pND].pNDpar,offset nilND
|
|
|
|
ifdef debug
|
|
push bx
|
|
call printI
|
|
add sp,2
|
|
endif
|
|
doRet
|
|
|
|
;;InsertNode ENDP
|
|
|
|
end
|