2004-08-19 Daniel Berlin <dberlin@dberlin.org>

	* vec.h (VEC_lower_bound): New macro.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@86262 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 68 insertions, 3 deletions

diff --git a/gcc/vec.h b/gcc/vec.h
index 35d260335b0..a3eea311320 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -75,6 +75,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
    element ordering 'ordered_remove', and one which does not
    'unordered_remove'.  The latter function copies the end element
    into the removed slot, rather than invoke a memmove operation.
+   The 'lower_bound' function will determine where to place an item in the
+   array using insert that will maintain sorted order.
 
    If you need to directly manipulate a vector, then the 'address'
    accessor will return the address of the start of the vector.  Also
@@ -300,6 +302,19 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 
 #define VEC_address(TDEF,V)		(VEC_OP(TDEF,address)(V))
 
+/* Find the first index in the vector not less than the object.
+   unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 
+                               bool (*lessthan) (const T, const T)); // Pointer
+   unsigned VEC_T_lower_bound (VEC(T) *v, const T *val,
+                               bool (*lessthan) (const T*, const T*)); // Object
+   
+   Find the first position in which VAL could be inserted without
+   changing the ordering of V.  LESSTHAN is a function that returns
+   true if the first argument is strictly less than the second.   */
+   
+#define VEC_lower_bound(TDEF,V,O,LT)    \
+       (VEC_OP(TDEF,lower_bound)(V,O,LT VEC_CHECK_INFO))
+
 #if !IN_GENGTYPE
 /* Reallocate an array of elements with prefix.  */
 extern void *vec_p_reserve (void *, int MEM_STAT_DECL);
@@ -475,7 +490,32 @@ static inline TDEF VEC_OP (TDEF,replace)		  	     	  \
   return old_obj_;							  \
 }									  \
 									  \
-static inline TDEF *VEC_OP (TDEF,quick_insert)		     	  	  \
+static inline unsigned VEC_OP (TDEF,lower_bound)			\
+     (VEC (TDEF) *vec_, const TDEF obj_, bool (*lessthan_)(const TDEF, const TDEF) VEC_CHECK_DECL) \
+{									\
+   unsigned int len_ = VEC_OP (TDEF, length) (vec_);			\
+   unsigned int half_, middle_;						\
+   unsigned int first_ = 0;						\
+   while (len_ > 0)							\
+     {									\
+        TDEF middle_elem_;						\
+        half_ = len_ >> 1;						\
+        middle_ = first_;						\
+        middle_ += half_;						\
+        middle_elem_ = VEC_OP (TDEF, index) (vec_, middle_ VEC_CHECK_PASS); \
+        if (lessthan_ (middle_elem_, obj_))				\
+          {								\
+             first_ = middle_;						\
+             ++first_;							\
+             len_ = len_ - half_ - 1;					\
+          }								\
+        else								\
+          len_ = half_;							\
+     }									\
+   return first_;							\
+}									\
+									\
+static inline TDEF *VEC_OP (TDEF,quick_insert)				\
      (VEC (TDEF) *vec_, unsigned ix_, TDEF obj_ VEC_CHECK_DECL)		  \
 {									  \
   TDEF *slot_;								  \
@@ -670,8 +710,33 @@ static inline TDEF *VEC_OP (TDEF,replace)				  \
   return slot_;								  \
 }									  \
 									  \
-static inline TDEF *VEC_OP (TDEF,quick_insert)				  \
-     (VEC (TDEF) *vec_, unsigned ix_, const TDEF *obj_ VEC_CHECK_DECL)	  \
+static inline unsigned VEC_OP (TDEF,lower_bound)			\
+     (VEC (TDEF) *vec_, const TDEF *obj_, bool (*lessthan_)(const TDEF *, const TDEF *) VEC_CHECK_DECL) \
+{									\
+   unsigned int len_ = VEC_OP (TDEF, length) (vec_);			\
+   unsigned int half_, middle_;						\
+   unsigned int first_ = 0;						\
+   while (len_ > 0)							\
+     {									\
+        TDEF *middle_elem_;						\
+        half_ = len_ >> 1;						\
+        middle_ = first_;						\
+        middle_ += half_;						\
+        middle_elem_ = VEC_OP (TDEF, index) (vec_, middle_ VEC_CHECK_PASS); \
+        if (lessthan_ (middle_elem_, obj_))				\
+          {								\
+             first_ = middle_;						\
+             ++first_;							\
+             len_ = len_ - half_ - 1;					\
+          }								\
+        else								\
+          len_ = half_;							\
+     }									\
+   return first_;							\
+}									\
+									\
+static inline TDEF *VEC_OP (TDEF,quick_insert)				\
+     (VEC (TDEF) *vec_, unsigned ix_, const TDEF *obj_ VEC_CHECK_DECL)	\
 {									  \
   TDEF *slot_;								  \
 									  \