#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);
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);
}
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)
{
}
~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;
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);
}
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)
}
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); }
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); }
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)
{
}
/* 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;
}
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>
projects / platform / upstream / harfbuzz.git / blobdiff