1 | /* |
2 | * Copyright © 2011 Red Hat Inc. |
3 | * |
4 | * This library is free software; you can redistribute it and/or |
5 | * modify it under the terms of the GNU Lesser General Public |
6 | * License as published by the Free Software Foundation; either |
7 | * version 2.1 of the License, or (at your option) any later version. |
8 | * |
9 | * This library is distributed in the hope that it will be useful, |
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | * Lesser General Public License for more details. |
13 | * |
14 | * You should have received a copy of the GNU Lesser General Public |
15 | * License along with this library. If not, see <http://www.gnu.org/licenses/>. |
16 | * |
17 | * Authors: Benjamin Otte <otte@gnome.org> |
18 | */ |
19 | |
20 | #include <config.h> |
21 | |
22 | #include "gtkallocatedbitmaskprivate.h" |
23 | #include "gtkprivate.h" |
24 | |
25 | |
26 | #define VALUE_TYPE gsize |
27 | |
28 | #define VALUE_SIZE_BITS (sizeof (VALUE_TYPE) * 8) |
29 | #define VALUE_BIT(idx) (((VALUE_TYPE) 1) << (idx)) |
30 | #define ALL_BITS (~((VALUE_TYPE) 0)) |
31 | |
32 | struct _GtkBitmask { |
33 | gsize len; |
34 | VALUE_TYPE data[1]; |
35 | }; |
36 | |
37 | #define ENSURE_ALLOCATED(mask, heap_mask) G_STMT_START { \ |
38 | if (!_gtk_bitmask_is_allocated (mask)) \ |
39 | { \ |
40 | heap_mask.data[0] = _gtk_bitmask_to_bits (mask); \ |
41 | heap_mask.len = heap_mask.data[0] ? 1 : 0; \ |
42 | mask = &heap_mask; \ |
43 | } \ |
44 | } G_STMT_END |
45 | |
46 | static GtkBitmask * |
47 | gtk_allocated_bitmask_resize (GtkBitmask *mask, |
48 | gsize size) G_GNUC_WARN_UNUSED_RESULT; |
49 | static GtkBitmask * |
50 | gtk_allocated_bitmask_resize (GtkBitmask *mask, |
51 | gsize size) |
52 | { |
53 | gsize i; |
54 | |
55 | if (size == mask->len) |
56 | return mask; |
57 | |
58 | mask = g_realloc (mem: mask, n_bytes: sizeof (GtkBitmask) + sizeof(VALUE_TYPE) * (size - 1)); |
59 | |
60 | for (i = mask->len; i < size; i++) |
61 | mask->data[i] = 0; |
62 | |
63 | mask->len = size; |
64 | |
65 | return mask; |
66 | } |
67 | |
68 | static GtkBitmask * |
69 | gtk_allocated_bitmask_new_for_bits (gsize bits) |
70 | { |
71 | GtkBitmask *mask; |
72 | |
73 | mask = g_malloc (n_bytes: sizeof (GtkBitmask)); |
74 | mask->len = bits ? 1 : 0; |
75 | mask->data[0] = bits; |
76 | |
77 | return mask; |
78 | } |
79 | |
80 | static GtkBitmask * |
81 | gtk_bitmask_ensure_allocated (GtkBitmask *mask) |
82 | { |
83 | if (_gtk_bitmask_is_allocated (mask)) |
84 | return mask; |
85 | else |
86 | return gtk_allocated_bitmask_new_for_bits (_gtk_bitmask_to_bits (mask)); |
87 | } |
88 | |
89 | GtkBitmask * |
90 | _gtk_allocated_bitmask_copy (const GtkBitmask *mask) |
91 | { |
92 | GtkBitmask *copy; |
93 | |
94 | gtk_internal_return_val_if_fail (mask != NULL, NULL); |
95 | |
96 | copy = gtk_allocated_bitmask_new_for_bits (bits: 0); |
97 | |
98 | return _gtk_allocated_bitmask_union (mask: copy, other: mask); |
99 | } |
100 | |
101 | void |
102 | _gtk_allocated_bitmask_free (GtkBitmask *mask) |
103 | { |
104 | gtk_internal_return_if_fail (mask != NULL); |
105 | |
106 | g_free (mem: mask); |
107 | } |
108 | |
109 | char * |
110 | _gtk_allocated_bitmask_to_string (const GtkBitmask *mask) |
111 | { |
112 | GString *str = g_string_new (NULL); |
113 | |
114 | _gtk_allocated_bitmask_print (mask, string: str); |
115 | |
116 | return g_string_free (string: str, FALSE); |
117 | } |
118 | |
119 | void |
120 | _gtk_allocated_bitmask_print (const GtkBitmask *mask, |
121 | GString *string) |
122 | { |
123 | GtkBitmask mask_allocated; |
124 | int i; |
125 | |
126 | gtk_internal_return_if_fail (mask != NULL); |
127 | gtk_internal_return_if_fail (string != NULL); |
128 | |
129 | ENSURE_ALLOCATED (mask, mask_allocated); |
130 | |
131 | for (i = mask->len * VALUE_SIZE_BITS - 1; i >= 0; i--) |
132 | { |
133 | if (_gtk_allocated_bitmask_get (mask, index_: i)) |
134 | break; |
135 | } |
136 | |
137 | if (i < 0) |
138 | { |
139 | g_string_append_c (string, '0'); |
140 | return; |
141 | } |
142 | |
143 | for (; i >= 0; i--) |
144 | { |
145 | g_string_append_c (string, _gtk_allocated_bitmask_get (mask, i) ? '1' : '0'); |
146 | } |
147 | } |
148 | |
149 | /* NB: Call this function whenever the |
150 | * array might have become too large. |
151 | * _gtk_allocated_bitmask_is_empty() depends on this. |
152 | */ |
153 | static GtkBitmask * |
154 | gtk_allocated_bitmask_shrink (GtkBitmask *mask) G_GNUC_WARN_UNUSED_RESULT; |
155 | static GtkBitmask * |
156 | gtk_allocated_bitmask_shrink (GtkBitmask *mask) |
157 | { |
158 | guint i; |
159 | |
160 | for (i = mask->len; i; i--) |
161 | { |
162 | if (mask->data[i - 1]) |
163 | break; |
164 | } |
165 | |
166 | if (i == 0 || |
167 | (i == 1 && mask->data[0] < VALUE_BIT (GTK_BITMASK_N_DIRECT_BITS))) |
168 | { |
169 | GtkBitmask *result = _gtk_bitmask_from_bits (i == 0 ? 0 : mask->data[0]); |
170 | _gtk_allocated_bitmask_free (mask); |
171 | return result; |
172 | } |
173 | |
174 | return gtk_allocated_bitmask_resize (mask, size: i); |
175 | } |
176 | |
177 | GtkBitmask * |
178 | _gtk_allocated_bitmask_intersect (GtkBitmask *mask, |
179 | const GtkBitmask *other) |
180 | { |
181 | GtkBitmask other_allocated; |
182 | guint i; |
183 | |
184 | gtk_internal_return_val_if_fail (mask != NULL, NULL); |
185 | gtk_internal_return_val_if_fail (other != NULL, NULL); |
186 | |
187 | mask = gtk_bitmask_ensure_allocated (mask); |
188 | ENSURE_ALLOCATED (other, other_allocated); |
189 | |
190 | for (i = 0; i < MIN (mask->len, other->len); i++) |
191 | { |
192 | mask->data[i] &= other->data[i]; |
193 | } |
194 | for (; i < mask->len; i++) |
195 | { |
196 | mask->data[i] = 0; |
197 | } |
198 | |
199 | return gtk_allocated_bitmask_shrink (mask); |
200 | } |
201 | |
202 | GtkBitmask * |
203 | _gtk_allocated_bitmask_union (GtkBitmask *mask, |
204 | const GtkBitmask *other) |
205 | { |
206 | GtkBitmask other_allocated; |
207 | guint i; |
208 | |
209 | gtk_internal_return_val_if_fail (mask != NULL, NULL); |
210 | gtk_internal_return_val_if_fail (other != NULL, NULL); |
211 | |
212 | mask = gtk_bitmask_ensure_allocated (mask); |
213 | ENSURE_ALLOCATED (other, other_allocated); |
214 | |
215 | mask = gtk_allocated_bitmask_resize (mask, MAX (mask->len, other->len)); |
216 | for (i = 0; i < other->len; i++) |
217 | { |
218 | mask->data[i] |= other->data[i]; |
219 | } |
220 | |
221 | return mask; |
222 | } |
223 | |
224 | GtkBitmask * |
225 | _gtk_allocated_bitmask_subtract (GtkBitmask *mask, |
226 | const GtkBitmask *other) |
227 | { |
228 | GtkBitmask other_allocated; |
229 | guint i, len; |
230 | |
231 | gtk_internal_return_val_if_fail (mask != NULL, NULL); |
232 | gtk_internal_return_val_if_fail (other != NULL, NULL); |
233 | |
234 | mask = gtk_bitmask_ensure_allocated (mask); |
235 | ENSURE_ALLOCATED (other, other_allocated); |
236 | |
237 | len = MIN (mask->len, other->len); |
238 | for (i = 0; i < len; i++) |
239 | { |
240 | mask->data[i] &= ~other->data[i]; |
241 | } |
242 | |
243 | return gtk_allocated_bitmask_shrink (mask); |
244 | } |
245 | |
246 | static inline void |
247 | gtk_allocated_bitmask_indexes (guint index_, |
248 | guint *array_index, |
249 | guint *bit_index) |
250 | { |
251 | *array_index = index_ / VALUE_SIZE_BITS; |
252 | *bit_index = index_ % VALUE_SIZE_BITS; |
253 | } |
254 | |
255 | gboolean |
256 | _gtk_allocated_bitmask_get (const GtkBitmask *mask, |
257 | guint index_) |
258 | { |
259 | guint array_index, bit_index; |
260 | |
261 | gtk_internal_return_val_if_fail (mask != NULL, FALSE); |
262 | |
263 | gtk_allocated_bitmask_indexes (index_, array_index: &array_index, bit_index: &bit_index); |
264 | |
265 | if (array_index >= mask->len) |
266 | return FALSE; |
267 | |
268 | return (mask->data[array_index] & VALUE_BIT (bit_index)) ? TRUE : FALSE; |
269 | } |
270 | |
271 | GtkBitmask * |
272 | _gtk_allocated_bitmask_set (GtkBitmask *mask, |
273 | guint index_, |
274 | gboolean value) |
275 | { |
276 | guint array_index, bit_index; |
277 | |
278 | gtk_internal_return_val_if_fail (mask != NULL, NULL); |
279 | |
280 | mask = gtk_bitmask_ensure_allocated (mask); |
281 | gtk_allocated_bitmask_indexes (index_, array_index: &array_index, bit_index: &bit_index); |
282 | |
283 | if (value) |
284 | { |
285 | if (array_index >= mask->len) |
286 | mask = gtk_allocated_bitmask_resize (mask, size: array_index + 1); |
287 | |
288 | mask->data[array_index] |= VALUE_BIT (bit_index); |
289 | } |
290 | else |
291 | { |
292 | if (array_index < mask->len) |
293 | { |
294 | mask->data[array_index] &= ~ VALUE_BIT (bit_index); |
295 | mask = gtk_allocated_bitmask_shrink (mask); |
296 | } |
297 | } |
298 | |
299 | return mask; |
300 | } |
301 | |
302 | GtkBitmask * |
303 | _gtk_allocated_bitmask_invert_range (GtkBitmask *mask, |
304 | guint start, |
305 | guint end) |
306 | { |
307 | guint i; |
308 | guint start_word, start_bit; |
309 | guint end_word, end_bit; |
310 | |
311 | gtk_internal_return_val_if_fail (mask != NULL, NULL); |
312 | gtk_internal_return_val_if_fail (start < end, NULL); |
313 | |
314 | mask = gtk_bitmask_ensure_allocated (mask); |
315 | |
316 | gtk_allocated_bitmask_indexes (index_: start, array_index: &start_word, bit_index: &start_bit); |
317 | gtk_allocated_bitmask_indexes (index_: end - 1, array_index: &end_word, bit_index: &end_bit); |
318 | |
319 | if (end_word >= mask->len) |
320 | mask = gtk_allocated_bitmask_resize (mask, size: end_word + 1); |
321 | |
322 | for (i = start_word; i <= end_word; i++) |
323 | mask->data[i] ^= ALL_BITS; |
324 | mask->data[start_word] ^= (((VALUE_TYPE) 1) << start_bit) - 1; |
325 | if (end_bit != VALUE_SIZE_BITS - 1) |
326 | mask->data[end_word] ^= ALL_BITS << (end_bit + 1); |
327 | |
328 | return gtk_allocated_bitmask_shrink (mask); |
329 | } |
330 | |
331 | gboolean |
332 | _gtk_allocated_bitmask_equals (const GtkBitmask *mask, |
333 | const GtkBitmask *other) |
334 | { |
335 | guint i; |
336 | |
337 | gtk_internal_return_val_if_fail (mask != NULL, FALSE); |
338 | gtk_internal_return_val_if_fail (other != NULL, FALSE); |
339 | |
340 | if (mask->len != other->len) |
341 | return FALSE; |
342 | |
343 | for (i = 0; i < mask->len; i++) |
344 | { |
345 | if (mask->data[i] != other->data[i]) |
346 | return FALSE; |
347 | } |
348 | |
349 | return TRUE; |
350 | } |
351 | |
352 | gboolean |
353 | _gtk_allocated_bitmask_intersects (const GtkBitmask *mask, |
354 | const GtkBitmask *other) |
355 | { |
356 | GtkBitmask mask_allocated, other_allocated; |
357 | int i; |
358 | |
359 | gtk_internal_return_val_if_fail (mask != NULL, FALSE); |
360 | gtk_internal_return_val_if_fail (other != NULL, FALSE); |
361 | |
362 | ENSURE_ALLOCATED (mask, mask_allocated); |
363 | ENSURE_ALLOCATED (other, other_allocated); |
364 | |
365 | for (i = MIN (mask->len, other->len) - 1; i >= 0; i--) |
366 | { |
367 | if (mask->data[i] & other->data[i]) |
368 | return TRUE; |
369 | } |
370 | |
371 | return FALSE; |
372 | } |
373 | |
374 | |