[PATCH]: Add lower_bound to vec.h
Thu Aug 19 08:36:00 GMT 2004
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
#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 Sidwell :: http://www.codesourcery.com :: CodeSourcery LLC
email@example.com :: http://www.planetfall.pwp.blueyonder.co.uk
More information about the Gcc-patches