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 }