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 template <typename K, typename V, 38 typename k_invalid_t = K, 39 typename v_invalid_t = V, 40 k_invalid_t kINVALID = hb_is_pointer (K) ? 0 : std::is_signed<K>::value ? hb_int_min (K) : (K) -1, 41 v_invalid_t vINVALID = hb_is_pointer (V) ? 0 : std::is_signed<V>::value ? hb_int_min (V) : (V) -1> 42 struct hb_hashmap_t 43 { 44 static constexpr K INVALID_KEY = kINVALID; 45 static constexpr V INVALID_VALUE = vINVALID; 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 () { hb_copy (o, *this); } hb_hashmap_thb_hashmap_t51 hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); } operator =hb_hashmap_t52 hb_hashmap_t& operator= (const hb_hashmap_t& o) { hb_copy (o, *this); return *this; } operator =hb_hashmap_t53 hb_hashmap_t& operator= (hb_hashmap_t&& o) { hb_swap (*this, o); return *this; } 54 hb_hashmap_thb_hashmap_t55 hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t () 56 { 57 for (auto&& item : lst) 58 set (item.first, item.second); 59 } 60 template <typename Iterable, 61 hb_requires (hb_is_iterable (Iterable))> hb_hashmap_thb_hashmap_t62 hb_hashmap_t (const Iterable &o) : hb_hashmap_t () 63 { 64 hb_copy (o, *this); 65 } 66 67 static_assert (std::is_trivially_copyable<K>::value, ""); 68 static_assert (std::is_trivially_copyable<V>::value, ""); 69 static_assert (std::is_trivially_destructible<K>::value, ""); 70 static_assert (std::is_trivially_destructible<V>::value, ""); 71 72 struct item_t 73 { 74 K key; 75 V value; 76 uint32_t hash; 77 clearhb_hashmap_t::item_t78 void clear () { key = kINVALID; value = vINVALID; hash = 0; } 79 operator ==hb_hashmap_t::item_t80 bool operator == (const K &o) { return hb_deref (key) == hb_deref (o); } operator ==hb_hashmap_t::item_t81 bool operator == (const item_t &o) { return *this == o.key; } is_unusedhb_hashmap_t::item_t82 bool is_unused () const { return key == kINVALID; } is_tombstonehb_hashmap_t::item_t83 bool is_tombstone () const { return key != kINVALID && value == vINVALID; } is_realhb_hashmap_t::item_t84 bool is_real () const { return key != kINVALID && value != vINVALID; } get_pairhb_hashmap_t::item_t85 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } 86 }; 87 88 hb_object_header_t header; 89 bool successful; /* Allocations successful */ 90 unsigned int population; /* Not including tombstones. */ 91 unsigned int occupancy; /* Including tombstones. */ 92 unsigned int mask; 93 unsigned int prime; 94 item_t *items; 95 swap(hb_hashmap_t & a,hb_hashmap_t & b)96 friend void swap (hb_hashmap_t& a, hb_hashmap_t& b) 97 { 98 if (unlikely (!a.successful || !b.successful)) 99 return; 100 hb_swap (a.population, b.population); 101 hb_swap (a.occupancy, b.occupancy); 102 hb_swap (a.mask, b.mask); 103 hb_swap (a.prime, b.prime); 104 hb_swap (a.items, b.items); 105 } init_shallowhb_hashmap_t106 void init_shallow () 107 { 108 successful = true; 109 population = occupancy = 0; 110 mask = 0; 111 prime = 0; 112 items = nullptr; 113 } inithb_hashmap_t114 void init () 115 { 116 hb_object_init (this); 117 init_shallow (); 118 } fini_shallowhb_hashmap_t119 void fini_shallow () 120 { 121 hb_free (items); 122 items = nullptr; 123 population = occupancy = 0; 124 } finihb_hashmap_t125 void fini () 126 { 127 hb_object_fini (this); 128 fini_shallow (); 129 } 130 resethb_hashmap_t131 void reset () 132 { 133 successful = true; 134 clear (); 135 } 136 in_errorhb_hashmap_t137 bool in_error () const { return !successful; } 138 resizehb_hashmap_t139 bool resize () 140 { 141 if (unlikely (!successful)) return false; 142 143 unsigned int power = hb_bit_storage (population * 2 + 8); 144 unsigned int new_size = 1u << power; 145 item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t)); 146 if (unlikely (!new_items)) 147 { 148 successful = false; 149 return false; 150 } 151 for (auto &_ : hb_iter (new_items, new_size)) 152 _.clear (); 153 154 unsigned int old_size = mask + 1; 155 item_t *old_items = items; 156 157 /* Switch to new, empty, array. */ 158 population = occupancy = 0; 159 mask = new_size - 1; 160 prime = prime_for (power); 161 items = new_items; 162 163 /* Insert back old items. */ 164 if (old_items) 165 for (unsigned int i = 0; i < old_size; i++) 166 if (old_items[i].is_real ()) 167 set_with_hash (old_items[i].key, 168 old_items[i].hash, 169 std::move (old_items[i].value)); 170 171 hb_free (old_items); 172 173 return true; 174 } 175 sethb_hashmap_t176 bool set (K key, const V& value) { return set_with_hash (key, hb_hash (key), value); } sethb_hashmap_t177 bool set (K key, V&& value) { return set_with_hash (key, hb_hash (key), std::move (value)); } 178 gethb_hashmap_t179 V get (K key) const 180 { 181 if (unlikely (!items)) return vINVALID; 182 unsigned int i = bucket_for (key); 183 return items[i].is_real () && items[i] == key ? items[i].value : vINVALID; 184 } 185 delhb_hashmap_t186 void del (K key) { set (key, vINVALID); } 187 188 /* Has interface. */ 189 static constexpr V SENTINEL = vINVALID; 190 typedef V value_t; operator []hb_hashmap_t191 value_t operator [] (K k) const { return get (k); } hashb_hashmap_t192 bool has (K k, V *vp = nullptr) const 193 { 194 V v = (*this)[k]; 195 if (vp) *vp = v; 196 return v != SENTINEL; 197 } 198 /* Projection. */ operator ()hb_hashmap_t199 V operator () (K k) const { return get (k); } 200 clearhb_hashmap_t201 void clear () 202 { 203 if (unlikely (!successful)) return; 204 205 if (items) 206 for (auto &_ : hb_iter (items, mask + 1)) 207 _.clear (); 208 209 population = occupancy = 0; 210 } 211 is_emptyhb_hashmap_t212 bool is_empty () const { return population == 0; } operator boolhb_hashmap_t213 explicit operator bool () const { return !is_empty (); } 214 get_populationhb_hashmap_t215 unsigned int get_population () const { return population; } 216 217 /* 218 * Iterator 219 */ 220 auto iter () const HB_AUTO_RETURN 221 ( 222 + hb_array (items, mask ? mask + 1 : 0) 223 | hb_filter (&item_t::is_real) 224 | hb_map (&item_t::get_pair) 225 ) 226 auto keys () const HB_AUTO_RETURN 227 ( 228 + hb_array (items, mask ? mask + 1 : 0) 229 | hb_filter (&item_t::is_real) 230 | hb_map (&item_t::key) 231 | hb_map (hb_ridentity) 232 ) 233 auto values () const HB_AUTO_RETURN 234 ( 235 + hb_array (items, mask ? mask + 1 : 0) 236 | hb_filter (&item_t::is_real) 237 | hb_map (&item_t::value) 238 | hb_map (hb_ridentity) 239 ) 240 241 /* Sink interface. */ 242 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v) 243 { set (v.first, v.second); return *this; } 244 245 protected: 246 247 template <typename VV> set_with_hashhb_hashmap_t248 bool set_with_hash (K key, uint32_t hash, VV&& value) 249 { 250 if (unlikely (!successful)) return false; 251 if (unlikely (key == kINVALID)) return true; 252 if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false; 253 unsigned int i = bucket_for_hash (key, hash); 254 255 if (value == vINVALID && items[i].key != key) 256 return true; /* Trying to delete non-existent key. */ 257 258 if (!items[i].is_unused ()) 259 { 260 occupancy--; 261 if (!items[i].is_tombstone ()) 262 population--; 263 } 264 265 items[i].key = key; 266 items[i].value = value; 267 items[i].hash = hash; 268 269 occupancy++; 270 if (!items[i].is_tombstone ()) 271 population++; 272 273 return true; 274 } 275 bucket_forhb_hashmap_t276 unsigned int bucket_for (K key) const 277 { 278 return bucket_for_hash (key, hb_hash (key)); 279 } 280 bucket_for_hashhb_hashmap_t281 unsigned int bucket_for_hash (K key, uint32_t hash) const 282 { 283 unsigned int i = hash % prime; 284 unsigned int step = 0; 285 unsigned int tombstone = (unsigned) -1; 286 while (!items[i].is_unused ()) 287 { 288 if (items[i].hash == hash && items[i] == key) 289 return i; 290 if (tombstone == (unsigned) -1 && items[i].is_tombstone ()) 291 tombstone = i; 292 i = (i + ++step) & mask; 293 } 294 return tombstone == (unsigned) -1 ? i : tombstone; 295 } 296 prime_forhb_hashmap_t297 static unsigned int prime_for (unsigned int shift) 298 { 299 /* Following comment and table copied from glib. */ 300 /* Each table size has an associated prime modulo (the first prime 301 * lower than the table size) used to find the initial bucket. Probing 302 * then works modulo 2^n. The prime modulo is necessary to get a 303 * good distribution with poor hash functions. 304 */ 305 /* Not declaring static to make all kinds of compilers happy... */ 306 /*static*/ const unsigned int prime_mod [32] = 307 { 308 1, /* For 1 << 0 */ 309 2, 310 3, 311 7, 312 13, 313 31, 314 61, 315 127, 316 251, 317 509, 318 1021, 319 2039, 320 4093, 321 8191, 322 16381, 323 32749, 324 65521, /* For 1 << 16 */ 325 131071, 326 262139, 327 524287, 328 1048573, 329 2097143, 330 4194301, 331 8388593, 332 16777213, 333 33554393, 334 67108859, 335 134217689, 336 268435399, 337 536870909, 338 1073741789, 339 2147483647 /* For 1 << 31 */ 340 }; 341 342 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 343 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 344 345 return prime_mod[shift]; 346 } 347 }; 348 349 /* 350 * hb_map_t 351 */ 352 353 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 354 hb_codepoint_t, 355 hb_codepoint_t, 356 hb_codepoint_t, 357 HB_MAP_VALUE_INVALID, 358 HB_MAP_VALUE_INVALID> 359 { 360 using hashmap = hb_hashmap_t<hb_codepoint_t, 361 hb_codepoint_t, 362 hb_codepoint_t, 363 hb_codepoint_t, 364 HB_MAP_VALUE_INVALID, 365 HB_MAP_VALUE_INVALID>; 366 367 hb_map_t () = default; 368 ~hb_map_t () = default; 369 hb_map_t (hb_map_t&) = default; 370 hb_map_t& operator= (const hb_map_t&) = default; 371 hb_map_t& operator= (hb_map_t&&) = default; hb_map_thb_map_t372 hb_map_t (std::initializer_list<hb_pair_t<hb_codepoint_t, hb_codepoint_t>> lst) : hashmap (lst) {} 373 template <typename Iterable, 374 hb_requires (hb_is_iterable (Iterable))> hb_map_thb_map_t375 hb_map_t (const Iterable &o) : hashmap (o) {} 376 }; 377 378 #endif /* HB_MAP_HH */ 379