CRFPREFIX                                                        22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   0

TABLE OF CONTENTS   



   (2)      41  DECLARATIONS

   (2)     183  DECLARATIONS

   (3)     205  FIND_KEY 

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   1

X01.00          DECLARATIONS                                                                                                     (1)



                                     0000     1 	.TITLE	FINDKEY 

                                     0000     2 	.IDENT	/X01.00/

                                     0000     3 

                                     0000     4 ;

                                     0000     5 ; COPYRIGHT (C) 1977

                                     0000     6 ; DIGITAL EQUIPMENT CORPORATION, MAYNARD, MASSACHUSETTS 01754

                                     0000     7 ;

                                     0000     8 ; THIS SOFTWARE IS FURNISHED  UNDER A LICENSE FOR USE ONLY ON A SINGLE

                                     0000     9 ; COMPUTER  SYSTEM AND  MAY BE  COPIED ONLY WITH  THE INCLUSION OF THE

                                     0000    10 ; ABOVE COPYRIGHT NOTICE.  THIS SOFTWARE, OR ANY OTHER COPIES THEREOF,

                                     0000    11 ; MAY NOT BE PROVIDED OR  OTHERWISE MADE AVAILABLE TO ANY OTHER PERSON

                                     0000    12 ; EXCEPT FOR USE ON SUCH SYSTEM AND TO ONE WHO AGREES TO THESE LICENSE

                                     0000    13 ; TERMS.  TITLE TO AND  OWNERSHIP OF THE  SOFTWARE  SHALL AT ALL TIMES

                                     0000    14 ; REMAIN IN DEC.

                                     0000    15 ;

                                     0000    16 ; THE INFORMATION IN THIS SOFTWARE IS SUBJECT TO CHANGE WITHOUT NOTICE

                                     0000    17 ; AND SHOULD  NOT BE CONSTRUED  AS A COMMITMENT  BY DIGITAL  EQUIPMENT

                                     0000    18 ; CORPORATION.

                                     0000    19 ;

                                     0000    20 ; DEC ASSUMES  NO  RESPONSIBILITY  FOR  THE USE OR  RELIABILITY OF ITS

                                     0000    21 ; SOFTWARE ON EQUIPMENT WHICH IS NOT SUPPLIED BY DEC.

                                     0000    22 ;

                                     0000    23 

                                     0000    24 ;++

                                     0000    25 ; FACILITY:  CROSS REFERENCE PROGRAM

                                     0000    26 ;

                                     0000    27 ; ABSTRACT:  THIS MODULE CONTAINS ROUTINES TO FIND THE NTH KEY IN THE

                                     0000    28 ;		B-TREE CONSTRUCTING A HISTORY LIST, AND TO FIND THE

                                     0000    29 ;		NEXT KEY IN THE B-TREE, GIVEN A PREVIOUSLY CONSTRUCTED

                                     0000    30 ;		HISTORY LIST.

                                     0000    31 ;

                                     0000    32 ;

                                     0000    33 ; ENVIRONMENT:  IT IS PART OF A LINKABLE IMAGE.

                                     0000    34 ;

                                     0000    35 ; AUTHOR:  K.D. MORSE, CREATION DATE:  28-APR-77

                                     0000    36 ;

                                     0000    37 ; MODIFIED BY:

                                     0000    38 ;

                                     0000    39 ;	, : VERSION

                                     0000    40 ; 01	- 

                                     0000    41 ;--

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   2

X01.00          DECLARATIONS                                                                                                     (2)



                                     0000    43 	.SBTTL	DECLARATIONS

                                     0000    44 ;

                                     0000    45 ; INCLUDE FILES:

                                     0000    46 ;

                                     0000    47 

                                     0000    48 ;

                                     0000    49 ; MACROS:

                                     0000    50 ;

                                     0000    51 

                                     0000    52 	$CRFDEF					; DEFINE CRF GLOBALS

                                     0000    53 

                                     0000    54 ;

                                     0000    55 ; EQUATED SYMBOLS:

                                     0000    56 ;

                                     0000    57 

                           00000008  0000    58 HIST_ENTRY_SIZ = 8				; SIZE OF HISTORY LIST ENTRY

                                     0000    59 

                                     0000    60 ;

                                     0000    61 ; OWN STORAGE:

                                     0000    62 ;

                                     0000    63 

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   3

X01.00          FIND_KEY                                                                                                         (3)



                                     0000    65 	.SBTTL	FIND_KEY 

                                     0000    66 ;++

                                     0000    67 ; FUNCTIONAL DESCRIPTION:

                                     0000    68 ;

                                     0000    69 ;	THIS MODULE CONTAINS TWO ROUTINES TO SEARCH THE B-TREE.

                                     0000    70 ;	THE FIRST SEARCHES FOR THE NTH KEY IN THE ENTIRE TREE, WHERE N

                                     0000    71 ;	IS A VALUE SUPPLIED BY THE CALLER.  IT BUILDS A HISTORY LIST

                                     0000    72 ;	AND RETURNS THE ADDRESS OF THE B-TREE ENTRY FOR THE NTH KEY.

                                     0000    73 ;	THE SECOND ENTRY POINT USES THE HISTORY LIST BUILT BY A SEARCH

                                     0000    74 ;	FOR THE NTH KEY AND FINDS THE NEXT LEXICALLY-ORDERED KEY IN THE

                                     0000    75 ;	B-TREE.  THIS ENTRY ADDRESS IS RETURNED WITH AN UPDATED HISTORY

                                     0000    76 ;	LIST.  BOTH ENTRY POINTS RETURN A SUCCESS OR FAILURE STATUS CODE.

                                     0000    77 ;

                                     0000    78 ; CALLING SEQUENCE:

                                     0000    79 ;

                                     0000    80 ;	CALLS	#0,FIND_NTH_KEY

                                     0000    81 ;	CALLS	#0,FIND_NEXT_KEY

                                     0000    82 ;

                                     0000    83 ; INPUT PARAMETERS:

                                     0000    84 ;

                                     0000    85 ;	NONE

                                     0000    86 ;

                                     0000    87 ; IMPLICIT INPUTS:

                                     0000    88 ;

                                     0000    89 ;	R4 - CONTAINS THE ADDRESS OF THE HISTORY LIST

                                     0000    90 ;	R5 - CONTAINS N, THE NUMBER OF THE KEY TO LOCATE IN THE B-TREE

                                     0000    91 ;	R6 - CONTAINS THE ADDRESS OF THE OUTPUT FORMAT TABLE (TREE LISTHEAD)

                                     0000    92 ;			(USED ONLY FOR FIND NTH KEY)

                                     0000    93 ;

                                     0000    94 ; OUTPUT PARAMETERS:

                                     0000    95 ;

                                     0000    96 ;	NONE

                                     0000    97 ;

                                     0000    98 ; IMPLICIT OUTPUTS:

                                     0000    99 ;

                                     0000   100 ;	SUCCESS:

                                     0000   101 ;		R0 - CONTAINS A ONE

                                     0000   102 ;		R1 - CONTAINS THE ADDRESS OF THE ENTRY CONTAINING THE NTH KEY

                                     0000   103 ;	FAILURE:

                                     0000   104 ;		R0 - CONTAINS A ZERO INDICATING NO NTH KEY

                                     0000   105 ;		R0 - CONTAINS CRF$_HISTOVRFLO INDICATING HISTORY LIST TOO SMALL

                                     0000   106 ;

                                     0000   107 ; COMPLETION CODES:

                                     0000   108 ;

                                     0000   109 ;	CRF$_SUCCESS - SUCCESSFUL STATUS CODE

                                     0000   110 ;	CRF$_HISTOVRFLO - FAILURE, HISTORY LIST OVERFLOWED

                                     0000   111 ;

                                     0000   112 ; SIDE EFFECTS:

                                     0000   113 ;

                                     0000   114 ;	THE HISTORY LIST IS BUILT/UPDATED.

                                     0000   115 ;

                                     0000   116 ;--

                                     0000   117 

                                     0000   118 	.ENABL	LSB

                                     0000   119 

                                     0000   120 

                                 00000000   121 	.PSECT	CRF$CODE,RD,NOWRT,EXE,SHR,PIC

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   4

X01.00          FIND_KEY                                                                                                         (3)



                                     0000   122 

                                     0000   123 FIND_NTH_KEY::

                               018C  0000   124 	.WORD	^M<R2,R3,R7,R8>			; ENTRY POINT (OR MASK)

            57         70 A4     9E  0002   125 	MOVAB	HIS$K_LISTSIZE(R4),R7		; GET ADDR TOP OF HIST LIST

                          84     D4  0006   126 	CLRL	(R4)+				; ZERO = BOT OF HIST LIST

            58            54     D0  0008   127 	MOVL	R4,R8				; ADDR FOR TOP OF HIST LIST

                          84     7C  000B   128 	CLRQ	(R4)+				; CLR BOT HIST LIST ENTRY

            84            55     D0  000D   129 	MOVL	R5,(R4)+			; STORE NUMBER OF ENTRY

            64            66     D0  0010   130 	MOVL	CRF$L_ROOT(R6),HIS$L_NODE(R4)	; PUT ROOT NODE ONTO LIST

                       04 A4     D4  0013   131 	CLRL	HIS$L_OFFSET(R4)		; CLEAR OFFSET TO ENTRY

                          14     11  0016   132 	BRB	5$				; BRANCH TO SEARCH ROUTINE

                                     0018   133 FIND_NEXT_KEY::

                               018C  0018   134 	.WORD	^M<R2,R3,R7,R8>			; ENTRY POINT (OR MASK)

            57         70 A4     9E  001A   135 	MOVAB	HIS$K_LISTSIZE(R4),R7		; GET ADDR TOP OF HIST LIST

                       0C A4     D6  001E   136 	INCL	HIS$L_NTH(R4)			; INC HIST LIST ENTRY #

            58         04 A4     9E  0021   137 	MOVAB	HIS$L_TOP(R4),R8		; COMPUTE WHERE TO STORE

            54         04 A4     D0  0025   138 	MOVL	HIS$L_TOP(R4),R4		; GET TOP ENTRY ON LIST

            55            01     9A  0029   139 	MOVZBL	#1,R5				; SET TO FIND NEXT ENTRY

       0000'CF            01     90  002C   140 5$:	MOVB	#1,W^CRF_INSRT_FLAG		; SET NEXT ENTRY SEARCH FLAG

            52            64     D0  0031   141 10$:	MOVL	HIS$L_NODE(R4),R2		; IS THERE A NODE ADDRESS?

                          02     12  0034   142 	BNEQ	20$				; YES, CONTINUE

                          4D     11  0036   143 	BRB	NO_MORE				; NO, NO MORE TREE TO SEARCH

         04 A4            64     C1  0038   144 20$:	ADDL3	HIS$L_NODE(R4),HIS$L_OFFSET(R4),R3 ; GET ENTRY ADDRESS

                          53         003C       

                       04 A3     D5  003D   145 	TSTL	KEY$L_LINKUP(R3)		; DOES ENTRY HAVE LINKUP?

                          19     13  0040   146 	BEQL	30$				; NO, EXIT DOWNWARD SEARCH

         08 A4         04 A3     D0  0042   147 	MOVL	KEY$L_LINKUP(R3),HIS$L_LINKUP(R4) ; PUT LINKUP ONTO LIST

                       0C A4     D4  0047   148 	CLRL	HIS$L_LINKUPOFF(R4)		; CLEAR OFFSET TO ENTRY

            54            08     C0  004A   149 	ADDL	#HIST_ENTRY_SIZ,R4		; MAKE LINKUP CURRENT ENTRY

            57            54     D1  004D   150 	CMPL	R4,R7				; AT TOP OF HIST LIST?

                          DF     1F  0050   151 	BLSSU	10$				; NO, ROOM FOR NEXT ENTRY

            50   00658062 8F     D0  0052   152 	MOVL	#CRF$_HISTOVRFLO,R0		; ERROR, FULL HIST LIST

                          2C     11  0059   153 	BRB	FIND_NTH_EXIT			; RETURN

                                     005B   154 ;

                                     005B   155 ; FOUND THE NODE FARTHEST DOWN THE TREE.  NOW FIND ITS ENTRY.

                                     005B   156 ;

                          FFA2'  30  005B   157 30$:	BSBW	GET_NXT_PRV			; GET NEXT ENTRY IN NODE

            0F            50     E8  005E   158 	BLBS	R0,40$				; BRANCH IF GOT IT

            54            08     C2  0061   159 	SUBL2	#HIST_ENTRY_SIZ,R4		; NO NEXT NODE, GO BACK

            52            64     D0  0064   160 	MOVL	HIS$L_NODE(R4),R2		; SET NEW NODE ADDR

                          1C     13  0067   161 	BEQL	NO_MORE				; BRANCH ON NO FATHER NODE

         04 A4            52     C1  0069   162 	ADDL3	R2,HIS$L_OFFSET(R4),R3		; TO ITS FATHER NODE

                          53         006D       

                          EB     11  006E   163 	BRB	30$				; FOR NEXT ENTRY

                                     0070   164 ;

                                     0070   165 ; FOUND THE NEXT ENTRY IN THE TREE.  DECIDE IF THIS IS IT.

                                     0070   166 ;

            68            54     D0  0070   167 40$:	MOVL	R4,(R8)				; SET NEW TOP OF HIST LIST

            51            52     C3  0073   168 	SUBL3	R2,R1,HIS$L_OFFSET(R4)		; SET OFFSET TO ENTRY

                       04 A4         0076       

                          55     D7  0078   169 	DECL	R5				; FOUND NEXT ENTRY

                          BC     12  007A   170 	BNEQ	20$				; BUT NOT ONE REQUESTED

            50   00658001 8F     D0  007C   171 	MOVL	#CRF$_SUCCESS,R0		; SUCCESS, FOUND ENTRY

                          02     11  0083   172 	BRB	FIND_NTH_EXIT			; RETURN

                                     0085   173 NO_MORE:

                          50     D4  0085   174 	CLRL	R0				; SET NO MORE STATUS CODE

                                     0087   175 FIND_NTH_EXIT:

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   5

X01.00          FIND_KEY                                                                                                         (3)



                                 04  0087   176 	RET					; RETURN

                                     0088   177 

                                     0088   178 	.DSABL	LSB

                                     0088   179 	.END

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   6

SYMBOL TABLE                                                                                                                     (3)



BIT...         = 006580AA            FIND_NTH_KEY     00000000 RG    03   

CRF$B_FLAGS      00000009            FLD$B_MAXLNG   = 00000003            

CRF$B_IR_DEFIND  00000014            FLD$B_SET_CLR  = 00000002            

CRF$B_KEYTYPE    00000008            FLD$K_LENGTH   = 0000000C            

CRF$B_OU_PAG1    0000000C            FLD$L_FAODSC   = 00000004            

CRF$B_OU_PRTIND  00000014            FLD$W_MASK     = 00000000            

CRF$B_OU_SAVIND  00000018            GBL...         = 00000000            

CRF$B_OU_SUCPAG  00000010            GET_NXT_PRV      ********   X   03   

CRF$K_FACILCOD = 00000065            HIS$K_ENTRYSIZE= 00000010            

CRF$L_ERROR      0000000C            HIS$K_LISTSIZE = 00000070            

CRF$L_IK_CTLTBL  00000004            HIS$L_FATHER   = FFFFFFF0            

CRF$L_IK_KEYADR  00000008            HIS$L_FATHROFF = FFFFFFF4            

CRF$L_IK_VALADR  0000000C            HIS$L_LEFTBRO  = FFFFFFF8            

CRF$L_IR_CTLTBL  00000004            HIS$L_LEFTSON  = 00000008            

CRF$L_IR_KEYADR  00000008            HIS$L_LINKUP   = 00000008            

CRF$L_IR_REFADR  0000000C            HIS$L_LINKUPOFF= 0000000C            

CRF$L_K1FMTBL    00000014            HIS$L_NODE     = 00000000            

CRF$L_K2FMTBL    00000018            HIS$L_NTH      = 0000000C            

CRF$L_OUTPUT     00000010            HIS$L_OFFSET   = 00000004            

CRF$L_OU_CTLTBL  00000004            HIS$L_RIGHTBRO = FFFFFFFC            

CRF$L_OU_LINWID  00000008            HIS$L_RIGHTSON = 0000000C            

CRF$L_R1FMTBL    00000024            HIS$L_TOP      = 00000004            

CRF$L_R2FMTBL    00000028            HIST_ENTRY_SIZ = 00000008            

CRF$L_ROOT       00000000            KEY$B_DEFLNG   = 00000018            

CRF$L_V1FMTBL    0000001C            KEY$K_DATASIZE = 0000001C            

CRF$L_V2FMTBL    00000020            KEY$K_SIZE     = 00000028            

CRF$W_ENTSIZE    00000004            KEY$L_DATA     = 0000000C            

CRF$W_ERRSTS     0000000A            KEY$L_KEYADDR  = 00000008            

CRF$W_IK_VALFLG  00000010            KEY$L_LINKUP   = 00000004            

CRF$W_IR_REFLAG  00000010            KEY$L_REFLIST  = 00000010            

CRF$W_NODSIZE    00000006            KEY$L_VALADDR  = 0000000C            

CRF$_BLDNODFAIL= 00658052            KEY$T_DEFNAME  = 00000019            

CRF$_BLKWTHINBL= 00658072            KEY$W_DEFFLAG  = 00000016            

CRF$_EXPREGFAIL= 0065806A            KEY$W_NEXT     = 00000000            

CRF$_FAILINSRT = 0065807A            KEY$W_PREV     = 00000002            

CRF$_FAOFAIL   = 0065809A            KEY$W_VALFLAG  = 00000014            

CRF$_FOUNDKEY  = 00658021            NOD$K_1STFREE  = 00000010            

CRF$_HISTOVRFLO= 00658062            NOD$K_NUMFREE  = 0000000C            

CRF$_ILLBLKSIZE= 00658082            NOD$K_SIZE     = 000001F0            

CRF$_KEY1STENTR= 00658011            NO_MORE          00000085 R     03   

CRF$_KEYPRVENTR= 00658009            REF$B_REFLNG   = 00000006            

CRF$_KEYTYPE   = 006580A2            REF$K_SIZE     = 00000016            

CRF$_LINELNG   = 00658092            REF$L_FLINK    = 00000000            

CRF$_NO_OUTRTN = 0065808A            REF$T_REFNAME  = 00000007            

CRF$_REFLNG    = 0065805A            REF$W_REFFLAG  = 00000004            

CRF$_REFPRVENTR= 00658019            

CRF$_SUCCESS   = 00658001            

CRF_INSRT_FLAG   ********   X   03   

DMY$K_SIZE     = 00000010            

DMY$L_KEYADDR  = 00000008            

DMY$L_LINKUP   = 00000004            

DMY$W_1STFREE  = 0000000E            

DMY$W_FIRST    = 00000000            

DMY$W_LAST     = 00000002            

DMY$W_NUMFREE  = 0000000C            

FIND_NEXT_KEY    00000018 RG    03   

FIND_NTH_EXIT    00000087 R     03   

FINDKEY                                                          22-AUG-1978 04:40:48   VAX-11 MACRO X0.3-11               Page   7

PROGRAM SECTION SYNOPSIS                                                                                                         (3)







PROGRAM SECTION SYNOPSIS



.  ABS  .        00000000      00     NOPIC   USR   CON   ABS   LCL NOSHR NOEXE NORD  NOWRT BYTE  

. BLANK .        00000000      01     NOPIC   USR   CON   REL   LCL NOSHR   EXE   RD    WRT BYTE  

$ABS$            0000002C      02     NOPIC   USR   CON   ABS   LCL NOSHR   EXE   RD    WRT BYTE  

CRF$CODE         00000088      03       PIC   USR   CON   REL   LCL   SHR   EXE   RD  NOWRT BYTE  





THERE WERE NO ERRORS OR WARNINGS.

23568. BYTES LEFT IN FREE MEMORY POOL.

1414. BYTES OF RECLAIMED MEMORY.

OBJ$:FINDKEY,LIS$:FINDKEY/-SP=LIB$:CRF/ML,SRC$:CRFPREFIX,FINDKEY

16 MLB DIR RDS - 149 GETS TO DEFINE 8 MACROS. 8 INTER. FILE WRITES. 

