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