50826
|
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 |
|
54232
|
27 |
#ifndef HB_MAP_HH
|
|
28 |
#define HB_MAP_HH
|
50826
|
29 |
|
54232
|
30 |
#include "hb.hh"
|
50826
|
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 |
{
|
54232
|
47 |
HB_NO_COPY_ASSIGN (hb_map_t);
|
|
48 |
hb_map_t () { init (); }
|
|
49 |
~hb_map_t () { fini (); }
|
|
50 |
|
50826
|
51 |
struct item_t
|
|
52 |
{
|
|
53 |
hb_codepoint_t key;
|
|
54 |
hb_codepoint_t value;
|
|
55 |
|
54232
|
56 |
bool is_unused () const { return key == INVALID; }
|
|
57 |
bool is_tombstone () const { return key != INVALID && value == INVALID; }
|
50826
|
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 |
|
54232
|
68 |
void init_shallow ()
|
50826
|
69 |
{
|
|
70 |
successful = true;
|
|
71 |
population = occupancy = 0;
|
|
72 |
mask = 0;
|
|
73 |
prime = 0;
|
|
74 |
items = nullptr;
|
|
75 |
}
|
54232
|
76 |
void init ()
|
50826
|
77 |
{
|
|
78 |
hb_object_init (this);
|
|
79 |
init_shallow ();
|
|
80 |
}
|
54232
|
81 |
void fini_shallow ()
|
50826
|
82 |
{
|
|
83 |
free (items);
|
54232
|
84 |
items = nullptr;
|
50826
|
85 |
}
|
54232
|
86 |
void fini ()
|
50826
|
87 |
{
|
54232
|
88 |
population = occupancy = 0;
|
50826
|
89 |
hb_object_fini (this);
|
|
90 |
fini_shallow ();
|
|
91 |
}
|
|
92 |
|
54232
|
93 |
bool in_error () const { return !successful; }
|
|
94 |
|
|
95 |
bool resize ()
|
50826
|
96 |
{
|
|
97 |
if (unlikely (!successful)) return false;
|
|
98 |
|
54232
|
99 |
unsigned int power = hb_bit_storage (population * 2 + 8);
|
50826
|
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 |
|
54232
|
129 |
void set (hb_codepoint_t key, hb_codepoint_t value)
|
50826
|
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 |
}
|
54232
|
154 |
hb_codepoint_t get (hb_codepoint_t key) const
|
50826
|
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 |
|
54232
|
161 |
void del (hb_codepoint_t key) { set (key, INVALID); }
|
50826
|
162 |
|
54232
|
163 |
bool has (hb_codepoint_t key) const
|
|
164 |
{ return get (key) != INVALID; }
|
|
165 |
|
|
166 |
hb_codepoint_t operator [] (unsigned int key) const
|
50826
|
167 |
{ return get (key); }
|
|
168 |
|
54232
|
169 |
static constexpr hb_codepoint_t INVALID = HB_MAP_VALUE_INVALID;
|
50826
|
170 |
|
54232
|
171 |
void clear ()
|
50826
|
172 |
{
|
|
173 |
memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t));
|
|
174 |
population = occupancy = 0;
|
|
175 |
}
|
|
176 |
|
54232
|
177 |
bool is_empty () const { return population == 0; }
|
50826
|
178 |
|
54232
|
179 |
unsigned int get_population () const { return population; }
|
50826
|
180 |
|
|
181 |
protected:
|
|
182 |
|
54232
|
183 |
unsigned int bucket_for (hb_codepoint_t key) const
|
50826
|
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 |
|
54232
|
199 |
static unsigned int prime_for (unsigned int shift)
|
50826
|
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 |
|
54232
|
252 |
#endif /* HB_MAP_HH */
|