; IfsDirKey.asm -- Directory CompareKey and EntryLength procedures
;			handed to B-tree package
; Copyright Xerox Corporation 1981

; Last modified May 3, 1981  12:35 PM by Taft

.ent DirCompareKey, DirEntryLength
.bext IFSError

; The following must agree with the FD structure in IfsFiles.decl
; and the DR structure in IfsDirs.decl.
FD.lenBodyString = 7.
FD.version = 9.
FD.dr = 10.
DR.header = 0.
DR.pathName = 6.
drHeaderMask = 171600
drLengthMask = 177

.dmr GetNextChar = 66400

.srel

DirCompareKey: .DirCompareKey
DirEntryLength: .DirEntryLength

.nrel

; DirCompareKey(fd, record)
; Returns -1 if fd (key) is less than record, 0 if equal, 1 if greater.
; Note: this procedure is not reentrant.

.DirCompareKey:
	sta 3 1 2
	sta 0 2 2		; fd
	sta 1 3 2		; record

; Set up CSD (character stream descriptor) for fd (key)
	mov 0 3			; fd
	lda 0 FD.lenBodyString 3 ; number of key characters to examine
	subzr 1 1		; 100000B
	add 1 0			; begin at right-hand byte
	lda 3 FD.dr 3
	lda 1 cDR.pathName
	add 3 1			; address of string in key
	lda 3 csdKey
	snz 3 3			; CSD pointers already set up?
	 jsr SetupCSDs		; no, do so first
	sta 0 0 3
	sta 1 1 3

; Set up CSD for record
	lda 3 3 2		; record
	lda 0 DR.header 3	; minimal check that this is really a DR
	lda 1 cdrHeaderMask
	and# 0 1 szr
	 jmp BadDR
	lda 0 DR.pathName 3	; extract string length
	lda 1 c177400
	ands 1 0
	subzr 1 1		; 100000B
	add 1 0			; begin at right-hand byte
	lda 1 cDR.pathName
	add 3 1			; address of string in record
	lda 3 csdRecord
	sta 0 0 3
	sta 1 1 3

; DirCompareKey (cont'd)

; Compare characters in the "<dir>name!" portion
CompareBodyLoop:
	lda 0 csdKey
	GetNextChar 140		; get char from key, convert to upper case
	 jmp KeyExhausted
	mov 1 3
	lda 0 csdRecord
	GetNextChar 140		; get char from record, convert to upper case
	 jmp RetGr		; exhausted: key is greater than record
	sne 1 3
	 jmp CompareBodyLoop	; equal, continue comparing

; First mismatch.  If all remaining characters of the record are digits
; then the record body is an initial substring of the key and we declare
; the key to be greater.  Otherwise we return the result of comparing
; the mismatching character codes.  Note that the only possible effect
; of looking at the rest of the record is to return "greater" where we
; otherwise would return "less".  But if keyChar > recChar anyway, then
; just say so now without bothering to check.
	slt 3 1
	 jmp RetGr

CheckDigitsLoop:
	lda 0 cDigit0		; recChar a digit?
	sub 0 1
	lda 0 d10
	sltu 1 0
	 jmp RetLs		; no, key is less than record
	lda 0 csdRecord
	GetNextChar 0		; get next char from record
	 jmp RetGr		; exhausted: key is greater than record
	jmp CheckDigitsLoop

; Key is exhausted before record: bodies seem to match.
; Now parse the version string in the directory entry and compare the
; key version number to it.  If a non-digit is encountered then the
; key body is an initial substring of the record and is therefore "less".
KeyExhausted:
	mkzero 3 3		; init parsed version
ParseVersionLoop:
	lda 0 csdRecord
	GetNextChar 0		; get next char from record
	 jmp VersionExhausted	; exhausted: go compare version numbers
	lda 0 cDigit0		; recChar a digit?
	sub 0 1
	lda 0 d10
	sltu 1 0
	 jmp RetLs		; no, key is less than record
	mov 3 0			; yes, multiply parsed version by 10
	addzl 3 3
	addzl 0 3
	add 1 3			; add in new digit
	jmp ParseVersionLoop

; Reached end of version number.  Compare key version to it.
VersionExhausted:
	mov 3 1
	lda 3 2 2		; fd
	lda 0 FD.version 3
	sne 0 1
	 jmp RetEq
	sltu 0 1
RetGr:	 mkone 0 0 skp		; key > record, return 1
RetLs:	  mkminusone 0 0	; key < record, return -1
	lda 3 1 2
	jmp 1 3

RetEq:	mkzero 0 0		; key = record, return 0
	lda 3 1 2
	jmp 1 3

; Internal procedure to set up csdRecord and csdKey.
; Returns with AC3 = csdKey.
; Does not disturb other ACs.

SetupCSDs:
	sta 3 csdBlk
	jsr AfterCSDs

csdBlk:	.blk 5

AfterCSDs:
	skeven 3 3		; force CSDs to be even
	 inc 3 3
	sta 3 csdRecord
	inc 3 3
	inc 3 3
	sta 3 csdKey
	jmp @csdBlk

csdKey:	.blk 1
csdRecord: .blk 1

c177400: 177400
cDigit0: 60
d10:	10.
cDR.pathName: DR.pathName



; DirEntryLength(record)
; returns the record's length.

.DirEntryLength:
	sta 0 2 2
	lda 0 @2 2
	lda 1 cdrHeaderMask	; Check for valid DR
	and# 1 0 szr		; Unused bits must be zero
	 jmp BadDRx
	lda 1 cdrLengthMask	; Extract length -- must be nonzero
	and 1 0 snr
	 jmp BadDRx
	jmp 1 3

BadDRx:	sta 3 1 2
BadDR:	lda 0 2 2
	lda 1 3 2
	jsr @370
	 6
	 77400
	lda 0 .ecBadDR
	jsrii lvIFSError	; IFSError(ecBadDR)
	 2

cdrHeaderMask: drHeaderMask
cdrLengthMask: drLengthMask

.ecBadDR: 120.
lvIFSError: IFSError

.end

// The following procedures are equivalent to the ones in this module:

//----------------------------------------------------------------------------
let DirCompareKey(fd, record) = valof
//----------------------------------------------------------------------------
// The CompareKeyRoutine passed to the B-Tree package.
// Compares the key "fd" with the pathName portion of
// the directory entry "record", returning -1, 0, or 1 if the
// key is respectively less than, equal to, or greater than the entry.
[
if (record>>DR.header & drHeaderMask) ne 0 then IFSError(ecBadDR)

// First, compare chars in the "<dir>name!" (string) portion
let key = fd>>FD.dr
let lenRecStr = record>>DR.pathName.length
for i = 1 to fd>>FD.lenBodyString do
   [
   // If we run off the end of the record then the key is greater.
   if i gr lenRecStr resultis 1

   let keyChar = key>>DR.pathName.char↑i
   let recChar = record>>DR.pathName.char↑i
   if keyChar ne recChar then
      [
      // Lower-case alphabetics collate with upper-case
      if keyChar ge $a & keyChar le $z then keyChar = keyChar-($a-$A)
      if recChar ge $a & recChar le $z then recChar = recChar-($a-$A)
      if keyChar ne recChar then
         [
         // Definitely a mismatch.  If all remaining characters of the
         // record are digits then the record body is an initial substring
         // of the key and we declare the key to be greater.  Otherwise we
         // return the result of comparing the mismatching character codes.
         // Note that the only possible effect of looking at the rest of the
         // record is to return "greater" where we otherwise would return
         // "less".  But if keyChar > recChar anyway, then just say so now
         // without bothering to check.
         if keyChar ls recChar then
            for j = i to lenRecStr do
               [
               let digit = record>>DR.pathName.char↑j - $0
               if digit ls 0 % digit gr 9 resultis -1
               ]
         resultis 1
         ]
      ]
   ]

// Bodies equal, now parse the version string in the directory
// entry and compare the key version number to it.
// If a non-digit is encountered then the key body is an initial substring
// of the record and we return "less than".
let version = 0
for i = fd>>FD.lenBodyString+1 to lenRecStr do
   [
   let digit = record>>DR.pathName.char↑i - $0
   if digit ls 0 % digit gr 9 resultis -1  //non-digit encountered
   version = 10*version+digit
   ]
resultis Usc(fd>>FD.version, version)
]

//----------------------------------------------------------------------------
and DirEntryLength(record) = valof
//----------------------------------------------------------------------------
[
let length = record>>DR.length
if (record>>DR.header & drHeaderMask) ne 0 % length eq 0 then
   IFSError(ecBadDR)
resultis length
]