gfx/harfbuzz/src/hb-map.hh

   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 #include "hb-set.hh"
  33
  34
  35 /*
  36  * hb_hashmap_t
  37  */
  38
  39 extern HB_INTERNAL const hb_codepoint_t minus_1;
  40
  41 template <typename K, typename V,
  42           bool minus_one = false>
  43 struct hb_hashmap_t
  44 {
  45   static constexpr bool realloc_move = true;
  46
  47   hb_hashmap_t ()  { init (); }
  48   ~hb_hashmap_t () { fini (); }
  49
  50   hb_hashmap_t (const hb_hashmap_t& o) : hb_hashmap_t ()
  51   {
  52     if (unlikely (!o.mask)) return;
  53
  54     if (item_t::is_trivial)
  55     {
  56       items = (item_t *) hb_malloc (sizeof (item_t) * (o.mask + 1));
  57       if (unlikely (!items))
  58       {
  59         successful = false;
  60         return;
  61       }
  62       population = o.population;
  63       occupancy = o.occupancy;
  64       mask = o.mask;
  65       prime = o.prime;
  66       max_chain_length = o.max_chain_length;
  67       memcpy (items, o.items, sizeof (item_t) * (mask + 1));
  68       return;
  69     }
  70
  71     alloc (o.population); hb_copy (o, *this);
  72   }
  73   hb_hashmap_t (hb_hashmap_t&& o) : hb_hashmap_t () { hb_swap (*this, o); }
  74   hb_hashmap_t& operator= (const hb_hashmap_t& o)  { reset (); alloc (o.population); hb_copy (o, *this); return *this; }
  75   hb_hashmap_t& operator= (hb_hashmap_t&& o)  { hb_swap (*this, o); return *this; }
  76
  77   hb_hashmap_t (std::initializer_list<hb_pair_t<K, V>> lst) : hb_hashmap_t ()
  78   {
  79     for (auto&& item : lst)
  80       set (item.first, item.second);
  81   }
  82   template <typename Iterable,
  83             hb_requires (hb_is_iterable (Iterable))>
  84   hb_hashmap_t (const Iterable &o) : hb_hashmap_t ()
  85   {
  86     auto iter = hb_iter (o);
  87     if (iter.is_random_access_iterator || iter.has_fast_len)
  88       alloc (hb_len (iter));
  89     hb_copy (iter, *this);
  90   }
  91
  92   struct item_t
  93   {
  94     K key;
  95     uint32_t is_real_ : 1;
  96     uint32_t is_used_ : 1;
  97     uint32_t hash : 30;
  98     V value;
  99
 100     item_t () : key (),
 101                 is_real_ (false), is_used_ (false),
 102                 hash (0),
 103                 value () {}
 104
 105     // Needed for https://github.com/harfbuzz/harfbuzz/issues/4138
 106     K& get_key () { return key; }
 107     V& get_value () { return value; }
 108
 109     bool is_used () const { return is_used_; }
 110     void set_used (bool is_used) { is_used_ = is_used; }
 111     void set_real (bool is_real) { is_real_ = is_real; }
 112     bool is_real () const { return is_real_; }
 113
 114     template <bool v = minus_one,
 115               hb_enable_if (v == false)>
 116     static inline const V& default_value () { return Null(V); };
 117     template <bool v = minus_one,
 118               hb_enable_if (v == true)>
 119     static inline const V& default_value ()
 120     {
 121       static_assert (hb_is_same (V, hb_codepoint_t), "");
 122       return minus_1;
 123     };
 124
 125     bool operator == (const K &o) const { return hb_deref (key) == hb_deref (o); }
 126     bool operator == (const item_t &o) const { return *this == o.key; }
 127     hb_pair_t<K, V> get_pair() const { return hb_pair_t<K, V> (key, value); }
 128     hb_pair_t<const K &, V &> get_pair_ref() { return hb_pair_t<const K &, V &> (key, value); }
 129
 130     uint32_t total_hash () const
 131     { return (hash * 31u) + hb_hash (value); }
 132
 133     static constexpr bool is_trivial = hb_is_trivially_constructible(K) &&
 134                                        hb_is_trivially_destructible(K) &&
 135                                        hb_is_trivially_constructible(V) &&
 136                                        hb_is_trivially_destructible(V);
 137   };
 138
 139   hb_object_header_t header;
 140   unsigned int successful : 1; /* Allocations successful */
 141   unsigned int population : 31; /* Not including tombstones. */
 142   unsigned int occupancy; /* Including tombstones. */
 143   unsigned int mask;
 144   unsigned int prime;
 145   unsigned int max_chain_length;
 146   item_t *items;
 147
 148   friend void swap (hb_hashmap_t& a, hb_hashmap_t& b)
 149   {
 150     if (unlikely (!a.successful || !b.successful))
 151       return;
 152     unsigned tmp = a.population;
 153     a.population = b.population;
 154     b.population = tmp;
 155     //hb_swap (a.population, b.population);
 156     hb_swap (a.occupancy, b.occupancy);
 157     hb_swap (a.mask, b.mask);
 158     hb_swap (a.prime, b.prime);
 159     hb_swap (a.max_chain_length, b.max_chain_length);
 160     hb_swap (a.items, b.items);
 161   }
 162   void init ()
 163   {
 164     hb_object_init (this);
 165
 166     successful = true;
 167     population = occupancy = 0;
 168     mask = 0;
 169     prime = 0;
 170     max_chain_length = 0;
 171     items = nullptr;
 172   }
 173   void fini ()
 174   {
 175     hb_object_fini (this);
 176
 177     if (likely (items))
 178     {
 179       unsigned size = mask + 1;
 180       if (!item_t::is_trivial)
 181         for (unsigned i = 0; i < size; i++)
 182           items[i].~item_t ();
 183       hb_free (items);
 184       items = nullptr;
 185     }
 186     population = occupancy = 0;
 187   }
 188
 189   void reset ()
 190   {
 191     successful = true;
 192     clear ();
 193   }
 194
 195   bool in_error () const { return !successful; }
 196
 197   bool alloc (unsigned new_population = 0)
 198   {
 199     if (unlikely (!successful)) return false;
 200
 201     if (new_population != 0 && (new_population + new_population / 2) < mask) return true;
 202
 203     unsigned int power = hb_bit_storage (hb_max ((unsigned) population, new_population) * 2 + 8);
 204     unsigned int new_size = 1u << power;
 205     item_t *new_items = (item_t *) hb_malloc ((size_t) new_size * sizeof (item_t));
 206     if (unlikely (!new_items))
 207     {
 208       successful = false;
 209       return false;
 210     }
 211     if (!item_t::is_trivial)
 212       for (auto &_ : hb_iter (new_items, new_size))
 213         new (&_) item_t ();
 214     else
 215       hb_memset (new_items, 0, (size_t) new_size * sizeof (item_t));
 216
 217     unsigned int old_size = size ();
 218     item_t *old_items = items;
 219
 220     /* Switch to new, empty, array. */
 221     population = occupancy = 0;
 222     mask = new_size - 1;
 223     prime = prime_for (power);
 224     max_chain_length = power * 2;
 225     items = new_items;
 226
 227     /* Insert back old items. */
 228     for (unsigned int i = 0; i < old_size; i++)
 229     {
 230       if (old_items[i].is_real ())
 231       {
 232         set_with_hash (std::move (old_items[i].key),
 233                        old_items[i].hash,
 234                        std::move (old_items[i].value));
 235       }
 236     }
 237     if (!item_t::is_trivial)
 238       for (unsigned int i = 0; i < old_size; i++)
 239         old_items[i].~item_t ();
 240
 241     hb_free (old_items);
 242
 243     return true;
 244   }
 245
 246   template <typename KK, typename VV>
 247   bool set_with_hash (KK&& key, uint32_t hash, VV&& value, bool overwrite = true)
 248   {
 249     if (unlikely (!successful)) return false;
 250     if (unlikely ((occupancy + occupancy / 2) >= mask && !alloc ())) return false;
 251
 252     hash &= 0x3FFFFFFF; // We only store lower 30bit of hash
 253     unsigned int tombstone = (unsigned int) -1;
 254     unsigned int i = hash % prime;
 255     unsigned length = 0;
 256     unsigned step = 0;
 257     while (items[i].is_used ())
 258     {
 259       if ((std::is_integral<K>::value || items[i].hash == hash) &&
 260           items[i] == key)
 261       {
 262         if (!overwrite)
 263           return false;
 264         else
 265           break;
 266       }
 267       if (!items[i].is_real () && tombstone == (unsigned) -1)
 268         tombstone = i;
 269       i = (i + ++step) & mask;
 270       length++;
 271     }
 272
 273     item_t &item = items[tombstone == (unsigned) -1 ? i : tombstone];
 274
 275     if (item.is_used ())
 276     {
 277       occupancy--;
 278       population -= item.is_real ();
 279     }
 280
 281     item.key = std::forward<KK> (key);
 282     item.value = std::forward<VV> (value);
 283     item.hash = hash;
 284     item.set_used (true);
 285     item.set_real (true);
 286
 287     occupancy++;
 288     population++;
 289
 290     if (unlikely (length > max_chain_length) && occupancy * 8 > mask)
 291       alloc (mask - 8); // This ensures we jump to next larger size
 292
 293     return true;
 294   }
 295
 296   template <typename VV>
 297   bool set (const K &key, VV&& value, bool overwrite = true) { return set_with_hash (key, hb_hash (key), std::forward<VV> (value), overwrite); }
 298   template <typename VV>
 299   bool set (K &&key, VV&& value, bool overwrite = true)
 300   {
 301     uint32_t hash = hb_hash (key);
 302     return set_with_hash (std::move (key), hash, std::forward<VV> (value), overwrite);
 303   }
 304   bool add (const K &key)
 305   {
 306     uint32_t hash = hb_hash (key);
 307     return set_with_hash (key, hash, item_t::default_value ());
 308   }
 309
 310   const V& get_with_hash (const K &key, uint32_t hash) const
 311   {
 312     if (!items) return item_t::default_value ();
 313     auto *item = fetch_item (key, hb_hash (key));
 314     if (item)
 315       return item->value;
 316     return item_t::default_value ();
 317   }
 318   const V& get (const K &key) const
 319   {
 320     if (!items) return item_t::default_value ();
 321     return get_with_hash (key, hb_hash (key));
 322   }
 323
 324   void del (const K &key)
 325   {
 326     if (!items) return;
 327     auto *item = fetch_item (key, hb_hash (key));
 328     if (item)
 329     {
 330       item->set_real (false);
 331       population--;
 332     }
 333   }
 334
 335   /* Has interface. */
 336   const V& operator [] (K k) const { return get (k); }
 337   template <typename VV=V>
 338   bool has (const K &key, VV **vp = nullptr) const
 339   {
 340     if (!items) return false;
 341     auto *item = fetch_item (key, hb_hash (key));
 342     if (item)
 343     {
 344       if (vp) *vp = std::addressof (item->value);
 345       return true;
 346     }
 347     return false;
 348   }
 349   item_t *fetch_item (const K &key, uint32_t hash) const
 350   {
 351     hash &= 0x3FFFFFFF; // We only store lower 30bit of hash
 352     unsigned int i = hash % prime;
 353     unsigned step = 0;
 354     while (items[i].is_used ())
 355     {
 356       if ((std::is_integral<K>::value || items[i].hash == hash) &&
 357           items[i] == key)
 358       {
 359         if (items[i].is_real ())
 360           return &items[i];
 361         else
 362           return nullptr;
 363       }
 364       i = (i + ++step) & mask;
 365     }
 366     return nullptr;
 367   }
 368   /* Projection. */
 369   const V& operator () (K k) const { return get (k); }
 370
 371   unsigned size () const { return mask ? mask + 1 : 0; }
 372
 373   void clear ()
 374   {
 375     if (unlikely (!successful)) return;
 376
 377     for (auto &_ : hb_iter (items, size ()))
 378     {
 379       /* Reconstruct items. */
 380       _.~item_t ();
 381       new (&_) item_t ();
 382     }
 383
 384     population = occupancy = 0;
 385   }
 386
 387   bool is_empty () const { return population == 0; }
 388   explicit operator bool () const { return !is_empty (); }
 389
 390   uint32_t hash () const
 391   {
 392     return
 393     + iter_items ()
 394     | hb_reduce ([] (uint32_t h, const item_t &_) { return h ^ _.total_hash (); }, (uint32_t) 0u)
 395     ;
 396   }
 397
 398   bool is_equal (const hb_hashmap_t &other) const
 399   {
 400     if (population != other.population) return false;
 401
 402     for (auto pair : iter ())
 403       if (other.get (pair.first) != pair.second)
 404         return false;
 405
 406     return true;
 407   }
 408   bool operator == (const hb_hashmap_t &other) const { return is_equal (other); }
 409   bool operator != (const hb_hashmap_t &other) const { return !is_equal (other); }
 410
 411   unsigned int get_population () const { return population; }
 412
 413   void update (const hb_hashmap_t &other)
 414   {
 415     if (unlikely (!successful)) return;
 416
 417     hb_copy (other, *this);
 418   }
 419
 420   /*
 421    * Iterator
 422    */
 423
 424   auto iter_items () const HB_AUTO_RETURN
 425   (
 426     + hb_iter (items, this->size ())
 427     | hb_filter (&item_t::is_real)
 428   )
 429   auto iter_ref () const HB_AUTO_RETURN
 430   (
 431     + this->iter_items ()
 432     | hb_map (&item_t::get_pair_ref)
 433   )
 434   auto iter () const HB_AUTO_RETURN
 435   (
 436     + this->iter_items ()
 437     | hb_map (&item_t::get_pair)
 438   )
 439   auto keys_ref () const HB_AUTO_RETURN
 440   (
 441     + this->iter_items ()
 442     | hb_map (&item_t::get_key)
 443   )
 444   auto keys () const HB_AUTO_RETURN
 445   (
 446     + this->keys_ref ()
 447     | hb_map (hb_ridentity)
 448   )
 449   auto values_ref () const HB_AUTO_RETURN
 450   (
 451     + this->iter_items ()
 452     | hb_map (&item_t::get_value)
 453   )
 454   auto values () const HB_AUTO_RETURN
 455   (
 456     + this->values_ref ()
 457     | hb_map (hb_ridentity)
 458   )
 459
 460   /* C iterator. */
 461   bool next (int *idx,
 462              K *key,
 463              V *value) const
 464   {
 465     unsigned i = (unsigned) (*idx + 1);
 466
 467     unsigned count = size ();
 468     while (i < count && !items[i].is_real ())
 469       i++;
 470
 471     if (i >= count)
 472     {
 473       *idx = -1;
 474       return false;
 475     }
 476
 477     *key = items[i].key;
 478     *value = items[i].value;
 479
 480     *idx = (signed) i;
 481     return true;
 482   }
 483
 484   /* Sink interface. */
 485   hb_hashmap_t& operator << (const hb_pair_t<K, V>& v)
 486   { set (v.first, v.second); return *this; }
 487   hb_hashmap_t& operator << (const hb_pair_t<K, V&&>& v)
 488   { set (v.first, std::move (v.second)); return *this; }
 489   hb_hashmap_t& operator << (const hb_pair_t<K&&, V>& v)
 490   { set (std::move (v.first), v.second); return *this; }
 491   hb_hashmap_t& operator << (const hb_pair_t<K&&, V&&>& v)
 492   { set (std::move (v.first), std::move (v.second)); return *this; }
 493
 494   static unsigned int prime_for (unsigned int shift)
 495   {
 496     /* Following comment and table copied from glib. */
 497     /* Each table size has an associated prime modulo (the first prime
 498      * lower than the table size) used to find the initial bucket. Probing
 499      * then works modulo 2^n. The prime modulo is necessary to get a
 500      * good distribution with poor hash functions.
 501      */
 502     /* Not declaring static to make all kinds of compilers happy... */
 503     /*static*/ const unsigned int prime_mod [32] =
 504     {
 505       1,          /* For 1 << 0 */
 506       2,
 507       3,
 508       7,
 509       13,
 510       31,
 511       61,
 512       127,
 513       251,
 514       509,
 515       1021,
 516       2039,
 517       4093,
 518       8191,
 519       16381,
 520       32749,
 521       65521,      /* For 1 << 16 */
 522       131071,
 523       262139,
 524       524287,
 525       1048573,
 526       2097143,
 527       4194301,
 528       8388593,
 529       16777213,
 530       33554393,
 531       67108859,
 532       134217689,
 533       268435399,
 534       536870909,
 535       1073741789,
 536       2147483647  /* For 1 << 31 */
 537     };
 538
 539     if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
 540       return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
 541
 542     return prime_mod[shift];
 543   }
 544 };
 545
 546 /*
 547  * hb_map_t
 548  */
 549
 550 struct hb_map_t : hb_hashmap_t<hb_codepoint_t,
 551                                hb_codepoint_t,
 552                                true>
 553 {
 554   using hashmap = hb_hashmap_t<hb_codepoint_t,
 555                                hb_codepoint_t,
 556                                true>;
 557
 558   ~hb_map_t () = default;
 559   hb_map_t () : hashmap () {}
 560   hb_map_t (const hb_map_t &o) : hashmap ((hashmap &) o) {}
 561   hb_map_t (hb_map_t &&o) : hashmap (std::move ((hashmap &) o)) {}
 562   hb_map_t& operator= (const hb_map_t&) = default;
 563   hb_map_t& operator= (hb_map_t&&) = default;
 564   hb_map_t (std::initializer_list<hb_codepoint_pair_t> lst) : hashmap (lst) {}
 565   template <typename Iterable,
 566             hb_requires (hb_is_iterable (Iterable))>
 567   hb_map_t (const Iterable &o) : hashmap (o) {}
 568 };
 569
 570
 571 #endif /* HB_MAP_HH */