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 { hb_hashmap_thb_hashmap_t45 hb_hashmap_t () { init (); } ~hb_hashmap_thb_hashmap_t46 ~hb_hashmap_t () { fini (); } 47 hb_hashmap_thb_hashmap_t48 hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t () { alloc (o.population); hb_copy (o, *this); } hb_hashmap_thb_hashmap_t49 hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); } operator =hb_hashmap_t50 hb_hashmap_t& operator= (const hb_hashmap_t& o) { reset (); alloc (o.population); hb_copy (o, *this); return *this; } operator =hb_hashmap_t51 hb_hashmap_t& operator= (hb_hashmap_t&& o) { hb_swap (*this, o); return *this; } 52 hb_hashmap_thb_hashmap_t53 hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t () 54 { 55 for (auto&& item : lst) 56 set (item.first, item.second); 57 } 58 template <typename Iterable, 59 hb_requires (hb_is_iterable (Iterable))> hb_hashmap_thb_hashmap_t60 hb_hashmap_t (const Iterable &o) : hb_hashmap_t () 61 { 62 auto iter = hb_iter (o); 63 if (iter.is_random_access_iterator || iter.has_fast_len) 64 alloc (hb_len (iter)); 65 hb_copy (iter, *this); 66 } 67 68 struct item_t 69 { 70 K key; 71 uint32_t is_real_ : 1; 72 uint32_t is_used_ : 1; 73 uint32_t hash : 30; 74 V value; 75 item_thb_hashmap_t::item_t76 item_t () : key (), 77 is_real_ (false), is_used_ (false), 78 hash (0), 79 value () {} 80 81 // Needed for https://github.com/harfbuzz/harfbuzz/issues/4138 get_keyhb_hashmap_t::item_t82 K& get_key () { return key; } get_valuehb_hashmap_t::item_t83 V& get_value () { return value; } 84 is_usedhb_hashmap_t::item_t85 bool is_used () const { return is_used_; } set_usedhb_hashmap_t::item_t86 void set_used (bool is_used) { is_used_ = is_used; } set_realhb_hashmap_t::item_t87 void set_real (bool is_real) { is_real_ = is_real; } is_realhb_hashmap_t::item_t88 bool is_real () const { return is_real_; } 89 90 template <bool v = minus_one, 91 hb_enable_if (v == false)> default_valuehb_hashmap_t::item_t92 static inline const V& default_value () { return Null(V); }; 93 template <bool v = minus_one, 94 hb_enable_if (v == true)> default_valuehb_hashmap_t::item_t95 static inline const V& default_value () 96 { 97 static_assert (hb_is_same (V, hb_codepoint_t), ""); 98 return minus_1; 99 }; 100 operator ==hb_hashmap_t::item_t101 bool operator == (const K &o) const { return hb_deref (key) == hb_deref (o); } operator ==hb_hashmap_t::item_t102 bool operator == (const item_t &o) const { return *this == o.key; } get_pairhb_hashmap_t::item_t103 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } get_pair_refhb_hashmap_t::item_t104 hb_pair_t<const K &, V &> get_pair_ref() { return hb_pair_t<const K &, V &> (key, value); } 105 total_hashhb_hashmap_t::item_t106 uint32_t total_hash () const 107 { return (hash * 31u) + hb_hash (value); } 108 109 static constexpr bool is_trivial = hb_is_trivially_constructible(K) && 110 hb_is_trivially_destructible(K) && 111 hb_is_trivially_constructible(V) && 112 hb_is_trivially_destructible(V); 113 }; 114 115 hb_object_header_t header; 116 unsigned int successful : 1; /* Allocations successful */ 117 unsigned int population : 31; /* Not including tombstones. */ 118 unsigned int occupancy; /* Including tombstones. */ 119 unsigned int mask; 120 unsigned int prime; 121 unsigned int max_chain_length; 122 item_t *items; 123 swap(hb_hashmap_t & a,hb_hashmap_t & b)124 friend void swap (hb_hashmap_t& a, hb_hashmap_t& b) 125 { 126 if (unlikely (!a.successful || !b.successful)) 127 return; 128 unsigned tmp = a.population; 129 a.population = b.population; 130 b.population = tmp; 131 //hb_swap (a.population, b.population); 132 hb_swap (a.occupancy, b.occupancy); 133 hb_swap (a.mask, b.mask); 134 hb_swap (a.prime, b.prime); 135 hb_swap (a.max_chain_length, b.max_chain_length); 136 hb_swap (a.items, b.items); 137 } inithb_hashmap_t138 void init () 139 { 140 hb_object_init (this); 141 142 successful = true; 143 population = occupancy = 0; 144 mask = 0; 145 prime = 0; 146 max_chain_length = 0; 147 items = nullptr; 148 } finihb_hashmap_t149 void fini () 150 { 151 hb_object_fini (this); 152 153 if (likely (items)) 154 { 155 unsigned size = mask + 1; 156 if (!item_t::is_trivial) 157 for (unsigned i = 0; i < size; i++) 158 items[i].~item_t (); 159 hb_free (items); 160 items = nullptr; 161 } 162 population = occupancy = 0; 163 } 164 resethb_hashmap_t165 void reset () 166 { 167 successful = true; 168 clear (); 169 } 170 in_errorhb_hashmap_t171 bool in_error () const { return !successful; } 172 allochb_hashmap_t173 bool alloc (unsigned new_population = 0) 174 { 175 if (unlikely (!successful)) return false; 176 177 if (new_population != 0 && (new_population + new_population / 2) < mask) return true; 178 179 unsigned int power = hb_bit_storage (hb_max ((unsigned) population, new_population) * 2 + 8); 180 unsigned int new_size = 1u << power; 181 item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t)); 182 if (unlikely (!new_items)) 183 { 184 successful = false; 185 return false; 186 } 187 if (!item_t::is_trivial) 188 for (auto &_ : hb_iter (new_items, new_size)) 189 new (&_) item_t (); 190 else 191 hb_memset (new_items, 0, (size_t) new_size * sizeof (item_t)); 192 193 unsigned int old_size = size (); 194 item_t *old_items = items; 195 196 /* Switch to new, empty, array. */ 197 population = occupancy = 0; 198 mask = new_size - 1; 199 prime = prime_for (power); 200 max_chain_length = power * 2; 201 items = new_items; 202 203 /* Insert back old items. */ 204 for (unsigned int i = 0; i < old_size; i++) 205 { 206 if (old_items[i].is_real ()) 207 { 208 set_with_hash (std::move (old_items[i].key), 209 old_items[i].hash, 210 std::move (old_items[i].value)); 211 } 212 if (!item_t::is_trivial) 213 old_items[i].~item_t (); 214 } 215 216 hb_free (old_items); 217 218 return true; 219 } 220 221 template <typename KK, typename VV> set_with_hashhb_hashmap_t222 bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool overwrite = true) 223 { 224 if (unlikely (!successful)) return false; 225 if (unlikely ((occupancy + occupancy / 2) >= mask && !alloc ())) return false; 226 227 hash &= 0x3FFFFFFF; // We only store lower 30bit of hash 228 unsigned int tombstone = (unsigned int) -1; 229 unsigned int i = hash % prime; 230 unsigned length = 0; 231 unsigned step = 0; 232 while (items[i].is_used ()) 233 { 234 if ((std::is_integral<K>::value || items[i].hash == hash) && 235 items[i] == key) 236 { 237 if (!overwrite) 238 return false; 239 else 240 break; 241 } 242 if (!items[i].is_real () && tombstone == (unsigned) -1) 243 tombstone = i; 244 i = (i + ++step) & mask; 245 length++; 246 } 247 248 item_t &item = items[tombstone == (unsigned) -1 ? i : tombstone]; 249 250 if (item.is_used ()) 251 { 252 occupancy--; 253 population -= item.is_real (); 254 } 255 256 item.key = std::forward<KK> (key); 257 item.value = std::forward<VV> (value); 258 item.hash = hash; 259 item.set_used (true); 260 item.set_real (true); 261 262 occupancy++; 263 population++; 264 265 if (unlikely (length > max_chain_length) && occupancy * 8 > mask) 266 alloc (mask - 8); // This ensures we jump to next larger size 267 268 return true; 269 } 270 271 template <typename VV> sethb_hashmap_t272 bool set (const K &key, VV&& value, bool overwrite = true) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value), overwrite); } 273 template <typename VV> sethb_hashmap_t274 bool set (K &&key, VV&& value, bool overwrite = true) 275 { 276 uint32_t hash = hb_hash (key); 277 return set_with_hash (std::move (key), hash, std::forward<VV> (value), overwrite); 278 } addhb_hashmap_t279 bool add (const K &key) 280 { 281 uint32_t hash = hb_hash (key); 282 return set_with_hash (key, hash, item_t::default_value ()); 283 } 284 get_with_hashhb_hashmap_t285 const V& get_with_hash (const K &key, uint32_t hash) const 286 { 287 if (!items) return item_t::default_value (); 288 auto *item = fetch_item (key, hb_hash (key)); 289 if (item) 290 return item->value; 291 return item_t::default_value (); 292 } gethb_hashmap_t293 const V& get (const K &key) const 294 { 295 if (!items) return item_t::default_value (); 296 return get_with_hash (key, hb_hash (key)); 297 } 298 delhb_hashmap_t299 void del (const K &key) 300 { 301 if (!items) return; 302 auto *item = fetch_item (key, hb_hash (key)); 303 if (item) 304 { 305 item->set_real (false); 306 population--; 307 } 308 } 309 310 /* Has interface. */ operator []hb_hashmap_t311 const V& operator [] (K k) const { return get (k); } 312 template <typename VV=V> hashb_hashmap_t313 bool has (const K &key, VV **vp = nullptr) const 314 { 315 if (!items) return false; 316 auto *item = fetch_item (key, hb_hash (key)); 317 if (item) 318 { 319 if (vp) *vp = std::addressof (item->value); 320 return true; 321 } 322 return false; 323 } fetch_itemhb_hashmap_t324 item_t *fetch_item (const K &key, uint32_t hash) const 325 { 326 hash &= 0x3FFFFFFF; // We only store lower 30bit of hash 327 unsigned int i = hash % prime; 328 unsigned step = 0; 329 while (items[i].is_used ()) 330 { 331 if ((std::is_integral<K>::value || items[i].hash == hash) && 332 items[i] == key) 333 { 334 if (items[i].is_real ()) 335 return &items[i]; 336 else 337 return nullptr; 338 } 339 i = (i + ++step) & mask; 340 } 341 return nullptr; 342 } 343 /* Projection. */ operator ()hb_hashmap_t344 const V& operator () (K k) const { return get (k); } 345 sizehb_hashmap_t346 unsigned size () const { return mask ? mask + 1 : 0; } 347 clearhb_hashmap_t348 void clear () 349 { 350 if (unlikely (!successful)) return; 351 352 for (auto &_ : hb_iter (items, size ())) 353 { 354 /* Reconstruct items. */ 355 _.~item_t (); 356 new (&_) item_t (); 357 } 358 359 population = occupancy = 0; 360 } 361 is_emptyhb_hashmap_t362 bool is_empty () const { return population == 0; } operator boolhb_hashmap_t363 explicit operator bool () const { return !is_empty (); } 364 hashhb_hashmap_t365 uint32_t hash () const 366 { 367 return 368 + iter_items () 369 | hb_reduce ([] (uint32_t h, const item_t &_) { return h ^ _.total_hash (); }, (uint32_t) 0u) 370 ; 371 } 372 is_equalhb_hashmap_t373 bool is_equal (const hb_hashmap_t &other) const 374 { 375 if (population != other.population) return false; 376 377 for (auto pair : iter ()) 378 if (other.get (pair.first) != pair.second) 379 return false; 380 381 return true; 382 } operator ==hb_hashmap_t383 bool operator == (const hb_hashmap_t &other) const { return is_equal (other); } operator !=hb_hashmap_t384 bool operator != (const hb_hashmap_t &other) const { return !is_equal (other); } 385 get_populationhb_hashmap_t386 unsigned int get_population () const { return population; } 387 updatehb_hashmap_t388 void update (const hb_hashmap_t &other) 389 { 390 if (unlikely (!successful)) return; 391 392 hb_copy (other, *this); 393 } 394 395 /* 396 * Iterator 397 */ 398 iter_itemshb_hashmap_t399 auto iter_items () const HB_AUTO_RETURN 400 ( 401 + hb_iter (items, this->size ()) 402 | hb_filter (&item_t::is_real) 403 ) 404 auto iter_ref () const HB_AUTO_RETURN 405 ( 406 + this->iter_items () 407 | hb_map (&item_t::get_pair_ref) 408 ) 409 auto iter () const HB_AUTO_RETURN 410 ( 411 + this->iter_items () 412 | hb_map (&item_t::get_pair) 413 ) 414 auto keys_ref () const HB_AUTO_RETURN 415 ( 416 + this->iter_items () 417 | hb_map (&item_t::get_key) 418 ) 419 auto keys () const HB_AUTO_RETURN 420 ( 421 + this->keys_ref () 422 | hb_map (hb_ridentity) 423 ) 424 auto values_ref () const HB_AUTO_RETURN 425 ( 426 + this->iter_items () 427 | hb_map (&item_t::get_value) 428 ) 429 auto values () const HB_AUTO_RETURN 430 ( 431 + this->values_ref () 432 | hb_map (hb_ridentity) 433 ) 434 435 /* C iterator. */ 436 bool next (int *idx, 437 K *key, 438 V *value) const 439 { 440 unsigned i = (unsigned) (*idx + 1); 441 442 unsigned count = size (); 443 while (i < count && !items[i].is_real ()) 444 i++; 445 446 if (i >= count) 447 { 448 *idx = -1; 449 return false; 450 } 451 452 *key = items[i].key; 453 *value = items[i].value; 454 455 *idx = (signed) i; 456 return true; 457 } 458 459 /* Sink interface. */ operator <<hb_hashmap_t460 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v) 461 { set (v.first, v.second); return *this; } operator <<hb_hashmap_t462 hb_hashmap_t& operator << (const hb_pair_t<K, V&&>& v) 463 { set (v.first, std::move (v.second)); return *this; } operator <<hb_hashmap_t464 hb_hashmap_t& operator << (const hb_pair_t<K&&, V>& v) 465 { set (std::move (v.first), v.second); return *this; } operator <<hb_hashmap_t466 hb_hashmap_t& operator << (const hb_pair_t<K&&, V&&>& v) 467 { set (std::move (v.first), std::move (v.second)); return *this; } 468 prime_forhb_hashmap_t469 static unsigned int prime_for (unsigned int shift) 470 { 471 /* Following comment and table copied from glib. */ 472 /* Each table size has an associated prime modulo (the first prime 473 * lower than the table size) used to find the initial bucket. Probing 474 * then works modulo 2^n. The prime modulo is necessary to get a 475 * good distribution with poor hash functions. 476 */ 477 /* Not declaring static to make all kinds of compilers happy... */ 478 /*static*/ const unsigned int prime_mod [32] = 479 { 480 1, /* For 1 << 0 */ 481 2, 482 3, 483 7, 484 13, 485 31, 486 61, 487 127, 488 251, 489 509, 490 1021, 491 2039, 492 4093, 493 8191, 494 16381, 495 32749, 496 65521, /* For 1 << 16 */ 497 131071, 498 262139, 499 524287, 500 1048573, 501 2097143, 502 4194301, 503 8388593, 504 16777213, 505 33554393, 506 67108859, 507 134217689, 508 268435399, 509 536870909, 510 1073741789, 511 2147483647 /* For 1 << 31 */ 512 }; 513 514 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 515 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 516 517 return prime_mod[shift]; 518 } 519 }; 520 521 /* 522 * hb_map_t 523 */ 524 525 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 526 hb_codepoint_t, 527 true> 528 { 529 using hashmap = hb_hashmap_t<hb_codepoint_t, 530 hb_codepoint_t, 531 true>; 532 533 ~hb_map_t () = default; hb_map_thb_map_t534 hb_map_t () : hashmap () {} hb_map_thb_map_t535 hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {} hb_map_thb_map_t536 hb_map_t (hb_map_t &&o) : hashmap (std::move ((hashmap &) o)) {} 537 hb_map_t& operator= (const hb_map_t&) = default; 538 hb_map_t& operator= (hb_map_t&&) = default; hb_map_thb_map_t539 hb_map_t (std::initializer_list<hb_codepoint_pair_t> lst) : hashmap (lst) {} 540 template <typename Iterable, 541 hb_requires (hb_is_iterable (Iterable))> hb_map_thb_map_t542 hb_map_t (const Iterable &o) : hashmap (o) {} 543 }; 544 545 546 #endif /* HB_MAP_HH */ 547