On Wed, Apr 20, 2016 at 8:22 AM, <tbsaunde+...@tbsaunde.org> wrote:
> From: Trevor Saunders <tbsaunde+...@tbsaunde.org>
>
> Later patches use these functions, and I believe Mikhail has mentioned before
> he'd like to have begin / end () on vec before.
begin() / end () is fine. But contains ()? That makes using a O(n) algorithm
too easy I think (we have qsort + bsearch for a more efficient way).
I suppose you are replacing linear list walks with contains () so it
might be ok...
At least stick some comment on contains () mentioning qsort / bsearch.
Ok with that change.
Richard.
> gcc/ChangeLog:
>
> 2016-04-19 Trevor Saunders <tbsaunde+...@tbsaunde.org>
>
> * vec.h (vec_safe_contains): New function.
> (vec::contains): Likewise.
> (vec::begin): Likewise.
> (vec::end): Likewise.
> ---
> gcc/vec.h | 39 ++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 38 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/vec.h b/gcc/vec.h
> index ff57528..3c16e83 100644
> --- a/gcc/vec.h
> +++ b/gcc/vec.h
> @@ -454,6 +454,10 @@ public:
> bool is_empty (void) const { return m_vecpfx.m_num == 0; }
> T *address (void) { return m_vecdata; }
> const T *address (void) const { return m_vecdata; }
> + T *begin () { return address (); }
> + const T *begin () const { return address (); }
> + T *end () { return address () + length (); }
> + const T *end () const { return address () + length (); }
> const T &operator[] (unsigned) const;
> T &operator[] (unsigned);
> T &last (void);
> @@ -473,6 +477,7 @@ public:
> void qsort (int (*) (const void *, const void *));
> T *bsearch (const void *key, int (*compar)(const void *, const void *));
> unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
> + bool contains (const T &search) const;
> static size_t embedded_size (unsigned);
> void embedded_init (unsigned, unsigned = 0, unsigned = 0);
> void quick_grow (unsigned len);
> @@ -542,7 +547,6 @@ vec_safe_is_empty (vec<T, A, vl_embed> *v)
> return v ? v->is_empty () : true;
> }
>
> -
> /* If V does not have space for NELEMS elements, call
> V->reserve(NELEMS, EXACT). */
> template<typename T, typename A>
> @@ -695,6 +699,12 @@ vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T,
> A, vl_embed> *src
> }
> }
>
> +template<typename T, typename A>
> +inline bool
> +vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
> +{
> + return v? v->contains (search) : false;
> +}
>
> /* Index into vector. Return the IX'th element. IX must be in the
> domain of the vector. */
> @@ -973,6 +983,19 @@ vec<T, A, vl_embed>::bsearch (const void *key,
> return NULL;
> }
>
> +/* Return true if the vector contains search. */
> +
> +template<typename T, typename A>
> +inline bool
> +vec<T, A, vl_embed>::contains (const T &search) const
> +{
> + unsigned int len = length ();
> + for (unsigned int i = 0; i < len; i++)
> + if ((*this)[i] == search)
> + return true;
> +
> + return false;
> +}
>
> /* Find and return the first position in which OBJ could be inserted
> without changing the ordering of this vector. LESSTHAN is a
> @@ -1167,6 +1190,10 @@ public:
> const T *address (void) const
> { return m_vec ? m_vec->m_vecdata : NULL; }
>
> + T *begin () { return address (); }
> + const T *begin () const { return address (); }
> + T *end () { return begin () + length (); }
> + const T *end () const { return begin () + length (); }
> const T &operator[] (unsigned ix) const
> { return (*m_vec)[ix]; }
>
> @@ -1208,6 +1235,7 @@ public:
> void qsort (int (*) (const void *, const void *));
> T *bsearch (const void *key, int (*compar)(const void *, const void *));
> unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
> + bool contains (const T &search) const;
>
> bool using_auto_storage () const;
>
> @@ -1695,6 +1723,15 @@ vec<T, va_heap, vl_ptr>::lower_bound (T obj,
> return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
> }
>
> +/* Return true if the vector contains search. */
> +
> +template<typename T>
> +inline bool
> +vec<T, va_heap, vl_ptr>::contains (const T &search) const
> +{
> + return m_vec ? m_vec->contains (search) : false;
> +}
> +
> template<typename T>
> inline bool
> vec<T, va_heap, vl_ptr>::using_auto_storage () const
> --
> 2.7.4
>
