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
  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);
  43   hb_hashmap_t ()  { init (); }
  44   ~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
  55     void clear () { key = kINVALID; value = vINVALID; hash = 0; }
  56
  57     bool operator == (K o) { return hb_deref (key) == hb_deref (o); }
  58     bool operator == (const item_t &o) { return *this == o.key; }
  59     bool is_unused () const    { return key == kINVALID; }
  60     bool is_tombstone () const { return key != kINVALID && value == vINVALID; }
  61     bool is_real () const { return key != kINVALID && value != vINVALID; }
  62     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
  73   void init_shallow ()
  74   {
  75     successful = true;
  76     population = occupancy = 0;
  77     mask = 0;
  78     prime = 0;
  79     items = nullptr;
  80   }
  81   void init ()
  82   {
  83     hb_object_init (this);
  84     init_shallow ();
  85   }
  86   void fini_shallow ()
  87   {
  88     free (items);
  89     items = nullptr;
  90     population = occupancy = 0;
  91   }
  92   void fini ()
  93   {
  94     hb_object_fini (this);
  95     fini_shallow ();
  96   }
  97
  98   void reset ()
  99   {
 100     if (unlikely (hb_object_is_immutable (this)))
 101       return;
 102     successful = true;
 103     clear ();
 104   }
 105
 106   bool in_error () const { return !successful; }
 107
 108   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
 146   void set (K key, V value)
 147   {
 148     set_with_hash (key, hb_hash (key), value);
 149   }
 150
 151   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
 158   void del (K key) { set (key, vINVALID); }
 159
 160   /* Has interface. */
 161   static constexpr V SENTINEL = vINVALID;
 162   typedef V value_t;
 163   value_t operator [] (K k) const { return get (k); }
 164   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. */
 171   V operator () (K k) const { return get (k); }
 172
 173   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
 185   bool is_empty () const { return population == 0; }
 186
 187   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& operator << (const hb_pair_t<K, V>& v)
 215   { set (v.first, v.second); return *this; }
 216
 217   protected:
 218
 219   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
 245   unsigned int bucket_for (K key) const
 246   {
 247     return bucket_for_hash (key, hb_hash (key));
 248   }
 249
 250   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
 266   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 */