From 5815280853df205cee38d4d9226856e1dba00685 Mon Sep 17 00:00:00 2001 From: Daniel Berlin Date: Thu, 19 Aug 2004 19:24:58 +0000 Subject: [PATCH] vec.h (VEC_lower_bound): New macro. 2004-08-19 Daniel Berlin * vec.h (VEC_lower_bound): New macro. From-SVN: r86262 --- gcc/ChangeLog | 4 +++ gcc/vec.h | 71 ++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 72 insertions(+), 3 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cf8fd9253dd..770d2c0cf02 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,7 @@ +2004-08-19 Daniel Berlin + + * vec.h (VEC_lower_bound): New macro. + 2004-08-19 Richard Sandiford PR target/16446 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_; \ \ -- 2.30.2