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 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 *) 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 free (old_items); 139 140 return true; 141 } 142 sethb_hashmap_t143 void set (K key, V value) 144 { 145 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 void set_with_hash (K key, uint32_t hash, V value) 215 { 216 if (unlikely (!successful)) return; 217 if (unlikely (key == kINVALID)) return; 218 if ((occupancy + occupancy / 2) >= mask && !resize ()) return; 219 unsigned int i = bucket_for_hash (key, hash); 220 221 if (value == vINVALID && items[i].key != key) 222 return; /* 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 bucket_forhb_hashmap_t240 unsigned int bucket_for (K key) const 241 { 242 return bucket_for_hash (key, hb_hash (key)); 243 } 244 bucket_for_hashhb_hashmap_t245 unsigned int bucket_for_hash (K key, uint32_t hash) const 246 { 247 unsigned int i = hash % prime; 248 unsigned int step = 0; 249 unsigned int tombstone = (unsigned) -1; 250 while (!items[i].is_unused ()) 251 { 252 if (items[i].hash == hash && items[i] == key) 253 return i; 254 if (tombstone == (unsigned) -1 && items[i].is_tombstone ()) 255 tombstone = i; 256 i = (i + ++step) & mask; 257 } 258 return tombstone == (unsigned) -1 ? i : tombstone; 259 } 260 prime_forhb_hashmap_t261 static unsigned int prime_for (unsigned int shift) 262 { 263 /* Following comment and table copied from glib. */ 264 /* Each table size has an associated prime modulo (the first prime 265 * lower than the table size) used to find the initial bucket. Probing 266 * then works modulo 2^n. The prime modulo is necessary to get a 267 * good distribution with poor hash functions. 268 */ 269 /* Not declaring static to make all kinds of compilers happy... */ 270 /*static*/ const unsigned int prime_mod [32] = 271 { 272 1, /* For 1 << 0 */ 273 2, 274 3, 275 7, 276 13, 277 31, 278 61, 279 127, 280 251, 281 509, 282 1021, 283 2039, 284 4093, 285 8191, 286 16381, 287 32749, 288 65521, /* For 1 << 16 */ 289 131071, 290 262139, 291 524287, 292 1048573, 293 2097143, 294 4194301, 295 8388593, 296 16777213, 297 33554393, 298 67108859, 299 134217689, 300 268435399, 301 536870909, 302 1073741789, 303 2147483647 /* For 1 << 31 */ 304 }; 305 306 if (unlikely (shift >= ARRAY_LENGTH (prime_mod))) 307 return prime_mod[ARRAY_LENGTH (prime_mod) - 1]; 308 309 return prime_mod[shift]; 310 } 311 }; 312 313 /* 314 * hb_map_t 315 */ 316 317 struct hb_map_t : hb_hashmap_t<hb_codepoint_t, 318 hb_codepoint_t, 319 HB_MAP_VALUE_INVALID, 320 HB_MAP_VALUE_INVALID> {}; 321 322 323 #endif /* HB_MAP_HH */ 324