diff options
Diffstat (limited to 'src/3rdparty/harfbuzz-ng/src/hb-vector.hh')
| -rw-r--r-- | src/3rdparty/harfbuzz-ng/src/hb-vector.hh | 436 |
1 files changed, 326 insertions, 110 deletions
diff --git a/src/3rdparty/harfbuzz-ng/src/hb-vector.hh b/src/3rdparty/harfbuzz-ng/src/hb-vector.hh index 110d457caf..dfe1b7d1c7 100644 --- a/src/3rdparty/harfbuzz-ng/src/hb-vector.hh +++ b/src/3rdparty/harfbuzz-ng/src/hb-vector.hh @@ -29,21 +29,54 @@ #include "hb.hh" #include "hb-array.hh" +#include "hb-meta.hh" #include "hb-null.hh" -template <typename Type> +template <typename Type, + bool sorted=false> struct hb_vector_t { + static constexpr bool realloc_move = true; + 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 () { init (); } - hb_vector_t (const hb_vector_t &o) + hb_vector_t () = default; + hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t () { - init (); - alloc (o.length); - hb_copy (o, *this); + 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) { @@ -54,58 +87,66 @@ struct hb_vector_t } ~hb_vector_t () { fini (); } - private: - int allocated; /* == -1 means allocation failed. */ public: - unsigned int length; + int allocated = 0; /* < 0 means allocation failed. */ + unsigned int length = 0; public: - Type *arrayZ; + Type *arrayZ = nullptr; void init () { allocated = length = 0; arrayZ = nullptr; } + void init0 () + { + } void fini () { - 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 fini_deep () - { - unsigned int count = length; - for (unsigned int i = 0; i < count; i++) - arrayZ[i].fini (); - fini (); - } void reset () { if (unlikely (in_error ())) - allocated = length; // Big hack! + 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); - 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) { - fini (); - allocated = o.allocated; - length = o.length; - arrayZ = o.arrayZ; - o.init (); + hb_swap (*this, o); return *this; } 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); } @@ -134,27 +175,23 @@ struct hb_vector_t /* Sink interface. */ template <typename T> - hb_vector_t& operator << (T&& v) { push (hb_forward<T> (v)); return *this; } + hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; } - hb_array_t< Type> as_array () { return hb_array (arrayZ, length); } - hb_array_t<const Type> as_array () const { return hb_array (arrayZ, length); } + array_t as_array () { return hb_array (arrayZ, length); } + c_array_t as_array () const { return hb_array (arrayZ, length); } /* Iterator. */ - typedef hb_array_t<const Type> iter_t; - typedef hb_array_t< Type> writer_t; + 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 (); } - hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const - { return as_array ().sub_array (start_offset, count); } - hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const - { return as_array ().sub_array (start_offset, count); } - hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) - { return as_array ().sub_array (start_offset, count); } - hb_array_t<Type> 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); } @@ -170,50 +207,223 @@ struct hb_vector_t 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) { - 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 = hb_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 (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 types that can be moved using realloc(). */ + template <typename T = Type, + hb_enable_if (T::realloc_move)> + 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 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; - unsigned int new_allocated = allocated; - while (size >= new_allocated) - new_allocated += (new_allocated >> 1) + 8; + new_allocated = allocated; + while (size > new_allocated) + new_allocated += (new_allocated >> 1) + 8; + } + + + /* Reallocate */ - Type *new_array = nullptr; 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 = (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type)); - if (unlikely (!new_array)) + if (unlikely (overflows)) { - allocated = -1; + 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; } @@ -223,64 +433,79 @@ struct hb_vector_t 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) - memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ)); + { + 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); - return hb_move (arrayZ[--length]); /* Does this move actually work? */ + 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; - memmove (static_cast<void *> (&arrayZ[i]), - static_cast<void *> (&arrayZ[i + 1]), - (length - i - 1) * sizeof (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) { - unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; - if (size < length) - length = size; + if (unlikely (i >= length)) + return; + if (i != length - 1) + arrayZ[i] = std::move (arrayZ[length - 1]); + arrayZ[length - 1].~Type (); + length--; } - template <typename T> - Type *find (T v) + void shrink (int size_, bool shrink_memory = true) { - for (unsigned int i = 0; i < length; i++) - if (arrayZ[i] == v) - return &arrayZ[i]; - return nullptr; - } - template <typename T> - const Type *find (T v) const - { - for (unsigned int i = 0; i < length; i++) - if (arrayZ[i] == v) - return &arrayZ[i]; - return nullptr; + 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. */ } - void qsort (int (*cmp)(const void*, const void*)) + + /* Sorting API. */ + 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> Type *lsearch (const T &x, Type *not_found = nullptr) { return as_array ().lsearch (x, not_found); } @@ -290,34 +515,25 @@ struct hb_vector_t template <typename T> bool lfind (const T &x, unsigned *pos = nullptr) const { return as_array ().lfind (x, pos); } -}; - -template <typename Type> -struct hb_sorted_vector_t : hb_vector_t<Type> -{ - hb_sorted_array_t< Type> as_array () { return hb_sorted_array (this->arrayZ, this->length); } - hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->length); } - /* Iterator. */ - typedef hb_sorted_array_t<const Type> const_iter_t; - typedef hb_sorted_array_t< Type> iter_t; - const_iter_t iter () const { return as_array (); } - const_iter_t citer () const { return as_array (); } - iter_t iter () { return as_array (); } - operator iter_t () { return iter (); } - operator const_iter_t () const { return iter (); } - - template <typename T> + /* 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> + 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> + 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 */ |