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 == (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     if (unlikely (hb_object_is_immutable (this)))
101       return;
102     successful = true;
103     clear ();
104   }
105 
in_errorhb_hashmap_t106   bool in_error () const { return !successful; }
107 
resizehb_hashmap_t108   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 
sethb_hashmap_t146   void set (K key, V value)
147   {
148     set_with_hash (key, hb_hash (key), value);
149   }
150 
gethb_hashmap_t151   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 
delhb_hashmap_t158   void del (K key) { set (key, vINVALID); }
159 
160   /* Has interface. */
161   static constexpr V SENTINEL = vINVALID;
162   typedef V value_t;
operator []hb_hashmap_t163   value_t operator [] (K k) const { return get (k); }
hashb_hashmap_t164   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. */
operator ()hb_hashmap_t171   V operator () (K k) const { return get (k); }
172 
clearhb_hashmap_t173   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 
is_emptyhb_hashmap_t185   bool is_empty () const { return population == 0; }
186 
get_populationhb_hashmap_t187   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<K, V, kINVALID, vINVALID>& operator << (const hb_pair_t<K, V>& v)
215   { set (v.first, v.second); return *this; }
216 
217   protected:
218 
set_with_hashhb_hashmap_t219   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 
bucket_forhb_hashmap_t245   unsigned int bucket_for (K key) const
246   {
247     return bucket_for_hash (key, hb_hash (key));
248   }
249 
bucket_for_hashhb_hashmap_t250   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 
prime_forhb_hashmap_t266   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 */
329