Leaving aside hashing and suchlike, we've used this for a while in multiple
places.
It's a ripoff of the C binsrch algorithm in the Tenenbaum data structures book,
so there's nothing ~that~ proprietary about it.
I edited it to take out our specific stuff, so check carefully as I may have
missed a variable.
I'm sure it's easy to rip apart from an elegance standpoint, but it does what
it says on the tin well enough.
I removed all our site specific macros, so you should be able to adapt it
easily enough.
***********************************************************************
* BINARY SEARCH FOR REQUESTED TABLE ENTRY *
* NTRY: R1: KEY TO FIND *
* EXIT: FULL: A(RECORD) - CC:EQ *
* FULL: A(INSERTION POINT) - CC:NEQ *
***********************************************************************
SPACE 1
BSRCH <use your favorite register preserving macro>
LR R4,R1 R4 = A(KEYARG)
L R5,=A(YOUR TABLE) R5 = A(START OF DATA)
L R0,=A(length of table) R0 = LENGTH OF DATA IN
BUFFER
SRDL R0,32
*
LHI RF,l'single entry RF = LENGTH OF SINGLE ENTRY
DR R0,RF
CHI R1,6
BL SQSRCH LESS THAN 6 - DO SEQUENTIAL SEARCH
*
XR R0,R0 R0 = LOW
BCTR R1,0 R1 = HIGH
LHI RE,l'key-1 RE = L'KEY-1
*
BSRCH02 CR R0,R1 WHILE LOW <= HIGH
BH BSRCH04 R0 POINTS TO INSERTION POINT
*
LR R3,R0 R3 = MID
AR R3,R1
SRL R3,1 MID=(HIGH+LOW)/2
*
LR RF,R3
MH RF,ISKEYLN4
AR RF,R5 RF=A(TEST ENTRY)
*
EX RE,BSMTCH TRY TO MATCH KEY
BE BSXIT KEY == K(MID)
*
BL *+12
LA R0,1(R3) IF CC HIGH : LOW = MID+1
B BSRCH02
*
LR R1,R3 IF CC LOW : HIGH = MID-1;
BCTR R1,0
B BSRCH02
*
BSRCH04 LR RF,R0
MH RF,ISKEYLN4
AR RF,R5
B BSXIT
*
SQSRCH L RF,=A(YOUR TABLE)
L R1,=A(YOUR TABLE)
A R1,=a(l'table)
AHI R1,l'entry R1 = A(LAST ENTRY)
*
LHI R0,l'entry R0 = L'ENTRY
LHI RE,l'key-1 RE = L'KEY-1
*
SSRCH02 EX RE,BSMTCH TRY TO MATCH KEY
BNH BSXIT
BXLE RF,R0,SSRCH02
DC H'0'
*
BSMTCH CLC 0(0,R4),0(RF) COMPARE REQUESTED KEY WITH RECORD
*
BSXIT ST RF,FULL
<restore your registers>
-----Original Message-----
From: IBM Mainframe Assembler List [mailto:ASSEMBLER-LIST@LISTSERV.UGA.EDU] On
Behalf Of Rob van der Heij
Sent: Monday, October 21, 2013 7:50 AM
To: ASSEMBLER-LIST@LISTSERV.UGA.EDU
Subject: Re: Linear search vs binary
If you want to make it 4096 entries, you could step through the table with
binary search very cheap by shifting a mask on each pass. I would already think
about it with 35 entries... ;-)
On 21 October 2013 13:32, Dougie Lawson <dl1...@gmail.com> wrote:
> If I have a table of 3,500 entries of twelve bytes (I'm doing a
> compare of eight bytes to find the entry I'm looking for and a check
> on a half word marker for the end of the table to avoid running off
> the end) then is it worth the pain of re-writing it as a binary search.
>
> If it is worth the pain and does anyone have a sample binary search
> tucked away.
>
> The table is built into a CSECT at the bottom of my code. I can
> restructure it if we need any special pointers to make a binary search work.
>
> Dougie
>
