1 /* intset.c - Source for a set of unsigned integers (implemented as a
2 * variable length bitfield)
3 *
4 * Copyright © 2005-2010 Collabora Ltd. <http://www.collabora.co.uk/>
5 * Copyright © 2005-2006 Nokia Corporation
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public License
9 * as published by the Free Software Foundation; either version 2.1 of
10 * the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20 * 02110-1301 USA
21 *
22 */
23
24 /**
25 * SECTION:intset
26 * @title: TpIntset
27 * @short_description: a set of unsigned integers
28 * @see_also: #TpHandleSet
29 *
30 * A #TpIntset is a set of unsigned integers, implemented as a
31 * dynamically-allocated sparse bitfield.
32 */
33
34 #include "config.h"
35
36 #include <telepathy-glib/intset.h>
37 #include <telepathy-glib/util.h>
38
39 #include <string.h>
40 #include <glib.h>
41
42 /* On platforms with 64-bit pointers we could pack 64 bits into the values,
43 * if count_bits32() is replaced with a 64-bit version. This doesn't work
44 * yet. */
45 #undef USE_64_BITS
46
47 #ifdef USE_64_BITS
48 # define BITFIELD_BITS 64
49 # define BITFIELD_LOG2_BITS 6
50 #else
51 # define BITFIELD_BITS 32
52 # define BITFIELD_LOG2_BITS 5
53 #endif
54
55 G_STATIC_ASSERT (1 << BITFIELD_LOG2_BITS == BITFIELD_BITS);
56 G_STATIC_ASSERT (sizeof (gpointer) >= sizeof (gsize));
57 #define LOW_MASK (BITFIELD_BITS - 1)
58 #define HIGH_PART(x) (x & ~LOW_MASK)
59 #define LOW_PART(x) (x & LOW_MASK)
60
61 /**
62 * TP_TYPE_INTSET:
63 *
64 * The boxed type of a #TpIntset.
65 *
66 * Since: 0.11.3
67 */
68
69 GType
tp_intset_get_type(void)70 tp_intset_get_type (void)
71 {
72 static GType type = 0;
73
74 if (G_UNLIKELY (type == 0))
75 {
76 /* The "TpIntSet" type has to be registered for backwards compatibility.
77 * The canonical name of the type is now "TpIntset"; see fdo#30134. */
78 g_boxed_type_register_static (g_intern_static_string ("TpIntSet"),
79 (GBoxedCopyFunc) tp_intset_copy,
80 (GBoxedFreeFunc) tp_intset_destroy);
81 type = g_boxed_type_register_static (g_intern_static_string ("TpIntset"),
82 (GBoxedCopyFunc) tp_intset_copy,
83 (GBoxedFreeFunc) tp_intset_destroy);
84 }
85
86 return type;
87 }
88
89 /**
90 * TpIntFunc:
91 * @i: The relevant integer
92 * @userdata: Opaque user data
93 *
94 * A callback function acting on unsigned integers.
95 */
96 /* (typedef, see header) */
97
98 /**
99 * TpIntSetIter: (skip)
100 *
101 * Before 0.11.16, this was the name for <type>TpIntsetIter</type>, but
102 * it's now just a backwards compatibility typedef.
103 *
104 * Deprecated: since 0.19.0. Use #TpIntsetFastIter instead
105 */
106
107 /**
108 * TpIntsetIter:
109 * @set: The set iterated over.
110 * @element: Must be (guint)(-1) before iteration starts. Set to the next
111 * element in the set by tp_intset_iter_next(); undefined after
112 * tp_intset_iter_next() returns %FALSE.
113 *
114 * A structure representing iteration over a set of integers. Must be
115 * initialized with either TP_INTSET_ITER_INIT() or tp_intset_iter_init().
116 *
117 * Since 0.11.6, consider using #TpIntsetFastIter if iteration in
118 * numerical order is not required.
119 *
120 * Before 0.11.16, this type was called <type>TpIntSetIter</type>,
121 * which is now a backwards compatibility typedef.
122 *
123 * Deprecated: since 0.19.0. Use #TpIntsetFastIter instead
124 */
125 /* (public, see header) */
126
127 /**
128 * TP_INTSET_ITER_INIT:
129 * @set: A set of integers
130 *
131 * A suitable static initializer for a #TpIntsetIter, to be used as follows:
132 *
133 * <informalexample><programlisting>
134 * void
135 * do_something (const TpIntset *intset)
136 * {
137 * TpIntsetIter iter = TP_INTSET_ITER_INIT (intset);
138 * /<!-- -->* ... do something with iter ... *<!-- -->/
139 * }
140 * </programlisting></informalexample>
141 *
142 * Deprecated: since 0.19.0. Use #TpIntsetFastIter instead
143 */
144 /* (macro, see header) */
145
146 /**
147 * tp_intset_iter_init:
148 * @iter: An integer set iterator to be initialized.
149 * @set: An integer set to be used by that iterator
150 *
151 * Reset the iterator @iter to the beginning and make it iterate over @set.
152 *
153 * Deprecated: since 0.19.0. Use #TpIntsetFastIter instead
154 */
155 void
tp_intset_iter_init(TpIntsetIter * iter,const TpIntset * set)156 tp_intset_iter_init (
157 TpIntsetIter *iter,
158 const TpIntset *set)
159 {
160 g_return_if_fail (iter != NULL);
161 iter->set = set;
162 iter->element = (guint)(-1);
163 }
164
165 /**
166 * tp_intset_iter_reset:
167 * @iter: An integer set iterator to be reset.
168 *
169 * Reset the iterator @iter to the beginning. It must already be associated
170 * with a set.
171 *
172 * Deprecated: since 0.19.0. Use #TpIntsetFastIter instead
173 */
174 void
tp_intset_iter_reset(TpIntsetIter * iter)175 tp_intset_iter_reset (TpIntsetIter *iter)
176 {
177 g_return_if_fail (iter != NULL);
178 g_return_if_fail (iter->set != NULL);
179 iter->element = (guint)(-1);
180 }
181
182 /**
183 * TpIntset:
184 *
185 * Opaque type representing a set of unsigned integers.
186 *
187 * Before 0.11.16, this type was called <type>TpIntSet</type>, which is
188 * now a backwards compatibility typedef.
189 */
190
191 struct _TpIntset
192 {
193 /* HIGH_PART(n) => bitfield where bit LOW_PART(n) is set if n is present.
194 *
195 * For instance, when using 32-bit values, the set { 5, 23 } is represented
196 * by the map { 0 => (1 << 23 | 1 << 5) }, and the set { 1, 32, 42 } is
197 * represented by the map { 0 => (1 << 1), 32 => (1 << 10 | 1 << 0) }. */
198 GHashTable *table;
199 guint largest_ever;
200 };
201
202 /*
203 * Update @set's largest_ever member to be at least as large as everything
204 * that could be encoded in the hash table key @key.
205 *
206 * We could use g_bit_nth_msf (value, BITFIELD_BITS) instead of LOW_MASK if we
207 * wanted to get largest_ever exactly right, but we just need something
208 * reasonable to make TpIntsetIter terminate early, and carrying on for up to
209 * BITFIELD_BITS extra iterations isn't a problem.
210 */
211 static inline void
intset_update_largest_ever(TpIntset * set,gpointer key)212 intset_update_largest_ever (TpIntset *set,
213 gpointer key)
214 {
215 guint upper_bound = GPOINTER_TO_UINT (key) | LOW_MASK;
216
217 if (set->largest_ever < upper_bound)
218 set->largest_ever = upper_bound;
219 }
220
221 /**
222 * tp_intset_sized_new:
223 * @size: ignored (it was previously 1 more than the largest integer you
224 * expect to store)
225 *
226 * Allocate a new integer set.
227 *
228 * Returns: a new, empty integer set to be destroyed with tp_intset_destroy()
229 */
230 TpIntset *
tp_intset_sized_new(guint size G_GNUC_UNUSED)231 tp_intset_sized_new (guint size G_GNUC_UNUSED)
232 {
233 return tp_intset_new ();
234 }
235
236 /**
237 * tp_intset_new:
238 *
239 * Allocate a new integer set.
240 *
241 * Returns: a new, empty integer set to be destroyed with tp_intset_destroy()
242 */
243 TpIntset *
tp_intset_new()244 tp_intset_new ()
245 {
246 TpIntset *set = g_slice_new (TpIntset);
247
248 set->table = g_hash_table_new (NULL, NULL);
249 set->largest_ever = 0;
250 return set;
251 }
252
253 /**
254 * tp_intset_new_containing:
255 * @element: integer to add to a new set
256 *
257 * Allocate a new integer set containing the given integer.
258 *
259 * Returns: a new integer set containing @element, to be destroyed with
260 * tp_intset_destroy()
261 *
262 * Since: 0.7.26
263 */
264 TpIntset *
tp_intset_new_containing(guint element)265 tp_intset_new_containing (guint element)
266 {
267 TpIntset *ret = tp_intset_new ();
268
269 tp_intset_add (ret, element);
270
271 return ret;
272 }
273
274 /**
275 * tp_intset_destroy:
276 * @set: set
277 *
278 * Free all memory used by the set.
279 */
280 void
tp_intset_destroy(TpIntset * set)281 tp_intset_destroy (TpIntset *set)
282 {
283 g_return_if_fail (set != NULL);
284
285 g_hash_table_unref (set->table);
286 g_slice_free (TpIntset, set);
287 }
288
289 /**
290 * tp_intset_clear:
291 * @set: set
292 *
293 * Unset every integer in the set.
294 */
295 void
tp_intset_clear(TpIntset * set)296 tp_intset_clear (TpIntset *set)
297 {
298 g_return_if_fail (set != NULL);
299
300 g_hash_table_remove_all (set->table);
301 }
302
303 /**
304 * tp_intset_add:
305 * @set: set
306 * @element: integer to add
307 *
308 * Add an integer into a TpIntset.
309 */
310 void
tp_intset_add(TpIntset * set,guint element)311 tp_intset_add (TpIntset *set,
312 guint element)
313 {
314 gpointer key = GSIZE_TO_POINTER ((gsize) HIGH_PART (element));
315 gsize bit = LOW_PART (element);
316 gpointer old_value, new_value;
317
318 g_return_if_fail (set != NULL);
319
320 old_value = g_hash_table_lookup (set->table, key);
321 new_value = GSIZE_TO_POINTER (GPOINTER_TO_SIZE (old_value) | (1 << bit));
322
323 if (old_value != new_value)
324 g_hash_table_insert (set->table, key, new_value);
325
326 if (element > set->largest_ever)
327 set->largest_ever = element;
328 }
329
330 /**
331 * tp_intset_remove:
332 * @set: set
333 * @element: integer to add
334 *
335 * Remove an integer from a TpIntset
336 *
337 * Returns: %TRUE if @element was previously in @set
338 */
339 gboolean
tp_intset_remove(TpIntset * set,guint element)340 tp_intset_remove (TpIntset *set,
341 guint element)
342 {
343 gpointer key = GSIZE_TO_POINTER ((gsize) HIGH_PART (element));
344 gsize bit = LOW_PART (element);
345 gpointer old_value, new_value;
346
347 g_return_val_if_fail (set != NULL, FALSE);
348
349 old_value = g_hash_table_lookup (set->table, key);
350 new_value = GSIZE_TO_POINTER (GPOINTER_TO_SIZE (old_value) & ~ (1 << bit));
351
352 if (old_value != new_value)
353 {
354 if (new_value == NULL)
355 g_hash_table_remove (set->table, key);
356 else
357 g_hash_table_insert (set->table, key, new_value);
358
359 return TRUE;
360 }
361
362 return FALSE;
363 }
364
365 static inline gboolean
_tp_intset_is_member(const TpIntset * set,guint element)366 _tp_intset_is_member (const TpIntset *set,
367 guint element)
368 {
369 gpointer key = GSIZE_TO_POINTER ((gsize) HIGH_PART (element));
370 gsize bit = LOW_PART (element);
371 gpointer value;
372
373 value = g_hash_table_lookup (set->table, key);
374 return ((GPOINTER_TO_SIZE (value) & (1 << bit)) != 0);
375 }
376
377 /**
378 * tp_intset_is_member:
379 * @set: set
380 * @element: integer to test
381 *
382 * Tests if @element is a member of @set
383 *
384 * Returns: %TRUE if @element is in @set
385 */
386 gboolean
tp_intset_is_member(const TpIntset * set,guint element)387 tp_intset_is_member (const TpIntset *set, guint element)
388 {
389 g_return_val_if_fail (set != NULL, FALSE);
390
391 return _tp_intset_is_member (set, element);
392 }
393
394 /**
395 * tp_intset_foreach:
396 * @set: set
397 * @func: (scope call): @TpIntFunc to use to iterate the set
398 * @userdata: user data to pass to each call of @func
399 *
400 * Call @func(element, @userdata) for each element of @set, in order.
401 */
402
403 void
tp_intset_foreach(const TpIntset * set,TpIntFunc func,gpointer userdata)404 tp_intset_foreach (const TpIntset *set,
405 TpIntFunc func,
406 gpointer userdata)
407 {
408 gsize high_part, low_part;
409
410 g_return_if_fail (set != NULL);
411 g_return_if_fail (func != NULL);
412
413 for (high_part = 0;
414 high_part <= set->largest_ever;
415 high_part += BITFIELD_BITS)
416 {
417 gsize entry = GPOINTER_TO_SIZE (g_hash_table_lookup (set->table,
418 GSIZE_TO_POINTER (high_part)));
419
420 if (entry == 0)
421 continue;
422
423 for (low_part = 0; low_part < BITFIELD_BITS; low_part++)
424 {
425 if (entry & (1 << low_part))
426 {
427 func (high_part + low_part, userdata);
428 }
429 }
430 }
431 }
432
433 static void
addint(guint i,gpointer data)434 addint (guint i, gpointer data)
435 {
436 GArray *array = (GArray *) data;
437 g_array_append_val (array, i);
438 }
439
440 /**
441 * tp_intset_to_array:
442 * @set: set to convert
443 *
444 * <!--Returns: says it all-->
445 *
446 * Returns: (element-type uint) (transfer full): a GArray of guint (which must
447 * be freed by the caller) containing the same integers as @set.
448 */
449 GArray *
tp_intset_to_array(const TpIntset * set)450 tp_intset_to_array (const TpIntset *set)
451 {
452 GArray *array;
453
454 g_return_val_if_fail (set != NULL, NULL);
455
456 array = g_array_new (FALSE, TRUE, sizeof (guint));
457
458 tp_intset_foreach (set, addint, array);
459
460 return array;
461 }
462
463
464 /**
465 * tp_intset_from_array:
466 * @array: (element-type uint): An array of guint
467 *
468 * <!--Returns: says it all-->
469 *
470 * Returns: A set containing the same integers as @array.
471 */
472
473 TpIntset *
tp_intset_from_array(const GArray * array)474 tp_intset_from_array (const GArray *array)
475 {
476 TpIntset *set;
477 guint i;
478
479 g_return_val_if_fail (array != NULL, NULL);
480
481 set = tp_intset_new ();
482
483 for (i = 0; i < array->len; i++)
484 {
485 tp_intset_add (set, g_array_index (array, guint, i));
486 }
487
488 return set;
489 }
490
491 /* these magic numbers would need adjusting for 64-bit storage */
492 G_STATIC_ASSERT (BITFIELD_BITS == 32);
493
494 static inline guint
count_bits32(guint32 n)495 count_bits32 (guint32 n)
496 {
497 n = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
498 return ((n + (n >> 3)) & 030707070707) % 63;
499 }
500
501 /**
502 * tp_intset_size:
503 * @set: A set of integers
504 *
505 * <!--Returns: says it all-->
506 *
507 * Returns: The number of integers in @set
508 */
509
510 guint
tp_intset_size(const TpIntset * set)511 tp_intset_size (const TpIntset *set)
512 {
513 guint count = 0;
514 gpointer entry;
515 GHashTableIter iter;
516
517 g_return_val_if_fail (set != NULL, 0);
518
519 g_hash_table_iter_init (&iter, (GHashTable *) set->table);
520
521 while (g_hash_table_iter_next (&iter, NULL, &entry))
522 {
523 count += count_bits32 (GPOINTER_TO_SIZE (entry));
524 }
525
526 return count;
527 }
528
529 /**
530 * tp_intset_is_empty:
531 * @set: a set of integers
532 *
533 * Return the same thing as <code>(tp_intset_size (set) == 0)</code>,
534 * but calculated more efficiently.
535 *
536 * Returns: %TRUE if @set is empty
537 *
538 * Since: 0.11.6
539 */
540 gboolean
tp_intset_is_empty(const TpIntset * set)541 tp_intset_is_empty (const TpIntset *set)
542 {
543 g_return_val_if_fail (set != NULL, TRUE);
544 return (g_hash_table_size (set->table) == 0);
545 }
546
547 /**
548 * tp_intset_is_equal:
549 * @left: A set of integers
550 * @right: A set of integers
551 *
552 * <!--Returns: says it all-->
553 *
554 * Returns: %TRUE if @left and @right contain the same bits
555 */
556
557 gboolean
tp_intset_is_equal(const TpIntset * left,const TpIntset * right)558 tp_intset_is_equal (const TpIntset *left,
559 const TpIntset *right)
560 {
561 gpointer key, value;
562 GHashTableIter iter;
563
564 g_return_val_if_fail (left != NULL, FALSE);
565 g_return_val_if_fail (right != NULL, FALSE);
566
567 if (g_hash_table_size (left->table) != g_hash_table_size (right->table))
568 return FALSE;
569
570 g_hash_table_iter_init (&iter, (GHashTable *) left->table);
571
572 while (g_hash_table_iter_next (&iter, &key, &value))
573 {
574 if (g_hash_table_lookup (right->table, key) != value)
575 {
576 return FALSE;
577 }
578 }
579
580 return TRUE;
581 }
582
583
584 /**
585 * tp_intset_copy:
586 * @orig: A set of integers
587 *
588 * <!--Returns: says it all-->
589 *
590 * Returns: A set containing the same integers as @orig, to be freed with
591 * tp_intset_destroy() by the caller
592 */
593
594 TpIntset *
tp_intset_copy(const TpIntset * orig)595 tp_intset_copy (const TpIntset *orig)
596 {
597 gpointer key, value;
598 GHashTableIter iter;
599 TpIntset *ret;
600
601 g_return_val_if_fail (orig != NULL, NULL);
602
603 ret = tp_intset_new ();
604
605 g_hash_table_iter_init (&iter, (GHashTable *) orig->table);
606
607 while (g_hash_table_iter_next (&iter, &key, &value))
608 {
609 intset_update_largest_ever (ret, key);
610 g_hash_table_insert (ret->table, key, value);
611 }
612
613 return ret;
614 }
615
616
617 /**
618 * tp_intset_intersection:
619 * @left: The left operand
620 * @right: The right operand
621 *
622 * <!--Returns: says it all-->
623 *
624 * Returns: The set of those integers which are in both @left and @right
625 * (analogous to the bitwise operation left & right), to be freed with
626 * tp_intset_destroy() by the caller
627 */
628
629 TpIntset *
tp_intset_intersection(const TpIntset * left,const TpIntset * right)630 tp_intset_intersection (const TpIntset *left, const TpIntset *right)
631 {
632 gpointer key, value;
633 GHashTableIter iter;
634 TpIntset *ret;
635
636 ret = tp_intset_new ();
637
638 g_hash_table_iter_init (&iter, (GHashTable *) left->table);
639
640 while (g_hash_table_iter_next (&iter, &key, &value))
641 {
642 gsize v = GPOINTER_TO_SIZE (value);
643
644 v &= GPOINTER_TO_SIZE (g_hash_table_lookup (right->table, key));
645
646 if (v != 0)
647 {
648 intset_update_largest_ever (ret, key);
649 g_hash_table_insert (ret->table, key, GSIZE_TO_POINTER (v));
650 }
651 }
652
653 return ret;
654 }
655
656 /**
657 * tp_intset_union:
658 * @left: The left operand
659 * @right: The right operand
660 *
661 * <!--Returns: says it all-->
662 *
663 * Returns: The set of those integers which are in either @left or @right
664 * (analogous to the bitwise operation left | right), to be freed with
665 * tp_intset_destroy() by the caller
666 */
667
668 TpIntset *
tp_intset_union(const TpIntset * left,const TpIntset * right)669 tp_intset_union (const TpIntset *left, const TpIntset *right)
670 {
671 TpIntset *ret;
672
673 ret = tp_intset_copy (left);
674 tp_intset_union_update (ret, right);
675
676 return ret;
677 }
678
679 /**
680 * tp_intset_union_update:
681 * @self: the set to change
682 * @other: members to add
683 *
684 * Add each integer in @other to @self, analogous to the bitwise operation
685 * self |= other.
686 *
687 * Since: 0.13.10
688 */
689 void
tp_intset_union_update(TpIntset * self,const TpIntset * other)690 tp_intset_union_update (TpIntset *self,
691 const TpIntset *other)
692 {
693 gpointer key, value;
694 GHashTableIter iter;
695
696 g_hash_table_iter_init (&iter, (GHashTable *) other->table);
697
698 while (g_hash_table_iter_next (&iter, &key, &value))
699 {
700 gsize v = GPOINTER_TO_SIZE (value);
701
702 intset_update_largest_ever (self, key);
703 v |= GPOINTER_TO_SIZE (g_hash_table_lookup (self->table, key));
704 g_hash_table_insert (self->table, key, GSIZE_TO_POINTER (v));
705 }
706 }
707
708 /**
709 * tp_intset_difference:
710 * @left: The left operand
711 * @right: The right operand
712 *
713 * <!--Returns: says it all-->
714 *
715 * Returns: The set of those integers which are in @left and not in @right
716 * (analogous to the bitwise operation left & (~right)), to be freed with
717 * tp_intset_destroy() by the caller
718 */
719
720 TpIntset *
tp_intset_difference(const TpIntset * left,const TpIntset * right)721 tp_intset_difference (const TpIntset *left, const TpIntset *right)
722 {
723 TpIntset *ret;
724
725 g_return_val_if_fail (left != NULL, NULL);
726 g_return_val_if_fail (right != NULL, NULL);
727
728 ret = tp_intset_copy (left);
729 tp_intset_difference_update (ret, right);
730
731 return ret;
732 }
733
734 /**
735 * tp_intset_difference_update:
736 * @self: the set to change
737 * @other: members to remove
738 *
739 * Remove each integer in @other from @self, analogous to the bitwise
740 * operation self &= (~other).
741 *
742 * Since: 0.13.10
743 */
744 void
tp_intset_difference_update(TpIntset * self,const TpIntset * other)745 tp_intset_difference_update (TpIntset *self,
746 const TpIntset *other)
747 {
748 gpointer key, value;
749 GHashTableIter iter;
750
751 g_hash_table_iter_init (&iter, (GHashTable *) other->table);
752
753 while (g_hash_table_iter_next (&iter, &key, &value))
754 {
755 gsize v = GPOINTER_TO_SIZE (value);
756 v = (GPOINTER_TO_SIZE (g_hash_table_lookup (self->table, key))) & ~v;
757
758 /* No need to update largest_ever here - we're only deleting members. */
759
760 if (v == 0)
761 g_hash_table_remove (self->table, key);
762 else
763 g_hash_table_insert (self->table, key, GSIZE_TO_POINTER (v));
764 }
765 }
766
767 /**
768 * tp_intset_symmetric_difference:
769 * @left: The left operand
770 * @right: The right operand
771 *
772 * <!--Returns: says it all-->
773 *
774 * Returns: The set of those integers which are in either @left or @right
775 * but not both (analogous to the bitwise operation left ^ right), to be freed
776 * with tp_intset_destroy() by the caller
777 */
778
779 TpIntset *
tp_intset_symmetric_difference(const TpIntset * left,const TpIntset * right)780 tp_intset_symmetric_difference (const TpIntset *left, const TpIntset *right)
781 {
782 TpIntset *ret;
783 gpointer key, value;
784 GHashTableIter iter;
785
786 g_return_val_if_fail (left != NULL, NULL);
787 g_return_val_if_fail (right != NULL, NULL);
788
789 ret = tp_intset_copy (left);
790
791 g_hash_table_iter_init (&iter, (GHashTable *) right->table);
792
793 while (g_hash_table_iter_next (&iter, &key, &value))
794 {
795 gsize v = GPOINTER_TO_SIZE (value);
796 v = v ^ GPOINTER_TO_SIZE (g_hash_table_lookup (ret->table, key));
797
798 /* No need to update largest_ever here - we're only deleting members. */
799
800 if (v == 0)
801 g_hash_table_remove (ret->table, key);
802 else
803 g_hash_table_insert (ret->table, key, GSIZE_TO_POINTER (v));
804 }
805
806 return ret;
807 }
808
809 static void
_dump_foreach(guint i,gpointer data)810 _dump_foreach (guint i, gpointer data)
811 {
812 GString *tmp = (GString *) data;
813
814 if (tmp->len == 0)
815 g_string_append_printf (tmp, "%u", i);
816 else
817 g_string_append_printf (tmp, " %u", i);
818 }
819
820 /**
821 * tp_intset_dump:
822 * @set: An integer set
823 *
824 * <!--Returns: says it all-->
825 *
826 * Returns: a string which the caller must free with g_free, listing the
827 * numbers in @set in a human-readable format
828 */
829 gchar *
tp_intset_dump(const TpIntset * set)830 tp_intset_dump (const TpIntset *set)
831 {
832 GString *tmp = g_string_new ("");
833
834 tp_intset_foreach (set, _dump_foreach, tmp);
835 return g_string_free (tmp, FALSE);
836 }
837
838 /**
839 * tp_intset_iter_next:
840 * @iter: An iterator originally initialized with TP_INTSET_INIT(set)
841 *
842 * If there are integers in (@iter->set) higher than (@iter->element), set
843 * (iter->element) to the next one and return %TRUE. Otherwise return %FALSE.
844 *
845 * Usage:
846 *
847 * <informalexample><programlisting>
848 * TpIntsetIter iter = TP_INTSET_INIT (intset);
849 * while (tp_intset_iter_next (&iter))
850 * {
851 * printf ("%u is in the intset\n", iter.element);
852 * }
853 * </programlisting></informalexample>
854 *
855 * Since 0.11.6, consider using #TpIntsetFastIter if iteration in
856 * numerical order is not required.
857 *
858 * Returns: %TRUE if (@iter->element) has been advanced
859 */
860 gboolean
tp_intset_iter_next(TpIntsetIter * iter)861 tp_intset_iter_next (TpIntsetIter *iter)
862 {
863 g_return_val_if_fail (iter != NULL, FALSE);
864 g_return_val_if_fail (iter->set != NULL, FALSE);
865
866 do
867 {
868 if (iter->element == (guint)(-1))
869 {
870 /* only just started */
871 iter->element = 0;
872 }
873 else
874 {
875 ++iter->element;
876 }
877
878 if (_tp_intset_is_member (iter->set, iter->element))
879 {
880 return TRUE;
881 }
882 }
883 while (iter->element < iter->set->largest_ever &&
884 iter->element != (guint)(-1));
885 return FALSE;
886 }
887
888 /**
889 * TpIntSetFastIter: (skip)
890 *
891 * Before 0.11.16, this was the name for <type>TpIntsetFastIter</type>,
892 * but it's now just a backwards compatibility typedef.
893 *
894 * Deprecated: since 0.19.0. Use #TpIntsetFastIter instead
895 */
896
897 /**
898 * TpIntsetFastIter:
899 *
900 * An opaque structure representing iteration in undefined order over a set of
901 * integers. Must be initialized with tp_intset_fast_iter_init().
902 *
903 * Before 0.11.16, this type was called <type>TpIntSetFastIter</type>,
904 * which is now a backwards compatibility typedef.
905 *
906 * Usage is similar to #GHashTableIter:
907 *
908 * <informalexample><programlisting>
909 * TpIntsetFastIter iter;
910 * guint element;
911 *
912 * tp_intset_fast_iter_init (&iter, intset);
913 *
914 * while (tp_intset_fast_iter_next (&iter, &element))
915 * {
916 * printf ("%u is in the intset\n", element);
917 * }
918 * </programlisting></informalexample>
919 *
920 * Since: 0.11.6
921 */
922
923 typedef struct {
924 GHashTableIter hash_iter;
925 gboolean ok;
926 gsize high_part;
927 gsize bitfield;
928 } RealFastIter;
929
930 G_STATIC_ASSERT (sizeof (TpIntsetFastIter) >= sizeof (RealFastIter));
931
932 /**
933 * tp_intset_fast_iter_init:
934 * @iter: an iterator
935 * @set: a set
936 *
937 * Initialize @iter to iterate over @set in arbitrary order. @iter will become
938 * invalid if @set is modified.
939 *
940 * Since: 0.11.6
941 */
942 void
tp_intset_fast_iter_init(TpIntsetFastIter * iter,const TpIntset * set)943 tp_intset_fast_iter_init (TpIntsetFastIter *iter,
944 const TpIntset *set)
945 {
946 RealFastIter *real = (RealFastIter *) iter;
947 g_return_if_fail (set != NULL);
948 g_return_if_fail (set->table != NULL);
949
950 g_hash_table_iter_init (&real->hash_iter, (GHashTable *) set->table);
951 real->bitfield = 0;
952 real->high_part = 0;
953 real->ok = TRUE;
954 }
955
956 /**
957 * tp_intset_fast_iter_next:
958 * @iter: an iterator
959 * @output: a location to store a new integer, in arbitrary order
960 *
961 * Advances @iter and retrieves the integer it now points to. Iteration
962 * is not necessarily in numerical order.
963 *
964 * Returns: %FALSE if the end of the set has been reached
965 *
966 * Since: 0.11.6
967 */
968 gboolean
tp_intset_fast_iter_next(TpIntsetFastIter * iter,guint * output)969 tp_intset_fast_iter_next (TpIntsetFastIter *iter,
970 guint *output)
971 {
972 RealFastIter *real = (RealFastIter *) iter;
973 guint low_part;
974
975 if (!real->ok)
976 return FALSE;
977
978 if (real->bitfield == 0)
979 {
980 gpointer k, v;
981
982 real->ok = g_hash_table_iter_next (&real->hash_iter, &k, &v);
983
984 if (!real->ok)
985 return FALSE;
986
987 real->high_part = GPOINTER_TO_SIZE (k);
988 real->bitfield = GPOINTER_TO_SIZE (v);
989 g_assert (real->bitfield != 0);
990 }
991
992 for (low_part = 0; low_part < BITFIELD_BITS; low_part++)
993 {
994 if (real->bitfield & (1 << low_part))
995 {
996 /* clear the bit so we won't return it again */
997 real->bitfield -= (1 << low_part);
998
999 if (output != NULL)
1000 *output = real->high_part | low_part;
1001
1002 return TRUE;
1003 }
1004 }
1005
1006 g_assert_not_reached ();
1007 }
1008