src/hb-map-private.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_PRIVATE_HH
  28 #define HB_MAP_PRIVATE_HH
  29
  30 #include "hb-private.hh"
  31 #include "hb-object-private.hh"
  32
  33
  34 template <typename T>
  35 inline uint32_t Hash (const T &v)
  36 {
  37   /* Knuth's multiplicative method: */
  38   return (uint32_t) v * 2654435761u;
  39 }
  40
  41
  42 /*
  43  * hb_map_t
  44  */
  45
  46 struct hb_map_t
  47 {
  48   struct item_t
  49   {
  50     hb_codepoint_t key;
  51     hb_codepoint_t value;
  52
  53     inline bool is_unused (void) const { return key == INVALID; }
  54     inline bool is_tombstone (void) const { return key != INVALID && value == INVALID; }
  55   };
  56
  57   hb_object_header_t header;
  58   bool successful; /* Allocations successful */
  59   unsigned int population; /* Not including tombstones. */
  60   unsigned int occupancy; /* Including tombstones. */
  61   unsigned int mask;
  62   unsigned int prime;
  63   item_t *items;
  64
  65   inline void init_shallow (void)
  66   {
  67     successful = true;
  68     population = occupancy = 0;
  69     mask = 0;
  70     prime = 0;
  71     items = nullptr;
  72   }
  73   inline void init (void)
  74   {
  75     hb_object_init (this);
  76     init_shallow ();
  77   }
  78   inline void fini_shallow (void)
  79   {
  80     free (items);
  81   }
  82   inline void fini (void)
  83   {
  84     hb_object_fini (this);
  85     fini_shallow ();
  86   }
  87
  88   inline bool resize (void)
  89   {
  90     if (unlikely (!successful)) return false;
  91
  92     unsigned int power = _hb_bit_storage (population * 2 + 8);
  93     unsigned int new_size = 1u << power;
  94     item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t));
  95     if (unlikely (!new_items))
  96     {
  97       successful = false;
  98       return false;
  99     }
 100     memset (new_items, 0xFF, (size_t) new_size * sizeof (item_t));
 101
 102     unsigned int old_size = mask + 1;
 103     item_t *old_items = items;
 104
 105     /* Switch to new, empty, array. */
 106     population = occupancy = 0;
 107     mask = new_size - 1;
 108     prime = prime_for (power);
 109     items = new_items;
 110
 111     /* Insert back old items. */
 112     if (old_items)
 113       for (unsigned int i = 0; i < old_size; i++)
 114         if (old_items[i].key != INVALID && old_items[i].value != INVALID)
 115           set (old_items[i].key, old_items[i].value);
 116
 117     free (old_items);
 118
 119     return true;
 120   }
 121
 122   inline void set (hb_codepoint_t key, hb_codepoint_t value)
 123   {
 124     if (unlikely (!successful)) return;
 125     if (unlikely (key == INVALID)) return;
 126     if ((occupancy + occupancy / 2) >= mask && !resize ()) return;
 127     unsigned int i = bucket_for (key);
 128
 129     if (value == INVALID && items[i].key != key)
 130       return; /* Trying to delete non-existent key. */
 131
 132     if (!items[i].is_unused ())
 133     {
 134       occupancy--;
 135       if (items[i].is_tombstone ())
 136         population--;
 137     }
 138
 139     items[i].key = key;
 140     items[i].value = value;
 141
 142     occupancy++;
 143     if (!items[i].is_tombstone ())
 144       population++;
 145
 146   }
 147   inline hb_codepoint_t get (hb_codepoint_t key) const
 148   {
 149     if (unlikely (!items)) return INVALID;
 150     unsigned int i = bucket_for (key);
 151     return items[i].key == key ? items[i].value : INVALID;
 152   }
 153
 154   inline void del (hb_codepoint_t key)
 155   {
 156     set (key, INVALID);
 157   }
 158   inline bool has (hb_codepoint_t key) const
 159   {
 160     return get (key) != INVALID;
 161   }
 162
 163   inline hb_codepoint_t operator [] (unsigned int key) const
 164   { return get (key); }
 165
 166   static const hb_codepoint_t INVALID = HB_MAP_VALUE_INVALID;
 167
 168   inline void clear (void)
 169   {
 170     memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t));
 171     population = occupancy = 0;
 172   }
 173
 174   inline bool is_empty (void) const
 175   {
 176     return population != 0;
 177   }
 178
 179   inline unsigned int get_population () const
 180   {
 181     return population;
 182   }
 183
 184   protected:
 185
 186   inline unsigned int bucket_for (hb_codepoint_t key) const
 187   {
 188     unsigned int i = Hash (key) % prime;
 189     unsigned int step = 0;
 190     unsigned int tombstone = INVALID;
 191     while (!items[i].is_unused ())
 192     {
 193       if (items[i].key == key)
 194         return i;
 195       if (tombstone == INVALID && items[i].is_tombstone ())
 196         tombstone = i;
 197       i = (i + ++step) & mask;
 198     }
 199     return tombstone == INVALID ? i : tombstone;
 200   }
 201
 202   static inline unsigned int prime_for (unsigned int shift)
 203   {
 204     /* Following comment and table copied from glib. */
 205     /* Each table size has an associated prime modulo (the first prime
 206      * lower than the table size) used to find the initial bucket. Probing
 207      * then works modulo 2^n. The prime modulo is necessary to get a
 208      * good distribution with poor hash functions.
 209      */
 210     /* Not declaring static to make all kinds of compilers happy... */
 211     /*static*/ const unsigned int prime_mod [32] =
 212     {
 213       1,          /* For 1 << 0 */
 214       2,
 215       3,
 216       7,
 217       13,
 218       31,
 219       61,
 220       127,
 221       251,
 222       509,
 223       1021,
 224       2039,
 225       4093,
 226       8191,
 227       16381,
 228       32749,
 229       65521,      /* For 1 << 16 */
 230       131071,
 231       262139,
 232       524287,
 233       1048573,
 234       2097143,
 235       4194301,
 236       8388593,
 237       16777213,
 238       33554393,
 239       67108859,
 240       134217689,
 241       268435399,
 242       536870909,
 243       1073741789,
 244       2147483647  /* For 1 << 31 */
 245     };
 246
 247     if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
 248       return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
 249
 250     return prime_mod[shift];
 251   }
 252 };
 253
 254
 255 #endif /* HB_MAP_PRIVATE_HH */