|
1 /* gintset.c - Source for a Glib-link set of integers |
|
2 * Copyright (C) 2006 Collabora Ltd. |
|
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 License |
|
6 * as published by the Free Software Foundation; either version 2.1 of |
|
7 * the License, or (at your option) any later version. |
|
8 * |
|
9 * This library is distributed in the hope that it will be useful, but |
|
10 * 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, write to the Free Software |
|
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA |
|
17 * 02110-1301 USA |
|
18 * |
|
19 */ |
|
20 |
|
21 #include <string.h> |
|
22 #include <glib.h> |
|
23 #include "gintset.h" |
|
24 |
|
25 #define DEFAULT_SIZE 16 |
|
26 #define DEFAULT_INCREMENT 8 |
|
27 #define DEFAULT_INCREMENT_LOG2 3 |
|
28 |
|
29 struct _GIntSet |
|
30 { |
|
31 guint32 *bits; |
|
32 guint size; |
|
33 }; |
|
34 |
|
35 static GIntSet * |
|
36 _g_intset_new_with_size (guint size) |
|
37 { |
|
38 GIntSet *set = g_new (GIntSet, 1); |
|
39 set->size = MAX (size, DEFAULT_SIZE); |
|
40 set->bits = g_new0 (guint32, set->size); |
|
41 return set; |
|
42 } |
|
43 |
|
44 |
|
45 GIntSet * |
|
46 g_intset_new () |
|
47 { |
|
48 return _g_intset_new_with_size (DEFAULT_SIZE); |
|
49 } |
|
50 |
|
51 /** |
|
52 * g_intset_destroy: |
|
53 * @set: set |
|
54 * |
|
55 * delete the set |
|
56 */ |
|
57 |
|
58 void |
|
59 g_intset_destroy (GIntSet *set) |
|
60 { |
|
61 g_return_if_fail (set != NULL); |
|
62 |
|
63 g_free (set->bits); |
|
64 g_free (set); |
|
65 } |
|
66 |
|
67 /** |
|
68 * g_intset_clear: |
|
69 * @set : set |
|
70 * |
|
71 * Unset every integer in the set. |
|
72 */ |
|
73 void |
|
74 g_intset_clear (GIntSet *set) |
|
75 { |
|
76 g_return_if_fail (set != NULL); |
|
77 |
|
78 memset (set->bits, 0, set->size * sizeof (guint32)); |
|
79 } |
|
80 |
|
81 /** |
|
82 * g_intset_add: |
|
83 * @set: set |
|
84 * @element: integer to add |
|
85 * |
|
86 * Add an integer into a GIntSet |
|
87 */ |
|
88 |
|
89 void |
|
90 g_intset_add (GIntSet *set, guint element) |
|
91 { |
|
92 guint offset; |
|
93 guint newsize; |
|
94 |
|
95 g_return_if_fail (set != NULL); |
|
96 |
|
97 offset = element >> 5; |
|
98 |
|
99 if (offset >= set->size) |
|
100 { |
|
101 newsize = ((offset>>DEFAULT_INCREMENT_LOG2) +1 ) << DEFAULT_INCREMENT_LOG2; |
|
102 set->bits = g_renew(guint32, set->bits, newsize); |
|
103 memset (set->bits + set->size, 0, sizeof(guint32) * (newsize - set->size)); |
|
104 set->size = newsize; |
|
105 g_assert(offset<newsize); |
|
106 } |
|
107 set->bits[offset] = set->bits[offset] | (1<<(element & 0x1f)); |
|
108 } |
|
109 |
|
110 /** |
|
111 * g_intset_remove: |
|
112 * @set: set |
|
113 * @element: integer to add |
|
114 * |
|
115 * Remove an integer from a GIntSet |
|
116 * Returns: TRUE if element was in set |
|
117 */ |
|
118 |
|
119 gboolean |
|
120 g_intset_remove (GIntSet *set, guint element) |
|
121 { |
|
122 guint offset; |
|
123 guint mask; |
|
124 |
|
125 g_return_val_if_fail (set != NULL, FALSE); |
|
126 |
|
127 offset = element >> 5; |
|
128 mask = 1 << (element & 0x1f); |
|
129 if (offset >= set->size) |
|
130 return FALSE; |
|
131 else if (!(set->bits[offset] & mask)) |
|
132 return FALSE; |
|
133 else |
|
134 { |
|
135 set->bits[offset] &= ~mask; |
|
136 return TRUE; |
|
137 } |
|
138 } |
|
139 |
|
140 /** |
|
141 * g_intset_is_member: |
|
142 * @set: set |
|
143 * @element: integer to test |
|
144 * |
|
145 * Tests if @element is a member of @set |
|
146 * Returns: TRUE if element was in set |
|
147 */ |
|
148 |
|
149 gboolean |
|
150 g_intset_is_member (const GIntSet *set, guint element) |
|
151 { |
|
152 guint offset; |
|
153 |
|
154 g_return_val_if_fail (set != NULL, FALSE); |
|
155 |
|
156 offset = element >> 5; |
|
157 if (offset >= set->size) |
|
158 return FALSE; |
|
159 else |
|
160 return (set->bits[offset] & (1 << (element & 0x1f))); |
|
161 } |
|
162 |
|
163 /** |
|
164 * g_intset_foreach: |
|
165 * @set: set |
|
166 * @func: @GIntFunc to use to iterate the set |
|
167 * @userdata: user data to pass to each call of @func |
|
168 * |
|
169 * Iterates every member of the set calling @func |
|
170 */ |
|
171 |
|
172 void |
|
173 g_intset_foreach (const GIntSet *set, GIntFunc func, gpointer userdata) |
|
174 { |
|
175 guint i, j; |
|
176 |
|
177 g_return_if_fail (set != NULL); |
|
178 g_return_if_fail (func != NULL); |
|
179 |
|
180 for (i = 0; i < set->size; i++) |
|
181 { |
|
182 if (set->bits[i]) |
|
183 for (j = 0; j < 32; j++) |
|
184 { |
|
185 if (set->bits[i] & 1 << j) |
|
186 func (i * 32 + j, userdata); |
|
187 } |
|
188 } |
|
189 } |
|
190 |
|
191 |
|
192 static void |
|
193 addint (guint32 i, gpointer data) |
|
194 { |
|
195 GArray *array = (GArray *) data; |
|
196 g_array_append_val (array, i); |
|
197 } |
|
198 |
|
199 /** |
|
200 * g_intset_to_array: |
|
201 * @set: set to convert |
|
202 * Convert a gintset to an array, allocates the array for you, hence you |
|
203 * must free it after use. |
|
204 */ |
|
205 |
|
206 GArray * |
|
207 g_intset_to_array (GIntSet *set) |
|
208 { |
|
209 GArray *array; |
|
210 |
|
211 g_return_val_if_fail (set != NULL, NULL); |
|
212 |
|
213 array = g_array_new (FALSE, TRUE, sizeof (guint32)); |
|
214 |
|
215 g_intset_foreach (set, addint, array); |
|
216 |
|
217 return array; |
|
218 } |
|
219 |
|
220 |
|
221 GIntSet * |
|
222 g_intset_from_array (GArray *array) |
|
223 { |
|
224 GIntSet *set; |
|
225 guint32 max, i; |
|
226 |
|
227 g_return_val_if_fail (array != NULL, NULL); |
|
228 |
|
229 /* look at the 1st, last and middle values in the array to get an |
|
230 * approximation of the largest */ |
|
231 max = 0; |
|
232 if (array->len > 0) |
|
233 max = g_array_index (array, guint32, 0); |
|
234 if (array->len > 1) |
|
235 max = MAX (max, g_array_index (array, guint32, array->len - 1)); |
|
236 if (array->len > 2) |
|
237 max = MAX (max, g_array_index (array, guint32, (array->len - 1) >> 1)); |
|
238 set = _g_intset_new_with_size (1 + (max >> 5)); |
|
239 |
|
240 for (i = 0; i < array->len; i++) |
|
241 { |
|
242 g_intset_add (set, g_array_index (array, guint32, i)); |
|
243 } |
|
244 |
|
245 return set; |
|
246 } |
|
247 |
|
248 |
|
249 guint |
|
250 g_intset_size (const GIntSet *set) |
|
251 { |
|
252 guint i, count = 0; |
|
253 guint32 n; |
|
254 |
|
255 g_return_val_if_fail (set != NULL, 0); |
|
256 |
|
257 for (i = 0; i < set->size; i++) |
|
258 { |
|
259 n = set->bits[i]; |
|
260 n = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111); |
|
261 count += ((n + (n >> 3)) & 030707070707) % 63; |
|
262 } |
|
263 |
|
264 return count; |
|
265 } |
|
266 |
|
267 |
|
268 gboolean |
|
269 g_intset_is_equal (const GIntSet *left, const GIntSet *right) |
|
270 { |
|
271 const GIntSet *large, *small; |
|
272 guint i; |
|
273 |
|
274 g_return_val_if_fail (left != NULL, FALSE); |
|
275 g_return_val_if_fail (right != NULL, FALSE); |
|
276 |
|
277 if (left->size > right->size) |
|
278 { |
|
279 large = left; |
|
280 small = right; |
|
281 } |
|
282 else |
|
283 { |
|
284 large = right; |
|
285 small = left; |
|
286 } |
|
287 |
|
288 for (i = 0; i < small->size; i++) |
|
289 { |
|
290 if (large->bits[i] != small->bits[i]) |
|
291 return FALSE; |
|
292 } |
|
293 |
|
294 for (i = small->size; i < large->size; i++) |
|
295 { |
|
296 if (large->bits[i] != 0) |
|
297 return FALSE; |
|
298 } |
|
299 |
|
300 return TRUE; |
|
301 } |
|
302 |
|
303 GIntSet * |
|
304 g_intset_copy (const GIntSet *orig) |
|
305 { |
|
306 GIntSet *ret; |
|
307 |
|
308 g_return_val_if_fail (orig != NULL, NULL); |
|
309 |
|
310 ret = _g_intset_new_with_size (orig->size); |
|
311 memcpy (ret->bits, orig->bits, (ret->size * sizeof (guint32))); |
|
312 |
|
313 return ret; |
|
314 } |
|
315 |
|
316 |
|
317 GIntSet * |
|
318 g_intset_intersection (const GIntSet *left, const GIntSet *right) |
|
319 { |
|
320 const GIntSet *large, *small; |
|
321 GIntSet *ret; |
|
322 guint i; |
|
323 |
|
324 g_return_val_if_fail (left != NULL, NULL); |
|
325 g_return_val_if_fail (right != NULL, NULL); |
|
326 |
|
327 if (left->size > right->size) |
|
328 { |
|
329 large = left; |
|
330 small = right; |
|
331 } |
|
332 else |
|
333 { |
|
334 large = right; |
|
335 small = left; |
|
336 } |
|
337 |
|
338 ret = g_intset_copy (small); |
|
339 |
|
340 for (i = 0; i < ret->size; i++) |
|
341 { |
|
342 ret->bits[i] &= large->bits[i]; |
|
343 } |
|
344 |
|
345 return ret; |
|
346 } |
|
347 |
|
348 |
|
349 GIntSet * |
|
350 g_intset_union (const GIntSet *left, const GIntSet *right) |
|
351 { |
|
352 const GIntSet *large, *small; |
|
353 GIntSet *ret; |
|
354 guint i; |
|
355 |
|
356 g_return_val_if_fail (left != NULL, NULL); |
|
357 g_return_val_if_fail (right != NULL, NULL); |
|
358 |
|
359 if (left->size > right->size) |
|
360 { |
|
361 large = left; |
|
362 small = right; |
|
363 } |
|
364 else |
|
365 { |
|
366 large = right; |
|
367 small = left; |
|
368 } |
|
369 |
|
370 ret = g_intset_copy (large); |
|
371 |
|
372 for (i = 0; i < small->size; i++) |
|
373 { |
|
374 ret->bits[i] |= small->bits[i]; |
|
375 } |
|
376 |
|
377 return ret; |
|
378 } |
|
379 |
|
380 |
|
381 GIntSet * |
|
382 g_intset_difference (const GIntSet *left, const GIntSet *right) |
|
383 { |
|
384 GIntSet *ret; |
|
385 guint i; |
|
386 |
|
387 g_return_val_if_fail (left != NULL, NULL); |
|
388 g_return_val_if_fail (right != NULL, NULL); |
|
389 |
|
390 ret = g_intset_copy (left); |
|
391 |
|
392 for (i = 0; i < MIN (right->size, left->size); i++) |
|
393 { |
|
394 ret->bits[i] &= ~right->bits[i]; |
|
395 } |
|
396 |
|
397 return ret; |
|
398 } |
|
399 |
|
400 |
|
401 GIntSet * |
|
402 g_intset_symmetric_difference (const GIntSet *left, const GIntSet *right) |
|
403 { |
|
404 const GIntSet *large, *small; |
|
405 GIntSet *ret; |
|
406 guint i; |
|
407 |
|
408 g_return_val_if_fail (left != NULL, NULL); |
|
409 g_return_val_if_fail (right != NULL, NULL); |
|
410 |
|
411 if (left->size > right->size) |
|
412 { |
|
413 large = left; |
|
414 small = right; |
|
415 } |
|
416 else |
|
417 { |
|
418 large = right; |
|
419 small = left; |
|
420 } |
|
421 |
|
422 ret = g_intset_copy (large); |
|
423 |
|
424 for (i = 0; i < small->size; i++) |
|
425 { |
|
426 ret->bits[i] ^= small->bits[i]; |
|
427 } |
|
428 |
|
429 return ret; |
|
430 } |
|
431 |
|
432 static void |
|
433 _dump_foreach (guint i, gpointer data) |
|
434 { |
|
435 GString *tmp = (GString *) data; |
|
436 |
|
437 if (tmp->len == 0) |
|
438 g_string_append_printf (tmp, "%d", i); |
|
439 else |
|
440 g_string_append_printf (tmp, " %d", i); |
|
441 } |
|
442 |
|
443 gchar * |
|
444 g_intset_dump (const GIntSet *set) |
|
445 { |
|
446 GString *tmp = g_string_new (""); |
|
447 |
|
448 g_intset_foreach (set, _dump_foreach, tmp); |
|
449 return g_string_free (tmp, FALSE); |
|
450 } |