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 K kINVALID = hb_is_pointer (K) ? 0 : std::is_signed<K>::value ? hb_int_min (K) : (K) -1, 39 V vINVALID = hb_is_pointer (V) ? 0 : std::is_signed<V>::value ? hb_int_min (V) : (V) -1> 40 struct hb_hashmap_t 41 { 42 static constexpr K INVALID_KEY = kINVALID; 43 static constexpr V INVALID_VALUE = vINVALID; 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 () { 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) { 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 hb_copy (o, *this); 63 } 64 65 static_assert (std::is_integral<K>::value || hb_is_pointer (K), ""); 66 static_assert (std::is_integral<V>::value || hb_is_pointer (V), ""); 67 68 struct item_t 69 { 70 K key; 71 V value; 72 uint32_t hash; 73 clearhb_hashmap_t::item_t74 void clear () { key = kINVALID; value = vINVALID; hash = 0; } 75 operator ==hb_hashmap_t::item_t76 bool operator == (const K &o) { return hb_deref (key) == hb_deref (o); } operator ==hb_hashmap_t::item_t77 bool operator == (const item_t &o) { return *this == o.key; } is_unusedhb_hashmap_t::item_t78 bool is_unused () const { return key == kINVALID; } is_tombstonehb_hashmap_t::item_t79 bool is_tombstone () const { return key != kINVALID && value == vINVALID; } is_realhb_hashmap_t::item_t80 bool is_real () const { return key != kINVALID && value != vINVALID; } get_pairhb_hashmap_t::item_t81 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } 82 }; 83 84 hb_object_header_t header; 85 bool successful; /* Allocations successful */ 86 unsigned int population; /* Not including tombstones. */ 87 unsigned int occupancy; /* Including tombstones. */ 88 unsigned int mask; 89 unsigned int prime; 90 item_t *items; 91 swap(hb_hashmap_t & a,hb_hashmap_t & b)92 friend void swap (hb_hashmap_t& a, hb_hashmap_t& b) 93 { 94 if (unlikely (!a.successful || !b.successful)) 95 return; 96 hb_swap (a.population, b.population); 97 hb_swap (a.occupancy, b.occupancy); 98 hb_swap (a.mask, b.mask); 99 hb_swap (a.prime, b.prime); 100 hb_swap (a.items, b.items); 101 } init_shallowhb_hashmap_t102 void init_shallow () 103 { 104 successful = true; 105 population = occupancy = 0; 106 mask = 0; 107 prime = 0; 108 items = nullptr; 109 } inithb_hashmap_t110 void init () 111 { 112 hb_object_init (this); 113 init_shallow (); 114 } fini_shallowhb_hashmap_t115 void fini_shallow () 116 { 117 hb_free (items); 118 items = nullptr; 119 population = occupancy = 0; 120 } finihb_hashmap_t121 void fini () 122 { 123 hb_object_fini (this); 124 fini_shallow (); 125 } 126 resethb_hashmap_t127 void reset () 128 { 129 successful = true; 130 clear (); 131 } 132 in_errorhb_hashmap_t133 bool in_error () const { return !successful; } 134 resizehb_hashmap_t135 bool resize () 136 { 137 if (unlikely (!successful)) return false; 138 139 unsigned int power = hb_bit_storage (population * 2 + 8); 140 unsigned int new_size = 1u << power; 141 item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t)); 142 if (unlikely (!new_items)) 143 { 144 successful = false; 145 return false; 146 } 147 for (auto &_ : hb_iter (new_items, new_size)) 148 _.clear (); 149 150 unsigned int old_size = mask + 1; 151 item_t *old_items = items; 152 153 /* Switch to new, empty, array. */ 154 population = occupancy = 0; 155 mask = new_size - 1; 156 prime = prime_for (power); 157 items = new_items; 158 159 /* Insert back old items. */ 160 if (old_items) 161 for (unsigned int i = 0; i < old_size; i++) 162 if (old_items[i].is_real ()) 163 set_with_hash (old_items[i].key, 164 old_items[i].hash, 165 std::move (old_items[i].value)); 166 167 hb_free (old_items); 168 169 return true; 170 } 171 sethb_hashmap_t172 bool set (K key, const V& value) { return set_with_hash (key, hb_hash (key), value); } sethb_hashmap_t173 bool set (K key, V&& value) { return set_with_hash (key, hb_hash (key), std::move (value)); } 174 gethb_hashmap_t175 V get (K key) const 176 { 177 if (unlikely (!items)) return vINVALID; 178 unsigned int i = bucket_for (key); 179 return items[i].is_real () && items[i] == key ? items[i].value : vINVALID; 180 } 181 delhb_hashmap_t182 void del (K key) { set (key, vINVALID); } 183 184 /* Has interface. */ 185 static constexpr V SENTINEL = vINVALID; 186 typedef V value_t; operator []hb_hashmap_t187 value_t operator [] (K k) const { return get (k); } hashb_hashmap_t188 bool has (K k, V *vp = nullptr) const 189 { 190 V v = (*this)[k]; 191 if (vp) *vp = v; 192 return v != SENTINEL; 193 } 194 /* Projection. */ operator ()hb_hashmap_t195 V operator () (K k) const { return get (k); } 196 clearhb_hashmap_t197 void clear () 198 { 199 if (unlikely (!successful)) return; 200 201 if (items) 202 for (auto &_ : hb_iter (items, mask + 1)) 203 _.clear (); 204 205 population = occupancy = 0; 206 } 207 is_emptyhb_hashmap_t208 bool is_empty () const { return population == 0; } operator boolhb_hashmap_t209 explicit operator bool () const { return !is_empty (); } 210 get_populationhb_hashmap_t211 unsigned int get_population () const { return population; } 212 213 /* 214 * Iterator 215 */ 216 auto iter () const HB_AUTO_RETURN 217 ( 218 + hb_array (items, mask ? mask + 1 : 0) 219 | hb_filter (&item_t::is_real) 220 | hb_map (&item_t::get_pair) 221 ) 222 auto keys () const HB_AUTO_RETURN 223 ( 224 + hb_array (items, mask ? mask + 1 : 0) 225 | hb_filter (&item_t::is_real) 226 | hb_map (&item_t::key) 227 | hb_map (hb_ridentity) 228 ) 229 auto values () const HB_AUTO_RETURN 230 ( 231 + hb_array (items, mask ? mask + 1 : 0) 232 | hb_filter (&item_t::is_real) 233 | hb_map (&item_t::value) 234 | hb_map (hb_ridentity) 235 ) 236 237 /* Sink interface. */ 238 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v) 239 { set (v.first, v.second); return *this; } 240 241 protected: 242 243 template <typename VV> set_with_hashhb_hashmap_t244 bool set_with_hash (K key, uint32_t hash, VV&& value) 245 { 246 if (unlikely (!successful)) return false; 247 if (unlikely (key == kINVALID)) return true; 248 if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false; 249 unsigned int i = bucket_for_hash (key, hash); 250 251 if (value == vINVALID && items[i].key != key) 252 return true; /* Trying to delete non-existent key. */ 253 254 if (!items[i].is_unused ()) 255 { 256 occupancy--; 257 if (!items[i].is_tombstone ()) 258 population--; 259 } 260 261 items[i].key = key; 262 items[i].value = value; 263 items[i].hash = hash; 264 265 occupancy++; 266 if (!items[i].is_tombstone ()) 267 population++; 268 269 return true; 270 } 271 bucket_forhb_hashmap_t272 unsigned int bucket_for (K key) const 273 { 274 return bucket_for_hash (key, hb_hash (key)); 275 } 276 bucket_for_hashhb_hashmap_t277 unsigned int bucket_for_hash (K key, uint32_t hash) const 278 { 279 unsigned int i = hash % prime; 280 unsigned int step = 0; 281 unsigned int tombstone = (unsigned) -1; 282 while (!items[i].is_unused ()) 283 { 284 if (items[i].hash == hash && items[i] == key) 285 return i; 286 if (tombstone == (unsigned) -1 && items[i].is_tombstone ()) 287 tombstone = i; 288 i = (i + ++step) & mask; 289 } 290 return tombstone == (unsigned) -1 ? i : tombstone; 291 } 292 prime_forhb_hashmap_t293 static unsigned int prime_for (unsigned int shift) 294 { 295 /* Following comment and table copied from glib. */ 296 /* Each table size has an associated prime modulo (the first prime 297 * lower than the table size) used to find the initial bucket. Probing 298 * then works modulo 2^n. The prime modulo is necessary to get a 299 * good distribution with poor hash functions. 300 */ 301 /* Not declaring static to make all kinds of compilers happy... */ 302 /*static*/ const unsigned int prime_mod [32] = 303 { 304 1, /* For 1 << 0 */ 305 2, 306 3, 307 7, 308 13, 309 31, 310 61, 311 127, 312 251, 313 509, 314 1021, 315 2039, 316 4093, 317 8191, 318 16381, 319 32749, 320 65521, /* For 1 << 16 */ 321 131071, 322 262139, 323 524287, 324 1048573, 325 2097143, 326 4194301, 327 8388593, 328 16777213, 329 33554393, 330 67108859, 331 134217689, 332 268435399, 333 536870909, 334 1073741789, 335 2147483647 /* For 1 << 31 */ 336 }; 337 338 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 339 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 340 341 return prime_mod[shift]; 342 } 343 }; 344 345 /* 346 * hb_map_t 347 */ 348 349 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 350 hb_codepoint_t, 351 HB_MAP_VALUE_INVALID, 352 HB_MAP_VALUE_INVALID> 353 { 354 using hashmap = hb_hashmap_t<hb_codepoint_t, 355 hb_codepoint_t, 356 HB_MAP_VALUE_INVALID, 357 HB_MAP_VALUE_INVALID>; 358 359 hb_map_t () = default; 360 ~hb_map_t () = default; 361 hb_map_t (hb_map_t& o) = default; 362 hb_map_t& operator= (const hb_map_t& other) = default; 363 hb_map_t& operator= (hb_map_t&& other) = default; hb_map_thb_map_t364 hb_map_t (std::initializer_list<hb_pair_t<hb_codepoint_t, hb_codepoint_t>> lst) : hashmap (lst) {} 365 template <typename Iterable, 366 hb_requires (hb_is_iterable (Iterable))> hb_map_thb_map_t367 hb_map_t (const Iterable &o) : hashmap (o) {} 368 }; 369 370 #endif /* HB_MAP_HH */ 371