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 == (const 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 for (auto &_ : hb_iter (new_items, new_size))
121 _.clear ();
122
123 unsigned int old_size = mask + 1;
124 item_t *old_items = items;
125
126 /* Switch to new, empty, array. */
127 population = occupancy = 0;
128 mask = new_size - 1;
129 prime = prime_for (power);
130 items = new_items;
131
132 /* Insert back old items. */
133 if (old_items)
134 for (unsigned int i = 0; i < old_size; i++)
135 if (old_items[i].is_real ())
136 set_with_hash (old_items[i].key,
137 old_items[i].hash,
138 old_items[i].value);
139
140 free (old_items);
141
142 return true;
143 }
144
145 void set (K key, V value)
146 {
147 set_with_hash (key, hb_hash (key), value);
148 }
149
150 V get (K key) const
151 {
152 if (unlikely (!items)) return vINVALID;
153 unsigned int i = bucket_for (key);
154 return items[i].is_real () && items[i] == key ? items[i].value : vINVALID;
155 }
156
157 void del (K key) { set (key, vINVALID); }
158
159 /* Has interface. */
160 static constexpr V SENTINEL = vINVALID;
161 typedef V value_t;
162 value_t operator [] (K k) const { return get (k); }
163 bool has (K k, V *vp = nullptr) const
164 {
165 V v = (*this)[k];
166 if (vp) *vp = v;
167 return v != SENTINEL;
168 }
169 /* Projection. */
170 V operator () (K k) const { return get (k); }
171
172 void clear ()
173 {
174 if (unlikely (hb_object_is_immutable (this)))
175 return;
176 if (items)
177 for (auto &_ : hb_iter (items, mask + 1))
178 _.clear ();
179
180 population = occupancy = 0;
181 }
182
183 bool is_empty () const { return population == 0; }
184
185 unsigned int get_population () const { return population; }
186
187 /*
188 * Iterator
189 */
190 auto iter () const HB_AUTO_RETURN
191 (
192 + hb_array (items, mask ? mask + 1 : 0)
193 | hb_filter (&item_t::is_real)
194 | hb_map (&item_t::get_pair)
195 )
196 auto keys () const HB_AUTO_RETURN
197 (
198 + hb_array (items, mask ? mask + 1 : 0)
199 | hb_filter (&item_t::is_real)
200 | hb_map (&item_t::key)
201 | hb_map (hb_ridentity)
202 )
203 auto values () const HB_AUTO_RETURN
204 (
205 + hb_array (items, mask ? mask + 1 : 0)
206 | hb_filter (&item_t::is_real)
207 | hb_map (&item_t::value)
208 | hb_map (hb_ridentity)
209 )
210
211 /* Sink interface. */
212 hb_hashmap_t& operator << (const hb_pair_t<K, V>& v)
213 { set (v.first, v.second); return *this; }
214
215 protected:
216
217 void set_with_hash (K key, uint32_t hash, V value)
218 {
219 if (unlikely (!successful)) return;
220 if (unlikely (key == kINVALID)) return;
221 if ((occupancy + occupancy / 2) >= mask && !resize ()) return;
222 unsigned int i = bucket_for_hash (key, hash);
223
224 if (value == vINVALID && items[i].key != key)
225 return; /* Trying to delete non-existent key. */
226
227 if (!items[i].is_unused ())
228 {
229 occupancy--;
230 if (items[i].is_tombstone ())
231 population--;
232 }
233
234 items[i].key = key;
235 items[i].value = value;
236 items[i].hash = hash;
237
238 occupancy++;
239 if (!items[i].is_tombstone ())
240 population++;
241 }
242
243 unsigned int bucket_for (K key) const
244 {
245 return bucket_for_hash (key, hb_hash (key));
246 }
247
248 unsigned int bucket_for_hash (K key, uint32_t hash) const
249 {
250 unsigned int i = hash % prime;
251 unsigned int step = 0;
252 unsigned int tombstone = (unsigned) -1;
253 while (!items[i].is_unused ())
254 {
255 if (items[i].hash == hash && items[i] == key)
256 return i;
257 if (tombstone == (unsigned) -1 && items[i].is_tombstone ())
258 tombstone = i;
259 i = (i + ++step) & mask;
260 }
261 return tombstone == (unsigned) -1 ? i : tombstone;
262 }
263
264 static unsigned int prime_for (unsigned int shift)
265 {
266 /* Following comment and table copied from glib. */
267 /* Each table size has an associated prime modulo (the first prime
268 * lower than the table size) used to find the initial bucket. Probing
269 * then works modulo 2^n. The prime modulo is necessary to get a
270 * good distribution with poor hash functions.
271 */
272 /* Not declaring static to make all kinds of compilers happy... */
273 /*static*/ const unsigned int prime_mod [32] =
274 {
275 1, /* For 1 << 0 */
276 2,
277 3,
278 7,
279 13,
280 31,
281 61,
282 127,
283 251,
284 509,
285 1021,
286 2039,
287 4093,
288 8191,
289 16381,
290 32749,
291 65521, /* For 1 << 16 */
292 131071,
293 262139,
294 524287,
295 1048573,
296 2097143,
297 4194301,
298 8388593,
299 16777213,
300 33554393,
301 67108859,
302 134217689,
303 268435399,
304 536870909,
305 1073741789,
306 2147483647 /* For 1 << 31 */
307 };
308
309 if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
310 return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
311
312 return prime_mod[shift];
313 }
314};
315
316/*
317 * hb_map_t
318 */
319
320struct hb_map_t : hb_hashmap_t<hb_codepoint_t,
321 hb_codepoint_t,
322 HB_MAP_VALUE_INVALID,
323 HB_MAP_VALUE_INVALID> {};
324
325
326#endif /* HB_MAP_HH */
327