🚀 go-pugleaf

[clong@topaz.rutgers.edu (Chris Long) writes...]
> 
> I find myself needing a really hot 68000 binary search routine.  This
> routine will be called millions of times, so it should be as efficient
> as possible.  I need it to go through about 10,000 items, each with a
> size of ~ 10 bytes.  Does anyone have something like this already coded?

Direct from the dLibs library source archive... here is bsearch()...

-----------------------------------8<-----------------------------------
#include <stdio.h>

int	_bsearch;	/* index of element found, or where to insert */

char *bsearch(key, base, num, size, cmp)
	register char *key;		/* item to search for */
	register char *base;		/* base address */
	int num;			/* number of elements */
	register int size;		/* element size in bytes */
	register int (*cmp)();		/* comparison function */
	{
	register int a, b, c, dir;

	a = 0;
	b = num - 1;
	while(a <= b)
		{
		c = (a + b) >> 1;	/* == ((a + b) / 2) */
		if (dir = (*cmp)((base + (c * size)), key))
			{
			if (dir > 0)
				b = c - 1;
			else /* (dir < 0) */
				a = c + 1;
			}
		else
			{
			_bsearch = c;
			return(base + (c * size));
			}
		}
	_bsearch = b;	
	return(NULL);
	}
-----------------------------------8<-----------------------------------

You will probably want to hard code the comparison function, since I
assume this is a special purpose "as fast as possible" application of
the more general function.  Also, obviously, conversion to hand-optimized
68000 assembly is left as an exercise to the reader.

> The most helpful response gets a postcard with an incredibly ugly 
> picture of Hill Center, the mathematical and computer sciences
> building here.

Actually, I'd prefer if you just sent me back your optimized assembly
code conversion.  That way I can re-generalize it (to take a compare
function pointer) and include it in the next dLibs release.

> Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ  08901  (201) 846-5569
> 
> "The proofs are so obvious that they can be left to the reader."
> Lars V. Ahlfors, _Complex Analysis_

I hope this is want you needed.

\\   /  Dale Schumacher                         399 Beacon Ave.
 \\ /   (alias: Dalnefre')                      St. Paul, MN  55104-3527
  ><    ...umn-cs!midgard.mn.org!syntel!dal     United States of America
 / \\   "What is wanted is not the will to believe, but the will to find out,
/   \\  which is the exact opposite." -Bertrand Russell