diff options
| author | Daniel Berlin <dberlin@dberlin.org> | 2004-08-19 19:24:58 +0000 |
|---|---|---|
| committer | Daniel Berlin <dberlin@gcc.gnu.org> | 2004-08-19 19:24:58 +0000 |
| commit | 5815280853df205cee38d4d9226856e1dba00685 (patch) | |
| tree | 5b47c7d93e50d2833953ebd3b70b833eb659c71e | |
| parent | d096936ca209de4adffbe8eb2f8b5a9f5af00be1 (diff) | |
| download | gcc-5815280853df205cee38d4d9226856e1dba00685.zip gcc-5815280853df205cee38d4d9226856e1dba00685.tar.gz gcc-5815280853df205cee38d4d9226856e1dba00685.tar.bz2 | |
vec.h (VEC_lower_bound): New macro.
2004-08-19 Daniel Berlin <dberlin@dberlin.org>
* vec.h (VEC_lower_bound): New macro.
From-SVN: r86262
| -rw-r--r-- | gcc/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/vec.h | 71 |
2 files changed, 72 insertions, 3 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cf8fd92..770d2c0 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,7 @@ +2004-08-19 Daniel Berlin <dberlin@dberlin.org> + + * vec.h (VEC_lower_bound): New macro. + 2004-08-19 Richard Sandiford <rsandifo@redhat.com> PR target/16446 @@ -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_; \ \ |