Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/hb-array.hh @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * Copyright © 2018 Google, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Google Author(s): Behdad Esfahbod
25 */
26
27 #ifndef HB_ARRAY_HH
28 #define HB_ARRAY_HH
29
30 #include "hb.hh"
31 #include "hb-algs.hh"
32 #include "hb-iter.hh"
33 #include "hb-null.hh"
34
35
36 template <typename Type>
37 struct hb_sorted_array_t;
38
39 enum hb_not_found_t
40 {
41 HB_NOT_FOUND_DONT_STORE,
42 HB_NOT_FOUND_STORE,
43 HB_NOT_FOUND_STORE_CLOSEST,
44 };
45
46
47 template <typename Type>
48 struct hb_array_t : hb_iter_with_fallback_t<hb_array_t<Type>, Type&>
49 {
50 /*
51 * Constructors.
52 */
53 hb_array_t () = default;
54 hb_array_t (const hb_array_t&) = default;
55 ~hb_array_t () = default;
56 hb_array_t& operator= (const hb_array_t&) = default;
57 hb_array_t& operator= (hb_array_t&&) = default;
58
59 constexpr hb_array_t (Type *array_, unsigned int length_) : arrayZ (array_), length (length_) {}
60 template <unsigned int length_>
61 constexpr hb_array_t (Type (&array_)[length_]) : hb_array_t (array_, length_) {}
62
63 template <typename U,
64 hb_enable_if (hb_is_cr_convertible(U, Type))>
65 constexpr hb_array_t (const hb_array_t<U> &o) :
66 hb_iter_with_fallback_t<hb_array_t, Type&> (),
67 arrayZ (o.arrayZ), length (o.length), backwards_length (o.backwards_length) {}
68 template <typename U,
69 hb_enable_if (hb_is_cr_convertible(U, Type))>
70 hb_array_t& operator = (const hb_array_t<U> &o)
71 { arrayZ = o.arrayZ; length = o.length; backwards_length = o.backwards_length; return *this; }
72
73 /*
74 * Iterator implementation.
75 */
76 typedef Type& __item_t__;
77 static constexpr bool is_random_access_iterator = true;
78 Type& __item_at__ (unsigned i) const
79 {
80 if (unlikely (i >= length)) return CrapOrNull (Type);
81 return arrayZ[i];
82 }
83 void __forward__ (unsigned n)
84 {
85 if (unlikely (n > length))
86 n = length;
87 length -= n;
88 backwards_length += n;
89 arrayZ += n;
90 }
91 void __rewind__ (unsigned n)
92 {
93 if (unlikely (n > backwards_length))
94 n = backwards_length;
95 length += n;
96 backwards_length -= n;
97 arrayZ -= n;
98 }
99 unsigned __len__ () const { return length; }
100 /* Ouch. The operator== compares the contents of the array. For range-based for loops,
101 * it's best if we can just compare arrayZ, though comparing contents is still fast,
102 * but also would require that Type has operator==. As such, we optimize this operator
103 * for range-based for loop and just compare arrayZ and length.
104 *
105 * The above comment is outdated now because we implemented separate begin/end to
106 * objects that were using hb_array_t for range-based loop before. */
107 bool operator != (const hb_array_t& o) const
108 { return this->arrayZ != o.arrayZ || this->length != o.length; }
109
110 /* Faster range-based for loop without bounds-check. */
111 Type *begin () const { return arrayZ; }
112 Type *end () const { return arrayZ + length; }
113
114
115 /* Extra operators.
116 */
117 Type * operator & () const { return arrayZ; }
118 operator hb_array_t<const Type> () { return hb_array_t<const Type> (arrayZ, length); }
119 template <typename T> operator T * () const { return arrayZ; }
120
121 HB_INTERNAL bool operator == (const hb_array_t &o) const;
122
123 uint32_t hash () const
124 {
125 uint32_t current = 0;
126 for (auto &v : *this)
127 current = current * 31 + hb_hash (v);
128 return current;
129 }
130
131 /*
132 * Compare, Sort, and Search.
133 */
134
135 /* Note: our compare is NOT lexicographic; it also does NOT call Type::cmp. */
136 int cmp (const hb_array_t &a) const
137 {
138 if (length != a.length)
139 return (int) a.length - (int) length;
140 return hb_memcmp (a.arrayZ, arrayZ, get_size ());
141 }
142 HB_INTERNAL static int cmp (const void *pa, const void *pb)
143 {
144 hb_array_t *a = (hb_array_t *) pa;
145 hb_array_t *b = (hb_array_t *) pb;
146 return b->cmp (*a);
147 }
148
149 template <typename T>
150 Type *lsearch (const T &x, Type *not_found = nullptr)
151 {
152 unsigned i;
153 return lfind (x, &i) ? &this->arrayZ[i] : not_found;
154 }
155 template <typename T>
156 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
157 {
158 unsigned i;
159 return lfind (x, &i) ? &this->arrayZ[i] : not_found;
160 }
161 template <typename T>
162 bool lfind (const T &x, unsigned *pos = nullptr,
163 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
164 unsigned int to_store = (unsigned int) -1) const
165 {
166 for (unsigned i = 0; i < length; ++i)
167 if (hb_equal (x, this->arrayZ[i]))
168 {
169 if (pos)
170 *pos = i;
171 return true;
172 }
173
174 if (pos)
175 {
176 switch (not_found)
177 {
178 case HB_NOT_FOUND_DONT_STORE:
179 break;
180
181 case HB_NOT_FOUND_STORE:
182 *pos = to_store;
183 break;
184
185 case HB_NOT_FOUND_STORE_CLOSEST:
186 *pos = length;
187 break;
188 }
189 }
190 return false;
191 }
192
193 hb_sorted_array_t<Type> qsort (int (*cmp_)(const void*, const void*))
194 {
195 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), "");
196 if (likely (length))
197 hb_qsort (arrayZ, length, this->get_item_size (), cmp_);
198 return hb_sorted_array_t<Type> (*this);
199 }
200 hb_sorted_array_t<Type> qsort ()
201 {
202 //static_assert (hb_enable_if (hb_is_trivially_copy_assignable(Type)), "");
203 if (likely (length))
204 hb_qsort (arrayZ, length, this->get_item_size (), Type::cmp);
205 return hb_sorted_array_t<Type> (*this);
206 }
207
208 /*
209 * Other methods.
210 */
211
212 unsigned int get_size () const { return length * this->get_item_size (); }
213
214 /*
215 * Reverse the order of items in this array in the range [start, end).
216 */
217 void reverse (unsigned start = 0, unsigned end = -1)
218 {
219 start = hb_min (start, length);
220 end = hb_min (end, length);
221
222 if (end < start + 2)
223 return;
224
225 for (unsigned lhs = start, rhs = end - 1; lhs < rhs; lhs++, rhs--)
226 hb_swap (arrayZ[rhs], arrayZ[lhs]);
227 }
228
229 hb_array_t sub_array (unsigned int start_offset = 0, unsigned int *seg_count = nullptr /* IN/OUT */) const
230 {
231 if (!start_offset && !seg_count)
232 return *this;
233
234 unsigned int count = length;
235 if (unlikely (start_offset > count))
236 count = 0;
237 else
238 count -= start_offset;
239 if (seg_count)
240 count = *seg_count = hb_min (count, *seg_count);
241 return hb_array_t (arrayZ + start_offset, count);
242 }
243 hb_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
244 { return sub_array (start_offset, &seg_count); }
245
246 hb_array_t truncate (unsigned length) const { return sub_array (0, length); }
247
248 template <typename T,
249 unsigned P = sizeof (Type),
250 hb_enable_if (P == 1)>
251 const T *as () const
252 { return length < hb_min_size (T) ? &Null (T) : reinterpret_cast<const T *> (arrayZ); }
253
254 template <typename T,
255 unsigned P = sizeof (Type),
256 hb_enable_if (P == 1)>
257 bool check_range (const T *p, unsigned int size = T::static_size) const
258 {
259 return arrayZ <= ((const char *) p)
260 && ((const char *) p) <= arrayZ + length
261 && (unsigned int) (arrayZ + length - (const char *) p) >= size;
262 }
263
264 /* Only call if you allocated the underlying array using hb_malloc() or similar. */
265 void fini ()
266 { hb_free ((void *) arrayZ); arrayZ = nullptr; length = 0; }
267
268 template <typename hb_serialize_context_t,
269 typename U = Type,
270 hb_enable_if (!(sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>)))>
271 hb_array_t copy (hb_serialize_context_t *c) const
272 {
273 TRACE_SERIALIZE (this);
274 auto* out = c->start_embed (arrayZ);
275 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ());
276 for (unsigned i = 0; i < length; i++)
277 out[i] = arrayZ[i]; /* TODO: add version that calls c->copy() */
278 return_trace (hb_array_t (out, length));
279 }
280
281 template <typename hb_serialize_context_t,
282 typename U = Type,
283 hb_enable_if (sizeof (U) < sizeof (long long) && hb_is_trivially_copy_assignable(hb_decay<Type>))>
284 hb_array_t copy (hb_serialize_context_t *c) const
285 {
286 TRACE_SERIALIZE (this);
287 auto* out = c->start_embed (arrayZ);
288 if (unlikely (!c->extend_size (out, get_size (), false))) return_trace (hb_array_t ());
289 hb_memcpy (out, arrayZ, get_size ());
290 return_trace (hb_array_t (out, length));
291 }
292
293 template <typename hb_sanitize_context_t>
294 bool sanitize (hb_sanitize_context_t *c) const
295 { return c->check_array (arrayZ, length); }
296
297 /*
298 * Members
299 */
300
301 public:
302 Type *arrayZ = nullptr;
303 unsigned int length = 0;
304 unsigned int backwards_length = 0;
305 };
306 template <typename T> inline hb_array_t<T>
307 hb_array (T *array, unsigned int length)
308 { return hb_array_t<T> (array, length); }
309 template <typename T, unsigned int length_> inline hb_array_t<T>
310 hb_array (T (&array_)[length_])
311 { return hb_array_t<T> (array_); }
312
313 template <typename Type>
314 struct hb_sorted_array_t :
315 hb_array_t<Type>,
316 hb_iter_t<hb_sorted_array_t<Type>, Type&>
317 {
318 typedef hb_iter_t<hb_sorted_array_t, Type&> iter_base_t;
319 HB_ITER_USING (iter_base_t);
320 static constexpr bool is_random_access_iterator = true;
321 static constexpr bool is_sorted_iterator = true;
322
323 hb_sorted_array_t () = default;
324 hb_sorted_array_t (const hb_sorted_array_t&) = default;
325 ~hb_sorted_array_t () = default;
326 hb_sorted_array_t& operator= (const hb_sorted_array_t&) = default;
327 hb_sorted_array_t& operator= (hb_sorted_array_t&&) = default;
328
329 constexpr hb_sorted_array_t (Type *array_, unsigned int length_) : hb_array_t<Type> (array_, length_) {}
330 template <unsigned int length_>
331 constexpr hb_sorted_array_t (Type (&array_)[length_]) : hb_array_t<Type> (array_) {}
332
333 template <typename U,
334 hb_enable_if (hb_is_cr_convertible(U, Type))>
335 constexpr hb_sorted_array_t (const hb_array_t<U> &o) :
336 hb_array_t<Type> (o),
337 hb_iter_t<hb_sorted_array_t, Type&> () {}
338 template <typename U,
339 hb_enable_if (hb_is_cr_convertible(U, Type))>
340 hb_sorted_array_t& operator = (const hb_array_t<U> &o)
341 { hb_array_t<Type> (*this) = o; return *this; }
342
343 /* Iterator implementation. */
344
345 /* See comment in hb_array_of::operator != */
346 bool operator != (const hb_sorted_array_t& o) const
347 { return this->arrayZ != o.arrayZ || this->length != o.length; }
348
349 /* Faster range-based for loop without bounds-check. */
350 Type *begin () const { return this->arrayZ; }
351 Type *end () const { return this->arrayZ + this->length; }
352
353
354 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int *seg_count /* IN/OUT */) const
355 { return hb_sorted_array_t (((const hb_array_t<Type> *) (this))->sub_array (start_offset, seg_count)); }
356 hb_sorted_array_t sub_array (unsigned int start_offset, unsigned int seg_count) const
357 { return sub_array (start_offset, &seg_count); }
358
359 hb_sorted_array_t truncate (unsigned length) const { return sub_array (0, length); }
360
361 template <typename T>
362 Type *bsearch (const T &x, Type *not_found = nullptr)
363 {
364 unsigned int i;
365 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
366 }
367 template <typename T>
368 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
369 {
370 unsigned int i;
371 return bfind (x, &i) ? &this->arrayZ[i] : not_found;
372 }
373 template <typename T>
374 bool bfind (const T &x, unsigned int *i = nullptr,
375 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
376 unsigned int to_store = (unsigned int) -1) const
377 {
378 unsigned pos;
379
380 if (bsearch_impl (x, &pos))
381 {
382 if (i)
383 *i = pos;
384 return true;
385 }
386
387 if (i)
388 {
389 switch (not_found)
390 {
391 case HB_NOT_FOUND_DONT_STORE:
392 break;
393
394 case HB_NOT_FOUND_STORE:
395 *i = to_store;
396 break;
397
398 case HB_NOT_FOUND_STORE_CLOSEST:
399 *i = pos;
400 break;
401 }
402 }
403 return false;
404 }
405 template <typename T, typename ...Ts>
406 bool bsearch_impl (const T &x, unsigned *pos, Ts... ds) const
407 {
408 return hb_bsearch_impl (pos,
409 x,
410 this->arrayZ,
411 this->length,
412 sizeof (Type),
413 _hb_cmp_method<T, Type, Ts...>,
414 std::forward<Ts> (ds)...);
415 }
416 };
417 template <typename T> inline hb_sorted_array_t<T>
418 hb_sorted_array (T *array, unsigned int length)
419 { return hb_sorted_array_t<T> (array, length); }
420 template <typename T, unsigned int length_> inline hb_sorted_array_t<T>
421 hb_sorted_array (T (&array_)[length_])
422 { return hb_sorted_array_t<T> (array_); }
423
424 template <typename T>
425 inline bool hb_array_t<T>::operator == (const hb_array_t<T> &o) const
426 {
427 if (o.length != this->length) return false;
428 for (unsigned int i = 0; i < this->length; i++) {
429 if (this->arrayZ[i] != o.arrayZ[i]) return false;
430 }
431 return true;
432 }
433 template <>
434 inline bool hb_array_t<const char>::operator == (const hb_array_t<const char> &o) const
435 {
436 if (o.length != this->length) return false;
437 return 0 == hb_memcmp (arrayZ, o.arrayZ, length);
438 }
439 template <>
440 inline bool hb_array_t<const unsigned char>::operator == (const hb_array_t<const unsigned char> &o) const
441 {
442 if (o.length != this->length) return false;
443 return 0 == hb_memcmp (arrayZ, o.arrayZ, length);
444 }
445
446
447 /* Specialize hash() for byte arrays. */
448
449 template <>
450 inline uint32_t hb_array_t<const char>::hash () const
451 {
452 uint32_t current = 0;
453 unsigned i = 0;
454
455 #if defined(__OPTIMIZE__) && !defined(HB_NO_PACKED) && \
456 ((defined(__GNUC__) && __GNUC__ >= 5) || defined(__clang__))
457 struct __attribute__((packed)) packed_uint32_t { uint32_t v; };
458 for (; i + 4 <= this->length; i += 4)
459 current = current * 31 + hb_hash ((uint32_t) ((packed_uint32_t *) &this->arrayZ[i])->v);
460 #endif
461
462 for (; i < this->length; i++)
463 current = current * 31 + hb_hash (this->arrayZ[i]);
464 return current;
465 }
466
467 template <>
468 inline uint32_t hb_array_t<const unsigned char>::hash () const
469 {
470 uint32_t current = 0;
471 unsigned i = 0;
472
473 #if defined(__OPTIMIZE__) && !defined(HB_NO_PACKED) && \
474 ((defined(__GNUC__) && __GNUC__ >= 5) || defined(__clang__))
475 struct __attribute__((packed)) packed_uint32_t { uint32_t v; };
476 for (; i + 4 <= this->length; i += 4)
477 current = current * 31 + hb_hash ((uint32_t) ((packed_uint32_t *) &this->arrayZ[i])->v);
478 #endif
479
480 for (; i < this->length; i++)
481 current = current * 31 + hb_hash (this->arrayZ[i]);
482 return current;
483 }
484
485
486 typedef hb_array_t<const char> hb_bytes_t;
487 typedef hb_array_t<const unsigned char> hb_ubytes_t;
488
489
490
491 #endif /* HB_ARRAY_HH */