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
32struct _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
46static GtkBitmask *
47gtk_allocated_bitmask_resize (GtkBitmask *mask,
48 gsize size) G_GNUC_WARN_UNUSED_RESULT;
49static GtkBitmask *
50gtk_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
68static GtkBitmask *
69gtk_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
80static GtkBitmask *
81gtk_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
89GtkBitmask *
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
101void
102_gtk_allocated_bitmask_free (GtkBitmask *mask)
103{
104 gtk_internal_return_if_fail (mask != NULL);
105
106 g_free (mem: mask);
107}
108
109char *
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
119void
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 */
153static GtkBitmask *
154gtk_allocated_bitmask_shrink (GtkBitmask *mask) G_GNUC_WARN_UNUSED_RESULT;
155static GtkBitmask *
156gtk_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
177GtkBitmask *
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
202GtkBitmask *
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
224GtkBitmask *
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
246static inline void
247gtk_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
255gboolean
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
271GtkBitmask *
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
302GtkBitmask *
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
331gboolean
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
352gboolean
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

source code of gtk/gtk/gtkallocatedbitmask.c