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 #include "hb-set.hh" 33 34 35 /* 36 * hb_hashmap_t 37 */ 38 39 extern HB_INTERNAL const hb_codepoint_t minus_1; 40 41 template <typename K, typename V, 42 bool minus_one = false> 43 struct hb_hashmap_t 44 { 45 static constexpr bool realloc_move = true; 46 hb_hashmap_thb_hashmap_t47 hb_hashmap_t () { init (); } ~hb_hashmap_thb_hashmap_t48 ~hb_hashmap_t () { fini (); } 49 hb_hashmap_thb_hashmap_t50 hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () 51 { 52 if (unlikely (!o.mask)) return; 53 54 if (item_t::is_trivial) 55 { 56 items = (item_t *) hb_malloc (sizeof (item_t) * (o.mask + 1)); 57 if (unlikely (!items)) 58 { 59 successful = false; 60 return; 61 } 62 population = o.population; 63 occupancy = o.occupancy; 64 mask = o.mask; 65 prime = o.prime; 66 max_chain_length = o.max_chain_length; 67 memcpy (items, o.items, sizeof (item_t) * (mask + 1)); 68 return; 69 } 70 71 alloc (o.population); hb_copy (o, *this); 72 } hb_hashmap_thb_hashmap_t73 hb_hashmap_t (hb_hashmap_t&& o) noexcept : hb_hashmap_t () { hb_swap (*this, o); } operator =hb_hashmap_t74 hb_hashmap_t& operator= (const hb_hashmap_t& o) { reset (); alloc (o.population); hb_copy (o, *this); return *this; } operator =hb_hashmap_t75 hb_hashmap_t& operator= (hb_hashmap_t&& o) noexcept { hb_swap (*this, o); return *this; } 76 hb_hashmap_thb_hashmap_t77 hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t () 78 { 79 for (auto&& item : lst) 80 set (item.first, item.second); 81 } 82 template <typename Iterable, 83 hb_requires (hb_is_iterable (Iterable))> hb_hashmap_thb_hashmap_t84 hb_hashmap_t (const Iterable &o) : hb_hashmap_t () 85 { 86 auto iter = hb_iter (o); 87 if (iter.is_random_access_iterator || iter.has_fast_len) 88 alloc (hb_len (iter)); 89 hb_copy (iter, *this); 90 } 91 92 struct item_t 93 { 94 K key; 95 uint32_t is_real_ : 1; 96 uint32_t is_used_ : 1; 97 uint32_t hash : 30; 98 V value; 99 item_thb_hashmap_t::item_t100 item_t () : key (), 101 is_real_ (false), is_used_ (false), 102 hash (0), 103 value () {} 104 105 // Needed for https://github.com/harfbuzz/harfbuzz/issues/4138 get_keyhb_hashmap_t::item_t106 K& get_key () { return key; } get_valuehb_hashmap_t::item_t107 V& get_value () { return value; } 108 is_usedhb_hashmap_t::item_t109 bool is_used () const { return is_used_; } set_usedhb_hashmap_t::item_t110 void set_used (bool is_used) { is_used_ = is_used; } set_realhb_hashmap_t::item_t111 void set_real (bool is_real) { is_real_ = is_real; } is_realhb_hashmap_t::item_t112 bool is_real () const { return is_real_; } 113 114 template <bool v = minus_one, 115 hb_enable_if (v == false)> default_valuehb_hashmap_t::item_t116 static inline const V& default_value () { return Null(V); }; 117 template <bool v = minus_one, 118 hb_enable_if (v == true)> default_valuehb_hashmap_t::item_t119 static inline const V& default_value () 120 { 121 static_assert (hb_is_same (V, hb_codepoint_t), ""); 122 return minus_1; 123 }; 124 operator ==hb_hashmap_t::item_t125 bool operator == (const K &o) const { return hb_deref (key) == hb_deref (o); } operator ==hb_hashmap_t::item_t126 bool operator == (const item_t &o) const { return *this == o.key; } get_pairhb_hashmap_t::item_t127 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } get_pair_refhb_hashmap_t::item_t128 hb_pair_t<const K &, V &> get_pair_ref() { return hb_pair_t<const K &, V &> (key, value); } 129 total_hashhb_hashmap_t::item_t130 uint32_t total_hash () const 131 { return (hash * 31u) + hb_hash (value); } 132 133 static constexpr bool is_trivial = hb_is_trivially_constructible(K) && 134 hb_is_trivially_destructible(K) && 135 hb_is_trivially_constructible(V) && 136 hb_is_trivially_destructible(V); 137 }; 138 139 hb_object_header_t header; 140 bool successful; /* Allocations successful */ 141 unsigned short max_chain_length; 142 unsigned int population; /* Not including tombstones. */ 143 unsigned int occupancy; /* Including tombstones. */ 144 unsigned int mask; 145 unsigned int prime; 146 item_t *items; 147 swap(hb_hashmap_t & a,hb_hashmap_t & b)148 friend void swap (hb_hashmap_t& a, hb_hashmap_t& b) noexcept 149 { 150 if (unlikely (!a.successful || !b.successful)) 151 return; 152 hb_swap (a.max_chain_length, b.max_chain_length); 153 hb_swap (a.population, b.population); 154 hb_swap (a.occupancy, b.occupancy); 155 hb_swap (a.mask, b.mask); 156 hb_swap (a.prime, b.prime); 157 hb_swap (a.items, b.items); 158 } inithb_hashmap_t159 void init () 160 { 161 hb_object_init (this); 162 163 successful = true; 164 max_chain_length = 0; 165 population = occupancy = 0; 166 mask = 0; 167 prime = 0; 168 items = nullptr; 169 } finihb_hashmap_t170 void fini () 171 { 172 hb_object_fini (this); 173 174 if (likely (items)) 175 { 176 unsigned size = mask + 1; 177 if (!item_t::is_trivial) 178 for (unsigned i = 0; i < size; i++) 179 items[i].~item_t (); 180 hb_free (items); 181 items = nullptr; 182 } 183 population = occupancy = 0; 184 } 185 resethb_hashmap_t186 void reset () 187 { 188 successful = true; 189 clear (); 190 } 191 in_errorhb_hashmap_t192 bool in_error () const { return !successful; } 193 allochb_hashmap_t194 bool alloc (unsigned new_population = 0) 195 { 196 if (unlikely (!successful)) return false; 197 198 if (new_population != 0 && (new_population + new_population / 2) < mask) return true; 199 200 unsigned int power = hb_bit_storage (hb_max ((unsigned) population, new_population) * 2 + 8); 201 unsigned int new_size = 1u << power; 202 item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t)); 203 if (unlikely (!new_items)) 204 { 205 successful = false; 206 return false; 207 } 208 if (!item_t::is_trivial) 209 for (auto &_ : hb_iter (new_items, new_size)) 210 new (&_) item_t (); 211 else 212 hb_memset (new_items, 0, (size_t) new_size * sizeof (item_t)); 213 214 unsigned int old_size = size (); 215 item_t *old_items = items; 216 217 /* Switch to new, empty, array. */ 218 population = occupancy = 0; 219 mask = new_size - 1; 220 prime = prime_for (power); 221 max_chain_length = power * 2; 222 items = new_items; 223 224 /* Insert back old items. */ 225 for (unsigned int i = 0; i < old_size; i++) 226 { 227 if (old_items[i].is_real ()) 228 { 229 set_with_hash (std::move (old_items[i].key), 230 old_items[i].hash, 231 std::move (old_items[i].value)); 232 } 233 } 234 if (!item_t::is_trivial) 235 for (unsigned int i = 0; i < old_size; i++) 236 old_items[i].~item_t (); 237 238 hb_free (old_items); 239 240 return true; 241 } 242 243 template <typename KK, typename VV> set_with_hashhb_hashmap_t244 bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool overwrite = true) 245 { 246 if (unlikely (!successful)) return false; 247 if (unlikely ((occupancy + occupancy / 2) >= mask && !alloc ())) return false; 248 249 hash &= 0x3FFFFFFF; // We only store lower 30bit of hash 250 unsigned int tombstone = (unsigned int) -1; 251 unsigned int i = hash % prime; 252 unsigned length = 0; 253 unsigned step = 0; 254 while (items[i].is_used ()) 255 { 256 if ((std::is_integral<K>::value || items[i].hash == hash) && 257 items[i] == key) 258 { 259 if (!overwrite) 260 return false; 261 else 262 break; 263 } 264 if (!items[i].is_real () && tombstone == (unsigned) -1) 265 tombstone = i; 266 i = (i + ++step) & mask; 267 length++; 268 } 269 270 item_t &item = items[tombstone == (unsigned) -1 ? i : tombstone]; 271 272 if (item.is_used ()) 273 { 274 occupancy--; 275 population -= item.is_real (); 276 } 277 278 item.key = std::forward<KK> (key); 279 item.value = std::forward<VV> (value); 280 item.hash = hash; 281 item.set_used (true); 282 item.set_real (true); 283 284 occupancy++; 285 population++; 286 287 if (unlikely (length > max_chain_length) && occupancy * 8 > mask) 288 alloc (mask - 8); // This ensures we jump to next larger size 289 290 return true; 291 } 292 293 template <typename VV> sethb_hashmap_t294 bool set (const K &key, VV&& value, bool overwrite = true) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value), overwrite); } 295 template <typename VV> sethb_hashmap_t296 bool set (K &&key, VV&& value, bool overwrite = true) 297 { 298 uint32_t hash = hb_hash (key); 299 return set_with_hash (std::move (key), hash, std::forward<VV> (value), overwrite); 300 } addhb_hashmap_t301 bool add (const K &key) 302 { 303 uint32_t hash = hb_hash (key); 304 return set_with_hash (key, hash, item_t::default_value ()); 305 } 306 get_with_hashhb_hashmap_t307 const V& get_with_hash (const K &key, uint32_t hash) const 308 { 309 if (!items) return item_t::default_value (); 310 auto *item = fetch_item (key, hash); 311 if (item) 312 return item->value; 313 return item_t::default_value (); 314 } gethb_hashmap_t315 const V& get (const K &key) const 316 { 317 if (!items) return item_t::default_value (); 318 return get_with_hash (key, hb_hash (key)); 319 } 320 delhb_hashmap_t321 void del (const K &key) 322 { 323 if (!items) return; 324 auto *item = fetch_item (key, hb_hash (key)); 325 if (item) 326 { 327 item->set_real (false); 328 population--; 329 } 330 } 331 332 /* Has interface. */ operator []hb_hashmap_t333 const V& operator [] (K k) const { return get (k); } 334 template <typename VV=V> hashb_hashmap_t335 bool has (const K &key, VV **vp = nullptr) const 336 { 337 if (!items) return false; 338 auto *item = fetch_item (key, hb_hash (key)); 339 if (item) 340 { 341 if (vp) *vp = std::addressof (item->value); 342 return true; 343 } 344 return false; 345 } fetch_itemhb_hashmap_t346 item_t *fetch_item (const K &key, uint32_t hash) const 347 { 348 hash &= 0x3FFFFFFF; // We only store lower 30bit of hash 349 unsigned int i = hash % prime; 350 unsigned step = 0; 351 while (items[i].is_used ()) 352 { 353 if ((std::is_integral<K>::value || items[i].hash == hash) && 354 items[i] == key) 355 { 356 if (items[i].is_real ()) 357 return &items[i]; 358 else 359 return nullptr; 360 } 361 i = (i + ++step) & mask; 362 } 363 return nullptr; 364 } 365 /* Projection. */ operator ()hb_hashmap_t366 const V& operator () (K k) const { return get (k); } 367 sizehb_hashmap_t368 unsigned size () const { return mask ? mask + 1 : 0; } 369 clearhb_hashmap_t370 void clear () 371 { 372 if (unlikely (!successful)) return; 373 374 for (auto &_ : hb_iter (items, size ())) 375 { 376 /* Reconstruct items. */ 377 _.~item_t (); 378 new (&_) item_t (); 379 } 380 381 population = occupancy = 0; 382 } 383 is_emptyhb_hashmap_t384 bool is_empty () const { return population == 0; } operator boolhb_hashmap_t385 explicit operator bool () const { return !is_empty (); } 386 hashhb_hashmap_t387 uint32_t hash () const 388 { 389 return 390 + iter_items () 391 | hb_reduce ([] (uint32_t h, const item_t &_) { return h ^ _.total_hash (); }, (uint32_t) 0u) 392 ; 393 } 394 is_equalhb_hashmap_t395 bool is_equal (const hb_hashmap_t &other) const 396 { 397 if (population != other.population) return false; 398 399 for (auto pair : iter ()) 400 if (other.get (pair.first) != pair.second) 401 return false; 402 403 return true; 404 } operator ==hb_hashmap_t405 bool operator == (const hb_hashmap_t &other) const { return is_equal (other); } operator !=hb_hashmap_t406 bool operator != (const hb_hashmap_t &other) const { return !is_equal (other); } 407 get_populationhb_hashmap_t408 unsigned int get_population () const { return population; } 409 updatehb_hashmap_t410 void update (const hb_hashmap_t &other) 411 { 412 if (unlikely (!successful)) return; 413 414 hb_copy (other, *this); 415 } 416 417 /* 418 * Iterator 419 */ 420 iter_itemshb_hashmap_t421 auto iter_items () const HB_AUTO_RETURN 422 ( 423 + hb_iter (items, this->size ()) 424 | hb_filter (&item_t::is_real) 425 ) 426 auto iter_ref () const HB_AUTO_RETURN 427 ( 428 + this->iter_items () 429 | hb_map (&item_t::get_pair_ref) 430 ) 431 auto iter () const HB_AUTO_RETURN 432 ( 433 + this->iter_items () 434 | hb_map (&item_t::get_pair) 435 ) 436 auto keys_ref () const HB_AUTO_RETURN 437 ( 438 + this->iter_items () 439 | hb_map (&item_t::get_key) 440 ) 441 auto keys () const HB_AUTO_RETURN 442 ( 443 + this->keys_ref () 444 | hb_map (hb_ridentity) 445 ) 446 auto values_ref () const HB_AUTO_RETURN 447 ( 448 + this->iter_items () 449 | hb_map (&item_t::get_value) 450 ) 451 auto values () const HB_AUTO_RETURN 452 ( 453 + this->values_ref () 454 | hb_map (hb_ridentity) 455 ) 456 457 /* C iterator. */ 458 bool next (int *idx, 459 K *key, 460 V *value) const 461 { 462 unsigned i = (unsigned) (*idx + 1); 463 464 unsigned count = size (); 465 while (i < count && !items[i].is_real ()) 466 i++; 467 468 if (i >= count) 469 { 470 *idx = -1; 471 return false; 472 } 473 474 *key = items[i].key; 475 *value = items[i].value; 476 477 *idx = (signed) i; 478 return true; 479 } 480 481 /* Sink interface. */ operator <<hb_hashmap_t482 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v) 483 { set (v.first, v.second); return *this; } operator <<hb_hashmap_t484 hb_hashmap_t& operator << (const hb_pair_t<K, V&&>& v) 485 { set (v.first, std::move (v.second)); return *this; } operator <<hb_hashmap_t486 hb_hashmap_t& operator << (const hb_pair_t<K&&, V>& v) 487 { set (std::move (v.first), v.second); return *this; } operator <<hb_hashmap_t488 hb_hashmap_t& operator << (const hb_pair_t<K&&, V&&>& v) 489 { set (std::move (v.first), std::move (v.second)); return *this; } 490 prime_forhb_hashmap_t491 static unsigned int prime_for (unsigned int shift) 492 { 493 /* Following comment and table copied from glib. */ 494 /* Each table size has an associated prime modulo (the first prime 495 * lower than the table size) used to find the initial bucket. Probing 496 * then works modulo 2^n. The prime modulo is necessary to get a 497 * good distribution with poor hash functions. 498 */ 499 /* Not declaring static to make all kinds of compilers happy... */ 500 /*static*/ const unsigned int prime_mod [32] = 501 { 502 1, /* For 1 << 0 */ 503 2, 504 3, 505 7, 506 13, 507 31, 508 61, 509 127, 510 251, 511 509, 512 1021, 513 2039, 514 4093, 515 8191, 516 16381, 517 32749, 518 65521, /* For 1 << 16 */ 519 131071, 520 262139, 521 524287, 522 1048573, 523 2097143, 524 4194301, 525 8388593, 526 16777213, 527 33554393, 528 67108859, 529 134217689, 530 268435399, 531 536870909, 532 1073741789, 533 2147483647 /* For 1 << 31 */ 534 }; 535 536 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 537 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 538 539 return prime_mod[shift]; 540 } 541 }; 542 543 /* 544 * hb_map_t 545 */ 546 547 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 548 hb_codepoint_t, 549 true> 550 { 551 using hashmap = hb_hashmap_t<hb_codepoint_t, 552 hb_codepoint_t, 553 true>; 554 555 ~hb_map_t () = default; hb_map_thb_map_t556 hb_map_t () : hashmap () {} hb_map_thb_map_t557 hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {} hb_map_thb_map_t558 hb_map_t (hb_map_t &&o) noexcept : hashmap (std::move ((hashmap &) o)) {} 559 hb_map_t& operator= (const hb_map_t&) = default; 560 hb_map_t& operator= (hb_map_t&&) = default; hb_map_thb_map_t561 hb_map_t (std::initializer_list<hb_codepoint_pair_t> lst) : hashmap (lst) {} 562 template <typename Iterable, 563 hb_requires (hb_is_iterable (Iterable))> hb_map_thb_map_t564 hb_map_t (const Iterable &o) : hashmap (o) {} 565 }; 566 567 568 #endif /* HB_MAP_HH */ 569