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 template <typename T>
34 inline uint32_t Hash (const T &v)
35 {
36 /* Knuth's multiplicative method: */
37 return (uint32_t) v * 2654435761u;
38 }
39
40
41 /*
42 * hb_map_t
43 */
44
45 struct hb_map_t
46 {
47 HB_NO_COPY_ASSIGN (hb_map_t);
48 hb_map_t () { init (); }
49 ~hb_map_t () { fini (); }
50
51 struct item_t
52 {
53 hb_codepoint_t key;
54 hb_codepoint_t value;
55
56 bool is_unused () const { return key == INVALID; }
57 bool is_tombstone () const { return key != INVALID && value == INVALID; }
58 };
59
60 hb_object_header_t header;
61 bool successful; /* Allocations successful */
62 unsigned int population; /* Not including tombstones. */
63 unsigned int occupancy; /* Including tombstones. */
64 unsigned int mask;
65 unsigned int prime;
66 item_t *items;
67
68 void init_shallow ()
69 {
70 successful = true;
71 population = occupancy = 0;
72 mask = 0;
73 prime = 0;
74 items = nullptr;
75 }
76 void init ()
77 {
78 hb_object_init (this);
79 init_shallow ();
80 }
81 void fini_shallow ()
82 {
83 free (items);
84 items = nullptr;
85 }
86 void fini ()
87 {
88 population = occupancy = 0;
89 hb_object_fini (this);
90 fini_shallow ();
91 }
92
93 bool in_error () const { return !successful; }
94
95 bool resize ()
96 {
97 if (unlikely (!successful)) return false;
98
99 unsigned int power = hb_bit_storage (population * 2 + 8);
100 unsigned int new_size = 1u << power;
101 item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t));
102 if (unlikely (!new_items))
103 {
104 successful = false;
105 return false;
106 }
107 memset (new_items, 0xFF, (size_t) new_size * sizeof (item_t));
108
109 unsigned int old_size = mask + 1;
110 item_t *old_items = items;
111
112 /* Switch to new, empty, array. */
113 population = occupancy = 0;
114 mask = new_size - 1;
115 prime = prime_for (power);
116 items = new_items;
117
118 /* Insert back old items. */
119 if (old_items)
120 for (unsigned int i = 0; i < old_size; i++)
121 if (old_items[i].key != INVALID && old_items[i].value != INVALID)
122 set (old_items[i].key, old_items[i].value);
123
124 free (old_items);
125
126 return true;
127 }
128
129 void set (hb_codepoint_t key, hb_codepoint_t value)
130 {
131 if (unlikely (!successful)) return;
132 if (unlikely (key == INVALID)) return;
133 if ((occupancy + occupancy / 2) >= mask && !resize ()) return;
134 unsigned int i = bucket_for (key);
135
136 if (value == INVALID && items[i].key != key)
137 return; /* Trying to delete non-existent key. */
138
139 if (!items[i].is_unused ())
140 {
141 occupancy--;
142 if (items[i].is_tombstone ())
143 population--;
144 }
145
146 items[i].key = key;
147 items[i].value = value;
148
149 occupancy++;
150 if (!items[i].is_tombstone ())
151 population++;
152
153 }
154 hb_codepoint_t get (hb_codepoint_t key) const
155 {
156 if (unlikely (!items)) return INVALID;
157 unsigned int i = bucket_for (key);
158 return items[i].key == key ? items[i].value : INVALID;
159 }
160
161 void del (hb_codepoint_t key) { set (key, INVALID); }
162
163 bool has (hb_codepoint_t key) const
164 { return get (key) != INVALID; }
165
166 hb_codepoint_t operator [] (unsigned int key) const
167 { return get (key); }
168
169 static constexpr hb_codepoint_t INVALID = HB_MAP_VALUE_INVALID;
170
171 void clear ()
172 {
173 memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t));
174 population = occupancy = 0;
175 }
176
177 bool is_empty () const { return population == 0; }
178
179 unsigned int get_population () const { return population; }
180
181 protected:
182
183 unsigned int bucket_for (hb_codepoint_t key) const
184 {
185 unsigned int i = Hash (key) % prime;
186 unsigned int step = 0;
187 unsigned int tombstone = INVALID;
188 while (!items[i].is_unused ())
189 {
190 if (items[i].key == key)
191 return i;
192 if (tombstone == INVALID && items[i].is_tombstone ())
193 tombstone = i;
194 i = (i + ++step) & mask;
195 }
196 return tombstone == INVALID ? i : tombstone;
197 }
198
199 static unsigned int prime_for (unsigned int shift)
200 {
201 /* Following comment and table copied from glib. */
202 /* Each table size has an associated prime modulo (the first prime
203 * lower than the table size) used to find the initial bucket. Probing
204 * then works modulo 2^n. The prime modulo is necessary to get a
205 * good distribution with poor hash functions.
206 */
207 /* Not declaring static to make all kinds of compilers happy... */
208 /*static*/ const unsigned int prime_mod [32] =
209 {
210 1, /* For 1 << 0 */
211 2,
212 3,
213 7,
214 13,
215 31,
216 61,
217 127,
218 251,
219 509,
220 1021,
221 2039,
222 4093,
223 8191,
224 16381,
225 32749,
226 65521, /* For 1 << 16 */
227 131071,
228 262139,
229 524287,
230 1048573,
231 2097143,
232 4194301,
233 8388593,
234 16777213,
235 33554393,
236 67108859,
237 134217689,
238 268435399,
239 536870909,
240 1073741789,
241 2147483647 /* For 1 << 31 */
242 };
243
244 if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
245 return prime_mod[ARRAY_LENGTH (prime_mod) - 1];
246
247 return prime_mod[shift];
248 }
249 };
250
251
252 #endif /* HB_MAP_HH */