# 2.11BSD#431 - /usr/src/new/m11/srch.m11

       1:         .title  srch
       2:         .ident  /03apr4/
       3:
       4:         .mcall  (at)always,scan,genedt
       5:         .mcall (at)sdebug,ndebug
       6:         always
       7:
       8:         .globl  srchi
       9:         .globl  search, next,   scan,   scanc,  scanw
      10:         .globl  append, insert, zap
      11:         .globl  rolndx, rolupd, mactop , symbot
      12:
      13:         .globl  symovf
      14:
      15:         .globl  xmit0
      16:         .globl  symlp,  symhp,  dumrol
      17:         .globl  savreg, symbol
      18:
      19:         .if df  rsx11d
      20:         .globl  ed.reg, edmask, symrol, regrol, cpopj
      21:         .endc
      22:
      23:         xitsec                  ;start in default sector
      24:
      25: srchi:                          ;search init
      26:         mov     #dumrol,r0      ;end of variable rolls
      27: 1$:     mov     symhp,<^pl rolbas>(r0)  ;point all to top
      28:         mov     symhp,<^pl roltop>(r0)
      29:         clrb    <^pl rolsiz>+1(r0)
      30:         sub     #2,r0           ;get next lower
      31:         bge     1$
      32:         mov     symlp,mactop    ;bottom is start of macros
      33:         add     #bpmb-1,mactop  ;must be even
      34:         bic     #bpmb-1,mactop
      35:         mov     symhp,symbot    ;for sake of 'uplift' <<< REEDS
      36:         mov     symhp,symlp     ;symlp should always == symbot [debug, REEDS]
      37:         return
      38:         .if ndf rsx11d
      39:
      40: search:                         ;binary roll search
      41:         call    setrol          ;set roll registers
      42:         mov     r3,-(sp)
      43:         sub     r3,r1           ;point one slot low
      44:         mov     r2,r3
      45:         sub     r1,r3           ;compute size
      46:         clr     r0              ;get set to compute search offset
      47:         sec                     ;  (r0 doubles as t/f flag)
      48: 1$:     rol     r0              ;shift bit
      49:         bic     r0,r3           ;clear corresponding bit.  last one?
      50:         bne     1$              ;  no
      51: 2$:     add     r0,r1
      52: 3$:     asr     r0              ;end of iteration, halve offset
      53:         bic     #2,r0           ;end?
      54:         beq     7$              ;  yes
      55: 4$:     cmp     r2,r1           ;off in no-mans's land?
      56:         blos    6$              ;  yes
      57:         cmp     (r4),(r1)       ;no, first words match?
      58:         bne     5$              ;  no
      59:         cmp     2(r4),2(r1)     ;yes, how about second?
      60:         beq     8$              ;  yes, found
      61: 5$:     bhi     2$              ;no, branch if too high
      62: 6$:     sub     r0,r1           ;lower index
      63:         br      3$
      64:
      65: 7$:     cmp     (r1)+,(r1)+     ;point to insertion slot
      66: 8$:     mov     (sp)+,r3
      67:         br      scanx           ;exit through scan
      68:         .iff
      69:
      70: search:
      71:         call    setrol
      72:         bit     #ed.reg,edmask  ;register definition enabled?
      73:         bne     10$             ;if ne no
      74:         cmp     r5,#symrol      ;symbol roll?
      75:         bne     10$             ;if ne no
      76:         bit     #7,(r4)         ;make ruff ruff test bypass 90%
      77:         bne     10$             ;if ne don't check for register
      78:         scan    regrol          ;scan register roll
      79:         mov     r5,rolndx       ;restore roll index
      80:         tst     r0              ;find symbol?
      81:         beq     10$             ;if eq no find em
      82:         return                  ;
      83: 10$:    mov     r1,-(sp)        ;save roll base
      84:         cmp     r1,r2           ;any in roll?
      85:         beq     5$              ;if eq no
      86:         sub     r3,r2           ;calculate high and low bounds
      87:         mov     r1,r0           ;
      88:         bic     #177770,(sp)    ;
      89: 1$:     mov     r0,r1           ;calculate trial index
      90:         add     r2,r1           ;
      91:         ror     r1              ;halve result
      92:         bic     #7,r1           ;clear garbage bits
      93:         bis     (sp),r1         ;
      94:         cmp     (r1),(r4)       ;compare high parts
      95:         bhi     3$              ;if hi set new high limit
      96:         blo     2$              ;if lo set new low limit
      97:         cmp     2(r1),2(r4)     ;compare low parts
      98:         beq     6$              ;if eq hit
      99:         bhi     3$              ;if hi set new high limit
     100: 2$:     mov     r1,r0           ;set new low limit
     101:         add     r3,r0           ;reduce by one more
     102:         cmp     r0,r2           ;any more to search?
     103:         blos    1$              ;if los yes
     104:         add     r3,r1           ;point to proper entry
     105:         br      5$              ;exit
     106: 3$:     mov     r1,r2           ;se new high limit
     107:         sub     r3,r2           ;reduce by one more
     108:         cmp     r0,r2           ;any more to search?
     109:         blos    1$              ;if los yes
     110: 5$:     clr     r0              ;set false flag
     111: 6$:     tst     (sp)+           ;clean stack
     112:         br      scanx           ;vammoosa
     113:
     114:         genedt  reg
     115:
     116:         .endc
     117: next:                           ;get the next entry
     118:         call    setrol
     119:         mov     rolupd,r0
     120:         add     r0,r1
     121:         add     r3,r0
     122:         cmp     r1,r2
     123:         blo     scanx
     124:         br      scanxf
     125:
     126: scanw:                          ;scan one word
     127:         call    setrol          ;set registers
     128:         clr     r0              ;assume false
     129: 1$:     inc     r0              ;tally entry count
     130:         cmp     (r4),(r1)       ;match?
     131:         beq     scany           ;  yes
     132:         add     r3,r1           ;no, increment pointer
     133:         cmp     r1,r2           ;finished?
     134:         blo     1$              ;  no
     135:         clr     r0
     136:         return                  ;yes, exit false
     137:
     138: scanc:                          ;scan continuation
     139:         call    setrof          ;set regs
     140:         mov     rolpnt,r1       ;get current pointer
     141:         add     r3,r1           ;update
     142:         br      scanf           ;jump into middle
     143:
     144: scan:                           ;linear roll scan
     145:         call    setrol          ;set roll registers
     146: scanf:  clr     r0              ;assume false
     147: 1$:     cmp     r1,r2           ;end?
     148:         bhis    scanxf          ;  yes, exit false
     149:         inc     r0
     150:         cmp     (r4),(r1)       ;no, match on first words?
     151:         bne     2$              ;  yes
     152:         cmp     2(r4),2(r1)     ;no, how about second?
     153:         beq     scanx           ;  yes
     154: 2$:     add     r3,r1           ;increment by size
     155:         br      1$
     156:
     157:         .enabl  lsb
     158: scanxf: clr     r0              ;false exit
     159: scanx:  mov     r1,rolpnt       ;set entry pointer
     160:         mov     r0,rolupd       ;save flag
     161:         beq     1$              ;branch if not found
     162: scany:  mov     r4,r2           ;pointer to "symbol"
     163:         neg     r3              ;negate entry size
     164:         jmp     xmit0(r3)       ;found, xfer arguments
     165:
     166: 1$:     cmp     (r4)+,(r4)+     ;bypass symbol itself
     167:         asr     r3              ;get word count
     168:         sub     #2,r3           ;compensate for above cmp
     169:         ble     3$              ;branch if end
     170: 2$:     clr     (r4)+           ;clear word
     171:         sob     r3,2$
     172: 3$:     return
     173:         .dsabl  lsb
     174: append:                         ;append to end of roll
     175:         call    setrol
     176:         mov     r2,rolpnt       ;set pointer
     177:         clr     rolupd
     178:         br      inserf
     179:
     180: insert:                         ;insert in roll
     181:         call    setrof          ;set roll registers (but no arg)
     182: inserf: mov     rolpnt,r0       ;points to proper slot
     183:         tst     rolupd          ;was search true?
     184:         bne     5$              ;  yes
     185:         incb    <^pl rolsiz>+1(r5)      ;update entry count
     186:         add     r3,<^pl roltop>(r5)     ;update top pointer
     187:         cmp     r2,<^pl rolbas>+2(r5)   ;gap between rolls?
     188:         bne     5$              ;  yes, just stuff it
     189:         mov     <^pl rolbas>,r1 ;ditto for separate stack
     190:         mov     r1,r2
     191:         sub     r3,r2
     192:         mov     r2,symbot
     193:         ;cmp	r2,mactop	;room?
     194:         ;bhi	1$		;  yes
     195:         ;jmp	symovf		;no, error
     196:         mov     #symovf,upbomb  ; where to go on error
     197:         call    uplift
     198:         add     upgap,r0
     199:         add     upgap,r1
     200:         add     upgap,r2
     201:
     202:         ; fall through...
     203: 1$:     sub     r1,r0           ;compute byte count
     204:         asr     r0              ;  now word count
     205:         beq     4$              ;branch if first time
     206:
     207: 2$:     mov     (r1)+,(r2)+     ;move an entry down
     208:         sob     r0,2$
     209: 4$:     sub     r3,<^pl rolbas>(r5)     ;decrement pointers
     210:         sub     r3,<^pl roltop>(r5)
     211:         sub     #2,r5           ;more rolls?
     212:         bge     4$              ;  yes
     213:         mov     r2,r0           ;point to insertion slot
     214: 5$:     asr     r3              ;halve size count
     215: 6$:     mov     (r4)+,(r0)+     ;move an entry into place
     216:         sob     r3,6$           ;loop if not end
     217:         mov     <^pl rolbas>,symbot
     218:         mov     <^pl rolbas>,symlp
     219:         return
     220:
     221:
     222: .globl  $brkad, $brksy          ; defined in exec.m11
     223:
     224: .globl  putn
     225: uplift::                        ;<<< REEDS. move all the rolls up in core
     226:                                 ; can be called from 'insert' above and also
     227:                                 ; from 'getblk' in mac.m11.  Thanks to Steve
     228:                                 ; Ragle for showing the need for a call from
     229:                                 ; otherwise growing macros can scribble.
     230:                                 ; And to Joel Rubin for debugging help.
     231:         .irpc   xx,<0123>
     232:         mov     r'xx,-(sp)
     233:         .endm
     234:         cmp     symbot,mactop
     235:         blos    10$
     236:         clr     upgap
     237:         jmp     99$
     238: 10$:                            ; go here if symbot <= mactop
     239:
     240:         mov     symhp,upgap     ; stash old highest in-space address
     241:         add     #10102,symhp
     242:         bic     #77,symhp       ; click bic rounds to next highest mult of 64
     243:
     244:         mov     symhp,$brkad
     245:         mov     $brkad,-(sp)
     246:         tst     -(sp)
     247:         $sbrk
     248:         bcs     98$
     249:         cmp     (sp)+,(sp)+
     250:         br      1$
     251: 98$:
     252:         cmp     (sp)+,(sp)+
     253:         jmp     @upbomb         ; error bail-out: symovf or macovf
     254: 1$:
     255:         sub     #2,symhp        ; new highest in-space address
     256:         mov     symhp,r0
     257:         mov     upgap,r1        ; recall old highest address
     258:         mov     r0,r3
     259:         sub     r1,r3           ; r3 has the distance syms were shifted
     260:         mov     symlp,r2        ; symlp is OLD bottom of symbols.
     261:         tst     -(r2)           ; r2 ==> word before old bottom
     262: 2$:
     263:         mov     (r1),(r0)
     264:         tst     -(r1)
     265:         tst     -(r0)
     266:         cmp     r1,r2
     267:         bne     2$
     268:
     269: 9$:     mov     r3,upgap        ; how much the syms were lifted
     270:         mov     #dumrol,r0      ; swiped from srchi
     271: 3$:     add     r3,<^pl rolbas>(r0)
     272:         add     r3,<^pl roltop>(r0)
     273:         sub     #2,r0
     274:         bge     3$
     275:
     276:         add     r3,rolpnt
     277:         add     r3,symlp
     278:         mov     symlp,symbot
     279:         tst     rolupd
     280:         beq     30$
     281:         add     r3,rolupd
     282: 30$:
     283: 99$:
     284:         .irpc   xx,<3210>
     285:         mov     (sp)+,r'xx
     286:         .endm
     287:         return
     288:
     289:         entsect mixed
     290: upgap:          .blkw
     291: upbomb::        .blkw                   ; contains address of error handler
     292:         xitsec
     293: zap:                            ;empty a roll
     294:         call    setrol
     295:         mov     r1,<^pl roltop>(r5)     ;make top = bottom
     296:         clrb    <^pl rolsiz>+1(r5)      ;clear entry count
     297:         return
     298:
     299:
     300: setrol:                         ;set roll registers
     301:         mov     r0,rolndx       ;set argument
     302: setrof: mov     (sp)+,r0        ;save return address
     303:         call    savreg          ;save registers
     304:         mov     r5,-(sp)        ;  and current character
     305:         mov     rolndx,r5       ;set index
     306:         mov     <^pl rolbas>(r5),r1     ;current base
     307:         mov     <^pl roltop>(r5),r2     ;current top
     308:         movb    <^pl rolsiz>(r5),r3     ;entry size
     309:         mov     #symbol,r4      ;pointer to symbol
     310:         call    (r0)            ;call proper routine
     311:         mov     (sp)+,r5        ;restore current character
     312:         return                  ;  and rest of regs
     313:
     314:         entsec  mixed
     315: rolndx: .blkw                   ;roll index
     316: rolpnt: .blkw                   ;roll pointer
     317: rolupd: .blkw                   ;roll update
     318: mactop: .blkw                   ;current top of macro storage
     319: symbot: .blkw                   ;current bottom of dynamic rolls.
     320:                                 ;	@mactop<=@symbot  or uplift will fix it
     321:         xitsec
     322:
     323:         .end

Last modified: 1987-02-27 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 729 |