1 | /* |
2 | * Copyright © 2020 Benjamin Otte |
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 "gtkbitset.h" |
23 | |
24 | #include "roaring/roaring.c" |
25 | |
26 | /** |
27 | * GtkBitset: (ref-func gtk_bitset_ref) (unref-func gtk_bitset_unref) |
28 | * |
29 | * A `GtkBitset` represents a set of unsigned integers. |
30 | * |
31 | * Another name for this data structure is "bitmap". |
32 | * |
33 | * The current implementation is based on [roaring bitmaps](https://roaringbitmap.org/). |
34 | * |
35 | * A bitset allows adding a set of integers and provides support for set operations |
36 | * like unions, intersections and checks for equality or if a value is contained |
37 | * in the set. `GtkBitset` also contains various functions to query metadata about |
38 | * the bitset, such as the minimum or maximum values or its size. |
39 | * |
40 | * The fastest way to iterate values in a bitset is [struct@Gtk.BitsetIter]. |
41 | * |
42 | * The main use case for `GtkBitset` is implementing complex selections for |
43 | * [iface@Gtk.SelectionModel]. |
44 | */ |
45 | |
46 | struct _GtkBitset |
47 | { |
48 | int ref_count; |
49 | roaring_bitmap_t roaring; |
50 | }; |
51 | |
52 | |
53 | G_DEFINE_BOXED_TYPE (GtkBitset, gtk_bitset, |
54 | gtk_bitset_ref, |
55 | gtk_bitset_unref) |
56 | |
57 | /** |
58 | * gtk_bitset_ref: |
59 | * @self: (nullable): a `GtkBitset` |
60 | * |
61 | * Acquires a reference on the given `GtkBitset`. |
62 | * |
63 | * Returns: (transfer none): the `GtkBitset` with an additional reference |
64 | */ |
65 | GtkBitset * |
66 | gtk_bitset_ref (GtkBitset *self) |
67 | { |
68 | g_return_val_if_fail (self != NULL, NULL); |
69 | |
70 | self->ref_count += 1; |
71 | |
72 | return self; |
73 | } |
74 | |
75 | /** |
76 | * gtk_bitset_unref: |
77 | * @self: (nullable): a `GtkBitset` |
78 | * |
79 | * Releases a reference on the given `GtkBitset`. |
80 | * |
81 | * If the reference was the last, the resources associated to the @self are |
82 | * freed. |
83 | */ |
84 | void |
85 | gtk_bitset_unref (GtkBitset *self) |
86 | { |
87 | g_return_if_fail (self != NULL); |
88 | g_return_if_fail (self->ref_count > 0); |
89 | |
90 | self->ref_count -= 1; |
91 | if (self->ref_count > 0) |
92 | return; |
93 | |
94 | ra_clear (ra: &self->roaring.high_low_container); |
95 | g_slice_free (GtkBitset, self); |
96 | } |
97 | |
98 | /** |
99 | * gtk_bitset_contains: |
100 | * @self: a `GtkBitset` |
101 | * @value: the value to check |
102 | * |
103 | * Checks if the given @value has been added to @self |
104 | * |
105 | * Returns: %TRUE if @self contains @value |
106 | **/ |
107 | gboolean |
108 | gtk_bitset_contains (const GtkBitset *self, |
109 | guint value) |
110 | { |
111 | g_return_val_if_fail (self != NULL, FALSE); |
112 | |
113 | return roaring_bitmap_contains (r: &self->roaring, val: value); |
114 | } |
115 | |
116 | /** |
117 | * gtk_bitset_is_empty: |
118 | * @self: a `GtkBitset` |
119 | * |
120 | * Check if no value is contained in bitset. |
121 | * |
122 | * Returns: %TRUE if @self is empty |
123 | **/ |
124 | gboolean |
125 | gtk_bitset_is_empty (const GtkBitset *self) |
126 | { |
127 | g_return_val_if_fail (self != NULL, TRUE); |
128 | |
129 | return roaring_bitmap_is_empty (ra: &self->roaring); |
130 | } |
131 | |
132 | /** |
133 | * gtk_bitset_equals: |
134 | * @self: a `GtkBitset` |
135 | * @other: another `GtkBitset` |
136 | * |
137 | * Returns %TRUE if @self and @other contain the same values. |
138 | * |
139 | * Returns: %TRUE if @self and @other contain the same values |
140 | **/ |
141 | gboolean |
142 | gtk_bitset_equals (const GtkBitset *self, |
143 | const GtkBitset *other) |
144 | { |
145 | g_return_val_if_fail (self != NULL, other == NULL); |
146 | g_return_val_if_fail (other != NULL, FALSE); |
147 | |
148 | if (self == other) |
149 | return TRUE; |
150 | |
151 | return roaring_bitmap_equals (ra1: &self->roaring, ra2: &other->roaring); |
152 | } |
153 | |
154 | /** |
155 | * gtk_bitset_get_minimum: |
156 | * @self: a `GtkBitset` |
157 | * |
158 | * Returns the smallest value in @self. |
159 | * |
160 | * If @self is empty, `G_MAXUINT` is returned. |
161 | * |
162 | * Returns: The smallest value in @self |
163 | **/ |
164 | guint |
165 | gtk_bitset_get_minimum (const GtkBitset *self) |
166 | { |
167 | g_return_val_if_fail (self != NULL, G_MAXUINT); |
168 | |
169 | return roaring_bitmap_minimum (bm: &self->roaring); |
170 | } |
171 | |
172 | /** |
173 | * gtk_bitset_get_maximum: |
174 | * @self: a `GtkBitset` |
175 | * |
176 | * Returns the largest value in @self. |
177 | * |
178 | * If @self is empty, 0 is returned. |
179 | * |
180 | * Returns: The largest value in @self |
181 | **/ |
182 | guint |
183 | gtk_bitset_get_maximum (const GtkBitset *self) |
184 | { |
185 | g_return_val_if_fail (self != NULL, 0); |
186 | |
187 | return roaring_bitmap_maximum (bm: &self->roaring); |
188 | } |
189 | |
190 | /** |
191 | * gtk_bitset_get_size: |
192 | * @self: a `GtkBitset` |
193 | * |
194 | * Gets the number of values that were added to the set. |
195 | * |
196 | * For example, if the set is empty, 0 is returned. |
197 | * |
198 | * Note that this function returns a `guint64`, because when all |
199 | * values are set, the return value is `G_MAXUINT + 1`. Unless you |
200 | * are sure this cannot happen (it can't with `GListModel`), be sure |
201 | * to use a 64bit type. |
202 | * |
203 | * Returns: The number of values in the set. |
204 | */ |
205 | guint64 |
206 | gtk_bitset_get_size (const GtkBitset *self) |
207 | { |
208 | g_return_val_if_fail (self != NULL, 0); |
209 | |
210 | return roaring_bitmap_get_cardinality (ra: &self->roaring); |
211 | } |
212 | |
213 | /** |
214 | * gtk_bitset_get_size_in_range: |
215 | * @self: a `GtkBitset` |
216 | * @first: the first element to include |
217 | * @last: the last element to include |
218 | * |
219 | * Gets the number of values that are part of the set from @first to @last |
220 | * (inclusive). |
221 | * |
222 | * Note that this function returns a `guint64`, because when all values are |
223 | * set, the return value is `G_MAXUINT + 1`. Unless you are sure this cannot |
224 | * happen (it can't with `GListModel`), be sure to use a 64bit type. |
225 | * |
226 | * Returns: The number of values in the set from @first to @last. |
227 | */ |
228 | guint64 |
229 | gtk_bitset_get_size_in_range (const GtkBitset *self, |
230 | guint first, |
231 | guint last) |
232 | { |
233 | g_return_val_if_fail (self != NULL, 0); |
234 | g_return_val_if_fail (last >= first, 0); |
235 | |
236 | return roaring_bitmap_range_cardinality (ra: &self->roaring, range_start: first, range_end: ((uint64_t) last) + 1); |
237 | } |
238 | |
239 | /** |
240 | * gtk_bitset_get_nth: |
241 | * @self: a `GtkBitset` |
242 | * @nth: index of the item to get |
243 | * |
244 | * Returns the value of the @nth item in self. |
245 | * |
246 | * If @nth is >= the size of @self, 0 is returned. |
247 | * |
248 | * Returns: the value of the @nth item in @self |
249 | */ |
250 | guint |
251 | gtk_bitset_get_nth (const GtkBitset *self, |
252 | guint nth) |
253 | { |
254 | uint32_t result; |
255 | |
256 | if (!roaring_bitmap_select (bm: &self->roaring, rank: nth, element: &result)) |
257 | return 0; |
258 | |
259 | return result; |
260 | } |
261 | |
262 | /** |
263 | * gtk_bitset_new_empty: |
264 | * |
265 | * Creates a new empty bitset. |
266 | * |
267 | * Returns: A new empty bitset |
268 | */ |
269 | GtkBitset * |
270 | gtk_bitset_new_empty (void) |
271 | { |
272 | GtkBitset *self; |
273 | |
274 | self = g_slice_new0 (GtkBitset); |
275 | |
276 | self->ref_count = 1; |
277 | |
278 | ra_init (new_ra: &self->roaring.high_low_container); |
279 | |
280 | return self; |
281 | } |
282 | |
283 | /** |
284 | * gtk_bitset_new_range: |
285 | * @start: first value to add |
286 | * @n_items: number of consecutive values to add |
287 | * |
288 | * Creates a bitset with the given range set. |
289 | * |
290 | * Returns: A new bitset |
291 | **/ |
292 | GtkBitset * |
293 | gtk_bitset_new_range (guint start, |
294 | guint n_items) |
295 | { |
296 | GtkBitset *self; |
297 | |
298 | self = gtk_bitset_new_empty (); |
299 | |
300 | gtk_bitset_add_range (self, start, n_items); |
301 | |
302 | return self; |
303 | } |
304 | |
305 | /** |
306 | * gtk_bitset_copy: |
307 | * @self: a `GtkBitset` |
308 | * |
309 | * Creates a copy of @self. |
310 | * |
311 | * Returns: (transfer full): A new bitset that contains the same |
312 | * values as @self |
313 | */ |
314 | GtkBitset * |
315 | gtk_bitset_copy (const GtkBitset *self) |
316 | { |
317 | GtkBitset *copy; |
318 | |
319 | g_return_val_if_fail (self != NULL, NULL); |
320 | |
321 | copy = gtk_bitset_new_empty (); |
322 | roaring_bitmap_overwrite (dest: ©->roaring, src: &self->roaring); |
323 | |
324 | return copy; |
325 | } |
326 | |
327 | /** |
328 | * gtk_bitset_remove_all: |
329 | * @self: a `GtkBitset` |
330 | * |
331 | * Removes all values from the bitset so that it is empty again. |
332 | */ |
333 | void |
334 | gtk_bitset_remove_all (GtkBitset *self) |
335 | { |
336 | g_return_if_fail (self != NULL); |
337 | |
338 | roaring_bitmap_clear (r: &self->roaring); |
339 | } |
340 | |
341 | /** |
342 | * gtk_bitset_add: |
343 | * @self: a `GtkBitset` |
344 | * @value: value to add |
345 | * |
346 | * Adds @value to @self if it wasn't part of it before. |
347 | * |
348 | * Returns: %TRUE if @value was not part of @self and @self |
349 | * was changed |
350 | */ |
351 | gboolean |
352 | gtk_bitset_add (GtkBitset *self, |
353 | guint value) |
354 | { |
355 | g_return_val_if_fail (self != NULL, FALSE); |
356 | |
357 | return roaring_bitmap_add_checked (r: &self->roaring, val: value); |
358 | } |
359 | |
360 | /** |
361 | * gtk_bitset_remove: |
362 | * @self: a `GtkBitset` |
363 | * @value: value to add |
364 | * |
365 | * Removes @value from @self if it was part of it before. |
366 | * |
367 | * Returns: %TRUE if @value was part of @self and @self |
368 | * was changed |
369 | */ |
370 | gboolean |
371 | gtk_bitset_remove (GtkBitset *self, |
372 | guint value) |
373 | { |
374 | g_return_val_if_fail (self != NULL, FALSE); |
375 | |
376 | return roaring_bitmap_remove_checked (r: &self->roaring, val: value); |
377 | } |
378 | |
379 | /** |
380 | * gtk_bitset_add_range: |
381 | * @self: a `GtkBitset` |
382 | * @start: first value to add |
383 | * @n_items: number of consecutive values to add |
384 | * |
385 | * Adds all values from @start (inclusive) to @start + @n_items |
386 | * (exclusive) in @self. |
387 | */ |
388 | void |
389 | gtk_bitset_add_range (GtkBitset *self, |
390 | guint start, |
391 | guint n_items) |
392 | { |
393 | g_return_if_fail (self != NULL); |
394 | |
395 | if (n_items == 0) |
396 | return; |
397 | |
398 | /* overflow check, the == 0 is to allow add_range(G_MAXUINT, 1); */ |
399 | g_return_if_fail (start + n_items == 0 || start + n_items > start); |
400 | |
401 | roaring_bitmap_add_range_closed (ra: &self->roaring, min: start, max: start + n_items - 1); |
402 | } |
403 | |
404 | /** |
405 | * gtk_bitset_remove_range: |
406 | * @self: a `GtkBitset` |
407 | * @start: first value to remove |
408 | * @n_items: number of consecutive values to remove |
409 | * |
410 | * Removes all values from @start (inclusive) to @start + @n_items (exclusive) |
411 | * in @self. |
412 | */ |
413 | void |
414 | gtk_bitset_remove_range (GtkBitset *self, |
415 | guint start, |
416 | guint n_items) |
417 | { |
418 | g_return_if_fail (self != NULL); |
419 | |
420 | if (n_items == 0) |
421 | return; |
422 | |
423 | /* overflow check, the == 0 is to allow add_range(G_MAXUINT, 1); */ |
424 | g_return_if_fail (start + n_items == 0 || start + n_items > start); |
425 | |
426 | roaring_bitmap_remove_range_closed (ra: &self->roaring, min: start, max: start + n_items - 1); |
427 | } |
428 | |
429 | /** |
430 | * gtk_bitset_add_range_closed: |
431 | * @self: a `GtkBitset` |
432 | * @first: first value to add |
433 | * @last: last value to add |
434 | * |
435 | * Adds the closed range [@first, @last], so @first, @last and all |
436 | * values in between. @first must be smaller than @last. |
437 | */ |
438 | void |
439 | gtk_bitset_add_range_closed (GtkBitset *self, |
440 | guint first, |
441 | guint last) |
442 | { |
443 | g_return_if_fail (self != NULL); |
444 | g_return_if_fail (first <= last); |
445 | |
446 | roaring_bitmap_add_range_closed (ra: &self->roaring, min: first, max: last); |
447 | } |
448 | |
449 | /** |
450 | * gtk_bitset_remove_range_closed: |
451 | * @self: a `GtkBitset` |
452 | * @first: first value to remove |
453 | * @last: last value to remove |
454 | * |
455 | * Removes the closed range [@first, @last], so @first, @last and all |
456 | * values in between. @first must be smaller than @last. |
457 | */ |
458 | void |
459 | gtk_bitset_remove_range_closed (GtkBitset *self, |
460 | guint first, |
461 | guint last) |
462 | { |
463 | g_return_if_fail (self != NULL); |
464 | g_return_if_fail (first <= last); |
465 | |
466 | roaring_bitmap_remove_range_closed (ra: &self->roaring, min: first, max: last); |
467 | } |
468 | |
469 | /** |
470 | * gtk_bitset_add_rectangle: |
471 | * @self: a `GtkBitset` |
472 | * @start: first value to add |
473 | * @width: width of the rectangle |
474 | * @height: height of the rectangle |
475 | * @stride: row stride of the grid |
476 | * |
477 | * Interprets the values as a 2-dimensional boolean grid with the given @stride |
478 | * and inside that grid, adds a rectangle with the given @width and @height. |
479 | */ |
480 | void |
481 | gtk_bitset_add_rectangle (GtkBitset *self, |
482 | guint start, |
483 | guint width, |
484 | guint height, |
485 | guint stride) |
486 | { |
487 | guint i; |
488 | |
489 | g_return_if_fail (self != NULL); |
490 | g_return_if_fail ((start % stride) + width <= stride); |
491 | g_return_if_fail (G_MAXUINT - start >= height * stride); |
492 | |
493 | if (width == 0 || height == 0) |
494 | return; |
495 | |
496 | for (i = 0; i < height; i++) |
497 | gtk_bitset_add_range (self, start: i * stride + start, n_items: width); |
498 | } |
499 | |
500 | /** |
501 | * gtk_bitset_remove_rectangle: |
502 | * @self: a `GtkBitset` |
503 | * @start: first value to remove |
504 | * @width: width of the rectangle |
505 | * @height: height of the rectangle |
506 | * @stride: row stride of the grid |
507 | * |
508 | * Interprets the values as a 2-dimensional boolean grid with the given @stride |
509 | * and inside that grid, removes a rectangle with the given @width and @height. |
510 | */ |
511 | void |
512 | gtk_bitset_remove_rectangle (GtkBitset *self, |
513 | guint start, |
514 | guint width, |
515 | guint height, |
516 | guint stride) |
517 | { |
518 | guint i; |
519 | |
520 | g_return_if_fail (self != NULL); |
521 | g_return_if_fail (width <= stride); |
522 | g_return_if_fail (G_MAXUINT - start >= height * stride); |
523 | |
524 | if (width == 0 || height == 0) |
525 | return; |
526 | |
527 | for (i = 0; i < height; i++) |
528 | gtk_bitset_remove_range (self, start: i * stride + start, n_items: width); |
529 | } |
530 | |
531 | /** |
532 | * gtk_bitset_union: |
533 | * @self: a `GtkBitset` |
534 | * @other: the `GtkBitset` to union with |
535 | * |
536 | * Sets @self to be the union of @self and @other. |
537 | * |
538 | * That is, add all values from @other into @self that weren't part of it. |
539 | * |
540 | * It is allowed for @self and @other to be the same bitset. Nothing will |
541 | * happen in that case. |
542 | */ |
543 | void |
544 | gtk_bitset_union (GtkBitset *self, |
545 | const GtkBitset *other) |
546 | { |
547 | g_return_if_fail (self != NULL); |
548 | g_return_if_fail (other != NULL); |
549 | |
550 | if (self == other) |
551 | return; |
552 | |
553 | roaring_bitmap_or_inplace (x1: &self->roaring, x2: &other->roaring); |
554 | } |
555 | |
556 | /** |
557 | * gtk_bitset_intersect: |
558 | * @self: a `GtkBitset` |
559 | * @other: the `GtkBitset` to intersect with |
560 | * |
561 | * Sets @self to be the intersection of @self and @other. |
562 | * |
563 | * In other words, remove all values from @self that are not part of @other. |
564 | * |
565 | * It is allowed for @self and @other to be the same bitset. Nothing will |
566 | * happen in that case. |
567 | */ |
568 | void |
569 | gtk_bitset_intersect (GtkBitset *self, |
570 | const GtkBitset *other) |
571 | { |
572 | g_return_if_fail (self != NULL); |
573 | g_return_if_fail (other != NULL); |
574 | |
575 | if (self == other) |
576 | return; |
577 | |
578 | roaring_bitmap_and_inplace (x1: &self->roaring, x2: &other->roaring); |
579 | } |
580 | |
581 | /** |
582 | * gtk_bitset_subtract: |
583 | * @self: a `GtkBitset` |
584 | * @other: the `GtkBitset` to subtract |
585 | * |
586 | * Sets @self to be the subtraction of @other from @self. |
587 | * |
588 | * In other words, remove all values from @self that are part of @other. |
589 | * |
590 | * It is allowed for @self and @other to be the same bitset. The bitset |
591 | * will be emptied in that case. |
592 | */ |
593 | void |
594 | gtk_bitset_subtract (GtkBitset *self, |
595 | const GtkBitset *other) |
596 | { |
597 | g_return_if_fail (self != NULL); |
598 | g_return_if_fail (other != NULL); |
599 | |
600 | if (self == other) |
601 | { |
602 | roaring_bitmap_clear (r: &self->roaring); |
603 | return; |
604 | } |
605 | |
606 | roaring_bitmap_andnot_inplace (x1: &self->roaring, x2: &other->roaring); |
607 | } |
608 | |
609 | /** |
610 | * gtk_bitset_difference: |
611 | * @self: a `GtkBitset` |
612 | * @other: the `GtkBitset` to compute the difference from |
613 | * |
614 | * Sets @self to be the symmetric difference of @self and @other. |
615 | * |
616 | * The symmetric difference is set @self to contain all values that |
617 | * were either contained in @self or in @other, but not in both. |
618 | * This operation is also called an XOR. |
619 | * |
620 | * It is allowed for @self and @other to be the same bitset. The bitset |
621 | * will be emptied in that case. |
622 | */ |
623 | void |
624 | gtk_bitset_difference (GtkBitset *self, |
625 | const GtkBitset *other) |
626 | { |
627 | g_return_if_fail (self != NULL); |
628 | g_return_if_fail (other != NULL); |
629 | |
630 | if (self == other) |
631 | { |
632 | roaring_bitmap_clear (r: &self->roaring); |
633 | return; |
634 | } |
635 | |
636 | roaring_bitmap_xor_inplace (x1: &self->roaring, x2: &other->roaring); |
637 | } |
638 | |
639 | /** |
640 | * gtk_bitset_shift_left: |
641 | * @self: a `GtkBitset` |
642 | * @amount: amount to shift all values to the left |
643 | * |
644 | * Shifts all values in @self to the left by @amount. |
645 | * |
646 | * Values smaller than @amount are discarded. |
647 | */ |
648 | void |
649 | gtk_bitset_shift_left (GtkBitset *self, |
650 | guint amount) |
651 | { |
652 | GtkBitset *original; |
653 | GtkBitsetIter iter; |
654 | guint value; |
655 | gboolean loop; |
656 | |
657 | g_return_if_fail (self != NULL); |
658 | |
659 | if (amount == 0) |
660 | return; |
661 | |
662 | original = gtk_bitset_copy (self); |
663 | gtk_bitset_remove_all (self); |
664 | |
665 | for (loop = gtk_bitset_iter_init_at (iter: &iter, set: original, target: amount, value: &value); |
666 | loop; |
667 | loop = gtk_bitset_iter_next (iter: &iter, value: &value)) |
668 | { |
669 | gtk_bitset_add (self, value: value - amount); |
670 | } |
671 | |
672 | gtk_bitset_unref (self: original); |
673 | } |
674 | |
675 | /** |
676 | * gtk_bitset_shift_right: |
677 | * @self: a `GtkBitset` |
678 | * @amount: amount to shift all values to the right |
679 | * |
680 | * Shifts all values in @self to the right by @amount. |
681 | * |
682 | * Values that end up too large to be held in a #guint are discarded. |
683 | */ |
684 | void |
685 | gtk_bitset_shift_right (GtkBitset *self, |
686 | guint amount) |
687 | { |
688 | GtkBitset *original; |
689 | GtkBitsetIter iter; |
690 | guint value; |
691 | gboolean loop; |
692 | |
693 | g_return_if_fail (self != NULL); |
694 | |
695 | if (amount == 0) |
696 | return; |
697 | |
698 | original = gtk_bitset_copy (self); |
699 | gtk_bitset_remove_all (self); |
700 | |
701 | for (loop = gtk_bitset_iter_init_first (iter: &iter, set: original, value: &value); |
702 | loop && value <= G_MAXUINT - amount; |
703 | loop = gtk_bitset_iter_next (iter: &iter, value: &value)) |
704 | { |
705 | gtk_bitset_add (self, value: value + amount); |
706 | } |
707 | |
708 | gtk_bitset_unref (self: original); |
709 | } |
710 | |
711 | /** |
712 | * gtk_bitset_splice: |
713 | * @self: a `GtkBitset` |
714 | * @position: position at which to slice |
715 | * @removed: number of values to remove |
716 | * @added: number of values to add |
717 | * |
718 | * This is a support function for `GListModel` handling, by mirroring |
719 | * the `GlistModel::items-changed` signal. |
720 | * |
721 | * First, it "cuts" the values from @position to @removed from |
722 | * the bitset. That is, it removes all those values and shifts |
723 | * all larger values to the left by @removed places. |
724 | * |
725 | * Then, it "pastes" new room into the bitset by shifting all values |
726 | * larger than @position by @added spaces to the right. This frees |
727 | * up space that can then be filled. |
728 | */ |
729 | void |
730 | gtk_bitset_splice (GtkBitset *self, |
731 | guint position, |
732 | guint removed, |
733 | guint added) |
734 | { |
735 | g_return_if_fail (self != NULL); |
736 | /* overflow */ |
737 | g_return_if_fail (position + removed >= position); |
738 | g_return_if_fail (position + added >= position); |
739 | |
740 | gtk_bitset_remove_range (self, start: position, n_items: removed); |
741 | |
742 | if (removed != added) |
743 | { |
744 | GtkBitset *shift = gtk_bitset_copy (self); |
745 | |
746 | gtk_bitset_remove_range (self: shift, start: 0, n_items: position); |
747 | gtk_bitset_remove_range_closed (self, first: position, G_MAXUINT); |
748 | if (added > removed) |
749 | gtk_bitset_shift_right (self: shift, amount: added - removed); |
750 | else |
751 | gtk_bitset_shift_left (self: shift, amount: removed - added); |
752 | gtk_bitset_union (self, other: shift); |
753 | gtk_bitset_unref (self: shift); |
754 | } |
755 | } |
756 | |
757 | G_STATIC_ASSERT (sizeof (GtkBitsetIter) >= sizeof (roaring_uint32_iterator_t)); |
758 | |
759 | static GtkBitsetIter * |
760 | gtk_bitset_iter_copy (GtkBitsetIter *iter) |
761 | { |
762 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
763 | |
764 | return (GtkBitsetIter *) roaring_copy_uint32_iterator (it: riter); |
765 | } |
766 | |
767 | static void |
768 | gtk_bitset_iter_free (GtkBitsetIter *iter) |
769 | { |
770 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
771 | |
772 | roaring_free_uint32_iterator (it: riter); |
773 | } |
774 | |
775 | G_DEFINE_BOXED_TYPE (GtkBitsetIter, gtk_bitset_iter, gtk_bitset_iter_copy, gtk_bitset_iter_free) |
776 | |
777 | /** |
778 | * gtk_bitset_iter_init_first: |
779 | * @iter: (out): a pointer to an uninitialized `GtkBitsetIter` |
780 | * @set: a `GtkBitset` |
781 | * @value: (out) (optional): Set to the first value in @set |
782 | * |
783 | * Initializes an iterator for @set and points it to the first |
784 | * value in @set. |
785 | * |
786 | * If @set is empty, %FALSE is returned and @value is set to %G_MAXUINT. |
787 | * |
788 | * Returns: %TRUE if @set isn't empty. |
789 | */ |
790 | gboolean |
791 | gtk_bitset_iter_init_first (GtkBitsetIter *iter, |
792 | const GtkBitset *set, |
793 | guint *value) |
794 | { |
795 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
796 | |
797 | g_return_val_if_fail (iter != NULL, FALSE); |
798 | g_return_val_if_fail (set != NULL, FALSE); |
799 | |
800 | roaring_init_iterator (ra: &set->roaring, newit: riter); |
801 | |
802 | if (value) |
803 | *value = riter->has_value ? riter->current_value : 0; |
804 | |
805 | return riter->has_value; |
806 | } |
807 | |
808 | /** |
809 | * gtk_bitset_iter_init_last: |
810 | * @iter: (out): a pointer to an uninitialized `GtkBitsetIter` |
811 | * @set: a `GtkBitset` |
812 | * @value: (out) (optional): Set to the last value in @set |
813 | * |
814 | * Initializes an iterator for @set and points it to the last |
815 | * value in @set. |
816 | * |
817 | * If @set is empty, %FALSE is returned. |
818 | * |
819 | * Returns: %TRUE if @set isn't empty. |
820 | **/ |
821 | gboolean |
822 | gtk_bitset_iter_init_last (GtkBitsetIter *iter, |
823 | const GtkBitset *set, |
824 | guint *value) |
825 | { |
826 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
827 | |
828 | g_return_val_if_fail (iter != NULL, FALSE); |
829 | g_return_val_if_fail (set != NULL, FALSE); |
830 | |
831 | roaring_init_iterator_last (ra: &set->roaring, newit: riter); |
832 | |
833 | if (value) |
834 | *value = riter->has_value ? riter->current_value : 0; |
835 | |
836 | return riter->has_value; |
837 | } |
838 | |
839 | /** |
840 | * gtk_bitset_iter_init_at: |
841 | * @iter: (out): a pointer to an uninitialized `GtkBitsetIter` |
842 | * @set: a `GtkBitset` |
843 | * @target: target value to start iterating at |
844 | * @value: (out) (optional): Set to the found value in @set |
845 | * |
846 | * Initializes @iter to point to @target. |
847 | * |
848 | * If @target is not found, finds the next value after it. |
849 | * If no value >= @target exists in @set, this function returns %FALSE. |
850 | * |
851 | * Returns: %TRUE if a value was found. |
852 | */ |
853 | gboolean |
854 | gtk_bitset_iter_init_at (GtkBitsetIter *iter, |
855 | const GtkBitset *set, |
856 | guint target, |
857 | guint *value) |
858 | { |
859 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
860 | |
861 | g_return_val_if_fail (iter != NULL, FALSE); |
862 | g_return_val_if_fail (set != NULL, FALSE); |
863 | |
864 | roaring_init_iterator (ra: &set->roaring, newit: riter); |
865 | if (!roaring_move_uint32_iterator_equalorlarger (it: riter, val: target)) |
866 | { |
867 | if (value) |
868 | *value = 0; |
869 | return FALSE; |
870 | } |
871 | |
872 | if (value) |
873 | *value = riter->current_value; |
874 | |
875 | return TRUE; |
876 | } |
877 | |
878 | /** |
879 | * gtk_bitset_iter_next: |
880 | * @iter: a pointer to a valid `GtkBitsetIter` |
881 | * @value: (out) (optional): Set to the next value |
882 | * |
883 | * Moves @iter to the next value in the set. |
884 | * |
885 | * If it was already pointing to the last value in the set, |
886 | * %FALSE is returned and @iter is invalidated. |
887 | * |
888 | * Returns: %TRUE if a next value existed |
889 | */ |
890 | gboolean |
891 | gtk_bitset_iter_next (GtkBitsetIter *iter, |
892 | guint *value) |
893 | { |
894 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
895 | |
896 | g_return_val_if_fail (iter != NULL, FALSE); |
897 | |
898 | if (!roaring_advance_uint32_iterator (it: riter)) |
899 | { |
900 | if (value) |
901 | *value = 0; |
902 | return FALSE; |
903 | } |
904 | |
905 | if (value) |
906 | *value = riter->current_value; |
907 | |
908 | return TRUE; |
909 | } |
910 | |
911 | /** |
912 | * gtk_bitset_iter_previous: |
913 | * @iter: a pointer to a valid `GtkBitsetIter` |
914 | * @value: (out) (optional): Set to the previous value |
915 | * |
916 | * Moves @iter to the previous value in the set. |
917 | * |
918 | * If it was already pointing to the first value in the set, |
919 | * %FALSE is returned and @iter is invalidated. |
920 | * |
921 | * Returns: %TRUE if a previous value existed |
922 | */ |
923 | gboolean |
924 | gtk_bitset_iter_previous (GtkBitsetIter *iter, |
925 | guint *value) |
926 | { |
927 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
928 | |
929 | g_return_val_if_fail (iter != NULL, FALSE); |
930 | |
931 | if (!roaring_previous_uint32_iterator (it: riter)) |
932 | { |
933 | if (value) |
934 | *value = 0; |
935 | return FALSE; |
936 | } |
937 | |
938 | if (value) |
939 | *value = riter->current_value; |
940 | |
941 | return TRUE; |
942 | } |
943 | |
944 | /** |
945 | * gtk_bitset_iter_get_value: |
946 | * @iter: a `GtkBitsetIter` |
947 | * |
948 | * Gets the current value that @iter points to. |
949 | * |
950 | * If @iter is not valid and [method@Gtk.BitsetIter.is_valid] |
951 | * returns %FALSE, this function returns 0. |
952 | * |
953 | * Returns: The current value pointer to by @iter |
954 | */ |
955 | guint |
956 | gtk_bitset_iter_get_value (const GtkBitsetIter *iter) |
957 | { |
958 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
959 | |
960 | g_return_val_if_fail (iter != NULL, 0); |
961 | |
962 | if (!riter->has_value) |
963 | return 0; |
964 | |
965 | return riter->current_value; |
966 | } |
967 | |
968 | /** |
969 | * gtk_bitset_iter_is_valid: |
970 | * @iter: a `GtkBitsetIter` |
971 | * |
972 | * Checks if @iter points to a valid value. |
973 | * |
974 | * Returns: %TRUE if @iter points to a valid value |
975 | */ |
976 | gboolean |
977 | gtk_bitset_iter_is_valid (const GtkBitsetIter *iter) |
978 | { |
979 | roaring_uint32_iterator_t *riter = (roaring_uint32_iterator_t *) iter; |
980 | |
981 | g_return_val_if_fail (iter != NULL, FALSE); |
982 | |
983 | return riter->has_value; |
984 | } |
985 | |