SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2





      1						.TITLE	SRCIV

      2						.IDENT	/02/

      3

      4					;

      5					; COPYRIGHT   1975,  DIGITAL  EQUIPMENT  CORP.,  MAYNARD,   MASS.

      6					;

      7					; THIS SOFTWARE IS FURNISHED TO PURCHASER UNDER A LICENSE FOR USE

      8					; ON A SINGLE COMPUTER SYSTEM  AND  CAN BE COPIED (WITH INCLUSION

      9					; OF DEC'S COPYRIGHT NOTICE)  ONLY FOR USE IN SUCH SYSTEM, EXCEPT

     10					; AS MAY OTHERWISE BE PROVIDED IN WRITING BY DEC.

     11					;

     12					; THE INFORMATION IN  THIS DOCUMENT IS  SUBJECT TO CHANGE WITHOUT

     13					; NOTICE AND SHOULD NOT  BE CONSTRUED AS  A COMMITMENT BY DIGITAL

     14					; EQUIPMENT CORPORATION.

     15					;

     16					; DEC ASSUMES  NO  RESPONSIBILITY  FOR  THE  USE  OR  RELIABILITY

     17					; OF ITS  SOFTWARE  ON  EQUIPMENT  WHICH IS NOT  SUPPLIED BY DEC.

     18					;

     19					; VERSION 02

     20					;

     21					; C. MONIA 27-NOV-74

     22					;

     23					; VIRTUAL MEMORY SEARCH AND INSERT SUBROUTINES

     24					;

     25					; EQUATED SYMBOLS

     26					;

     27					; SYMBOL ENTRY OFFSETS

     28					;

     29

     30	000000					.ASECT

     31

     32		000000 			.=0

     33

     34	000000				S$YNXT:	.BLKW	1		; OFFSET TO NEXT (0=NONE)

     35	000002				S$YPRV:	.BLKW	1		; OFFSET TO PREVIOUS (0=NONE)

     36	000004				S$YUP:	.BLKW	1		; LINK UP (0=NONE)

     37	000006				S$YM:	.BLKW	1		; SYMBOL NAME (WORD 1)

     38	000010					.BLKW	1		; SYMBOL NAME (WORD 2)

     39	000012					.BLKW	1		; SYMBOL EXTENSION

     40

     41					;

     42					; B-TREE NODE OFFSETS

     43					;

     44

     45	000014					.ASECT

     46

     47	000014				B$HOL::	.BLKW	1		; OFFSET TO FIRST HOLE (0=NONE)

     48	000016				B$HCT::	.BLKW	1		; COUNT OF HOLES (0=NONE)

     49	000020				B$DAT::	.BLKW	1		; OFFSET TO NODE DATA AREA

     50

     51					;

     52					; HISTORY LIST ENTRY OFFSETS

     53					;

     54

     55	000022					.ASECT

     56

     57		000000 			.=0

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-1





     58

     59	000000				H$ISYM::.BLKW	1		; OFFSET TO INSERTION POINT

     60	000002				H$NODE::.BLKW	1		; VIRTUAL ADDRESS OF NODE ON PATH

     61	000004				H$LBR::	.BLKW	1		; VIRTUAL ADDRESS OF LEFT BROTHER

     62	000006				H$RBR::	.BLKW	1		; VIRTUAL ADDRESS OF RIGHT BROTHER

     63	000010				H$FINS::.BLKW	1		; INSERTION POINT OFFSET OF FATHER NODE

     64	000012				H$FNOD::.BLKW	1		; VIRTUAL ADDRESS OF FATHER NODE

     65

     66					;

     67					; LISTHEAD OFFSETS

     68					;

     69

     70	000014					.ASECT

     71

     72		000000 			.=0

     73

     74	000000				L$RNOD::.BLKW	1		; POINTER TO ROOT NODE (0=NONE)

     75	000002				L$ESIZ::.BLKW	1		; ENTRY SIZE (BYTES)

     76	000004				L$NSIZ::.BLKW	1		; NODE SIZE (BYTES)

     77

     78	000000					.PSECT

     79

     80

     81					;

     82					; LOCAL DATA (ADJACENCY ASSUMED).

     83					;

     84

     85	000000				LHEAD:	.BLKW	1		; POINTER TO B-TREE LISTHEAD

     86	000002				HPTR:	.BLKW	1		; HISTORY LIST POINTER

     87	000004				SYM:	.BLKW	1		; POINTER TO SYMBOL TO BE INSERTED

     88	000006				TSYM:	.BLKW	1		; POINTER TO SYMBOL FOR DOWN-TREE INSERTION

     89	000010				IFLG:	.BLKB	1		; INSERTION CONTROL FLAG

     90	000011					.BLKB	1		; RESERVED BYTE

     91	000012				RNEW:	.BLKW	1		; REAL ADDRESS OF NEW NODE

     92	000014				VNEW:	.BLKW	1		; VIRTUAL ADDRESS OF NEW NODE

     93	000016				VUP:	.BLKW	1		; VIRTUAL ADDRESS OF LINK-UP

     94	000020				EHIST:				; END OF HISTORY LIST

     95	000020					.BLKW	6.*4		; SEARCH HISTORY LIST

     96	000100	000000 				.WORD	0		; START OF HISTORY LIST

     97	000102	000000 				.WORD	0		; ...

     98	000104	000000 				.WORD	0		; ...

     99	000106	000000 			HIST:	.WORD	0		; ...

    100

    101					;+

    102					; VIRTUAL MEMORY SEARCH AND INSERT SUBROUTINES

    103					;

    104					; THESE SUBROUTINES ARE CALLED TO PERFORM THE FOLLOWING

    105					; FUNCTIONS:

    106					;

    107					;	'$SRCIV' - SEARCH A SYMBOL TABLE FOR EDIT OR INSERTION

    108					;	'$ISYMV' - INSERT A SYMBOL IN THE TABLE

    109					;	'$SRCHV' - SEARCH FOR A SPECIFIED ENTRY

    110					;	'$ISEDV' - PERFORM AN ORDERLY EDIT OF THE TABLE

    111					;	'$ISEDP' - PERFORM EDIT FROM SPECIFIED ENTRY IN TABLE

    112					;

    113					; THESE ROUTINES CONSTRUCT AND OPERATE ON A TABLE RESIDING IN

    114					; VIRTUAL MEMORY. THE TABLE IS STRUCTURD AS AN 'M-WAY'

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-2





    115					; TREE AS DESCRIBED IN KNUTH VOL. 3, SECTION 6.2.4. SPECIFICALLY

    116					; THE B-TREE STRUCTURE IS IMPLEMENTED WITH TWO-WAY SPLITTING

    117					; AND ROTATION TO EITHER THE LEFT OR RIGHT BROTHER

    118					;

    119					; DATA STRUCTURES:

    120					;

    121					;	TABLE LISTHEAD

    122					;

    123					; LHEAD:	.WORD	ROOT	; VIRTUAL ADDRESS OF ROOT NODE (0=NONE)

    124					;		.WORD	ESIZE	; SIZE OF EACH ENTRY (BYTES)

    125					;		.WORD	NSIZE	; SIZE OF EACH B-TREE NODE (BYTES)

    126					;

    127					;	B-TREE NODE FORMAT

    128					;

    129					;	NODE HEADER

    130					;

    131					; NODE:		.WORD	FIRST	; OFFSET TO FIRST ENTRY (0=NONE)

    132					;		.WORD	LAST	; OFFSET TO LAST ENTRY (0=NONE)

    133					;		.WORD	LNKUP	; VIRTUAL ADDRESS OF LINK UP (0=NONE)

    134					;		.WORD	-1	; DUMMY KEY

    135					;		.WORD	-1	; ...

    136					;		.WORD	-1	; KEY EXTENSION

    137					; B$HOL:	.WORD	HOLE	; OFFSET TO FIRST FREE HOLE (0=NONE)

    138					; B$HCT:	.WORD	COUNT	; NUMBER OF FREE HOLES

    139					; B$DAT:	.BLKW	NSIZ-20	; DATA AREA (INCLUDING EXTENSION)

    140					;

    141					; THE DATA AREA WITHIN EACH NODE IS SUBDIVIDED INTO FIXED

    142					; LENGTH BLOCKS EQUAL IN SIZE TO THE LENGTH OF AN ENTRY.

    143					; UNOCCUPIED BLOCKS (HOLES) ARE FORWARD LINKED VIA THE

    144					; FIRST WORD. ENTRIES ARE LINKED LINEARLY IN LEXICAL ASCENDING

    145					; ORDER AND HAVE THE FORMAT DESCRIBED BELOW. OBSERVE THAT

    146					; THE ENTRY LISTHEAD HAS THE SAME STRUCTURE AS THE ENTRY

    147					; ITSELF TO FACILITATE THE DETECTION OF ENDPOINTS.

    148					;

    149					; LINKAGES ARE VIA OFFSETS RELATIVE TO THE START OF

    150					; THE NODE.

    151					;

    152					;	SYMBOL TABLE ENTRY FORMAT

    153					;

    154					; S$YNXT:	.WORD	NEXT	; OFFSET TO NEXT (0=NONE)

    155					; S$YPRV:	.WORD	PREV	; OFFSET TO PREVIOUS (0=NONE)

    156					; S$YUP:	.WORD	LNKUP	; VIRTUAL ADDRESS OF LINK UP (0=NONE)

    157					; S$YM:		.WORD	SYMHI	; RADIX-50 SYMBOL NAME (WORD 1)

    158					;		.WORD	SYMLO	; RADIX-50 SYMBOL NAME (WORD 2)

    159					;		.WORD	SYMEXT	; OPTIONAL KEY EXTENSION

    160					; 		.BLKW	ESIZE-14 ; ENTRY DATA (WITH EXTENSION)

    161					;

    162					; OFFSETS ARE RELATIVE TO THE START OF THE NODE

    163					;

    164					;-

    165					;+

    166					; **-$ISEDV-PERFORM ORDERLY EDIT OF B-TREE

    167					; **-$ISEDP-PERFORM EDIT OF B-TREE FROM SPECIFIED ENTRY

    168					;

    169					; INPUTS:

    170					;

    171					;	R0=REAL ADDRESS OF B-TREE LISTHEAD

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-3





    172					; IF ENTRY IS AT $ISEDP:

    173					;

    174					;	R1=ADDRESS OF STARTING SYMBOL (SEE 'DATA STRUCTURES')

    175					;

    176					;

    177					; OUTPUTS:

    178					;

    179					;	C/CLEAR:

    180					;

    181					;	R0=REAL ADDRESS OF NEXT SYMBOL IN LEXICAL SEQUENCE

    182					;	R1=VIRTUAL ADDRESS OF NEXT SYMBOL IN LEXICAL SEQUENCE

    183					;

    184					;	CO-ROUTINE CALL IS MADE TO THE CALLER. TO TERMINATE

    185					;	THE EDIT, THE CALLER SHOULD REMOVE THE RETURN

    186					;	ADDRESS FROM THE STACK.

    187					;

    188					;	C/SET: NO FURTHER ENTRIES IN TREE

    189					;

    190					;	R1 IS CLEARED

    191					;

    192					;	EXIT IS VIA 'RETURN'

    193					;

    194					;

    195					; R3 - R5 ARE PRESERVED

    196					;

    197					; SUBROUTINE $ISEDV IS CALLED TO INITIALIZE A SCAN OF

    198					; ALL ENTRIES IN A B-TREE IN LEXICAL SEQUENCE. IF A VALID

    199					; ENTRY IS FOUND, THE ROUTINE EXECUTES A CO-ROUTINE CALL TO THE

    200					; CALLER WITH THE C-BIT CLEAR. SUBSEQUENT CO-ROUTINE CALLS

    201					; WILL RETURN THE REMAINDER OF THE ENTRIES IN SEQUENCE. THE

    202					; CALLER MAY TERMINATE THE SCAN BY REMOVING THE RETURN

    203					; ADDRESS FROM THE STACK. IF NO FURTHER ENTRIES REMAIN, THE

    204					; ROUTINE EXITS WITH C-SET VIA A 'RETURN'.

    205					;

    206					; SUBROUTINE $ISEDP IS CALLED TO INITIALIZE A SCAN OF

    207					; ALL ENTRIES FROM THE SPECIFIED KEY TO THE END

    208					; OF THE TABLES. IN ALL OTHER RESPECTS, IT IS IDENTICAL TO

    209					; $ISEDV.

    210					;

    211					;-

    212

    213	000110				$ISEDV::			;

    214	000110	012701 	000072'			MOV	#HIST-6-6,R1	; GET ADDRESS OF NULL SYMBOL ENTRY

    215	000114				$ISEDP::			;

    216	000114					CALL	$SRCIV		; BUILD HISTORY LIST

    217	000120	010446 				MOV	R4,-(SP)	; SAVE R4

    218	000122	016704 	177654 			MOV	HPTR,R4		; GET HISTORY LIST POINTER

    219	000126				10$:				;

    220	000126	011401 				MOV	(R4),R1		; GET OFFSET TO SYMBOL

    221	000130	001006 				BNE	20$		; IF NE NOT AT END OF NODE

    222	000132	005764 	000002 			TST	H$NODE(R4)	; AT END OF HISTORY LIST?

    223	000136	001436 				BEQ	60$		; IF EQ YES

    224	000140	062704 	000010 			ADD	#H$FINS,R4	; POP HISTORY LIST ENTRY

    225	000144	000770 				BR	10$		; GO AGAIN

    226	000146				20$:				;

    227	000146	006201 				ASR	R1		; CONVERT TO VIRTUAL OFFSET

    228	000150	066401 	000002 			ADD	H$NODE(R4),R1	; CONVERT TO VIRTUAL ENTRY ADDRESS

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-4





    229	000154					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    230	000160				30$:				;

    231	000160	010467 	177616 			MOV	R4,HPTR		; SAVE HISTORY LIST POINTER

    232	000164	012604 				MOV	(SP)+,R4	; RESTORE R4

    233	000166	000241 				CLC			; SET SUCCESS

    234	000170					CALL	@(SP)+		; CALL THE CALLER

    235	000172	010446 				MOV	R4,-(SP)	; SAVE R4

    236	000174	016704 	177602 			MOV	HPTR,R4		; GET HISTORY LIST POINTER

    237	000200	016401 	000002 			MOV	H$NODE(R4),R1	; GET VIRTUAL ADDRESS OF NODE

    238	000204					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    239	000210	062400 				ADD	(R4)+,R0	; OFFSET TO ADDRESS OF CURRENT ENTRY

    240	000212				40$:				;

    241	000212	011044 				MOV	(R0),-(R4)	; PUSH OFFSET TO NEXT

    242	000214	016001 	000004 			MOV	S$YUP(R0),R1	; GET VIRTUAL ADDRESS OF LINK UP

    243	000220	001742 				BEQ	10$		; IF EQ NO LINK UP

    244	000222	024444 				CMP	-(R4),-(R4)	; PUSH DUMMY ENTRIES

    245	000224	010144 				MOV	R1,-(R4)	; PUSH ADDRESS OF LINK UP

    246	000226					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    247	000232	000767 				BR	40$		; GO AGAIN

    248	000234				60$:				;

    249	000234	012604 				MOV	(SP)+,R4	; RESTORE R4

    250	000236	000261 				SEC			; FLAG END OF TABLE REACHED

    251	000240					RETURN			;

    252

    253					;+

    254					; **-$ISYMV-INSERT SYMBOL IN B-TREE

    255					;

    256					; INPUTS:

    257					;

    258					;	HISTORY LIST BUILT BY $SRCIV

    259					;

    260					; OUTPUTS:

    261					;

    262					;	C/SET: NEW ROOT NODE CREATED

    263					;

    264					;	C/CLEAR: NEW ROOT NOT CREATED

    265					;

    266					; R3 - R5 PRESERVED

    267					;

    268					; SPECIFIED KEY IS INSERTED IN THE TREE. C-SET INDICATES

    269					; THAT THE LISTHEAD WAS ALTERED. HENCE, THE CALLER SHOULD

    270					; WRITE-MARK THE APPROPRIATE PAGE IF THIS DATA IS KEPT

    271					; IN VIRTUAL MEMORY.

    272					;

    273					; THE INSERTION ROUTINE WILL UTILIZE ALL AVAILABLE SPACE

    274					; IN THE LEFT OR RIGHT BROTHERS BEFORE SPAWNING A NEW

    275					; NODE AT ANY LEVEL.

    276					;

    277					; PRIOR TO CALLING THIS ROUTINE $SRCIV MUST BE INVOKED TO

    278					; BUILD THE HISTORY LIST.

    279					;

    280					;-

    281

    282	000242				$ISYMV::			;

    283	000242					SAVRG			; SAVE NON-VOLATILE REGISTERS

    284	000246	005046 				CLR	-(SP)		; ASSUME ROOT NOT SPLIT

    285	000250	012703 	000000'			MOV	#LHEAD,R3	; POINT TO LISTHEAD STORAGE

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-5





    286	000254	012305 				MOV	(R3)+,R5	; GET ADDRESS OF LISTHEAD

    287	000256	012304 				MOV	(R3)+,R4	; GET HISTORY LIST POINTER

    288	000260	012303 				MOV	(R3)+,R3	; GET ADDRESS OF SYMBOL TO INSERT

    289	000262	016501 	000002 			MOV	L$ESIZ(R5),R1	; GET SIZE OF ENTRY

    290	000266	006301 				ASL	R1		; DOUBLE ENTRY SIZE

    291	000270					CALL	$ALBLK		; ALLOCATE HOLDING AREAS

    292	000274	010067 	177506 			MOV	R0,TSYM		; SET ADDRESS OF TEMP. SYMBOL STORAGE

    293	000300	066500 	000002 			ADD	L$ESIZ(R5),R0	; COMPUTE ADDRESS OF SYMBOL STORAGE

    294	000304	010067 	177474 			MOV	R0,SYM		; SAVE ADDRESS OF SYMBOL STORAGE

    295	000310	010001 				MOV	R0,R1		; COPY ADDRESS OF SYMBOL STORE

    296	000312					CALL	XFREN		; COPY SYMBOL DATA

    297	000316	005061 	000004 			CLR	S$YUP(R1)	; CLEAR LINK-UP

    298	000322	010103 				MOV	R1,R3		; SET SYMBOL ADDRESS

    299	000324				10$:				;

    300	000324	105067 	177460 			CLRB	IFLG		; ASSUME ROTATE/INSERT TO THE RIGHT

    301	000330	016401 	000002 			MOV	H$NODE(R4),R1	; GET ADDRESS OF INSERTION NODE

    302	000334	001006 				BNE	20$		; IF NE HAVE NODE

    303	000336					CALL	BLDND		; BUILD NEW ROOT NODE

    304	000342	011560 	000004 			MOV	(R5),S$YUP(R0)	; SET LINK-UP TO OLD ROOT

    305	000346	010115 				MOV	R1,(R5)		; SET ADDRESS OF NEW ROOT

    306	000350	005216 				INC	(SP)		; FLAG ROOT-SPLIT

    307	000352				20$:				;

    308	000352					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    309	000356	005760 	000014 			TST	B$HOL(R0)	; ROOM TO INSERT NEW ENTRY?

    310	000362	001402 				BEQ	25$		; IF EQ NO

    311	000364	000167 	000442 			JMP	110$		; INSERT ENTRY, EXIT

    312	000370				25$:				;

    313	000370	016401 	000004 			MOV	H$LBR(R4),R1	; GET ADDRESS OF LEFT BROTHER

    314	000374	001413 				BEQ	30$		; IF EQ NO LEFT BROTHER

    315	000376					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    316	000402	005760 	000014 			TST	B$HOL(R0)	; ROOM FOR AN ENTRY?

    317	000406	001406 				BEQ	30$		; IF EQ NO

    318	000410	105267 	177374 			INCB	IFLG		; SET ROTATION-LEFT FLAG

    319	000414	016467 	000002 	177374 		MOV	H$NODE(R4),VUP	; SET VIRTUAL ADDRESS OF NEW LINK-UP

    320	000422	000412 				BR	40$		; TO COMMON ROTATION CODE

    321	000424				30$:				;

    322	000424	016401 	000006 			MOV	H$RBR(R4),R1	; GET ADDRESS OF RIGHT BROTHER

    323	000430	001457 				BEQ	60$		; IF EQ NO RIGHT BROTHER

    324	000432					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    325	000436	005760 	000014 			TST	B$HOL(R0)	; ROOM FOR ENTRY IN RIGHT BROTHER?

    326	000442	001452 				BEQ	60$		; IF EQ NO, SPAWN NEW NODE

    327	000444	010167 	177346 			MOV	R1,VUP		; SET VIRTUAL ADDRESS OF NEW LINK-UP

    328

    329					;

    330					; COMMON ROTATION CODE

    331					;

    332					; THIS CODE IS ENTERED WHENEVER THERE IS SPACE FOR AN ENTRY

    333					; WITHIN AN EXISTING BROTHER NODE. THIS SECTION OF CODE

    334					; WILL TRANSFER THE FATHER ENTRY TO THE BROTHER NODE

    335					; SET THE LINK-UP OF THE INSERTED ENTRY AND RELEASE

    336					; THE SPACE WITHIN THE FATHER NODE. UPON COMPLE-

    337					; TION, COMMON CODE FOR DISTRIBUTING SPACE WITHIN

    338					; THE BROTHER NODES IS ENTERED. THE INSERTION PROCESS

    339					; AUTOMATICALLY TERMINATES ON SUCCESFUL INSERTION AT THE

    340					; LEVEL OF THE FATHER NODE

    341					;

    342					; OBSERVE THAT THE ROTATION PROCESS MAY ALTER THE INSERTION

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-6





    343					; POINT OF THE FATHER (IE FOR ROTATION TO THE RIGHT).

    344					;

    345

    346	000450				40$:				;

    347	000450					CALL	$WRMPG		; WRITE-MARK PAGE

    348	000454					CALL	$LCKPG		; LOCK PAGE IN MEMORY

    349	000460	010067 	177326 			MOV	R0,RNEW		; SAVE REAL ADDRESS OF NEW NODE

    350	000464	010167 	177324 			MOV	R1,VNEW		; SAVE VIRTUAL ADDRESS OF NEW NODE

    351	000470	016401 	000012 			MOV	H$FNOD(R4),R1	; GET VIRTUAL ADDRESS OF FATHER NODE

    352	000474					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    353	000500					CALL	$WRMPG		; WRITE-MARK PAGE

    354	000504	010002 				MOV	R0,R2		; COPY REAL ADDRESS

    355	000506	016403 	000010 			MOV	H$FINS(R4),R3	; GET OFFSET TO INSERTION POINT

    356	000512	060203 				ADD	R2,R3		; CONVERT TO ADDRESS

    357	000514	105367 	177270 			DECB	IFLG		; DECREMENT ROTATION FLAG

    358	000520	001002 				BNE	50$		; IF NE, ROTATION RIGHT

    359	000522					CALL	GTNXT		; GET PREVIOUS ENTRY

    360	000526				50$:				;

    361	000526	011364 	000010 			MOV	(R3),H$FINS(R4)	; SET NEW INSERTION POINT

    362	000532	105267 	177252 			INCB	IFLG		; RESET INSERTION FLAG

    363	000536	016700 	177250 			MOV	RNEW,R0		; GET REAL ADDRESS OF NEW

    364	000542					CALL	MOVEN		; ROTATE FATHER ENTRY AND DELETE IT

    365	000546	062701 	000004 			ADD	#S$YUP,R1	; POINT TO LINK-UP

    366	000552	010146 				MOV	R1,-(SP)	; SAVE ADDRESS OF ENTRY+OFFSET

    367	000554	011101 				MOV	(R1),R1		; GET VIRTUAL ADDRESS OF LINK-UP

    368	000556					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    369	000562	016036 	000004 			MOV	S$YUP(R0),@(SP)+ ; SET LINK-UP OF ROTATED ENTRY

    370	000566	000412 				BR	70$		; BALANCE SPACE IN BROTHERS

    371

    372					;

    373					; THIS SECTION OF CODE IS ENTERED TO CREATE A NEW BROTHER

    374					; NODE TO THE RIGHT OF THE INSERTION NODE. UPON COMPLETION

    375					; COMMON CODE TO BALANCE SPACE BETWEEN BROTHERS IS EXECUTED

    376					;

    377

    378	000570				60$:				;

    379	000570					CALL	BLDND		; CREATE A NEW NODE

    380	000574	010167 	177216 			MOV	R1,VUP		; SET VIRTUAL ADDRESS OF NEW LINK-UP

    381	000600					CALL	$LCKPG		; LOCK NEW PAGE IN MEMORY

    382	000604	010067 	177202 			MOV	R0,RNEW		; SAVE REAL ADDRESS OF NEW BROTHER

    383	000610	010167 	177200 			MOV	R1,VNEW		; SAVE VIRTUAL ADDRESS OF BROTHER

    384

    385					;

    386					; COMMON CODE TO BALANCE SPACE IN BROTHER NODES:

    387					;

    388					; THIS SECTION OF CODE TRANSFERS ENTRIES BETWEEN THE INSER-

    389					; TION NODE AND THE APPROPRIATE BROTHER UNTIL THE AMOUNT OF SPACE

    390					; IN BOTH NODES IS BALANCED. BALANCE IS ACHIEVED WHEN THE NUM-

    391					; BER OF HOLES IN THE BROTHER IS EQUAL TO OR ONE GREATER THAN

    392					; THE NUMBER OF HOLES IN THE INSERTION NODE.

    393					;

    394					;

    395

    396	000614				70$:				;

    397	000614	016401 	000002 			MOV	H$NODE(R4),R1	; GET VIRTUAL ADDRESS OF INSERTION NODE

    398	000620					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    399	000624					CALL	$WRMPG		; WRITE-MARK PAGE

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-7





    400	000630	016701 	177150 			MOV	SYM,R1		; GET ADDRESS OF SYMBOL TO INSERT

    401	000634	011402 				MOV	(R4),R2		; GET OFFSET TO INSERTION POINT

    402	000636					CALL	INSKY		; LOGICALLY INSERT KEY

    403	000642	010002 				MOV	R0,R2		; COPY ADDRESS OF INSERTION NODE

    404	000644	010003 				MOV	R0,R3		; SET LISTHEAD ADDRESS

    405	000646	016700 	177140 			MOV	RNEW,R0		; GET ADDRESS OF NEW NODE

    406	000652					CALL	GTNXT		; GET NEXT ENTRY IN SEQUENCE

    407	000656	005046 				CLR	-(SP)		; CLEAR PHYSICAL INSERT FLAG

    408	000660				80$:				;

    409	000660	016046 	000016 			MOV	B$HCT(R0),-(SP)	; PUSH ENTRY COUNT OF BROTHER

    410	000664	166216 	000016 			SUB	B$HCT(R2),(SP)	; SUBTRACT ENTRY COUNT OF INSERT NODE

    411	000670	022627 	000001 			CMP	(SP)+,#1	; NODES BALANCED?

    412	000674	101404 				BLOS	90$		; IF LOS YES

    413	000676					CALL	MOVEN		; TRANSFER NEXT ENTRY IN SEQUENCE

    414	000702	005516 				ADC	(SP)		; SAVE PHYSICAL INSERT FLAG

    415	000704	000765 				BR	80$		; GO AGAIN

    416

    417					;

    418					; THE NODES ARE NOW BALANCED. SETUP THE ENTRY TO BE

    419					; MOVED DOWN-TREE AND INSURE THAT THE ENTRY TO BE IN-

    420					; SERTED IS PHYSICALLY RESIDENT IN A NODE.

    421					;

    422

    423	000706				90$:				;

    424	000706	016701 	177074 			MOV	TSYM,R1		; GET TEMP SYMBOL STORAGE

    425	000712					CALL	MOVEN1		; MOVE THE LAST ENTRY FROM INSERT NODE

    426	000716	005526 				ADC	(SP)+		; SAVE PHYSICAL INSERT FLAG, TEST FLAG

    427	000720	001014 				BNE	100$		; IF NE ENTRY PHYSICALLY IN A NODE

    428	000722	010200 				MOV	R2,R0		; COPY INSERT NODE ADDRESS

    429	000724					CALL	RQNB		; REQUEST SPACE IN NODE

    430	000730	016703 	177050 			MOV	SYM,R3		; GET ADDRESS OF SYMBOL TO INSERT

    431	000734					CALL	XFREN		; TRANSFER ENTRY

    432	000740					CALL	DLTKY		; LOGICALLY DELETE THIS KEY

    433	000744	011302 				MOV	(R3),R2		; GET LINK NEXT

    434	000746					CALL	INSKY		; LOGICALLY INSERT NEW ENTRY

    435	000752				100$:				;

    436	000752	016703 	177030 			MOV	TSYM,R3		; GET ADDRESS OF TEMP SYMBOL STORE

    437	000756	016701 	177034 			MOV	VUP,R1		; GET VIRTUAL ADDRESS OF UP

    438	000762					CALL	$CVRL		; CONVERT TO REAL

    439	000766	016360 	000004 	000004 		MOV	S$YUP(R3),S$YUP(R0) ; SET NEW LINK-UP

    440	000774	010163 	000004 			MOV	R1,S$YUP(R3)	; SET LINK-UP OF SYMBOL

    441	001000	016767 	177000 	177000 		MOV	SYM,TSYM	; SWAP STORAGE POINTERS

    442	001006	010367 	176772 			MOV	R3,SYM		; ...

    443	001012	016701 	176776 			MOV	VNEW,R1		; GET VIRTUAL ADDRESS OF NEW

    444	001016					CALL	$UNLPG		; UNLOCK NEW

    445	001022	062704 	000010 			ADD	#H$FINS,R4	; POP LIST POINTER

    446	001026	000167 	177272 			JMP	10$		; GO AGAIN

    447

    448					;

    449					; TERMINATE INSERTION PROCESS

    450					;

    451

    452	001032				110$:				;

    453	001032					CALL	$WRMPG		; WRITE-MARK INSERTION NODE

    454	001036	011402 				MOV	(R4),R2		; GET OFFSET TO INSERTION POINT

    455	001040					CALL	RQNB		; REQUEST NODE ENTRY SPACE

    456	001044					CALL	XFREN		; MOVE ENTRY

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-8





    457	001050					CALL	INSKY		; LOGICALLY INSERT NEW KEY

    458	001054	016501 	000002 			MOV	L$ESIZ(R5),R1	; GET SIZE OF ENTRY

    459	001060	020367 	176722 			CMP	R3,TSYM		; AT START OF ALLOCATION

    460	001064	103401 				BLO	120$		; IF LO YES

    461	001066	160103 				SUB	R1,R3		; SET ADDRESS OF START

    462	001070				120$:				;

    463	001070	012700 	000000G			MOV	#$FRHD,R0	; GET ADDRESS OF FREE POOL LISTHEAD

    464	001074	010302 				MOV	R3,R2		; SET ADDRESS OF BLOCK TO RELEASE

    465	001076	006301 				ASL	R1		; SET SIZE OF BLOCK

    466	001100					CALL	$RLCB		; RELEASE TEMP STORAGE BLOCKS

    467	001104	006026 				ROR	(SP)+		; GET ROOT-SPLIT INDICATOR

    468	001106					RETURN			;

    469

    470					;+

    471					; **-$SRCHV-SEARCH B-TREE FOR ENTRY

    472					;

    473					; INPUTS:

    474					;

    475					;	R0=ADDRESS OF LISTHEAD

    476					;	R1=ADDRESS OF SYMBOL (SEE 'DATA STRUCTURES')

    477					;

    478					; OUTPUTS:

    479					;

    480					;	C/CLEAR: FOUND REQUESTED ENTRY

    481					;

    482					;	R0=REAL ADDRESS OF ENTRY

    483					;	R1=VIRTUAL ADDRESS OF ENTRY

    484					;

    485					;	C/SET: ENTRY NOT IN TREE

    486					;

    487					;	R1=0

    488					;

    489					; R3 - R5 ARE PRESERVED

    490					;-

    491

    492	001110				$SRCHV::			;

    493	001110					SAVRG			; SAVE NON-VOLATILE REGISTERS

    494	001114	010005 				MOV	R0,R5		; COPY LISTHEAD ADDRESS

    495	001116	010103 				MOV	R1,R3		; COPY ADDRESS OF SYMBOL

    496	001120	011502 				MOV	(R5),R2		; GET ROOT NODE VIRTUAL ADDRESS

    497	001122				10$:				;

    498	001122	010201 				MOV	R2,R1		; GET ADDRESS OF LINK-UP

    499	001124	000261 				SEC			; ASSUME NO LINK-UP

    500	001126	001405 				BEQ	20$		; IF EQ SYMBOL NOT IN LIST

    501	001130					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    502	001134					CALL	SRCKY		; SEARCH FOR SYMBOL

    503	001140	103770 				BCS	10$		; IF C/S NOT IN NODE

    504	001142				20$:				;

    505	001142					RETURN			;

    506

    507					;+

    508					; **-$SRCIV-SEARCH FOR INSERTION

    509					;

    510					; INPUTS:

    511					;

    512					;	R0=ADDRESS OF LISTHEAD (SEE 'DATA STRUCTURES')

    513					;	R1=ADDRESS OF SYMBOL TO BE INSERTED (SEE 'DATA STRUCTURES')

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-9





    514					;

    515					; OUTPUTS:

    516					;

    517					;	SEARCH HISTORY LIST IS BUILT CONTAINING THE NODES AND

    518					; INSERTION POINT OFFSETS FROM THE ROOT NODE TO THE

    519					; NODE TO RECEIVE THE SYMBOL ALONG WITH THE FOLLOWING:

    520					;

    521					;	C-SET: SYMBOL NOT IN TABLE

    522					;

    523					;	C-CLEAR: SYMBOL IN TABLE

    524					;

    525					;	R1=VIRTUAL ADDRESS OF SYMBOL

    526					;

    527					; R3-R5 PRESERVED

    528					;

    529					; SEARCH HISTORY LIST FORMAT:

    530					;

    531					; THE LIST RECORDS THE VIRTUAL ADDRESS OF EACH NODE ON THE

    532					; PATH FROM THE ROOT NODE TO THE NODE TO RECEIVE THE NEW ENTRY

    533					; ALONG WITH THE CORRESPONDING OFFSET TO THE ENTRY AFTER THE INSERTION

    534					; POINT.

    535					;

    536					; EACH ENTRY IN THE LIST HAS THE FOLLOWING FORMAT:

    537					;

    538					;		.

    539					;		.

    540					;		.

    541					;		.WORD	INSP	; OFFSET TO INSERTION POINT

    542					;		.WORD	NADDR	; VIRTUAL ADDRESS OF NODE CONTAINING POINT

    543					;		.WORD	LBRO	; LEFT BROTHER

    544					;		.WORD	RBRO	; RIGHT BROTHER

    545					;

    546					;-

    547

    548	001144				$SRCIV::			;

    549	001144					SAVRG			; SAVE NON-VOLATILE REGISTERS

    550	001150	012705 	000006'			MOV	#SYM+2,R5	; POINT TO LOCATION OF SYMBOL ADDRESS

    551	001154	010145 				MOV	R1,-(R5)	; SAVE ADDRESS OF NEW ENTRY

    552	001156	010103 				MOV	R1,R3		; COPY ADDRESS OF NEW SYMBOL

    553	001160	005745 				TST	-(R5)		; POINT TO LISTHEAD STORAGE

    554	001162	010045 				MOV	R0,-(R5)	; SAVE LISTHEAD ADDRESS

    555	001164	011505 				MOV	(R5),R5		; GET LISTHEAD ADDRESS

    556	001166	012704 	000100'			MOV	#HIST-6,R4	; SETUP POINTER TO HISTORY TABLE

    557	001172	005046 				CLR	-(SP)		; CLEAR REAL ADDRESS OF CURRENT NODE

    558	001174	005067 	176614 			CLR	VNEW		; CLEAR VIRTUAL ADDRESS OF FOUND SYMBOL

    559	001200	011502 				MOV	(R5),R2		; GET ADDRESS OF ROOT NODE

    560	001202				10$:				;

    561	001202	010201 				MOV	R2,R1		; GET ADDRESS OF LINK UP

    562	001204	001433 				BEQ	50$		; IF EQ NO LINK UP

    563	001206	010144 				MOV	R1,-(R4)	; PUSH LINK UP

    564	001210					CALL	$CVRL		; CONVERT TO REAL ADDRESS

    565	001214	010016 				MOV	R0,(SP)		; SAVE REAL ADDRESS

    566	001216					CALL	SRCKY		; SEARCH FOR KEY

    567	001222	103402 				BCS	20$		; IF C/S KEY NOT FOUND

    568	001224	010167 	176564 			MOV	R1,VNEW		; SAVE VIRTUAL ADDRESS OF KEY

    569	001230				20$:				;

    570	001230	010001 				MOV	R0,R1		; COPY REAL ADDRESS

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-10





    571	001232	161601 				SUB	(SP),R1		; CONVERT TO OFFSET

    572	001234	010144 				MOV	R1,-(R4)	; PUSH INSERTION POINT OFFSET

    573	001236	001402 				BEQ	25$		; IF EQ AT END OF NODE

    574	001240	016001 	000004 			MOV	S$YUP(R0),R1	; GET LINK-UP RIGHT

    575	001244				25$:				;

    576	001244	010144 				MOV	R1,-(R4)	; PUSH ON LIST

    577	001246	016001 	000002 			MOV	S$YPRV(R0),R1	; GET LINK-PREVIOUS OFFSET

    578	001252	001406 				BEQ	30$		; IF EQ NO LINK-PREVIOUS

    579	001254	061601 				ADD	(SP),R1		; CONVERT TO ADDRESS

    580	001256	016101 	000002 			MOV	S$YPRV(R1),R1	; GET LINK PREVIOUS AGAIN

    581	001262	061601 				ADD	(SP),R1		; CONVERT TO ADDRESS

    582	001264	016101 	000004 			MOV	S$YUP(R1),R1	; GET LINK-UP LEFT

    583	001270				30$:				;

    584	001270	010144 				MOV	R1,-(R4)	; PUSH LINK-UP LEFT

    585	001272	000743 				BR	10$		; GO AGAIN

    586	001274				50$:				;

    587	001274	000261 				SEC			; ASSUME SYMBOL NOT FOUND

    588	001276	016701 	176512 			MOV	VNEW,R1		; GET VIRTUAL ADDRESS OF SYMBOL

    589	001302	001401 				BEQ	60$		; IF EQ NOT FOUND

    590	001304	000241 				CLC			; SET FOUND INDICATOR

    591	001306				60$:				;

    592	001306	012424 				MOV	(R4)+,(R4)+	; ADJUST HISTORY LIST (LEAVE C BIT INTACT)

    593	001310	005226 				INC	(SP)+		; CLEAN STACK

    594	001312	010467 	176464 			MOV	R4,HPTR		; SAVE LIST POINTER

    595	001316					RETURN			;

    596

    597					;

    598					; BUILD NEW NODE

    599					;

    600					; THIS ROUTINE ALLOCATES A NEW B-TREE NODE AND CREATES THE

    601					; LIST OF FREE SPACE(HOLES)

    602					;

    603					; INPUTS:

    604					;

    605					;	R5=LISTHEAD ADDRESS

    606					;

    607					; OUTPUTS:

    608					;

    609					;	R0=REAL ADDRESS OF NODE

    610					;	R1=VIRTUAL ADDRESS OF NODE

    611					;

    612					;	THE FREE LIST WITHIN THE NODE IS BUILT

    613					;

    614					; R2 IS DESTROYED.

    615					;

    616

    617	001320				BLDND:				;

    618	001320	010346 				MOV	R3,-(SP)	; SAVE R3

    619	001322	016501 	000004 			MOV	L$NSIZ(R5),R1	; GET NODE SIZE (BYTES)

    620	001326					CALL	$ALVRT		; ALLOCATE VIRTUAL MEMORY

    621	001332	010046 				MOV	R0,-(SP)	; SAVE REAL ADDRESS

    622	001334	062700 	000006 			ADD	#S$YM,R0	; OFFSET TO DUMMY NAME

    623	001340	005320 				DEC	(R0)+		; SET DUMMY NAME (-1)

    624	001342	005320 				DEC	(R0)+		; ...

    625	001344	005320 				DEC	(R0)+		; ...

    626	001346	005720 				TST	(R0)+		; POINT TO HOLE COUNT

    627	001350	012703 	000020 			MOV	#B$DAT,R3	; SET OFFSET TO DATA AREA

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-11





    628	001354				10$:				;

    629	001354	010302 				MOV	R3,R2		; SET OFFSET TO NEXT HOLE

    630	001356	066503 	000002 			ADD	L$ESIZ(R5),R3	; ADD ENTRY SIZE TO OFFSET

    631	001362	020365 	000004 			CMP	R3,L$NSIZ(R5)	; HOLE ENTIRELY WITHIN NODE?

    632	001366	103007 				BHIS	20$		; IF HIS NO

    633	001370	005210 				INC	(R0)		; INCREMENT FREE COUNT

    634	001372	014046 				MOV	-(R0),-(SP)	; SAVE OFFSET TO FIRST HOLE

    635	001374	010220 				MOV	R2,(R0)+	; SET NEW FIRST

    636	001376	066602 	000002 			ADD	2(SP),R2	; CONVERT NEW FIRST TO ADDRESS

    637	001402	012612 				MOV	(SP)+,(R2)	; LINK OLD FIRST TO NEW

    638	001404	000763 				BR	10$		; GO AGAIN

    639	001406				20$:				;

    640	001406	012600 				MOV	(SP)+,R0	; GET REAL ADDRESS OF NODE

    641	001410	012603 				MOV	(SP)+,R3	; RESTORE R3

    642	001412					RETURN			;

    643

    644					;

    645					; LOGICALLY DELETE KEY FROM NODE

    646					;

    647					; INPUTS:

    648					;

    649					;	R2=NODE ADDRESS

    650					;	R3=ADDRESS OF ENTRY TO BE DELETED

    651					;

    652					; OUTPUTS:

    653					;

    654					;	ENTRY IS LOGICALLY DELETED, SPACE IS NOT RELEASED

    655					;

    656					; ALL REGISTER CONTENTS ARE PRESERVED.

    657					;

    658

    659	001414				DLTKY:				;

    660	001414	012346 				MOV	(R3)+,-(SP)	; PUSH LINK-NEXT OFFSET

    661	001416	060216 				ADD	R2,(SP)		; CONVERT LINK-NEXT TO ADDRESS

    662	001420	062716 	000002 			ADD	#S$YPRV,(SP)	; POINT TO LINK-PREVIOUS

    663	001424	011336 				MOV	(R3),@(SP)+	; SET NEW LINK-PREVIOUS

    664	001426	011346 				MOV	(R3),-(SP)	; PUSH LINK-PREVIOUS OFFSET

    665	001430	060216 				ADD	R2,(SP)		; CONVERT TO ADDRESS

    666	001432	014336 				MOV	-(R3),@(SP)+	; SET NEW LINK-NEXT

    667	001434					RETURN			;

    668

    669					;

    670					; GET NEXT/PREVIOUS ENTRY FROM NODE

    671					;

    672					; INPUTS:

    673					;

    674					;	R2=NODE ADDRESS

    675					;	R3=ADDRESS OF CURRENT ENTRY

    676					;	IFLG=1, GET NEXT ENTRY IN SEQUENCE

    677					;	IFLG=0, GET PREVIOUS ENTRY IN SEQUENCE

    678					;

    679					; OUTPUTS:

    680					;

    681					;	C/CLEAR:

    682					;

    683					;	R3=ADDRESS OF APPROPRIATE ENTRY

    684					;

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-12





    685					;	C/SET: NO MORE ENTRIES IN NODE

    686					;

    687					;	R3=NODE ADDRESS

    688					;

    689					; ALL OTHER REGISTER CONTENTS ARE PRESERVED

    690					;

    691

    692	001436				GTNXT:				;

    693	001436	105767 	176346 			TSTB	IFLG		; PREVIOUS WANTED?

    694	001442	001001 				BNE	10$		; IF NE NO, GET NEXT

    695	001444	005723 				TST	(R3)+		; STEP TO LINK-PREVIOUS

    696	001446				10$:				;

    697	001446	011303 				MOV	(R3),R3		; GET OFFSET TO REQUESTED ENTRY

    698	001450	060203 				ADD	R2,R3		; CONVERT TO ADDRESS

    699	001452	020203 				CMP	R2,R3		; AT LISTHEAD?

    700	001454	000241 				CLC			; ASSUME NO

    701	001456	001001 				BNE	20$		; IF NE NO

    702	001460	000261 				SEC			; SET C-BIT

    703	001462				20$:				;

    704	001462					RETURN			;

    705

    706					;

    707					; LOGICALLY INSERT ENTRY IN NODE

    708					;

    709					; INPUTS:

    710					;

    711					;	R0=ADDRESS OF NODE TO RECEIVE INSERT

    712					;	R1=ADDRESS OF ENTRY TO BE INSERTED

    713					;	R2=OFFSET TO INSERTION POINT

    714					;

    715					; OUTPUTS:

    716					;

    717					;	ENTRY IS LOGICALLY INSERTED IN NODE

    718					;

    719					; R2 IS DESTROYED

    720					;

    721

    722	001464				INSKY:				;

    723	001464	010146 				MOV	R1,-(SP)	; COPY ADDRESS OF NEW

    724	001466	160016 				SUB	R0,(SP)		; CONVERT TO OFFSET

    725	001470	010221 				MOV	R2,(R1)+	; SET LINK NEXT

    726	001472	060002 				ADD	R0,R2		; CONVERT LINK-NEXT TO ADDRESS

    727	001474	016211 	000002 			MOV	S$YPRV(R2),(R1)	; SET LINK-PREVIOUS

    728	001500	011662 	000002 			MOV	(SP),S$YPRV(R2)	; SET NEW LINK-PREVIOUS

    729	001504	011102 				MOV	(R1),R2		; GET LINK-PREVIOUS

    730	001506	060002 				ADD	R0,R2		; CONVERT TO ADDRESS

    731	001510	012612 				MOV	(SP)+,(R2)	; SET NEW LINK NEXT

    732	001512	005741 				TST	-(R1)		; POINT TO ADDRESS OF NEW

    733	001514					RETURN			;

    734

    735					;

    736					; MOVE ENTRY BETWEEN NODES

    737					;

    738					; THIS SUBROUTINE PHYSICALLY REMOVES AN ENTRY FROM A NODE

    739					; AND ADDS IT TO A NEW NODE. THE SPACE PREVIOUSLY OCCUPIED

    740					; IS RELEASED UNLESS THE ENTRY WAS LOGICALLY INSERTED ONLY.

    741					;

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-13





    742					; IF THE ENTRY WAS LOGICALLY INSERTED BUT DID NOT EXIST

    743					; AS A PHYSICAL ENTRY (IE A NEW INSERTION IN THE TABLE) THE C-BIT

    744					; IS SET ON EXIT. OTHERWISE, THE C-BIT IS CLEAR.

    745					;

    746					;

    747					; INPUTS:

    748					;

    749					;	R0=ADDRESS OF NODE TO RECEIVE ENTRY

    750					;	R2=ADDRESS OF NODE CONTAINING ENTRY

    751					;	R3=ADDRESS OF ENTRY TO BE MOVED

    752					;	SYM=ADDRESS OF NEW INSERT

    753					;

    754					; OUTPUTS:

    755					;

    756					; 	C/CLEAR: LOGICAL ENTRY NOT MOVED

    757					;

    758					;	R1=ADDRESS OF NEW ENTRY

    759					;	R3=ADDRESS OF NEXT ENTRY(0=END OF LIST)

    760					;

    761					;	C/SET: LOGICAL ENTRY MOVED

    762					;

    763					;	R1,R3 SETUP AS ABOVE

    764					;

    765					; ALL OTHER REGISTERS ARE UNMODIFIED

    766					;

    767

    768						.ENABL	LSB

    769

    770	001516				MOVEN:				;

    771	001516					CALL	RQNB		; REQUEST SPACE FOR NEW ENTRY

    772	001522	010246 				MOV	R2,-(SP)	; SAVE R2

    773	001524	011002 				MOV	(R0),R2		; ASSUME ROTATION RIGHT

    774	001526	105767 	176256 			TSTB	IFLG		; TEST ROTATION FLAG

    775	001532	001401 				BEQ	10$		; IF EQ ROTATION RIGHT

    776	001534	005002 				CLR	R2		; SET TO INSERT AT END

    777	001536				10$:				;

    778	001536					CALL	INSKY		; INSERT NEW KEY

    779	001542	012602 				MOV	(SP)+,R2	; RESTORE R2

    780	001544				MOVEN1:				;

    781	001544					CALL	XFREN		; MOVE ENTRY DATA

    782	001550	010346 				MOV	R3,-(SP)	; SAVE ADDRESS OF CURRENT

    783	001552					CALL	GTNXT		; GET ADDRESS OF NEXT ENTRY

    784	001556	010346 				MOV	R3,-(SP)	; SAVE ADDRESS OF NEXT

    785	001560	016603 	000002 			MOV	2(SP),R3	; GET CURRENT

    786	001564					CALL	DLTKY		; LOGICALLY DELETE THIS KEY

    787	001570	020367 	176210 			CMP	R3,SYM		; ENTRY PHYSICALLY IN NODE?

    788	001574	000261 				SEC			; ASSUME NO

    789	001576	001403 				BEQ	20$		; IF EQ NO

    790	001600					CALL	RLNB		; RELEASE ENTRY

    791	001604	000241 				CLC			; CLEAR C-BIT

    792	001606				20$:				;

    793	001606	012603 				MOV	(SP)+,R3	; GET ADDRESS OF NEXT

    794	001610	005226 				INC	(SP)+		; CLEAN STACK

    795	001612					RETURN			;

    796

    797						.DSABL	LSB

    798

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-14





    799

    800					;

    801					; RELEASE SPACE FOR AN ENTRY WITHIN A NODE

    802					;

    803					; INPUTS:

    804					;

    805					;	R2=NODE ADDRESS

    806					;	R3=ADDRESS OF ENTRY TO RELEASE

    807					;

    808					; OUTPUTS:

    809					;

    810					;	ENTRY IS RELEASED AND ADDED TO FREE LIST

    811					;

    812					; R3 IS DESTROYED

    813					;

    814

    815	001614				RLNB:				;

    816	001614	016213 	000014 			MOV	B$HOL(R2),(R3)	; SET POINTER TO NEXT HOLE

    817	001620	160203 				SUB	R2,R3		; CONVERT HOLE TO OFFSET

    818	001622	010362 	000014 			MOV	R3,B$HOL(R2)	; SET THIS ENTRY AS FIRST HOLE

    819	001626	005262 	000016 			INC	B$HCT(R2)	; INCREMENT HOLE COUNT

    820	001632					RETURN			;

    821

    822					;

    823					; REQUEST SPACE FOR ENTRY IN NODE

    824					;

    825					; INPUTS:

    826					;

    827					;	R0=NODE ADDRESS

    828					;

    829					; OUTPUTS:

    830					;

    831					;	C/CLEAR: REQUESTED SPACE AVAILABLE

    832					;	R1=ADDRESS OF BLOCK REQUESTED

    833					;

    834					;	C/SET: NO SPACE IN NODE

    835					;	R1=0

    836					;

    837

    838	001634				RQNB:				;

    839	001634	016001 	000014 			MOV	B$HOL(R0),R1	; GET OFFSET OF FIRST FREE HOLE

    840	001640	000261 				SEC			; ASSUME NO SPACE AVAILABLE

    841	001642	001405 				BEQ	10$		; IF EQ NO SPACE

    842	001644	060001 				ADD	R0,R1		; CONVERT TO ADDRESS

    843	001646	011160 	000014 			MOV	(R1),B$HOL(R0)	; SET NEW FIRST HOLE

    844	001652	005360 	000016 			DEC	B$HCT(R0)	; DECREMENT HOLE COUNT

    845	001656				10$:				;

    846	001656					RETURN			;

    847

    848					;

    849					; SEARCH NODE FOR KEY

    850					;

    851					; INPUTS:

    852					;

    853					;	R0=REAL ADDRESS OF NODE

    854					;	R1=VIRTUAL ADDRESS OF NODE

    855					;	R3=ADDRESS OF KEY

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-15





    856					;

    857					; OUTPUTS:

    858					;

    859					;	C/CLEAR: KEY FOUND

    860					;

    861					;	R0=REAL ADDRESS OF KEY

    862					;	R1=VIRTUAL ADDRESS OF KEY

    863					;	R2=VIRTUAL ADDRESS OF LINK UP FROM PRECEDING KEY

    864					;

    865					;	C/SET: KEY NOT IN NODE

    866					;

    867					;	R0=REAL ADDRESS OF KEY AT POINT FOR INSERTION

    868					;	R1=VIRTUAL ADDRESS OF KEY AT INSERTION POINT

    869					;	R2=VIRTUAL ADDRESS OF LINK UP FROM PREVIOUS KEY

    870					;

    871					; R3 - R5 UNMODIFIED

    872					;

    873

    874	001660				SRCKY:				;

    875	001660	010002 				MOV	R0,R2		; COPY REAL ADDRESS OF NODE

    876	001662	010146 				MOV	R1,-(SP)	; SAVE VIRTUAL ADDRESS

    877	001664	005046 				CLR	-(SP)		; SAVE SPACE FOR LINK-UP ON STACK

    878	001666				10$:				;

    879	001666	016016 	000004 			MOV	S$YUP(R0),(SP)	; SAVE LINK-UP OF PREVIOUS

    880	001672	011000 				MOV	(R0),R0		; GET LINK-NEXT OFFSET

    881	001674	060200 				ADD	R2,R0		; CONVERT TO ADDRESS

    882	001676	026360 	000006 	000006 		CMP	S$YM(R3),S$YM(R0) ; TEST FIRST HALF OF SYMBOL

    883	001704	101370 				BHI	10$		; IF HI GET NEXT ENTRY

    884	001706	103411 				BLO	20$		; IF LO SYMBOL NOT IN NODE (C-SET)

    885	001710	026360 	000010 	000010 		CMP	S$YM+2(R3),S$YM+2(R0) ; CHECK SECOND HALF OF SYMBOL

    886	001716	101363 				BHI	10$		; IF HI GET NEXT ENTRY

    887	001720	103404 				BLO	20$		; IF LO NOT IN NODE

    888	001722	026360 	000012 	000012 		CMP	S$YM+4(R3),S$YM+4(R0) ; CHECK EXTENSION

    889	001730	101356 				BHI	10$		; IF HI GET NEXT ENTRY

    890	001732				20$:				;

    891	001732	006046 				ROR	-(SP)		; SAVE FOUND FLAG

    892	001734	010001 				MOV	R0,R1		; COPY REAL ADDRESS

    893	001736	160201 				SUB	R2,R1		; COMPUTE OFFSET

    894	001740	006201 				ASR	R1		; CONVERT TO VIRTUAL OFFSET

    895	001742	066601 	000004 			ADD	4(SP),R1	; CONVERT TO VIRTUAL ADDRESS

    896	001746	006126 				ROL	(SP)+		; RESTORE C BIT

    897	001750	012602 				MOV	(SP)+,R2	; SET VIRTUAL ADDRESS OF LINK UP

    898	001752	005226 				INC	(SP)+		; CLEAN STACK

    899	001754					RETURN			;

    900

    901					;

    902					; TRANSFER AN ENTRY

    903					;

    904					; INPUTS:

    905					;

    906					;	R1=REAL ADDESS TO RECEIVE ENTRY

    907					;	R3=REAL ADDRESS OF ENTRY

    908					;	R5=ADDRESS OF LISTHEAD

    909					;

    910					; OUTPUTS:

    911					;

    912					;	ENTRY IS MOVED TO NEW LOCATION

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-16





    913					;

    914					; ALL REGISTERS ARE PRESERVED

    915					;

    916

    917	001756				XFREN:				;

    918	001756					SAVVR			; SAVE VOLATILE REGISTERS

    919	001762	010300 				MOV	R3,R0		; COPY ADDRESS OF ENTRY

    920	001764	016502 	000002 			MOV	L$ESIZ(R5),R2	; GET SIZE OF ENTRY

    921	001770	012746 	000004 			MOV	#S$YUP,-(SP)	; GET OFFSET TO LINK UP

    922	001774	161602 				SUB	(SP),R2		; SET TO MOVE ONLY LINK-UP PLUS DATA

    923	001776	006202 				ASR	R2		; CONVERT TO WORD COUNT

    924	002000	061601 				ADD	(SP),R1		; STEP TO LINK-UP OF NEW

    925	002002	062600 				ADD	(SP)+,R0	; STEP TO LINK-UP OF ENTRY

    926	002004				10$:				;

    927	002004	012021 				MOV	(R0)+,(R1)+	; TRANSFER ENTRY

    928	002006					SOB	R2,10$		; LOOP UNTIL COMPLETE

    929	002012					RETURN			;

    930

    931		000001 				.END

SRCIV	MACRO M1110  22-AUG-78 02:00  PAGE 2-17

SYMBOL TABLE



BLDND   001320R  	H$FINS  000010 G 	L$RNOD  000000 G 	S$YPRV  000002   	$ISEDV  000110RG

B$DAT   000020 G 	H$FNOD  000012 G 	MOVEN   001516R  	S$YUP   000004   	$ISYMV  000242RG

B$HCT   000016 G 	H$ISYM  000000 G 	MOVEN1  001544R  	TSYM    000006R  	$LCKPG= ****** GX

B$HOL   000014 G 	H$LBR   000004 G 	RLNB    001614R  	VNEW    000014R  	$RLCB = ****** GX

CR    = 000015   	H$NODE  000002 G 	RNEW    000012R  	VT    = 000013   	$SAVRG= ****** GX

DLTKY   001414R  	H$RBR   000006 G 	RQNB    001634R  	VUP     000016R  	$SAVVR= ****** GX

EHIST   000020R  	IFLG    000010R  	R$$11M= 000000   	XFREN   001756R  	$SRCHV  001110RG

FF    = 000014   	INSKY   001464R  	SPA   = 000040   	$ALBLK= ****** GX	$SRCIV  001144RG

GTNXT   001436R  	LF    = 000012   	SRCKY   001660R  	$ALVRT= ****** GX	$UNLPG= ****** GX

HIST    000106R  	LHEAD   000000R  	SYM     000004R  	$CVRL = ****** GX	$WRMPG= ****** GX

HPTR    000002R  	L$ESIZ  000002 G 	S$YM    000006   	$FRHD = ****** GX	$$    = 000001

HT    = 000011   	L$NSIZ  000004 G 	S$YNXT  000000   	$ISEDP  000114RG



. ABS.	000022	   000

      	002014	   001

ERRORS DETECTED:  0



VIRTUAL MEMORY USED:  983 WORDS  ( 4 PAGES)

DYNAMIC MEMORY:  2772 WORDS  ( 10 PAGES)

ELAPSED TIME:  00:00:16

OBJ$:SRCIV,LIS$:SRCIV/-SP=SRC$:MACFLM,SRCIV

