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

TABLE OF CONTENTS   



   (2)      41  DECLARATIONS

   (2)     182  DECLARATIONS

   (3)     205  SRCH_INSRT 

SRCHINSRT                                                        22-AUG-1978 04:40:57   VAX-11 MACRO X0.3-11               Page   1

X01.00          DECLARATIONS                                                                                                     (1)



                                     0000     1 	.TITLE	SRCHINSRT

                                     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 ROUTINE SEARCHES THE B-TREE FOR THE PLACE TO INSERT

                                     0000    28 ;		A KEY.  IT BUILDS A HISTORY LIST AND RETURNS A STATUS

                                     0000    29 ;		CODE AS TO WHETHER OR NOT THE KEY IS ALREADY IN THE B-TREE.

                                     0000    30 ;

                                     0000    31 ;

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

                                     0000    33 ;

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

                                     0000    35 ;

                                     0000    36 ; MODIFIED BY:

                                     0000    37 ;

                                     0000    38 ;	, : VERSION

                                     0000    39 ; 01	- 

                                     0000    40 ;--

SRCHINSRT                                                        22-AUG-1978 04:40:57   VAX-11 MACRO X0.3-11               Page   2

X01.00          DECLARATIONS                                                                                                     (2)



                                     0000    42 	.SBTTL	DECLARATIONS

                                     0000    43 ;

                                     0000    44 ; INCLUDE FILES:

                                     0000    45 ;

                                     0000    46 

                                     0000    47 ;

                                     0000    48 ; MACROS:

                                     0000    49 ;

                                     0000    50 

                                     0000    51 	$CRFDEF					; DEFINE CRF GLOBALS

                                     0000    52 

                                     0000    53 ;

                                     0000    54 ; EQUATED SYMBOLS:

                                     0000    55 ;

                                     0000    56 

                                     0000    57 ;

                                     0000    58 ; OWN STORAGE:

                                     0000    59 ;

                                     0000    60 

                                 00000000    61 	.PSECT	CRF$DATA,RD,WRT,NOEXE,NOSHR,PIC

                                     0000    62 

                           00000070  0000    63 CRF_HISTORY:: .BLKB	HIS$K_LISTSIZE		; HISTORY LIST

SRCHINSRT                                                        22-AUG-1978 04:40:57   VAX-11 MACRO X0.3-11               Page   3

X01.00          SRCH_INSRT                                                                                                       (3)



                                     0070    65 	.SBTTL	SRCH_INSRT 

                                     0070    66 ;++

                                     0070    67 ; FUNCTIONAL DESCRIPTION:

                                     0070    68 ;

                                     0070    69 ;	THIS ROUTINE SEARCHES THE B-TREE FOR THE INSERTION POINT FOR A 

                                     0070    70 ;	KEY SPECIFIED BY THE USER.  A HISTORY LIST IS BUILT TO POINT TO

                                     0070    71 ;	THE PLACE TO INSERT THE KEY.  IF THE KEY IS IN THE B-TREE, THE

                                     0070    72 ;	ADDRESS OF THE ENTRY IS RETURNED.

                                     0070    73 ;

                                     0070    74 ;	A HISTORY LIST ENTRY CONSISTS OF FOUR LONGWORDS AS FOLLOW:

                                     0070    75 ;		1) NODE ADDRESS

                                     0070    76 ;		2) OFFSET TO INSERTION POINT IN NODE

                                     0070    77 ;		3) LINK-UP OF ENTRY PREVIOUS TO INSERTION POINT

                                     0070    78 ;		   (LEFT SON OF NODE)

                                     0070    79 ;		4) LINK-UP OF ENTRY FOLLOWING INSERTION POINT

                                     0070    80 ;		   (RIGHT SON OF NODE)

                                     0070    81 ;	THIS ORGANIZATION PROVIDES THE LEFT AND RIGHT BROTHERS OF

                                     0070    82 ;	THE ACTUAL NODE TO RECEIVE THE NEW ENTRY AND ALSO THE LEFT

                                     0070    83 ;	AND RIGHT BROTHERS OF THE PREVIOUS NODES UP THE TREE (NEEDED

                                     0070    84 ;	FOR ROTATION).

                                     0070    85 ;

                                     0070    86 ; CALLING SEQUENCE:

                                     0070    87 ;

                                     0070    88 ;	CALLS	#0,SRCH_INSRT

                                     0070    89 ;

                                     0070    90 ; INPUT PARAMETERS:

                                     0070    91 ;

                                     0070    92 ;	NONE

                                     0070    93 ;

                                     0070    94 ; IMPLICIT INPUTS:

                                     0070    95 ;

                                     0070    96 ;	R4 - CONTAINS THE ADDRESS OF A HISTORY LIST TO BE BUILT

                                     0070    97 ;	R5 - CONTAINS THE ADDRESS OF THE SYMBOL TO BE INSERTED

                                     0070    98 ;	R6 - CONTAINS THE ADDRESS OF THE CRF CONTROL TABLE (TREE LISTHEAD)

                                     0070    99 ;

                                     0070   100 ; OUTPUT PARAMETERS:

                                     0070   101 ;

                                     0070   102 ;	NONE

                                     0070   103 ;

                                     0070   104 ; IMPLICIT OUTPUTS:

                                     0070   105 ;

                                     0070   106 ;	SUCCESS:

                                     0070   107 ;		R0 - CONTAINS AN ONE, INDICATING COMPLETED HISTORY LIST

                                     0070   108 ;		R1 - CONTAINS EITHER:

                                     0070   109 ;			ZERO INDICATING THE KEY IS NOT IN THE B-TREE, OR

                                     0070   110 ;			THE ADDRESS OF THE KEY IN THE B-TREE

                                     0070   111 ;	FAILURE:

                                     0070   112 ;		R0 - CONTAINS CRF$_HISTOVRFLO, INDICATING HISTORY LIST OVERFLOW

                                     0070   113 ;

                                     0070   114 ; COMPLETION CODES:

                                     0070   115 ;

                                     0070   116 ;	CRF$_SUCCESS - SUCCESSFUL STATUS CODE

                                     0070   117 ;	CRF$_HISTOVRFLO - FAILURE, HISTORY LIST OVERFLOWED

                                     0070   118 

                                     0070   119 ;

                                     0070   120 ; SIDE EFFECTS:

                                     0070   121 ;

SRCHINSRT                                                        22-AUG-1978 04:40:57   VAX-11 MACRO X0.3-11               Page   4

X01.00          SRCH_INSRT                                                                                                       (3)



                                     0070   122 ;	THE HISTORY LIST IS BUILT.

                                     0070   123 ;

                                     0070   124 ;--

                                     0070   125 

                                     0070   126 

                                     0070   127 

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

                                     0000   129 

                                     0000   130 SRCH_INSRT::

                               0794  0000   131 	.WORD	^M<R2,R4,R7,R8,R9,R10>	; ENTRY POINT (OR MASK)

                          59     D4  0002   132 	CLRL	R9				; CLR ADDR OF KEY IN TREE

   00000070 8F            54     C1  0004   133 	ADDL3	R4,#HIS$K_LISTSIZE,R10		; GET BOTTOM OF HIST LIST

                          5A         000B       

            58         04 A4     9E  000C   134 	MOVAB	HIS$L_TOP(R4),R8		; ADDR TO HOLD TOP OF LIST

                          84     7C  0010   135 	CLRQ	(R4)+				; CLR BOTTOM LIST ENTRY

                          84     7C  0012   136 	CLRQ	(R4)+				; CLR REST OF LIST ENTRY

                          64     7C  0014   137 	CLRQ	(R4)				; CLEAR ROOT OF TREE

            52            66     D0  0016   138 	MOVL	CRF$L_ROOT(R6),R2		; GET ADDR OF ROOT

                          3F     13  0019   139 	BEQL	60$				; NO ROOT, GO OFFSET HIST LIST

            57            52     D0  001B   140 10$:	MOVL	R2,R7				; GET LINK-UP OF PREV ENTRY

                          4B     13  001E   141 	BEQL	70$				; NO MORE LINK-UPS

            64            57     D0  0020   142 	MOVL	R7,HIS$L_NODE(R4)		; PUT NODE IN HISTORY LIST

                          FFDA'  30  0023   143 	BSBW	SRCH_NODE			; FIND INSERTION POINT IN NODE

            03            50     E9  0026   144 	BLBC	R0,20$				; BRANCH IF KEY NOT IN NODE

            59            51     D0  0029   145 	MOVL	R1,R9				; SAVE KEY ADDR IN B-TREE

            51            57     C3  002C   146 20$:	SUBL3	R7,R1,HIS$L_OFFSET(R4)		; SAVE INSRT PNT OFFSET

                       04 A4         002F       

                          07     13  0031   147 	BEQL	30$				; IF 0, AT DUMMY ENTRY

         0C A4         04 A1     D0  0033   148 	MOVL	KEY$L_LINKUP(R1),HIS$L_RIGHTSON(R4) ; SAVE RIGHT SON

                          03     11  0038   149 	BRB	40$				; SKIP DUMMY LINK-UP

                       0C A4     D4  003A   150 30$:	CLRL	HIS$L_RIGHTSON(R4)		; DUMMY, SAVE NO RIGHT SON

                       02 A1     B5  003D   151 40$:	TSTW	KEY$W_PREV(R1)			; PREV ENTRY?

                          15     13  0040   152 	BEQL	50$				; NO, THEN NO LEFT SON

            51         02 A1     3C  0042   153 	MOVZWL	KEY$W_PREV(R1),R1		; GET OFFSET INTO NODE

            51            57     C0  0046   154 	ADDL2	R7,R1				; ADD IN NODE ADDRESS

            51         02 A1     3C  0049   155 	MOVZWL	KEY$W_PREV(R1),R1		; GET OFFSET TO PREV ENTRY

            51            57     C0  004D   156 	ADDL2	R7,R1				; GET ADDR OF PREV ENTRY

         08 A4         04 A1     D0  0050   157 	MOVL	KEY$L_LINKUP(R1),HIS$L_LEFTSON(R4) ; SAVE LEFT SON

                          03     11  0055   158 	BRB	60$				; SKIP NO LEFT SON

                       08 A4     D4  0057   159 50$:	CLRL	HIS$L_LEFTSON(R4)		; NO LEFT SON FOR DUMMY

            54            10     C0  005A   160 60$:	ADDL2	#HIS$K_ENTRYSIZE,R4		; JUMP PAST THIS ENTRY

            5A            54     D1  005D   161 	CMPL	R4,R10				; OVERFLOW HISTORY LIST?

                          B9     1F  0060   162 	BLSSU	10$				; NO, CONTINUE SEARCH

            50   00658062 8F     D0  0062   163 	MOVL	#CRF$_HISTOVRFLO,R0		; SET OVERFLOW STATUS CODE

                          0E     11  0069   164 	BRB	SRCH_INSRT_EXIT			; RETURN

            51            59     D0  006B   165 70$:	MOVL	R9,R1				; SET ADDR OF KEY ENTRY

            50   00658001 8F     D0  006E   166 	MOVL	#CRF$_SUCCESS,R0		; SET SUCCESSFUL HIST BUILD

            68         F0 A4     9E  0075   167 	MOVAB	-HIS$K_ENTRYSIZE(R4),(R8)	; RECORD ADDR OF TOP OF HIST LIST

                                     0079   168 SRCH_INSRT_EXIT:

                                 04  0079   169 	RET					; RETURN

                                     007A   170 	.END

SRCHINSRT                                                        22-AUG-1978 04:40:57   VAX-11 MACRO X0.3-11               Page   5

SYMBOL TABLE                                                                                                                     (3)



BIT...         = 006580AA            FLD$K_LENGTH   = 0000000C            

CRF$B_FLAGS      00000009            FLD$L_FAODSC   = 00000004            

CRF$B_IR_DEFIND  00000014            FLD$W_MASK     = 00000000            

CRF$B_KEYTYPE    00000008            GBL...         = 00000000            

CRF$B_OU_PAG1    0000000C            HIS$K_ENTRYSIZE= 00000010            

CRF$B_OU_PRTIND  00000014            HIS$K_LISTSIZE = 00000070            

CRF$B_OU_SAVIND  00000018            HIS$L_FATHER   = FFFFFFF0            

CRF$B_OU_SUCPAG  00000010            HIS$L_FATHROFF = FFFFFFF4            

CRF$K_FACILCOD = 00000065            HIS$L_LEFTBRO  = FFFFFFF8            

CRF$L_ERROR      0000000C            HIS$L_LEFTSON  = 00000008            

CRF$L_IK_CTLTBL  00000004            HIS$L_LINKUP   = 00000008            

CRF$L_IK_KEYADR  00000008            HIS$L_LINKUPOFF= 0000000C            

CRF$L_IK_VALADR  0000000C            HIS$L_NODE     = 00000000            

CRF$L_IR_CTLTBL  00000004            HIS$L_NTH      = 0000000C            

CRF$L_IR_KEYADR  00000008            HIS$L_OFFSET   = 00000004            

CRF$L_IR_REFADR  0000000C            HIS$L_RIGHTBRO = FFFFFFFC            

CRF$L_K1FMTBL    00000014            HIS$L_RIGHTSON = 0000000C            

CRF$L_K2FMTBL    00000018            HIS$L_TOP      = 00000004            

CRF$L_OUTPUT     00000010            KEY$B_DEFLNG   = 00000018            

CRF$L_OU_CTLTBL  00000004            KEY$K_DATASIZE = 0000001C            

CRF$L_OU_LINWID  00000008            KEY$K_SIZE     = 00000028            

CRF$L_R1FMTBL    00000024            KEY$L_DATA     = 0000000C            

CRF$L_R2FMTBL    00000028            KEY$L_KEYADDR  = 00000008            

CRF$L_ROOT       00000000            KEY$L_LINKUP   = 00000004            

CRF$L_V1FMTBL    0000001C            KEY$L_REFLIST  = 00000010            

CRF$L_V2FMTBL    00000020            KEY$L_VALADDR  = 0000000C            

CRF$W_ENTSIZE    00000004            KEY$T_DEFNAME  = 00000019            

CRF$W_ERRSTS     0000000A            KEY$W_DEFFLAG  = 00000016            

CRF$W_IK_VALFLG  00000010            KEY$W_NEXT     = 00000000            

CRF$W_IR_REFLAG  00000010            KEY$W_PREV     = 00000002            

CRF$W_NODSIZE    00000006            KEY$W_VALFLAG  = 00000014            

CRF$_BLDNODFAIL= 00658052            NOD$K_1STFREE  = 00000010            

CRF$_BLKWTHINBL= 00658072            NOD$K_NUMFREE  = 0000000C            

CRF$_EXPREGFAIL= 0065806A            NOD$K_SIZE     = 000001F0            

CRF$_FAILINSRT = 0065807A            REF$B_REFLNG   = 00000006            

CRF$_FAOFAIL   = 0065809A            REF$K_SIZE     = 00000016            

CRF$_FOUNDKEY  = 00658021            REF$L_FLINK    = 00000000            

CRF$_HISTOVRFLO= 00658062            REF$T_REFNAME  = 00000007            

CRF$_ILLBLKSIZE= 00658082            REF$W_REFFLAG  = 00000004            

CRF$_KEY1STENTR= 00658011            SRCH_INSRT       00000000 RG    04   

CRF$_KEYPRVENTR= 00658009            SRCH_INSRT_EXIT  00000079 R     04   

CRF$_KEYTYPE   = 006580A2            SRCH_NODE        ********   X   04   

CRF$_LINELNG   = 00658092            

CRF$_NO_OUTRTN = 0065808A            

CRF$_REFLNG    = 0065805A            

CRF$_REFPRVENTR= 00658019            

CRF$_SUCCESS   = 00658001            

CRF_HISTORY      00000000 RG    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            

FLD$B_MAXLNG   = 00000003            

FLD$B_SET_CLR  = 00000002            

SRCHINSRT                                                        22-AUG-1978 04:40:57   VAX-11 MACRO X0.3-11               Page   6

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$DATA         00000070      03       PIC   USR   CON   REL   LCL NOSHR NOEXE   RD    WRT BYTE  

CRF$CODE         0000007A      04       PIC   USR   CON   REL   LCL   SHR   EXE   RD  NOWRT BYTE  





THERE WERE NO ERRORS OR WARNINGS.

23566. BYTES LEFT IN FREE MEMORY POOL.

1432. BYTES OF RECLAIMED MEMORY.

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

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

