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 == (const 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 hb_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 successful = true; 101 clear (); 102 } 103 in_errorhb_hashmap_t104 bool in_error () const { return !successful; } 105 resizehb_hashmap_t106 bool resize () 107 { 108 if (unlikely (!successful)) return false; 109 110 unsigned int power = hb_bit_storage (population * 2 + 8); 111 unsigned int new_size = 1u << power; 112 item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t)); 113 if (unlikely (!new_items)) 114 { 115 successful = false; 116 return false; 117 } 118 for (auto &_ : hb_iter (new_items, new_size)) 119 _.clear (); 120 121 unsigned int old_size = mask + 1; 122 item_t *old_items = items; 123 124 /* Switch to new, empty, array. */ 125 population = occupancy = 0; 126 mask = new_size - 1; 127 prime = prime_for (power); 128 items = new_items; 129 130 /* Insert back old items. */ 131 if (old_items) 132 for (unsigned int i = 0; i < old_size; i++) 133 if (old_items[i].is_real ()) 134 set_with_hash (old_items[i].key, 135 old_items[i].hash, 136 old_items[i].value); 137 138 hb_free (old_items); 139 140 return true; 141 } 142 sethb_hashmap_t143 bool set (K key, V value) 144 { 145 return set_with_hash (key, hb_hash (key), value); 146 } 147 gethb_hashmap_t148 V get (K key) const 149 { 150 if (unlikely (!items)) return vINVALID; 151 unsigned int i = bucket_for (key); 152 return items[i].is_real () && items[i] == key ? items[i].value : vINVALID; 153 } 154 delhb_hashmap_t155 void del (K key) { set (key, vINVALID); } 156 157 /* Has interface. */ 158 static constexpr V SENTINEL = vINVALID; 159 typedef V value_t; operator []hb_hashmap_t160 value_t operator [] (K k) const { return get (k); } hashb_hashmap_t161 bool has (K k, V *vp = nullptr) const 162 { 163 V v = (*this)[k]; 164 if (vp) *vp = v; 165 return v != SENTINEL; 166 } 167 /* Projection. */ operator ()hb_hashmap_t168 V operator () (K k) const { return get (k); } 169 clearhb_hashmap_t170 void clear () 171 { 172 if (items) 173 for (auto &_ : hb_iter (items, mask + 1)) 174 _.clear (); 175 176 population = occupancy = 0; 177 } 178 is_emptyhb_hashmap_t179 bool is_empty () const { return population == 0; } operator boolhb_hashmap_t180 explicit operator bool () const { return !is_empty (); } 181 get_populationhb_hashmap_t182 unsigned int get_population () const { return population; } 183 184 /* 185 * Iterator 186 */ 187 auto iter () const HB_AUTO_RETURN 188 ( 189 + hb_array (items, mask ? mask + 1 : 0) 190 | hb_filter (&item_t::is_real) 191 | hb_map (&item_t::get_pair) 192 ) 193 auto keys () const HB_AUTO_RETURN 194 ( 195 + hb_array (items, mask ? mask + 1 : 0) 196 | hb_filter (&item_t::is_real) 197 | hb_map (&item_t::key) 198 | hb_map (hb_ridentity) 199 ) 200 auto values () const HB_AUTO_RETURN 201 ( 202 + hb_array (items, mask ? mask + 1 : 0) 203 | hb_filter (&item_t::is_real) 204 | hb_map (&item_t::value) 205 | hb_map (hb_ridentity) 206 ) 207 208 /* Sink interface. */ 209 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v) 210 { set (v.first, v.second); return *this; } 211 212 protected: 213 set_with_hashhb_hashmap_t214 bool set_with_hash (K key, uint32_t hash, V value) 215 { 216 if (unlikely (!successful)) return false; 217 if (unlikely (key == kINVALID)) return true; 218 if (unlikely ((occupancy + occupancy / 2) >= mask && !resize ())) return false; 219 unsigned int i = bucket_for_hash (key, hash); 220 221 if (value == vINVALID && items[i].key != key) 222 return true; /* Trying to delete non-existent key. */ 223 224 if (!items[i].is_unused ()) 225 { 226 occupancy--; 227 if (items[i].is_tombstone ()) 228 population--; 229 } 230 231 items[i].key = key; 232 items[i].value = value; 233 items[i].hash = hash; 234 235 occupancy++; 236 if (!items[i].is_tombstone ()) 237 population++; 238 239 return true; 240 } 241 bucket_forhb_hashmap_t242 unsigned int bucket_for (K key) const 243 { 244 return bucket_for_hash (key, hb_hash (key)); 245 } 246 bucket_for_hashhb_hashmap_t247 unsigned int bucket_for_hash (K key, uint32_t hash) const 248 { 249 unsigned int i = hash % prime; 250 unsigned int step = 0; 251 unsigned int tombstone = (unsigned) -1; 252 while (!items[i].is_unused ()) 253 { 254 if (items[i].hash == hash && items[i] == key) 255 return i; 256 if (tombstone == (unsigned) -1 && items[i].is_tombstone ()) 257 tombstone = i; 258 i = (i + ++step) & mask; 259 } 260 return tombstone == (unsigned) -1 ? i : tombstone; 261 } 262 prime_forhb_hashmap_t263 static unsigned int prime_for (unsigned int shift) 264 { 265 /* Following comment and table copied from glib. */ 266 /* Each table size has an associated prime modulo (the first prime 267 * lower than the table size) used to find the initial bucket. Probing 268 * then works modulo 2^n. The prime modulo is necessary to get a 269 * good distribution with poor hash functions. 270 */ 271 /* Not declaring static to make all kinds of compilers happy... */ 272 /*static*/ const unsigned int prime_mod [32] = 273 { 274 1, /* For 1 << 0 */ 275 2, 276 3, 277 7, 278 13, 279 31, 280 61, 281 127, 282 251, 283 509, 284 1021, 285 2039, 286 4093, 287 8191, 288 16381, 289 32749, 290 65521, /* For 1 << 16 */ 291 131071, 292 262139, 293 524287, 294 1048573, 295 2097143, 296 4194301, 297 8388593, 298 16777213, 299 33554393, 300 67108859, 301 134217689, 302 268435399, 303 536870909, 304 1073741789, 305 2147483647 /* For 1 << 31 */ 306 }; 307 308 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 309 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 310 311 return prime_mod[shift]; 312 } 313 }; 314 315 /* 316 * hb_map_t 317 */ 318 319 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 320 hb_codepoint_t, 321 HB_MAP_VALUE_INVALID, 322 HB_MAP_VALUE_INVALID> {}; 323 324 325 #endif /* HB_MAP_HH */ 326