Trailing-Edge
-
PDP-10 Archives
-
decuslib20-06
-
decus/20-158/bintab.mac
There are no other files named bintab.mac in the archive.
00100 TITLE BINTAB BINARY-SEARCH-TABLE MANIPULATION ROUTINES
00200 SUBTTL DEFINITIONS
00300
00400 COMMENT \
00500
00600 These routines provide a capability similar to the DECSYSTEM-20
00700 TBLUK and TBADD JSYSes except that a simpler (shorter) format is
00800 used for the data. The table which stores the data has the following
00900 format:
01000
01100 |-------------------------------------------------|
01200 Word 0 | # of actual entries | Max. # of entries |
01300 |-------------------------------------------------|
01400 Word 1 | Address of argument | Data for user prog. |
01500 |-------------------------------------------------|
01600 Word 2 | Address of argument | Data for user prog. |
01700 |-------------------------------------------------|
01800 | |
01900 | etc. |
02000 | |
02100 |-------------------------------------------------|
02200
02300 The arguments are themselves one-word values stored somewhere in
02400 memory (not necessarily in order). The table of addresses is
02500 maintained in order of increasing value of arguments, though.
02600 This permits a simple binary-search method to be used to look up
02700 values in the table.
02800
02900 BINADD
03000 The BINADD procedure adds an entry to the sorted table and
03100 maintains sorted order. The calling sequence is a simple
03200 PUSHJ P,BINADD. The arguments are in the AC's in the manner of
03300 JSYSes:
03400
03500 Accepts in AC1: Address of word 0 (header word) of the table to
03600 which the entry is to be added.
03700 AC2: Entry to be added (refer to BINLUK for format of entry)
03800
03900 Returns +1 always with address in table of the new entry in
04000 the right-hand halfword of AC1; if the new entry was
04100 added the value of the left-halfword is 0.
04200
04300
04400 If the table is full, the left-halfword of AC1 is -1.
04500
04600 If the entry was already in the table, the left-halfword
04700 of AC1 is -2.
04800
04900 BINLUK
05000 The BINLUK procedure searches for a one-word value in a
05100 sorted table and returns either the address of the table entry in
05200 that table or the address where the entry would be if it were in
05300 the table. The calling sequence is a simple PUSHJ P,BINLUK. The
05400 arguments are in the AC's in the manner of JSYSes:
05500
05600 Accepts in AC1: address of word 0 (header word) of the table in which
05700 the entry is to be located.
05800 AC2: the value to be looked up.
05900
06000 Returns +1 always with
06100 AC1 containing in the right halfword the address in the table
06200 of the entry which matches the value sought or where it
06300 would be if it were in the table.
06400 The left halfword is 0 if the word is in the table, -1 if
06500 it is not.
06600
06700
06800
06900
07000 \
07100
07200 ENTRY BINLUK,BINADD
07300 SALL
07400 SEARCH MACSYM,MONSYM,CMD
07500 .REQUIRE SYS:MACREL
07600
07700 ;Accumulator definitions
07800
07900 T0==0
08000 A==1
08100 B==2
08200 C==3
08300 D==4
08400 Q1==5
08500 Q2==6
08600 Q3==7
08700 P1==10
08800 P2==11
08900 P3==12
09000 P4==13
09100 F==15
09200 L==16
09300 P=17
09400
09500 ;Definition of constants
09600
09700 .JBFF==121
09800 MAXCOR=777000
09900
10000 BINLUK: PUSH P,P1 ;LOW=P1
10100 PUSH P,P2 ;HIGH=P2
10200 MOVEI P1,(A) ;LOW=0 (RELATIVE TO TABLE ENTRIES)
10300 HLRZ P2,(A) ;HIGH=LENGTH+1 (RELATIVE TO TABLE ENTRIES)
10400 ADDI P2,1(P1)
10500
10600 BINLUP: CAIG P2,1(P1) ;WHILE HIGH>LOW+1 DO
10700 JRST NOTFND ; (OTHERWISE QUIT)
10800 MOVE A,P1
10900 ADD A,P2
11000 ASH A,-1 ;INDEX := (HIGH+LOW) DIV 2
11100 HLRZ P4,(A) ;GET ADDRESS OF TABLE VALUE
11200 MOVE P4,(P4) ;AND VALUE
11300 CAMN B,P4 ;IF NUMBER=TABLE[INDEX]
11400 JRST FND ; THEN FOUND=TRUE
11500 CAMLE B,P4 ; ELSE IF NUMBER>TABLE[INDEX]
11600 SKIPA P1,A ; THEN LOW:=INDEX
11700 MOVE P2,A ; ELSE HIGH:=INDEX
11800 JRST BINLUP ;END
11900
12000 NOTFND: HRRI A,1(P1) ;return the address LOW+1
12100 TLOA A,777777 ;FLAG AS NOT FOUND
12200 FND: TLZ A,777777 ;OR FOUND, AS THE CASE MAY BE
12300 POP P,P2
12400 POP P,P1
12500 RET ;AND GO BACK
12600
12700
12800 SUBTTL BINADD
12900 BINADD: PUSH P,P1
13000 PUSH P,B ;SAVE ENTRY TO ADD
13100 PUSH P,A ; AND ADDRESS OF TABLE HEADER
13200 HLRZ B,B ;GET ADDRESS OF DATA REPRESENTED BY ENTRY
13300 MOVE B,(B) ;NOW VALUE
13400 CALL BINLUK ;FIND OUT WHERE IT BELONGS
13500 TLNE A,777777 ;IS IT ALREADY IN THE TABLE?
13600 JRST ADDIN ;NO
13700 POP P,B ;YES - JUST STORE NEW ENTRY
13800 POP P,B ; OVER THE OLD (IGNORE SAVED A REG)
13900 MOVEM B,(A)
14000 HRLI A,-2 ;FLAG CONDITION FOR CALLER
14100 POP P,P1 ;RETORE AC
14200 RET ;AND RETURN
14300
14400 ;NEED TO ADD NEW ENTRY
14500
14600 ADDIN: POP P,B ;GET ADDRESS OF TABLE HEADER
14700 MOVE B,(B) ;AND CURR,,MAX SIZE OF TABLE
14800 HLRZ P1,B ;CURR SIZE IN P1
14900 CAIL P1,(B) ;CURR SIZE < MAX?
15000 JRST FULL ; NO - CAN'T ADD TO TABLE!
15100 AOS P1 ;OK TO ADD - TELL HEADER
15200 MOVE B,1(P) ;GET ADDR OF HEADER AGAIN
15300 HRLM P1,(B)
15400 ADDI P1,(B) ;COMPUTE ADDRESS OF END OF TABLE
15500 SUBI P1,(A) ;COMPUTE NUMBER OF WORDS TO MOVE DOWN
15600 MOVN P1,P1
15700 HRLZ P1,P1
15800 HRRI P1,(A) ;-COUNT,,ENTRY LOC
15900 POP P,B ;GET ENTRY TO MAKE
16000 EXCH B,(P1) ;MAKE ENTRY
16100 AOBJN P1,.-1 ;AND MOVE TABLE DOWN
16200 MOVEM B,(P1) ;NOW MOVE IN LAST ENTRY TO NEW END
16300 POP P,P1 ;RESTORE AND RETURN
16400 HRLI A,0 ;FLAG AS NORMAL RETURN
16500 RET
16600
16700 FULL: HRLI A,-1 ;RETURN FLAG FOR FULL TABLE
16800 POP P,B ;RESTORE AC'S AND RETURN
16900 POP P,P1
17000 RET
17100 END