X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fhb-vector.hh;h=13cfe56b59f98cfbd50e9303a9b81a9121743788;hb=f0a0bdf96095ae4b3524be4ee4bc32ebe2dfd564;hp=6c7d32e49d87a2e179843a85ae81910d06495177;hpb=8b9bac85deb2ace750acafa5e0da676f633aadeb;p=platform%2Fupstream%2Fharfbuzz.git

diff --git a/src/hb-vector.hh b/src/hb-vector.hh
index 6c7d32e..13cfe56 100644
--- a/src/hb-vector.hh
+++ b/src/hb-vector.hh
@@ -29,12 +29,13 @@
 
 #include "hb.hh"
 #include "hb-array.hh"
+#include "hb-meta.hh"
 #include "hb-null.hh"
 
 
 template <typename Type,
 	  bool sorted=false>
-struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty_t>::type
+struct hb_vector_t
 {
   typedef Type item_t;
   static constexpr unsigned item_size = hb_static_size (Type);
@@ -44,7 +45,7 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   hb_vector_t () = default;
   hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
   {
-    alloc (lst.size ());
+    alloc (lst.size (), true);
     for (auto&& item : lst)
       push (item);
   }
@@ -52,14 +53,28 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
 	    hb_requires (hb_is_iterable (Iterable))>
   hb_vector_t (const Iterable &o) : hb_vector_t ()
   {
-    if (hb_iter (o).is_random_access_iterator)
-      alloc (hb_len (hb_iter (o)));
-    hb_copy (o, *this);
+    auto iter = hb_iter (o);
+    if (iter.is_random_access_iterator || iter.has_fast_len)
+      alloc (hb_len (iter), true);
+    hb_copy (iter, *this);
   }
   hb_vector_t (const hb_vector_t &o) : hb_vector_t ()
   {
-    alloc (o.length);
-    hb_copy (o, *this);
+    alloc (o.length, true);
+    if (unlikely (in_error ())) return;
+    copy_array (o.as_array ());
+  }
+  hb_vector_t (array_t o) : hb_vector_t ()
+  {
+    alloc (o.length, true);
+    if (unlikely (in_error ())) return;
+    copy_array (o);
+  }
+  hb_vector_t (c_array_t o) : hb_vector_t ()
+  {
+    alloc (o.length, true);
+    if (unlikely (in_error ())) return;
+    copy_array (o);
   }
   hb_vector_t (hb_vector_t &&o)
   {
@@ -70,9 +85,8 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   }
   ~hb_vector_t () { fini (); }
 
-  private:
-  int allocated = 0; /* == -1 means allocation failed. */
   public:
+  int allocated = 0; /* < 0 means allocation failed. */
   unsigned int length = 0;
   public:
   Type *arrayZ = nullptr;
@@ -82,18 +96,27 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
     allocated = length = 0;
     arrayZ = nullptr;
   }
+  void init0 ()
+  {
+  }
 
   void fini ()
   {
-    shrink_vector (0);
-    hb_free (arrayZ);
+    /* We allow a hack to make the vector point to a foreign array
+     * by the user. In that case length/arrayZ are non-zero but
+     * allocated is zero. Don't free anything. */
+    if (allocated)
+    {
+      shrink_vector (0);
+      hb_free (arrayZ);
+    }
     init ();
   }
 
   void reset ()
   {
     if (unlikely (in_error ()))
-      allocated = length; // Big hack!
+      reset_error ();
     resize (0);
   }
 
@@ -107,8 +130,11 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   hb_vector_t& operator = (const hb_vector_t &o)
   {
     reset ();
-    alloc (o.length);
-    hb_copy (o, *this);
+    alloc (o.length, true);
+    if (unlikely (in_error ())) return *this;
+
+    copy_array (o.as_array ());
+
     return *this;
   }
   hb_vector_t& operator = (hb_vector_t &&o)
@@ -118,7 +144,7 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   }
 
   hb_bytes_t as_bytes () const
-  { return hb_bytes_t ((const char *) arrayZ, length * item_size); }
+  { return hb_bytes_t ((const char *) arrayZ, get_size ()); }
 
   bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
   bool operator != (const hb_vector_t &o) const { return !(*this == o); }
@@ -160,14 +186,10 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   operator   iter_t () const { return   iter (); }
   operator writer_t ()       { return writer (); }
 
-  c_array_t sub_array (unsigned int start_offset, unsigned int count) const
-  { return as_array ().sub_array (start_offset, count); }
-  c_array_t sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
-  { return as_array ().sub_array (start_offset, count); }
-  array_t sub_array (unsigned int start_offset, unsigned int count)
-  { return as_array ().sub_array (start_offset, count); }
-  array_t sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
-  { return as_array ().sub_array (start_offset, count); }
+  /* Faster range-based for loop. */
+  Type *begin () const { return arrayZ; }
+  Type *end () const { return arrayZ + length; }
+
 
   hb_sorted_array_t<Type> as_sorted_array ()
   { return hb_sorted_array (arrayZ, length); }
@@ -183,104 +205,168 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   Type *push ()
   {
     if (unlikely (!resize (length + 1)))
-      return &Crap (Type);
-    return &arrayZ[length - 1];
+      return std::addressof (Crap (Type));
+    return std::addressof (arrayZ[length - 1]);
   }
-  template <typename T>
-  Type *push (T&& v)
+  template <typename... Args> Type *push (Args&&... args)
   {
-    /* TODO Emplace? */
-    Type *p = push ();
-    if (p == &Crap (Type))
+    if (unlikely ((int) length >= allocated && !alloc (length + 1)))
       // If push failed to allocate then don't copy v, since this may cause
       // the created copy to leak memory since we won't have stored a
       // reference to it.
-      return p;
-    *p = std::forward<T> (v);
-    return p;
+      return std::addressof (Crap (Type));
+
+    /* Emplace. */
+    Type *p = std::addressof (arrayZ[length++]);
+    return new (p) Type (std::forward<Args> (args)...);
   }
 
   bool in_error () const { return allocated < 0; }
+  void set_error ()
+  {
+    assert (allocated >= 0);
+    allocated = -allocated - 1;
+  }
+  void reset_error ()
+  {
+    assert (allocated < 0);
+    allocated = -(allocated + 1);
+  }
 
   template <typename T = Type,
-	    hb_enable_if (std::is_trivially_copy_assignable<T>::value)>
+	    hb_enable_if (hb_is_trivially_copy_assignable(T))>
   Type *
-  realloc_vector (unsigned new_allocated)
+  realloc_vector (unsigned new_allocated, hb_priority<0>)
   {
+    if (!new_allocated)
+    {
+      hb_free (arrayZ);
+      return nullptr;
+    }
     return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
   }
   template <typename T = Type,
-	    hb_enable_if (!std::is_trivially_copy_assignable<T>::value)>
+	    hb_enable_if (!hb_is_trivially_copy_assignable(T))>
   Type *
-  realloc_vector (unsigned new_allocated)
+  realloc_vector (unsigned new_allocated, hb_priority<0>)
   {
+    if (!new_allocated)
+    {
+      hb_free (arrayZ);
+      return nullptr;
+    }
     Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type));
     if (likely (new_array))
     {
       for (unsigned i = 0; i < length; i++)
+      {
 	new (std::addressof (new_array[i])) Type ();
-      for (unsigned i = 0; i < (unsigned) length; i++)
 	new_array[i] = std::move (arrayZ[i]);
-      unsigned old_length = length;
-      shrink_vector (0);
-      length = old_length;
+	arrayZ[i].~Type ();
+      }
       hb_free (arrayZ);
     }
     return new_array;
   }
+  /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */
+  template <typename T = Type,
+	    hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
+			  hb_is_same (T, hb_array_t <typename T::item_t>))>
+  Type *
+  realloc_vector (unsigned new_allocated, hb_priority<1>)
+  {
+    if (!new_allocated)
+    {
+      hb_free (arrayZ);
+      return nullptr;
+    }
+    return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
+  }
 
   template <typename T = Type,
-	    hb_enable_if (std::is_trivially_constructible<T>::value ||
-			  !std::is_default_constructible<T>::value)>
+	    hb_enable_if (hb_is_trivially_constructible(T))>
   void
-  grow_vector (unsigned size)
+  grow_vector (unsigned size, hb_priority<0>)
   {
-    memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
+    hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
     length = size;
   }
   template <typename T = Type,
-	    hb_enable_if (!std::is_trivially_constructible<T>::value &&
-			   std::is_default_constructible<T>::value)>
+	    hb_enable_if (!hb_is_trivially_constructible(T))>
   void
-  grow_vector (unsigned size)
+  grow_vector (unsigned size, hb_priority<0>)
   {
-    while (length < size)
-    {
-      length++;
-      new (std::addressof (arrayZ[length - 1])) Type ();
-    }
+    for (; length < size; length++)
+      new (std::addressof (arrayZ[length])) Type ();
   }
-
+  /* Specialization for hb_vector_t<hb_{vector,array}_t<U>> to speed up. */
   template <typename T = Type,
-	    hb_enable_if (std::is_trivially_destructible<T>::value)>
+	    hb_enable_if (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
+			  hb_is_same (T, hb_array_t <typename T::item_t>))>
   void
-  shrink_vector (unsigned size)
+  grow_vector (unsigned size, hb_priority<1>)
   {
+    hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
     length = size;
   }
+
   template <typename T = Type,
-	    hb_enable_if (!std::is_trivially_destructible<T>::value)>
+	    hb_enable_if (hb_is_trivially_copyable (T))>
   void
-  shrink_vector (unsigned size)
+  copy_array (hb_array_t<const Type> other)
+  {
+    length = other.length;
+    if (!HB_OPTIMIZE_SIZE_VAL && sizeof (T) >= sizeof (long long))
+      /* This runs faster because of alignment. */
+      for (unsigned i = 0; i < length; i++)
+	arrayZ[i] = other.arrayZ[i];
+    else
+       hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size);
+  }
+  template <typename T = Type,
+	    hb_enable_if (!hb_is_trivially_copyable (T) &&
+			   std::is_copy_constructible<T>::value)>
+  void
+  copy_array (hb_array_t<const Type> other)
   {
-    while ((unsigned) length > size)
+    length = 0;
+    while (length < other.length)
     {
-      arrayZ[(unsigned) length - 1].~Type ();
-      length--;
+      length++;
+      new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]);
     }
   }
-
   template <typename T = Type,
-	    hb_enable_if (std::is_trivially_copy_assignable<T>::value)>
+	    hb_enable_if (!hb_is_trivially_copyable (T) &&
+			  !std::is_copy_constructible<T>::value &&
+			  std::is_default_constructible<T>::value &&
+			  std::is_copy_assignable<T>::value)>
   void
-  shift_down_vector (unsigned i)
+  copy_array (hb_array_t<const Type> other)
   {
-    memmove (static_cast<void *> (&arrayZ[i - 1]),
-	     static_cast<void *> (&arrayZ[i]),
-	     (length - i) * sizeof (Type));
+    length = 0;
+    while (length < other.length)
+    {
+      length++;
+      new (std::addressof (arrayZ[length - 1])) Type ();
+      arrayZ[length - 1] = other.arrayZ[length - 1];
+    }
   }
-  template <typename T = Type,
-	    hb_enable_if (!std::is_trivially_copy_assignable<T>::value)>
+
+  void
+  shrink_vector (unsigned size)
+  {
+    assert (size <= length);
+    if (!std::is_trivially_destructible<Type>::value)
+    {
+      unsigned count = length - size;
+      Type *p = arrayZ + length - 1;
+      while (count--)
+        p--->~Type ();
+    }
+    length = size;
+  }
+
   void
   shift_down_vector (unsigned i)
   {
@@ -289,31 +375,54 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
   }
 
   /* Allocate for size but don't adjust length. */
-  bool alloc (unsigned int size)
+  bool alloc (unsigned int size, bool exact=false)
   {
     if (unlikely (in_error ()))
       return false;
 
-    if (likely (size <= (unsigned) allocated))
-      return true;
+    unsigned int new_allocated;
+    if (exact)
+    {
+      /* If exact was specified, we allow shrinking the storage. */
+      size = hb_max (size, length);
+      if (size <= (unsigned) allocated &&
+	  size >= (unsigned) allocated >> 2)
+	return true;
 
-    /* Reallocate */
+      new_allocated = size;
+    }
+    else
+    {
+      if (likely (size <= (unsigned) allocated))
+	return true;
+
+      new_allocated = allocated;
+      while (size > new_allocated)
+	new_allocated += (new_allocated >> 1) + 8;
+    }
 
-    unsigned int new_allocated = allocated;
-    while (size >= new_allocated)
-      new_allocated += (new_allocated >> 1) + 8;
 
-    Type *new_array = nullptr;
+    /* Reallocate */
+
     bool overflows =
       (int) in_error () ||
-      (new_allocated < (unsigned) allocated) ||
+      (new_allocated < size) ||
       hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
-    if (likely (!overflows))
-      new_array = realloc_vector (new_allocated);
 
-    if (unlikely (!new_array))
+    if (unlikely (overflows))
+    {
+      set_error ();
+      return false;
+    }
+
+    Type *new_array = realloc_vector (new_allocated, hb_prioritize);
+
+    if (unlikely (new_allocated && !new_array))
     {
-      allocated = -1;
+      if (new_allocated <= (unsigned) allocated)
+        return true; // shrinking failed; it's okay; happens in our fuzzer
+
+      set_error ();
       return false;
     }
 
@@ -323,54 +432,77 @@ struct hb_vector_t : std::conditional<sorted, hb_vector_t<Type, false>, hb_empty
     return true;
   }
 
-  bool resize (int size_)
+  bool resize (int size_, bool initialize = true, bool exact = false)
   {
     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
-    if (!alloc (size))
+    if (!alloc (size, exact))
       return false;
 
     if (size > length)
-      grow_vector (size);
+    {
+      if (initialize)
+	grow_vector (size, hb_prioritize);
+    }
     else if (size < length)
-      shrink_vector (size);
+    {
+      if (initialize)
+	shrink_vector (size);
+    }
 
     length = size;
     return true;
   }
+  bool resize_exact (int size_, bool initialize = true)
+  {
+    return resize (size_, initialize, true);
+  }
 
   Type pop ()
   {
     if (!length) return Null (Type);
-    Type v = std::move (arrayZ[length - 1]);
+    Type v (std::move (arrayZ[length - 1]));
     arrayZ[length - 1].~Type ();
     length--;
     return v;
   }
 
-  void remove (unsigned int i)
+  void remove_ordered (unsigned int i)
   {
     if (unlikely (i >= length))
       return;
-    arrayZ[i].~Type ();
     shift_down_vector (i + 1);
+    arrayZ[length - 1].~Type ();
     length--;
   }
 
-  void shrink (int size_)
+  template <bool Sorted = sorted,
+	    hb_enable_if (!Sorted)>
+  void remove_unordered (unsigned int i)
+  {
+    if (unlikely (i >= length))
+      return;
+    if (i != length - 1)
+      arrayZ[i] = std::move (arrayZ[length - 1]);
+    arrayZ[length - 1].~Type ();
+    length--;
+  }
+
+  void shrink (int size_, bool shrink_memory = true)
   {
     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
     if (size >= length)
       return;
 
     shrink_vector (size);
+
+    if (shrink_memory)
+      alloc (size, true); /* To force shrinking memory if needed. */
   }
 
 
   /* Sorting API. */
-  void qsort (int (*cmp)(const void*, const void*))
+  void qsort (int (*cmp)(const void*, const void*) = Type::cmp)
   { as_array ().qsort (cmp); }
-  void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
-  { as_array ().qsort (start, end); }
 
   /* Unsorted search API. */
   template <typename T>