Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/hb-vector.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 © 2017,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_VECTOR_HH
28 #define HB_VECTOR_HH
29
30 #include "hb.hh"
31 #include "hb-array.hh"
32 #include "hb-meta.hh"
33 #include "hb-null.hh"
34
35
36 template <typename Type,
37 bool sorted=false>
38 struct hb_vector_t
39 {
40 typedef Type item_t;
41 static constexpr unsigned item_size = hb_static_size (Type);
42 using array_t = typename std::conditional<sorted, hb_sorted_array_t<Type>, hb_array_t<Type>>::type;
43 using c_array_t = typename std::conditional<sorted, hb_sorted_array_t<const Type>, hb_array_t<const Type>>::type;
44
45 hb_vector_t () = default;
46 hb_vector_t (std::initializer_list<Type> lst) : hb_vector_t ()
47 {
48 alloc (lst.size ());
49 for (auto&& item : lst)
50 push (item);
51 }
52 template <typename Iterable,
53 hb_requires (hb_is_iterable (Iterable))>
54 hb_vector_t (const Iterable &o) : hb_vector_t ()
55 {
56 auto iter = hb_iter (o);
57 if (iter.is_random_access_iterator)
58 alloc (hb_len (iter));
59 hb_copy (iter, *this);
60 }
61 hb_vector_t (const hb_vector_t &o) : hb_vector_t ()
62 {
63 alloc (o.length);
64 if (unlikely (in_error ())) return;
65 copy_vector (o);
66 }
67 hb_vector_t (hb_vector_t &&o)
68 {
69 allocated = o.allocated;
70 length = o.length;
71 arrayZ = o.arrayZ;
72 o.init ();
73 }
74 ~hb_vector_t () { fini (); }
75
76 public:
77 int allocated = 0; /* == -1 means allocation failed. */
78 unsigned int length = 0;
79 public:
80 Type *arrayZ = nullptr;
81
82 void init ()
83 {
84 allocated = length = 0;
85 arrayZ = nullptr;
86 }
87 void init0 ()
88 {
89 }
90
91 void fini ()
92 {
93 shrink_vector (0);
94 hb_free (arrayZ);
95 init ();
96 }
97
98 void reset ()
99 {
100 if (unlikely (in_error ()))
101 /* Big Hack! We don't know the true allocated size before
102 * an allocation failure happened. But we know it was at
103 * least as big as length. Restore it to that and continue
104 * as if error did not happen. */
105 allocated = length;
106 resize (0);
107 }
108
109 friend void swap (hb_vector_t& a, hb_vector_t& b)
110 {
111 hb_swap (a.allocated, b.allocated);
112 hb_swap (a.length, b.length);
113 hb_swap (a.arrayZ, b.arrayZ);
114 }
115
116 hb_vector_t& operator = (const hb_vector_t &o)
117 {
118 reset ();
119 alloc (o.length);
120 if (unlikely (in_error ())) return *this;
121
122 copy_vector (o);
123
124 return *this;
125 }
126 hb_vector_t& operator = (hb_vector_t &&o)
127 {
128 hb_swap (*this, o);
129 return *this;
130 }
131
132 hb_bytes_t as_bytes () const
133 { return hb_bytes_t ((const char *) arrayZ, get_size ()); }
134
135 bool operator == (const hb_vector_t &o) const { return as_array () == o.as_array (); }
136 bool operator != (const hb_vector_t &o) const { return !(*this == o); }
137 uint32_t hash () const { return as_array ().hash (); }
138
139 Type& operator [] (int i_)
140 {
141 unsigned int i = (unsigned int) i_;
142 if (unlikely (i >= length))
143 return Crap (Type);
144 return arrayZ[i];
145 }
146 const Type& operator [] (int i_) const
147 {
148 unsigned int i = (unsigned int) i_;
149 if (unlikely (i >= length))
150 return Null (Type);
151 return arrayZ[i];
152 }
153
154 Type& tail () { return (*this)[length - 1]; }
155 const Type& tail () const { return (*this)[length - 1]; }
156
157 explicit operator bool () const { return length; }
158 unsigned get_size () const { return length * item_size; }
159
160 /* Sink interface. */
161 template <typename T>
162 hb_vector_t& operator << (T&& v) { push (std::forward<T> (v)); return *this; }
163
164 array_t as_array () { return hb_array (arrayZ, length); }
165 c_array_t as_array () const { return hb_array (arrayZ, length); }
166
167 /* Iterator. */
168 typedef c_array_t iter_t;
169 typedef array_t writer_t;
170 iter_t iter () const { return as_array (); }
171 writer_t writer () { return as_array (); }
172 operator iter_t () const { return iter (); }
173 operator writer_t () { return writer (); }
174
175 /* Faster range-based for loop. */
176 Type *begin () const { return arrayZ; }
177 Type *end () const { return arrayZ + length; }
178
179
180 hb_sorted_array_t<Type> as_sorted_array ()
181 { return hb_sorted_array (arrayZ, length); }
182 hb_sorted_array_t<const Type> as_sorted_array () const
183 { return hb_sorted_array (arrayZ, length); }
184
185 template <typename T> explicit operator T * () { return arrayZ; }
186 template <typename T> explicit operator const T * () const { return arrayZ; }
187
188 Type * operator + (unsigned int i) { return arrayZ + i; }
189 const Type * operator + (unsigned int i) const { return arrayZ + i; }
190
191 Type *push ()
192 {
193 if (unlikely (!resize (length + 1)))
194 return &Crap (Type);
195 return std::addressof (arrayZ[length - 1]);
196 }
197 template <typename T,
198 typename T2 = Type,
199 hb_enable_if (!std::is_copy_constructible<T2>::value &&
200 std::is_copy_assignable<T>::value)>
201 Type *push (T&& v)
202 {
203 Type *p = push ();
204 if (p == &Crap (Type))
205 // If push failed to allocate then don't copy v, since this may cause
206 // the created copy to leak memory since we won't have stored a
207 // reference to it.
208 return p;
209 *p = std::forward<T> (v);
210 return p;
211 }
212 template <typename T,
213 typename T2 = Type,
214 hb_enable_if (std::is_copy_constructible<T2>::value)>
215 Type *push (T&& v)
216 {
217 if (unlikely (!alloc (length + 1)))
218 // If push failed to allocate then don't copy v, since this may cause
219 // the created copy to leak memory since we won't have stored a
220 // reference to it.
221 return &Crap (Type);
222
223 /* Emplace. */
224 length++;
225 Type *p = std::addressof (arrayZ[length - 1]);
226 return new (p) Type (std::forward<T> (v));
227 }
228
229 bool in_error () const { return allocated < 0; }
230
231 template <typename T = Type,
232 hb_enable_if (hb_is_trivially_copy_assignable(T))>
233 Type *
234 realloc_vector (unsigned new_allocated)
235 {
236 return (Type *) hb_realloc (arrayZ, new_allocated * sizeof (Type));
237 }
238 template <typename T = Type,
239 hb_enable_if (!hb_is_trivially_copy_assignable(T))>
240 Type *
241 realloc_vector (unsigned new_allocated)
242 {
243 Type *new_array = (Type *) hb_malloc (new_allocated * sizeof (Type));
244 if (likely (new_array))
245 {
246 for (unsigned i = 0; i < length; i++)
247 {
248 new (std::addressof (new_array[i])) Type ();
249 new_array[i] = std::move (arrayZ[i]);
250 arrayZ[i].~Type ();
251 }
252 hb_free (arrayZ);
253 }
254 return new_array;
255 }
256
257 template <typename T = Type,
258 hb_enable_if (hb_is_trivially_constructible(T))>
259 void
260 grow_vector (unsigned size)
261 {
262 memset (arrayZ + length, 0, (size - length) * sizeof (*arrayZ));
263 length = size;
264 }
265 template <typename T = Type,
266 hb_enable_if (!hb_is_trivially_constructible(T))>
267 void
268 grow_vector (unsigned size)
269 {
270 while (length < size)
271 {
272 length++;
273 new (std::addressof (arrayZ[length - 1])) Type ();
274 }
275 }
276
277 template <typename T = Type,
278 hb_enable_if (hb_is_trivially_copyable (T))>
279 void
280 copy_vector (const hb_vector_t &other)
281 {
282 length = other.length;
283 #ifndef HB_OPTIMIZE_SIZE
284 if (sizeof (T) >= sizeof (long long))
285 /* This runs faster because of alignment. */
286 for (unsigned i = 0; i < length; i++)
287 arrayZ[i] = other.arrayZ[i];
288 else
289 #endif
290 hb_memcpy ((void *) arrayZ, (const void *) other.arrayZ, length * item_size);
291 }
292 template <typename T = Type,
293 hb_enable_if (!hb_is_trivially_copyable (T) &&
294 std::is_copy_constructible<T>::value)>
295 void
296 copy_vector (const hb_vector_t &other)
297 {
298 length = 0;
299 while (length < other.length)
300 {
301 length++;
302 new (std::addressof (arrayZ[length - 1])) Type (other.arrayZ[length - 1]);
303 }
304 }
305 template <typename T = Type,
306 hb_enable_if (!hb_is_trivially_copyable (T) &&
307 !std::is_copy_constructible<T>::value &&
308 std::is_default_constructible<T>::value &&
309 std::is_copy_assignable<T>::value)>
310 void
311 copy_vector (const hb_vector_t &other)
312 {
313 length = 0;
314 while (length < other.length)
315 {
316 length++;
317 new (std::addressof (arrayZ[length - 1])) Type ();
318 arrayZ[length - 1] = other.arrayZ[length - 1];
319 }
320 }
321
322 void
323 shrink_vector (unsigned size)
324 {
325 while ((unsigned) length > size)
326 {
327 arrayZ[(unsigned) length - 1].~Type ();
328 length--;
329 }
330 }
331
332 void
333 shift_down_vector (unsigned i)
334 {
335 for (; i < length; i++)
336 arrayZ[i - 1] = std::move (arrayZ[i]);
337 }
338
339 /* Allocate for size but don't adjust length. */
340 bool alloc (unsigned int size)
341 {
342 if (unlikely (in_error ()))
343 return false;
344
345 if (likely (size <= (unsigned) allocated))
346 return true;
347
348 /* Reallocate */
349
350 unsigned int new_allocated = allocated;
351 while (size >= new_allocated)
352 new_allocated += (new_allocated >> 1) + 8;
353
354 Type *new_array = nullptr;
355 bool overflows =
356 (int) in_error () ||
357 (new_allocated < (unsigned) allocated) ||
358 hb_unsigned_mul_overflows (new_allocated, sizeof (Type));
359 if (likely (!overflows))
360 new_array = realloc_vector (new_allocated);
361
362 if (unlikely (!new_array))
363 {
364 allocated = -1;
365 return false;
366 }
367
368 arrayZ = new_array;
369 allocated = new_allocated;
370
371 return true;
372 }
373
374 bool resize (int size_, bool initialize = true)
375 {
376 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
377 if (!alloc (size))
378 return false;
379
380 if (size > length)
381 {
382 if (initialize)
383 grow_vector (size);
384 }
385 else if (size < length)
386 {
387 if (initialize)
388 shrink_vector (size);
389 }
390
391 length = size;
392 return true;
393 }
394
395 Type pop ()
396 {
397 if (!length) return Null (Type);
398 Type v {std::move (arrayZ[length - 1])};
399 arrayZ[length - 1].~Type ();
400 length--;
401 return v;
402 }
403
404 void remove_ordered (unsigned int i)
405 {
406 if (unlikely (i >= length))
407 return;
408 shift_down_vector (i + 1);
409 arrayZ[length - 1].~Type ();
410 length--;
411 }
412
413 template <bool Sorted = sorted,
414 hb_enable_if (!Sorted)>
415 void remove_unordered (unsigned int i)
416 {
417 if (unlikely (i >= length))
418 return;
419 if (i != length - 1)
420 arrayZ[i] = std::move (arrayZ[length - 1]);
421 arrayZ[length - 1].~Type ();
422 length--;
423 }
424
425 void shrink (int size_)
426 {
427 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;
428 if (size >= length)
429 return;
430
431 shrink_vector (size);
432 }
433
434
435 /* Sorting API. */
436 void qsort (int (*cmp)(const void*, const void*) = Type::cmp)
437 { as_array ().qsort (cmp); }
438
439 /* Unsorted search API. */
440 template <typename T>
441 Type *lsearch (const T &x, Type *not_found = nullptr)
442 { return as_array ().lsearch (x, not_found); }
443 template <typename T>
444 const Type *lsearch (const T &x, const Type *not_found = nullptr) const
445 { return as_array ().lsearch (x, not_found); }
446 template <typename T>
447 bool lfind (const T &x, unsigned *pos = nullptr) const
448 { return as_array ().lfind (x, pos); }
449
450 /* Sorted search API. */
451 template <typename T,
452 bool Sorted=sorted, hb_enable_if (Sorted)>
453 Type *bsearch (const T &x, Type *not_found = nullptr)
454 { return as_array ().bsearch (x, not_found); }
455 template <typename T,
456 bool Sorted=sorted, hb_enable_if (Sorted)>
457 const Type *bsearch (const T &x, const Type *not_found = nullptr) const
458 { return as_array ().bsearch (x, not_found); }
459 template <typename T,
460 bool Sorted=sorted, hb_enable_if (Sorted)>
461 bool bfind (const T &x, unsigned int *i = nullptr,
462 hb_not_found_t not_found = HB_NOT_FOUND_DONT_STORE,
463 unsigned int to_store = (unsigned int) -1) const
464 { return as_array ().bfind (x, i, not_found, to_store); }
465 };
466
467 template <typename Type>
468 using hb_sorted_vector_t = hb_vector_t<Type, true>;
469
470 #endif /* HB_VECTOR_HH */