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