diff options
Diffstat (limited to 'src/3rdparty/harfbuzz-ng/src/hb-array.hh')
| -rw-r--r-- | src/3rdparty/harfbuzz-ng/src/hb-array.hh | 300 |
1 files changed, 211 insertions, 89 deletions
diff --git a/src/3rdparty/harfbuzz-ng/src/hb-array.hh b/src/3rdparty/harfbuzz-ng/src/hb-array.hh index d9adf2c728..9037179bc5 100644 --- a/src/3rdparty/harfbuzz-ng/src/hb-array.hh +++ b/src/3rdparty/harfbuzz-ng/src/hb-array.hh @@ -36,20 +36,35 @@ template <typename Type> struct hb_sorted_array_t; +enum hb_not_found_t +{ + HB_NOT_FOUND_DONT_STORE, + HB_NOT_FOUND_STORE, + HB_NOT_FOUND_STORE_CLOSEST, +}; + + template <typename Type> struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> { + static constexpr bool realloc_move = true; + /* * Constructors. */ - hb_array_t () : arrayZ (nullptr), length (0), backwards_length (0) {} - hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_), backwards_length (0) {} + hb_array_t () = default; + hb_array_t (const hb_array_t&) = default; + ~hb_array_t () = default; + hb_array_t& operator= (const hb_array_t&) = default; + hb_array_t& operator= (hb_array_t&&) = default; + + constexpr hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {} template <unsigned int length_> - hb_array_t (Type (&array_)[length_]) : arrayZ (array_), length (length_), backwards_length (0) {} + constexpr hb_array_t (Type (&array_)[length_]) : hb_array_t (array_, length_) {} template <typename U, hb_enable_if (hb_is_cr_convertible(U, Type))> - hb_array_t (const hb_array_t<U> &o) : + constexpr hb_array_t (const hb_array_t<U> &o) : hb_iter_with_fallback_t<hb_array_t, Type&> (), arrayZ (o.arrayZ), length (o.length), backwards_length (o.backwards_length) {} template <typename U, @@ -62,11 +77,25 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> */ typedef Type& __item_t__; static constexpr bool is_random_access_iterator = true; + static constexpr bool has_fast_len = true; + Type& __item__ () const + { + if (unlikely (!length)) return CrapOrNull (Type); + return *arrayZ; + } Type& __item_at__ (unsigned i) const { if (unlikely (i >= length)) return CrapOrNull (Type); return arrayZ[i]; } + void __next__ () + { + if (unlikely (!length)) + return; + length--; + backwards_length++; + arrayZ++; + } void __forward__ (unsigned n) { if (unlikely (n > length)) @@ -75,6 +104,14 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> backwards_length += n; arrayZ += n; } + void __prev__ () + { + if (unlikely (!backwards_length)) + return; + length++; + backwards_length--; + arrayZ--; + } void __rewind__ (unsigned n) { if (unlikely (n > backwards_length)) @@ -87,10 +124,17 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> /* Ouch. The operator== compares the contents of the array. For range-based for loops, * it's best if we can just compare arrayZ, though comparing contents is still fast, * but also would require that Type has operator==. As such, we optimize this operator - * for range-based for loop and just compare arrayZ. No need to compare length, as we - * assume we're only compared to .end(). */ + * for range-based for loop and just compare arrayZ and length. + * + * The above comment is outdated now because we implemented separate begin/end to + * objects that were using hb_array_t for range-based loop before. */ bool operator != (const hb_array_t& o) const - { return arrayZ != o.arrayZ; } + { return this->arrayZ != o.arrayZ || this->length != o.length; } + + /* Faster range-based for loop without bounds-check. */ + Type *begin () const { return arrayZ; } + Type *end () const { return arrayZ + length; } + /* Extra operators. */ @@ -100,10 +144,15 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> HB_INTERNAL bool operator == (const hb_array_t &o) const; - uint32_t hash () const { - uint32_t current = 0; - for (unsigned int i = 0; i < this->length; i++) { - current = current * 31 + hb_hash (this->arrayZ[i]); + uint32_t hash () const + { + // FNV-1a hash function + // https://github.com/harfbuzz/harfbuzz/pull/4228 + uint32_t current = /*cbf29ce4*/0x84222325; + for (auto &v : *this) + { + current = current ^ hb_hash (v); + current = current * 16777619; } return current; } @@ -129,41 +178,61 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> template <typename T> Type *lsearch (const T &x, Type *not_found = nullptr) { - unsigned int count = length; - for (unsigned int i = 0; i < count; i++) - if (!this->arrayZ[i].cmp (x)) - return &this->arrayZ[i]; - return not_found; + unsigned i; + return lfind (x, &i) ? &this->arrayZ[i] : not_found; } template <typename T> const Type *lsearch (const T &x, const Type *not_found = nullptr) const { - unsigned int count = length; - for (unsigned int i = 0; i < count; i++) - if (!this->arrayZ[i].cmp (x)) - return &this->arrayZ[i]; - return not_found; + unsigned i; + return lfind (x, &i) ? &this->arrayZ[i] : not_found; + } + template <typename T> + bool lfind (const T &x, unsigned *pos = nullptr, + hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, + unsigned int to_store = (unsigned int) -1) const + { + for (unsigned i = 0; i < length; ++i) + if (hb_equal (x, this->arrayZ[i])) + { + if (pos) + *pos = i; + return true; + } + + if (pos) + { + switch (not_found) + { + case HB_NOT_FOUND_DONT_STORE: + break; + + case HB_NOT_FOUND_STORE: + *pos = to_store; + break; + + case HB_NOT_FOUND_STORE_CLOSEST: + *pos = length; + break; + } + } + return false; } hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*)) { + //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), ""); if (likely (length)) hb_qsort (arrayZ, length, this->get_item_size (), cmp_); return hb_sorted_array_t<Type> (*this); } hb_sorted_array_t<Type> qsort () { + //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), ""); if (likely (length)) hb_qsort (arrayZ, length, this->get_item_size (), Type::cmp); return hb_sorted_array_t<Type> (*this); } - void qsort (unsigned int start, unsigned int end) - { - end = hb_min (end, length); - assert (start <= end); - if (likely (start < end)) - hb_qsort (arrayZ + start, end - start, this->get_item_size (), Type::cmp); - } /* * Other methods. @@ -171,6 +240,21 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> unsigned int get_size () const { return length * this->get_item_size (); } + /* + * Reverse the order of items in this array in the range [start, end). + */ + void reverse (unsigned start = 0, unsigned end = -1) + { + start = hb_min (start, length); + end = hb_min (end, length); + + if (end < start + 2) + return; + + for (unsigned lhs = start, rhs = end - 1; lhs < rhs; lhs++, rhs--) + hb_swap (arrayZ[rhs], arrayZ[lhs]); + } + hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const { if (!start_offset && !seg_count) @@ -194,32 +278,47 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> unsigned P = sizeof (Type), hb_enable_if (P == 1)> const T *as () const - { return length < hb_null_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); } + { return length < hb_min_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); } template <typename T, unsigned P = sizeof (Type), hb_enable_if (P == 1)> - bool in_range (const T *p, unsigned int size = T::static_size) const + bool check_range (const T *p, unsigned int size = T::static_size) const { - return ((const char *) p) >= arrayZ - && ((const char *) p + size) <= arrayZ + length; + return arrayZ <= ((const char *) p) + && ((const char *) p) <= arrayZ + length + && (unsigned int) (arrayZ + length - (const char *) p) >= size; } - /* Only call if you allocated the underlying array using malloc() or similar. */ - void free () - { ::free ((void *) arrayZ); arrayZ = nullptr; length = 0; } + /* Only call if you allocated the underlying array using hb_malloc() or similar. */ + void fini () + { hb_free ((void *) arrayZ); arrayZ = nullptr; length = 0; } - template <typename hb_serialize_context_t> + template <typename hb_serialize_context_t, + typename U = Type, + hb_enable_if (!(sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>)))> hb_array_t copy (hb_serialize_context_t *c) const { TRACE_SERIALIZE (this); auto* out = c->start_embed (arrayZ); - if (unlikely (!c->extend_size (out, get_size ()))) return_trace (hb_array_t ()); + if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ()); for (unsigned i = 0; i < length; i++) out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */ return_trace (hb_array_t (out, length)); } + template <typename hb_serialize_context_t, + typename U = Type, + hb_enable_if (sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>))> + hb_array_t copy (hb_serialize_context_t *c) const + { + TRACE_SERIALIZE (this); + auto* out = c->start_embed (arrayZ); + if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ()); + hb_memcpy (out, arrayZ, get_size ()); + return_trace (hb_array_t (out, length)); + } + template <typename hb_sanitize_context_t> bool sanitize (hb_sanitize_context_t *c) const { return c->check_array (arrayZ, length); } @@ -229,53 +328,62 @@ struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&> */ public: - Type *arrayZ; - unsigned int length; - unsigned int backwards_length; + Type *arrayZ = nullptr; + unsigned int length = 0; + unsigned int backwards_length = 0; }; template <typename T> inline hb_array_t<T> +hb_array () +{ return hb_array_t<T> (); } +template <typename T> inline hb_array_t<T> hb_array (T *array, unsigned int length) { return hb_array_t<T> (array, length); } template <typename T, unsigned int length_> inline hb_array_t<T> hb_array (T (&array_)[length_]) { return hb_array_t<T> (array_); } -enum hb_bfind_not_found_t -{ - HB_BFIND_NOT_FOUND_DONT_STORE, - HB_BFIND_NOT_FOUND_STORE, - HB_BFIND_NOT_FOUND_STORE_CLOSEST, -}; - template <typename Type> struct hb_sorted_array_t : - hb_iter_t<hb_sorted_array_t<Type>, Type&>, - hb_array_t<Type> + hb_array_t<Type>, + hb_iter_t<hb_sorted_array_t<Type>, Type&> { typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t; HB_ITER_USING (iter_base_t); static constexpr bool is_random_access_iterator = true; static constexpr bool is_sorted_iterator = true; + static constexpr bool has_fast_len = true; - hb_sorted_array_t () : hb_array_t<Type> () {} - hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {} + hb_sorted_array_t () = default; + hb_sorted_array_t (const hb_sorted_array_t&) = default; + ~hb_sorted_array_t () = default; + hb_sorted_array_t& operator= (const hb_sorted_array_t&) = default; + hb_sorted_array_t& operator= (hb_sorted_array_t&&) = default; + + constexpr hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {} template <unsigned int length_> - hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {} + constexpr hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {} template <typename U, hb_enable_if (hb_is_cr_convertible(U, Type))> - hb_sorted_array_t (const hb_array_t<U> &o) : - hb_iter_t<hb_sorted_array_t, Type&> (), - hb_array_t<Type> (o) {} + constexpr hb_sorted_array_t (const hb_array_t<U> &o) : + hb_array_t<Type> (o), + hb_iter_t<hb_sorted_array_t, Type&> () {} template <typename U, hb_enable_if (hb_is_cr_convertible(U, Type))> hb_sorted_array_t& operator = (const hb_array_t<U> &o) { hb_array_t<Type> (*this) = o; return *this; } /* Iterator implementation. */ + + /* See comment in hb_array_of::operator != */ bool operator != (const hb_sorted_array_t& o) const { return this->arrayZ != o.arrayZ || this->length != o.length; } + /* Faster range-based for loop without bounds-check. */ + Type *begin () const { return this->arrayZ; } + Type *end () const { return this->arrayZ + this->length; } + + hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); } hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const @@ -297,46 +405,47 @@ struct hb_sorted_array_t : } template <typename T> bool bfind (const T &x, unsigned int *i = nullptr, - hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE, + hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE, unsigned int to_store = (unsigned int) -1) const { - int min = 0, max = (int) this->length - 1; - const Type *array = this->arrayZ; - while (min <= max) + unsigned pos; + + if (bsearch_impl (x, &pos)) { - int mid = ((unsigned int) min + (unsigned int) max) / 2; - int c = array[mid].cmp (x); - if (c < 0) - max = mid - 1; - else if (c > 0) - min = mid + 1; - else - { - if (i) - *i = mid; - return true; - } + if (i) + *i = pos; + return true; } + if (i) { switch (not_found) { - case HB_BFIND_NOT_FOUND_DONT_STORE: + case HB_NOT_FOUND_DONT_STORE: break; - case HB_BFIND_NOT_FOUND_STORE: + case HB_NOT_FOUND_STORE: *i = to_store; break; - case HB_BFIND_NOT_FOUND_STORE_CLOSEST: - if (max < 0 || (max < (int) this->length && array[max].cmp (x) > 0)) - max++; - *i = max; + case HB_NOT_FOUND_STORE_CLOSEST: + *i = pos; break; } } return false; } + template <typename T, typename ...Ts> + bool bsearch_impl (const T &x, unsigned *pos, Ts... ds) const + { + return hb_bsearch_impl (pos, + x, + this->arrayZ, + this->length, + sizeof (Type), + _hb_cmp_method<T, Type, Ts...>, + std::forward<Ts> (ds)...); + } }; template <typename T> inline hb_sorted_array_t<T> hb_sorted_array (T *array, unsigned int length) @@ -346,7 +455,7 @@ hb_sorted_array (T (&array_)[length_]) { return hb_sorted_array_t<T> (array_); } template <typename T> -bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const +inline bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const { if (o.length != this->length) return false; for (unsigned int i = 0; i < this->length; i++) { @@ -354,24 +463,37 @@ bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const } return true; } +template <> +inline bool hb_array_t<const char>::operator == (const hb_array_t<const char> &o) const +{ + if (o.length != this->length) return false; + return 0 == hb_memcmp (arrayZ, o.arrayZ, length); +} +template <> +inline bool hb_array_t<const unsigned char>::operator == (const hb_array_t<const unsigned char> &o) const +{ + if (o.length != this->length) return false; + return 0 == hb_memcmp (arrayZ, o.arrayZ, length); +} + -/* TODO Specialize opeator== for hb_bytes_t and hb_ubytes_t. */ +/* Specialize hash() for byte arrays. */ +#ifndef HB_OPTIMIZE_SIZE_MORE template <> -inline uint32_t hb_array_t<const char>::hash () const { - uint32_t current = 0; - for (unsigned int i = 0; i < this->length; i++) - current = current * 31 + (uint32_t) (this->arrayZ[i] * 2654435761u); - return current; +inline uint32_t hb_array_t<const char>::hash () const +{ + // https://github.com/harfbuzz/harfbuzz/pull/4228 + return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */); } template <> -inline uint32_t hb_array_t<const unsigned char>::hash () const { - uint32_t current = 0; - for (unsigned int i = 0; i < this->length; i++) - current = current * 31 + (uint32_t) (this->arrayZ[i] * 2654435761u); - return current; +inline uint32_t hb_array_t<const unsigned char>::hash () const +{ + // https://github.com/harfbuzz/harfbuzz/pull/4228 + return fasthash32(arrayZ, length, 0xf437ffe6 /* magic? */); } +#endif typedef hb_array_t<const char> hb_bytes_t; |