[PATCH]: Add lower_bound to vec.h

Daniel Berlin dberlin@dberlin.org
Thu Aug 19 12:37:00 GMT 2004


On Aug 19, 2004, at 4:14 AM, Nathan Sidwell wrote:

> 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 could do this if you really like, but i'm not sure it's necessary, 
see below.

> 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)
I'm not sure this is isn't just a premature concern.
Looking at the generated assembly and object files on powerpc, it's 
only 1.5x the size of the other vector functions.
Thus, I'd rather take care of this particular problem when it actually 
becomes a problem :)
However, if you really have strong feelings about this, i'm happy to do 
the above.



More information about the Gcc-patches mailing list