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 {
hb_hashmap_thb_hashmap_t43 hb_hashmap_t () { init (); }
~hb_hashmap_thb_hashmap_t44 ~hb_hashmap_t () { fini (); }
45
hb_hashmap_thb_hashmap_t46 hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { resize (o.population); hb_copy (o, *this); }
hb_hashmap_thb_hashmap_t47 hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); }
operator =hb_hashmap_t48 hb_hashmap_t& operator= (const hb_hashmap_t& o) { reset (); resize (o.population); hb_copy (o, *this); return *this; }
operator =hb_hashmap_t49 hb_hashmap_t& operator= (hb_hashmap_t&& o) { hb_swap (*this, o); return *this; }
50
hb_hashmap_thb_hashmap_t51 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))>
hb_hashmap_thb_hashmap_t58 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
item_thb_hashmap_t::item_t74 item_t () : key (),
75 hash (0),
76 is_used_ (false), is_tombstone_ (false),
77 value () {}
78
is_usedhb_hashmap_t::item_t79 bool is_used () const { return is_used_; }
set_usedhb_hashmap_t::item_t80 void set_used (bool is_used) { is_used_ = is_used; }
is_tombstonehb_hashmap_t::item_t81 bool is_tombstone () const { return is_tombstone_; }
set_tombstonehb_hashmap_t::item_t82 void set_tombstone (bool is_tombstone) { is_tombstone_ = is_tombstone; }
is_realhb_hashmap_t::item_t83 bool is_real () const { return is_used_ && !is_tombstone_; }
84
85 template <bool v = minus_one,
86 hb_enable_if (v == false)>
default_valuehb_hashmap_t::item_t87 static inline const V& default_value () { return Null(V); };
88 template <bool v = minus_one,
89 hb_enable_if (v == true)>
default_valuehb_hashmap_t::item_t90 static inline const V& default_value ()
91 {
92 static_assert (hb_is_same (V, hb_codepoint_t), "");
93 return minus_1;
94 };
95
operator ==hb_hashmap_t::item_t96 bool operator == (const K &o) const { return hb_deref (key) == hb_deref (o); }
operator ==hb_hashmap_t::item_t97 bool operator == (const item_t &o) const { return *this == o.key; }
get_pairhb_hashmap_t::item_t98 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); }
get_pair_refhb_hashmap_t::item_t99 hb_pair_t<const K &, const V &> get_pair_ref() const { return hb_pair_t<const K &, const V &> (key, value); }
100
total_hashhb_hashmap_t::item_t101 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
swap(hb_hashmap_t & a,hb_hashmap_t & b)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 }
inithb_hashmap_t126 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 }
finihb_hashmap_t136 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
resethb_hashmap_t150 void reset ()
151 {
152 successful = true;
153 clear ();
154 }
155
in_errorhb_hashmap_t156 bool in_error () const { return !successful; }
157
resizehb_hashmap_t158 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>
set_with_hashhb_hashmap_t202 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>
sethb_hashmap_t232 bool set (const K &key, VV&& value) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value)); }
233 template <typename VV>
sethb_hashmap_t234 bool set (K &&key, VV&& value) { return set_with_hash (std::move (key), hb_hash (key), std::forward<VV> (value)); }
235
get_with_hashhb_hashmap_t236 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 }
gethb_hashmap_t242 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
delhb_hashmap_t248 void del (const K &key) { set_with_hash (key, hb_hash (key), item_t::default_value (), true); }
249
250 /* Has interface. */
operator []hb_hashmap_t251 const V& operator [] (K k) const { return get (k); }
252 template <typename VV=V>
hashb_hashmap_t253 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. */
operator ()hb_hashmap_t267 V operator () (K k) const { return get (k); }
268
sizehb_hashmap_t269 unsigned size () const { return mask ? mask + 1 : 0; }
270
clearhb_hashmap_t271 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
is_emptyhb_hashmap_t285 bool is_empty () const { return population == 0; }
operator boolhb_hashmap_t286 explicit operator bool () const { return !is_empty (); }
287
hashhb_hashmap_t288 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
is_equalhb_hashmap_t296 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 }
operator ==hb_hashmap_t306 bool operator == (const hb_hashmap_t &other) const { return is_equal (other); }
operator !=hb_hashmap_t307 bool operator != (const hb_hashmap_t &other) const { return !is_equal (other); }
308
get_populationhb_hashmap_t309 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; }
operator <<hb_hashmap_t354 hb_hashmap_t& operator << (const hb_pair_t<K, V&&>& v)
355 { set (v.first, std::move (v.second)); return *this; }
operator <<hb_hashmap_t356 hb_hashmap_t& operator << (const hb_pair_t<K&&, V>& v)
357 { set (std::move (v.first), v.second); return *this; }
operator <<hb_hashmap_t358 hb_hashmap_t& operator << (const hb_pair_t<K&&, V&&>& v)
359 { set (std::move (v.first), std::move (v.second)); return *this; }
360
item_for_hashhb_hashmap_t361 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
prime_forhb_hashmap_t378 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;
hb_map_thb_map_t443 hb_map_t () : hashmap () {}
hb_map_thb_map_t444 hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {}
hb_map_thb_map_t445 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;
hb_map_thb_map_t448 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))>
hb_map_thb_map_t451 hb_map_t (const Iterable &o) : hashmap (o) {}
452 };
453
454 template <typename K, typename V>
455 static inline
hb_hashmap_create()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
hb_hashmap_destroy(hb_hashmap_t<K,V> * map)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 */
488