src/hb-vector.hh - third_party/harfbuzz - Git at Google

 /*
  * Copyright © 2017,2018  Google, Inc.
  *
  *  This is part of HarfBuzz, a text shaping library.
  *
  * Permission is hereby granted, without written agreement and without
  * license or royalty fees, to use, copy, modify, and distribute this
  * software and its documentation for any purpose, provided that the
  * above copyright notice and the following two paragraphs appear in
  * all copies of this software.
  *
  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  * DAMAGE.
  *
  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  *
  * Google Author(s): Behdad Esfahbod
  */

 #ifndef HB_VECTOR_HH
 #define HB_VECTOR_HH

 #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
 {
   typedef Type item_t;
   static constexpr unsigned item_size = hb_static_size (Type);
   using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type;
   using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type;

   hb_vector_t () = default;
   hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
   {
     alloc (lst.size (), true);
     for (auto&& item : lst)
       push (item);
   }
   template <typename Iterable,
 	    hb_requires (hb_is_iterable (Iterable))>
   hb_vector_t (const Iterable &o) : hb_vector_t ()
   {
     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, 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)
   {
     allocated = o.allocated;
     length = o.length;
     arrayZ = o.arrayZ;
     o.init ();
   }
   ~hb_vector_t () { fini (); }

   public:
   int allocated = 0; /* < 0 means allocation failed. */
   unsigned int length = 0;
   public:
   Type *arrayZ = nullptr;

   void init ()
   {
     allocated = length = 0;
     arrayZ = nullptr;
   }
   void init0 ()
   {
   }

   void fini ()
   {
     /* 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 ()))
       reset_error ();
     resize (0);
   }

   friend void swap (hb_vector_t& a, hb_vector_t& b)
   {
     hb_swap (a.allocated, b.allocated);
     hb_swap (a.length, b.length);
     hb_swap (a.arrayZ, b.arrayZ);
   }

   hb_vector_t& operator = (const hb_vector_t &o)
   {
     reset ();
     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)
   {
     hb_swap (*this, o);
     return *this;
   }

   hb_bytes_t as_bytes () const
   { 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); }
   uint32_t hash () const { return as_array ().hash (); }

   Type& operator [] (int i_)
   {
     unsigned int i = (unsigned int) i_;
     if (unlikely (i >= length))
       return Crap (Type);
     return arrayZ[i];
   }
   const Type& operator [] (int i_) const
   {
     unsigned int i = (unsigned int) i_;
     if (unlikely (i >= length))
       return Null (Type);
     return arrayZ[i];
   }

   Type& tail () { return (*this)[length - 1]; }
   const Type& tail () const { return (*this)[length - 1]; }

   explicit operator bool () const { return length; }
   unsigned get_size () const { return length * item_size; }

   /* Sink interface. */
   template <typename T>
   hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; }

   array_t   as_array ()       { return hb_array (arrayZ, length); }
   c_array_t as_array () const { return hb_array (arrayZ, length); }

   /* Iterator. */
   typedef c_array_t   iter_t;
   typedef array_t   writer_t;
     iter_t   iter () const { return as_array (); }
   writer_t writer ()       { return as_array (); }
   operator   iter_t () const { return   iter (); }
   operator writer_t ()       { return writer (); }

   /* 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); }
   hb_sorted_array_t<const Type> as_sorted_array () const
   { return hb_sorted_array (arrayZ, length); }

   template <typename T> explicit operator T * () { return arrayZ; }
   template <typename T> explicit operator const T * () const { return arrayZ; }

   Type * operator  + (unsigned int i) { return arrayZ + i; }
   const Type * operator  + (unsigned int i) const { return arrayZ + i; }

   Type *push ()
   {
     if (unlikely (!resize (length + 1)))
       return std::addressof (Crap (Type));
     return std::addressof (arrayZ[length - 1]);
   }
   template <typename... Args> Type *push (Args&&... args)
   {
     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 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 (hb_is_trivially_copy_assignable(T))>
   Type *
   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 (!hb_is_trivially_copy_assignable(T))>
   Type *
   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 ();
 	new_array[i] = std::move (arrayZ[i]);
 	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 (hb_is_trivially_constructible(T))>
   void
   grow_vector (unsigned size, hb_priority<0>)
   {
     hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
     length = size;
   }
   template <typename T = Type,
 	    hb_enable_if (!hb_is_trivially_constructible(T))>
   void
   grow_vector (unsigned size, hb_priority<0>)
   {
     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 (hb_is_same (T, hb_vector_t<typename T::item_t>) ||
 			  hb_is_same (T, hb_array_t <typename T::item_t>))>
   void
   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 (hb_is_trivially_copyable (T))>
   void
   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)
   {
     length = 0;
     while (length < other.length)
     {
       length++;
       new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]);
     }
   }
   template <typename T = Type,
 	    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
   copy_array (hb_array_t<const Type> other)
   {
     length = 0;
     while (length < other.length)
     {
       length++;
       new (std::addressof (arrayZ[length - 1])) Type ();
       arrayZ[length - 1] = other.arrayZ[length - 1];
     }
   }

   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)
   {
     for (; i < length; i++)
       arrayZ[i - 1] = std::move (arrayZ[i]);
   }

   /* Allocate for size but don't adjust length. */
   bool alloc (unsigned int size, bool exact=false)
   {
     if (unlikely (in_error ()))
       return false;

     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;

       new_allocated = size;
     }
     else
     {
       if (likely (size <= (unsigned) allocated))
 	return true;

       new_allocated = allocated;
       while (size > new_allocated)
 	new_allocated += (new_allocated >> 1) + 8;
     }


     /* Reallocate */

     bool overflows =
       (int) in_error () ||
       (new_allocated < size) ||
       hb_unsigned_mul_overflows (new_allocated, sizeof (Type));

     if (unlikely (overflows))
     {
       set_error ();
       return false;
     }

     Type *new_array = realloc_vector (new_allocated, hb_prioritize);

     if (unlikely (new_allocated && !new_array))
     {
       if (new_allocated <= (unsigned) allocated)
         return true; // shrinking failed; it's okay; happens in our fuzzer

       set_error ();
       return false;
     }

     arrayZ = new_array;
     allocated = new_allocated;

     return true;
   }

   bool resize (int size_, bool initialize = true, bool exact = false)
   {
     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
     if (!alloc (size, exact))
       return false;

     if (size > length)
     {
       if (initialize)
 	grow_vector (size, hb_prioritize);
     }
     else if (size < length)
     {
       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]));
     arrayZ[length - 1].~Type ();
     length--;
     return v;
   }

   void remove_ordered (unsigned int i)
   {
     if (unlikely (i >= length))
       return;
     shift_down_vector (i + 1);
     arrayZ[length - 1].~Type ();
     length--;
   }

   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*) = Type::cmp)
   { as_array ().qsort (cmp); }

   /* Unsorted search API. */
   template <typename T>
   Type *lsearch (const T &x, Type *not_found = nullptr)
   { return as_array ().lsearch (x, not_found); }
   template <typename T>
   const Type *lsearch (const T &x, const Type *not_found = nullptr) const
   { return as_array ().lsearch (x, not_found); }
   template <typename T>
   bool lfind (const T &x, unsigned *pos = nullptr) const
   { return as_array ().lfind (x, pos); }

   /* Sorted search API. */
   template <typename T,
 	    bool Sorted=sorted, hb_enable_if (Sorted)>
   Type *bsearch (const T &x, Type *not_found = nullptr)
   { return as_array ().bsearch (x, not_found); }
   template <typename T,
 	    bool Sorted=sorted, hb_enable_if (Sorted)>
   const Type *bsearch (const T &x, const Type *not_found = nullptr) const
   { return as_array ().bsearch (x, not_found); }
   template <typename T,
 	    bool Sorted=sorted, hb_enable_if (Sorted)>
   bool bfind (const T &x, unsigned int *i = nullptr,
 	      hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
 	      unsigned int to_store = (unsigned int) -1) const
   { return as_array ().bfind (x, i, not_found, to_store); }
 };

 template <typename Type>
 using hb_sorted_vector_t = hb_vector_t<Type, true>;

 #endif /* HB_VECTOR_HH */
	/*
	* Copyright © 2017,2018 Google, Inc.
	*
	* This is part of HarfBuzz, a text shaping library.
	*
	* Permission is hereby granted, without written agreement and without
	* license or royalty fees, to use, copy, modify, and distribute this
	* software and its documentation for any purpose, provided that the
	* above copyright notice and the following two paragraphs appear in
	* all copies of this software.
	*
	* IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
	* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
	* ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
	* IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
	* DAMAGE.
	*
	* THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
	* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
	* FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
	* ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
	* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
	*
	* Google Author(s): Behdad Esfahbod
	*/

	#ifndef HB_VECTOR_HH
	#define HB_VECTOR_HH

	#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
	{
	typedef Type item_t;
	static constexpr unsigned item_size = hb_static_size (Type);
	using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type;
	using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type;

	hb_vector_t () = default;
	hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
	{
	alloc (lst.size (), true);
	for (auto&& item : lst)
	push (item);
	}
	template <typename Iterable,
	hb_requires (hb_is_iterable (Iterable))>
	hb_vector_t (const Iterable &o) : hb_vector_t ()
	{
	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, 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)
	{
	allocated = o.allocated;
	length = o.length;
	arrayZ = o.arrayZ;
	o.init ();
	}
	~hb_vector_t () { fini (); }

	public:
	int allocated = 0; /* < 0 means allocation failed. */
	unsigned int length = 0;
	public:
	Type *arrayZ = nullptr;

	void init ()
	{
	allocated = length = 0;
	arrayZ = nullptr;
	}
	void init0 ()
	{
	}

	void fini ()
	{
	/* 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 ()))
	reset_error ();
	resize (0);
	}

	friend void swap (hb_vector_t& a, hb_vector_t& b)
	{
	hb_swap (a.allocated, b.allocated);
	hb_swap (a.length, b.length);
	hb_swap (a.arrayZ, b.arrayZ);
	}

	hb_vector_t& operator = (const hb_vector_t &o)
	{
	reset ();
	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)
	{
	hb_swap (*this, o);
	return *this;
	}

	hb_bytes_t as_bytes () const
	{ 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); }
	uint32_t hash () const { return as_array ().hash (); }

	Type& operator [] (int i_)
	{
	unsigned int i = (unsigned int) i_;
	if (unlikely (i >= length))
	return Crap (Type);
	return arrayZ[i];
	}
	const Type& operator [] (int i_) const
	{
	unsigned int i = (unsigned int) i_;
	if (unlikely (i >= length))
	return Null (Type);
	return arrayZ[i];
	}

	Type& tail () { return (*this)[length - 1]; }
	const Type& tail () const { return (*this)[length - 1]; }

	explicit operator bool () const { return length; }
	unsigned get_size () const { return length * item_size; }

	/* Sink interface. */
	template <typename T>
	hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; }

	array_t as_array () { return hb_array (arrayZ, length); }
	c_array_t as_array () const { return hb_array (arrayZ, length); }

	/* Iterator. */
	typedef c_array_t iter_t;
	typedef array_t writer_t;
	iter_t iter () const { return as_array (); }
	writer_t writer () { return as_array (); }
	operator iter_t () const { return iter (); }
	operator writer_t () { return writer (); }

	/* 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); }
	hb_sorted_array_t<const Type> as_sorted_array () const
	{ return hb_sorted_array (arrayZ, length); }

	template <typename T> explicit operator T * () { return arrayZ; }
	template <typename T> explicit operator const T * () const { return arrayZ; }

	Type * operator + (unsigned int i) { return arrayZ + i; }
	const Type * operator + (unsigned int i) const { return arrayZ + i; }

	Type *push ()
	{
	if (unlikely (!resize (length + 1)))
	return std::addressof (Crap (Type));
	return std::addressof (arrayZ[length - 1]);
	}
	template <typename... Args> Type *push (Args&&... args)
	{
	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 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 (hb_is_trivially_copy_assignable(T))>
	Type *
	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 (!hb_is_trivially_copy_assignable(T))>
	Type *
	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 ();
	new_array[i] = std::move (arrayZ[i]);
	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 (hb_is_trivially_constructible(T))>
	void
	grow_vector (unsigned size, hb_priority<0>)
	{
	hb_memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
	length = size;
	}
	template <typename T = Type,
	hb_enable_if (!hb_is_trivially_constructible(T))>
	void
	grow_vector (unsigned size, hb_priority<0>)
	{
	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 (hb_is_same (T, hb_vector_t<typename T::item_t>) \|\|
	hb_is_same (T, hb_array_t <typename T::item_t>))>
	void
	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 (hb_is_trivially_copyable (T))>
	void
	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)
	{
	length = 0;
	while (length < other.length)
	{
	length++;
	new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]);
	}
	}
	template <typename T = Type,
	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
	copy_array (hb_array_t<const Type> other)
	{
	length = 0;
	while (length < other.length)
	{
	length++;
	new (std::addressof (arrayZ[length - 1])) Type ();
	arrayZ[length - 1] = other.arrayZ[length - 1];
	}
	}

	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)
	{
	for (; i < length; i++)
	arrayZ[i - 1] = std::move (arrayZ[i]);
	}

	/* Allocate for size but don't adjust length. */
	bool alloc (unsigned int size, bool exact=false)
	{
	if (unlikely (in_error ()))
	return false;

	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;

	new_allocated = size;
	}
	else
	{
	if (likely (size <= (unsigned) allocated))
	return true;

	new_allocated = allocated;
	while (size > new_allocated)
	new_allocated += (new_allocated >> 1) + 8;
	}


	/* Reallocate */

	bool overflows =
	(int) in_error () \|\|
	(new_allocated < size) \|\|
	hb_unsigned_mul_overflows (new_allocated, sizeof (Type));

	if (unlikely (overflows))
	{
	set_error ();
	return false;
	}

	Type *new_array = realloc_vector (new_allocated, hb_prioritize);

	if (unlikely (new_allocated && !new_array))
	{
	if (new_allocated <= (unsigned) allocated)
	return true; // shrinking failed; it's okay; happens in our fuzzer

	set_error ();
	return false;
	}

	arrayZ = new_array;
	allocated = new_allocated;

	return true;
	}

	bool resize (int size_, bool initialize = true, bool exact = false)
	{
	unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
	if (!alloc (size, exact))
	return false;

	if (size > length)
	{
	if (initialize)
	grow_vector (size, hb_prioritize);
	}
	else if (size < length)
	{
	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]));
	arrayZ[length - 1].~Type ();
	length--;
	return v;
	}

	void remove_ordered (unsigned int i)
	{
	if (unlikely (i >= length))
	return;
	shift_down_vector (i + 1);
	arrayZ[length - 1].~Type ();
	length--;
	}

	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*) = Type::cmp)
	{ as_array ().qsort (cmp); }

	/* Unsorted search API. */
	template <typename T>
	Type lsearch (const T &x, Type not_found = nullptr)
	{ return as_array ().lsearch (x, not_found); }
	template <typename T>
	const Type lsearch (const T &x, const Type not_found = nullptr) const
	{ return as_array ().lsearch (x, not_found); }
	template <typename T>
	bool lfind (const T &x, unsigned *pos = nullptr) const
	{ return as_array ().lfind (x, pos); }

	/* Sorted search API. */
	template <typename T,
	bool Sorted=sorted, hb_enable_if (Sorted)>
	Type bsearch (const T &x, Type not_found = nullptr)
	{ return as_array ().bsearch (x, not_found); }
	template <typename T,
	bool Sorted=sorted, hb_enable_if (Sorted)>
	const Type bsearch (const T &x, const Type not_found = nullptr) const
	{ return as_array ().bsearch (x, not_found); }
	template <typename T,
	bool Sorted=sorted, hb_enable_if (Sorted)>
	bool bfind (const T &x, unsigned int *i = nullptr,
	hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
	unsigned int to_store = (unsigned int) -1) const
	{ return as_array ().bfind (x, i, not_found, to_store); }
	};

	template <typename Type>
	using hb_sorted_vector_t = hb_vector_t<Type, true>;

	#endif /* HB_VECTOR_HH */