diff mbox

[11/18] add some utility methods to vec

Message ID 1461133342-10794-12-git-send-email-tbsaunde+gcc@tbsaunde.org
State New
Headers show

Commit Message

tbsaunde+gcc@tbsaunde.org April 20, 2016, 6:22 a.m. UTC 
From: Trevor Saunders <tbsaunde+gcc@tbsaunde.org>

Later patches use these functions, and I believe Mikhail has mentioned before
he'd like to have begin / end () on vec before.

gcc/ChangeLog:

2016-04-19  Trevor Saunders  <tbsaunde+gcc@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(-)

Comments

Richard Biener April 20, 2016, 9:13 a.m. UTC | #1 
On Wed, Apr 20, 2016 at 8:22 AM,  <tbsaunde+gcc@tbsaunde.org> wrote:
> From: Trevor Saunders <tbsaunde+gcc@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+gcc@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
>
Segher Boessenkool April 20, 2016, 12:29 p.m. UTC | #2 
On Wed, Apr 20, 2016 at 02:22:15AM -0400, tbsaunde+gcc@tbsaunde.org wrote:
> +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;
> +}

Missing space.


Segher
Trevor Saunders April 21, 2016, 4:26 a.m. UTC | #3 
On Wed, Apr 20, 2016 at 11:13:42AM +0200, Richard Biener wrote:
> On Wed, Apr 20, 2016 at 8:22 AM,  <tbsaunde+gcc@tbsaunde.org> wrote:
> > From: Trevor Saunders <tbsaunde+gcc@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).

 Well, contains is better if you will search less than log(n) times.

> I suppose you are replacing linear list walks with contains () so it
> might be ok...

yeah, and I'm not really sure how much open coding it will actually make
people think more than they would otherwise.

> At least stick some comment on contains () mentioning qsort / bsearch.

sure

Trev

> 
> Ok with that change.
> 
> Richard.
> 
> > gcc/ChangeLog:
> >
> > 2016-04-19  Trevor Saunders  <tbsaunde+gcc@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
> >
diff mbox

Patch

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