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
37template <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>
40struct 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<K, V, kINVALID, vINVALID>& 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
322struct 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