[m-dev.] for review: new debugger command set, part 2

Andrew Bromage bromage at cs.mu.OZ.AU
Thu Jul 9 09:47:52 AEST 1998


G'day all.

Fergus Henderson wrote:

> Anyway, you could use a single macro for all binary searches:
> 
> /*
> ** // In C++ terminology:
> ** template <class T>
> ** MR_bsearch(T array[], int num_elements, int compare(T, T), T key,
> **		int& element, bool& found):
> ** ... (insert documentation here) ...
> */
> #define MR_bsearch(array, num_elements, compare, key, element, found)	\
> 	do {								\
> 		int	lo;						\
> 		int	hi;						\
> 		int	mid;						\
> 		int	diff;						\
> 									\
> 		lo = 0;							\
> 		hi = (num_elements) - 1;				\
> 		(found) = FALSE;					\
> 		while (lo <= hi) {					\
> 			mid = (lo + hi) / 2;				\
> 			diff = compare((array)[mid], (key));		\
> 			if (diff == 0) {				\
> 				(found) = TRUE;				\
> 				break;					\
> 			} else if (diff < 0) {				\
> 				lo = mid + 1;				\
> 			} else {					\
> 				hi = mid - 1;				\
> 			}						\
> 		}							\
> 		(element) = mid;					\
> 	} while(0);
[etc]

s/;// on the last line there.

While I think of it, the case quoted (searching for modules) there
weren't duplicate elements in the array.  The previous messages are
out of my spool now.  Are any of the other binary searches likely to
be on an array with duplicate elements and if so, is it important
which one is found?

The above binary search doesn't take that possibility into account.

Just being ultra-pedantic. :-)

Cheers,
Andrew Bromage



More information about the developers mailing list