Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/hb-map.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_MAP_HH
28 #define HB_MAP_HH
29
30 #include "hb.hh"
31
32
33 /*
34 * hb_hashmap_t
35 */
36
37 extern HB_INTERNAL const hb_codepoint_t minus_1;
38
39 template <typename K, typename V,
40 bool minus_one = false>
41 struct hb_hashmap_t
42 {
43 hb_hashmap_t () { init (); }
44 ~hb_hashmap_t () { fini (); }
45
46 hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { resize (o.population); hb_copy (o, *this); }
47 hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); }
48 hb_hashmap_t& operator= (const hb_hashmap_t& o) { reset (); resize (o.population); hb_copy (o, *this); return *this; }
49 hb_hashmap_t& operator= (hb_hashmap_t&& o) { hb_swap (*this, o); return *this; }
50
51 hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t ()
52 {
53 for (auto&& item : lst)
54 set (item.first, item.second);
55 }
56 template <typename Iterable,
57 hb_requires (hb_is_iterable (Iterable))>
58 hb_hashmap_t (const Iterable &o) : hb_hashmap_t ()
59 {
60 auto iter = hb_iter (o);
61 if (iter.is_random_access_iterator)
62 resize (hb_len (iter));
63 hb_copy (iter, *this);
64 }
65
66 struct item_t
67 {
68 K key;
69 uint32_t hash : 30;
70 uint32_t is_used_ : 1;
71 uint32_t is_tombstone_ : 1;
72 V value;
73
74 item_t () : key (),
75 hash (0),
76 is_used_ (false), is_tombstone_ (false),
77 value () {}
78
79 bool is_used () const { return is_used_; }
80 void set_used (bool is_used) { is_used_ = is_used; }
81 bool is_tombstone () const { return is_tombstone_; }
82 void set_tombstone (bool is_tombstone) { is_tombstone_ = is_tombstone; }
83 bool is_real () const { return is_used_ && !is_tombstone_; }
84
85 template <bool v = minus_one,
86 hb_enable_if (v == false)>
87 static inline const V& default_value () { return Null(V); };
88 template <bool v = minus_one,
89 hb_enable_if (v == true)>
90 static inline const V& default_value ()
91 {
92 static_assert (hb_is_same (V, hb_codepoint_t), "");
93 return minus_1;
94 };
95
96 bool operator == (const K &o) const { return hb_deref (key) == hb_deref (o); }
97 bool operator == (const item_t &o) const { return *this == o.key; }
98 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); }
99 hb_pair_t<const K &, const V &> get_pair_ref() const { return hb_pair_t<const K &, const V &> (key, value); }
100
101 uint32_t total_hash () const
102 { return (hash * 31) + hb_hash (value); }
103 };
104
105 hb_object_header_t header;
106 unsigned int successful : 1; /* Allocations successful */
107 unsigned int population : 31; /* Not including tombstones. */
108 unsigned int occupancy; /* Including tombstones. */
109 unsigned int mask;
110 unsigned int prime;
111 item_t *items;
112
113 friend void swap (hb_hashmap_t& a, hb_hashmap_t& b)
114 {
115 if (unlikely (!a.successful || !b.successful))
116 return;
117 unsigned tmp = a.population;
118 a.population = b.population;
119 b.population = tmp;
120 //hb_swap (a.population, b.population);
121 hb_swap (a.occupancy, b.occupancy);
122 hb_swap (a.mask, b.mask);
123 hb_swap (a.prime, b.prime);
124 hb_swap (a.items, b.items);
125 }
126 void init ()
127 {
128 hb_object_init (this);
129
130 successful = true;
131 population = occupancy = 0;
132 mask = 0;
133 prime = 0;
134 items = nullptr;
135 }
136 void fini ()
137 {
138 hb_object_fini (this);
139
140 if (likely (items)) {
141 unsigned size = mask + 1;
142 for (unsigned i = 0; i < size; i++)
143 items[i].~item_t ();
144 hb_free (items);
145 items = nullptr;
146 }
147 population = occupancy = 0;
148 }
149
150 void reset ()
151 {
152 successful = true;
153 clear ();
154 }
155
156 bool in_error () const { return !successful; }
157
158 bool resize (unsigned new_population = 0)
159 {
160 if (unlikely (!successful)) return false;
161
162 if (new_population != 0 && (new_population + new_population / 2) < mask) return true;
163
164 unsigned int power = hb_bit_storage (hb_max ((unsigned) population, new_population) * 2 + 8);
165 unsigned int new_size = 1u << power;
166 item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t));
167 if (unlikely (!new_items))
168 {
169 successful = false;
170 return false;
171 }
172 for (auto &_ : hb_iter (new_items, new_size))
173 new (&_) item_t ();
174
175 unsigned int old_size = size ();
176 item_t *old_items = items;
177
178 /* Switch to new, empty, array. */
179 population = occupancy = 0;
180 mask = new_size - 1;
181 prime = prime_for (power);
182 items = new_items;
183
184 /* Insert back old items. */
185 for (unsigned int i = 0; i < old_size; i++)
186 {
187 if (old_items[i].is_real ())
188 {
189 set_with_hash (std::move (old_items[i].key),
190 old_items[i].hash,
191 std::move (old_items[i].value));
192 }
193 old_items[i].~item_t ();
194 }
195
196 hb_free (old_items);
197
198 return true;
199 }
200
201 template <typename KK, typename VV>
202 bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool is_delete=false)
203 {
204 if (unlikely (!successful)) return false;
205 if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false;
206 item_t &item = item_for_hash (key, hash);
207
208 if (is_delete && !(item == key))
209 return true; /* Trying to delete non-existent key. */
210
211 if (item.is_used ())
212 {
213 occupancy--;
214 if (!item.is_tombstone ())
215 population--;
216 }
217
218 item.key = std::forward<KK> (key);
219 item.value = std::forward<VV> (value);
220 item.hash = hash;
221 item.set_used (true);
222 item.set_tombstone (is_delete);
223
224 occupancy++;
225 if (!is_delete)
226 population++;
227
228 return true;
229 }
230
231 template <typename VV>
232 bool set (const K &key, VV&& value) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value)); }
233 template <typename VV>
234 bool set (K &&key, VV&& value) { return set_with_hash (std::move (key), hb_hash (key), std::forward<VV> (value)); }
235
236 const V& get_with_hash (const K &key, uint32_t hash) const
237 {
238 if (unlikely (!items)) return item_t::default_value ();
239 auto &item = item_for_hash (key, hash);
240 return item.is_real () && item == key ? item.value : item_t::default_value ();
241 }
242 const V& get (const K &key) const
243 {
244 if (unlikely (!items)) return item_t::default_value ();
245 return get_with_hash (key, hb_hash (key));
246 }
247
248 void del (const K &key) { set_with_hash (key, hb_hash (key), item_t::default_value (), true); }
249
250 /* Has interface. */
251 const V& operator [] (K k) const { return get (k); }
252 template <typename VV=V>
253 bool has (K key, VV **vp = nullptr) const
254 {
255 if (unlikely (!items))
256 return false;
257 auto &item = item_for_hash (key, hb_hash (key));
258 if (item.is_real () && item == key)
259 {
260 if (vp) *vp = std::addressof (item.value);
261 return true;
262 }
263 else
264 return false;
265 }
266 /* Projection. */
267 V operator () (K k) const { return get (k); }
268
269 unsigned size () const { return mask ? mask + 1 : 0; }
270
271 void clear ()
272 {
273 if (unlikely (!successful)) return;
274
275 for (auto &_ : hb_iter (items, size ()))
276 {
277 /* Reconstruct items. */
278 _.~item_t ();
279 new (&_) item_t ();
280 }
281
282 population = occupancy = 0;
283 }
284
285 bool is_empty () const { return population == 0; }
286 explicit operator bool () const { return !is_empty (); }
287
288 uint32_t hash () const
289 {
290 return
291 + iter_items ()
292 | hb_reduce ([] (uint32_t h, const item_t &_) { return h ^ _.total_hash (); }, (uint32_t) 0u)
293 ;
294 }
295
296 bool is_equal (const hb_hashmap_t &other) const
297 {
298 if (population != other.population) return false;
299
300 for (auto pair : iter ())
301 if (other.get (pair.first) != pair.second)
302 return false;
303
304 return true;
305 }
306 bool operator == (const hb_hashmap_t &other) const { return is_equal (other); }
307 bool operator != (const hb_hashmap_t &other) const { return !is_equal (other); }
308
309 unsigned int get_population () const { return population; }
310
311 /*
312 * Iterator
313 */
314
315 auto iter_items () const HB_AUTO_RETURN
316 (
317 + hb_iter (items, size ())
318 | hb_filter (&item_t::is_real)
319 )
320 auto iter_ref () const HB_AUTO_RETURN
321 (
322 + iter_items ()
323 | hb_map (&item_t::get_pair_ref)
324 )
325 auto iter () const HB_AUTO_RETURN
326 (
327 + iter_items ()
328 | hb_map (&item_t::get_pair)
329 )
330 auto keys_ref () const HB_AUTO_RETURN
331 (
332 + iter_items ()
333 | hb_map (&item_t::key)
334 )
335 auto keys () const HB_AUTO_RETURN
336 (
337 + keys_ref ()
338 | hb_map (hb_ridentity)
339 )
340 auto values_ref () const HB_AUTO_RETURN
341 (
342 + iter_items ()
343 | hb_map (&item_t::value)
344 )
345 auto values () const HB_AUTO_RETURN
346 (
347 + values_ref ()
348 | hb_map (hb_ridentity)
349 )
350
351 /* Sink interface. */
352 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v)
353 { set (v.first, v.second); return *this; }
354 hb_hashmap_t& operator << (const hb_pair_t<K, V&&>& v)
355 { set (v.first, std::move (v.second)); return *this; }
356 hb_hashmap_t& operator << (const hb_pair_t<K&&, V>& v)
357 { set (std::move (v.first), v.second); return *this; }
358 hb_hashmap_t& operator << (const hb_pair_t<K&&, V&&>& v)
359 { set (std::move (v.first), std::move (v.second)); return *this; }
360
361 item_t& item_for_hash (const K &key, uint32_t hash) const
362 {
363 hash &= 0x3FFFFFFF; // We only store lower 30bit of hash
364 unsigned int i = hash % prime;
365 unsigned int step = 0;
366 unsigned int tombstone = (unsigned) -1;
367 while (items[i].is_used ())
368 {
369 if (items[i].hash == hash && items[i] == key)
370 return items[i];
371 if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
372 tombstone = i;
373 i = (i + ++step) & mask;
374 }
375 return items[tombstone == (unsigned) -1 ? i : tombstone];
376 }
377
378 static unsigned int prime_for (unsigned int shift)
379 {
380 /* Following comment and table copied from glib. */
381 /* Each table size has an associated prime modulo (the first prime
382 * lower than the table size) used to find the initial bucket. Probing
383 * then works modulo 2^n. The prime modulo is necessary to get a
384 * good distribution with poor hash functions.
385 */
386 /* Not declaring static to make all kinds of compilers happy... */
387 /*static*/ const unsigned int prime_mod [32] =
388 {
389 1, /* For 1 << 0 */
390 2,
391 3,
392 7,
393 13,
394 31,
395 61,
396 127,
397 251,
398 509,
399 1021,
400 2039,
401 4093,
402 8191,
403 16381,
404 32749,
405 65521, /* For 1 << 16 */
406 131071,
407 262139,
408 524287,
409 1048573,
410 2097143,
411 4194301,
412 8388593,
413 16777213,
414 33554393,
415 67108859,
416 134217689,
417 268435399,
418 536870909,
419 1073741789,
420 2147483647 /* For 1 << 31 */
421 };
422
423 if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
424 return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
425
426 return prime_mod[shift];
427 }
428 };
429
430 /*
431 * hb_map_t
432 */
433
434 struct hb_map_t : hb_hashmap_t<hb_codepoint_t,
435 hb_codepoint_t,
436 true>
437 {
438 using hashmap = hb_hashmap_t<hb_codepoint_t,
439 hb_codepoint_t,
440 true>;
441
442 ~hb_map_t () = default;
443 hb_map_t () : hashmap () {}
444 hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {}
445 hb_map_t (hb_map_t &&o) : hashmap (std::move ((hashmap &) o)) {}
446 hb_map_t& operator= (const hb_map_t&) = default;
447 hb_map_t& operator= (hb_map_t&&) = default;
448 hb_map_t (std::initializer_list<hb_pair_t<hb_codepoint_t, hb_codepoint_t>> lst) : hashmap (lst) {}
449 template <typename Iterable,
450 hb_requires (hb_is_iterable (Iterable))>
451 hb_map_t (const Iterable &o) : hashmap (o) {}
452 };
453
454 template <typename K, typename V>
455 static inline
456 hb_hashmap_t<K, V>* hb_hashmap_create ()
457 {
458 using hashmap = hb_hashmap_t<K, V>;
459 hashmap* map;
460 if (!(map = hb_object_create<hashmap> ()))
461 return nullptr;
462
463 return map;
464 }
465
466 template <typename K, typename V>
467 static inline
468 void hb_hashmap_destroy (hb_hashmap_t<K, V>* map)
469 {
470 if (!hb_object_destroy (map))
471 return;
472
473 hb_free (map);
474 }
475
476 namespace hb {
477
478 template <typename K, typename V>
479 struct vtable<hb_hashmap_t<K, V>>
480 {
481 static constexpr auto destroy = hb_hashmap_destroy<K,V>;
482 };
483
484 }
485
486
487 #endif /* HB_MAP_HH */