home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Professional / OS2PRO194.ISO / os2 / prgramer / asm / bsearch.asm < prev    next >
Encoding:
Assembly Source File  |  1988-12-01  |  5.1 KB  |  141 lines
  1.         title   BSEARCH binary search engine
  2.         page    55,132
  3.         .286
  4.  
  5. ; BSEARCH.ASM --- General purpose binary search routine (OS/2 version)
  6. ; by Ray Duncan, Copyright 1988 Ziff Davis Communications
  7. ;
  8. ; Call with:    BX    = file handle
  9. ;               CX    = record length
  10. ;               DS:DX = record buffer address
  11. ;               SI    = first (left) record number
  12. ;               DI    = last (right) record number
  13. ;               ES:BP = key structure address
  14. ;
  15. ;               where the key structure is:
  16. ;               dw    n          length of key
  17. ;               dw    m          offset of key in record
  18. ;               db    n dup (?)  key value
  19. ;
  20. ; Returns:      if record found
  21. ;               Zero flag = set
  22. ;               AX    = record number
  23. ;
  24. ;               if record not found
  25. ;               Zero flag = clear
  26. ;               AX    = undefined
  27. ;
  28. ;               All other registers preserved
  29.  
  30.         extrn   DosChgFilePtr:far       ; references to OS/2 API
  31.         extrn   DosRead:far
  32.  
  33. _TEXT   segment word public 'CODE'
  34.  
  35.         extrn   strcmp:near
  36.  
  37.         assume  cs:_TEXT
  38.  
  39. rlen    equ     word ptr [bp-6]         ; receives DosRead length
  40. fptr    equ     word ptr [bp-4]
  41. kbuff   equ     dword ptr [bp]          ; key address
  42. right   equ     word ptr [bp+4]         ; last record number
  43. left    equ     word ptr [bp+6]         ; first record number
  44. fbuff   equ     dword ptr [bp+8]        ; file buffer address
  45. flen    equ     word ptr [bp+12]        ; file record size
  46. fhandle equ     word ptr [bp+14]        ; file handle
  47.  
  48.         public  bsearch 
  49. bsearch proc    near
  50.  
  51.         cmp     si,di                   ; first > last record?
  52.         jng     bsch1                   ; no, jump
  53.         ret                             ; record absent, end search
  54.  
  55. bsch1:  push    bx                      ; save registers
  56.         push    cx
  57.         push    ds
  58.         push    dx
  59.         push    si
  60.         push    di
  61.         push    es
  62.         push    bp
  63.         mov     bp,sp                   ; point to stack frame
  64.         sub     sp,6                    ; allocate local variables
  65.  
  66.         mov     ax,si                   ; calculate record number
  67.         add     ax,di                   ; at middle of file segment             
  68.         shr     ax,1                    ; (left + right) / 2
  69.         push    ax                      ; save record number
  70.         mul     cx                      ; DX:AX := file offset
  71.  
  72.                                         ; set file pointer...
  73.         push    bx                      ; file handle
  74.         push    dx                      ; file offset
  75.         push    ax
  76.         push    0                       ; method = rel. to start of file
  77.         push    ss                      ; receives absolute file ptr
  78.         lea     ax,fptr
  79.         push    ax
  80.         call    DosChgFilePtr           ; transfer to OS/2
  81.  
  82.                                         ; now read record...
  83.         push    bx                      ; file handle
  84.         lds     dx,fbuff                ; address of record buffer
  85.         push    ds
  86.         push    dx
  87.         push    flen                    ; length of record
  88.         push    ss                      ; receives actual bytes read
  89.         lea     ax,rlen
  90.         push    ax
  91.         call    DosRead                 ; transfer to OS/2
  92.  
  93.         les     di,kbuff                ; ES:DI = key structure
  94.         mov     si,dx                   ; DS:SI = record buffer
  95.         add     si,es:[di+2]            ; DS:SI = key within record
  96.         mov     bx,es:[di]              ; BX = length of key
  97.         mov     dx,bx                   ; DS = length of key
  98.         add     di,4                    ; ES:DI = address of key
  99.         call    strcmp                  ; now compare keys
  100.  
  101.         pop     ax                      ; recover record number
  102.         jz      bsch4                   ; match found, exit
  103.  
  104.         push    bp                      ; save stack frame pointer
  105.         mov     bx,fhandle              ; set up to bisect file and
  106.         mov     cx,flen                 ; perform recursive search
  107.         mov     si,left
  108.         mov     di,right
  109.         lds     dx,fbuff
  110.         les     bp,kbuff
  111.         jl      bsch2                   ; branch on key comparison
  112.  
  113.         mov     di,ax                   ; record < search key
  114.         dec     di                      ; set right = current - 1
  115.         jmp     bsch3
  116.  
  117. bsch2:  mov     si,ax                   ; record > search key
  118.         inc     si                      ; set left = current + 1
  119.  
  120. bsch3:  call    bsearch                 ; inspect next middle record
  121.         pop     bp                      ; restore stack frame pointer
  122.  
  123. bsch4:  mov     sp,bp                   ; discard local variables
  124.         pop     bp                      ; restore registers     
  125.         pop     es                      ; leaving Z flag undisturbed
  126.         pop     di
  127.         pop     si
  128.         pop     dx
  129.         pop     ds
  130.         pop     cx
  131.         pop     bx
  132.  
  133.         ret                             ; and return to caller
  134.  
  135. bsearch endp
  136.  
  137. _TEXT   ends
  138.  
  139.         end
  140.  
  141.