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 : hb_is_signed (K) ? hb_int_min (K) : (K) -1, 39 V vINVALID = hb_is_pointer (V) ? 0 : hb_is_signed (V) ? hb_int_min (V) : (V) -1> 40 struct hb_hashmap_t 41 { 42 HB_DELETE_COPY_ASSIGN (hb_hashmap_t); hb_hashmap_thb_hashmap_t43 hb_hashmap_t () { init (); } ~hb_hashmap_thb_hashmap_t44 ~hb_hashmap_t () { fini (); } 45 46 static_assert (hb_is_integral (K) || hb_is_pointer (K), ""); 47 static_assert (hb_is_integral (V) || hb_is_pointer (V), ""); 48 49 struct item_t 50 { 51 K key; 52 V value; 53 uint32_t hash; 54 clearhb_hashmap_t::item_t55 void clear () { key = kINVALID; value = vINVALID; hash = 0; } 56 operator ==hb_hashmap_t::item_t57 bool operator == (K o) { return hb_deref (key) == hb_deref (o); } operator ==hb_hashmap_t::item_t58 bool operator == (const item_t &o) { return *this == o.key; } is_unusedhb_hashmap_t::item_t59 bool is_unused () const { return key == kINVALID; } is_tombstonehb_hashmap_t::item_t60 bool is_tombstone () const { return key != kINVALID && value == vINVALID; } is_realhb_hashmap_t::item_t61 bool is_real () const { return key != kINVALID && value != vINVALID; } get_pairhb_hashmap_t::item_t62 hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); } 63 }; 64 65 hb_object_header_t header; 66 bool successful; /* Allocations successful */ 67 unsigned int population; /* Not including tombstones. */ 68 unsigned int occupancy; /* Including tombstones. */ 69 unsigned int mask; 70 unsigned int prime; 71 item_t *items; 72 init_shallowhb_hashmap_t73 void init_shallow () 74 { 75 successful = true; 76 population = occupancy = 0; 77 mask = 0; 78 prime = 0; 79 items = nullptr; 80 } inithb_hashmap_t81 void init () 82 { 83 hb_object_init (this); 84 init_shallow (); 85 } fini_shallowhb_hashmap_t86 void fini_shallow () 87 { 88 free (items); 89 items = nullptr; 90 population = occupancy = 0; 91 } finihb_hashmap_t92 void fini () 93 { 94 hb_object_fini (this); 95 fini_shallow (); 96 } 97 resethb_hashmap_t98 void reset () 99 { 100 if (unlikely (hb_object_is_immutable (this))) 101 return; 102 successful = true; 103 clear (); 104 } 105 in_errorhb_hashmap_t106 bool in_error () const { return !successful; } 107 resizehb_hashmap_t108 bool resize () 109 { 110 if (unlikely (!successful)) return false; 111 112 unsigned int power = hb_bit_storage (population * 2 + 8); 113 unsigned int new_size = 1u << power; 114 item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t)); 115 if (unlikely (!new_items)) 116 { 117 successful = false; 118 return false; 119 } 120 + hb_iter (new_items, new_size) 121 | hb_apply (&item_t::clear) 122 ; 123 124 unsigned int old_size = mask + 1; 125 item_t *old_items = items; 126 127 /* Switch to new, empty, array. */ 128 population = occupancy = 0; 129 mask = new_size - 1; 130 prime = prime_for (power); 131 items = new_items; 132 133 /* Insert back old items. */ 134 if (old_items) 135 for (unsigned int i = 0; i < old_size; i++) 136 if (old_items[i].is_real ()) 137 set_with_hash (old_items[i].key, 138 old_items[i].hash, 139 old_items[i].value); 140 141 free (old_items); 142 143 return true; 144 } 145 sethb_hashmap_t146 void set (K key, V value) 147 { 148 set_with_hash (key, hb_hash (key), value); 149 } 150 gethb_hashmap_t151 V get (K key) const 152 { 153 if (unlikely (!items)) return vINVALID; 154 unsigned int i = bucket_for (key); 155 return items[i].is_real () && items[i] == key ? items[i].value : vINVALID; 156 } 157 delhb_hashmap_t158 void del (K key) { set (key, vINVALID); } 159 160 /* Has interface. */ 161 static constexpr V SENTINEL = vINVALID; 162 typedef V value_t; operator []hb_hashmap_t163 value_t operator [] (K k) const { return get (k); } hashb_hashmap_t164 bool has (K k, V *vp = nullptr) const 165 { 166 V v = (*this)[k]; 167 if (vp) *vp = v; 168 return v != SENTINEL; 169 } 170 /* Projection. */ operator ()hb_hashmap_t171 V operator () (K k) const { return get (k); } 172 clearhb_hashmap_t173 void clear () 174 { 175 if (unlikely (hb_object_is_immutable (this))) 176 return; 177 if (items) 178 + hb_iter (items, mask + 1) 179 | hb_apply (&item_t::clear) 180 ; 181 182 population = occupancy = 0; 183 } 184 is_emptyhb_hashmap_t185 bool is_empty () const { return population == 0; } 186 get_populationhb_hashmap_t187 unsigned int get_population () const { return population; } 188 189 /* 190 * Iterator 191 */ 192 auto iter () const HB_AUTO_RETURN 193 ( 194 + hb_array (items, mask ? mask + 1 : 0) 195 | hb_filter (&item_t::is_real) 196 | hb_map (&item_t::get_pair) 197 ) 198 auto keys () const HB_AUTO_RETURN 199 ( 200 + hb_array (items, mask ? mask + 1 : 0) 201 | hb_filter (&item_t::is_real) 202 | hb_map (&item_t::key) 203 | hb_map (hb_ridentity) 204 ) 205 auto values () const HB_AUTO_RETURN 206 ( 207 + hb_array (items, mask ? mask + 1 : 0) 208 | hb_filter (&item_t::is_real) 209 | hb_map (&item_t::value) 210 | hb_map (hb_ridentity) 211 ) 212 213 /* Sink interface. */ 214 hb_hashmap_t<K, V, kINVALID, vINVALID>& operator << (const hb_pair_t<K, V>& v) 215 { set (v.first, v.second); return *this; } 216 217 protected: 218 set_with_hashhb_hashmap_t219 void set_with_hash (K key, uint32_t hash, V value) 220 { 221 if (unlikely (!successful)) return; 222 if (unlikely (key == kINVALID)) return; 223 if ((occupancy + occupancy / 2) >= mask && !resize ()) return; 224 unsigned int i = bucket_for_hash (key, hash); 225 226 if (value == vINVALID && items[i].key != key) 227 return; /* Trying to delete non-existent key. */ 228 229 if (!items[i].is_unused ()) 230 { 231 occupancy--; 232 if (items[i].is_tombstone ()) 233 population--; 234 } 235 236 items[i].key = key; 237 items[i].value = value; 238 items[i].hash = hash; 239 240 occupancy++; 241 if (!items[i].is_tombstone ()) 242 population++; 243 } 244 bucket_forhb_hashmap_t245 unsigned int bucket_for (K key) const 246 { 247 return bucket_for_hash (key, hb_hash (key)); 248 } 249 bucket_for_hashhb_hashmap_t250 unsigned int bucket_for_hash (K key, uint32_t hash) const 251 { 252 unsigned int i = hash % prime; 253 unsigned int step = 0; 254 unsigned int tombstone = (unsigned) -1; 255 while (!items[i].is_unused ()) 256 { 257 if (items[i].hash == hash && items[i] == key) 258 return i; 259 if (tombstone == (unsigned) -1 && items[i].is_tombstone ()) 260 tombstone = i; 261 i = (i + ++step) & mask; 262 } 263 return tombstone == (unsigned) -1 ? i : tombstone; 264 } 265 prime_forhb_hashmap_t266 static unsigned int prime_for (unsigned int shift) 267 { 268 /* Following comment and table copied from glib. */ 269 /* Each table size has an associated prime modulo (the first prime 270 * lower than the table size) used to find the initial bucket. Probing 271 * then works modulo 2^n. The prime modulo is necessary to get a 272 * good distribution with poor hash functions. 273 */ 274 /* Not declaring static to make all kinds of compilers happy... */ 275 /*static*/ const unsigned int prime_mod [32] = 276 { 277 1, /* For 1 << 0 */ 278 2, 279 3, 280 7, 281 13, 282 31, 283 61, 284 127, 285 251, 286 509, 287 1021, 288 2039, 289 4093, 290 8191, 291 16381, 292 32749, 293 65521, /* For 1 << 16 */ 294 131071, 295 262139, 296 524287, 297 1048573, 298 2097143, 299 4194301, 300 8388593, 301 16777213, 302 33554393, 303 67108859, 304 134217689, 305 268435399, 306 536870909, 307 1073741789, 308 2147483647 /* For 1 << 31 */ 309 }; 310 311 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 312 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 313 314 return prime_mod[shift]; 315 } 316 }; 317 318 /* 319 * hb_map_t 320 */ 321 322 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 323 hb_codepoint_t, 324 HB_MAP_VALUE_INVALID, 325 HB_MAP_VALUE_INVALID> {}; 326 327 328 #endif /* HB_MAP_HH */ 329