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