Re: [PATCH]: Add lower_bound to vec.h

[Nathan Sidwell <nathan at codesourcery dot com>]

Daniel Berlin wrote:
> This adds a lower_bound function to vec.h (the C analogue of 
> std::lower_bound), so that you can keep ordered vectors in ordered (and 
> later, so you can do binary searches to find items).
> I have significant use for ordered vectors in the new points-to code.
>
> This is a direct translation of the version of lower_bound used in 
> libstdc++ (specialized for our vector case).

This is a case where C++ templates would DTRT. Because of the comparison
function pointer being passed (which presumbaly is another inline fn), we want
to make lower_bound inline too, so the indirect call can be flattened.  It
might well be better to not have lower_bound itself be inlined into its caller
though. In C++ you'd make the comparison function a non-type template
parameter, and declare something like
	template <bool (*comp)(T, T), typename T>
	  int lower_bound (VEC<T> &v, T elem);

Have you considered defining a separate DEF_VEC_LOWER_BOUND macro, of the
form
	#define DEF_VEC_LOWER_BOUND_P(T, COMP)  <BODY_OF_LOWER_BOUND>
and using it like
	static inline DEF_VEC_LOWER_BOUND_P(edge_t, edge_order_fn);
thus allowing the user to control linkage and placement of the function body?
(I think you'll need separate _P and _O versions).

I'm concerned that forcing lower_bound to be inline will lead to code bloat
(either by inlining it, or by outlining it in every object file that needs it)

nathan

--
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk